Java > Open Source Codes > com > tc > aspectwerkz > util > SequencedHashMap


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

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags