Java > Open Source Codes > org > apache > commons > collections > SequencedHashMap


1 /*
2  * Copyright 2002-2004 The Apache Software Foundation
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  * http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 package org.apache.commons.collections;
17
18 import java.io.Externalizable ;
19 import java.io.IOException ;
20 import java.io.ObjectInput ;
21 import java.io.ObjectOutput ;
22 import java.util.AbstractCollection ;
23 import java.util.AbstractSet ;
24 import java.util.ArrayList ;
25 import java.util.Collection ;
26 import java.util.ConcurrentModificationException ;
27 import java.util.HashMap ;
28 import java.util.Iterator ;
29 import java.util.List ;
30 import java.util.Map ;
31 import java.util.NoSuchElementException ;
32 import java.util.Set ;
33
34 import org.apache.commons.collections.list.UnmodifiableList;
35
36 /**
37  * A map of objects whose mapping entries are sequenced based on the order in
38  * which they were added. This data structure has fast <i>O(1)</i> search
39  * time, deletion time, and insertion time.
40  * <p>
41  * Although this map is sequenced, it cannot implement
42  * {@link java.util.List} because of incompatible interface definitions.
43  * The remove methods in List and Map have different return values
44  * (see: {@link java.util.List#remove(Object)} and {@link java.util.Map#remove(Object)}).
45  * <p>
46  * This class is not thread safe. When a thread safe implementation is
47  * required, use {@link java.util.Collections#synchronizedMap(Map)} as it is documented,
48  * or use explicit synchronization controls.
49  *
50  * @deprecated Replaced by LinkedMap and ListOrderedMap in map subpackage. Due to be removed in v4.0.
51  * @see org.apache.commons.collections.map.LinkedMap
52  * @see org.apache.commons.collections.map.ListOrderedMap
53  * @since Commons Collections 2.0
54  * @version $Revision: 1.28 $ $Date: 2004/02/18 01:15:42 $
55  *
56  * @author Michael A. Smith
57  * @author Daniel Rall
58  * @author Henning P. Schmiedehausen
59  * @author Stephen Colebourne
60  */
61 public class SequencedHashMap implements Map , Cloneable , Externalizable {
62
63     /**
64      * {@link java.util.Map.Entry} that doubles as a node in the linked list
65      * of sequenced mappings.
66      */
67     private static class Entry implements Map.Entry , KeyValue {
68         // Note: This class cannot easily be made clonable. While the actual
69 // implementation of a clone would be simple, defining the semantics is
70 // difficult. If a shallow clone is implemented, then entry.next.prev !=
71 // entry, which is unintuitive and probably breaks all sorts of assumptions
72 // in code that uses this implementation. If a deep clone is
73 // implemented, then what happens when the linked list is cyclical (as is
74 // the case with SequencedHashMap)? It's impossible to know in the clone
75 // when to stop cloning, and thus you end up in a recursive loop,
76 // continuously cloning the "next" in the list.
77
78         private final Object key;
79         private Object value;
80
81         // package private to allow the SequencedHashMap to access and manipulate
82 // them.
83 Entry next = null;
84         Entry prev = null;
85
86         public Entry(Object key, Object value) {
87             this.key = key;
88             this.value = value;
89         }
90
91         // per Map.Entry.getKey()
92 public Object getKey() {
93             return this.key;
94         }
95
96         // per Map.Entry.getValue()
97 public Object getValue() {
98             return this.value;
99         }
100
101         // per Map.Entry.setValue()
102 public Object setValue(Object value) {
103             Object oldValue = this.value;
104             this.value = value;
105             return oldValue;
106         }
107
108         public int hashCode() {
109             // implemented per api docs for Map.Entry.hashCode()
110 return ((getKey() == null ? 0 : getKey().hashCode()) ^ (getValue() == null ? 0 : getValue().hashCode()));
111         }
112
113         public boolean equals(Object obj) {
114             if (obj == null)
115                 return false;
116             if (obj == this)
117                 return true;
118             if (!(obj instanceof Map.Entry ))
119                 return false;
120
121             Map.Entry other = (Map.Entry ) obj;
122
123             // implemented per api docs for Map.Entry.equals(Object)
124 return (
125                 (getKey() == null ? other.getKey() == null : getKey().equals(other.getKey()))
126                     && (getValue() == null ? other.getValue() == null : getValue().equals(other.getValue())));
127         }
128         public String toString() {
129             return "[" + getKey() + "=" + getValue() + "]";
130         }
131     }
132
133     /**
134      * Construct an empty sentinel used to hold the head (sentinel.next) and the
135      * tail (sentinel.prev) of the list. The sentinel has a <code>null</code>
136      * key and value.
137      */
138     private static final Entry createSentinel() {
139         Entry s = new Entry(null, null);
140         s.prev = s;
141         s.next = s;
142         return s;
143     }
144
145     /**
146      * Sentinel used to hold the head and tail of the list of entries.
147      */
148     private Entry sentinel;
149
150     /**
151      * Map of keys to entries
152      */
153     private HashMap entries;
154
155     /**
156      * Holds the number of modifications that have occurred to the map,
157      * excluding modifications made through a collection view's iterator
158      * (e.g. entrySet().iterator().remove()). This is used to create a
159      * fail-fast behavior with the iterators.
160      */
161     private transient long modCount = 0;
162
163     /**
164      * Construct a new sequenced hash map with default initial size and load
165      * factor.
166      */
167     public SequencedHashMap() {
168         sentinel = createSentinel();
169         entries = new HashMap ();
170     }
171
172     /**
173      * Construct a new sequenced hash map with the specified initial size and
174      * default load factor.
175      *
176      * @param initialSize the initial size for the hash table
177      *
178      * @see HashMap#HashMap(int)
179      */
180     public SequencedHashMap(int initialSize) {
181         sentinel = createSentinel();
182         entries = new HashMap (initialSize);
183     }
184
185     /**
186      * Construct a new sequenced hash map with the specified initial size and
187      * load factor.
188      *
189      * @param initialSize the initial size for the hash table
190      *
191      * @param loadFactor the load factor for the hash table.
192      *
193      * @see HashMap#HashMap(int,float)
194      */
195     public SequencedHashMap(int initialSize, float loadFactor) {
196         sentinel = createSentinel();
197         entries = new HashMap (initialSize, loadFactor);
198     }
199
200     /**
201      * Construct a new sequenced hash map and add all the elements in the
202      * specified map. The order in which the mappings in the specified map are
203      * added is defined by {@link #putAll(Map)}.
204      */
205     public SequencedHashMap(Map m) {
206         this();
207         putAll(m);
208     }
209
210     /**
211      * Removes an internal entry from the linked list. This does not remove
212      * it from the underlying map.
213      */
214     private void removeEntry(Entry entry) {
215         entry.next.prev = entry.prev;
216         entry.prev.next = entry.next;
217     }
218
219     /**
220      * Inserts a new internal entry to the tail of the linked list. This does
221      * not add the entry to the underlying map.
222      */
223     private void insertEntry(Entry entry) {
224         entry.next = sentinel;
225         entry.prev = sentinel.prev;
226         sentinel.prev.next = entry;
227         sentinel.prev = entry;
228     }
229
230     // per Map.size()
231
232     /**
233      * Implements {@link Map#size()}.
234      */
235     public int size() {
236         // use the underlying Map's size since size is not maintained here.
237 return entries.size();
238     }
239
240     /**
241      * Implements {@link Map#isEmpty()}.
242      */
243     public boolean isEmpty() {
244         // for quick check whether the map is entry, we can check the linked list
245 // and see if there's anything in it.
246 return sentinel.next == sentinel;
247     }
248
249     /**
250      * Implements {@link Map#containsKey(Object)}.
251      */
252     public boolean containsKey(Object key) {
253         // pass on to underlying map implementation
254 return entries.containsKey(key);
255     }
256
257     /**
258      * Implements {@link Map#containsValue(Object)}.
259      */
260     public boolean containsValue(Object value) {
261         // unfortunately, we cannot just pass this call to the underlying map
262 // because we are mapping keys to entries, not keys to values. The
263 // underlying map doesn't have an efficient implementation anyway, so this
264 // isn't a big deal.
265
266         // do null comparison outside loop so we only need to do it once. This
267 // provides a tighter, more efficient loop at the expense of slight
268 // code duplication.
269 if (value == null) {
270             for (Entry pos = sentinel.next; pos != sentinel; pos = pos.next) {
271                 if (pos.getValue() == null)
272                     return true;
273             }
274         } else {
275             for (Entry pos = sentinel.next; pos != sentinel; pos = pos.next) {
276                 if (value.equals(pos.getValue()))
277                     return true;
278             }
279         }
280         return false;
281     }
282
283     /**
284      * Implements {@link Map#get(Object)}.
285      */
286     public Object get(Object o) {
287         // find entry for the specified key object
288 Entry entry = (Entry) entries.get(o);
289         if (entry == null)
290             return null;
291
292         return entry.getValue();
293     }
294
295     /**
296      * Return the entry for the "oldest" mapping. That is, return the Map.Entry
297      * for the key-value pair that was first put into the map when compared to
298      * all the other pairings in the map. This behavior is equivalent to using
299      * <code>entrySet().iterator().next()</code>, but this method provides an
300      * optimized implementation.
301      *
302      * @return The first entry in the sequence, or <code>null</code> if the
303      * map is empty.
304      */
305     public Map.Entry getFirst() {
306         // sentinel.next points to the "first" element of the sequence -- the head
307 // of the list, which is exactly the entry we need to return. We must test
308 // for an empty list though because we don't want to return the sentinel!
309 return (isEmpty()) ? null : sentinel.next;
310     }
311
312     /**
313      * Return the key for the "oldest" mapping. That is, return the key for the
314      * mapping that was first put into the map when compared to all the other
315      * objects in the map. This behavior is equivalent to using
316      * <code>getFirst().getKey()</code>, but this method provides a slightly
317      * optimized implementation.
318      *
319      * @return The first key in the sequence, or <code>null</code> if the
320      * map is empty.
321      */
322     public Object getFirstKey() {
323         // sentinel.next points to the "first" element of the sequence -- the head
324 // of the list -- and the requisite key is returned from it. An empty list
325 // does not need to be tested. In cases where the list is empty,
326 // sentinel.next will point to the sentinel itself which has a null key,
327 // which is exactly what we would want to return if the list is empty (a
328 // nice convenient way to avoid test for an empty list)
329 return sentinel.next.getKey();
330     }
331
332     /**
333      * Return the value for the "oldest" mapping. That is, return the value for
334      * the mapping that was first put into the map when compared to all the
335      * other objects in the map. This behavior is equivalent to using
336      * <code>getFirst().getValue()</code>, but this method provides a slightly
337      * optimized implementation.
338      *
339      * @return The first value in the sequence, or <code>null</code> if the
340      * map is empty.
341      */
342     public Object getFirstValue() {
343         // sentinel.next points to the "first" element of the sequence -- the head
344 // of the list -- and the requisite value is returned from it. An empty
345 // list does not need to be tested. In cases where the list is empty,
346 // sentinel.next will point to the sentinel itself which has a null value,
347 // which is exactly what we would want to return if the list is empty (a
348 // nice convenient way to avoid test for an empty list)
349 return sentinel.next.getValue();
350     }
351
352     /**
353      * Return the entry for the "newest" mapping. That is, return the Map.Entry
354      * for the key-value pair that was first put into the map when compared to
355      * all the other pairings in the map. The behavior is equivalent to:
356      *
357      * <pre>
358      * Object obj = null;
359      * Iterator iter = entrySet().iterator();
360      * while(iter.hasNext()) {
361      * obj = iter.next();
362      * }
363      * return (Map.Entry)obj;
364      * </pre>
365      *
366      * However, the implementation of this method ensures an O(1) lookup of the
367      * last key rather than O(n).
368      *
369      * @return The last entry in the sequence, or <code>null</code> if the map
370      * is empty.
371      */
372     public Map.Entry getLast() {
373         // sentinel.prev points to the "last" element of the sequence -- the tail
374 // of the list, which is exactly the entry we need to return. We must test
375 // for an empty list though because we don't want to return the sentinel!
376 return (isEmpty()) ? null : sentinel.prev;
377     }
378
379     /**
380      * Return the key for the "newest" mapping. That is, return the key for the
381      * mapping that was last put into the map when compared to all the other
382      * objects in the map. This behavior is equivalent to using
383      * <code>getLast().getKey()</code>, but this method provides a slightly
384      * optimized implementation.
385      *
386      * @return The last key in the sequence, or <code>null</code> if the map is
387      * empty.
388      */
389     public Object getLastKey() {
390         // sentinel.prev points to the "last" element of the sequence -- the tail
391 // of the list -- and the requisite key is returned from it. An empty list
392 // does not need to be tested. In cases where the list is empty,
393 // sentinel.prev will point to the sentinel itself which has a null key,
394 // which is exactly what we would want to return if the list is empty (a
395 // nice convenient way to avoid test for an empty list)
396 return sentinel.prev.getKey();
397     }
398
399     /**
400      * Return the value for the "newest" mapping. That is, return the value for
401      * the mapping that was last put into the map when compared to all the other
402      * objects in the map. This behavior is equivalent to using
403      * <code>getLast().getValue()</code>, but this method provides a slightly
404      * optimized implementation.
405      *
406      * @return The last value in the sequence, or <code>null</code> if the map
407      * is empty.
408      */
409     public Object getLastValue() {
410         // sentinel.prev points to the "last" element of the sequence -- the tail
411 // of the list -- and the requisite value is returned from it. An empty
412 // list does not need to be tested. In cases where the list is empty,
413 // sentinel.prev will point to the sentinel itself which has a null value,
414 // which is exactly what we would want to return if the list is empty (a
415 // nice convenient way to avoid test for an empty list)
416 return sentinel.prev.getValue();
417     }
418
419     /**
420      * Implements {@link Map#put(Object, Object)}.
421      */
422     public Object put(Object key, Object value) {
423         modCount++;
424
425         Object oldValue = null;
426
427         // lookup the entry for the specified key
428 Entry e = (Entry) entries.get(key);
429
430         // check to see if it already exists
431 if (e != null) {
432             // remove from list so the entry gets "moved" to the end of list
433 removeEntry(e);
434
435             // update value in map
436 oldValue = e.setValue(value);
437
438             // Note: We do not update the key here because its unnecessary. We only
439 // do comparisons using equals(Object) and we know the specified key and
440 // that in the map are equal in that sense. This may cause a problem if
441 // someone does not implement their hashCode() and/or equals(Object)
442 // method properly and then use it as a key in this map.
443 } else {
444             // add new entry
445 e = new Entry(key, value);
446             entries.put(key, e);
447         }
448         // assert(entry in map, but not list)
449
450         // add to list
451 insertEntry(e);
452
453         return oldValue;
454     }
455
456     /**
457      * Implements {@link Map#remove(Object)}.
458      */
459     public Object remove(Object key) {
460         Entry e = removeImpl(key);
461         return (e == null) ? null : e.getValue();
462     }
463
464     /**
465      * Fully remove an entry from the map, returning the old entry or null if
466      * there was no such entry with the specified key.
467      */
468     private Entry removeImpl(Object key) {
469         Entry e = (Entry) entries.remove(key);
470         if (e == null)
471             return null;
472         modCount++;
473         removeEntry(e);
474         return e;
475     }
476
477     /**
478      * Adds all the mappings in the specified map to this map, replacing any
479      * mappings that already exist (as per {@link Map#putAll(Map)}). The order
480      * in which the entries are added is determined by the iterator returned
481      * from {@link Map#entrySet()} for the specified map.
482      *
483      * @param t the mappings that should be added to this map.
484      *
485      * @throws NullPointerException if <code>t</code> is <code>null</code>
486      */
487     public void putAll(Map t) {
488         Iterator iter = t.entrySet().iterator();
489         while (iter.hasNext()) {
490             Map.Entry entry = (Map.Entry ) iter.next();
491             put(entry.getKey(), entry.getValue());
492         }
493     }
494
495     /**
496      * Implements {@link Map#clear()}.
497      */
498     public void clear() {
499         modCount++;
500
501         // remove all from the underlying map
502 entries.clear();
503
504         // and the list
505 sentinel.next = sentinel;
506         sentinel.prev = sentinel;
507     }
508
509     /**
510      * Implements {@link Map#equals(Object)}.
511      */
512     public boolean equals(Object obj) {
513         if (obj == null)
514             return false;
515         if (obj == this)
516             return true;
517
518         if (!(obj instanceof Map ))
519             return false;
520
521         return entrySet().equals(((Map ) obj).entrySet());
522     }
523
524     /**
525      * Implements {@link Map#hashCode()}.
526      */
527     public int hashCode() {
528         return entrySet().hashCode();
529     }
530
531     /**
532      * Provides a string representation of the entries within the map. The
533      * format of the returned string may change with different releases, so this
534      * method is suitable for debugging purposes only. If a specific format is
535      * required, use {@link #entrySet()}.{@link Set#iterator() iterator()} and
536      * iterate over the entries in the map formatting them as appropriate.
537      */
538     public String toString() {
539         StringBuffer buf = new StringBuffer ();
540         buf.append('[');
541         for (Entry pos = sentinel.next; pos != sentinel; pos = pos.next) {
542             buf.append(pos.getKey());
543             buf.append('=');
544             buf.append(pos.getValue());
545             if (pos.next != sentinel) {
546                 buf.append(',');
547             }
548         }
549         buf.append(']');
550
551         return buf.toString();
552     }
553
554     /**
555      * Implements {@link Map#keySet()}.
556      */
557     public Set keySet() {
558         return new AbstractSet () {
559
560             // required impls
561 public Iterator iterator() {
562                 return new OrderedIterator(KEY);
563             }
564             public boolean remove(Object o) {
565                 Entry e = SequencedHashMap.this.removeImpl(o);
566                 return (e != null);
567             }
568
569             // more efficient impls than abstract set
570 public void clear() {
571                 SequencedHashMap.this.clear();
572             }
573             public int size() {
574                 return SequencedHashMap.this.size();
575             }
576             public boolean isEmpty() {
577                 return SequencedHashMap.this.isEmpty();
578             }
579             public boolean contains(Object o) {
580                 return SequencedHashMap.this.containsKey(o);
581             }
582
583         };
584     }
585
586     /**
587      * Implements {@link Map#values()}.
588      */
589     public Collection values() {
590         return new AbstractCollection () {
591             // required impl
592 public Iterator iterator() {
593                 return new OrderedIterator(VALUE);
594             }
595             public boolean remove(Object value) {
596                 // do null comparison outside loop so we only need to do it once. This
597 // provides a tighter, more efficient loop at the expense of slight
598 // code duplication.
599 if (value == null) {
600                     for (Entry pos = sentinel.next; pos != sentinel; pos = pos.next) {
601                         if (pos.getValue() == null) {
602                             SequencedHashMap.this.removeImpl(pos.getKey());
603                             return true;
604                         }
605                     }
606                 } else {
607                     for (Entry pos = sentinel.next; pos != sentinel; pos = pos.next) {
608                         if (value.equals(pos.getValue())) {
609                             SequencedHashMap.this.removeImpl(pos.getKey());
610                             return true;
611                         }
612                     }
613                 }
614
615                 return false;
616             }
617
618             // more efficient impls than abstract collection
619 public void clear() {
620                 SequencedHashMap.this.clear();
621             }
622             public int size() {
623                 return SequencedHashMap.this.size();
624             }
625             public boolean isEmpty() {
626                 return SequencedHashMap.this.isEmpty();
627             }
628             public boolean contains(Object o) {
629                 return SequencedHashMap.this.containsValue(o);
630             }
631         };
632     }
633
634     /**
635      * Implements {@link Map#entrySet()}.
636      */
637     public Set entrySet() {
638         return new AbstractSet () {
639             // helper
640 private Entry findEntry(Object o) {
641                 if (o == null)
642                     return null;
643                 if (!(o instanceof Map.Entry ))
644                     return null;
645
646                 Map.Entry e = (Map.Entry ) o;
647                 Entry entry = (Entry) entries.get(e.getKey());
648                 if (entry != null && entry.equals(e))
649                     return entry;
650                 else
651                     return null;
652             }
653
654             // required impl
655 public Iterator iterator() {
656                 return new OrderedIterator(ENTRY);
657             }
658             public boolean remove(Object o) {
659                 Entry e = findEntry(o);
660                 if (e == null)
661                     return false;
662
663                 return SequencedHashMap.this.removeImpl(e.getKey()) != null;
664             }
665
666             // more efficient impls than abstract collection
667 public void clear() {
668                 SequencedHashMap.this.clear();
669             }
670             public int size() {
671                 return SequencedHashMap.this.size();
672             }
673             public boolean isEmpty() {
674                 return SequencedHashMap.this.isEmpty();
675             }
676             public boolean contains(Object o) {
677                 return findEntry(o) != null;
678             }
679         };
680     }
681
682     // constants to define what the iterator should return on "next"
683 private static final int KEY = 0;
684     private static final int VALUE = 1;
685     private static final int ENTRY = 2;
686     private static final int REMOVED_MASK = 0x80000000;
687
688     private class OrderedIterator implements Iterator {
689         /**
690          * Holds the type that should be returned from the iterator. The value
691          * should be either {@link #KEY}, {@link #VALUE}, or {@link #ENTRY}. To
692          * save a tiny bit of memory, this field is also used as a marker for when
693          * remove has been called on the current object to prevent a second remove
694          * on the same element. Essentially, if this value is negative (i.e. the
695          * bit specified by {@link #REMOVED_MASK} is set), the current position
696          * has been removed. If positive, remove can still be called.
697          */
698         private int returnType;
699
700         /**
701          * Holds the "current" position in the iterator. When pos.next is the
702          * sentinel, we've reached the end of the list.
703          */
704         private Entry pos = sentinel;
705
706         /**
707          * Holds the expected modification count. If the actual modification
708          * count of the map differs from this value, then a concurrent
709          * modification has occurred.
710          */
711         private transient long expectedModCount = modCount;
712
713         /**
714          * Construct an iterator over the sequenced elements in the order in which
715          * they were added. The {@link #next()} method returns the type specified
716          * by <code>returnType</code> which must be either {@link #KEY}, {@link
717          * #VALUE}, or {@link #ENTRY}.
718          */
719         public OrderedIterator(int returnType) {
720             //// Since this is a private inner class, nothing else should have
721 //// access to the constructor. Since we know the rest of the outer
722 //// class uses the iterator correctly, we can leave of the following
723 //// check:
724 //if(returnType >= 0 && returnType <= 2) {
725 // throw new IllegalArgumentException("Invalid iterator type");
726 //}
727
728             // Set the "removed" bit so that the iterator starts in a state where
729 // "next" must be called before "remove" will succeed.
730 this.returnType = returnType | REMOVED_MASK;
731         }
732
733         /**
734          * Returns whether there is any additional elements in the iterator to be
735          * returned.
736          *
737          * @return <code>true</code> if there are more elements left to be
738          * returned from the iterator; <code>false</code> otherwise.
739          */
740         public boolean hasNext() {
741             return pos.next != sentinel;
742         }
743
744         /**
745          * Returns the next element from the iterator.
746          *
747          * @return the next element from the iterator.
748          *
749          * @throws NoSuchElementException if there are no more elements in the
750          * iterator.
751          *
752          * @throws ConcurrentModificationException if a modification occurs in
753          * the underlying map.
754          */
755         public Object next() {
756             if (modCount != expectedModCount) {
757                 throw new ConcurrentModificationException ();
758             }
759             if (pos.next == sentinel) {
760                 throw new NoSuchElementException ();
761             }
762
763             // clear the "removed" flag
764 returnType = returnType & ~REMOVED_MASK;
765
766             pos = pos.next;
767             switch (returnType) {
768                 case KEY :
769                     return pos.getKey();
770                 case VALUE :
771                     return pos.getValue();
772                 case ENTRY :
773                     return pos;
774                 default :
775                     // should never happen
776 throw new Error ("bad iterator type: " + returnType);
777             }
778
779         }
780
781         /**
782          * Removes the last element returned from the {@link #next()} method from
783          * the sequenced map.
784          *
785          * @throws IllegalStateException if there isn't a "last element" to be
786          * removed. That is, if {@link #next()} has never been called, or if
787          * {@link #remove()} was already called on the element.
788          *
789          * @throws ConcurrentModificationException if a modification occurs in
790          * the underlying map.
791          */
792         public void remove() {
793             if ((returnType & REMOVED_MASK) != 0) {
794                 throw new IllegalStateException ("remove() must follow next()");
795             }
796             if (modCount != expectedModCount) {
797                 throw new ConcurrentModificationException ();
798             }
799
800             SequencedHashMap.this.removeImpl(pos.getKey());
801
802             // update the expected mod count for the remove operation
803 expectedModCount++;
804
805             // set the removed flag
806 returnType = returnType | REMOVED_MASK;
807         }
808     }
809
810     // APIs maintained from previous version of SequencedHashMap for backwards
811 // compatibility
812
813     /**
814      * Creates a shallow copy of this object, preserving the internal structure
815      * by copying only references. The keys and values themselves are not
816      * <code>clone()</code>'d. The cloned object maintains the same sequence.
817      *
818      * @return A clone of this instance.
819      *
820      * @throws CloneNotSupportedException if clone is not supported by a
821      * subclass.
822      */
823     public Object clone() throws CloneNotSupportedException {
824         // yes, calling super.clone() silly since we're just blowing away all
825 // the stuff that super might be doing anyway, but for motivations on
826 // this, see:
827 // http://www.javaworld.com/javaworld/jw-01-1999/jw-01-object.html
828 SequencedHashMap map = (SequencedHashMap) super.clone();
829
830         // create new, empty sentinel
831 map.sentinel = createSentinel();
832
833         // create a new, empty entry map
834 // note: this does not preserve the initial capacity and load factor.
835 map.entries = new HashMap ();
836
837         // add all the mappings
838 map.putAll(this);
839
840         // Note: We cannot just clone the hashmap and sentinel because we must
841 // duplicate our internal structures. Cloning those two will not clone all
842 // the other entries they reference, and so the cloned hash map will not be
843 // able to maintain internal consistency because there are two objects with
844 // the same entries. See discussion in the Entry implementation on why we
845 // cannot implement a clone of the Entry (and thus why we need to recreate
846 // everything).
847
848         return map;
849     }
850
851     /**
852      * Returns the Map.Entry at the specified index
853      *
854      * @throws ArrayIndexOutOfBoundsException if the specified index is
855      * <code>&lt; 0</code> or <code>&gt;</code> the size of the map.
856      */
857     private Map.Entry getEntry(int index) {
858         Entry pos = sentinel;
859
860         if (index < 0) {
861             throw new ArrayIndexOutOfBoundsException (index + " < 0");
862         }
863
864         // loop to one before the position
865 int i = -1;
866         while (i < (index - 1) && pos.next != sentinel) {
867             i++;
868             pos = pos.next;
869         }
870         // pos.next is the requested position
871
872         // if sentinel is next, past end of list
873 if (pos.next == sentinel) {
874             throw new ArrayIndexOutOfBoundsException (index + " >= " + (i + 1));
875         }
876
877         return pos.next;
878     }
879
880     /**
881      * Gets the key at the specified index.
882      *
883      * @param index the index to retrieve
884      * @return the key at the specified index, or null
885      * @throws ArrayIndexOutOfBoundsException if the <code>index</code> is
886      * <code>&lt; 0</code> or <code>&gt;</code> the size of the map.
887      */
888     public Object get(int index) {
889         return getEntry(index).getKey();
890     }
891
892     /**
893      * Gets the value at the specified index.
894      *
895      * @param index the index to retrieve
896      * @return the value at the specified index, or null
897      * @throws ArrayIndexOutOfBoundsException if the <code>index</code> is
898      * <code>&lt; 0</code> or <code>&gt;</code> the size of the map.
899      */
900     public Object getValue(int index) {
901         return getEntry(index).getValue();
902     }
903
904     /**
905      * Gets the index of the specified key.
906      *
907      * @param key the key to find the index of
908      * @return the index, or -1 if not found
909      */
910     public int indexOf(Object key) {
911         Entry e = (Entry) entries.get(key);
912         if (e == null) {
913             return -1;
914         }
915         int pos = 0;
916         while (e.prev != sentinel) {
917             pos++;
918             e = e.prev;
919         }
920         return pos;
921     }
922
923     /**
924      * Gets an iterator over the keys.
925      *
926      * @return an iterator over the keys
927      */
928     public Iterator iterator() {
929         return keySet().iterator();
930     }
931
932     /**
933      * Gets the last index of the specified key.
934      *
935      * @param key the key to find the index of
936      * @return the index, or -1 if not found
937      */
938     public int lastIndexOf(Object key) {
939         // keys in a map are guaranteed to be unique
940 return indexOf(key);
941     }
942
943     /**
944      * Returns a List view of the keys rather than a set view. The returned
945      * list is unmodifiable. This is required because changes to the values of
946      * the list (using {@link java.util.ListIterator#set(Object)}) will
947      * effectively remove the value from the list and reinsert that value at
948      * the end of the list, which is an unexpected side effect of changing the
949      * value of a list. This occurs because changing the key, changes when the
950      * mapping is added to the map and thus where it appears in the list.
951      *
952      * <p>An alternative to this method is to use {@link #keySet()}
953      *
954      * @see #keySet()
955      * @return The ordered list of keys.
956      */
957     public List sequence() {
958         List l = new ArrayList (size());
959         Iterator iter = keySet().iterator();
960         while (iter.hasNext()) {
961             l.add(iter.next());
962         }
963
964         return UnmodifiableList.decorate(l);
965     }
966
967     /**
968      * Removes the element at the specified index.
969      *
970      * @param index The index of the object to remove.
971      * @return The previous value corresponding the <code>key</code>, or
972      * <code>null</code> if none existed.
973      *
974      * @throws ArrayIndexOutOfBoundsException if the <code>index</code> is
975      * <code>&lt; 0</code> or <code>&gt;</code> the size of the map.
976      */
977     public Object remove(int index) {
978         return remove(get(index));
979     }
980
981     // per Externalizable.readExternal(ObjectInput)
982
983     /**
984      * Deserializes this map from the given stream.
985      *
986      * @param in the stream to deserialize from
987      * @throws IOException if the stream raises it
988      * @throws ClassNotFoundException if the stream raises it
989      */
990     public void readExternal(ObjectInput in) throws IOException , ClassNotFoundException {
991         int size = in.readInt();
992         for (int i = 0; i < size; i++) {
993             Object key = in.readObject();
994             Object value = in.readObject();
995             put(key, value);
996         }
997     }
998
999     /**
1000     * Serializes this map to the given stream.
1001     *
1002     * @param out the stream to serialize to
1003     * @throws IOException if the stream raises it
1004     */
1005    public void writeExternal(ObjectOutput out) throws IOException {
1006        out.writeInt(size());
1007        for (Entry pos = sentinel.next; pos != sentinel; pos = pos.next) {
1008            out.writeObject(pos.getKey());
1009            out.writeObject(pos.getValue());
1010        }
1011    }
1012
1013    // add a serial version uid, so that if we change things in the future
1014 // without changing the format, we can still deserialize properly.
1015 private static final long serialVersionUID = 3380552487888102930L;
1016
1017}
1018

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags