001: /*
002: * All content copyright (c) 2003-2006 Terracotta, Inc., except as may otherwise be noted in a separate copyright notice. All rights reserved.
003: */
004:
005: package com.tc.aspectwerkz.util;
006:
007: import java.io.Externalizable;
008: import java.io.IOException;
009: import java.io.ObjectInput;
010: import java.io.ObjectOutput;
011: import java.util.AbstractCollection;
012: import java.util.AbstractSet;
013: import java.util.ArrayList;
014: import java.util.Collection;
015: import java.util.Collections;
016: import java.util.ConcurrentModificationException;
017: import java.util.HashMap;
018: import java.util.Iterator;
019: import java.util.List;
020: import java.util.Map;
021: import java.util.NoSuchElementException;
022: import java.util.Set;
023:
024: /**
025: * A map of objects whose mapping entries are sequenced based on the order in which they were added. This data structure
026: * has fast <I>O(1) </I> search time, deletion time, and insertion time. <p/>
027: * <p/>
028: * Although this map is sequenced, it cannot implement {@link java.util.List}because of incompatible interface
029: * definitions. The remove methods in List and Map have different return values (see:
030: * {@linkjava.util.List#remove(Object)}and {@link java.util.Map#remove(Object)}).<p/>
031: * <p/>
032: * This class is not thread safe. When a thread safe implementation is required, use {@link
033: * Collections#synchronizedMap(Map)} as it is documented, or use explicit synchronization controls.
034: *
035: * @author <a href="mailto:mas@apache.org">Michael A. Smith </A>
036: * @author <a href="mailto:dlr@collab.net">Daniel Rall </a>
037: * @author <a href="mailto:hps@intermeta.de">Henning P. Schmiedehausen </a>
038: * @since 2.0
039: */
040: public class SequencedHashMap implements Map, Cloneable, Externalizable {
041: // constants to define what the iterator should return on "next"
042: private static final int KEY = 0;
043:
044: private static final int VALUE = 1;
045:
046: private static final int ENTRY = 2;
047:
048: private static final int REMOVED_MASK = 0x80000000;
049:
050: // add a serial version uid, so that if we change things in the future
051: // without changing the format, we can still deserialize properly.
052: private static final long serialVersionUID = 3380552487888102930L;
053:
054: /**
055: * Sentinel used to hold the head and tail of the list of entries.
056: */
057: private Entry sentinel;
058:
059: /**
060: * Map of keys to entries
061: */
062: private HashMap entries;
063:
064: /**
065: * Holds the number of modifications that have occurred to the map, excluding modifications made through a
066: * collection view's iterator (e.g. entrySet().iterator().remove()). This is used to create a fail-fast behavior
067: * with the iterators.
068: */
069: private transient long modCount = 0;
070:
071: /**
072: * Construct a new sequenced hash map with default initial size and load factor.
073: */
074: public SequencedHashMap() {
075: sentinel = createSentinel();
076: entries = new HashMap();
077: }
078:
079: /**
080: * Construct a new sequenced hash map with the specified initial size and default load factor.
081: *
082: * @param initialSize the initial size for the hash table
083: * @see HashMap#HashMap(int)
084: */
085: public SequencedHashMap(int initialSize) {
086: sentinel = createSentinel();
087: entries = new HashMap(initialSize);
088: }
089:
090: /**
091: * Construct a new sequenced hash map with the specified initial size and load factor.
092: *
093: * @param initialSize the initial size for the hash table
094: * @param loadFactor the load factor for the hash table.
095: * @see HashMap#HashMap(int,float)
096: */
097: public SequencedHashMap(int initialSize, float loadFactor) {
098: sentinel = createSentinel();
099: 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
495: .getKey());
496: return true;
497: }
498: }
499: } else {
500: for (Entry pos = sentinel.next; pos != sentinel; pos = pos.next) {
501: if (value.equals(pos.getValue())) {
502: SequencedHashMap.this .removeImpl(pos
503: .getKey());
504: return true;
505: }
506: }
507: }
508: return false;
509: }
510:
511: // more efficient impls than abstract collection
512: public void clear() {
513: SequencedHashMap.this .clear();
514: }
515:
516: public int size() {
517: return SequencedHashMap.this .size();
518: }
519:
520: public boolean isEmpty() {
521: return SequencedHashMap.this .isEmpty();
522: }
523:
524: public boolean contains(Object o) {
525: return SequencedHashMap.this .containsValue(o);
526: }
527: };
528: }
529:
530: /**
531: * Implements {@link Map#entrySet()}.
532: */
533: public Set entrySet() {
534: return new AbstractSet() {
535: // helper
536: private Entry findEntry(Object o) {
537: if (o == null) {
538: return null;
539: }
540: if (!(o instanceof Map.Entry)) {
541: return null;
542: }
543: Map.Entry e = (Map.Entry) o;
544: Entry entry = (Entry) entries.get(e.getKey());
545: if ((entry != null) && entry.equals(e)) {
546: return entry;
547: } else {
548: return null;
549: }
550: }
551:
552: // required impl
553: public Iterator iterator() {
554: return new OrderedIterator(ENTRY);
555: }
556:
557: public boolean remove(Object o) {
558: Entry e = findEntry(o);
559: if (e == null) {
560: return false;
561: }
562: return SequencedHashMap.this .removeImpl(e.getKey()) != null;
563: }
564:
565: // more efficient impls than abstract collection
566: public void clear() {
567: SequencedHashMap.this .clear();
568: }
569:
570: public int size() {
571: return SequencedHashMap.this .size();
572: }
573:
574: public boolean isEmpty() {
575: return SequencedHashMap.this .isEmpty();
576: }
577:
578: public boolean contains(Object o) {
579: return findEntry(o) != null;
580: }
581: };
582: }
583:
584: // APIs maintained from previous version of SequencedHashMap for backwards
585: // compatibility
586:
587: /**
588: * Creates a shallow copy of this object, preserving the internal structure by copying only references. The keys and
589: * values themselves are not <code>clone()</code> 'd. The cloned object maintains the same sequence.
590: *
591: * @return A clone of this instance.
592: * @throws CloneNotSupportedException if clone is not supported by a subclass.
593: */
594: public Object clone() throws CloneNotSupportedException {
595: // yes, calling super.clone() silly since we're just blowing away all
596: // the stuff that super might be doing anyway, but for motivations on
597: // this, see:
598: // http://www.javaworld.com/javaworld/jw-01-1999/jw-01-object.html
599: SequencedHashMap map = (SequencedHashMap) super .clone();
600:
601: // create new, empty sentinel
602: map.sentinel = createSentinel();
603:
604: // create a new, empty entry map
605: // note: this does not preserve the initial capacity and load factor.
606: map.entries = new HashMap();
607:
608: // add all the mappings
609: map.putAll(this );
610:
611: // Note: We cannot just clone the hashmap and sentinel because we must
612: // duplicate our internal structures. Cloning those two will not clone all
613: // the other entries they reference, and so the cloned hash map will not be
614: // able to maintain internal consistency because there are two objects with
615: // the same entries. See discussion in the Entry implementation on why we
616: // cannot implement a clone of the Entry (and thus why we need to recreate
617: // everything).
618: return map;
619: }
620:
621: /**
622: * Returns the Map.Entry at the specified index
623: *
624: * @throws ArrayIndexOutOfBoundsException if the specified index is <code>< 0</code> or <code>></code> the
625: * size of the map.
626: */
627: private Map.Entry getEntry(int index) {
628: Entry pos = sentinel;
629: if (index < 0) {
630: throw new ArrayIndexOutOfBoundsException(index + " < 0");
631: }
632:
633: // loop to one before the position
634: int i = -1;
635: while ((i < (index - 1)) && (pos.next != sentinel)) {
636: i++;
637: pos = pos.next;
638: }
639:
640: // pos.next is the requested position
641: // if sentinel is next, past end of list
642: if (pos.next == sentinel) {
643: throw new ArrayIndexOutOfBoundsException(index + " >= "
644: + (i + 1));
645: }
646: return pos.next;
647: }
648:
649: /**
650: * Returns the key at the specified index.
651: *
652: * @throws ArrayIndexOutOfBoundsException if the <code>index</code> is <code>< 0</code> or <code>></code>
653: * the size of the map.
654: */
655: public Object get(int index) {
656: return getEntry(index).getKey();
657: }
658:
659: /**
660: * Returns the value at the specified index.
661: *
662: * @throws ArrayIndexOutOfBoundsException if the <code>index</code> is <code>< 0</code> or <code>></code>
663: * the size of the map.
664: */
665: public Object getValue(int index) {
666: return getEntry(index).getValue();
667: }
668:
669: /**
670: * Returns the index of the specified key.
671: */
672: public int indexOf(Object key) {
673: Entry e = (Entry) entries.get(key);
674: int pos = 0;
675: while (e.prev != sentinel) {
676: pos++;
677: e = e.prev;
678: }
679: return pos;
680: }
681:
682: /**
683: * Returns a key iterator.
684: */
685: public Iterator iterator() {
686: return keySet().iterator();
687: }
688:
689: /**
690: * Returns the last index of the specified key.
691: */
692: public int lastIndexOf(Object key) {
693: // keys in a map are guarunteed to be unique
694: return indexOf(key);
695: }
696:
697: /**
698: * Returns a List view of the keys rather than a set view. The returned list is unmodifiable. This is required
699: * because changes to the values of the list (using {@link java.util.ListIterator#set(Object)}) will effectively
700: * remove the value from the list and reinsert that value at the end of the list, which is an unexpected side effect
701: * of changing the value of a list. This occurs because changing the key, changes when the mapping is added to the
702: * map and thus where it appears in the list. <p/>
703: * <p/>
704: * An alternative to this method is to use {@link #keySet()}
705: *
706: * @return The ordered list of keys.
707: * @see #keySet()
708: */
709: public List sequence() {
710: List l = new ArrayList(size());
711: Iterator iter = keySet().iterator();
712: while (iter.hasNext()) {
713: l.add(iter.next());
714: }
715: return Collections.unmodifiableList(l);
716: }
717:
718: /**
719: * Removes the element at the specified index.
720: *
721: * @param index The index of the object to remove.
722: * @return The previous value coressponding the <code>key</code>, or <code>null</code> if none existed.
723: * @throws ArrayIndexOutOfBoundsException if the <code>index</code> is <code>< 0</code> or <code>></code>
724: * the size of the map.
725: */
726: public Object remove(int index) {
727: return remove(get(index));
728: }
729:
730: // per Externalizable.readExternal(ObjectInput)
731:
732: /**
733: * Deserializes this map from the given stream.
734: *
735: * @param in the stream to deserialize from
736: * @throws IOException if the stream raises it
737: * @throws ClassNotFoundException if the stream raises it
738: */
739: public void readExternal(ObjectInput in) throws IOException,
740: ClassNotFoundException {
741: int size = in.readInt();
742: for (int i = 0; i < size; i++) {
743: Object key = in.readObject();
744: Object value = in.readObject();
745: put(key, value);
746: }
747: }
748:
749: /**
750: * Serializes this map to the given stream.
751: *
752: * @param out the stream to serialize to
753: * @throws IOException if the stream raises it
754: */
755: public void writeExternal(ObjectOutput out) throws IOException {
756: out.writeInt(size());
757: for (Entry pos = sentinel.next; pos != sentinel; pos = pos.next) {
758: out.writeObject(pos.getKey());
759: out.writeObject(pos.getValue());
760: }
761: }
762:
763: /**
764: * {@link java.util.Map.Entry}that doubles as a node in the linked list of sequenced mappings.
765: */
766: private static class Entry implements Map.Entry {
767: // Note: This class cannot easily be made clonable. While the actual
768: // implementation of a clone would be simple, defining the semantics is
769: // difficult. If a shallow clone is implemented, then entry.next.prev !=
770: // entry, which is unintuitive and probably breaks all sorts of assumptions
771: // in code that uses this implementation. If a deep clone is
772: // implementated, then what happens when the linked list is cyclical (as is
773: // the case with SequencedHashMap)? It's impossible to know in the clone
774: // when to stop cloning, and thus you end up in a recursive loop,
775: // continuously cloning the "next" in the list.
776: private final Object key;
777:
778: private Object value;
779:
780: // package private to allow the SequencedHashMap to access and manipulate
781: // them.
782: Entry next = null;
783:
784: Entry prev = null;
785:
786: public Entry(Object key, Object value) {
787: this .key = key;
788: this .value = value;
789: }
790:
791: // per Map.Entry.getKey()
792: public Object getKey() {
793: return this .key;
794: }
795:
796: // per Map.Entry.getValue()
797: public Object getValue() {
798: return this .value;
799: }
800:
801: // per Map.Entry.setValue()
802: public Object setValue(Object value) {
803: Object oldValue = this .value;
804: this .value = value;
805: return oldValue;
806: }
807:
808: public int hashCode() {
809: // implemented per api docs for Map.Entry.hashCode()
810: return (((getKey() == null) ? 0 : getKey().hashCode()) ^ ((getValue() == null) ? 0
811: : getValue().hashCode()));
812: }
813:
814: public boolean equals(Object obj) {
815: if (obj == null) {
816: return false;
817: }
818: if (obj == this ) {
819: return true;
820: }
821: if (!(obj instanceof Map.Entry)) {
822: return false;
823: }
824: Map.Entry other = (Map.Entry) obj;
825:
826: // implemented per api docs for Map.Entry.equals(Object)
827: return (((getKey() == null) ? (other.getKey() == null)
828: : getKey().equals(other.getKey())) && ((getValue() == null) ? (other
829: .getValue() == null)
830: : getValue().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(
932: "remove() must follow next()");
933: }
934: if (modCount != expectedModCount) {
935: throw new ConcurrentModificationException();
936: }
937: SequencedHashMap.this .removeImpl(pos.getKey());
938:
939: // update the expected mod count for the remove operation
940: expectedModCount++;
941:
942: // set the removed flag
943: returnType = returnType | REMOVED_MASK;
944: }
945: }
946: }
|