Return-Path: Delivered-To: apmail-jakarta-commons-dev-archive@apache.org Received: (qmail 46361 invoked from network); 13 Nov 2001 07:31:33 -0000 Received: from unknown (HELO nagoya.betaversion.org) (192.18.49.131) by daedalus.apache.org with SMTP; 13 Nov 2001 07:31:33 -0000 Received: (qmail 12952 invoked by uid 97); 13 Nov 2001 07:31:37 -0000 Delivered-To: qmlist-jakarta-archive-commons-dev@jakarta.apache.org Received: (qmail 12890 invoked by uid 97); 13 Nov 2001 07:31:35 -0000 Mailing-List: contact commons-dev-help@jakarta.apache.org; run by ezmlm Precedence: bulk List-Unsubscribe: List-Subscribe: List-Help: List-Post: List-Id: "Jakarta Commons Developers List" Reply-To: "Jakarta Commons Developers List" Delivered-To: mailing list commons-dev@jakarta.apache.org Received: (qmail 12877 invoked from network); 13 Nov 2001 07:31:35 -0000 From: "Michael Smith" To: "Jakarta Commons Developers List" Subject: [PATCH] RE: [Collections] Insertion Ordered Map Date: Tue, 13 Nov 2001 02:31:30 -0500 Message-ID: MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="----=_NextPart_000_0016_01C16BEB.4D5FDFE0" X-Priority: 3 (Normal) X-MSMail-Priority: Normal X-Mailer: Microsoft Outlook IMO, Build 9.0.2416 (9.0.2910.0) Importance: Normal In-Reply-To: X-MimeOLE: Produced By Microsoft MimeOLE V5.50.4133.2400 X-Spam-Rating: daedalus.apache.org 1.6.2 0/1000/N X-Spam-Rating: daedalus.apache.org 1.6.2 0/1000/N ------=_NextPart_000_0016_01C16BEB.4D5FDFE0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit > -----Original Message----- > From: dlr@despot.finemaltcoding.com > [mailto:dlr@despot.finemaltcoding.com]On Behalf Of Daniel Rall > > Some while ago there was discussion about HashMaps that maintained > > their insertion order (and what the name of such a thing should be). > > @see org.apache.commons.collections.SequencedHashMap Hmmm.... Sounds like a more reasonable name, but the implementation of Sequenced HashMap suffers from some of the the same problem that Lance's posted version did: Adding and removing from the list are both O(n) (although adding is O(1) when the key does not already exist, it's O(n) if it does). A "Hash" map implies that insertions, lookups, and removals from the mapping are O(1) based on hashed lookups. Additionally, the sets and collections in SequencedHashMap returned by keySet(), values(), and entries() are not properly backed by the map. Removing an element from one of those sets/collections, will cause the SequencedHashMap to retain objects in its sequence which no longer appear in the map. That's a bug. Attached is a patch to the test case to test for such a condition. When running the test cases, I noticed that the SequencedHashMap tests are already failing due to keySet() not maintaining order of the keys when cloned. The implementation that I provided gives true hash map functionality, including O(1) insertions, lookups and removals, has iterators that are backed by the underlying map, and fixes the failing tests (both the old one and my new one). For your reference, I've reattached it to this message. Since there is a preexisting class, I've kept it backwards-compatible by adding implementations of all the existing methods. To simplify the commit of the rewriten SequencedHashMap, I have also attached a diff against the current CVS version. regards, michael Attachment summary: tests.patch - patch against test case to ensure consistency when removing an element using an iterator on the keySet() test-results.pre - results of the test cases after adding the new test case and before any changes to SequencedHashMap sequencedhashmap.patch - diff for the new version of SequencedHashMap.java SequencedHashMap.java - new version of SequencedHashMap that maintains O(1) insertion, removal, lookup. It also has keySet(), values(), and entrySet() that are backed by the map correctly. test-results.post - results of the test cases after changing SequencedHashMap ------=_NextPart_000_0016_01C16BEB.4D5FDFE0 Content-Type: application/octet-stream; name="tests.patch" Content-Transfer-Encoding: quoted-printable Content-Disposition: attachment; filename="tests.patch" diff -u -r1.1 TestSequencedHashMap.java --- src/test/org/apache/commons/collections/TestSequencedHashMap.java = 2001/09/ 17 16:43:49 1.1 +++ src/test/org/apache/commons/collections/TestSequencedHashMap.java = 2001/11/ 13 05:29:40 @@ -107,6 +107,42 @@ return new Object[] { "bar", "frob", new Object() }; } + public void testKeySetIteratorRemove() { + Object[] keys =3D getKeys(); + Object[] values =3D getValues(); + for(int i =3D 0; i < keys.length; i++) { + labRat.put(keys[i], values[i]); + } + + for(int i =3D keys.length - 1; i >=3D 0; i--) { + // go to last key in the key set view of the map + Iterator iter =3D labRat.keySet().iterator(); + while(iter.hasNext()) { + iter.next(); + } + + // and remove it + iter.remove(); + + assertEquals("size() does not match expected size after " + + "remove using key set iterator", + i, labRat.size()); + + // make sure that iterator() has the correct number of = entries in + // it as well. + int count =3D 0; + iter =3D labRat.iterator(); + while(iter.hasNext()) { + iter.next(); + count++; + } + + assertEquals("iterator() does not have the same number of " = + + "values as the map", + labRat.size(), count); + } + } + public void testSequenceMap() throws Throwable { Object[] keys =3D getKeys(); int expectedSize =3D keys.length; ------=_NextPart_000_0016_01C16BEB.4D5FDFE0 Content-Type: application/octet-stream; name="test-results.pre" Content-Transfer-Encoding: quoted-printable Content-Disposition: attachment; filename="test-results.pre" Buildfile: build.xml init: build-java: build-test: test: [java] ......................................... [java] ......................................... [java] ......................................... [java] ......................................... [java] ......................................... [java] ......................................... [java] ......................................... [java] ........F........F......................... [java] ........F.F................................ [java] ............. [java] Time: 1.392 [java] There were 4 failures: [java] 1) = testIterator(org.apache.commons.collections.TestHashBag)junit.framework.A= ssertionFailedError: First should be 'A' expected: but was: [java] at = org.apache.commons.collections.TestBag.testIterator(Unknown Source) [java] at sun.reflect.NativeMethodAccessorImpl.invoke0(Native = Method) [java] at = sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java= :42) [java] at = sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorI= mpl.java:28) [java] 2) = testIteratorFail(org.apache.commons.collections.TestHashBag)junit.framewo= rk.AssertionFailedError: First should be 'A' expected: but was: [java] at = org.apache.commons.collections.TestBag.testIteratorFail(Unknown Source) [java] at sun.reflect.NativeMethodAccessorImpl.invoke0(Native = Method) [java] at = sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java= :42) [java] at = sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorI= mpl.java:28) [java] 3) = testKeySetIteratorRemove(org.apache.commons.collections.TestSequencedHash= Map)junit.framework.AssertionFailedError: iterator() does not have the = same number of values as the map expected:<2> but was:<3> [java] at = org.apache.commons.collections.TestSequencedHashMap.testKeySetIteratorRem= ove(Unknown Source) [java] at sun.reflect.NativeMethodAccessorImpl.invoke0(Native = Method) [java] at = sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java= :42) [java] at = sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorI= mpl.java:28) [java] 4) = testSequenceMap(org.apache.commons.collections.TestSequencedHashMap)junit= .framework.AssertionFailedError: Cloned key does not match orginal = expected: but was: [java] at = org.apache.commons.collections.TestSequencedHashMap.testSequenceMap(Unkno= wn Source) [java] at sun.reflect.NativeMethodAccessorImpl.invoke0(Native = Method) [java] at = sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java= :42) [java] at = sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorI= mpl.java:28) [java]=20 [java] FAILURES!!! [java] Tests run: 382, Failures: 4, Errors: 0 [java]=20 Total time: 4 seconds ------=_NextPart_000_0016_01C16BEB.4D5FDFE0 Content-Type: application/octet-stream; name="sequencedhashmap.patch" Content-Transfer-Encoding: quoted-printable Content-Disposition: attachment; filename="sequencedhashmap.patch" Index: = D:/home/michael/dev/jakarta/jakarta-commons/collections/src/java/org/apac= he/commons/collections/SequencedHashMap.java =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D RCS file: = /home/cvspublic/jakarta-commons/collections/src/java/org/apache/commons/c= ollections/SequencedHashMap.java,v retrieving revision 1.1 diff -u -r1.1 SequencedHashMap.java --- = D:/home/michael/dev/jakarta/jakarta-commons/collections/src/java/org/apac= he/commons/collections/SequencedHashMap.java 2001/09/17 16:43:49 1.1 +++ = D:/home/michael/dev/jakarta/jakarta-commons/collections/src/java/org/apac= he/commons/collections/SequencedHashMap.java 2001/11/13 06:55:38 @@ -54,85 +54,363 @@ * . */ =20 +import java.util.Collections; import java.util.Collection; 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; =20 /** - *

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.

+ * A map of objects whose mapping entries are sequenced based on the = order in + * which they were added. This data structure has fast O(1) = search + * time, deletion time, and insertion time. * - *

Implementing the List interface is not possible due to a instance - * method name clash between the Collection and the List interface: + * 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 HashMap). * - * - * - * - *
Collectionsboolean remove(Object o)
ListsObject remove(Object o)
- *

+ *

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)}). * - *

+ *

This class is not thread safe. When a thread safe = implementation is + * required, wrap this class using {@link = Collections#synchronizedMap(Map)}, + * or use explicit synchronization controls. * - *

A slightly more complex implementation and interface could = involve - * the use of a list of Map.Entry objects.

- * + * @author Michael A. = Smith * @author Daniel Rall - * @author Henning P. = Schmiedehausen + * @author Henning P. = Schmiedehausen=20 */ public class SequencedHashMap extends HashMap { - /** - * The index of the eldest element in the collection. - */ - protected static final int ELDEST_INDEX =3D 0; =20 /** - * Indicator for an unknown index. - */ - private static final int UNKNOWN_INDEX =3D -1; + * {@link java.util.Map.Entry} that doubles as a node in the = linked list + * of sequenced mappings. + **/ + private static class Entry implements Map.Entry { + private final Object key_; + private Object value_; + =20 + Entry next =3D null; + Entry prev =3D null; + + public Entry(Object key, Object value) { + this.key_ =3D key; + this.value_ =3D value; + } =20 - /** - * 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; + public Object getKey() {=20 + return this.key_;=20 + } =20 - /** - * Creates a new instance with default storage. - */ - public SequencedHashMap () - { - keySequence =3D new LinkedList(); + public Object getValue() {=20 + return this.value_;=20 + } + + public Object setValue(Object value) {=20 + Object oldValue =3D this.value_; + this.value_ =3D value;=20 + return oldValue; + } + + public int hashCode() {=20 + // per Map.Entry.hashCode() api docs + return ((getKey() =3D=3D null ? 0 : getKey().hashCode()) ^ + (getValue()=3D=3Dnull ? 0 : = getValue().hashCode()));=20 + } + + public boolean equals(Object obj) { + if(obj =3D=3D null) return false; + if(obj =3D=3D this) return true; + Map.Entry other =3D (Map.Entry)obj; + + // per Map.Entry.equals(Object api docs) + return((getKey() =3D=3D null ? + other.getKey() =3D=3D null :=20 + getKey().equals(other.getKey())) && + (getValue() =3D=3D null ? + other.getValue() =3D=3D null :=20 + getValue().equals(other.getValue()))); + } + public String toString() { + return "[" + getKey() + "=3D" + getValue() + "]"; + } + } + + private static final Entry createSentinel() { + Entry s =3D new Entry(null, null); + s.prev =3D s; + s.next =3D s; + return s; + } + + private Entry sentinel; + private HashMap entries; + + public SequencedHashMap() { + sentinel =3D createSentinel(); + entries =3D new HashMap(); + } + + public SequencedHashMap(int initialSize) { + sentinel =3D createSentinel(); + entries =3D new HashMap(initialSize); + } + + public SequencedHashMap(int initialSize, float loadFactor) { + sentinel =3D createSentinel(); + entries =3D new HashMap(initialSize, loadFactor); + } + + public SequencedHashMap(Map m) { + this(); + putAll(m); } =20 /** - * Creates a new instance with the specified storage. - * - * @param size The storage to allocate up front. - */ - public SequencedHashMap (int size) - { - super(size); - keySequence =3D new LinkedList(); + * 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 =3D entry.prev; + entry.prev.next =3D entry.next; =20 } =20 /** - * Clears all elements. - */ - public void clear () - { - super.clear(); - keySequence.clear(); + * Inserts a new internal entry to the linked list. This does not = add the + * entry to the underlying map. + **/ + private void insertEntry(Entry entry) { + entry.next =3D sentinel; + entry.prev =3D sentinel.prev; + sentinel.prev.next =3D entry; + sentinel.prev =3D entry; + } + + public int size() { + return entries.size(); + } + + public boolean isEmpty() { + return entries.isEmpty(); + } + + public boolean containsKey(Object key) { + return entries.containsKey(key); + } + + public boolean containsValue(Object value) { + return entries.containsValue(value); + } + + public Object get(Object o) { + // find entry for the specified key + Entry entry =3D (Entry)entries.get(o); + if(entry =3D=3D null) return null; + =20 + return entry.getValue(); } =20 + public Object put(Object key, Object value) { + + Object oldValue =3D null; + + Entry e =3D (Entry)entries.get(key); + if(e !=3D null) { + // remove from list so the entry gets "moved" to the front = of list + removeEntry(e); + + // update value in map + oldValue =3D e.setValue(value); + } else { + // add new entry + e =3D new Entry(key, value); + entries.put(key, e); + } + // entry in map, but not list + + // add to list + insertEntry(e); + + return oldValue; + } + + public Object remove(Object key) { + Entry e =3D (Entry)entries.remove(key); + if(e =3D=3D null) return null; + removeEntry(e); + return e.getValue(); + } + + // use abstract map impl + //void putAll(Map t) + + public void clear() { + entries.clear(); + sentinel.next =3D sentinel; + sentinel.prev =3D sentinel; + } + + public Set keySet() { + return new AbstractSet() { + + // required impl + public Iterator iterator() { return new = OrderedIterator(KEY); } + public boolean remove(Object o) { + return SequencedHashMap.this.remove(o) !=3D null; + } + + // more efficient impls than abstract set + public void clear() {=20 + SequencedHashMap.this.clear();=20 + } + public int size() {=20 + return SequencedHashMap.this.size();=20 + } + public boolean isEmpty() {=20 + return SequencedHashMap.this.isEmpty();=20 + } + public boolean contains(Object o) {=20 + return SequencedHashMap.this.containsKey(o); + } + + }; + } + + public Collection values() { + return new AbstractCollection() { + // required impl + public Iterator iterator() { return new = OrderedIterator(VALUE); } + public boolean remove(Object o) { + for(Entry pos =3D sentinel.next; pos !=3D sentinel; pos = =3D pos.next) { + if((pos.getValue() =3D=3D null && o =3D=3D null) || + (pos.getValue() !=3D null && = pos.getValue().equals(o))) { + SequencedHashMap.this.remove(pos.getKey()); + return true; + } + } + return false; + } + + // more efficient impls than abstract collection + public void clear() {=20 + SequencedHashMap.this.clear();=20 + } + public int size() {=20 + return SequencedHashMap.this.size();=20 + } + public boolean isEmpty() {=20 + return SequencedHashMap.this.isEmpty();=20 + } + public boolean contains(Object o) { + return SequencedHashMap.this.containsValue(o); + } + }; + } + + public Set entrySet() { + return new AbstractSet() { + // helper + private Entry findEntry(Object o) { + if(o =3D=3D null) return null; + if(!(o instanceof Map.Entry)) return null; + =20 + Map.Entry e =3D (Map.Entry)o; + Entry entry =3D (Entry)entries.get(e.getKey()); + if(entry.equals(e)) return entry; + else return null; + } + + // required impl + public Iterator iterator() {=20 + return new OrderedIterator(ENTRY);=20 + } + public boolean remove(Object o) { + Entry e =3D findEntry(o); + if(e =3D=3D null) return false; + + return SequencedHashMap.this.remove(e.getKey()) !=3D = null; + } =20 + + // more efficient impls than abstract collection + public void clear() {=20 + SequencedHashMap.this.clear();=20 + } + public int size() {=20 + return SequencedHashMap.this.size();=20 + } + public boolean isEmpty() {=20 + return SequencedHashMap.this.isEmpty();=20 + } + public boolean contains(Object o) { + return findEntry(o) !=3D null; + } + }; + } + + private static final int KEY =3D 0; + private static final int VALUE =3D 1; + private static final int ENTRY =3D 2; + + private class OrderedIterator implements Iterator { + + private int returnType; + private Entry pos =3D sentinel; + boolean removable =3D false; + =20 + public OrderedIterator(int returnType) { + this.returnType =3D returnType; + } + + public boolean hasNext() { + return pos.next !=3D sentinel; + } + + public Object next() { + if(pos.next =3D=3D sentinel) { + throw new NoSuchElementException(); + } + pos =3D pos.next; + removable =3D true; + switch(returnType) { + case KEY: + return pos.getKey(); + case VALUE: + return pos.getValue(); + case ENTRY: + return pos; + default: + throw new Error("bad iterator type"); + } + + } + =20 + public void remove() { + if(!removable) { + throw new IllegalStateException("remove() must follow = next()"); + } + =20 + SequencedHashMap.this.remove(pos.getKey()); + } + } + + // 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, values, and @@ -142,25 +420,70 @@ */ public Object clone () { - SequencedHashMap seqHash =3D (SequencedHashMap) super.clone(); - seqHash.keySequence =3D (LinkedList) keySequence.clone(); - return seqHash; + // 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 =3D (SequencedHashMap)super.clone(); + map.sentinel =3D createSentinel(); + + // note: this does not preserve the initial capacity and load = factor. + map.entries =3D new HashMap();=20 + =20 + map.putAll(this); + + return map; } =20 /** + * Returns the Map.Entry at the specified index + * + * @exception ArrayIndexOutOfBoundsException if the specified = index is + * < 0 or > the size of the map. + **/ + private Map.Entry getEntry(int index) { + Entry pos =3D sentinel; + + if(index < 0) { + throw new ArrayIndexOutOfBoundsException(index + " < 0"); + } + + // loop to one before the position + int i =3D -1; + while(i < index && pos.next !=3D sentinel) { + i++; + pos =3D pos.next; + } + // pos.next is the requested position + =20 + // if sentinel is next, past end of list + if(pos.next =3D=3D sentinel) { + throw new ArrayIndexOutOfBoundsException(index + " >=3D " + = (i + 1)); + } + + return pos.next; + } + + /** * Returns the key at the specified index. + * + * @exception ArrayIndexOutOfBoundsException if the = index is + * < 0 or > the size of the map. */ public Object get (int index) { - return keySequence.get(index); + return getEntry(index).getKey(); } =20 /** * Returns the value at the specified index. + * + * @exception ArrayIndexOutOfBoundsException if the = index is + * < 0 or > the size of the map. */ public Object getValue (int index) { - return get(get(index)); + return getEntry(index).getValue(); } =20 /** @@ -168,7 +491,13 @@ */ public int indexOf (Object key) { - return keySequence.indexOf(key); + Entry e =3D (Entry)entries.get(key); + int pos =3D 0; + while(e.prev !=3D sentinel) { + pos++; + e =3D e.prev; + } + return pos; } =20 /** @@ -176,7 +505,7 @@ */ public Iterator iterator () { - return keySequence.iterator(); + return keySet().iterator(); } =20 /** @@ -184,128 +513,48 @@ */ public int lastIndexOf (Object key) { - return keySequence.lastIndexOf(key); + // keys in a map are guarunteed to be unique + return indexOf(key); } =20 /** - * Returns the ordered sequence of keys. + * 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. * - * This method is meant to be used for retrieval of Key / Value = pairs - * in e.g. Velocity: - * 
-     * ## $table contains a sequenced hashtable
-     * #foreach ($key in $table.sequence())
-     * <TR>
-     * <TD>Key: $key</TD>
-     * </TD>Value: $table.get($key)</TD>
-     * </TR>
-     * #end
-     *
+ *

An alternative to this method is to use {@link #keySet()} * - * @return The ordered list of keys. + * @see #keySet() + * @return The ordered list of keys. =20 */ public List sequence() - { - return keySequence; - } - - /** - * Stores the provided key/value pair. Freshens the sequence of = existing - * elements. - * - * @param key The key to the provided value. - * @param value The value to store. - * @return The previous value for the specified key, or - * null if none. - */ - public Object put (Object key, Object value) - { - Object prevValue =3D super.put(key, value); - freshenSequence(key, prevValue); - return prevValue; - } - - /** - * Freshens the sequence of the element value if - * value is not null. - * - * @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 !=3D null) - { - // Freshening existing element's sequence. - keySequence.remove(key); + List l =3D new ArrayList(size()); + Iterator iter =3D keySet().iterator(); + while(iter.hasNext()) { + l.add(iter.next()); } - keySequence.add(key); + =20 + return Collections.unmodifiableList(l); } =20 /** - * Stores the provided key/value pairs. - * - * @param t The key/value pairs to store. - */ - public void putAll (Map t) - { - Set set =3D t.entrySet(); - for (Iterator iter =3D set.iterator(); iter.hasNext(); ) - { - Map.Entry e =3D (Map.Entry)iter.next(); - put(e.getKey(), e.getValue()); - } - } - - /** * Removes the element at the specified index. * * @param index The index of the object to remove. * @return The previous value coressponding the = key, or * null if none existed. - */ - public Object remove (int index) - { - return remove(index, null); - } - - /** - * Removes the element with the specified key. * - * @param key The Map key of the object to remove. - * @return The previous value coressponding the = key, or - * null if none existed. + * @exception ArrayIndexOutOfBoundsException if the = index is + * < 0 or > the size of the map. */ - public Object remove (Object key) + public Object remove (int index) { - return remove(UNKNOWN_INDEX, key); + return remove(get(index)); } =20 - /** - * Removes the element with the specified key or index. - * - * @param index The index of the object to remove, or - * UNKNOWN_INDEX if not known. - * @param key The Map key of the object to remove. - * @return The previous value coressponding the = key, or - * null if none existed. - */ - private final Object remove (int index, Object key) - { - if (index =3D=3D UNKNOWN_INDEX) - { - index =3D indexOf(key); - } - if (key =3D=3D null) - { - key =3D get(index); - } - if (index !=3D UNKNOWN_INDEX) - { - keySequence.remove(index); - } - return super.remove(key); - } } - ------=_NextPart_000_0016_01C16BEB.4D5FDFE0 Content-Type: application/octet-stream; name="SequencedHashMap.java" Content-Transfer-Encoding: quoted-printable Content-Disposition: attachment; filename="SequencedHashMap.java" package org.apache.commons.collections; /* = =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D * The Apache Software License, Version 1.1 * * Copyright (c) 2001 The Apache Software Foundation. All rights * reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in * the documentation and/or other materials provided with the * distribution. * * 3. The end-user documentation included with the redistribution, * if any, must include the following acknowledgment: * "This product includes software developed by the * Apache Software Foundation (http://www.apache.org/)." * Alternately, this acknowledgment may appear in the software = itself, * if and wherever such third-party acknowledgments normally appear. * * 4. The names "Apache" and "Apache Software Foundation" and * "Apache Turbine" must not be used to endorse or promote products * derived from this software without prior written permission. For * written permission, please contact apache@apache.org. * * 5. Products derived from this software may not be called "Apache", * "Apache Turbine", nor may "Apache" appear in their name, without * prior written permission of the Apache Software Foundation. * * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE * DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. * = =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D * * This software consists of voluntary contributions made by many * individuals on behalf of the Apache Software Foundation. For more * information on the Apache Software Foundation, please see * . */ import java.util.Collections; import java.util.Collection; import java.util.HashMap; import java.util.Iterator; 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; /** * A map of objects whose mapping entries are sequenced based on the = order in * which they were added. This data structure has fast O(1) = 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 HashMap). * *

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)}). * *

This class is not thread safe. When a thread safe implementation = is * required, wrap this class using {@link = Collections#synchronizedMap(Map)}, * or use explicit synchronization controls. * * @author Michael A. = Smith * @author Daniel Rall * @author Henning P. = Schmiedehausen=20 */ public class SequencedHashMap extends HashMap { /** * {@link java.util.Map.Entry} that doubles as a node in the linked = list * of sequenced mappings. **/ private static class Entry implements Map.Entry { private final Object key_; private Object value_; =20 Entry next =3D null; Entry prev =3D null; public Entry(Object key, Object value) { this.key_ =3D key; this.value_ =3D value; } public Object getKey() {=20 return this.key_;=20 } public Object getValue() {=20 return this.value_;=20 } public Object setValue(Object value) {=20 Object oldValue =3D this.value_; this.value_ =3D value;=20 return oldValue; } public int hashCode() {=20 // per Map.Entry.hashCode() api docs return ((getKey() =3D=3D null ? 0 : getKey().hashCode()) ^ (getValue()=3D=3Dnull ? 0 : getValue().hashCode())); = } public boolean equals(Object obj) { if(obj =3D=3D null) return false; if(obj =3D=3D this) return true; Map.Entry other =3D (Map.Entry)obj; // per Map.Entry.equals(Object api docs) return((getKey() =3D=3D null ? other.getKey() =3D=3D null :=20 getKey().equals(other.getKey())) && (getValue() =3D=3D null ? other.getValue() =3D=3D null :=20 getValue().equals(other.getValue()))); } public String toString() { return "[" + getKey() + "=3D" + getValue() + "]"; } } private static final Entry createSentinel() { Entry s =3D new Entry(null, null); s.prev =3D s; s.next =3D s; return s; } private Entry sentinel; private HashMap entries; public SequencedHashMap() { sentinel =3D createSentinel(); entries =3D new HashMap(); } public SequencedHashMap(int initialSize) { sentinel =3D createSentinel(); entries =3D new HashMap(initialSize); } public SequencedHashMap(int initialSize, float loadFactor) { sentinel =3D createSentinel(); entries =3D new HashMap(initialSize, loadFactor); } 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 =3D entry.prev; entry.prev.next =3D entry.next; =20 } /** * Inserts a new internal entry to the linked list. This does not = add the * entry to the underlying map. **/ private void insertEntry(Entry entry) { entry.next =3D sentinel; entry.prev =3D sentinel.prev; sentinel.prev.next =3D entry; sentinel.prev =3D entry; } public int size() { return entries.size(); } public boolean isEmpty() { return entries.isEmpty(); } public boolean containsKey(Object key) { return entries.containsKey(key); } public boolean containsValue(Object value) { return entries.containsValue(value); } public Object get(Object o) { // find entry for the specified key Entry entry =3D (Entry)entries.get(o); if(entry =3D=3D null) return null; =20 return entry.getValue(); } public Object put(Object key, Object value) { Object oldValue =3D null; Entry e =3D (Entry)entries.get(key); if(e !=3D null) { // remove from list so the entry gets "moved" to the front = of list removeEntry(e); // update value in map oldValue =3D e.setValue(value); } else { // add new entry e =3D new Entry(key, value); entries.put(key, e); } // entry in map, but not list // add to list insertEntry(e); return oldValue; } public Object remove(Object key) { Entry e =3D (Entry)entries.remove(key); if(e =3D=3D null) return null; removeEntry(e); return e.getValue(); } // use abstract map impl //void putAll(Map t) public void clear() { entries.clear(); sentinel.next =3D sentinel; sentinel.prev =3D sentinel; } public Set keySet() { return new AbstractSet() { // required impl public Iterator iterator() { return new = OrderedIterator(KEY); } public boolean remove(Object o) { return SequencedHashMap.this.remove(o) !=3D null; } // more efficient impls than abstract set public void clear() {=20 SequencedHashMap.this.clear();=20 } public int size() {=20 return SequencedHashMap.this.size();=20 } public boolean isEmpty() {=20 return SequencedHashMap.this.isEmpty();=20 } public boolean contains(Object o) {=20 return SequencedHashMap.this.containsKey(o); } }; } public Collection values() { return new AbstractCollection() { // required impl public Iterator iterator() { return new = OrderedIterator(VALUE); } public boolean remove(Object o) { for(Entry pos =3D sentinel.next; pos !=3D sentinel; pos = =3D pos.next) { if((pos.getValue() =3D=3D null && o =3D=3D null) || (pos.getValue() !=3D null && = pos.getValue().equals(o))) { SequencedHashMap.this.remove(pos.getKey()); return true; } } return false; } // more efficient impls than abstract collection public void clear() {=20 SequencedHashMap.this.clear();=20 } public int size() {=20 return SequencedHashMap.this.size();=20 } public boolean isEmpty() {=20 return SequencedHashMap.this.isEmpty();=20 } public boolean contains(Object o) { return SequencedHashMap.this.containsValue(o); } }; } public Set entrySet() { return new AbstractSet() { // helper private Entry findEntry(Object o) { if(o =3D=3D null) return null; if(!(o instanceof Map.Entry)) return null; =20 Map.Entry e =3D (Map.Entry)o; Entry entry =3D (Entry)entries.get(e.getKey()); if(entry.equals(e)) return entry; else return null; } // required impl public Iterator iterator() {=20 return new OrderedIterator(ENTRY);=20 } public boolean remove(Object o) { Entry e =3D findEntry(o); if(e =3D=3D null) return false; return SequencedHashMap.this.remove(e.getKey()) !=3D = null; } =20 // more efficient impls than abstract collection public void clear() {=20 SequencedHashMap.this.clear();=20 } public int size() {=20 return SequencedHashMap.this.size();=20 } public boolean isEmpty() {=20 return SequencedHashMap.this.isEmpty();=20 } public boolean contains(Object o) { return findEntry(o) !=3D null; } }; } private static final int KEY =3D 0; private static final int VALUE =3D 1; private static final int ENTRY =3D 2; private class OrderedIterator implements Iterator { private int returnType; private Entry pos =3D sentinel; boolean removable =3D false; =20 public OrderedIterator(int returnType) { this.returnType =3D returnType; } public boolean hasNext() { return pos.next !=3D sentinel; } public Object next() { if(pos.next =3D=3D sentinel) { throw new NoSuchElementException(); } pos =3D pos.next; removable =3D true; switch(returnType) { case KEY: return pos.getKey(); case VALUE: return pos.getValue(); case ENTRY: return pos; default: throw new Error("bad iterator type"); } } =20 public void remove() { if(!removable) { throw new IllegalStateException("remove() must follow = next()"); } =20 SequencedHashMap.this.remove(pos.getKey()); } } // 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, values, and * sequence are not clone()'d. * * @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 =3D (SequencedHashMap)super.clone(); map.sentinel =3D createSentinel(); // note: this does not preserve the initial capacity and load = factor. map.entries =3D new HashMap();=20 =20 map.putAll(this); return map; } /** * Returns the Map.Entry at the specified index * * @exception ArrayIndexOutOfBoundsException if the specified index = is * < 0 or > the size of the map. **/ private Map.Entry getEntry(int index) { Entry pos =3D sentinel; if(index < 0) { throw new ArrayIndexOutOfBoundsException(index + " < 0"); } // loop to one before the position int i =3D -1; while(i < index && pos.next !=3D sentinel) { i++; pos =3D pos.next; } // pos.next is the requested position =20 // if sentinel is next, past end of list if(pos.next =3D=3D sentinel) { throw new ArrayIndexOutOfBoundsException(index + " >=3D " + = (i + 1)); } return pos.next; } /** * Returns the key at the specified index. * * @exception ArrayIndexOutOfBoundsException if the = index is * < 0 or > 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 = index is * < 0 or > 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 =3D (Entry)entries.get(key); int pos =3D 0; while(e.prev !=3D sentinel) { pos++; e =3D 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. * *

An alternative to this method is to use {@link #keySet()} * * @see #keySet() * @return The ordered list of keys. =20 */ public List sequence() { List l =3D new ArrayList(size()); Iterator iter =3D keySet().iterator(); while(iter.hasNext()) { l.add(iter.next()); } =20 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 = key, or * null if none existed. * * @exception ArrayIndexOutOfBoundsException if the = index is * < 0 or > the size of the map. */ public Object remove (int index) { return remove(get(index)); } } ------=_NextPart_000_0016_01C16BEB.4D5FDFE0 Content-Type: application/octet-stream; name="test-results.post" Content-Transfer-Encoding: quoted-printable Content-Disposition: attachment; filename="test-results.post" Buildfile: build.xml init: build-java: build-test: test: [java] ......................................... [java] ......................................... [java] ......................................... [java] ......................................... [java] ......................................... [java] ......................................... [java] ......................................... [java] ........F........F......................... [java] ......................................... [java] ............. [java] Time: 1.432 [java] There were 2 failures: [java] 1) = testIterator(org.apache.commons.collections.TestHashBag)junit.framework.A= ssertionFailedError: First should be 'A' expected: but was: [java] at = org.apache.commons.collections.TestBag.testIterator(Unknown Source) [java] at sun.reflect.NativeMethodAccessorImpl.invoke0(Native = Method) [java] at = sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java= :42) [java] at = sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorI= mpl.java:28) [java] 2) = testIteratorFail(org.apache.commons.collections.TestHashBag)junit.framewo= rk.AssertionFailedError: First should be 'A' expected: but was: [java] at = org.apache.commons.collections.TestBag.testIteratorFail(Unknown Source) [java] at sun.reflect.NativeMethodAccessorImpl.invoke0(Native = Method) [java] at = sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java= :42) [java] at = sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorI= mpl.java:28) [java]=20 [java] FAILURES!!! [java] Tests run: 382, Failures: 2, Errors: 0 [java]=20 Total time: 4 seconds ------=_NextPart_000_0016_01C16BEB.4D5FDFE0 Content-Type: text/plain; charset=us-ascii -- To unsubscribe, e-mail: For additional commands, e-mail: ------=_NextPart_000_0016_01C16BEB.4D5FDFE0--

So one cannot implement both interfaces at the same, which is - * unfortunate because the List interface would be very nice in - * conjuction with Velocity.