001    /*
002     *  Licensed to the Apache Software Foundation (ASF) under one or more
003     *  contributor license agreements.  See the NOTICE file distributed with
004     *  this work for additional information regarding copyright ownership.
005     *  The ASF licenses this file to You under the Apache License, Version 2.0
006     *  (the "License"); you may not use this file except in compliance with
007     *  the License.  You may obtain a copy of the License at
008     *
009     *      http://www.apache.org/licenses/LICENSE-2.0
010     *
011     *  Unless required by applicable law or agreed to in writing, software
012     *  distributed under the License is distributed on an "AS IS" BASIS,
013     *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014     *  See the License for the specific language governing permissions and
015     *  limitations under the License.
016     */
017    package org.apache.commons.collections;
018    
019    import java.io.Externalizable;
020    import java.io.IOException;
021    import java.io.ObjectInput;
022    import java.io.ObjectOutput;
023    import java.util.AbstractCollection;
024    import java.util.AbstractSet;
025    import java.util.ArrayList;
026    import java.util.Collection;
027    import java.util.ConcurrentModificationException;
028    import java.util.HashMap;
029    import java.util.Iterator;
030    import java.util.List;
031    import java.util.Map;
032    import java.util.NoSuchElementException;
033    import java.util.Set;
034    
035    import org.apache.commons.collections.list.UnmodifiableList;
036    
037    /**
038     * A map of objects whose mapping entries are sequenced based on the order in
039     * which they were added.  This data structure has fast <i>O(1)</i> search
040     * time, deletion time, and insertion time.
041     * <p>
042     * Although this map is sequenced, it cannot implement
043     * {@link java.util.List} because of incompatible interface definitions.
044     * The remove methods in List and Map have different return values 
045     * (see: {@link java.util.List#remove(Object)} and {@link java.util.Map#remove(Object)}).
046     * <p>
047     * This class is not thread safe.  When a thread safe implementation is
048     * required, use {@link java.util.Collections#synchronizedMap(Map)} as it is documented,
049     * or use explicit synchronization controls.
050     *
051     * @deprecated Replaced by LinkedMap and ListOrderedMap in map subpackage. Due to be removed in v4.0.
052     * @see org.apache.commons.collections.map.LinkedMap
053     * @see org.apache.commons.collections.map.ListOrderedMap
054     * @since Commons Collections 2.0
055     * @version $Revision: 646777 $ $Date: 2008-04-10 13:33:15 +0100 (Thu, 10 Apr 2008) $
056     * 
057     * @author Michael A. Smith
058     * @author Daniel Rall
059     * @author Henning P. Schmiedehausen
060     * @author Stephen Colebourne
061     */
062    public class SequencedHashMap implements Map, Cloneable, Externalizable {
063    
064        /**
065         * {@link java.util.Map.Entry} that doubles as a node in the linked list
066         * of sequenced mappings.  
067         */
068        private static class Entry implements Map.Entry, KeyValue {
069            // Note: This class cannot easily be made clonable.  While the actual
070            // implementation of a clone would be simple, defining the semantics is
071            // difficult.  If a shallow clone is implemented, then entry.next.prev !=
072            // entry, which is unintuitive and probably breaks all sorts of assumptions
073            // in code that uses this implementation.  If a deep clone is
074            // implemented, then what happens when the linked list is cyclical (as is
075            // the case with SequencedHashMap)?  It's impossible to know in the clone
076            // when to stop cloning, and thus you end up in a recursive loop,
077            // continuously cloning the "next" in the list.
078    
079            private final Object key;
080            private Object value;
081    
082            // package private to allow the SequencedHashMap to access and manipulate
083            // them.
084            Entry next = null;
085            Entry prev = null;
086    
087            public Entry(Object key, Object value) {
088                this.key = key;
089                this.value = value;
090            }
091    
092            // per Map.Entry.getKey()
093            public Object getKey() {
094                return this.key;
095            }
096    
097            // per Map.Entry.getValue()
098            public Object getValue() {
099                return this.value;
100            }
101    
102            // per Map.Entry.setValue()
103            public Object setValue(Object value) {
104                Object oldValue = this.value;
105                this.value = value;
106                return oldValue;
107            }
108    
109            public int hashCode() {
110                // implemented per api docs for Map.Entry.hashCode()
111                return ((getKey() == null ? 0 : getKey().hashCode()) ^ (getValue() == null ? 0 : getValue().hashCode()));
112            }
113    
114            public boolean equals(Object obj) {
115                if (obj == null)
116                    return false;
117                if (obj == this)
118                    return true;
119                if (!(obj instanceof Map.Entry))
120                    return false;
121    
122                Map.Entry other = (Map.Entry) obj;
123    
124                // implemented per api docs for Map.Entry.equals(Object) 
125                return (
126                    (getKey() == null ? other.getKey() == null : getKey().equals(other.getKey()))
127                        && (getValue() == null ? other.getValue() == null : getValue().equals(other.getValue())));
128            }
129            public String toString() {
130                return "[" + getKey() + "=" + getValue() + "]";
131            }
132        }
133    
134        /**
135         *  Construct an empty sentinel used to hold the head (sentinel.next) and the
136         *  tail (sentinel.prev) of the list.  The sentinel has a <code>null</code>
137         *  key and value.
138         */
139        private static final Entry createSentinel() {
140            Entry s = new Entry(null, null);
141            s.prev = s;
142            s.next = s;
143            return s;
144        }
145    
146        /**
147         *  Sentinel used to hold the head and tail of the list of entries.
148         */
149        private Entry sentinel;
150    
151        /**
152         *  Map of keys to entries
153         */
154        private HashMap entries;
155    
156        /**
157         *  Holds the number of modifications that have occurred to the map,
158         *  excluding modifications made through a collection view's iterator
159         *  (e.g. entrySet().iterator().remove()).  This is used to create a
160         *  fail-fast behavior with the iterators.
161         */
162        private transient long modCount = 0;
163    
164        /**
165         *  Construct a new sequenced hash map with default initial size and load
166         *  factor.
167         */
168        public SequencedHashMap() {
169            sentinel = createSentinel();
170            entries = new HashMap();
171        }
172    
173        /**
174         *  Construct a new sequenced hash map with the specified initial size and
175         *  default load factor.
176         *
177         *  @param initialSize the initial size for the hash table 
178         *
179         *  @see HashMap#HashMap(int)
180         */
181        public SequencedHashMap(int initialSize) {
182            sentinel = createSentinel();
183            entries = new HashMap(initialSize);
184        }
185    
186        /**
187         *  Construct a new sequenced hash map with the specified initial size and
188         *  load factor.
189         *
190         *  @param initialSize the initial size for the hash table 
191         *
192         *  @param loadFactor the load factor for the hash table.
193         *
194         *  @see HashMap#HashMap(int,float)
195         */
196        public SequencedHashMap(int initialSize, float loadFactor) {
197            sentinel = createSentinel();
198            entries = new HashMap(initialSize, loadFactor);
199        }
200    
201        /**
202         *  Construct a new sequenced hash map and add all the elements in the
203         *  specified map.  The order in which the mappings in the specified map are
204         *  added is defined by {@link #putAll(Map)}.  
205         */
206        public SequencedHashMap(Map m) {
207            this();
208            putAll(m);
209        }
210    
211        /**
212         *  Removes an internal entry from the linked list.  This does not remove
213         *  it from the underlying map.
214         */
215        private void removeEntry(Entry entry) {
216            entry.next.prev = entry.prev;
217            entry.prev.next = entry.next;
218        }
219    
220        /**
221         *  Inserts a new internal entry to the tail of the linked list.  This does
222         *  not add the entry to the underlying map.
223         */
224        private void insertEntry(Entry entry) {
225            entry.next = sentinel;
226            entry.prev = sentinel.prev;
227            sentinel.prev.next = entry;
228            sentinel.prev = entry;
229        }
230    
231        // per Map.size()
232    
233        /**
234         *  Implements {@link Map#size()}.
235         */
236        public int size() {
237            // use the underlying Map's size since size is not maintained here.
238            return entries.size();
239        }
240    
241        /**
242         *  Implements {@link Map#isEmpty()}.
243         */
244        public boolean isEmpty() {
245            // for quick check whether the map is entry, we can check the linked list
246            // and see if there's anything in it.
247            return sentinel.next == sentinel;
248        }
249    
250        /**
251         *  Implements {@link Map#containsKey(Object)}.
252         */
253        public boolean containsKey(Object key) {
254            // pass on to underlying map implementation
255            return entries.containsKey(key);
256        }
257    
258        /**
259         *  Implements {@link Map#containsValue(Object)}.
260         */
261        public boolean containsValue(Object value) {
262            // unfortunately, we cannot just pass this call to the underlying map
263            // because we are mapping keys to entries, not keys to values.  The
264            // underlying map doesn't have an efficient implementation anyway, so this
265            // isn't a big deal.
266    
267            // do null comparison outside loop so we only need to do it once.  This
268            // provides a tighter, more efficient loop at the expense of slight
269            // code duplication.
270            if (value == null) {
271                for (Entry pos = sentinel.next; pos != sentinel; pos = pos.next) {
272                    if (pos.getValue() == null)
273                        return true;
274                }
275            } else {
276                for (Entry pos = sentinel.next; pos != sentinel; pos = pos.next) {
277                    if (value.equals(pos.getValue()))
278                        return true;
279                }
280            }
281            return false;
282        }
283    
284        /**
285         *  Implements {@link Map#get(Object)}.
286         */
287        public Object get(Object o) {
288            // find entry for the specified key object
289            Entry entry = (Entry) entries.get(o);
290            if (entry == null)
291                return null;
292    
293            return entry.getValue();
294        }
295    
296        /**
297         *  Return the entry for the "oldest" mapping.  That is, return the Map.Entry
298         *  for the key-value pair that was first put into the map when compared to
299         *  all the other pairings in the map.  This behavior is equivalent to using
300         *  <code>entrySet().iterator().next()</code>, but this method provides an
301         *  optimized implementation.
302         *
303         *  @return The first entry in the sequence, or <code>null</code> if the
304         *  map is empty.
305         */
306        public Map.Entry getFirst() {
307            // sentinel.next points to the "first" element of the sequence -- the head
308            // of the list, which is exactly the entry we need to return.  We must test
309            // for an empty list though because we don't want to return the sentinel!
310            return (isEmpty()) ? null : sentinel.next;
311        }
312    
313        /**
314         *  Return the key for the "oldest" mapping.  That is, return the key for the
315         *  mapping that was first put into the map when compared to all the other
316         *  objects in the map.  This behavior is equivalent to using
317         *  <code>getFirst().getKey()</code>, but this method provides a slightly
318         *  optimized implementation.
319         *
320         *  @return The first key in the sequence, or <code>null</code> if the
321         *  map is empty.
322         */
323        public Object getFirstKey() {
324            // sentinel.next points to the "first" element of the sequence -- the head
325            // of the list -- and the requisite key is returned from it.  An empty list
326            // does not need to be tested.  In cases where the list is empty,
327            // sentinel.next will point to the sentinel itself which has a null key,
328            // which is exactly what we would want to return if the list is empty (a
329            // nice convenient way to avoid test for an empty list)
330            return sentinel.next.getKey();
331        }
332    
333        /**
334         *  Return the value for the "oldest" mapping.  That is, return the value for
335         *  the mapping that was first put into the map when compared to all the
336         *  other objects in the map.  This behavior is equivalent to using
337         *  <code>getFirst().getValue()</code>, but this method provides a slightly
338         *  optimized implementation.
339         *
340         *  @return The first value in the sequence, or <code>null</code> if the
341         *  map is empty.
342         */
343        public Object getFirstValue() {
344            // sentinel.next points to the "first" element of the sequence -- the head
345            // of the list -- and the requisite value is returned from it.  An empty
346            // list does not need to be tested.  In cases where the list is empty,
347            // sentinel.next will point to the sentinel itself which has a null value,
348            // which is exactly what we would want to return if the list is empty (a
349            // nice convenient way to avoid test for an empty list)
350            return sentinel.next.getValue();
351        }
352    
353        /**
354         *  Return the entry for the "newest" mapping.  That is, return the Map.Entry
355         *  for the key-value pair that was first put into the map when compared to
356         *  all the other pairings in the map.  The behavior is equivalent to:
357         *
358         *  <pre>
359         *    Object obj = null;
360         *    Iterator iter = entrySet().iterator();
361         *    while(iter.hasNext()) {
362         *      obj = iter.next();
363         *    }
364         *    return (Map.Entry)obj;
365         *  </pre>
366         *
367         *  However, the implementation of this method ensures an O(1) lookup of the
368         *  last key rather than O(n).
369         *
370         *  @return The last entry in the sequence, or <code>null</code> if the map
371         *  is empty.
372         */
373        public Map.Entry getLast() {
374            // sentinel.prev points to the "last" element of the sequence -- the tail
375            // of the list, which is exactly the entry we need to return.  We must test
376            // for an empty list though because we don't want to return the sentinel!
377            return (isEmpty()) ? null : sentinel.prev;
378        }
379    
380        /**
381         *  Return the key for the "newest" mapping.  That is, return the key for the
382         *  mapping that was last put into the map when compared to all the other
383         *  objects in the map.  This behavior is equivalent to using
384         *  <code>getLast().getKey()</code>, but this method provides a slightly
385         *  optimized implementation.
386         *
387         *  @return The last key in the sequence, or <code>null</code> if the map is
388         *  empty.
389         */
390        public Object getLastKey() {
391            // sentinel.prev points to the "last" element of the sequence -- the tail
392            // of the list -- and the requisite key is returned from it.  An empty list
393            // does not need to be tested.  In cases where the list is empty,
394            // sentinel.prev will point to the sentinel itself which has a null key,
395            // which is exactly what we would want to return if the list is empty (a
396            // nice convenient way to avoid test for an empty list)
397            return sentinel.prev.getKey();
398        }
399    
400        /**
401         *  Return the value for the "newest" mapping.  That is, return the value for
402         *  the mapping that was last put into the map when compared to all the other
403         *  objects in the map.  This behavior is equivalent to using
404         *  <code>getLast().getValue()</code>, but this method provides a slightly
405         *  optimized implementation.
406         *
407         *  @return The last value in the sequence, or <code>null</code> if the map
408         *  is empty.
409         */
410        public Object getLastValue() {
411            // sentinel.prev points to the "last" element of the sequence -- the tail
412            // of the list -- and the requisite value is returned from it.  An empty
413            // list does not need to be tested.  In cases where the list is empty,
414            // sentinel.prev will point to the sentinel itself which has a null value,
415            // which is exactly what we would want to return if the list is empty (a
416            // nice convenient way to avoid test for an empty list)
417            return sentinel.prev.getValue();
418        }
419    
420        /**
421         *  Implements {@link Map#put(Object, Object)}.
422         */
423        public Object put(Object key, Object value) {
424            modCount++;
425    
426            Object oldValue = null;
427    
428            // lookup the entry for the specified key
429            Entry e = (Entry) entries.get(key);
430    
431            // check to see if it already exists
432            if (e != null) {
433                // remove from list so the entry gets "moved" to the end of list
434                removeEntry(e);
435    
436                // update value in map
437                oldValue = e.setValue(value);
438    
439                // Note: We do not update the key here because its unnecessary.  We only
440                // do comparisons using equals(Object) and we know the specified key and
441                // that in the map are equal in that sense.  This may cause a problem if
442                // someone does not implement their hashCode() and/or equals(Object)
443                // method properly and then use it as a key in this map.  
444            } else {
445                // add new entry
446                e = new Entry(key, value);
447                entries.put(key, e);
448            }
449            // assert(entry in map, but not list)
450    
451            // add to list
452            insertEntry(e);
453    
454            return oldValue;
455        }
456    
457        /**
458         *  Implements {@link Map#remove(Object)}.
459         */
460        public Object remove(Object key) {
461            Entry e = removeImpl(key);
462            return (e == null) ? null : e.getValue();
463        }
464    
465        /**
466         *  Fully remove an entry from the map, returning the old entry or null if
467         *  there was no such entry with the specified key.
468         */
469        private Entry removeImpl(Object key) {
470            Entry e = (Entry) entries.remove(key);
471            if (e == null)
472                return null;
473            modCount++;
474            removeEntry(e);
475            return e;
476        }
477    
478        /**
479         *  Adds all the mappings in the specified map to this map, replacing any
480         *  mappings that already exist (as per {@link Map#putAll(Map)}).  The order
481         *  in which the entries are added is determined by the iterator returned
482         *  from {@link Map#entrySet()} for the specified map.
483         *
484         *  @param t the mappings that should be added to this map.
485         *
486         *  @throws NullPointerException if <code>t</code> is <code>null</code>
487         */
488        public void putAll(Map t) {
489            Iterator iter = t.entrySet().iterator();
490            while (iter.hasNext()) {
491                Map.Entry entry = (Map.Entry) iter.next();
492                put(entry.getKey(), entry.getValue());
493            }
494        }
495    
496        /**
497         *  Implements {@link Map#clear()}.
498         */
499        public void clear() {
500            modCount++;
501    
502            // remove all from the underlying map
503            entries.clear();
504    
505            // and the list
506            sentinel.next = sentinel;
507            sentinel.prev = sentinel;
508        }
509    
510        /**
511         *  Implements {@link Map#equals(Object)}.
512         */
513        public boolean equals(Object obj) {
514            if (obj == null)
515                return false;
516            if (obj == this)
517                return true;
518    
519            if (!(obj instanceof Map))
520                return false;
521    
522            return entrySet().equals(((Map) obj).entrySet());
523        }
524    
525        /**
526         *  Implements {@link Map#hashCode()}.
527         */
528        public int hashCode() {
529            return entrySet().hashCode();
530        }
531    
532        /**
533         *  Provides a string representation of the entries within the map.  The
534         *  format of the returned string may change with different releases, so this
535         *  method is suitable for debugging purposes only.  If a specific format is
536         *  required, use {@link #entrySet()}.{@link Set#iterator() iterator()} and
537         *  iterate over the entries in the map formatting them as appropriate.
538         */
539        public String toString() {
540            StringBuffer buf = new StringBuffer();
541            buf.append('[');
542            for (Entry pos = sentinel.next; pos != sentinel; pos = pos.next) {
543                buf.append(pos.getKey());
544                buf.append('=');
545                buf.append(pos.getValue());
546                if (pos.next != sentinel) {
547                    buf.append(',');
548                }
549            }
550            buf.append(']');
551    
552            return buf.toString();
553        }
554    
555        /**
556         *  Implements {@link Map#keySet()}.
557         */
558        public Set keySet() {
559            return new AbstractSet() {
560    
561                // required impls
562                public Iterator iterator() {
563                    return new OrderedIterator(KEY);
564                }
565                public boolean remove(Object o) {
566                    Entry e = SequencedHashMap.this.removeImpl(o);
567                    return (e != null);
568                }
569    
570                // more efficient impls than abstract set
571                public void clear() {
572                    SequencedHashMap.this.clear();
573                }
574                public int size() {
575                    return SequencedHashMap.this.size();
576                }
577                public boolean isEmpty() {
578                    return SequencedHashMap.this.isEmpty();
579                }
580                public boolean contains(Object o) {
581                    return SequencedHashMap.this.containsKey(o);
582                }
583    
584            };
585        }
586    
587        /**
588         *  Implements {@link Map#values()}.
589         */
590        public Collection values() {
591            return new AbstractCollection() {
592                // required impl
593                public Iterator iterator() {
594                    return new OrderedIterator(VALUE);
595                }
596                public boolean remove(Object value) {
597                    // do null comparison outside loop so we only need to do it once.  This
598                    // provides a tighter, more efficient loop at the expense of slight
599                    // code duplication.
600                    if (value == null) {
601                        for (Entry pos = sentinel.next; pos != sentinel; pos = pos.next) {
602                            if (pos.getValue() == null) {
603                                SequencedHashMap.this.removeImpl(pos.getKey());
604                                return true;
605                            }
606                        }
607                    } else {
608                        for (Entry pos = sentinel.next; pos != sentinel; pos = pos.next) {
609                            if (value.equals(pos.getValue())) {
610                                SequencedHashMap.this.removeImpl(pos.getKey());
611                                return true;
612                            }
613                        }
614                    }
615    
616                    return false;
617                }
618    
619                // more efficient impls than abstract collection
620                public void clear() {
621                    SequencedHashMap.this.clear();
622                }
623                public int size() {
624                    return SequencedHashMap.this.size();
625                }
626                public boolean isEmpty() {
627                    return SequencedHashMap.this.isEmpty();
628                }
629                public boolean contains(Object o) {
630                    return SequencedHashMap.this.containsValue(o);
631                }
632            };
633        }
634    
635        /**
636         *  Implements {@link Map#entrySet()}.
637         */
638        public Set entrySet() {
639            return new AbstractSet() {
640                // helper
641                private Entry findEntry(Object o) {
642                    if (o == null)
643                        return null;
644                    if (!(o instanceof Map.Entry))
645                        return null;
646    
647                    Map.Entry e = (Map.Entry) o;
648                    Entry entry = (Entry) entries.get(e.getKey());
649                    if (entry != null && entry.equals(e))
650                        return entry;
651                    else
652                        return null;
653                }
654    
655                // required impl
656                public Iterator iterator() {
657                    return new OrderedIterator(ENTRY);
658                }
659                public boolean remove(Object o) {
660                    Entry e = findEntry(o);
661                    if (e == null)
662                        return false;
663    
664                    return SequencedHashMap.this.removeImpl(e.getKey()) != null;
665                }
666    
667                // more efficient impls than abstract collection
668                public void clear() {
669                    SequencedHashMap.this.clear();
670                }
671                public int size() {
672                    return SequencedHashMap.this.size();
673                }
674                public boolean isEmpty() {
675                    return SequencedHashMap.this.isEmpty();
676                }
677                public boolean contains(Object o) {
678                    return findEntry(o) != null;
679                }
680            };
681        }
682    
683        // constants to define what the iterator should return on "next"
684        private static final int KEY = 0;
685        private static final int VALUE = 1;
686        private static final int ENTRY = 2;
687        private static final int REMOVED_MASK = 0x80000000;
688    
689        private class OrderedIterator implements Iterator {
690            /** 
691             *  Holds the type that should be returned from the iterator.  The value
692             *  should be either {@link #KEY}, {@link #VALUE}, or {@link #ENTRY}.  To
693             *  save a tiny bit of memory, this field is also used as a marker for when
694             *  remove has been called on the current object to prevent a second remove
695             *  on the same element.  Essentially, if this value is negative (i.e. the
696             *  bit specified by {@link #REMOVED_MASK} is set), the current position
697             *  has been removed.  If positive, remove can still be called.
698             */
699            private int returnType;
700    
701            /**
702             *  Holds the "current" position in the iterator.  When pos.next is the
703             *  sentinel, we've reached the end of the list.
704             */
705            private Entry pos = sentinel;
706    
707            /**
708             *  Holds the expected modification count.  If the actual modification
709             *  count of the map differs from this value, then a concurrent
710             *  modification has occurred.
711             */
712            private transient long expectedModCount = modCount;
713    
714            /**
715             *  Construct an iterator over the sequenced elements in the order in which
716             *  they were added.  The {@link #next()} method returns the type specified
717             *  by <code>returnType</code> which must be either {@link #KEY}, {@link
718             *  #VALUE}, or {@link #ENTRY}.
719             */
720            public OrderedIterator(int returnType) {
721                //// Since this is a private inner class, nothing else should have
722                //// access to the constructor.  Since we know the rest of the outer
723                //// class uses the iterator correctly, we can leave of the following
724                //// check:
725                //if(returnType >= 0 && returnType <= 2) {
726                //  throw new IllegalArgumentException("Invalid iterator type");
727                //}
728    
729                // Set the "removed" bit so that the iterator starts in a state where
730                // "next" must be called before "remove" will succeed.
731                this.returnType = returnType | REMOVED_MASK;
732            }
733    
734            /**
735             *  Returns whether there is any additional elements in the iterator to be
736             *  returned.
737             *
738             *  @return <code>true</code> if there are more elements left to be
739             *  returned from the iterator; <code>false</code> otherwise.
740             */
741            public boolean hasNext() {
742                return pos.next != sentinel;
743            }
744    
745            /**
746             *  Returns the next element from the iterator.
747             *
748             *  @return the next element from the iterator.
749             *
750             *  @throws NoSuchElementException if there are no more elements in the
751             *  iterator.
752             *
753             *  @throws ConcurrentModificationException if a modification occurs in
754             *  the underlying map.
755             */
756            public Object next() {
757                if (modCount != expectedModCount) {
758                    throw new ConcurrentModificationException();
759                }
760                if (pos.next == sentinel) {
761                    throw new NoSuchElementException();
762                }
763    
764                // clear the "removed" flag
765                returnType = returnType & ~REMOVED_MASK;
766    
767                pos = pos.next;
768                switch (returnType) {
769                    case KEY :
770                        return pos.getKey();
771                    case VALUE :
772                        return pos.getValue();
773                    case ENTRY :
774                        return pos;
775                    default :
776                        // should never happen
777                        throw new Error("bad iterator type: " + returnType);
778                }
779    
780            }
781    
782            /**
783             *  Removes the last element returned from the {@link #next()} method from
784             *  the sequenced map.
785             *
786             *  @throws IllegalStateException if there isn't a "last element" to be
787             *  removed.  That is, if {@link #next()} has never been called, or if
788             *  {@link #remove()} was already called on the element.
789             *
790             *  @throws ConcurrentModificationException if a modification occurs in
791             *  the underlying map.
792             */
793            public void remove() {
794                if ((returnType & REMOVED_MASK) != 0) {
795                    throw new IllegalStateException("remove() must follow next()");
796                }
797                if (modCount != expectedModCount) {
798                    throw new ConcurrentModificationException();
799                }
800    
801                SequencedHashMap.this.removeImpl(pos.getKey());
802    
803                // update the expected mod count for the remove operation
804                expectedModCount++;
805    
806                // set the removed flag
807                returnType = returnType | REMOVED_MASK;
808            }
809        }
810    
811        // APIs maintained from previous version of SequencedHashMap for backwards
812        // compatibility
813    
814        /**
815         * Creates a shallow copy of this object, preserving the internal structure
816         * by copying only references.  The keys and values themselves are not
817         * <code>clone()</code>'d.  The cloned object maintains the same sequence.
818         *
819         * @return A clone of this instance.  
820         *
821         * @throws CloneNotSupportedException if clone is not supported by a
822         * subclass.
823         */
824        public Object clone() throws CloneNotSupportedException {
825            // yes, calling super.clone() silly since we're just blowing away all
826            // the stuff that super might be doing anyway, but for motivations on
827            // this, see:
828            // http://www.javaworld.com/javaworld/jw-01-1999/jw-01-object.html
829            SequencedHashMap map = (SequencedHashMap) super.clone();
830    
831            // create new, empty sentinel
832            map.sentinel = createSentinel();
833    
834            // create a new, empty entry map
835            // note: this does not preserve the initial capacity and load factor.
836            map.entries = new HashMap();
837    
838            // add all the mappings
839            map.putAll(this);
840    
841            // Note: We cannot just clone the hashmap and sentinel because we must
842            // duplicate our internal structures.  Cloning those two will not clone all
843            // the other entries they reference, and so the cloned hash map will not be
844            // able to maintain internal consistency because there are two objects with
845            // the same entries.  See discussion in the Entry implementation on why we
846            // cannot implement a clone of the Entry (and thus why we need to recreate
847            // everything).
848    
849            return map;
850        }
851    
852        /**
853         *  Returns the Map.Entry at the specified index
854         *
855         *  @throws ArrayIndexOutOfBoundsException if the specified index is
856         *  <code>&lt; 0</code> or <code>&gt;</code> the size of the map.
857         */
858        private Map.Entry getEntry(int index) {
859            Entry pos = sentinel;
860    
861            if (index < 0) {
862                throw new ArrayIndexOutOfBoundsException(index + " < 0");
863            }
864    
865            // loop to one before the position
866            int i = -1;
867            while (i < (index - 1) && pos.next != sentinel) {
868                i++;
869                pos = pos.next;
870            }
871            // pos.next is the requested position
872    
873            // if sentinel is next, past end of list
874            if (pos.next == sentinel) {
875                throw new ArrayIndexOutOfBoundsException(index + " >= " + (i + 1));
876            }
877    
878            return pos.next;
879        }
880    
881        /**
882         * Gets the key at the specified index.
883         *
884         * @param index  the index to retrieve
885         * @return the key at the specified index, or null
886         * @throws ArrayIndexOutOfBoundsException if the <code>index</code> is
887         *  <code>&lt; 0</code> or <code>&gt;</code> the size of the map.
888         */
889        public Object get(int index) {
890            return getEntry(index).getKey();
891        }
892    
893        /**
894         * Gets the value at the specified index.
895         *
896         * @param index  the index to retrieve
897         * @return the value at the specified index, or null
898         * @throws ArrayIndexOutOfBoundsException if the <code>index</code> is
899         *  <code>&lt; 0</code> or <code>&gt;</code> the size of the map.
900         */
901        public Object getValue(int index) {
902            return getEntry(index).getValue();
903        }
904    
905        /**
906         * Gets the index of the specified key.
907         * 
908         * @param key  the key to find the index of
909         * @return the index, or -1 if not found
910         */
911        public int indexOf(Object key) {
912            Entry e = (Entry) entries.get(key);
913            if (e == null) {
914                return -1;
915            }
916            int pos = 0;
917            while (e.prev != sentinel) {
918                pos++;
919                e = e.prev;
920            }
921            return pos;
922        }
923    
924        /**
925         * Gets an iterator over the keys.
926         * 
927         * @return an iterator over the keys
928         */
929        public Iterator iterator() {
930            return keySet().iterator();
931        }
932    
933        /**
934         * Gets the last index of the specified key.
935         * 
936         * @param key  the key to find the index of
937         * @return the index, or -1 if not found
938         */
939        public int lastIndexOf(Object key) {
940            // keys in a map are guaranteed to be unique
941            return indexOf(key);
942        }
943    
944        /**
945         * Returns a List view of the keys rather than a set view.  The returned
946         * list is unmodifiable.  This is required because changes to the values of
947         * the list (using {@link java.util.ListIterator#set(Object)}) will
948         * effectively remove the value from the list and reinsert that value at
949         * the end of the list, which is an unexpected side effect of changing the
950         * value of a list.  This occurs because changing the key, changes when the
951         * mapping is added to the map and thus where it appears in the list.
952         *
953         * <p>An alternative to this method is to use {@link #keySet()}
954         *
955         * @see #keySet()
956         * @return The ordered list of keys.  
957         */
958        public List sequence() {
959            List l = new ArrayList(size());
960            Iterator iter = keySet().iterator();
961            while (iter.hasNext()) {
962                l.add(iter.next());
963            }
964    
965            return UnmodifiableList.decorate(l);
966        }
967    
968        /**
969         * Removes the element at the specified index.
970         *
971         * @param index The index of the object to remove.
972         * @return      The previous value corresponding the <code>key</code>, or
973         *              <code>null</code> if none existed.
974         *
975         * @throws ArrayIndexOutOfBoundsException if the <code>index</code> is
976         * <code>&lt; 0</code> or <code>&gt;</code> the size of the map.
977         */
978        public Object remove(int index) {
979            return remove(get(index));
980        }
981    
982        // per Externalizable.readExternal(ObjectInput)
983    
984        /**
985         * Deserializes this map from the given stream.
986         *
987         * @param in the stream to deserialize from
988         * @throws IOException if the stream raises it
989         * @throws ClassNotFoundException if the stream raises it
990         */
991        public void readExternal(ObjectInput in) throws IOException, ClassNotFoundException {
992            int size = in.readInt();
993            for (int i = 0; i < size; i++) {
994                Object key = in.readObject();
995                Object value = in.readObject();
996                put(key, value);
997            }
998        }
999    
1000        /**
1001         * Serializes this map to the given stream.
1002         *
1003         * @param out  the stream to serialize to
1004         * @throws IOException  if the stream raises it
1005         */
1006        public void writeExternal(ObjectOutput out) throws IOException {
1007            out.writeInt(size());
1008            for (Entry pos = sentinel.next; pos != sentinel; pos = pos.next) {
1009                out.writeObject(pos.getKey());
1010                out.writeObject(pos.getValue());
1011            }
1012        }
1013    
1014        // add a serial version uid, so that if we change things in the future
1015        // without changing the format, we can still deserialize properly.
1016        private static final long serialVersionUID = 3380552487888102930L;
1017    
1018    }