View Javadoc

    1   package org.codehaus.aspectwerkz.util;
    2
    3   /*
    4    * $Header: /home/projects/aspectwerkz/scm/aspectwerkz4/src/main/org/codehaus/aspectwerkz/util/SequencedHashMap.java,v 1.3 2004/10/22 12:40:40 avasseur Exp $
    5    * $Revision: 1.3 $
    6    * $Date: 2004/10/22 12:40:40 $
    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      * <p/>
    315      * <pre>
    316      * Object obj = null;
    317      * Iterator iter = entrySet().iterator();
    318      * while (iter.hasNext()) {
    319      *     obj = iter.next();
    320      * }
    321      * return (Map.Entry) obj;
    322      * </pre>
    323      * <p/>
    324      * <p/>However, the implementation of this method ensures an O(1) lookup of the last key rather than O(n).
    325      *
    326      * @return The last entry in the sequence, or <code>null</code> if the map is empty.
    327      */
    328     public Map.Entry getLast() {
    329         // 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()) ^
    864                     ((getValue() == null) ? 0 : getValue().hashCode()));
    865         }
    866
    867         public boolean equals(Object obj) {
    868             if (obj == null) {
    869                 return false;
    870             }
    871             if (obj == this) {
    872                 return true;
    873             }
    874             if (!(obj instanceof Map.Entry)) {
    875                 return false;
    876             }
    877             Map.Entry other = (Map.Entry) obj;
    878
    879             // implemented per api docs for Map.Entry.equals(Object)
    880             return (((getKey() == null) ? (other.getKey() == null) : getKey().equals(other.getKey())) && ((getValue() ==
    881                                                                                                            null)
    882                                                                                                           ?
    883                                                                                                           (other.getValue() ==
    884                                                                                                            null)
    885                                                                                                           :
    886                                                                                                           getValue()
    887                     .equals(other.getValue())));
    888         }
    889
    890         public String toString() {
    891             return "[" + getKey() + '=' + getValue() + ']';
    892         }
    893     }
    894
    895     private class OrderedIterator implements Iterator {
    896         /***
    897          * Holds the type that should be returned from the iterator. The value should be either {@link #KEY},
    898          * {@link#VALUE}, or {@link #ENTRY}. To save a tiny bit of memory, this field is also used as a marker for
    899          * when remove has been called on the current object to prevent a second remove on the same element.
    900          * Essientially, if this value is negative (i.e. the bit specified by {@link #REMOVED_MASK}is set), the current
    901          * position has been removed. If positive, remove can still be called.
    902          */
    903         private int returnType;
    904
    905         /***
    906          * Holds the "current" position in the iterator. When pos.next is the sentinel, we've reached the end of the
    907          * list.
    908          */
    909         private Entry pos = sentinel;
    910
    911         /***
    912          * Holds the expected modification count. If the actual modification count of the map differs from this value,
    913          * then a concurrent modification has occurred.
    914          */
    915         private transient long expectedModCount = modCount;
    916
    917         /***
    918          * Construct an iterator over the sequenced elements in the order in which they were added. The {@link #next()}
    919          * method returns the type specified by <code>returnType</code> which must be either {@link #KEY},
    920          * {@link#VALUE}, or {@link #ENTRY}.
    921          */
    922         public OrderedIterator(int returnType) {
    923             //// Since this is a private inner class, nothing else should have
    924             //// access to the constructor. Since we know the rest of the outer
    925             //// class uses the iterator correctly, we can leave of the following
    926             //// check:
    927             //if(returnType >= 0 && returnType <= 2) {
    928             //  throw new IllegalArgumentException("Invalid iterator type");
    929             //}
    930             // Set the "removed" bit so that the iterator starts in a state where
    931             // "next" must be called before "remove" will succeed.
    932             this.returnType = returnType | REMOVED_MASK;
    933         }
    934
    935         /***
    936          * Returns whether there is any additional elements in the iterator to be returned.
    937          *
    938          * @return <code>true</code> if there are more elements left to be returned from the iterator;
    939          *         <code>false</code> otherwise.
    940          */
    941         public boolean hasNext() {
    942             return pos.next != sentinel;
    943         }
    944
    945         /***
    946          * Returns the next element from the iterator.
    947          *
    948          * @return the next element from the iterator.
    949          * @throws NoSuchElementException if there are no more elements in the iterator.
    950          * @throws ConcurrentModificationException
    951          *                                if a modification occurs in the underlying map.
    952          */
    953         public Object next() {
    954             if (modCount != expectedModCount) {
    955                 throw new ConcurrentModificationException();
    956             }
    957             if (pos.next == sentinel) {
    958                 throw new NoSuchElementException();
    959             }
    960
    961             // clear the "removed" flag
    962             returnType = returnType & ~REMOVED_MASK;
    963             pos = pos.next;
    964             switch (returnType) {
    965                 case KEY:
    966                     return pos.getKey();
    967                 case VALUE:
    968                     return pos.getValue();
    969                 case ENTRY:
    970                     return pos;
    971                 default:
    972
    973                     // should never happen
    974                     throw new Error("bad iterator type: " + returnType);
    975             }
    976         }
    977
    978         /***
    979          * Removes the last element returned from the {@link #next()}method from the sequenced map.
    980          *
    981          * @throws IllegalStateException if there isn't a "last element" to be removed. That is, if {@link #next()}has
    982          *                               never been called, or if {@link #remove()}was already called on the element.
    983          * @throws ConcurrentModificationException
    984          *                               if a modification occurs in the underlying map.
    985          */
    986         public void remove() {
    987             if ((returnType & REMOVED_MASK) != 0) {
    988                 throw new IllegalStateException("remove() must follow next()");
    989             }
    990             if (modCount != expectedModCount) {
    991                 throw new ConcurrentModificationException();
    992             }
    993             SequencedHashMap.this.removeImpl(pos.getKey());
    994
    995             // update the expected mod count for the remove operation
    996             expectedModCount++;
    997
    998             // set the removed flag
    999             returnType = returnType | REMOVED_MASK;
    1000         }
    1001     }
    1002 }