KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > enhydra > shark > utilities > SequencedHashMap


1 /*
2  * $Header: /cvsroot/shark/Shark/modules/SharkUtilities/Maps/src/org/enhydra/shark/utilities/SequencedHashMap.java,v 1.1 2004/03/24 15:52:14 chupo Exp $
3  * $Revision: 1.1 $
4  * $Date: 2004/03/24 15:52:14 $
5  *
6  * ====================================================================
7  *
8  * The Apache Software License, Version 1.1
9  *
10  * Copyright (c) 1999-2002 The Apache Software Foundation. All rights
11  * reserved.
12  *
13  * Redistribution and use in source and binary forms, with or without
14  * modification, are permitted provided that the following conditions
15  * are met:
16  *
17  * 1. Redistributions of source code must retain the above copyright
18  * notice, this list of conditions and the following disclaimer.
19  *
20  * 2. Redistributions in binary form must reproduce the above copyright
21  * notice, this list of conditions and the following disclaimer in
22  * the documentation and/or other materials provided with the
23  * distribution.
24  *
25  * 3. The end-user documentation included with the redistribution, if
26  * any, must include the following acknowlegement:
27  * "This product includes software developed by the
28  * Apache Software Foundation (http://www.apache.org/)."
29  * Alternately, this acknowlegement may appear in the software itself,
30  * if and wherever such third-party acknowlegements normally appear.
31  *
32  * 4. The names "The Jakarta Project", "Commons", and "Apache Software
33  * Foundation" must not be used to endorse or promote products derived
34  * from this software without prior written permission. For written
35  * permission, please contact apache@apache.org.
36  *
37  * 5. Products derived from this software may not be called "Apache"
38  * nor may "Apache" appear in their names without prior written
39  * permission of the Apache Group.
40  *
41  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
42  * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
43  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
44  * DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
45  * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
46  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
47  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
48  * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
49  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
50  * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
51  * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
52  * SUCH DAMAGE.
53  * ====================================================================
54  *
55  * This software consists of voluntary contributions made by many
56  * individuals on behalf of the Apache Software Foundation. For more
57  * information on the Apache Software Foundation, please see
58  * <http://www.apache.org/>.
59  *
60  */

61 package org.enhydra.shark.utilities;
62
63 import java.io.Externalizable JavaDoc;
64 import java.io.ObjectInput JavaDoc;
65 import java.io.ObjectOutput JavaDoc;
66 import java.io.IOException JavaDoc;
67
68 import java.util.Collection JavaDoc;
69 import java.util.Collections JavaDoc;
70 import java.util.HashMap JavaDoc;
71 import java.util.Iterator JavaDoc;
72 import java.util.AbstractCollection JavaDoc;
73 import java.util.AbstractSet JavaDoc;
74 import java.util.ArrayList JavaDoc;
75 import java.util.List JavaDoc;
76 import java.util.Map JavaDoc;
77 import java.util.Set JavaDoc;
78 import java.util.NoSuchElementException JavaDoc;
79 import java.util.ConcurrentModificationException JavaDoc;
80
81 /**
82  * A map of objects whose mapping entries are sequenced based on the order in
83  * which they were added. This data structure has fast <I>O(1)</I> search
84  * time, deletion time, and insertion time.
85  *
86  * <P>Although this map is sequenced, it cannot implement {@link
87  * java.util.List} because of incompatible interface definitions. The remove
88  * methods in List and Map have different return values (see: {@link
89  * java.util.List#remove(Object)} and {@link java.util.Map#remove(Object)}).
90  *
91  * <P>This class is not thread safe. When a thread safe implementation is
92  * required, use {@link Collections#synchronizedMap(Map)} as it is documented,
93  * or use explicit synchronization controls.
94  *
95  * @since 2.0
96  * @author <a HREF="mailto:mas@apache.org">Michael A. Smith</A>
97  * @author <a HREF="mailto:dlr@collab.net">Daniel Rall</a>
98  * @author <a HREF="mailto:hps@intermeta.de">Henning P. Schmiedehausen</a>
99  */

100 public class SequencedHashMap implements Map JavaDoc, Cloneable JavaDoc, Externalizable JavaDoc {
101
102   /**
103    * {@link java.util.Map.Entry} that doubles as a node in the linked list
104    * of sequenced mappings.
105    **/

106   private static class Entry implements Map.Entry JavaDoc {
107     // Note: This class cannot easily be made clonable. While the actual
108
// implementation of a clone would be simple, defining the semantics is
109
// difficult. If a shallow clone is implemented, then entry.next.prev !=
110
// entry, which is unintuitive and probably breaks all sorts of assumptions
111
// in code that uses this implementation. If a deep clone is
112
// implementated, then what happens when the linked list is cyclical (as is
113
// the case with SequencedHashMap)? It's impossible to know in the clone
114
// when to stop cloning, and thus you end up in a recursive loop,
115
// continuously cloning the "next" in the list.
116

117     private final Object JavaDoc key;
118     private Object JavaDoc value;
119
120     // package private to allow the SequencedHashMap to access and manipulate
121
// them.
122
Entry next = null;
123     Entry prev = null;
124
125     public Entry(Object JavaDoc key, Object JavaDoc value) {
126       this.key = key;
127       this.value = value;
128     }
129
130     // per Map.Entry.getKey()
131
public Object JavaDoc getKey() {
132       return this.key;
133     }
134
135     // per Map.Entry.getValue()
136
public Object JavaDoc getValue() {
137       return this.value;
138     }
139
140     // per Map.Entry.setValue()
141
public Object JavaDoc setValue(Object JavaDoc value) {
142       Object JavaDoc oldValue = this.value;
143       this.value = value;
144       return oldValue;
145     }
146
147     public int hashCode() {
148       // implemented per api docs for Map.Entry.hashCode()
149
return ((getKey() == null ? 0 : getKey().hashCode()) ^
150               (getValue()==null ? 0 : getValue().hashCode()));
151     }
152
153     public boolean equals(Object JavaDoc obj) {
154       if(obj == null) return false;
155       if(obj == this) return true;
156       if(!(obj instanceof Map.Entry JavaDoc)) return false;
157
158       Map.Entry JavaDoc other = (Map.Entry JavaDoc)obj;
159
160       // implemented per api docs for Map.Entry.equals(Object)
161
return((getKey() == null ?
162               other.getKey() == null :
163               getKey().equals(other.getKey())) &&
164              (getValue() == null ?
165               other.getValue() == null :
166               getValue().equals(other.getValue())));
167     }
168     public String JavaDoc toString() {
169       return "[" + getKey() + "=" + getValue() + "]";
170     }
171   }
172
173   /**
174    * Construct an empty sentinel used to hold the head (sentinel.next) and the
175    * tail (sentinel.prev) of the list. The sentinal has a <code>null</code>
176    * key and value.
177    **/

178   private static final Entry createSentinel() {
179     Entry s = new Entry(null, null);
180     s.prev = s;
181     s.next = s;
182     return s;
183   }
184
185   /**
186    * Sentinel used to hold the head and tail of the list of entries.
187    **/

188   private Entry sentinel;
189
190   /**
191    * Map of keys to entries
192    **/

193   private HashMap JavaDoc entries;
194
195   /**
196    * Holds the number of modifications that have occurred to the map,
197    * excluding modifications made through a collection view's iterator
198    * (e.g. entrySet().iterator().remove()). This is used to create a
199    * fail-fast behavior with the iterators.
200    **/

201   private transient long modCount = 0;
202
203   /**
204    * Construct a new sequenced hash map with default initial size and load
205    * factor.
206    **/

207   public SequencedHashMap() {
208     sentinel = createSentinel();
209     entries = new HashMap JavaDoc();
210   }
211
212   /**
213    * Construct a new sequenced hash map with the specified initial size and
214    * default load factor.
215    *
216    * @param initialSize the initial size for the hash table
217    *
218    * @see HashMap#HashMap(int)
219    **/

220   public SequencedHashMap(int initialSize) {
221     sentinel = createSentinel();
222     entries = new HashMap JavaDoc(initialSize);
223   }
224
225   /**
226    * Construct a new sequenced hash map with the specified initial size and
227    * load factor.
228    *
229    * @param initialSize the initial size for the hash table
230    *
231    * @param loadFactor the load factor for the hash table.
232    *
233    * @see HashMap#HashMap(int,float)
234    **/

235   public SequencedHashMap(int initialSize, float loadFactor) {
236     sentinel = createSentinel();
237     entries = new HashMap JavaDoc(initialSize, loadFactor);
238   }
239
240   /**
241    * Construct a new sequenced hash map and add all the elements in the
242    * specified map. The order in which the mappings in the specified map are
243    * added is defined by {@link #putAll(Map)}.
244    **/

245   public SequencedHashMap(Map JavaDoc m) {
246     this();
247     putAll(m);
248   }
249
250   /**
251    * Removes an internal entry from the linked list. This does not remove
252    * it from the underlying map.
253    **/

254   private void removeEntry(Entry entry) {
255     entry.next.prev = entry.prev;
256     entry.prev.next = entry.next;
257   }
258
259   /**
260    * Inserts a new internal entry to the tail of the linked list. This does
261    * not add the entry to the underlying map.
262    **/

263   private void insertEntry(Entry entry) {
264     entry.next = sentinel;
265     entry.prev = sentinel.prev;
266     sentinel.prev.next = entry;
267     sentinel.prev = entry;
268   }
269
270   // per Map.size()
271

272   /**
273    * Implements {@link Map#size()}.
274    */

275   public int size() {
276     // use the underlying Map's size since size is not maintained here.
277
return entries.size();
278   }
279
280   /**
281    * Implements {@link Map#isEmpty()}.
282    */

283   public boolean isEmpty() {
284     // for quick check whether the map is entry, we can check the linked list
285
// and see if there's anything in it.
286
return sentinel.next == sentinel;
287   }
288
289   /**
290    * Implements {@link Map#containsKey(Object)}.
291    */

292   public boolean containsKey(Object JavaDoc key) {
293     // pass on to underlying map implementation
294
return entries.containsKey(key);
295   }
296
297   /**
298    * Implements {@link Map#containsValue(Object)}.
299    */

300   public boolean containsValue(Object JavaDoc value) {
301     // unfortunately, we cannot just pass this call to the underlying map
302
// because we are mapping keys to entries, not keys to values. The
303
// underlying map doesn't have an efficient implementation anyway, so this
304
// isn't a big deal.
305

306     // do null comparison outside loop so we only need to do it once. This
307
// provides a tighter, more efficient loop at the expense of slight
308
// code duplication.
309
if(value == null) {
310       for(Entry pos = sentinel.next; pos != sentinel; pos = pos.next) {
311         if(pos.getValue() == null) return true;
312       }
313     } else {
314       for(Entry pos = sentinel.next; pos != sentinel; pos = pos.next) {
315         if(value.equals(pos.getValue())) return true;
316       }
317     }
318     return false;
319   }
320
321   /**
322    * Implements {@link Map#get(Object)}.
323    */

324   public Object JavaDoc get(Object JavaDoc o) {
325     // find entry for the specified key object
326
Entry entry = (Entry)entries.get(o);
327     if(entry == null) return null;
328
329     return entry.getValue();
330   }
331
332   /**
333    * Return the entry for the "oldest" mapping. That is, return the Map.Entry
334    * for the key-value pair that was first put into the map when compared to
335    * all the other pairings in the map. This behavior is equivalent to using
336    * <code>entrySet().iterator().next()</code>, but this method provides an
337    * optimized implementation.
338    *
339    * @return The first entry in the sequence, or <code>null</code> if the
340    * map is empty.
341    **/

342   public Map.Entry JavaDoc getFirst() {
343     // sentinel.next points to the "first" element of the sequence -- the head
344
// of the list, which is exactly the entry we need to return. We must test
345
// for an empty list though because we don't want to return the sentinel!
346
return (isEmpty()) ? null : sentinel.next;
347   }
348
349   /**
350    * Return the key for the "oldest" mapping. That is, return the key for the
351    * mapping that was first put into the map when compared to all the other
352    * objects in the map. This behavior is equivalent to using
353    * <code>getFirst().getKey()</code>, but this method provides a slightly
354    * optimized implementation.
355    *
356    * @return The first key in the sequence, or <code>null</code> if the
357    * map is empty.
358    **/

359   public Object JavaDoc getFirstKey() {
360     // sentinel.next points to the "first" element of the sequence -- the head
361
// of the list -- and the requisite key is returned from it. An empty list
362
// does not need to be tested. In cases where the list is empty,
363
// sentinel.next will point to the sentinel itself which has a null key,
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.next.getKey();
367   }
368
369   /**
370    * Return the value for the "oldest" mapping. That is, return the value for
371    * the mapping that was first put into the map when compared to all the
372    * other objects in the map. This behavior is equivalent to using
373    * <code>getFirst().getValue()</code>, but this method provides a slightly
374    * optimized implementation.
375    *
376    * @return The first value in the sequence, or <code>null</code> if the
377    * map is empty.
378    **/

379   public Object JavaDoc getFirstValue() {
380     // sentinel.next points to the "first" element of the sequence -- the head
381
// of the list -- and the requisite value is returned from it. An empty
382
// list does not need to be tested. In cases where the list is empty,
383
// sentinel.next will point to the sentinel itself which has a null value,
384
// which is exactly what we would want to return if the list is empty (a
385
// nice convient way to avoid test for an empty list)
386
return sentinel.next.getValue();
387   }
388
389   /**
390    * Return the entry for the "newest" mapping. That is, return the Map.Entry
391    * for the key-value pair that was first put into the map when compared to
392    * all the other pairings in the map. The behavior is equivalent to:
393    *
394    * <pre>
395    * Object obj = null;
396    * Iterator iter = entrySet().iterator();
397    * while(iter.hasNext()) {
398    * obj = iter.next();
399    * }
400    * return (Map.Entry)obj;
401    * </pre>
402    *
403    * However, the implementation of this method ensures an O(1) lookup of the
404    * last key rather than O(n).
405    *
406    * @return The last entry in the sequence, or <code>null</code> if the map
407    * is empty.
408    **/

409   public Map.Entry JavaDoc getLast() {
410     // sentinel.prev points to the "last" element of the sequence -- the tail
411
// of the list, which is exactly the entry we need to return. We must test
412
// for an empty list though because we don't want to return the sentinel!
413
return (isEmpty()) ? null : sentinel.prev;
414   }
415
416   /**
417    * Return the key for the "newest" mapping. That is, return the key for the
418    * mapping that was last put into the map when compared to all the other
419    * objects in the map. This behavior is equivalent to using
420    * <code>getLast().getKey()</code>, but this method provides a slightly
421    * optimized implementation.
422    *
423    * @return The last key in the sequence, or <code>null</code> if the map is
424    * empty.
425    **/

426   public Object JavaDoc getLastKey() {
427     // sentinel.prev points to the "last" element of the sequence -- the tail
428
// of the list -- and the requisite key is returned from it. An empty list
429
// does not need to be tested. In cases where the list is empty,
430
// sentinel.prev will point to the sentinel itself which has a null key,
431
// which is exactly what we would want to return if the list is empty (a
432
// nice convient way to avoid test for an empty list)
433
return sentinel.prev.getKey();
434   }
435
436   /**
437    * Return the value for the "newest" mapping. That is, return the value for
438    * the mapping that was last put into the map when compared to all the other
439    * objects in the map. This behavior is equivalent to using
440    * <code>getLast().getValue()</code>, but this method provides a slightly
441    * optimized implementation.
442    *
443    * @return The last value in the sequence, or <code>null</code> if the map
444    * is empty.
445    **/

446   public Object JavaDoc getLastValue() {
447     // sentinel.prev points to the "last" element of the sequence -- the tail
448
// of the list -- and the requisite value is returned from it. An empty
449
// list does not need to be tested. In cases where the list is empty,
450
// sentinel.prev will point to the sentinel itself which has a null value,
451
// which is exactly what we would want to return if the list is empty (a
452
// nice convient way to avoid test for an empty list)
453
return sentinel.prev.getValue();
454   }
455
456   /**
457    * Implements {@link Map#put(Object, Object)}.
458    */

459   public Object JavaDoc put(Object JavaDoc key, Object JavaDoc value) {
460     modCount++;
461
462     Object JavaDoc oldValue = null;
463
464     // lookup the entry for the specified key
465
Entry e = (Entry)entries.get(key);
466
467     // check to see if it already exists
468
if(e != null) {
469       // remove from list so the entry gets "moved" to the end of list
470
removeEntry(e);
471
472       // update value in map
473
oldValue = e.setValue(value);
474
475       // Note: We do not update the key here because its unnecessary. We only
476
// do comparisons using equals(Object) and we know the specified key and
477
// that in the map are equal in that sense. This may cause a problem if
478
// someone does not implement their hashCode() and/or equals(Object)
479
// method properly and then use it as a key in this map.
480
} else {
481       // add new entry
482
e = new Entry(key, value);
483       entries.put(key, e);
484     }
485     // assert(entry in map, but not list)
486

487     // add to list
488
insertEntry(e);
489
490     return oldValue;
491   }
492
493   /**
494    * Implements {@link Map#remove(Object)}.
495    */

496   public Object JavaDoc remove(Object JavaDoc key) {
497     Entry e = removeImpl(key);
498     return (e == null) ? null : e.getValue();
499   }
500
501   /**
502    * Fully remove an entry from the map, returning the old entry or null if
503    * there was no such entry with the specified key.
504    **/

505   private Entry removeImpl(Object JavaDoc key) {
506     Entry e = (Entry)entries.remove(key);
507     if(e == null) return null;
508     modCount++;
509     removeEntry(e);
510     return e;
511   }
512
513   /**
514    * Adds all the mappings in the specified map to this map, replacing any
515    * mappings that already exist (as per {@link Map#putAll(Map)}). The order
516    * in which the entries are added is determined by the iterator returned
517    * from {@link Map#entrySet()} for the specified map.
518    *
519    * @param t the mappings that should be added to this map.
520    *
521    * @exception NullPointerException if <code>t</code> is <code>null</code>
522    **/

523   public void putAll(Map JavaDoc t) {
524     Iterator JavaDoc iter = t.entrySet().iterator();
525     while(iter.hasNext()) {
526       Map.Entry JavaDoc entry = (Map.Entry JavaDoc)iter.next();
527       put(entry.getKey(), entry.getValue());
528     }
529   }
530
531   /**
532    * Implements {@link Map#clear()}.
533    */

534   public void clear() {
535     modCount++;
536
537     // remove all from the underlying map
538
entries.clear();
539
540     // and the list
541
sentinel.next = sentinel;
542     sentinel.prev = sentinel;
543   }
544
545   /**
546    * Implements {@link Map#equals(Object)}.
547    */

548   public boolean equals(Object JavaDoc obj) {
549     if(obj == null) return false;
550     if(obj == this) return true;
551
552     if(!(obj instanceof Map JavaDoc)) return false;
553
554     return entrySet().equals(((Map JavaDoc)obj).entrySet());
555   }
556
557   /**
558    * Implements {@link Map#hashCode()}.
559    */

560   public int hashCode() {
561     return entrySet().hashCode();
562   }
563
564   /**
565    * Provides a string representation of the entries within the map. The
566    * format of the returned string may change with different releases, so this
567    * method is suitable for debugging purposes only. If a specific format is
568    * required, use {@link #entrySet()}.{@link Set#iterator() iterator()} and
569    * iterate over the entries in the map formatting them as appropriate.
570    **/

571   public String JavaDoc toString() {
572     StringBuffer JavaDoc buf = new StringBuffer JavaDoc();
573     buf.append('[');
574     for(Entry pos = sentinel.next; pos != sentinel; pos = pos.next) {
575       buf.append(pos.getKey());
576       buf.append('=');
577       buf.append(pos.getValue());
578       if(pos.next != sentinel) {
579         buf.append(',');
580       }
581     }
582     buf.append(']');
583
584     return buf.toString();
585   }
586
587   /**
588    * Implements {@link Map#keySet()}.
589    */

590   public Set JavaDoc keySet() {
591     return new AbstractSet JavaDoc() {
592
593       // required impls
594
public Iterator JavaDoc iterator() { return new OrderedIterator(KEY); }
595       public boolean remove(Object JavaDoc o) {
596         Entry e = SequencedHashMap.this.removeImpl(o);
597         return (e != null);
598       }
599
600       // more efficient impls than abstract set
601
public void clear() {
602         SequencedHashMap.this.clear();
603       }
604       public int size() {
605         return SequencedHashMap.this.size();
606       }
607       public boolean isEmpty() {
608         return SequencedHashMap.this.isEmpty();
609       }
610       public boolean contains(Object JavaDoc o) {
611         return SequencedHashMap.this.containsKey(o);
612       }
613
614     };
615   }
616
617   /**
618    * Implements {@link Map#values()}.
619    */

620   public Collection JavaDoc values() {
621     return new AbstractCollection JavaDoc() {
622       // required impl
623
public Iterator JavaDoc iterator() { return new OrderedIterator(VALUE); }
624       public boolean remove(Object JavaDoc value) {
625         // do null comparison outside loop so we only need to do it once. This
626
// provides a tighter, more efficient loop at the expense of slight
627
// code duplication.
628
if(value == null) {
629           for(Entry pos = sentinel.next; pos != sentinel; pos = pos.next) {
630             if(pos.getValue() == null) {
631               SequencedHashMap.this.removeImpl(pos.getKey());
632               return true;
633             }
634           }
635         } else {
636           for(Entry pos = sentinel.next; pos != sentinel; pos = pos.next) {
637             if(value.equals(pos.getValue())) {
638               SequencedHashMap.this.removeImpl(pos.getKey());
639               return true;
640             }
641           }
642         }
643
644         return false;
645       }
646
647       // more efficient impls than abstract collection
648
public void clear() {
649         SequencedHashMap.this.clear();
650       }
651       public int size() {
652         return SequencedHashMap.this.size();
653       }
654       public boolean isEmpty() {
655         return SequencedHashMap.this.isEmpty();
656       }
657       public boolean contains(Object JavaDoc o) {
658         return SequencedHashMap.this.containsValue(o);
659       }
660     };
661   }
662
663   /**
664    * Implements {@link Map#entrySet()}.
665    */

666   public Set JavaDoc entrySet() {
667     return new AbstractSet JavaDoc() {
668       // helper
669
private Entry findEntry(Object JavaDoc o) {
670         if(o == null) return null;
671         if(!(o instanceof Map.Entry JavaDoc)) return null;
672
673         Map.Entry JavaDoc e = (Map.Entry JavaDoc)o;
674         Entry entry = (Entry)entries.get(e.getKey());
675         if(entry != null && entry.equals(e)) return entry;
676         else return null;
677       }
678
679       // required impl
680
public Iterator JavaDoc iterator() {
681         return new OrderedIterator(ENTRY);
682       }
683       public boolean remove(Object JavaDoc o) {
684         Entry e = findEntry(o);
685         if(e == null) return false;
686
687         return SequencedHashMap.this.removeImpl(e.getKey()) != null;
688       }
689
690       // more efficient impls than abstract collection
691
public void clear() {
692         SequencedHashMap.this.clear();
693       }
694       public int size() {
695         return SequencedHashMap.this.size();
696       }
697       public boolean isEmpty() {
698         return SequencedHashMap.this.isEmpty();
699       }
700       public boolean contains(Object JavaDoc o) {
701         return findEntry(o) != null;
702       }
703     };
704   }
705
706   // constants to define what the iterator should return on "next"
707
private static final int KEY = 0;
708   private static final int VALUE = 1;
709   private static final int ENTRY = 2;
710   private static final int REMOVED_MASK = 0x80000000;
711
712   private class OrderedIterator implements Iterator JavaDoc {
713     /**
714      * Holds the type that should be returned from the iterator. The value
715      * should be either {@link #KEY}, {@link #VALUE}, or {@link #ENTRY}. To
716      * save a tiny bit of memory, this field is also used as a marker for when
717      * remove has been called on the current object to prevent a second remove
718      * on the same element. Essientially, if this value is negative (i.e. the
719      * bit specified by {@link #REMOVED_MASK} is set), the current position
720      * has been removed. If positive, remove can still be called.
721      **/

722     private int returnType;
723
724     /**
725      * Holds the "current" position in the iterator. When pos.next is the
726      * sentinel, we've reached the end of the list.
727      **/

728     private Entry pos = sentinel;
729
730     /**
731      * Holds the expected modification count. If the actual modification
732      * count of the map differs from this value, then a concurrent
733      * modification has occurred.
734      **/

735     private transient long expectedModCount = modCount;
736
737     /**
738      * Construct an iterator over the sequenced elements in the order in which
739      * they were added. The {@link #next()} method returns the type specified
740      * by <code>returnType</code> which must be either {@link #KEY}, {@link
741      * #VALUE}, or {@link #ENTRY}.
742      **/

743     public OrderedIterator(int returnType) {
744       //// Since this is a private inner class, nothing else should have
745
//// access to the constructor. Since we know the rest of the outer
746
//// class uses the iterator correctly, we can leave of the following
747
//// check:
748
//if(returnType >= 0 && returnType <= 2) {
749
// throw new IllegalArgumentException("Invalid iterator type");
750
//}
751

752       // Set the "removed" bit so that the iterator starts in a state where
753
// "next" must be called before "remove" will succeed.
754
this.returnType = returnType | REMOVED_MASK;
755     }
756
757     /**
758      * Returns whether there is any additional elements in the iterator to be
759      * returned.
760      *
761      * @return <code>true</code> if there are more elements left to be
762      * returned from the iterator; <code>false</code> otherwise.
763      **/

764     public boolean hasNext() {
765       return pos.next != sentinel;
766     }
767
768     /**
769      * Returns the next element from the iterator.
770      *
771      * @return the next element from the iterator.
772      *
773      * @exception NoSuchElementException if there are no more elements in the
774      * iterator.
775      *
776      * @exception ConcurrentModificationException if a modification occurs in
777      * the underlying map.
778      **/

779     public Object JavaDoc next() {
780       if(modCount != expectedModCount) {
781         throw new ConcurrentModificationException JavaDoc();
782       }
783       if(pos.next == sentinel) {
784         throw new NoSuchElementException JavaDoc();
785       }
786
787       // clear the "removed" flag
788
returnType = returnType & ~REMOVED_MASK;
789
790       pos = pos.next;
791       switch(returnType) {
792       case KEY:
793         return pos.getKey();
794       case VALUE:
795         return pos.getValue();
796       case ENTRY:
797         return pos;
798       default:
799         // should never happen
800
throw new Error JavaDoc("bad iterator type: " + returnType);
801       }
802
803     }
804
805     /**
806      * Removes the last element returned from the {@link #next()} method from
807      * the sequenced map.
808      *
809      * @exception IllegalStateException if there isn't a "last element" to be
810      * removed. That is, if {@link #next()} has never been called, or if
811      * {@link #remove()} was already called on the element.
812      *
813      * @exception ConcurrentModificationException if a modification occurs in
814      * the underlying map.
815      **/

816     public void remove() {
817       if((returnType & REMOVED_MASK) != 0) {
818         throw new IllegalStateException JavaDoc("remove() must follow next()");
819       }
820       if(modCount != expectedModCount) {
821         throw new ConcurrentModificationException JavaDoc();
822       }
823
824       SequencedHashMap.this.removeImpl(pos.getKey());
825
826       // update the expected mod count for the remove operation
827
expectedModCount++;
828
829       // set the removed flag
830
returnType = returnType | REMOVED_MASK;
831     }
832   }
833
834   // APIs maintained from previous version of SequencedHashMap for backwards
835
// compatibility
836

837   /**
838    * Creates a shallow copy of this object, preserving the internal structure
839    * by copying only references. The keys and values themselves are not
840    * <code>clone()</code>'d. The cloned object maintains the same sequence.
841    *
842    * @return A clone of this instance.
843    *
844    * @exception CloneNotSupportedException if clone is not supported by a
845    * subclass.
846    */

847   public Object JavaDoc clone () throws CloneNotSupportedException JavaDoc {
848     // yes, calling super.clone() silly since we're just blowing away all
849
// the stuff that super might be doing anyway, but for motivations on
850
// this, see:
851
// http://www.javaworld.com/javaworld/jw-01-1999/jw-01-object.html
852
SequencedHashMap map = (SequencedHashMap)super.clone();
853
854     // create new, empty sentinel
855
map.sentinel = createSentinel();
856
857     // create a new, empty entry map
858
// note: this does not preserve the initial capacity and load factor.
859
map.entries = new HashMap JavaDoc();
860
861     // add all the mappings
862
map.putAll(this);
863
864     // Note: We cannot just clone the hashmap and sentinel because we must
865
// duplicate our internal structures. Cloning those two will not clone all
866
// the other entries they reference, and so the cloned hash map will not be
867
// able to maintain internal consistency because there are two objects with
868
// the same entries. See discussion in the Entry implementation on why we
869
// cannot implement a clone of the Entry (and thus why we need to recreate
870
// everything).
871

872     return map;
873   }
874
875   /**
876    * Returns the Map.Entry at the specified index
877    *
878    * @exception ArrayIndexOutOfBoundsException if the specified index is
879    * <code>&lt; 0</code> or <code>&gt;</code> the size of the map.
880    **/

881   private Map.Entry JavaDoc getEntry(int index) {
882     Entry pos = sentinel;
883
884     if(index < 0) {
885       throw new ArrayIndexOutOfBoundsException JavaDoc(index + " < 0");
886     }
887
888     // loop to one before the position
889
int i = -1;
890     while(i < (index-1) && pos.next != sentinel) {
891       i++;
892       pos = pos.next;
893     }
894     // pos.next is the requested position
895

896     // if sentinel is next, past end of list
897
if(pos.next == sentinel) {
898       throw new ArrayIndexOutOfBoundsException JavaDoc(index + " >= " + (i + 1));
899     }
900
901     return pos.next;
902   }
903
904   /**
905    * Returns the key at the specified index.
906    *
907    * @exception ArrayIndexOutOfBoundsException if the <code>index</code> is
908    * <code>&lt; 0</code> or <code>&gt;</code> the size of the map.
909    */

910   public Object JavaDoc get (int index)
911   {
912     return getEntry(index).getKey();
913   }
914
915   /**
916    * Returns the value at the specified index.
917    *
918    * @exception ArrayIndexOutOfBoundsException if the <code>index</code> is
919    * <code>&lt; 0</code> or <code>&gt;</code> the size of the map.
920    */

921   public Object JavaDoc getValue (int index)
922   {
923     return getEntry(index).getValue();
924   }
925
926   /**
927    * Returns the index of the specified key.
928    */

929   public int indexOf (Object JavaDoc key)
930   {
931     Entry e = (Entry)entries.get(key);
932     int pos = 0;
933     while(e.prev != sentinel) {
934       pos++;
935       e = e.prev;
936     }
937     return pos;
938   }
939
940   /**
941    * Returns a key iterator.
942    */

943   public Iterator JavaDoc iterator ()
944   {
945     return keySet().iterator();
946   }
947
948   /**
949    * Returns the last index of the specified key.
950    */

951   public int lastIndexOf (Object JavaDoc key)
952   {
953     // keys in a map are guarunteed to be unique
954
return indexOf(key);
955   }
956
957   /**
958    * Returns a List view of the keys rather than a set view. The returned
959    * list is unmodifiable. This is required because changes to the values of
960    * the list (using {@link java.util.ListIterator#set(Object)}) will
961    * effectively remove the value from the list and reinsert that value at
962    * the end of the list, which is an unexpected side effect of changing the
963    * value of a list. This occurs because changing the key, changes when the
964    * mapping is added to the map and thus where it appears in the list.
965    *
966    * <P>An alternative to this method is to use {@link #keySet()}
967    *
968    * @see #keySet()
969    * @return The ordered list of keys.
970    */

971   public List JavaDoc sequence()
972   {
973     List JavaDoc l = new ArrayList JavaDoc(size());
974     Iterator JavaDoc iter = keySet().iterator();
975     while(iter.hasNext()) {
976       l.add(iter.next());
977     }
978
979     return Collections.unmodifiableList(l);
980   }
981
982   /**
983    * Removes the element at the specified index.
984    *
985    * @param index The index of the object to remove.
986    * @return The previous value coressponding the <code>key</code>, or
987    * <code>null</code> if none existed.
988    *
989    * @exception ArrayIndexOutOfBoundsException if the <code>index</code> is
990    * <code>&lt; 0</code> or <code>&gt;</code> the size of the map.
991    */

992   public Object JavaDoc remove (int index)
993   {
994     return remove(get(index));
995   }
996
997   // per Externalizable.readExternal(ObjectInput)
998

999   /**
1000   * Deserializes this map from the given stream.
1001   *
1002   * @param in the stream to deserialize from
1003   * @throws IOException if the stream raises it
1004   * @throws ClassNotFoundException if the stream raises it
1005   */

1006  public void readExternal( ObjectInput JavaDoc in )
1007    throws IOException JavaDoc, ClassNotFoundException JavaDoc
1008  {
1009    int size = in.readInt();
1010    for(int i = 0; i < size; i++) {
1011      Object JavaDoc key = in.readObject();
1012      Object JavaDoc value = in.readObject();
1013      put(key, value);
1014    }
1015  }
1016
1017  /**
1018   * Serializes this map to the given stream.
1019   *
1020   * @param out the stream to serialize to
1021   * @throws IOException if the stream raises it
1022   */

1023  public void writeExternal( ObjectOutput JavaDoc out ) throws IOException JavaDoc {
1024    out.writeInt(size());
1025    for(Entry pos = sentinel.next; pos != sentinel; pos = pos.next) {
1026      out.writeObject(pos.getKey());
1027      out.writeObject(pos.getValue());
1028    }
1029  }
1030
1031  // add a serial version uid, so that if we change things in the future
1032
// without changing the format, we can still deserialize properly.
1033
private static final long serialVersionUID = 3380552487888102930L;
1034
1035}
1036
Popular Tags