jcoverage | summary | package | file

Coverage details for org.chwf.util.SequencedHashMap

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

jcoverage | summary | package | file

this report was generated by version 1.0.5 of jcoverage.
visit www.jcoverage.com for updates.

copyright © 2003, jcoverage ltd. all rights reserved.
Java is a trademark of Sun Microsystems, Inc. in the United States and other countries.