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 (Sam, 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>< 0</code> or
1056 * <code>></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>< 0</code> or
1094 * <code>></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>< 0</code> or
1110 * <code>></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>< 0</code> or
1203 * <code>></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 }