View Javadoc
1   /*
2    *  Licensed to the Apache Software Foundation (ASF) under one
3    *  or more contributor license agreements.  See the NOTICE file
4    *  distributed with this work for additional information
5    *  regarding copyright ownership.  The ASF licenses this file
6    *  to you under the Apache License, Version 2.0 (the
7    *  "License"); you may not use this file except in compliance
8    *  with the License.  You may obtain a copy of the License at
9    *  
10   *    http://www.apache.org/licenses/LICENSE-2.0
11   *  
12   *  Unless required by applicable law or agreed to in writing,
13   *  software distributed under the License is distributed on an
14   *  "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
15   *  KIND, either express or implied.  See the License for the
16   *  specific language governing permissions and limitations
17   *  under the License. 
18   *  
19   */
20  package org.apache.directory.api.util;
21  
22  
23  import java.io.Externalizable;
24  import java.io.IOException;
25  import java.io.ObjectInput;
26  import java.io.ObjectOutput;
27  import java.util.AbstractCollection;
28  import java.util.AbstractSet;
29  import java.util.ArrayList;
30  import java.util.Collection;
31  import java.util.Collections;
32  import java.util.ConcurrentModificationException;
33  import java.util.HashMap;
34  import java.util.Iterator;
35  import java.util.List;
36  import java.util.Map;
37  import java.util.NoSuchElementException;
38  import java.util.Set;
39  
40  import org.apache.directory.api.i18n.I18n;
41  
42  
43  /**
44   * A map of objects whose mapping entries are sequenced based on the order in
45   * which they were added. This data structure has fast <i>O(1)</i> search time,
46   * deletion time, and insertion time.
47   * <p>
48   * Although this map is sequenced, it cannot implement {@link java.util.List}
49   * because of incompatible interface definitions. The remove methods in List and
50   * Map have different return values (see: {@link java.util.List#remove(Object)}
51   * and {@link java.util.Map#remove(Object)}).
52   * <p>
53   * This class is not thread safe. When a thread safe implementation is required,
54   * use {@link java.util.Collections#synchronizedMap(Map)} as it is documented,
55   * or use explicit synchronization controls.
56   * 
57   * @since Commons Collections 2.0
58   * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
59   */
60  @SuppressWarnings("rawtypes")
61  public class SequencedHashMap implements Map, Cloneable, Externalizable
62  {
63  
64      /**
65       * {@link java.util.Map.Entry} that doubles as a node in the linked list of
66       * sequenced mappings.
67       */
68      private static class Entry implements Map.Entry, KeyValue
69      {
70          // Note: This class cannot easily be made clonable. While the actual
71          // implementation of a clone would be simple, defining the semantics is
72          // difficult. If a shallow clone is implemented, then entry.next.prev !=
73          // entry, which is un-intuitive and probably breaks all sorts of
74          // assumptions
75          // in code that uses this implementation. If a deep clone is
76          // implemented, then what happens when the linked list is cyclical (as
77          // is
78          // the case with SequencedHashMap)? It's impossible to know in the clone
79          // when to stop cloning, and thus you end up in a recursive loop,
80          // continuously cloning the "next" in the list.
81  
82          private final Object key;
83  
84          private Object value;
85  
86          // package private to allow the SequencedHashMap to access and
87          // manipulate
88          // them.
89          Entry next = null;
90  
91          Entry prev = null;
92  
93  
94          public Entry( Object key, Object value )
95          {
96              this.key = key;
97              this.value = value;
98          }
99  
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 value )
117         {
118             Object oldValue = this.value;
119             this.value = value;
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 }