scolebourne 2003/11/04 15:36:24
Modified: collections/src/java/org/apache/commons/collections/decorators
OrderedMap.java
collections/src/test/org/apache/commons/collections/decorators
TestOrderedMap.java
Log:
Complete OrderedMap with MapIterator
Ensure fully tested
Revision Changes Path
1.5 +161 -298
jakarta-commons/collections/src/java/org/apache/commons/collections/decorators/OrderedMap.java
Index: OrderedMap.java
===================================================================
RCS file:
/home/cvs/jakarta-commons/collections/src/java/org/apache/commons/collections/decorators/OrderedMap.java,v
retrieving revision 1.4
retrieving revision 1.5
diff -u -r1.4 -r1.5
--- OrderedMap.java 3 Oct 2003 23:19:32 -0000 1.4
+++ OrderedMap.java 4 Nov 2003 23:36:23 -0000 1.5
@@ -57,6 +57,8 @@
*/
package org.apache.commons.collections.decorators;
+import java.util.AbstractCollection;
+import java.util.AbstractSet;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;
@@ -64,21 +66,24 @@
import java.util.Map;
import java.util.Set;
-import org.apache.commons.collections.pairs.DefaultMapEntry;
+import org.apache.commons.collections.iterators.DefaultMapIterator;
+import org.apache.commons.collections.iterators.MapIterator;
+import org.apache.commons.collections.pairs.AbstractMapEntry;
/**
- * Decorates a <code>Map</code> to ensure that the order of addition
- * is retained and used by the values and keySet iterators.
+ * Decorates a <code>Map</code> to ensure that the order of addition is retained.
+ * <p>
+ * The order will be used via the iterators and toArray methods on the views.
+ * The order is also returned by the <code>MapIterator</code>.
* <p>
* If an object is added to the Map for a second time, it will remain in the
* original position in the iteration.
- * <p>
- * The order can be observed via the iterator or toArray methods.
*
* @since Commons Collections 3.0
* @version $Revision$ $Date$
*
* @author Henri Yandell
+ * @author Stephen Colebourne
*/
public class OrderedMap extends AbstractMapDecorator implements Map {
@@ -87,6 +92,8 @@
/**
* Factory method to create an ordered map.
+ * <p>
+ * An <code>ArrayList</code> is used to retain order.
*
* @param map the map to decorate, must not be null
* @throws IllegalArgumentException if map is null
@@ -103,22 +110,10 @@
*/
protected OrderedMap(Map map) {
super(map);
- insertOrder.addAll( getMap().keySet() );
+ insertOrder.addAll(getMap().keySet());
}
//-----------------------------------------------------------------------
- public void clear() {
- getMap().clear();
- insertOrder.clear();
- }
-
- public void putAll(Map m) {
- for (Iterator it = m.entrySet().iterator(); it.hasNext();) {
- Map.Entry entry = (Map.Entry) it.next();
- put(entry.getKey(), entry.getValue());
- }
- }
-
public Object put(Object key, Object value) {
if (getMap().containsKey(key)) {
// re-adding doesn't change order
@@ -131,268 +126,151 @@
}
}
+ public void putAll(Map map) {
+ for (Iterator it = map.entrySet().iterator(); it.hasNext();) {
+ Map.Entry entry = (Map.Entry) it.next();
+ put(entry.getKey(), entry.getValue());
+ }
+ }
+
public Object remove(Object key) {
Object result = getMap().remove(key);
insertOrder.remove(key);
return result;
}
+ public void clear() {
+ getMap().clear();
+ insertOrder.clear();
+ }
+
+ //-----------------------------------------------------------------------
+ public MapIterator mapIterator() {
+ return new DefaultMapIterator(this);
+ }
+
public Set keySet() {
- return new KeyView( this, this.insertOrder );
+ return new KeySetView(this);
}
public Collection values() {
- return new ValuesView( this, this.insertOrder );
+ return new ValuesView(this);
}
- // QUERY: Should a change of value change insertion order?
public Set entrySet() {
- return new EntrySetView( this, this.insertOrder );
+ return new EntrySetView(this, this.insertOrder);
}
-
- // TODO: Code a toString up.
- // It needs to retain the right order, else it will
- // look peculiar.
+
+ //-----------------------------------------------------------------------
+ /**
+ * Returns the Map as a string.
+ *
+ * @return the Map as a String
+ */
public String toString() {
- return super.toString();
+ if (isEmpty()) {
+ return "{}";
+ }
+ StringBuffer buf = new StringBuffer();
+ buf.append('{');
+ boolean first = true;
+ Iterator it = entrySet().iterator();
+ while (it.hasNext()) {
+ Map.Entry entry = (Map.Entry) it.next();
+ Object key = entry.getKey();
+ Object value = entry.getValue();
+ buf.append(key == this ? "(this Map)" : key);
+ buf.append('=');
+ buf.append(value == this ? "(this Map)" : value);
+ if (first) {
+ first = false;
+ } else {
+ buf.append(", ");
+ }
+ }
+ buf.append('}');
+ return buf.toString();
}
- // class for handling the values() method's callback to this Map
- // THESE NEED UNIT TESTING as their own collections
- class ValuesView implements Collection {
- private OrderedMap parent;
- private List insertOrder;
+ //-----------------------------------------------------------------------
+ static class ValuesView extends AbstractCollection {
+ private final OrderedMap parent;
- ValuesView(OrderedMap parent, List insertOrder) {
+ ValuesView(OrderedMap parent) {
+ super();
this.parent = parent;
- this.insertOrder = insertOrder;
- }
-
- // slow to call
- Collection _values() {
- Iterator keys = this.insertOrder.iterator();
- ArrayList list = new ArrayList( insertOrder.size() );
- while( keys.hasNext() ) {
- list.add( this.parent.getMap().get( keys.next() ) );
- }
- return list;
}
public int size() {
return this.parent.size();
}
- public boolean isEmpty() {
- return this.parent.isEmpty();
- }
-
public boolean contains(Object value) {
return this.parent.containsValue(value);
}
- public Iterator iterator() {
- // TODO: Allow this to be backed
- return _values().iterator();
-// return new ValuesViewIterator( who? );
- }
-
- public Object[] toArray() {
- return _values().toArray();
- }
-
- public Object[] toArray(Object[] array) {
- return _values().toArray(array);
- }
-
- public boolean add(Object obj) {
- throw new UnsupportedOperationException("Not allowed. ");
- }
-
- public boolean remove(Object obj) {
- // who?? which value do I choose? first one?
- for(Iterator itr = this.insertOrder.iterator(); itr.hasNext(); ) {
- Object key = itr.next();
- Object value = this.parent.get(key);
-
- // also handles null
- if(value == obj) {
- return (this.parent.remove(key) != null);
- }
-
- if( (value != null) && value.equals(obj) ) {
- return (this.parent.remove(key) != null);
- }
- }
-
- return false;
- }
-
- public boolean containsAll(Collection coll) {
- // TODO: What does Collection spec say about null/empty?
- for(Iterator itr = coll.iterator(); itr.hasNext(); ) {
- if( !this.parent.containsValue( itr.next() ) ) {
- return false;
- }
- }
- return true;
- }
-
- public boolean addAll(Collection coll) {
- throw new UnsupportedOperationException("Not allowed. ");
- }
-
- public boolean removeAll(Collection coll) {
- // not transactional. No idea if removeAll's boolean
- // reply is meant to be
- boolean ret = false;
- for( Iterator itr = coll.iterator(); itr.hasNext(); ) {
- ret = ret && remove(itr.next());
- }
- return ret;
- }
-
- public boolean retainAll(Collection coll) {
- // transactional?
- boolean ret = false;
-
- for( Iterator itr = this.insertOrder.iterator(); itr.hasNext(); ) {
- Object key = itr.next();
- Object value = this.parent.get(key);
- if( coll.contains(value) ) {
- // retain
- } else {
- ret = ret && (parent.remove(key) != null);
- }
- }
-
- return ret;
- }
-
public void clear() {
this.parent.clear();
}
- public boolean equals(Object obj) {
- // exactly what to do here?
- return super.equals(obj);
- }
- public int hashCode() {
- return _values().hashCode();
- }
-
- public String toString() {
- return _values().toString();
+ public Iterator iterator() {
+ return new AbstractIteratorDecorator(parent.entrySet().iterator()) {
+ public Object next() {
+ return ((Map.Entry) iterator.next()).getValue();
+ }
+ };
}
}
+
+ //-----------------------------------------------------------------------
+ static class KeySetView extends AbstractSet {
+ private final OrderedMap parent;
- class KeyView implements Set {
-
- private OrderedMap parent;
- private List insertOrder;
-
- public KeyView(OrderedMap parent, List insertOrder) {
+ KeySetView(OrderedMap parent) {
+ super();
this.parent = parent;
- this.insertOrder = insertOrder;
}
public int size() {
return this.parent.size();
}
- public boolean isEmpty() {
- return this.parent.isEmpty();
- }
- public boolean contains(Object obj) {
- return this.parent.containsKey(obj);
- }
- public Iterator iterator() {
- // TODO: Needs to return a KeyViewIterator, which
- // removes from this and from the Map
- return this.insertOrder.iterator();
- }
- public Object toArray()[] {
- return this.insertOrder.toArray();
- }
- public Object toArray(Object[] array)[] {
- return this.insertOrder.toArray(array);
- }
- public boolean add(Object obj) {
- throw new UnsupportedOperationException("Not allowed. ");
- }
- public boolean remove(Object obj) {
- return (this.parent.remove(obj) != null);
- }
- public boolean containsAll(Collection coll) {
- // TODO: What does Collection spec say about null/empty?
- for(Iterator itr = coll.iterator(); itr.hasNext(); ) {
- if( !this.parent.containsKey( itr.next() ) ) {
- return false;
- }
- }
- return true;
- }
- public boolean addAll(Collection coll) {
- throw new UnsupportedOperationException("Not allowed. ");
- }
- public boolean removeAll(Collection coll) {
- // not transactional. No idea if removeAll's boolean
- // reply is meant to be
- boolean ret = false;
- for( Iterator itr = coll.iterator(); itr.hasNext(); ) {
- ret = ret && remove(itr.next());
- }
- return ret;
- }
- public boolean retainAll(Collection coll) {
- // transactional?
- boolean ret = false;
-
- for( Iterator itr = this.insertOrder.iterator(); itr.hasNext(); ) {
- Object key = itr.next();
- if( coll.contains(key) ) {
- // retain
- } else {
- ret = ret && (parent.remove(key) != null);
- }
- }
- return ret;
+ public boolean contains(Object value) {
+ return this.parent.containsKey(value);
}
+
public void clear() {
this.parent.clear();
}
- public boolean equals(Object obj) {
- // exactly what to do here?
- return super.equals(obj);
- }
- public int hashCode() {
- return this.parent.getMap().keySet().hashCode();
- }
- public String toString() {
- return this.insertOrder.toString();
+ public Iterator iterator() {
+ return new AbstractIteratorDecorator(parent.entrySet().iterator()) {
+ public Object next() {
+ return ((Map.Entry) super.next()).getKey();
+ }
+ };
}
}
- class EntrySetView implements Set {
-
- private OrderedMap parent;
- private List insertOrder;
+ //-----------------------------------------------------------------------
+ static class EntrySetView extends AbstractSet {
+ private final OrderedMap parent;
+ private final List insertOrder;
+ private Set entrySet;
public EntrySetView(OrderedMap parent, List insertOrder) {
+ super();
this.parent = parent;
this.insertOrder = insertOrder;
}
- public Set _entries() {
- Set set = new java.util.HashSet( this.insertOrder.size() );
- set = OrderedSet.decorate( set );
- for (Iterator it = insertOrder.iterator(); it.hasNext();) {
- Object key = it.next();
- set.add( new DefaultMapEntry( key, getMap().get( key ) ) );
+ private Set getEntrySet() {
+ if (entrySet == null) {
+ entrySet = parent.getMap().entrySet();
}
- return set;
+ return entrySet;
}
-
+
public int size() {
return this.parent.size();
}
@@ -401,98 +279,83 @@
}
public boolean contains(Object obj) {
- if(obj instanceof Map.Entry) {
- Map.Entry entry = (Map.Entry) obj;
- if( this.parent.containsKey(entry.getKey()) ) {
- Object value = this.parent.get(entry.getKey());
- if( obj == null && value == null ) {
- return true;
- } else {
- return obj.equals(value);
- }
- } else {
- return false;
- }
- } else {
- throw new IllegalArgumentException("Parameter must be a Map.Entry");
- }
+ return getEntrySet().contains(obj);
}
- public Iterator iterator() {
- // TODO: Needs to return a EntrySetViewIterator, which
- // removes from this and from the Map
- return _entries().iterator();
- }
- public Object toArray()[] {
- return _entries().toArray();
- }
- public Object toArray(Object[] array)[] {
- return _entries().toArray(array);
- }
- public boolean add(Object obj) {
- throw new UnsupportedOperationException("Not allowed. ");
+
+ public boolean containsAll(Collection coll) {
+ return getEntrySet().containsAll(coll);
}
+
public boolean remove(Object obj) {
- if(obj instanceof Map.Entry) {
- Map.Entry entry = (Map.Entry) obj;
- return (this.parent.remove(entry.getKey()) != null);
- } else {
- throw new IllegalArgumentException("Parameter must be a Map.Entry");
+ if (obj instanceof Map.Entry == false) {
+ return false;
}
- }
- // need to decide on IllegalArgument or ClassCast in this class
- // when not Map.Entry
- public boolean containsAll(Collection coll) {
- // TODO: What does Collection spec say about null/empty?
- for(Iterator itr = coll.iterator(); itr.hasNext(); ) {
- Map.Entry entry = (Map.Entry) itr.next();
- if( !this.parent.containsKey( entry.getKey() ) ) {
- return false;
- }
+ Object key = ((Map.Entry) obj).getKey();
+ if (parent.getMap().containsKey(key) == false) {
+ return false;
}
+ parent.remove(key);
return true;
}
- public boolean addAll(Collection coll) {
- throw new UnsupportedOperationException("Not allowed. ");
- }
- public boolean removeAll(Collection coll) {
- // not transactional. No idea if removeAll's boolean
- // reply is meant to be
- boolean ret = false;
- for( Iterator itr = coll.iterator(); itr.hasNext(); ) {
- Map.Entry entry = (Map.Entry) itr.next();
- ret = ret && remove( entry.getKey() );
- }
- return ret;
- }
- public boolean retainAll(Collection coll) {
- // transactional?
- boolean ret = false;
-
- for( Iterator itr = this.insertOrder.iterator(); itr.hasNext(); ) {
- Map.Entry entry = (Map.Entry) itr.next();
- Object key = entry.getKey();
- if( coll.contains(key) ) {
- // retain
- } else {
- ret = ret && (parent.remove(key) != null);
- }
- }
- return ret;
- }
public void clear() {
this.parent.clear();
}
+
public boolean equals(Object obj) {
- // exactly what to do here?
- return super.equals(obj);
+ if (obj == this) {
+ return true;
+ }
+ return getEntrySet().equals(obj);
}
+
public int hashCode() {
- return this.parent.getMap().entrySet().hashCode();
+ return getEntrySet().hashCode();
}
public String toString() {
- return this._entries().toString();
+ return getEntrySet().toString();
+ }
+
+ public Iterator iterator() {
+ return new OrderedIterator(parent, insertOrder);
+ }
+ }
+
+ static class OrderedIterator extends AbstractIteratorDecorator {
+ private final OrderedMap parent;
+ private Object last = null;
+
+ OrderedIterator(OrderedMap parent, List insertOrder) {
+ super(insertOrder.iterator());
+ this.parent = parent;
+ }
+
+ public Object next() {
+ last = super.next();
+ return new OrderedMapEntry(parent, last);
+ }
+
+ public void remove() {
+ super.remove();
+ parent.getMap().remove(last);
+ }
+ }
+
+ static class OrderedMapEntry extends AbstractMapEntry {
+ private final OrderedMap parent;
+
+ OrderedMapEntry(OrderedMap parent, Object key) {
+ super(key, null);
+ this.parent = parent;
+ }
+
+ public Object getValue() {
+ return parent.get(key);
+ }
+
+ public Object setValue(Object value) {
+ return parent.getMap().put(key, value);
}
}
1.3 +124 -4
jakarta-commons/collections/src/test/org/apache/commons/collections/decorators/TestOrderedMap.java
Index: TestOrderedMap.java
===================================================================
RCS file:
/home/cvs/jakarta-commons/collections/src/test/org/apache/commons/collections/decorators/TestOrderedMap.java,v
retrieving revision 1.2
retrieving revision 1.3
diff -u -r1.2 -r1.3
--- TestOrderedMap.java 3 Oct 2003 12:54:54 -0000 1.2
+++ TestOrderedMap.java 4 Nov 2003 23:36:23 -0000 1.3
@@ -65,9 +65,11 @@
import java.util.Set;
import junit.framework.Test;
-import junit.framework.TestSuite;
import org.apache.commons.collections.AbstractTestMap;
+import org.apache.commons.collections.BulkTest;
+import org.apache.commons.collections.iterators.AbstractTestMapIterator;
+import org.apache.commons.collections.iterators.MapIterator;
/**
* Extension of [EMAIL PROTECTED] TestMap} for exercising the [EMAIL PROTECTED]
OrderedMap}
@@ -77,6 +79,7 @@
* @version $Revision$ $Date$
*
* @author Henri Yandell
+ * @author Stephen Colebourne
*/
public class TestOrderedMap extends AbstractTestMap {
@@ -85,7 +88,7 @@
}
public static Test suite() {
- return new TestSuite(TestOrderedMap.class);
+ return BulkTest.makeSuite(TestOrderedMap.class);
}
public static void main(String args[]) {
@@ -97,6 +100,123 @@
return OrderedMap.decorate(new HashMap());
}
+ //-----------------------------------------------------------------------
+ public BulkTest bulkTestMapIterator() {
+ return new TestOrderedMapIterator();
+ }
+
+ public class TestOrderedMapIterator extends AbstractTestMapIterator {
+ public TestOrderedMapIterator() {
+ super("TestOrderedMapIterator");
+ }
+
+ protected Object addSetValue() {
+ return TestOrderedMap.this.getNewSampleValues()[0];
+ }
+
+ protected boolean supportsRemove() {
+ return TestOrderedMap.this.isRemoveSupported();
+ }
+
+ protected boolean supportsSetValue() {
+ return TestOrderedMap.this.isSetValueSupported();
+ }
+
+ protected MapIterator makeEmptyMapIterator() {
+ resetEmpty();
+ return ((OrderedMap) TestOrderedMap.this.map).mapIterator();
+ }
+
+ protected MapIterator makeFullMapIterator() {
+ resetFull();
+ return ((OrderedMap) TestOrderedMap.this.map).mapIterator();
+ }
+
+ protected Map getMap() {
+ // assumes makeFullMapIterator() called first
+ return TestOrderedMap.this.map;
+ }
+ }
+
+ //-----------------------------------------------------------------------
+ public void testMapIteratorRemove() {
+ resetFull();
+ OrderedMap testMap = (OrderedMap) map;
+ MapIterator it = testMap.mapIterator();
+ assertEquals(true, it.hasNext());
+ Object key = it.next();
+
+ if (isRemoveSupported() == false) {
+ try {
+ it.remove();
+ fail();
+ } catch (UnsupportedOperationException ex) {
+ }
+ return;
+ }
+
+ it.remove();
+ confirmed.remove(key);
+ assertEquals(false, testMap.containsKey(key));
+ verify();
+
+ try {
+ it.remove(); // second remove fails
+ } catch (IllegalStateException ex) {
+ }
+ verify();
+ }
+
+ //-----------------------------------------------------------------------
+ public void testMapIteratorSet() {
+ Object newValue1 = getOtherValues()[0];
+ Object newValue2 = getOtherValues()[1];
+
+ resetFull();
+ OrderedMap testMap = (OrderedMap) map;
+ MapIterator it = testMap.mapIterator();
+ assertEquals(true, it.hasNext());
+ Object key1 = it.next();
+
+ if (isSetValueSupported() == false) {
+ try {
+ it.setValue(newValue1);
+ fail();
+ } catch (UnsupportedOperationException ex) {
+ }
+ return;
+ }
+
+ it.setValue(newValue1);
+ confirmed.put(key1, newValue1);
+ assertSame(key1, it.getKey());
+ assertSame(newValue1, it.getValue());
+ assertEquals(true, testMap.containsKey(key1));
+ assertEquals(true, testMap.containsValue(newValue1));
+ assertEquals(newValue1, testMap.get(key1));
+ verify();
+
+ it.setValue(newValue1); // same value - should be OK
+ confirmed.put(key1, newValue1);
+ assertSame(key1, it.getKey());
+ assertSame(newValue1, it.getValue());
+ assertEquals(true, testMap.containsKey(key1));
+ assertEquals(true, testMap.containsValue(newValue1));
+ assertEquals(newValue1, testMap.get(key1));
+ verify();
+
+ Object key2 = it.next();
+ it.setValue(newValue2);
+ confirmed.put(key2, newValue2);
+ assertSame(key2, it.getKey());
+ assertSame(newValue2, it.getValue());
+ assertEquals(true, testMap.containsKey(key2));
+ assertEquals(true, testMap.containsValue(newValue2));
+ assertEquals(newValue2, testMap.get(key2));
+ verify();
+ }
+
+ //-----------------------------------------------------------------------
// Creates a known series of Objects, puts them in
// an OrderedMap and ensures that all three Collection
// methods return in the correct order.
---------------------------------------------------------------------
To unsubscribe, e-mail: [EMAIL PROTECTED]
For additional commands, e-mail: [EMAIL PROTECTED]
