Java > Open Source Codes > org > codehaus > aspectwerkz > util > SequencedHashMap


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

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags