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:[EMAIL PROTECTED]">Michael A. Smith</A> * @author <a href="mailto:[EMAIL PROTECTED]">Daniel Rall</a> * @author <a href="mailto:[EMAIL PROTECTED]">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()) - * <TR> - * <TD>Key: $key</TD> - * </TD>Value: $table.get($key)</TD> - * </TR> - * #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>< 0</code> or <code>></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>< 0</code> or <code>></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>< 0</code> or <code>></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>< 0</code> or <code>></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:[EMAIL PROTECTED]> For additional commands, e-mail: <mailto:[EMAIL PROTECTED]>