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