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