psteitz 2003/10/04 23:41:08
Modified: collections/src/java/org/apache/commons/collections
CommonsLinkedList.java NodeCachingLinkedList.java
collections/src/test/org/apache/commons/collections
TestCommonsLinkedList.java
TestNodeCachingLinkedList.java
Log:
Fixed bug related to CreateNode parameter order reported on commons-dev list by
[EMAIL PROTECTED] on 3-Oct-03.
Added tests to TestCommonsLinkedList to cover node-manipulation methods and changed
TestNodeCachingLinkedList to extend TestCommonsLinkedList.
Revision Changes Path
1.8 +43 -5
jakarta-commons/collections/src/java/org/apache/commons/collections/CommonsLinkedList.java
Index: CommonsLinkedList.java
===================================================================
RCS file:
/home/cvs/jakarta-commons/collections/src/java/org/apache/commons/collections/CommonsLinkedList.java,v
retrieving revision 1.7
retrieving revision 1.8
diff -u -r1.7 -r1.8
--- CommonsLinkedList.java 31 Aug 2003 17:26:43 -0000 1.7
+++ CommonsLinkedList.java 5 Oct 2003 06:41:08 -0000 1.8
@@ -79,6 +79,7 @@
* @version $Revision$ $Date$
*
* @author <a href="mailto:[EMAIL PROTECTED]">Rich Dougherty</a>
+ * @author Phil Steitz
*/
class CommonsLinkedList extends LinkedList
implements List, Serializable {
@@ -325,14 +326,34 @@
// Operations on nodes
+ /**
+ * Creates a new node with previous, next and element all set to null.
+ *
+ * @return newly created node
+ */
protected Node createNode() {
return new Node();
}
- protected Node createNode(Node next, Node previous, Object element) {
- return new Node(next, previous, element);
+ /**
+ * Creates a new node with the specified properties.
+ *
+ * @param previous node to precede the new node
+ * @param next node to follow the new node
+ * @param element element of the new node
+ */
+ protected Node createNode(Node previous, Node next, Object element) {
+ return new Node(previous, next, element);
}
+ /**
+ * Creates a new node with the specified object as its
+ * <code>elemnent</code> and inserts it before <code>node</code>.
+ *
+ * @param node node to insert before
+ * @param object element of the newly added node
+ * @throws NullPointerException if <code>node</code> is null
+ */
private void addNodeBefore(Node node, Object o) {
Node newNode = createNode(node.previous, node, o);
node.previous.next = newNode;
@@ -341,6 +362,14 @@
modCount++;
}
+ /**
+ * Creates a new node with the specified object as its
+ * <code>elemnent</code> and inserts it after <code>node</code>.
+ *
+ * @param node node to insert after
+ * @param o element of the newly added node
+ * @throws NullPointerException if <code>node</code> is null
+ */
protected void addNodeAfter(Node node, Object o) {
Node newNode = createNode(node, node.next, o);
node.next.previous = newNode;
@@ -349,6 +378,12 @@
modCount++;
}
+ /**
+ * Removes the specified node.
+ *
+ * @param node the node to remove
+ * @throws NullPointerException if <code>node</code> is null
+ */
protected void removeNode(Node node) {
node.previous.next = node.next;
node.next.previous = node.previous;
@@ -356,6 +391,9 @@
modCount++;
}
+ /**
+ * Removes all nodes by resetting the circular list marker.
+ */
protected void removeAllNodes() {
marker.next = marker;
marker.previous = marker;
@@ -367,7 +405,7 @@
* Gets the node at a particular index.
*
* @param index The index, starting from 0.
- * @param endMarkerAllowd Whether or not the end marker can be returned if
+ * @param endMarkerAllowed Whether or not the end marker can be returned if
* startIndex is set to the list's size.
* @throws IndexOutOfBoundsException If the index is less than 0; equal to
* the size of the list and endMakerAllowed is false; or greater than the
1.8 +15 -9
jakarta-commons/collections/src/java/org/apache/commons/collections/NodeCachingLinkedList.java
Index: NodeCachingLinkedList.java
===================================================================
RCS file:
/home/cvs/jakarta-commons/collections/src/java/org/apache/commons/collections/NodeCachingLinkedList.java,v
retrieving revision 1.7
retrieving revision 1.8
diff -u -r1.7 -r1.8
--- NodeCachingLinkedList.java 31 Aug 2003 17:26:44 -0000 1.7
+++ NodeCachingLinkedList.java 5 Oct 2003 06:41:08 -0000 1.8
@@ -69,6 +69,7 @@
*
* @author Jeff Varszegi
* @author <a href="mailto:[EMAIL PROTECTED]">Rich Dougherty</a>
+ * @author Phil Steitz
*/
public class NodeCachingLinkedList extends CommonsLinkedList {
@@ -114,7 +115,7 @@
/**
* Constructor that species the maximum cache size.
- *
+ *
* @param maximumCacheSize the maximum cache size
*/
public NodeCachingLinkedList(int maximumCacheSize) {
@@ -153,7 +154,7 @@
* Gets a node from the cache. If a node is returned, then the value of
* [EMAIL PROTECTED] #cacheSize} is decreased accordingly. The node that is
returned
* will have <code>null</code> values for next, previous and element.
- *
+ *
* @return A node, or <code>null</code> if there are no nodes in the cache.
*/
private Node getNodeFromCache() {
@@ -163,7 +164,7 @@
Node cachedNode = firstCachedNode;
firstCachedNode = cachedNode.next;
cachedNode.next = null; // This should be changed anyway, but defensively
- // set it to null.
+ // set it to null.
cacheSize--;
return cachedNode;
}
@@ -205,12 +206,17 @@
}
/**
- * Create a node, getting it from the cache if possible.
+ * Creates a new node with the specified properties, using a cached Node
+ * if possible.
+ *
+ * @param previous node to precede the new node
+ * @param next node to follow the new node
+ * @param element element of the new node
*/
- protected Node createNode(Node next, Node previous, Object element) {
+ protected Node createNode(Node previous, Node next, Object element) {
Node cachedNode = getNodeFromCache();
if (cachedNode == null) {
- return super.createNode(next, previous, element);
+ return super.createNode(previous, next, element);
} else {
cachedNode.next = next;
cachedNode.previous = previous;
@@ -224,7 +230,7 @@
* <code>addNodeToCache</code> on the node which has
* been removed.
*
- * @see CommonsLinkedList#removeNode
+ * @see CommonsLinkedList#removeNode(Node)
*/
protected void removeNode(Node node) {
super.removeNode(node);
1.4 +130 -6
jakarta-commons/collections/src/test/org/apache/commons/collections/TestCommonsLinkedList.java
Index: TestCommonsLinkedList.java
===================================================================
RCS file:
/home/cvs/jakarta-commons/collections/src/test/org/apache/commons/collections/TestCommonsLinkedList.java,v
retrieving revision 1.3
retrieving revision 1.4
diff -u -r1.3 -r1.4
--- TestCommonsLinkedList.java 31 Aug 2003 17:28:43 -0000 1.3
+++ TestCommonsLinkedList.java 5 Oct 2003 06:41:08 -0000 1.4
@@ -60,6 +60,7 @@
*/
package org.apache.commons.collections;
+import java.util.Arrays;
import java.util.LinkedList;
import junit.framework.Test;
@@ -68,17 +69,21 @@
* Test case for [EMAIL PROTECTED] CommonsLinkedList}.
*
* @author <a href="mailto:[EMAIL PROTECTED]">Rich Dougherty</a>
+ * @author David Hay
+ * @author Phil Steitz
*/
public class TestCommonsLinkedList extends TestLinkedList {
-
+
+ protected CommonsLinkedList list = null;
+
public TestCommonsLinkedList(String testName) {
super(testName);
}
-
+
public LinkedList makeEmptyLinkedList() {
return new CommonsLinkedList();
}
-
+
public static Test suite() {
return BulkTest.makeSuite(TestCommonsLinkedList.class);
}
@@ -87,4 +92,123 @@
return "2.2";
}
+ public void setUp() {
+ list = (CommonsLinkedList)makeEmptyList();
+ }
+
+ public void testRemoveFirst() {
+ list.addAll( Arrays.asList( new String[]{"value1", "value2"}));
+ assertEquals( "value1", list.removeFirst() );
+ checkNodes();
+ list.addLast( "value3");
+ checkNodes();
+ assertEquals( "value2", list.removeFirst() );
+ assertEquals( "value3", list.removeFirst() );
+ checkNodes();
+ list.addLast( "value4" );
+ checkNodes();
+ assertEquals( "value4", list.removeFirst() );
+ checkNodes();
+ }
+
+ public void testRemoveLast() {
+ list.addAll( Arrays.asList( new String[]{"value1", "value2"}));
+ assertEquals( "value2", list.removeLast() );
+ list.addFirst( "value3");
+ checkNodes();
+ assertEquals( "value1", list.removeLast() );
+ assertEquals( "value3", list.removeLast() );
+ list.addFirst( "value4" );
+ checkNodes();
+ assertEquals( "value4", list.removeFirst() );
+ }
+
+ public void testAddNodeAfter() {
+ list.addFirst("value1");
+ list.addNodeAfter(list.getNode(0,false),"value2");
+ assertEquals("value1", list.getFirst());
+ assertEquals("value2", list.getLast());
+ list.removeFirst();
+ checkNodes();
+ list.addNodeAfter(list.getNode(0,false),"value3");
+ checkNodes();
+ assertEquals("value2", list.getFirst());
+ assertEquals("value3", list.getLast());
+ list.addNodeAfter(list.getNode(0, false),"value4");
+ checkNodes();
+ assertEquals("value2", list.getFirst());
+ assertEquals("value3", list.getLast());
+ assertEquals("value4", list.get(1));
+ list.addNodeAfter(list.getNode(2, false), "value5");
+ checkNodes();
+ assertEquals("value2", list.getFirst());
+ assertEquals("value4", list.get(1));
+ assertEquals("value3", list.get(2));
+ assertEquals("value5", list.getLast());
+ }
+
+ public void testRemoveNode() {
+ list.addAll( Arrays.asList( new String[]{"value1", "value2"}));
+ list.removeNode(list.getNode(0, false));
+ checkNodes();
+ assertEquals("value2", list.getFirst());
+ assertEquals("value2", list.getLast());
+ list.addFirst("value1");
+ list.addFirst("value0");
+ checkNodes();
+ list.removeNode(list.getNode(1, false));
+ assertEquals("value0", list.getFirst());
+ assertEquals("value2", list.getLast());
+ checkNodes();
+ list.removeNode(list.getNode(1, false));
+ assertEquals("value0", list.getFirst());
+ assertEquals("value0", list.getLast());
+ checkNodes();
+ }
+
+ public void testGetNode() {
+ // get marker
+ assertEquals(list.getNode(0, true).previous, list.getNode(0, true).next);
+ try {
+ Object obj = list.getNode(0, false);
+ fail("Expecting IndexOutOfBoundsException.");
+ } catch (IndexOutOfBoundsException ex) {
+ // expected
+ }
+ list.addAll( Arrays.asList( new String[]{"value1", "value2"}));
+ checkNodes();
+ list.addFirst("value0");
+ checkNodes();
+ list.removeNode(list.getNode(1, false));
+ checkNodes();
+ try {
+ Object obj = list.getNode(2, false);
+ fail("Expecting IndexOutOfBoundsException.");
+ } catch (IndexOutOfBoundsException ex) {
+ // expected
+ }
+ try {
+ Object obj = list.getNode(-1, false);
+ fail("Expecting IndexOutOfBoundsException.");
+ } catch (IndexOutOfBoundsException ex) {
+ // expected
+ }
+ try {
+ Object obj = list.getNode(3, true);
+ fail("Expecting IndexOutOfBoundsException.");
+ } catch (IndexOutOfBoundsException ex) {
+ // expected
+ }
+ }
+
+ protected void checkNodes() {
+ for (int i = 0; i < list.size; i++) {
+ assertEquals(list.getNode(i, false).next, list.getNode(i + 1, true));
+ if (i < list.size - 1) {
+ assertEquals(list.getNode(i + 1, false).previous,
+ list.getNode(i, false));
+ }
+ }
+ }
+
}
1.5 +20 -5
jakarta-commons/collections/src/test/org/apache/commons/collections/TestNodeCachingLinkedList.java
Index: TestNodeCachingLinkedList.java
===================================================================
RCS file:
/home/cvs/jakarta-commons/collections/src/test/org/apache/commons/collections/TestNodeCachingLinkedList.java,v
retrieving revision 1.4
retrieving revision 1.5
diff -u -r1.4 -r1.5
--- TestNodeCachingLinkedList.java 31 Aug 2003 17:28:43 -0000 1.4
+++ TestNodeCachingLinkedList.java 5 Oct 2003 06:41:08 -0000 1.5
@@ -60,6 +60,7 @@
*/
package org.apache.commons.collections;
+import java.util.Arrays;
import java.util.LinkedList;
import junit.framework.Test;
@@ -67,9 +68,9 @@
* Test class for NodeCachingLinkedList, a performance optimised LinkedList.
*
* @author Jeff Varszegi
+ * @author Phil Steitz
*/
-public class TestNodeCachingLinkedList extends TestLinkedList {
- protected NodeCachingLinkedList list = null;
+public class TestNodeCachingLinkedList extends TestCommonsLinkedList {
public TestNodeCachingLinkedList(String _testName) {
super(_testName);
@@ -91,6 +92,20 @@
return "2.2";
}
+ public void testShrinkCache() {
+ list.addAll( Arrays.asList( new String[]{"1", "2", "3", "4"}));
+ list.removeAllNodes(); // Will dump all 4 elements into cache
+ ((NodeCachingLinkedList) list).setMaximumCacheSize(2); // shrink cache
+ list.addAll( Arrays.asList( new String[]{"1", "2", "3", "4"}));
+ checkNodes();
+ list.removeNode(list.getNode(0, false)); // no room in cache
+ list.removeNode(list.getNode(0, false));
+ list.removeNode(list.getNode(0, false));
+ checkNodes();
+ list.addAll( Arrays.asList( new String[]{"1", "2", "3", "4"}));
+ checkNodes();
+ }
+
public static void compareSpeed() {
NodeCachingLinkedList ncll = new NodeCachingLinkedList();
LinkedList ll = new LinkedList();
---------------------------------------------------------------------
To unsubscribe, e-mail: [EMAIL PROTECTED]
For additional commands, e-mail: [EMAIL PROTECTED]
