1 package org.codehaus.aspectwerkz.util;
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64 import java.io.Externalizable;
65 import java.io.IOException;
66 import java.io.ObjectInput;
67 import java.io.ObjectOutput;
68 import java.util.AbstractCollection;
69 import java.util.AbstractSet;
70 import java.util.ArrayList;
71 import java.util.Collection;
72 import java.util.Collections;
73 import java.util.ConcurrentModificationException;
74 import java.util.HashMap;
75 import java.util.Iterator;
76 import java.util.List;
77 import java.util.Map;
78 import java.util.NoSuchElementException;
79 import java.util.Set;
80
81 /***
82 * A map of objects whose mapping entries are sequenced based on the order in which they were added. This data structure
83 * has fast <I>O(1) </I> search time, deletion time, and insertion time. <p/>
84 * <P>
85 * Although this map is sequenced, it cannot implement {@link java.util.List}because of incompatible interface
86 * definitions. The remove methods in List and Map have different return values (see:
87 * {@linkjava.util.List#remove(Object)}and {@link java.util.Map#remove(Object)}).<p/>
88 * <P>
89 * This class is not thread safe. When a thread safe implementation is required, use {@link
90 * Collections#synchronizedMap(Map)} as it is documented, or use explicit synchronization controls.
91 *
92 * @author <a href="mailto:mas@apache.org">Michael A. Smith </A>
93 * @author <a href="mailto:dlr@collab.net">Daniel Rall </a>
94 * @author <a href="mailto:hps@intermeta.de">Henning P. Schmiedehausen </a>
95 * @since 2.0
96 */
97 public class SequencedHashMap implements Map, Cloneable, Externalizable {
98
99 private static final int KEY = 0;
100
101 private static final int VALUE = 1;
102
103 private static final int ENTRY = 2;
104
105 private static final int REMOVED_MASK = 0x80000000;
106
107
108
109 private static final long serialVersionUID = 3380552487888102930L;
110
111 /***
112 * Sentinel used to hold the head and tail of the list of entries.
113 */
114 private Entry sentinel;
115
116 /***
117 * Map of keys to entries
118 */
119 private HashMap entries;
120
121 /***
122 * Holds the number of modifications that have occurred to the map, excluding modifications made through a
123 * collection view's iterator (e.g. entrySet().iterator().remove()). This is used to create a fail-fast behavior
124 * with the iterators.
125 */
126 private transient long modCount = 0;
127
128 /***
129 * Construct a new sequenced hash map with default initial size and load factor.
130 */
131 public SequencedHashMap() {
132 sentinel = createSentinel();
133 entries = new HashMap();
134 }
135
136 /***
137 * Construct a new sequenced hash map with the specified initial size and default load factor.
138 *
139 * @param initialSize the initial size for the hash table
140 * @see HashMap#HashMap(int)
141 */
142 public SequencedHashMap(int initialSize) {
143 sentinel = createSentinel();
144 entries = new HashMap(initialSize);
145 }
146
147 /***
148 * Construct a new sequenced hash map with the specified initial size and load factor.
149 *
150 * @param initialSize the initial size for the hash table
151 * @param loadFactor the load factor for the hash table.
152 * @see HashMap#HashMap(int,float)
153 */
154 public SequencedHashMap(int initialSize, float loadFactor) {
155 sentinel = createSentinel();
156 entries = new HashMap(initialSize, loadFactor);
157 }
158
159 /***
160 * Construct a new sequenced hash map and add all the elements in the specified map. The order in which the mappings
161 * in the specified map are added is defined by {@link #putAll(Map)}.
162 */
163 public SequencedHashMap(Map m) {
164 this();
165 putAll(m);
166 }
167
168 /***
169 * Construct an empty sentinel used to hold the head (sentinel.next) and the tail (sentinel.prev) of the list. The
170 * sentinal has a <code>null</code> key and value.
171 */
172 private static final Entry createSentinel() {
173 Entry s = new Entry(null, null);
174 s.prev = s;
175 s.next = s;
176 return s;
177 }
178
179 /***
180 * Removes an internal entry from the linked list. This does not remove it from the underlying map.
181 */
182 private void removeEntry(Entry entry) {
183 entry.next.prev = entry.prev;
184 entry.prev.next = entry.next;
185 }
186
187 /***
188 * Inserts a new internal entry to the tail of the linked list. This does not add the entry to the underlying map.
189 */
190 private void insertEntry(Entry entry) {
191 entry.next = sentinel;
192 entry.prev = sentinel.prev;
193 sentinel.prev.next = entry;
194 sentinel.prev = entry;
195 }
196
197
198
199 /***
200 * Implements {@link Map#size()}.
201 */
202 public int size() {
203
204 return entries.size();
205 }
206
207 /***
208 * Implements {@link Map#isEmpty()}.
209 */
210 public boolean isEmpty() {
211
212
213 return sentinel.next == sentinel;
214 }
215
216 /***
217 * Implements {@link Map#containsKey(Object)}.
218 */
219 public boolean containsKey(Object key) {
220
221 return entries.containsKey(key);
222 }
223
224 /***
225 * Implements {@link Map#containsValue(Object)}.
226 */
227 public boolean containsValue(Object value) {
228
229
230
231
232
233
234
235 if (value == null) {
236 for (Entry pos = sentinel.next; pos != sentinel; pos = pos.next) {
237 if (pos.getValue() == null) {
238 return true;
239 }
240 }
241 } else {
242 for (Entry pos = sentinel.next; pos != sentinel; pos = pos.next) {
243 if (value.equals(pos.getValue())) {
244 return true;
245 }
246 }
247 }
248 return false;
249 }
250
251 /***
252 * Implements {@link Map#get(Object)}.
253 */
254 public Object get(Object o) {
255
256 Entry entry = (Entry) entries.get(o);
257 if (entry == null) {
258 return null;
259 }
260 return entry.getValue();
261 }
262
263 /***
264 * Return the entry for the "oldest" mapping. That is, return the Map.Entry for the key-value pair that was first
265 * put into the map when compared to all the other pairings in the map. This behavior is equivalent to using
266 * <code>entrySet().iterator().next()</code>, but this method provides an optimized implementation.
267 *
268 * @return The first entry in the sequence, or <code>null</code> if the map is empty.
269 */
270 public Map.Entry getFirst() {
271
272
273
274 return (isEmpty()) ? null : sentinel.next;
275 }
276
277 /***
278 * Return the key for the "oldest" mapping. That is, return the key for the mapping that was first put into the map
279 * when compared to all the other objects in the map. This behavior is equivalent to using
280 * <code>getFirst().getKey()</code>, but this method provides a slightly optimized implementation.
281 *
282 * @return The first key in the sequence, or <code>null</code> if the map is empty.
283 */
284 public Object getFirstKey() {
285
286
287
288
289
290
291 return sentinel.next.getKey();
292 }
293
294 /***
295 * Return the value for the "oldest" mapping. That is, return the value for the mapping that was first put into the
296 * map when compared to all the other objects in the map. This behavior is equivalent to using
297 * <code>getFirst().getValue()</code>, but this method provides a slightly optimized implementation.
298 *
299 * @return The first value in the sequence, or <code>null</code> if the map is empty.
300 */
301 public Object getFirstValue() {
302
303
304
305
306
307
308 return sentinel.next.getValue();
309 }
310
311 /***
312 * Return the entry for the "newest" mapping. That is, return the Map.Entry for the key-value pair that was first
313 * put into the map when compared to all the other pairings in the map. The behavior is equivalent to: <p/>
314 * <p/>
315 * <pre>
316 * Object obj = null;
317 * Iterator iter = entrySet().iterator();
318 * while (iter.hasNext()) {
319 * obj = iter.next();
320 * }
321 * return (Map.Entry) obj;
322 * </pre>
323 * <p/>
324 * <p/>However, the implementation of this method ensures an O(1) lookup of the last key rather than O(n).
325 *
326 * @return The last entry in the sequence, or <code>null</code> if the map is empty.
327 */
328 public Map.Entry getLast() {
329
330
331
332 return (isEmpty()) ? null : sentinel.prev;
333 }
334
335 /***
336 * Return the key for the "newest" mapping. That is, return the key for the mapping that was last put into the map
337 * when compared to all the other objects in the map. This behavior is equivalent to using
338 * <code>getLast().getKey()</code>, but this method provides a slightly optimized implementation.
339 *
340 * @return The last key in the sequence, or <code>null</code> if the map is empty.
341 */
342 public Object getLastKey() {
343
344
345
346
347
348
349 return sentinel.prev.getKey();
350 }
351
352 /***
353 * Return the value for the "newest" mapping. That is, return the value for the mapping that was last put into the
354 * map when compared to all the other objects in the map. This behavior is equivalent to using
355 * <code>getLast().getValue()</code>, but this method provides a slightly optimized implementation.
356 *
357 * @return The last value in the sequence, or <code>null</code> if the map is empty.
358 */
359 public Object getLastValue() {
360
361
362
363
364
365
366 return sentinel.prev.getValue();
367 }
368
369 /***
370 * Implements {@link Map#put(Object, Object)}.
371 */
372 public Object put(Object key, Object value) {
373 modCount++;
374 Object oldValue = null;
375
376
377 Entry e = (Entry) entries.get(key);
378
379
380 if (e != null) {
381
382 removeEntry(e);
383
384
385 oldValue = e.setValue(value);
386
387
388
389
390
391
392 } else {
393
394 e = new Entry(key, value);
395 entries.put(key, e);
396 }
397
398
399
400 insertEntry(e);
401 return oldValue;
402 }
403
404 /***
405 * Implements {@link Map#remove(Object)}.
406 */
407 public Object remove(Object key) {
408 Entry e = removeImpl(key);
409 return (e == null) ? null : e.getValue();
410 }
411
412 /***
413 * Fully remove an entry from the map, returning the old entry or null if there was no such entry with the specified
414 * key.
415 */
416 private Entry removeImpl(Object key) {
417 Entry e = (Entry) entries.remove(key);
418 if (e == null) {
419 return null;
420 }
421 modCount++;
422 removeEntry(e);
423 return e;
424 }
425
426 /***
427 * Adds all the mappings in the specified map to this map, replacing any mappings that already exist (as per
428 * {@linkMap#putAll(Map)}). The order in which the entries are added is determined by the iterator returned from
429 * {@linkMap#entrySet()}for the specified map.
430 *
431 * @param t the mappings that should be added to this map.
432 * @throws NullPointerException if <code>t</code> is <code>null</code>
433 */
434 public void putAll(Map t) {
435 Iterator iter = t.entrySet().iterator();
436 while (iter.hasNext()) {
437 Map.Entry entry = (Map.Entry) iter.next();
438 put(entry.getKey(), entry.getValue());
439 }
440 }
441
442 /***
443 * Implements {@link Map#clear()}.
444 */
445 public void clear() {
446 modCount++;
447
448
449 entries.clear();
450
451
452 sentinel.next = sentinel;
453 sentinel.prev = sentinel;
454 }
455
456 /***
457 * Implements {@link Map#equals(Object)}.
458 */
459 public boolean equals(Object obj) {
460 if (obj == null) {
461 return false;
462 }
463 if (obj == this) {
464 return true;
465 }
466 if (!(obj instanceof Map)) {
467 return false;
468 }
469 return entrySet().equals(((Map) obj).entrySet());
470 }
471
472 /***
473 * Implements {@link Map#hashCode()}.
474 */
475 public int hashCode() {
476 return entrySet().hashCode();
477 }
478
479 /***
480 * Provides a string representation of the entries within the map. The format of the returned string may change with
481 * different releases, so this method is suitable for debugging purposes only. If a specific format is required, use
482 * {@link #entrySet()}.{@link Set#iterator() iterator()}and iterate over the entries in the map formatting them
483 * as appropriate.
484 */
485 public String toString() {
486 StringBuffer buf = new StringBuffer();
487 buf.append('[');
488 for (Entry pos = sentinel.next; pos != sentinel; pos = pos.next) {
489 buf.append(pos.getKey());
490 buf.append('=');
491 buf.append(pos.getValue());
492 if (pos.next != sentinel) {
493 buf.append(',');
494 }
495 }
496 buf.append(']');
497 return buf.toString();
498 }
499
500 /***
501 * Implements {@link Map#keySet()}.
502 */
503 public Set keySet() {
504 return new AbstractSet() {
505
506 public Iterator iterator() {
507 return new OrderedIterator(KEY);
508 }
509
510 public boolean remove(Object o) {
511 Entry e = SequencedHashMap.this.removeImpl(o);
512 return (e != null);
513 }
514
515
516 public void clear() {
517 SequencedHashMap.this.clear();
518 }
519
520 public int size() {
521 return SequencedHashMap.this.size();
522 }
523
524 public boolean isEmpty() {
525 return SequencedHashMap.this.isEmpty();
526 }
527
528 public boolean contains(Object o) {
529 return SequencedHashMap.this.containsKey(o);
530 }
531 };
532 }
533
534 /***
535 * Implements {@link Map#values()}.
536 */
537 public Collection values() {
538 return new AbstractCollection() {
539
540 public Iterator iterator() {
541 return new OrderedIterator(VALUE);
542 }
543
544 public boolean remove(Object value) {
545
546
547
548 if (value == null) {
549 for (Entry pos = sentinel.next; pos != sentinel; pos = pos.next) {
550 if (pos.getValue() == null) {
551 SequencedHashMap.this.removeImpl(pos.getKey());
552 return true;
553 }
554 }
555 } else {
556 for (Entry pos = sentinel.next; pos != sentinel; pos = pos.next) {
557 if (value.equals(pos.getValue())) {
558 SequencedHashMap.this.removeImpl(pos.getKey());
559 return true;
560 }
561 }
562 }
563 return false;
564 }
565
566
567 public void clear() {
568 SequencedHashMap.this.clear();
569 }
570
571 public int size() {
572 return SequencedHashMap.this.size();
573 }
574
575 public boolean isEmpty() {
576 return SequencedHashMap.this.isEmpty();
577 }
578
579 public boolean contains(Object o) {
580 return SequencedHashMap.this.containsValue(o);
581 }
582 };
583 }
584
585 /***
586 * Implements {@link Map#entrySet()}.
587 */
588 public Set entrySet() {
589 return new AbstractSet() {
590
591 private Entry findEntry(Object o) {
592 if (o == null) {
593 return null;
594 }
595 if (!(o instanceof Map.Entry)) {
596 return null;
597 }
598 Map.Entry e = (Map.Entry) o;
599 Entry entry = (Entry) entries.get(e.getKey());
600 if ((entry != null) && entry.equals(e)) {
601 return entry;
602 } else {
603 return null;
604 }
605 }
606
607
608 public Iterator iterator() {
609 return new OrderedIterator(ENTRY);
610 }
611
612 public boolean remove(Object o) {
613 Entry e = findEntry(o);
614 if (e == null) {
615 return false;
616 }
617 return SequencedHashMap.this.removeImpl(e.getKey()) != null;
618 }
619
620
621 public void clear() {
622 SequencedHashMap.this.clear();
623 }
624
625 public int size() {
626 return SequencedHashMap.this.size();
627 }
628
629 public boolean isEmpty() {
630 return SequencedHashMap.this.isEmpty();
631 }
632
633 public boolean contains(Object o) {
634 return findEntry(o) != null;
635 }
636 };
637 }
638
639
640
641
642 /***
643 * Creates a shallow copy of this object, preserving the internal structure by copying only references. The keys and
644 * values themselves are not <code>clone()</code> 'd. The cloned object maintains the same sequence.
645 *
646 * @return A clone of this instance.
647 * @throws CloneNotSupportedException if clone is not supported by a subclass.
648 */
649 public Object clone() throws CloneNotSupportedException {
650
651
652
653
654 SequencedHashMap map = (SequencedHashMap) super.clone();
655
656
657 map.sentinel = createSentinel();
658
659
660
661 map.entries = new HashMap();
662
663
664 map.putAll(this);
665
666
667
668
669
670
671
672
673 return map;
674 }
675
676 /***
677 * Returns the Map.Entry at the specified index
678 *
679 * @throws ArrayIndexOutOfBoundsException if the specified index is <code>< 0</code> or <code>></code> the
680 * size of the map.
681 */
682 private Map.Entry getEntry(int index) {
683 Entry pos = sentinel;
684 if (index < 0) {
685 throw new ArrayIndexOutOfBoundsException(index + " < 0");
686 }
687
688
689 int i = -1;
690 while ((i < (index - 1)) && (pos.next != sentinel)) {
691 i++;
692 pos = pos.next;
693 }
694
695
696
697 if (pos.next == sentinel) {
698 throw new ArrayIndexOutOfBoundsException(index + " >= " + (i + 1));
699 }
700 return pos.next;
701 }
702
703 /***
704 * Returns the key at the specified index.
705 *
706 * @throws ArrayIndexOutOfBoundsException if the <code>index</code> is <code>< 0</code> or <code>></code>
707 * the size of the map.
708 */
709 public Object get(int index) {
710 return getEntry(index).getKey();
711 }
712
713 /***
714 * Returns the value at the specified index.
715 *
716 * @throws ArrayIndexOutOfBoundsException if the <code>index</code> is <code>< 0</code> or <code>></code>
717 * the size of the map.
718 */
719 public Object getValue(int index) {
720 return getEntry(index).getValue();
721 }
722
723 /***
724 * Returns the index of the specified key.
725 */
726 public int indexOf(Object key) {
727 Entry e = (Entry) entries.get(key);
728 int pos = 0;
729 while (e.prev != sentinel) {
730 pos++;
731 e = e.prev;
732 }
733 return pos;
734 }
735
736 /***
737 * Returns a key iterator.
738 */
739 public Iterator iterator() {
740 return keySet().iterator();
741 }
742
743 /***
744 * Returns the last index of the specified key.
745 */
746 public int lastIndexOf(Object key) {
747
748 return indexOf(key);
749 }
750
751 /***
752 * Returns a List view of the keys rather than a set view. The returned list is unmodifiable. This is required
753 * because changes to the values of the list (using {@link java.util.ListIterator#set(Object)}) will effectively
754 * remove the value from the list and reinsert that value at the end of the list, which is an unexpected side effect
755 * of changing the value of a list. This occurs because changing the key, changes when the mapping is added to the
756 * map and thus where it appears in the list. <p/>
757 * <P>
758 * An alternative to this method is to use {@link #keySet()}
759 *
760 * @return The ordered list of keys.
761 * @see #keySet()
762 */
763 public List sequence() {
764 List l = new ArrayList(size());
765 Iterator iter = keySet().iterator();
766 while (iter.hasNext()) {
767 l.add(iter.next());
768 }
769 return Collections.unmodifiableList(l);
770 }
771
772 /***
773 * Removes the element at the specified index.
774 *
775 * @param index The index of the object to remove.
776 * @return The previous value coressponding the <code>key</code>, or <code>null</code> if none existed.
777 * @throws ArrayIndexOutOfBoundsException if the <code>index</code> is <code>< 0</code> or <code>></code>
778 * the size of the map.
779 */
780 public Object remove(int index) {
781 return remove(get(index));
782 }
783
784
785
786 /***
787 * Deserializes this map from the given stream.
788 *
789 * @param in the stream to deserialize from
790 * @throws IOException if the stream raises it
791 * @throws ClassNotFoundException if the stream raises it
792 */
793 public void readExternal(ObjectInput in) throws IOException, ClassNotFoundException {
794 int size = in.readInt();
795 for (int i = 0; i < size; i++) {
796 Object key = in.readObject();
797 Object value = in.readObject();
798 put(key, value);
799 }
800 }
801
802 /***
803 * Serializes this map to the given stream.
804 *
805 * @param out the stream to serialize to
806 * @throws IOException if the stream raises it
807 */
808 public void writeExternal(ObjectOutput out) throws IOException {
809 out.writeInt(size());
810 for (Entry pos = sentinel.next; pos != sentinel; pos = pos.next) {
811 out.writeObject(pos.getKey());
812 out.writeObject(pos.getValue());
813 }
814 }
815
816 /***
817 * {@link java.util.Map.Entry}that doubles as a node in the linked list of sequenced mappings.
818 */
819 private static class Entry implements Map.Entry {
820
821
822
823
824
825
826
827
828
829 private final Object key;
830
831 private Object value;
832
833
834
835 Entry next = null;
836
837 Entry prev = null;
838
839 public Entry(Object key, Object value) {
840 this.key = key;
841 this.value = value;
842 }
843
844
845 public Object getKey() {
846 return this.key;
847 }
848
849
850 public Object getValue() {
851 return this.value;
852 }
853
854
855 public Object setValue(Object value) {
856 Object oldValue = this.value;
857 this.value = value;
858 return oldValue;
859 }
860
861 public int hashCode() {
862
863 return (((getKey() == null) ? 0 : getKey().hashCode()) ^
864 ((getValue() == null) ? 0 : getValue().hashCode()));
865 }
866
867 public boolean equals(Object obj) {
868 if (obj == null) {
869 return false;
870 }
871 if (obj == this) {
872 return true;
873 }
874 if (!(obj instanceof Map.Entry)) {
875 return false;
876 }
877 Map.Entry other = (Map.Entry) obj;
878
879
880 return (((getKey() == null) ? (other.getKey() == null) : getKey().equals(other.getKey())) && ((getValue() ==
881 null)
882 ?
883 (other.getValue() ==
884 null)
885 :
886 getValue()
887 .equals(other.getValue())));
888 }
889
890 public String toString() {
891 return "[" + getKey() + '=' + getValue() + ']';
892 }
893 }
894
895 private class OrderedIterator implements Iterator {
896 /***
897 * Holds the type that should be returned from the iterator. The value should be either {@link #KEY},
898 * {@link#VALUE}, or {@link #ENTRY}. To save a tiny bit of memory, this field is also used as a marker for
899 * when remove has been called on the current object to prevent a second remove on the same element.
900 * Essientially, if this value is negative (i.e. the bit specified by {@link #REMOVED_MASK}is set), the current
901 * position has been removed. If positive, remove can still be called.
902 */
903 private int returnType;
904
905 /***
906 * Holds the "current" position in the iterator. When pos.next is the sentinel, we've reached the end of the
907 * list.
908 */
909 private Entry pos = sentinel;
910
911 /***
912 * Holds the expected modification count. If the actual modification count of the map differs from this value,
913 * then a concurrent modification has occurred.
914 */
915 private transient long expectedModCount = modCount;
916
917 /***
918 * Construct an iterator over the sequenced elements in the order in which they were added. The {@link #next()}
919 * method returns the type specified by <code>returnType</code> which must be either {@link #KEY},
920 * {@link#VALUE}, or {@link #ENTRY}.
921 */
922 public OrderedIterator(int returnType) {
923
924
925
926
927
928
929
930
931
932 this.returnType = returnType | REMOVED_MASK;
933 }
934
935 /***
936 * Returns whether there is any additional elements in the iterator to be returned.
937 *
938 * @return <code>true</code> if there are more elements left to be returned from the iterator;
939 * <code>false</code> otherwise.
940 */
941 public boolean hasNext() {
942 return pos.next != sentinel;
943 }
944
945 /***
946 * Returns the next element from the iterator.
947 *
948 * @return the next element from the iterator.
949 * @throws NoSuchElementException if there are no more elements in the iterator.
950 * @throws ConcurrentModificationException
951 * if a modification occurs in the underlying map.
952 */
953 public Object next() {
954 if (modCount != expectedModCount) {
955 throw new ConcurrentModificationException();
956 }
957 if (pos.next == sentinel) {
958 throw new NoSuchElementException();
959 }
960
961
962 returnType = returnType & ~REMOVED_MASK;
963 pos = pos.next;
964 switch (returnType) {
965 case KEY:
966 return pos.getKey();
967 case VALUE:
968 return pos.getValue();
969 case ENTRY:
970 return pos;
971 default:
972
973
974 throw new Error("bad iterator type: " + returnType);
975 }
976 }
977
978 /***
979 * Removes the last element returned from the {@link #next()}method from the sequenced map.
980 *
981 * @throws IllegalStateException if there isn't a "last element" to be removed. That is, if {@link #next()}has
982 * never been called, or if {@link #remove()}was already called on the element.
983 * @throws ConcurrentModificationException
984 * if a modification occurs in the underlying map.
985 */
986 public void remove() {
987 if ((returnType & REMOVED_MASK) != 0) {
988 throw new IllegalStateException("remove() must follow next()");
989 }
990 if (modCount != expectedModCount) {
991 throw new ConcurrentModificationException();
992 }
993 SequencedHashMap.this.removeImpl(pos.getKey());
994
995
996 expectedModCount++;
997
998
999 returnType = returnType | REMOVED_MASK;
1000 }
1001 }
1002 }