SequencedHashMap


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