View Javadoc

1   package org.codehaus.aspectwerkz.util;
2   
3   /*
4    * $Header: /home/projects/aspectwerkz/scm/aspectwerkz3/src/main/org/codehaus/aspectwerkz/util/SequencedHashMap.java,v 1.7 2004/08/09 12:39:07 jboner Exp $
5    * $Revision: 1.7 $
6    * $Date: 2004/08/09 12:39:07 $
7    *
8    * ====================================================================
9    *
10   * The Apache Software License, Version 1.1
11   *
12   * Copyright (c) 1999-2002 The Apache Software Foundation.  All rights
13   * reserved.
14   *
15   * Redistribution and use in source and binary forms, with or without
16   * modification, are permitted provided that the following conditions
17   * are met:
18   *
19   * 1. Redistributions of source code must retain the above copyright
20   *    notice, this list of conditions and the following disclaimer.
21   *
22   * 2. Redistributions in binary form must reproduce the above copyright
23   *    notice, this list of conditions and the following disclaimer in
24   *    the documentation and/or other materials provided with the
25   *    distribution.
26   *
27   * 3. The end-user documentation included with the redistribution, if
28   *    any, must include the following acknowlegement:
29   *       "This product includes software developed by the
30   *        Apache Software Foundation (http://www.apache.org/)."
31   *    Alternately, this acknowlegement may appear in the software itself,
32   *    if and wherever such third-party acknowlegements normally appear.
33   *
34   * 4. The names "The Jakarta Project", "Commons", and "Apache Software
35   *    Foundation" must not be used to endorse or promote products derived
36   *    from this software without prior written permission. For written
37   *    permission, please contact apache@apache.org.
38   *
39   * 5. Products derived from this software may not be called "Apache"
40   *    nor may "Apache" appear in their names without prior written
41   *    permission of the Apache Group.
42   *
43   * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
44   * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
45   * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
46   * DISCLAIMED.  IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
47   * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
48   * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
49   * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
50   * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
51   * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
52   * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
53   * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
54   * SUCH DAMAGE.
55   * ====================================================================
56   *
57   * This software consists of voluntary contributions made by many
58   * individuals on behalf of the Apache Software Foundation.  For more
59   * information on the Apache Software Foundation, please see
60   * <http://www.apache.org/>.
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      // constants to define what the iterator should return on "next"
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     // add a serial version uid, so that if we change things in the future
108     // without changing the format, we can still deserialize properly.
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     // per Map.size()
198 
199     /***
200      * Implements {@link Map#size()}.
201      */
202     public int size() {
203         // use the underlying Map's size since size is not maintained here.
204         return entries.size();
205     }
206 
207     /***
208      * Implements {@link Map#isEmpty()}.
209      */
210     public boolean isEmpty() {
211         // for quick check whether the map is entry, we can check the linked list
212         // and see if there's anything in it.
213         return sentinel.next == sentinel;
214     }
215 
216     /***
217      * Implements {@link Map#containsKey(Object)}.
218      */
219     public boolean containsKey(Object key) {
220         // pass on to underlying map implementation
221         return entries.containsKey(key);
222     }
223 
224     /***
225      * Implements {@link Map#containsValue(Object)}.
226      */
227     public boolean containsValue(Object value) {
228         // unfortunately, we cannot just pass this call to the underlying map
229         // because we are mapping keys to entries, not keys to values. The
230         // underlying map doesn't have an efficient implementation anyway, so this
231         // isn't a big deal.
232         // do null comparison outside loop so we only need to do it once. This
233         // provides a tighter, more efficient loop at the expense of slight
234         // code duplication.
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         // find entry for the specified key object
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         // sentinel.next points to the "first" element of the sequence -- the head
272         // of the list, which is exactly the entry we need to return. We must test
273         // for an empty list though because we don't want to return the sentinel!
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         // sentinel.next points to the "first" element of the sequence -- the head
286         // of the list -- and the requisite key is returned from it. An empty list
287         // does not need to be tested. In cases where the list is empty,
288         // sentinel.next will point to the sentinel itself which has a null key,
289         // which is exactly what we would want to return if the list is empty (a
290         // nice convient way to avoid test for an empty list)
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         // sentinel.next points to the "first" element of the sequence -- the head
303         // of the list -- and the requisite value is returned from it. An empty
304         // list does not need to be tested. In cases where the list is empty,
305         // sentinel.next will point to the sentinel itself which has a null value,
306         // which is exactly what we would want to return if the list is empty (a
307         // nice convient way to avoid test for an empty list)
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      * 
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      * 
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         // sentinel.prev points to the "last" element of the sequence -- the tail
330         // of the list, which is exactly the entry we need to return. We must test
331         // for an empty list though because we don't want to return the sentinel!
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         // sentinel.prev points to the "last" element of the sequence -- the tail
344         // of the list -- and the requisite key is returned from it. An empty list
345         // does not need to be tested. In cases where the list is empty,
346         // sentinel.prev will point to the sentinel itself which has a null key,
347         // which is exactly what we would want to return if the list is empty (a
348         // nice convient way to avoid test for an empty list)
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         // sentinel.prev points to the "last" element of the sequence -- the tail
361         // of the list -- and the requisite value is returned from it. An empty
362         // list does not need to be tested. In cases where the list is empty,
363         // sentinel.prev will point to the sentinel itself which has a null value,
364         // which is exactly what we would want to return if the list is empty (a
365         // nice convient way to avoid test for an empty list)
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         // lookup the entry for the specified key
377         Entry e = (Entry) entries.get(key);
378 
379         // check to see if it already exists
380         if (e != null) {
381             // remove from list so the entry gets "moved" to the end of list
382             removeEntry(e);
383 
384             // update value in map
385             oldValue = e.setValue(value);
386 
387             // Note: We do not update the key here because its unnecessary. We only
388             // do comparisons using equals(Object) and we know the specified key and
389             // that in the map are equal in that sense. This may cause a problem if
390             // someone does not implement their hashCode() and/or equals(Object)
391             // method properly and then use it as a key in this map.
392         } else {
393             // add new entry
394             e = new Entry(key, value);
395             entries.put(key, e);
396         }
397 
398         // assert(entry in map, but not list)
399         // add to list
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         // remove all from the underlying map
449         entries.clear();
450 
451         // and the list
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             // required impls
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             // more efficient impls than abstract set
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             // required impl
540             public Iterator iterator() {
541                 return new OrderedIterator(VALUE);
542             }
543 
544             public boolean remove(Object value) {
545                 // do null comparison outside loop so we only need to do it once. This
546                 // provides a tighter, more efficient loop at the expense of slight
547                 // code duplication.
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             // more efficient impls than abstract collection
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             // helper
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             // required impl
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             // more efficient impls than abstract collection
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     // APIs maintained from previous version of SequencedHashMap for backwards
640     // compatibility
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         // yes, calling super.clone() silly since we're just blowing away all
651         // the stuff that super might be doing anyway, but for motivations on
652         // this, see:
653         // http://www.javaworld.com/javaworld/jw-01-1999/jw-01-object.html
654         SequencedHashMap map = (SequencedHashMap) super.clone();
655 
656         // create new, empty sentinel
657         map.sentinel = createSentinel();
658 
659         // create a new, empty entry map
660         // note: this does not preserve the initial capacity and load factor.
661         map.entries = new HashMap();
662 
663         // add all the mappings
664         map.putAll(this);
665 
666         // Note: We cannot just clone the hashmap and sentinel because we must
667         // duplicate our internal structures. Cloning those two will not clone all
668         // the other entries they reference, and so the cloned hash map will not be
669         // able to maintain internal consistency because there are two objects with
670         // the same entries. See discussion in the Entry implementation on why we
671         // cannot implement a clone of the Entry (and thus why we need to recreate
672         // everything).
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>&lt; 0</code> or <code>&gt;</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         // loop to one before the position
689         int i = -1;
690         while ((i < (index - 1)) && (pos.next != sentinel)) {
691             i++;
692             pos = pos.next;
693         }
694 
695         // pos.next is the requested position
696         // if sentinel is next, past end of list
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>&lt; 0</code> or <code>&gt;</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>&lt; 0</code> or <code>&gt;</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         // keys in a map are guarunteed to be unique
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>&lt; 0</code> or <code>&gt;</code>
778      *             the size of the map.
779      */
780     public Object remove(int index) {
781         return remove(get(index));
782     }
783 
784     // per Externalizable.readExternal(ObjectInput)
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         // Note: This class cannot easily be made clonable. While the actual
821         // implementation of a clone would be simple, defining the semantics is
822         // difficult. If a shallow clone is implemented, then entry.next.prev !=
823         // entry, which is unintuitive and probably breaks all sorts of assumptions
824         // in code that uses this implementation. If a deep clone is
825         // implementated, then what happens when the linked list is cyclical (as is
826         // the case with SequencedHashMap)? It's impossible to know in the clone
827         // when to stop cloning, and thus you end up in a recursive loop,
828         // continuously cloning the "next" in the list.
829         private final Object key;
830 
831         private Object value;
832 
833         // package private to allow the SequencedHashMap to access and manipulate
834         // them.
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         // per Map.Entry.getKey()
845         public Object getKey() {
846             return this.key;
847         }
848 
849         // per Map.Entry.getValue()
850         public Object getValue() {
851             return this.value;
852         }
853 
854         // per Map.Entry.setValue()
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             // implemented per api docs for Map.Entry.hashCode()
863             return (((getKey() == null) ? 0 : getKey().hashCode()) ^ ((getValue() == null) ? 0 : getValue().hashCode()));
864         }
865 
866         public boolean equals(Object obj) {
867             if (obj == null) {
868                 return false;
869             }
870             if (obj == this) {
871                 return true;
872             }
873             if (!(obj instanceof Map.Entry)) {
874                 return false;
875             }
876             Map.Entry other = (Map.Entry) obj;
877 
878             // implemented per api docs for Map.Entry.equals(Object)
879             return (((getKey() == null) ? (other.getKey() == null) : getKey().equals(other.getKey())) && ((getValue() == null)
880                 ? (other.getValue() == null)
881                 : getValue().equals(other.getValue())));
882         }
883 
884         public String toString() {
885             return "[" + getKey() + '=' + getValue() + ']';
886         }
887     }
888 
889     private class OrderedIterator implements Iterator {
890         /***
891          * Holds the type that should be returned from the iterator. The value should be either {@link #KEY},
892          * {@link#VALUE}, or {@link #ENTRY}. To save a tiny bit of memory, this field is also used as a marker for
893          * when remove has been called on the current object to prevent a second remove on the same element.
894          * Essientially, if this value is negative (i.e. the bit specified by {@link #REMOVED_MASK}is set), the current
895          * position has been removed. If positive, remove can still be called.
896          */
897         private int returnType;
898 
899         /***
900          * Holds the "current" position in the iterator. When pos.next is the sentinel, we've reached the end of the
901          * list.
902          */
903         private Entry pos = sentinel;
904 
905         /***
906          * Holds the expected modification count. If the actual modification count of the map differs from this value,
907          * then a concurrent modification has occurred.
908          */
909         private transient long expectedModCount = modCount;
910 
911         /***
912          * Construct an iterator over the sequenced elements in the order in which they were added. The {@link #next()}
913          * method returns the type specified by <code>returnType</code> which must be either {@link #KEY},
914          * {@link#VALUE}, or {@link #ENTRY}.
915          */
916         public OrderedIterator(int returnType) {
917             //// Since this is a private inner class, nothing else should have
918             //// access to the constructor. Since we know the rest of the outer
919             //// class uses the iterator correctly, we can leave of the following
920             //// check:
921             //if(returnType >= 0 && returnType <= 2) {
922             //  throw new IllegalArgumentException("Invalid iterator type");
923             //}
924             // Set the "removed" bit so that the iterator starts in a state where
925             // "next" must be called before "remove" will succeed.
926             this.returnType = returnType | REMOVED_MASK;
927         }
928 
929         /***
930          * Returns whether there is any additional elements in the iterator to be returned.
931          * 
932          * @return <code>true</code> if there are more elements left to be returned from the iterator;
933          *         <code>false</code> otherwise.
934          */
935         public boolean hasNext() {
936             return pos.next != sentinel;
937         }
938 
939         /***
940          * Returns the next element from the iterator.
941          * 
942          * @return the next element from the iterator.
943          * @throws NoSuchElementException if there are no more elements in the iterator.
944          * @throws ConcurrentModificationException if a modification occurs in the underlying map.
945          */
946         public Object next() {
947             if (modCount != expectedModCount) {
948                 throw new ConcurrentModificationException();
949             }
950             if (pos.next == sentinel) {
951                 throw new NoSuchElementException();
952             }
953 
954             // clear the "removed" flag
955             returnType = returnType & ~REMOVED_MASK;
956             pos = pos.next;
957             switch (returnType) {
958                 case KEY:
959                     return pos.getKey();
960                 case VALUE:
961                     return pos.getValue();
962                 case ENTRY:
963                     return pos;
964                 default:
965 
966                     // should never happen
967                     throw new Error("bad iterator type: " + returnType);
968             }
969         }
970 
971         /***
972          * Removes the last element returned from the {@link #next()}method from the sequenced map.
973          * 
974          * @throws IllegalStateException if there isn't a "last element" to be removed. That is, if {@link #next()}has
975          *             never been called, or if {@link #remove()}was already called on the element.
976          * @throws ConcurrentModificationException if a modification occurs in the underlying map.
977          */
978         public void remove() {
979             if ((returnType & REMOVED_MASK) != 0) {
980                 throw new IllegalStateException("remove() must follow next()");
981             }
982             if (modCount != expectedModCount) {
983                 throw new ConcurrentModificationException();
984             }
985             SequencedHashMap.this.removeImpl(pos.getKey());
986 
987             // update the expected mod count for the remove operation
988             expectedModCount++;
989 
990             // set the removed flag
991             returnType = returnType | REMOVED_MASK;
992         }
993     }
994 }