commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From morg...@apache.org
Subject cvs commit: jakarta-commons/collections/src/java/org/apache/commons/collections SequencedHashMap.java
Date Mon, 18 Feb 2002 20:34:57 GMT
morgand     02/02/18 12:34:57

  Modified:    collections/src/java/org/apache/commons/collections
                        SequencedHashMap.java
  Log:
  complete re-implementation of SequencedHashMap submitted by
  Michael Smith
  
  Revision  Changes    Path
  1.3       +799 -230  jakarta-commons/collections/src/java/org/apache/commons/collections/SequencedHashMap.java
  
  Index: SequencedHashMap.java
  ===================================================================
  RCS file: /home/cvs/jakarta-commons/collections/src/java/org/apache/commons/collections/SequencedHashMap.java,v
  retrieving revision 1.2
  retrieving revision 1.3
  diff -u -r1.2 -r1.3
  --- SequencedHashMap.java	10 Feb 2002 08:07:42 -0000	1.2
  +++ SequencedHashMap.java	18 Feb 2002 20:34:57 -0000	1.3
  @@ -1,7 +1,7 @@
   /*
  - * $Header: /home/cvs/jakarta-commons/collections/src/java/org/apache/commons/collections/SequencedHashMap.java,v
1.2 2002/02/10 08:07:42 jstrachan Exp $
  - * $Revision: 1.2 $
  - * $Date: 2002/02/10 08:07:42 $
  + * $Header: /home/cvs/jakarta-commons/collections/src/java/org/apache/commons/collections/SequencedHashMap.java,v
1.3 2002/02/18 20:34:57 morgand Exp $
  + * $Revision: 1.3 $
  + * $Date: 2002/02/18 20:34:57 $
    *
    * ====================================================================
    *
  @@ -58,262 +58,831 @@
    * <http://www.apache.org/>.
    *
    */
  -
   package org.apache.commons.collections;
   
  -
   import java.util.Collection;
  +import java.util.Collections;
   import java.util.HashMap;
   import java.util.Iterator;
  -import java.util.LinkedList;
  +import java.util.AbstractCollection;
  +import java.util.AbstractMap;
  +import java.util.AbstractSet;
  +import java.util.ArrayList;
   import java.util.List;
   import java.util.Map;
   import java.util.Set;
  +import java.util.NoSuchElementException;
   
   /**
  - * <p>A {@link java.util.HashMap} whose keys are sequenced.  The
  - * sequencing of the keys allow easy access to the values in the order
  - * which they were added in.  This class is thread safe.</p>
  - *
  - * <p>Implementing the List interface is not possible due to a instance
  - * method name clash between the Collection and the List interface:
  - *
  - * <table>
  - * <tr><td>Collections</td><td>boolean remove(Object o)</td></tr>
  - * <tr><td>Lists</td><td>Object remove(Object o)</td></tr>
  - * </table>
  - * </p>
  - *
  - * <p>So one cannot implement both interfaces at the same, which is
  - * unfortunate because the List interface would be very nice in
  - * conjuction with <a
  - * href="http://jakarta.apache.org/velocity/">Velocity</a>.</p>
  - *
  - * <p>A slightly more complex implementation and interface could involve
  - * the use of a list of <code>Map.Entry</code> objects.</p>
  + *  A map of objects whose mapping entries are sequenced based on the order in
  + *  which they were added.  This data structure has fast <I>O(1)</I> search
  + *  time, deletion time, and insertion time.
  + *
  + *  This class inherits from {@link java.util.HashMap} purely for backwards
  + *  compatibility.  It should really be inheriting from {@link
  + *  java.util.AbstractMap}, or with a tiny extra bit of work, implement the
  + *  full map interface on its own. APIs should not rely on this class being an
  + *  actual {@link java.util.HashMap}, and instead should recognize it only as a
  + *  generic {@link java.util.Map} (unless, of course, you need the sequencing
  + *  functionality, but even in that case, this class should not be referred to
  + *  as a java.util.HashMap).
  + *
  + *  <P>Although this map is sequenced, it cannot implement {@link
  + *  java.util.List} because of incompatible interface definitions.  The remove
  + *  methods in List and Map have different return values (see: {@link
  + *  java.util.List#remove(Object)} and {@link java.util.Map#remove(Object)}).
  + *
  + *  <P>This class is not thread safe.  When a thread safe implementation is
  + *  required, use {@link Collections#synchronizedMap(Map)} as it is documented,
  + *  or use explicit synchronization controls.
    *
  + *  @author <a href="mailto:michael@iammichael.org">Michael A. Smith</A>
    * @author <a href="mailto:dlr@collab.net">Daniel Rall</a>
    * @author <a href="mailto:hps@intermeta.de">Henning P. Schmiedehausen</a>
    */
  -public class SequencedHashMap extends HashMap
  -{
  -    /**
  -     * The index of the eldest element in the collection.
  -     */
  -    protected static final int ELDEST_INDEX = 0;
  -
  -    /**
  -     * Indicator for an unknown index.
  -     */
  -    private static final int UNKNOWN_INDEX = -1;
  -
  -    /**
  -     * The sequence used to keep track of the hash keys.  Younger objects are
  -     * kept towards the end of the list.  Does not allow duplicates.
  -     */
  -    private LinkedList keySequence;
  -
  -    /**
  -     * Creates a new instance with default storage.
  -     */
  -    public SequencedHashMap ()
  -    {
  -        keySequence = new LinkedList();
  -    }
  -
  -    /**
  -     * Creates a new instance with the specified storage.
  -     *
  -     * @param size The storage to allocate up front.
  -     */
  -    public SequencedHashMap (int size)
  -    {
  -        super(size);
  -        keySequence = new LinkedList();
  -    }
  -
  -    /**
  -     * Clears all elements.
  -     */
  -    public void clear ()
  -    {
  -        super.clear();
  -        keySequence.clear();
  -    }
  -
  -    /**
  -     * Creates a shallow copy of this object, preserving the internal
  -     * structure by copying only references.  The keys, values, and
  -     * sequence are not <code>clone()</code>'d.
  -     *
  -     * @return A clone of this instance.
  -     */
  -    public Object clone ()
  -    {
  -        SequencedHashMap seqHash = (SequencedHashMap) super.clone();
  -        seqHash.keySequence = (LinkedList) keySequence.clone();
  -        return seqHash;
  -    }
  -
  -    /**
  -     * Returns the key at the specified index.
  -     */
  -    public Object get (int index)
  -    {
  -        return keySequence.get(index);
  -    }
  -
  -    /**
  -     * Returns the value at the specified index.
  -     */
  -    public Object getValue (int index)
  -    {
  -        return get(get(index));
  -    }
  +public class SequencedHashMap extends HashMap {
   
  -    /**
  -     * Returns the index of the specified key.
  -     */
  -    public int indexOf (Object key)
  -    {
  -        return keySequence.indexOf(key);
  -    }
  -
  -    /**
  -     * Returns a key iterator.
  -     */
  -    public Iterator iterator ()
  -    {
  -        return keySequence.iterator();
  -    }
  +  /**
  +   *  {@link java.util.Map.Entry} that doubles as a node in the linked list
  +   *  of sequenced mappings.  
  +   **/
  +  private static class Entry implements Map.Entry {
  +    // Note: This class cannot easily be made clonable.  While the actual
  +    // implementation of a clone would be simple, defining the semantics is
  +    // difficult.  If a shallow clone is implemented, then entry.next.prev !=
  +    // entry, which is unintuitive and probably breaks all sorts of assumptions
  +    // in code that uses this implementation.  If a deep clone is
  +    // implementated, then what happens when the linked list is cyclical (as is
  +    // the case with SequencedHashMap)?  It's impossible to know in the clone
  +    // when to stop cloning, and thus you end up in a recursive loop,
  +    // continuously cloning the "next" in the list.
  +
  +    private final Object key;
  +    private Object value;
  +    
  +    // package private to allow the SequencedHashMap to access and manipulate
  +    // them.
  +    Entry next = null;
  +    Entry prev = null;
  +
  +    public Entry(Object key, Object value) {
  +      this.key = key;
  +      this.value = value;
  +    }
  +
  +    // per Map.Entry.getKey()
  +    public Object getKey() { 
  +      return this.key; 
  +    }
  +
  +    // per Map.Entry.getValue()
  +    public Object getValue() { 
  +      return this.value; 
  +    }
  +
  +    // per Map.Entry.setValue()
  +    public Object setValue(Object value) { 
  +      Object oldValue = this.value;
  +      this.value = value; 
  +      return oldValue;
  +    }
  +
  +    public int hashCode() { 
  +      // implemented per api docs for Map.Entry.hashCode()
  +      return ((getKey() == null ? 0 : getKey().hashCode()) ^
  +              (getValue()==null ? 0 : getValue().hashCode())); 
  +    }
  +
  +    public boolean equals(Object obj) {
  +      if(obj == null) return false;
  +      if(obj == this) return true;
  +      if(!(obj instanceof Map.Entry)) return false;
  +
  +      Map.Entry other = (Map.Entry)obj;
  +
  +      // implemented per api docs for Map.Entry.equals(Object) 
  +      return((getKey() == null ?
  +              other.getKey() == null : 
  +              getKey().equals(other.getKey()))  &&
  +             (getValue() == null ?
  +              other.getValue() == null : 
  +              getValue().equals(other.getValue())));
  +    }
  +    public String toString() {
  +      return "[" + getKey() + "=" + getValue() + "]";
  +    }
  +  }
  +
  +  /**
  +   *  Construct an empty sentinel used to hold the head (sentinel.next) and the
  +   *  tail (sentinel.prev) of the list.  The sentinal has a <code>null</code>
  +   *  key and value.
  +   **/
  +  private static final Entry createSentinel() {
  +    Entry s = new Entry(null, null);
  +    s.prev = s;
  +    s.next = s;
  +    return s;
  +  }
  +
  +  /**
  +   *  Sentinel used to hold the head and tail of the list of entries.
  +   **/
  +  private Entry sentinel;
  +
  +  /**
  +   *  Map of keys to entries
  +   **/
  +  private HashMap entries;
  +
  +  /**
  +   *  Construct a new sequenced hash map with default initial size and load
  +   *  factor.
  +   **/
  +  public SequencedHashMap() {
  +    sentinel = createSentinel();
  +    entries = new HashMap();
  +  }
  +
  +  /**
  +   *  Construct a new sequenced hash map with the specified initial size and
  +   *  default load factor.
  +   *
  +   *  @param initialSize the initial size for the hash table 
  +   *
  +   *  @see HashMap#HashMap(int)
  +   **/
  +  public SequencedHashMap(int initialSize) {
  +    sentinel = createSentinel();
  +    entries = new HashMap(initialSize);
  +  }
  +
  +  /**
  +   *  Construct a new sequenced hash map with the specified initial size and
  +   *  load factor.
  +   *
  +   *  @param initialSize the initial size for the hash table 
  +   *
  +   *  @param loadFactor the load factor for the hash table.
  +   *
  +   *  @see HashMap#HashMap(int,float)
  +   **/
  +  public SequencedHashMap(int initialSize, float loadFactor) {
  +    sentinel = createSentinel();
  +    entries = new HashMap(initialSize, loadFactor);
  +  }
  +
  +  /**
  +   *  Construct a new sequenced hash map and add all the elements in the
  +   *  specified map.  The order in which the mappings in the specified map are
  +   *  added is defined by {@link #putAll(Map)}.  
  +   **/
  +  public SequencedHashMap(Map m) {
  +    this();
  +    putAll(m);
  +  }
  +
  +  /**
  +   *  Removes an internal entry from the linked list.  This does not remove
  +   *  it from the underlying map.
  +   **/
  +  private void removeEntry(Entry entry) {
  +    entry.next.prev = entry.prev;
  +    entry.prev.next = entry.next;    
  +  }
  +
  +  /**
  +   *  Inserts a new internal entry to the tail of the linked list.  This does
  +   *  not add the entry to the underlying map.
  +   **/
  +  private void insertEntry(Entry entry) {
  +    entry.next = sentinel;
  +    entry.prev = sentinel.prev;
  +    sentinel.prev.next = entry;
  +    sentinel.prev = entry;
  +  }
  +
  +  // per Map.size()
  +  public int size() {
  +    // use the underlying Map's size since size is not maintained here.
  +    return entries.size();
  +  }
  +
  +  // per Map.isEmpty()
  +  public boolean isEmpty() {
  +    // for quick check whether the map is entry, we can check the linked list
  +    // and see if there's anything in it.
  +    return sentinel.next == sentinel;
  +  }
  +
  +  // per Map.containsKey(Object)
  +  public boolean containsKey(Object key) {
  +    // pass on to underlying map implementation
  +    return entries.containsKey(key);
  +  }
  +
  +  // per Map.containsValue(Object)
  +  public boolean containsValue(Object value) {
  +    // unfortunately, we cannot just pass this call to the underlying map
  +    // because we are mapping keys to entries, not keys to values.  The
  +    // underlying map doesn't have an efficient implementation anyway, so this
  +    // isn't a big deal.
  +
  +    // do null comparison outside loop so we only need to do it once.  This
  +    // provides a tighter, more efficient loop at the expense of slight
  +    // code duplication.
  +    if(value == null) {
  +      for(Entry pos = sentinel.next; pos != sentinel; pos = pos.next) {
  +        if(pos.getValue() == null) return true;
  +      } 
  +    } else {
  +      for(Entry pos = sentinel.next; pos != sentinel; pos = pos.next) {
  +        if(value.equals(pos.getValue())) return true;
  +      }
  +    }
  +    return false;      
  +  }
  +
  +  // per Map.get(Object)
  +  public Object get(Object o) {
  +    // find entry for the specified key object
  +    Entry entry = (Entry)entries.get(o);
  +    if(entry == null) return null;
  +      
  +    return entry.getValue();
  +  }
  +
  +  /**
  +   *  Return the entry for the "oldest" mapping.  That is, return the Map.Entry
  +   *  for the key-value pair that was first put into the map when compared to
  +   *  all the other pairings in the map.  This behavior is equivalent to using
  +   *  <code>entrySet().iterator().next()</code>, but this method provides an
  +   *  optimized implementation.
  +   *
  +   *  @return The first entry in the sequence, or <code>null</code> if the
  +   *  map is empty.
  +   **/
  +  public Map.Entry getFirst() {
  +    // sentinel.next points to the "first" element of the sequence -- the head
  +    // of the list, which is exactly the entry we need to return.  We must test
  +    // for an empty list though because we don't want to return the sentinel!
  +    return (isEmpty()) ? null : sentinel.next;
  +  }
  +
  +  /**
  +   *  Return the key for the "oldest" mapping.  That is, return the key for the
  +   *  mapping that was first put into the map when compared to all the other
  +   *  objects in the map.  This behavior is equivalent to using
  +   *  <code>getFirst().getKey()</code>, but this method provides a slightly
  +   *  optimized implementation.
  +   *
  +   *  @return The first key in the sequence, or <code>null</code> if the
  +   *  map is empty.
  +   **/
  +  public Object getFirstKey() {
  +    // sentinel.next points to the "first" element of the sequence -- the head
  +    // of the list -- and the requisite key is returned from it.  An empty list
  +    // does not need to be tested.  In cases where the list is empty,
  +    // sentinel.next will point to the sentinel itself which has a null key,
  +    // which is exactly what we would want to return if the list is empty (a
  +    // nice convient way to avoid test for an empty list)
  +    return sentinel.next.getKey();
  +  }
  +
  +  /**
  +   *  Return the value for the "oldest" mapping.  That is, return the value for
  +   *  the mapping that was first put into the map when compared to all the
  +   *  other objects in the map.  This behavior is equivalent to using
  +   *  <code>getFirst().getValue()</code>, but this method provides a slightly
  +   *  optimized implementation.
  +   *
  +   *  @return The first value in the sequence, or <code>null</code> if the
  +   *  map is empty.
  +   **/
  +  public Object getFirstValue() {
  +    // sentinel.next points to the "first" element of the sequence -- the head
  +    // of the list -- and the requisite value is returned from it.  An empty
  +    // list does not need to be tested.  In cases where the list is empty,
  +    // sentinel.next will point to the sentinel itself which has a null value,
  +    // which is exactly what we would want to return if the list is empty (a
  +    // nice convient way to avoid test for an empty list)
  +    return sentinel.next.getValue();
  +  }
  +
  +  /**
  +   *  Return the entry for the "newest" mapping.  That is, return the Map.Entry
  +   *  for the key-value pair that was first put into the map when compared to
  +   *  all the other pairings in the map.  The behavior is equivalent to:
  +   *
  +   *  <pre>
  +   *    Object obj = null;
  +   *    Iterator iter = entrySet().iterator();
  +   *    while(iter.hasNext()) {
  +   *      obj = iter.next();
  +   *    }
  +   *    return (Map.Entry)obj;
  +   *  </pre>
  +   *
  +   *  However, the implementation of this method ensures an O(1) lookup of the
  +   *  last key rather than O(n).
  +   *
  +   *  @return The last entry in the sequence, or <code>null</code> if the map
  +   *  is empty.
  +   **/
  +  public Map.Entry getLast() {
  +    // sentinel.prev points to the "last" element of the sequence -- the tail
  +    // of the list, which is exactly the entry we need to return.  We must test
  +    // for an empty list though because we don't want to return the sentinel!
  +    return (isEmpty()) ? null : sentinel.prev;
  +  }
  +
  +  /**
  +   *  Return the key for the "newest" mapping.  That is, return the key for the
  +   *  mapping that was last put into the map when compared to all the other
  +   *  objects in the map.  This behavior is equivalent to using
  +   *  <code>getLast().getKey()</code>, but this method provides a slightly
  +   *  optimized implementation.
  +   *
  +   *  @return The last key in the sequence, or <code>null</code> if the map
is
  +   *  empty.
  +   **/
  +  public Object getLastKey() {
  +    // sentinel.prev points to the "last" element of the sequence -- the tail
  +    // of the list -- and the requisite key is returned from it.  An empty list
  +    // does not need to be tested.  In cases where the list is empty,
  +    // sentinel.prev will point to the sentinel itself which has a null key,
  +    // which is exactly what we would want to return if the list is empty (a
  +    // nice convient way to avoid test for an empty list)
  +    return sentinel.prev.getKey();
  +  }
  +
  +  /**
  +   *  Return the value for the "newest" mapping.  That is, return the value for
  +   *  the mapping that was last put into the map when compared to all the other
  +   *  objects in the map.  This behavior is equivalent to using
  +   *  <code>getLast().getValue()</code>, but this method provides a slightly
  +   *  optimized implementation.
  +   *
  +   *  @return The last value in the sequence, or <code>null</code> if the map
  +   *  is empty.
  +   **/
  +  public Object getLastValue() {
  +    // sentinel.prev points to the "last" element of the sequence -- the tail
  +    // of the list -- and the requisite value is returned from it.  An empty
  +    // list does not need to be tested.  In cases where the list is empty,
  +    // sentinel.prev will point to the sentinel itself which has a null value,
  +    // which is exactly what we would want to return if the list is empty (a
  +    // nice convient way to avoid test for an empty list)
  +    return sentinel.prev.getValue();
  +  }
  +
  +  // per Map.put(Object,Object)
  +  public Object put(Object key, Object value) {
  +
  +    Object oldValue = null;
  +
  +    // lookup the entry for the specified key
  +    Entry e = (Entry)entries.get(key);
  +
  +    // check to see if it already exists
  +    if(e != null) {
  +      // remove from list so the entry gets "moved" to the end of list
  +      removeEntry(e);
  +
  +      // update value in map
  +      oldValue = e.setValue(value);
  +
  +      // Note: We do not update the key here because its unnecessary.  We only
  +      // do comparisons using equals(Object) and we know the specified key and
  +      // that in the map are equal in that sense.  This may cause a problem if
  +      // someone does not implement their hashCode() and/or equals(Object)
  +      // method properly and then use it as a key in this map.  
  +    } else {
  +      // add new entry
  +      e = new Entry(key, value);
  +      entries.put(key, e);
  +    }
  +    // assert(entry in map, but not list)
  +
  +    // add to list
  +    insertEntry(e);
  +
  +    return oldValue;
  +  }
  +
  +  // per Map.remove(Object)
  +  public Object remove(Object key) {
  +    Entry e = (Entry)entries.remove(key);
  +    if(e == null) return null;
  +    removeEntry(e);
  +    return e.getValue();
  +  }
  +
  +  /**
  +   *  Adds all the mappings in the specified map to this map, replacing any
  +   *  mappings that already exist (as per {@link Map#putAll(Map)}).  The order
  +   *  in which the entries are added is determined by the iterator returned
  +   *  from {@link Map#entrySet()} for the specified map.
  +   *
  +   *  @param t the mappings that should be added to this map.
  +   *
  +   *  @exception NullPointerException if <code>t</code> is <code>null</code>
  +   **/
  +  public void putAll(Map t) {
  +    Iterator iter = t.entrySet().iterator();
  +    while(iter.hasNext()) {
  +      Map.Entry entry = (Map.Entry)iter.next();
  +      put(entry.getKey(), entry.getValue());
  +    }
  +  }
  +
  +  // per Map.clear()
  +  public void clear() {
  +    // remove all from the underlying map
  +    entries.clear();
  +
  +    // and the list
  +    sentinel.next = sentinel;
  +    sentinel.prev = sentinel;
  +  }
  +
  +  // per Map.keySet()
  +  public Set keySet() {
  +    return new AbstractSet() {
  +
  +      // required impls
  +      public Iterator iterator() { return new OrderedIterator(KEY); }
  +      public boolean remove(Object o) {
  +        return SequencedHashMap.this.remove(o) != null;
  +      }
  +
  +      // more efficient impls than abstract set
  +      public void clear() { 
  +        SequencedHashMap.this.clear(); 
  +      }
  +      public int size() { 
  +        return SequencedHashMap.this.size(); 
  +      }
  +      public boolean isEmpty() { 
  +        return SequencedHashMap.this.isEmpty(); 
  +      }
  +      public boolean contains(Object o) { 
  +        return SequencedHashMap.this.containsKey(o);
  +      }
  +
  +    };
  +  }
  +
  +  // per Map.values()
  +  public Collection values() {
  +    return new AbstractCollection() {
  +      // required impl
  +      public Iterator iterator() { return new OrderedIterator(VALUE); }
  +      public boolean remove(Object value) {
  +        // do null comparison outside loop so we only need to do it once.  This
  +        // provides a tighter, more efficient loop at the expense of slight
  +        // code duplication.
  +        if(value == null) {
  +          for(Entry pos = sentinel.next; pos != sentinel; pos = pos.next) {
  +            if(pos.getValue() == null) {
  +              SequencedHashMap.this.remove(pos.getKey());
  +              return true;
  +            }
  +          } 
  +        } else {
  +          for(Entry pos = sentinel.next; pos != sentinel; pos = pos.next) {
  +            if(value.equals(pos.getValue())) {
  +              SequencedHashMap.this.remove(pos.getKey());
  +              return true;
  +            }
  +          }
  +        }
   
  -    /**
  -     * Returns the last index of the specified key.
  -     */
  -    public int lastIndexOf (Object key)
  -    {
  -        return keySequence.lastIndexOf(key);
  -    }
  +        return false;
  +      }
   
  -    /**
  -     * Returns the ordered sequence of keys.
  -     *
  -     * This method is meant to be used for retrieval of Key / Value pairs
  -     * in e.g. Velocity:
  -     * <PRE>
  -     * ## $table contains a sequenced hashtable
  -     * #foreach ($key in $table.sequence())
  -     * &lt;TR&gt;
  -     * &lt;TD&gt;Key: $key&lt;/TD&gt;
  -     * &lt;/TD&gt;Value: $table.get($key)&lt;/TD&gt;
  -     * &lt;/TR&gt;
  -     * #end
  -     * </PRE>
  -     *
  -     * @return The ordered list of keys.
  -     */
  -    public List sequence()
  -    {
  -        return keySequence;
  +      // more efficient impls than abstract collection
  +      public void clear() { 
  +        SequencedHashMap.this.clear(); 
  +      }
  +      public int size() { 
  +        return SequencedHashMap.this.size(); 
  +      }
  +      public boolean isEmpty() { 
  +        return SequencedHashMap.this.isEmpty(); 
  +      }
  +      public boolean contains(Object o) {
  +        return SequencedHashMap.this.containsValue(o);
  +      }
  +    };
  +  }
  +
  +  // per Map.entrySet()
  +  public Set entrySet() {
  +    return new AbstractSet() {
  +      // helper
  +      private Entry findEntry(Object o) {
  +        if(o == null) return null;
  +        if(!(o instanceof Map.Entry)) return null;
  +        
  +        Map.Entry e = (Map.Entry)o;
  +        Entry entry = (Entry)entries.get(e.getKey());
  +        if(entry.equals(e)) return entry;
  +        else return null;
  +      }
  +
  +      // required impl
  +      public Iterator iterator() { 
  +        return new OrderedIterator(ENTRY); 
  +      }
  +      public boolean remove(Object o) {
  +        Entry e = findEntry(o);
  +        if(e == null) return false;
  +
  +        return SequencedHashMap.this.remove(e.getKey()) != null;
  +      }        
  +
  +      // more efficient impls than abstract collection
  +      public void clear() { 
  +        SequencedHashMap.this.clear(); 
  +      }
  +      public int size() { 
  +        return SequencedHashMap.this.size(); 
  +      }
  +      public boolean isEmpty() { 
  +        return SequencedHashMap.this.isEmpty(); 
  +      }
  +      public boolean contains(Object o) {
  +        return findEntry(o) != null;
  +      }
  +    };
  +  }
  +
  +  // constants to define what the iterator should return on "next"
  +  private static final int KEY = 0;
  +  private static final int VALUE = 1;
  +  private static final int ENTRY = 2;
  +  private static final int REMOVED_MASK = 0x80000000;
  +
  +  private class OrderedIterator implements Iterator {
  +    /** 
  +     *  Holds the type that should be returned from the iterator.  The value
  +     *  should be either {@link #KEY}, {@link #VALUE}, or {@link #ENTRY}.  To
  +     *  save a tiny bit of memory, this field is also used as a marker for when
  +     *  remove has been called on the current object to prevent a second remove
  +     *  on the same element.  Essientially, if this value is negative (i.e. the
  +     *  bit specified by {@link #REMOVED_MASK} is set), the current position
  +     *  has been removed.  If positive, remove can still be called.
  +     **/
  +    private int returnType;
  +
  +    /**
  +     *  Holds the "current" position in the iterator.  when pos.next is the
  +     *  sentinel, we've reached the end of the list.
  +     **/
  +    private Entry pos = sentinel;
  +    
  +    /**
  +     *  Construct an iterator over the sequenced elements in the order in which
  +     *  they were added.  The {@link #next()} method returns the type specified
  +     *  by <code>returnType</code> which must be either {@link #KEY}, {@link
  +     *  #VALUE}, or {@link #ENTRY}.
  +     **/
  +    public OrderedIterator(int returnType) {
  +      //// Since this is a private inner class, nothing else should have
  +      //// access to the constructor.  Since we know the rest of the outer
  +      //// class uses the iterator correctly, we can leave of the following
  +      //// check:
  +      //if(returnType >= 0 && returnType <= 2) {
  +      //  throw new IllegalArgumentException("Invalid iterator type");
  +      //}
  +
  +      // Set the "removed" bit so that the iterator starts in a state where
  +      // "next" must be called before "remove" will succeed.
  +      this.returnType = returnType | REMOVED_MASK;
       }
   
       /**
  -     * Stores the provided key/value pair.  Freshens the sequence of existing
  -     * elements.
  +     *  Returns whether there is any additional elements in the iterator to be
  +     *  returned.
        *
  -     * @param key   The key to the provided value.
  -     * @param value The value to store.
  -     * @return      The previous value for the specified key, or
  -     *              <code>null</code> if none.
  -     */
  -    public Object put (Object key, Object value)
  -    {
  -        Object prevValue = super.put(key, value);
  -        freshenSequence(key, prevValue);
  -        return prevValue;
  +     *  @return <code>true</code> if there are more elements left to be
  +     *  returned from the iterator; <code>false</code> otherwise.
  +     **/
  +    public boolean hasNext() {
  +      return pos.next != sentinel;
       }
   
       /**
  -     * Freshens the sequence of the element <code>value</code> if
  -     * <code>value</code> is not <code>null</code>.
  +     *  Returns the next element from the iterator.
        *
  -     * @param key   The key whose sequence to freshen.
  -     * @param value The value whose existance to check before removing the old
  -     *              key sequence.
  -     */
  -    protected void freshenSequence(Object key, Object value)
  -    {
  -        if (value != null)
  -        {
  -            // Freshening existing element's sequence.
  -            keySequence.remove(key);
  -        }
  -        keySequence.add(key);
  -    }
  -
  -    /**
  -     * Stores the provided key/value pairs.
  +     *  @return the next element from the iterator.
        *
  -     * @param t The key/value pairs to store.
  -     */
  -    public void putAll (Map t)
  -    {
  -        Set set = t.entrySet();
  -        for (Iterator iter = set.iterator(); iter.hasNext(); )
  -        {
  -            Map.Entry e = (Map.Entry)iter.next();
  -            put(e.getKey(), e.getValue());
  -        }
  -    }
  +     *  @exception NoSuchElementException if there are no more elements in the
  +     *  iterator.
  +     **/
  +    public Object next() {
  +      if(pos.next == sentinel) {
  +        throw new NoSuchElementException();
  +      }
  +
  +      // clear the "removed" flag
  +      returnType = returnType & ~REMOVED_MASK;
  +
  +      pos = pos.next;
  +      switch(returnType) {
  +      case KEY:
  +        return pos.getKey();
  +      case VALUE:
  +        return pos.getValue();
  +      case ENTRY:
  +        return pos;
  +      default:
  +        // should never happen
  +        throw new Error("bad iterator type: " + returnType);
  +      }
   
  -    /**
  -     * Removes the element at the specified index.
  -     *
  -     * @param index The index of the object to remove.
  -     * @return      The previous value coressponding the <code>key</code>,
or
  -     *              <code>null</code> if none existed.
  -     */
  -    public Object remove (int index)
  -    {
  -        return remove(index, null);
       }
  -
  +    
       /**
  -     * Removes the element with the specified key.
  +     *  Removes the last element returned from the {@link #next()} method from
  +     *  the sequenced map.
        *
  -     * @param key   The <code>Map</code> key of the object to remove.
  -     * @return      The previous value coressponding the <code>key</code>,
or
  -     *              <code>null</code> if none existed.
  -     */
  -    public Object remove (Object key)
  -    {
  -        return remove(UNKNOWN_INDEX, key);
  -    }
  +     *  @exception IllegalStateException if there isn't a "last element" to be
  +     *  removed.  That is, if {@link #next()} has never been called, or if
  +     *  {@link #remove()} was already called on the element.
  +     **/
  +    public void remove() {
  +      if((returnType & REMOVED_MASK) != 0) {
  +        throw new IllegalStateException("remove() must follow next()");
  +      }
  +
  +      // remove the entry
  +      SequencedHashMap.this.remove(pos.getKey());
  +
  +      // set the removed flag
  +      returnType = returnType | REMOVED_MASK;
  +    }
  +  }
  +
  +  // APIs maintained from previous version of SequencedHashMap for backwards
  +  // compatibility
  +
  +  /**
  +   * Creates a shallow copy of this object, preserving the internal structure
  +   * by copying only references.  The keys and values themselves are not
  +   * <code>clone()</code>'d.  The cloned object maintains the same sequence.
  +   *
  +   * @return A clone of this instance.  
  +   */
  +  public Object clone () {
  +    // yes, calling super.clone() silly since we're just blowing away all
  +    // the stuff that super might be doing anyway, but for motivations on
  +    // this, see:
  +    // http://www.javaworld.com/javaworld/jw-01-1999/jw-01-object.html
  +    SequencedHashMap map = (SequencedHashMap)super.clone();
  +
  +    // create new, empty sentinel
  +    map.sentinel = createSentinel();
  +
  +    // create a new, empty entry map
  +    // note: this does not preserve the initial capacity and load factor.
  +    map.entries = new HashMap();
  +      
  +    // add all the mappings
  +    map.putAll(this);
  +
  +    // Note: We cannot just clone the hashmap and sentinel because we must
  +    // duplicate our internal structures.  Cloning those two will not clone all
  +    // the other entries they reference, and so the cloned hash map will not be
  +    // able to maintain internal consistency because there are two objects with
  +    // the same entries.  See discussion in the Entry implementation on why we
  +    // cannot implement a clone of the Entry (and thus why we need to recreate
  +    // everything).
  +
  +    return map;
  +  }
  +
  +  /**
  +   *  Returns the Map.Entry at the specified index
  +   *
  +   *  @exception ArrayIndexOutOfBoundsException if the specified index is
  +   *  <code>&lt; 0</code> or <code>&gt;</code> the size
of the map.
  +   **/
  +  private Map.Entry getEntry(int index) {
  +    Entry pos = sentinel;
  +
  +    if(index < 0) {
  +      throw new ArrayIndexOutOfBoundsException(index + " < 0");
  +    }
  +
  +    // loop to one before the position
  +    int i = -1;
  +    while(i < (index-1) && pos.next != sentinel) {
  +      i++;
  +      pos = pos.next;
  +    }
  +    // pos.next is the requested position
  +    
  +    // if sentinel is next, past end of list
  +    if(pos.next == sentinel) {
  +      throw new ArrayIndexOutOfBoundsException(index + " >= " + (i + 1));
  +    }
  +
  +    return pos.next;
  +  }
  +
  +  /**
  +   * Returns the key at the specified index.
  +   *
  +   *  @exception ArrayIndexOutOfBoundsException if the <code>index</code> is
  +   *  <code>&lt; 0</code> or <code>&gt;</code> the size
of the map.
  +   */
  +  public Object get (int index)
  +  {
  +    return getEntry(index).getKey();
  +  }
  +
  +  /**
  +   * Returns the value at the specified index.
  +   *
  +   *  @exception ArrayIndexOutOfBoundsException if the <code>index</code> is
  +   *  <code>&lt; 0</code> or <code>&gt;</code> the size
of the map.
  +   */
  +  public Object getValue (int index)
  +  {
  +    return getEntry(index).getValue();
  +  }
  +
  +  /**
  +   * Returns the index of the specified key.
  +   */
  +  public int indexOf (Object key)
  +  {
  +    Entry e = (Entry)entries.get(key);
  +    int pos = 0;
  +    while(e.prev != sentinel) {
  +      pos++;
  +      e = e.prev;
  +    }
  +    return pos;
  +  }
  +
  +  /**
  +   * Returns a key iterator.
  +   */
  +  public Iterator iterator ()
  +  {
  +    return keySet().iterator();
  +  }
  +
  +  /**
  +   * Returns the last index of the specified key.
  +   */
  +  public int lastIndexOf (Object key)
  +  {
  +    // keys in a map are guarunteed to be unique
  +    return indexOf(key);
  +  }
  +
  +  /**
  +   * Returns a List view of the keys rather than a set view.  The returned
  +   * list is unmodifiable.  This is required because changes to the values of
  +   * the list (using {@link java.util.ListIterator#set(Object)}) will
  +   * effectively remove the value from the list and reinsert that value at
  +   * the end of the list, which is an unexpected side effect of changing the
  +   * value of a list.  This occurs because changing the key, changes when the
  +   * mapping is added to the map and thus where it appears in the list.
  +   *
  +   * <P>An alternative to this method is to use {@link #keySet()}
  +   *
  +   * @see #keySet()
  +   * @return The ordered list of keys.  
  +   */
  +  public List sequence()
  +  {
  +    List l = new ArrayList(size());
  +    Iterator iter = keySet().iterator();
  +    while(iter.hasNext()) {
  +      l.add(iter.next());
  +    }
  +      
  +    return Collections.unmodifiableList(l);
  +  }
  +
  +  /**
  +   * Removes the element at the specified index.
  +   *
  +   * @param index The index of the object to remove.
  +   * @return      The previous value coressponding the <code>key</code>, or
  +   *              <code>null</code> if none existed.
  +   *
  +   * @exception ArrayIndexOutOfBoundsException if the <code>index</code> is
  +   * <code>&lt; 0</code> or <code>&gt;</code> the size
of the map.
  +   */
  +  public Object remove (int index)
  +  {
  +    return remove(get(index));
  +  }
   
  -    /**
  -     * Removes the element with the specified key or index.
  -     *
  -     * @param index The index of the object to remove, or
  -     *              <code>UNKNOWN_INDEX</code> if not known.
  -     * @param key   The <code>Map</code> key of the object to remove.
  -     * @return      The previous value coressponding the <code>key</code>,
or
  -     *              <code>null</code> if none existed.
  -     */
  -    private final Object remove (int index, Object key)
  -    {
  -        if (index == UNKNOWN_INDEX)
  -        {
  -            index = indexOf(key);
  -        }
  -        if (key == null)
  -        {
  -            key = get(index);
  -        }
  -        if (index != UNKNOWN_INDEX)
  -        {
  -            keySequence.remove(index);
  -        }
  -        return super.remove(key);
  -    }
   }
  -
  
  
  

--
To unsubscribe, e-mail:   <mailto:commons-dev-unsubscribe@jakarta.apache.org>
For additional commands, e-mail: <mailto:commons-dev-help@jakarta.apache.org>


Mime
View raw message