You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@commons.apache.org by sc...@apache.org on 2002/11/24 21:48:35 UTC
cvs commit: jakarta-commons/collections/src/java/org/apache/commons/collections SequencedHashMap.java
scolebourne 2002/11/24 12:48:35
Modified: collections/src/java/org/apache/commons/collections
SequencedHashMap.java
Log:
Fix bug in indexOf, identified by Johal
Reformat and Javadoc file
Revision Changes Path
1.15 +944 -923 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.14
retrieving revision 1.15
diff -u -r1.14 -r1.15
--- SequencedHashMap.java 12 Oct 2002 22:15:19 -0000 1.14
+++ SequencedHashMap.java 24 Nov 2002 20:48:35 -0000 1.15
@@ -77,7 +77,6 @@
import java.util.Set;
import java.util.NoSuchElementException;
import java.util.ConcurrentModificationException;
-
/**
* 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
@@ -92,944 +91,966 @@
* required, use {@link Collections#synchronizedMap(Map)} as it is documented,
* or use explicit synchronization controls.
*
- * @since 2.0
- * @author <a href="mailto:mas@apache.org">Michael A. Smith</A>
+ * @since 2.0
+ * @author <a href="mailto:mas@apache.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>
+ * @author Stephen Colebourne
*/
public class SequencedHashMap implements Map, Cloneable, Externalizable {
- /**
- * {@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()));
+ /**
+ * {@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() + "]";
+ }
}
- 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())));
+ /**
+ * 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;
}
- public String toString() {
- return "[" + getKey() + "=" + getValue() + "]";
+
+ /**
+ * Sentinel used to hold the head and tail of the list of entries.
+ **/
+ private Entry sentinel;
+
+ /**
+ * Map of keys to entries
+ **/
+ private HashMap entries;
+
+ /**
+ * Holds the number of modifications that have occurred to the map,
+ * excluding modifications made through a collection view's iterator
+ * (e.g. entrySet().iterator().remove()). This is used to create a
+ * fail-fast behavior with the iterators.
+ **/
+ private transient long modCount = 0;
+
+ /**
+ * 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()
+
+ /**
+ * Implements {@link Map#size()}.
+ */
+ public int size() {
+ // use the underlying Map's size since size is not maintained here.
+ return entries.size();
+ }
+
+ /**
+ * Implements {@link 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;
+ }
+
+ /**
+ * Implements {@link Map#containsKey(Object)}.
+ */
+ public boolean containsKey(Object key) {
+ // pass on to underlying map implementation
+ return entries.containsKey(key);
}
- }
- /**
- * 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;
-
- /**
- * Holds the number of modifications that have occurred to the map,
- * excluding modifications made through a collection view's iterator
- * (e.g. entrySet().iterator().remove()). This is used to create a
- * fail-fast behavior with the iterators.
- **/
- private transient long modCount = 0;
-
- /**
- * 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()
-
- /**
- * Implements {@link Map#size()}.
- */
- public int size() {
- // use the underlying Map's size since size is not maintained here.
- return entries.size();
- }
-
- /**
- * Implements {@link 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;
- }
-
- /**
- * Implements {@link Map#containsKey(Object)}.
- */
- public boolean containsKey(Object key) {
- // pass on to underlying map implementation
- return entries.containsKey(key);
- }
-
- /**
- * Implements {@link 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;
- }
-
- /**
- * Implements {@link 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();
- }
-
- /**
- * Implements {@link Map#put(Object, Object)}.
- */
- public Object put(Object key, Object value) {
- modCount++;
-
- 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;
- }
-
- /**
- * Implements {@link Map#remove(Object)}.
- */
- public Object remove(Object key) {
- Entry e = removeImpl(key);
- return (e == null) ? null : e.getValue();
- }
-
- /**
- * Fully remove an entry from the map, returning the old entry or null if
- * there was no such entry with the specified key.
- **/
- private Entry removeImpl(Object key) {
- Entry e = (Entry)entries.remove(key);
- if(e == null) return null;
- modCount++;
- removeEntry(e);
- return e;
- }
-
- /**
- * 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());
- }
- }
-
- /**
- * Implements {@link Map#clear()}.
- */
- public void clear() {
- modCount++;
-
- // remove all from the underlying map
- entries.clear();
-
- // and the list
- sentinel.next = sentinel;
- sentinel.prev = sentinel;
- }
-
- /**
- * Implements {@link Map#equals(Object)}.
- */
- public boolean equals(Object obj) {
- if(obj == null) return false;
- if(obj == this) return true;
-
- if(!(obj instanceof Map)) return false;
-
- return entrySet().equals(((Map)obj).entrySet());
- }
-
- /**
- * Implements {@link Map#hashCode()}.
- */
- public int hashCode() {
- return entrySet().hashCode();
- }
-
- /**
- * Provides a string representation of the entries within the map. The
- * format of the returned string may change with different releases, so this
- * method is suitable for debugging purposes only. If a specific format is
- * required, use {@link #entrySet()}.{@link Set#iterator() iterator()} and
- * iterate over the entries in the map formatting them as appropriate.
- **/
- public String toString() {
- StringBuffer buf = new StringBuffer();
- buf.append('[');
- for(Entry pos = sentinel.next; pos != sentinel; pos = pos.next) {
- buf.append(pos.getKey());
- buf.append('=');
- buf.append(pos.getValue());
- if(pos.next != sentinel) {
- buf.append(',');
- }
- }
- buf.append(']');
-
- return buf.toString();
- }
-
- /**
- * Implements {@link Map#keySet()}.
- */
- public Set keySet() {
- return new AbstractSet() {
-
- // required impls
- public Iterator iterator() { return new OrderedIterator(KEY); }
- public boolean remove(Object o) {
- Entry e = SequencedHashMap.this.removeImpl(o);
- return (e != 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);
- }
-
- };
- }
-
- /**
- * Implements {@link Map#values()}.
- */
- public Collection values() {
- return new AbstractCollection() {
- // required impl
- public Iterator iterator() { return new OrderedIterator(VALUE); }
- public boolean remove(Object value) {
+ /**
+ * Implements {@link 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) {
- SequencedHashMap.this.removeImpl(pos.getKey());
- return true;
+ 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())) {
- SequencedHashMap.this.removeImpl(pos.getKey());
- return true;
+ for (Entry pos = sentinel.next; pos != sentinel; pos = pos.next) {
+ if (value.equals(pos.getValue()))
+ return true;
}
- }
}
-
return false;
- }
+ }
+
+ /**
+ * Implements {@link 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();
+ }
+
+ /**
+ * Implements {@link Map#put(Object, Object)}.
+ */
+ public Object put(Object key, Object value) {
+ modCount++;
+
+ 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;
+ }
+
+ /**
+ * Implements {@link Map#remove(Object)}.
+ */
+ public Object remove(Object key) {
+ Entry e = removeImpl(key);
+ return (e == null) ? null : e.getValue();
+ }
- // 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);
- }
- };
- }
-
- /**
- * Implements {@link 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 != null && 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.removeImpl(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;
-
- /**
- * Holds the expected modification count. If the actual modification
- * count of the map differs from this value, then a concurrent
- * modification has occurred.
- **/
- private transient long expectedModCount = modCount;
-
- /**
- * 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;
- }
-
- /**
- * Returns whether there is any additional elements in the iterator to be
- * returned.
- *
- * @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;
- }
-
- /**
- * Returns the next element from the iterator.
- *
- * @return the next element from the iterator.
- *
- * @exception NoSuchElementException if there are no more elements in the
- * iterator.
- *
- * @exception ConcurrentModificationException if a modification occurs in
- * the underlying map.
- **/
- public Object next() {
- if(modCount != expectedModCount) {
- throw new ConcurrentModificationException();
- }
- 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:
+ /**
+ * Fully remove an entry from the map, returning the old entry or null if
+ * there was no such entry with the specified key.
+ **/
+ private Entry removeImpl(Object key) {
+ Entry e = (Entry) entries.remove(key);
+ if (e == null)
+ return null;
+ modCount++;
+ removeEntry(e);
+ return e;
+ }
+
+ /**
+ * 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.
+ *
+ * @throws 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());
+ }
+ }
+
+ /**
+ * Implements {@link Map#clear()}.
+ */
+ public void clear() {
+ modCount++;
+
+ // remove all from the underlying map
+ entries.clear();
+
+ // and the list
+ sentinel.next = sentinel;
+ sentinel.prev = sentinel;
+ }
+
+ /**
+ * Implements {@link Map#equals(Object)}.
+ */
+ public boolean equals(Object obj) {
+ if (obj == null)
+ return false;
+ if (obj == this)
+ return true;
+
+ if (!(obj instanceof Map))
+ return false;
+
+ return entrySet().equals(((Map) obj).entrySet());
+ }
+
+ /**
+ * Implements {@link Map#hashCode()}.
+ */
+ public int hashCode() {
+ return entrySet().hashCode();
+ }
+
+ /**
+ * Provides a string representation of the entries within the map. The
+ * format of the returned string may change with different releases, so this
+ * method is suitable for debugging purposes only. If a specific format is
+ * required, use {@link #entrySet()}.{@link Set#iterator() iterator()} and
+ * iterate over the entries in the map formatting them as appropriate.
+ **/
+ public String toString() {
+ StringBuffer buf = new StringBuffer();
+ buf.append('[');
+ for (Entry pos = sentinel.next; pos != sentinel; pos = pos.next) {
+ buf.append(pos.getKey());
+ buf.append('=');
+ buf.append(pos.getValue());
+ if (pos.next != sentinel) {
+ buf.append(',');
+ }
+ }
+ buf.append(']');
+
+ return buf.toString();
+ }
+
+ /**
+ * Implements {@link Map#keySet()}.
+ */
+ public Set keySet() {
+ return new AbstractSet() {
+
+ // required impls
+ public Iterator iterator() {
+ return new OrderedIterator(KEY);
+ }
+ public boolean remove(Object o) {
+ Entry e = SequencedHashMap.this.removeImpl(o);
+ return (e != 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);
+ }
+
+ };
+ }
+
+ /**
+ * Implements {@link 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.removeImpl(pos.getKey());
+ return true;
+ }
+ }
+ } else {
+ for (Entry pos = sentinel.next; pos != sentinel; pos = pos.next) {
+ if (value.equals(pos.getValue())) {
+ SequencedHashMap.this.removeImpl(pos.getKey());
+ return true;
+ }
+ }
+ }
+
+ return false;
+ }
+
+ // 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);
+ }
+ };
+ }
+
+ /**
+ * Implements {@link 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 != null && 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.removeImpl(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;
+
+ /**
+ * Holds the expected modification count. If the actual modification
+ * count of the map differs from this value, then a concurrent
+ * modification has occurred.
+ **/
+ private transient long expectedModCount = modCount;
+
+ /**
+ * 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;
+ }
+
+ /**
+ * Returns whether there is any additional elements in the iterator to be
+ * returned.
+ *
+ * @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;
+ }
+
+ /**
+ * Returns the next element from the iterator.
+ *
+ * @return the next element from the iterator.
+ *
+ * @throws NoSuchElementException if there are no more elements in the
+ * iterator.
+ *
+ * @throws ConcurrentModificationException if a modification occurs in
+ * the underlying map.
+ **/
+ public Object next() {
+ if (modCount != expectedModCount) {
+ throw new ConcurrentModificationException();
+ }
+ 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 last element returned from the {@link #next()} method from
+ * the sequenced map.
+ *
+ * @throws 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.
+ *
+ * @throws ConcurrentModificationException if a modification occurs in
+ * the underlying map.
+ **/
+ public void remove() {
+ if ((returnType & REMOVED_MASK) != 0) {
+ throw new IllegalStateException("remove() must follow next()");
+ }
+ if (modCount != expectedModCount) {
+ throw new ConcurrentModificationException();
+ }
+
+ SequencedHashMap.this.removeImpl(pos.getKey());
+
+ // update the expected mod count for the remove operation
+ expectedModCount++;
+
+ // 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.
+ *
+ * @throws CloneNotSupportedException if clone is not supported by a
+ * subclass.
+ */
+ public Object clone() throws CloneNotSupportedException {
+ // 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
+ *
+ * @throws 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;
+ }
+
+ /**
+ * Gets the key at the specified index.
+ *
+ * @param index the index to retrieve
+ * @return the key at the specified index, or null
+ * @throws 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();
+ }
+
+ /**
+ * Gets the value at the specified index.
+ *
+ * @param index the index to retrieve
+ * @return the value at the specified index, or null
+ * @throws 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();
+ }
+
+ /**
+ * Gets the index of the specified key.
+ *
+ * @param key the key to find the index of
+ * @return the index, or -1 if not found
+ */
+ public int indexOf(Object key) {
+ Entry e = (Entry) entries.get(key);
+ if (e == null) {
+ return -1;
+ }
+ int pos = 0;
+ while (e.prev != sentinel) {
+ pos++;
+ e = e.prev;
+ }
return pos;
- default:
- // should never happen
- throw new Error("bad iterator type: " + returnType);
- }
-
- }
-
- /**
- * Removes the last element returned from the {@link #next()} method from
- * the sequenced map.
- *
- * @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.
- *
- * @exception ConcurrentModificationException if a modification occurs in
- * the underlying map.
- **/
- public void remove() {
- if((returnType & REMOVED_MASK) != 0) {
- throw new IllegalStateException("remove() must follow next()");
- }
- if(modCount != expectedModCount) {
- throw new ConcurrentModificationException();
- }
-
- SequencedHashMap.this.removeImpl(pos.getKey());
-
- // update the expected mod count for the remove operation
- expectedModCount++;
-
- // 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.
- *
- * @exception CloneNotSupportedException if clone is not supported by a
- * subclass.
- */
- public Object clone () throws CloneNotSupportedException {
- // 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));
- }
-
- // per Externalizable.readExternal(ObjectInput)
-
- /**
- * Deserializes this map from the given stream.
- *
- * @param in the stream to deserialize from
- * @throws IOException if the stream raises it
- * @throws ClassNotFoundException if the stream raises it
- */
- public void readExternal( ObjectInput in )
- throws IOException, ClassNotFoundException
- {
- int size = in.readInt();
- for(int i = 0; i < size; i++) {
- Object key = in.readObject();
- Object value = in.readObject();
- put(key, value);
- }
- }
-
- /**
- * Serializes this map to the given stream.
- *
- * @param out the stream to serialize to
- * @throws IOException if the stream raises it
- */
- public void writeExternal( ObjectOutput out ) throws IOException {
- out.writeInt(size());
- for(Entry pos = sentinel.next; pos != sentinel; pos = pos.next) {
- out.writeObject(pos.getKey());
- out.writeObject(pos.getValue());
- }
- }
-
- // add a serial version uid, so that if we change things in the future
- // without changing the format, we can still deserialize properly.
- private static final long serialVersionUID = 3380552487888102930L;
+ }
+
+ /**
+ * Gets an iterator over the keys.
+ *
+ * @return an iterator over the keys
+ */
+ public Iterator iterator() {
+ return keySet().iterator();
+ }
+
+ /**
+ * Gets the last index of the specified key.
+ *
+ * @param key the key to find the index of
+ * @return the index, or -1 if not found
+ */
+ 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.
+ *
+ * @throws 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));
+ }
+
+ // per Externalizable.readExternal(ObjectInput)
+
+ /**
+ * Deserializes this map from the given stream.
+ *
+ * @param in the stream to deserialize from
+ * @throws IOException if the stream raises it
+ * @throws ClassNotFoundException if the stream raises it
+ */
+ public void readExternal(ObjectInput in) throws IOException, ClassNotFoundException {
+ int size = in.readInt();
+ for (int i = 0; i < size; i++) {
+ Object key = in.readObject();
+ Object value = in.readObject();
+ put(key, value);
+ }
+ }
+
+ /**
+ * Serializes this map to the given stream.
+ *
+ * @param out the stream to serialize to
+ * @throws IOException if the stream raises it
+ */
+ public void writeExternal(ObjectOutput out) throws IOException {
+ out.writeInt(size());
+ for (Entry pos = sentinel.next; pos != sentinel; pos = pos.next) {
+ out.writeObject(pos.getKey());
+ out.writeObject(pos.getValue());
+ }
+ }
+
+ // add a serial version uid, so that if we change things in the future
+ // without changing the format, we can still deserialize properly.
+ private static final long serialVersionUID = 3380552487888102930L;
}
--
To unsubscribe, e-mail: <ma...@jakarta.apache.org>
For additional commands, e-mail: <ma...@jakarta.apache.org>