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

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags