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 2003/12/28 23:45:47 UTC
cvs commit: jakarta-commons/collections/src/test/org/apache/commons/collections/map TestListOrderedMap.java TestLinkedMap.java
scolebourne 2003/12/28 14:45:47
Modified: collections/src/java/org/apache/commons/collections/map
ListOrderedMap.java LinkedMap.java
AbstractLinkedMap.java
collections/src/test/org/apache/commons/collections/map
TestListOrderedMap.java TestLinkedMap.java
Log:
Add list view methods to ordered maps
Revision Changes Path
1.9 +68 -2 jakarta-commons/collections/src/java/org/apache/commons/collections/map/ListOrderedMap.java
Index: ListOrderedMap.java
===================================================================
RCS file: /home/cvs/jakarta-commons/collections/src/java/org/apache/commons/collections/map/ListOrderedMap.java,v
retrieving revision 1.8
retrieving revision 1.9
diff -u -r1.8 -r1.9
--- ListOrderedMap.java 7 Dec 2003 23:59:13 -0000 1.8
+++ ListOrderedMap.java 28 Dec 2003 22:45:47 -0000 1.9
@@ -74,6 +74,7 @@
import org.apache.commons.collections.ResettableIterator;
import org.apache.commons.collections.iterators.AbstractIteratorDecorator;
import org.apache.commons.collections.keyvalue.AbstractMapEntry;
+import org.apache.commons.collections.list.UnmodifiableList;
/**
* Decorates a <code>Map</code> to ensure that the order of addition is retained.
@@ -82,6 +83,7 @@
* The order is also returned by the <code>MapIterator</code>.
* The <code>orderedMapIterator()</code> method accesses an iterator that can
* iterate both forwards and backwards through the map.
+ * In addition, non-interface methods are provided to access the map by index.
* <p>
* If an object is added to the Map for a second time, it will remain in the
* original position in the iteration.
@@ -260,6 +262,70 @@
}
buf.append('}');
return buf.toString();
+ }
+
+ //-----------------------------------------------------------------------
+ /**
+ * Gets the key at the specified index.
+ *
+ * @param index the index to retrieve
+ * @return the key at the specified index
+ * @throws IndexOutOfBoundsException if the index is invalid
+ */
+ public Object get(int index) {
+ return insertOrder.get(index);
+ }
+
+ /**
+ * Gets the value at the specified index.
+ *
+ * @param index the index to retrieve
+ * @return the key at the specified index
+ * @throws IndexOutOfBoundsException if the index is invalid
+ */
+ public Object getValue(int index) {
+ return get(insertOrder.get(index));
+ }
+
+ /**
+ * 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) {
+ return insertOrder.indexOf(key);
+ }
+
+ /**
+ * Removes the element at the specified index.
+ *
+ * @param index the index of the object to remove
+ * @return the previous value corresponding the <code>key</code>,
+ * or <code>null</code> if none existed
+ * @throws IndexOutOfBoundsException if the index is invalid
+ */
+ public Object remove(int index) {
+ return remove(get(index));
+ }
+
+ /**
+ * Gets an unmodifiable List view of the keys which changes as the map changes.
+ * <p>
+ * The returned list is unmodifiable 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 asList() {
+ return UnmodifiableList.decorate(insertOrder);
}
//-----------------------------------------------------------------------
1.6 +164 -3 jakarta-commons/collections/src/java/org/apache/commons/collections/map/LinkedMap.java
Index: LinkedMap.java
===================================================================
RCS file: /home/cvs/jakarta-commons/collections/src/java/org/apache/commons/collections/map/LinkedMap.java,v
retrieving revision 1.5
retrieving revision 1.6
diff -u -r1.5 -r1.6
--- LinkedMap.java 28 Dec 2003 17:58:54 -0000 1.5
+++ LinkedMap.java 28 Dec 2003 22:45:47 -0000 1.6
@@ -61,16 +61,26 @@
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.io.Serializable;
+import java.util.AbstractList;
+import java.util.Collection;
+import java.util.Iterator;
+import java.util.List;
+import java.util.ListIterator;
import java.util.Map;
+import org.apache.commons.collections.iterators.UnmodifiableIterator;
+import org.apache.commons.collections.iterators.UnmodifiableListIterator;
+import org.apache.commons.collections.list.UnmodifiableList;
+
/**
* A <code>Map</code> implementation that maintains the order of the entries.
- * In this implementation order is maintained is by original insertion.
+ * In this implementation order is maintained by original insertion.
* <p>
* This implementation improves on the JDK1.4 LinkedHashMap by adding the
* {@link org.apache.commons.collections.MapIterator MapIterator}
* functionality, additional convenience methods and allowing
* bidirectional iteration. It also implements <code>OrderedMap</code>.
+ * In addition, non-interface methods are provided to access the map by index.
* <p>
* The <code>orderedMapIterator()</code> method provides direct access to a
* bidirectional iterator. The iterators from the other views can also be cast
@@ -156,6 +166,157 @@
private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
in.defaultReadObject();
doReadObject(in);
+ }
+
+ //-----------------------------------------------------------------------
+ /**
+ * Gets the key at the specified index.
+ *
+ * @param index the index to retrieve
+ * @return the key at the specified index
+ * @throws IndexOutOfBoundsException if the index is invalid
+ */
+ public Object get(int index) {
+ return getEntry(index).getKey();
+ }
+
+ /**
+ * Gets the value at the specified index.
+ *
+ * @param index the index to retrieve
+ * @return the key at the specified index
+ * @throws IndexOutOfBoundsException if the index is invalid
+ */
+ 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) {
+ key = convertKey(key);
+ int i = 0;
+ for (LinkEntry entry = header.after; entry != header; entry = entry.after, i++) {
+ if (isEqualKey(key, entry.key)) {
+ return i;
+ }
+ }
+ return -1;
+ }
+
+ /**
+ * Removes the element at the specified index.
+ *
+ * @param index the index of the object to remove
+ * @return the previous value corresponding the <code>key</code>,
+ * or <code>null</code> if none existed
+ * @throws IndexOutOfBoundsException if the index is invalid
+ */
+ public Object remove(int index) {
+ return remove(get(index));
+ }
+
+ /**
+ * Gets an unmodifiable List view of the keys.
+ * <p>
+ * The returned list is unmodifiable 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 asList() {
+ return new LinkedMapList(this);
+ }
+
+ /**
+ * List view of map.
+ */
+ static class LinkedMapList extends AbstractList {
+
+ final LinkedMap parent;
+
+ LinkedMapList(LinkedMap parent) {
+ this.parent = parent;
+ }
+
+ public int size() {
+ return parent.size();
+ }
+
+ public Object get(int index) {
+ return parent.get(index);
+ }
+
+ public boolean contains(Object obj) {
+ return parent.containsKey(obj);
+ }
+
+ public int indexOf(Object obj) {
+ return parent.indexOf(obj);
+ }
+
+ public int lastIndexOf(Object obj) {
+ return parent.indexOf(obj);
+ }
+
+ public boolean containsAll(Collection coll) {
+ return parent.keySet().containsAll(coll);
+ }
+
+ public Object remove(int index) {
+ throw new UnsupportedOperationException();
+ }
+
+ public boolean remove(Object obj) {
+ throw new UnsupportedOperationException();
+ }
+
+ public boolean removeAll(Collection coll) {
+ throw new UnsupportedOperationException();
+ }
+
+ public boolean retainAll(Collection coll) {
+ throw new UnsupportedOperationException();
+ }
+
+ public void clear() {
+ throw new UnsupportedOperationException();
+ }
+
+ public Object[] toArray() {
+ return parent.keySet().toArray();
+ }
+
+ public Object[] toArray(Object[] array) {
+ return parent.keySet().toArray(array);
+ }
+
+ public Iterator iterator() {
+ return UnmodifiableIterator.decorate(parent.keySet().iterator());
+ }
+
+ public ListIterator listIterator() {
+ return UnmodifiableListIterator.decorate(super.listIterator());
+ }
+
+ public ListIterator listIterator(int fromIndex) {
+ return UnmodifiableListIterator.decorate(super.listIterator(fromIndex));
+ }
+
+ public List subList(int fromIndexInclusive, int toIndexExclusive) {
+ return UnmodifiableList.decorate(super.subList(fromIndexInclusive, toIndexExclusive));
+ }
}
}
1.3 +54 -9 jakarta-commons/collections/src/java/org/apache/commons/collections/map/AbstractLinkedMap.java
Index: AbstractLinkedMap.java
===================================================================
RCS file: /home/cvs/jakarta-commons/collections/src/java/org/apache/commons/collections/map/AbstractLinkedMap.java,v
retrieving revision 1.2
retrieving revision 1.3
diff -u -r1.2 -r1.3
--- AbstractLinkedMap.java 25 Dec 2003 01:09:01 -0000 1.2
+++ AbstractLinkedMap.java 28 Dec 2003 22:45:47 -0000 1.3
@@ -251,6 +251,37 @@
//-----------------------------------------------------------------------
/**
+ * Gets the key at the specified index.
+ *
+ * @param index the index to retrieve
+ * @return the key at the specified index
+ * @throws IndexOutOfBoundsException if the index is invalid
+ */
+ protected LinkEntry getEntry(int index) {
+ if (index < 0) {
+ throw new IndexOutOfBoundsException("Index " + index + " is less than zero");
+ }
+ if (index >= size) {
+ throw new IndexOutOfBoundsException("Index " + index + " is invalid for size " + size);
+ }
+ LinkEntry entry;
+ if (index < (size / 2)) {
+ // Search forwards
+ entry = header.after;
+ for (int currentIndex = 0; currentIndex < index; currentIndex++) {
+ entry = entry.after;
+ }
+ } else {
+ // Search backwards
+ entry = header;
+ for (int currentIndex = size; currentIndex > index; currentIndex--) {
+ entry = entry.before;
+ }
+ }
+ return entry;
+ }
+
+ /**
* Adds an entry into this map, maintaining insertion order.
* <p>
* This implementation adds the entry to the data storage table and
@@ -342,7 +373,7 @@
/**
* MapIterator implementation.
*/
- protected static class LinkMapIterator extends LinkIterator implements OrderedMapIterator {
+ static class LinkMapIterator extends LinkIterator implements OrderedMapIterator {
LinkMapIterator(AbstractLinkedMap map) {
super(map);
@@ -398,7 +429,7 @@
/**
* EntrySet iterator.
*/
- protected static class EntrySetIterator extends LinkIterator {
+ static class EntrySetIterator extends LinkIterator {
EntrySetIterator(AbstractLinkedMap map) {
super(map);
@@ -430,7 +461,7 @@
/**
* KeySet iterator.
*/
- protected static class KeySetIterator extends EntrySetIterator {
+ static class KeySetIterator extends EntrySetIterator {
KeySetIterator(AbstractLinkedMap map) {
super(map);
@@ -462,7 +493,7 @@
/**
* Values iterator.
*/
- protected static class ValuesIterator extends LinkIterator {
+ static class ValuesIterator extends LinkIterator {
ValuesIterator(AbstractLinkedMap map) {
super(map);
@@ -479,27 +510,41 @@
//-----------------------------------------------------------------------
/**
- * LinkEntry
+ * LinkEntry that stores the data.
*/
protected static class LinkEntry extends HashEntry {
+ /** The entry before this one in the order */
protected LinkEntry before;
+ /** The entry after this one in the order */
protected LinkEntry after;
+ /**
+ * Constructs a new entry.
+ *
+ * @param next the next entry in the hash bucket sequence
+ * @param hashCode the hash code
+ * @param key the key
+ * @param value the value
+ */
protected LinkEntry(HashEntry next, int hashCode, Object key, Object value) {
super(next, hashCode, key, value);
}
}
/**
- * Base Iterator
+ * Base Iterator that iterates in link order.
*/
protected static abstract class LinkIterator
implements OrderedIterator, ResettableIterator {
+ /** The parent map */
protected final AbstractLinkedMap map;
+ /** The current (last returned) entry */
protected LinkEntry current;
+ /** The next entry */
protected LinkEntry next;
+ /** The modification count expected */
protected int expectedModCount;
protected LinkIterator(AbstractLinkedMap map) {
@@ -512,7 +557,7 @@
public boolean hasNext() {
return (next != map.header);
}
-
+
public boolean hasPrevious() {
return (next.before != map.header);
}
1.6 +142 -2 jakarta-commons/collections/src/test/org/apache/commons/collections/map/TestListOrderedMap.java
Index: TestListOrderedMap.java
===================================================================
RCS file: /home/cvs/jakarta-commons/collections/src/test/org/apache/commons/collections/map/TestListOrderedMap.java,v
retrieving revision 1.5
retrieving revision 1.6
diff -u -r1.5 -r1.6
--- TestListOrderedMap.java 20 Nov 2003 22:34:49 -0000 1.5
+++ TestListOrderedMap.java 28 Dec 2003 22:45:47 -0000 1.6
@@ -57,12 +57,16 @@
*/
package org.apache.commons.collections.map;
+import java.util.ArrayList;
import java.util.HashMap;
+import java.util.List;
import java.util.Map;
import junit.framework.Test;
import org.apache.commons.collections.BulkTest;
+import org.apache.commons.collections.MapIterator;
+import org.apache.commons.collections.list.AbstractTestList;
/**
* Extension of {@link TestMap} for exercising the {@link ListOrderedMap}
@@ -91,6 +95,142 @@
public Map makeEmptyMap() {
return ListOrderedMap.decorate(new HashMap());
+ }
+
+ //-----------------------------------------------------------------------
+ public void testGetByIndex() {
+ resetEmpty();
+ ListOrderedMap lom = (ListOrderedMap) map;
+ try {
+ lom.get(0);
+ } catch (IndexOutOfBoundsException ex) {}
+ try {
+ lom.get(-1);
+ } catch (IndexOutOfBoundsException ex) {}
+
+ resetFull();
+ lom = (ListOrderedMap) map;
+ try {
+ lom.get(-1);
+ } catch (IndexOutOfBoundsException ex) {}
+ try {
+ lom.get(lom.size());
+ } catch (IndexOutOfBoundsException ex) {}
+
+ int i = 0;
+ for (MapIterator it = lom.mapIterator(); it.hasNext(); i++) {
+ assertSame(it.next(), lom.get(i));
+ }
+ }
+
+ public void testGetValueByIndex() {
+ resetEmpty();
+ ListOrderedMap lom = (ListOrderedMap) map;
+ try {
+ lom.getValue(0);
+ } catch (IndexOutOfBoundsException ex) {}
+ try {
+ lom.getValue(-1);
+ } catch (IndexOutOfBoundsException ex) {}
+
+ resetFull();
+ lom = (ListOrderedMap) map;
+ try {
+ lom.getValue(-1);
+ } catch (IndexOutOfBoundsException ex) {}
+ try {
+ lom.getValue(lom.size());
+ } catch (IndexOutOfBoundsException ex) {}
+
+ int i = 0;
+ for (MapIterator it = lom.mapIterator(); it.hasNext(); i++) {
+ it.next();
+ assertSame(it.getValue(), lom.getValue(i));
+ }
+ }
+
+ public void testIndexOf() {
+ resetEmpty();
+ ListOrderedMap lom = (ListOrderedMap) map;
+ assertEquals(-1, lom.indexOf(getOtherKeys()));
+
+ resetFull();
+ lom = (ListOrderedMap) map;
+ List list = new ArrayList();
+ for (MapIterator it = lom.mapIterator(); it.hasNext();) {
+ list.add(it.next());
+ }
+ for (int i = 0; i < list.size(); i++) {
+ assertEquals(i, lom.indexOf(list.get(i)));
+ }
+ }
+
+ public void testRemoveByIndex() {
+ resetEmpty();
+ ListOrderedMap lom = (ListOrderedMap) map;
+ try {
+ lom.remove(0);
+ } catch (IndexOutOfBoundsException ex) {}
+ try {
+ lom.remove(-1);
+ } catch (IndexOutOfBoundsException ex) {}
+
+ resetFull();
+ lom = (ListOrderedMap) map;
+ try {
+ lom.remove(-1);
+ } catch (IndexOutOfBoundsException ex) {}
+ try {
+ lom.remove(lom.size());
+ } catch (IndexOutOfBoundsException ex) {}
+
+ List list = new ArrayList();
+ for (MapIterator it = lom.mapIterator(); it.hasNext();) {
+ list.add(it.next());
+ }
+ for (int i = 0; i < list.size(); i++) {
+ Object key = list.get(i);
+ Object value = lom.get(key);
+ assertEquals(value, lom.remove(i));
+ list.remove(i);
+ assertEquals(false, lom.containsKey(key));
+ }
+ }
+
+ public BulkTest bulkTestListView() {
+ return new TestListView();
+ }
+
+ public class TestListView extends AbstractTestList {
+
+ TestListView() {
+ super("TestListView");
+ }
+
+ public List makeEmptyList() {
+ return ((ListOrderedMap) TestListOrderedMap.this.makeEmptyMap()).asList();
+ }
+
+ public List makeFullList() {
+ return ((ListOrderedMap) TestListOrderedMap.this.makeFullMap()).asList();
+ }
+
+ public Object[] getFullElements() {
+ return TestListOrderedMap.this.getSampleKeys();
+ }
+ public boolean isAddSupported() {
+ return false;
+ }
+ public boolean isRemoveSupported() {
+ return false;
+ }
+ public boolean isSetSupported() {
+ return false;
+ }
+ public boolean isNullSupported() {
+ return TestListOrderedMap.this.isAllowNullKey();
+ }
+
}
}
1.4 +140 -2 jakarta-commons/collections/src/test/org/apache/commons/collections/map/TestLinkedMap.java
Index: TestLinkedMap.java
===================================================================
RCS file: /home/cvs/jakarta-commons/collections/src/test/org/apache/commons/collections/map/TestLinkedMap.java,v
retrieving revision 1.3
retrieving revision 1.4
diff -u -r1.3 -r1.4
--- TestLinkedMap.java 7 Dec 2003 23:59:12 -0000 1.3
+++ TestLinkedMap.java 28 Dec 2003 22:45:47 -0000 1.4
@@ -66,8 +66,10 @@
import junit.textui.TestRunner;
import org.apache.commons.collections.BulkTest;
+import org.apache.commons.collections.MapIterator;
import org.apache.commons.collections.OrderedMap;
import org.apache.commons.collections.ResettableIterator;
+import org.apache.commons.collections.list.AbstractTestList;
/**
* JUnit tests.
@@ -159,6 +161,142 @@
assertSame(values[2], it.next());
}
+ //-----------------------------------------------------------------------
+ public void testGetByIndex() {
+ resetEmpty();
+ LinkedMap lm = (LinkedMap) map;
+ try {
+ lm.get(0);
+ } catch (IndexOutOfBoundsException ex) {}
+ try {
+ lm.get(-1);
+ } catch (IndexOutOfBoundsException ex) {}
+
+ resetFull();
+ lm = (LinkedMap) map;
+ try {
+ lm.get(-1);
+ } catch (IndexOutOfBoundsException ex) {}
+ try {
+ lm.get(lm.size());
+ } catch (IndexOutOfBoundsException ex) {}
+
+ int i = 0;
+ for (MapIterator it = lm.mapIterator(); it.hasNext(); i++) {
+ assertSame(it.next(), lm.get(i));
+ }
+ }
+
+ public void testGetValueByIndex() {
+ resetEmpty();
+ LinkedMap lm = (LinkedMap) map;
+ try {
+ lm.getValue(0);
+ } catch (IndexOutOfBoundsException ex) {}
+ try {
+ lm.getValue(-1);
+ } catch (IndexOutOfBoundsException ex) {}
+
+ resetFull();
+ lm = (LinkedMap) map;
+ try {
+ lm.getValue(-1);
+ } catch (IndexOutOfBoundsException ex) {}
+ try {
+ lm.getValue(lm.size());
+ } catch (IndexOutOfBoundsException ex) {}
+
+ int i = 0;
+ for (MapIterator it = lm.mapIterator(); it.hasNext(); i++) {
+ it.next();
+ assertSame(it.getValue(), lm.getValue(i));
+ }
+ }
+
+ public void testIndexOf() {
+ resetEmpty();
+ LinkedMap lm = (LinkedMap) map;
+ assertEquals(-1, lm.indexOf(getOtherKeys()));
+
+ resetFull();
+ lm = (LinkedMap) map;
+ List list = new ArrayList();
+ for (MapIterator it = lm.mapIterator(); it.hasNext();) {
+ list.add(it.next());
+ }
+ for (int i = 0; i < list.size(); i++) {
+ assertEquals(i, lm.indexOf(list.get(i)));
+ }
+ }
+
+ public void testRemoveByIndex() {
+ resetEmpty();
+ LinkedMap lm = (LinkedMap) map;
+ try {
+ lm.remove(0);
+ } catch (IndexOutOfBoundsException ex) {}
+ try {
+ lm.remove(-1);
+ } catch (IndexOutOfBoundsException ex) {}
+
+ resetFull();
+ lm = (LinkedMap) map;
+ try {
+ lm.remove(-1);
+ } catch (IndexOutOfBoundsException ex) {}
+ try {
+ lm.remove(lm.size());
+ } catch (IndexOutOfBoundsException ex) {}
+
+ List list = new ArrayList();
+ for (MapIterator it = lm.mapIterator(); it.hasNext();) {
+ list.add(it.next());
+ }
+ for (int i = 0; i < list.size(); i++) {
+ Object key = list.get(i);
+ Object value = lm.get(key);
+ assertEquals(value, lm.remove(i));
+ list.remove(i);
+ assertEquals(false, lm.containsKey(key));
+ }
+ }
+
+ public BulkTest bulkTestListView() {
+ return new TestListView();
+ }
+
+ public class TestListView extends AbstractTestList {
+
+ TestListView() {
+ super("TestListView");
+ }
+
+ public List makeEmptyList() {
+ return ((LinkedMap) TestLinkedMap.this.makeEmptyMap()).asList();
+ }
+
+ public List makeFullList() {
+ return ((LinkedMap) TestLinkedMap.this.makeFullMap()).asList();
+ }
+
+ public Object[] getFullElements() {
+ return TestLinkedMap.this.getSampleKeys();
+ }
+ public boolean isAddSupported() {
+ return false;
+ }
+ public boolean isRemoveSupported() {
+ return false;
+ }
+ public boolean isSetSupported() {
+ return false;
+ }
+ public boolean isNullSupported() {
+ return TestLinkedMap.this.isAllowNullKey();
+ }
+
+ }
+
// public void testCreate() throws Exception {
// resetEmpty();
// writeExternalFormToDisk((java.io.Serializable) map, "D:/dev/collections/data/test/LinkedMap.emptyCollection.version3.obj");
---------------------------------------------------------------------
To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: commons-dev-help@jakarta.apache.org