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