You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@commons.apache.org by tn...@apache.org on 2013/04/20 15:11:14 UTC
svn commit: r1470159 - in /commons/proper/collections/trunk: pom.xml
src/changes/changes.xml
src/main/java/org/apache/commons/collections4/list/TreeList.java
src/test/java/org/apache/commons/collections4/list/TreeListTest.java
Author: tn
Date: Sat Apr 20 13:11:14 2013
New Revision: 1470159
URL: http://svn.apache.org/r1470159
Log:
[COLLECTIONS-433] Improve performance of TreeList#addAll and TreeList(Collection). Thanks to Jeffrey Barnes for the patch.
Modified:
commons/proper/collections/trunk/pom.xml
commons/proper/collections/trunk/src/changes/changes.xml
commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/list/TreeList.java
commons/proper/collections/trunk/src/test/java/org/apache/commons/collections4/list/TreeListTest.java
Modified: commons/proper/collections/trunk/pom.xml
URL: http://svn.apache.org/viewvc/commons/proper/collections/trunk/pom.xml?rev=1470159&r1=1470158&r2=1470159&view=diff
==============================================================================
--- commons/proper/collections/trunk/pom.xml (original)
+++ commons/proper/collections/trunk/pom.xml Sat Apr 20 13:11:14 2013
@@ -124,12 +124,15 @@
<name>Federico Barbieri</name>
</contributor>
<contributor>
- <name>Arron Bates</name>
+ <name>Jeffrey Barnes</name>
</contributor>
<contributor>
<name>Nicola Ken Barozzi</name>
</contributor>
<contributor>
+ <name>Arron Bates</name>
+ </contributor>
+ <contributor>
<name>Sebastian Bazley</name>
</contributor>
<contributor>
Modified: commons/proper/collections/trunk/src/changes/changes.xml
URL: http://svn.apache.org/viewvc/commons/proper/collections/trunk/src/changes/changes.xml?rev=1470159&r1=1470158&r2=1470159&view=diff
==============================================================================
--- commons/proper/collections/trunk/src/changes/changes.xml (original)
+++ commons/proper/collections/trunk/src/changes/changes.xml Sat Apr 20 13:11:14 2013
@@ -22,6 +22,10 @@
<body>
<release version="4.0" date="TBA" description="Next release">
+ <action issue="COLLECTIONS-433" dev="tn" type="fix" due-to="Jeffrey Barnes">
+ Improve performance of "TreeList#addAll" and "TreeList(Collection)" by converting
+ the input collection into an AVL tree and efficiently merge it into the existing tree.
+ </action>
<action issue="COLLECTIONS-296" dev="tn" type="add" due-to="Julius Davies">
Added methods "CollectionUtils#merge(...)" to merge two sorted Collections
into a sorted List using the standard O(n) merge algorithm.
Modified: commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/list/TreeList.java
URL: http://svn.apache.org/viewvc/commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/list/TreeList.java?rev=1470159&r1=1470158&r2=1470159&view=diff
==============================================================================
--- commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/list/TreeList.java (original)
+++ commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/list/TreeList.java Sat Apr 20 13:11:14 2013
@@ -23,6 +23,7 @@ import java.util.Iterator;
import java.util.ListIterator;
import java.util.NoSuchElementException;
+import org.apache.commons.collections4.ArrayStack;
import org.apache.commons.collections4.OrderedIterator;
/**
@@ -53,6 +54,7 @@ import org.apache.commons.collections4.O
* @since 3.1
* @version $Id$
*/
+@SuppressWarnings("deprecation") // replace ArrayStack by ArrayDeque when moving to Java 1.6
public class TreeList<E> extends AbstractList<E> {
// add; toArray; iterator; insert; get; indexOf; remove
// TreeList = 1260;7360;3080; 160; 170;3400; 170;
@@ -74,14 +76,17 @@ public class TreeList<E> extends Abstrac
}
/**
- * Constructs a new empty list that copies the specified list.
+ * Constructs a new empty list that copies the specified collection.
*
* @param coll the collection to copy
* @throws NullPointerException if the collection is null
*/
public TreeList(final Collection<E> coll) {
super();
- addAll(coll);
+ if (!coll.isEmpty()) {
+ root = new AVLNode<E>(coll);
+ size = coll.size();
+ }
}
//-----------------------------------------------------------------------
@@ -204,6 +209,29 @@ public class TreeList<E> extends Abstrac
}
/**
+ * Appends all of the elements in the specified collection to the end of this list,
+ * in the order that they are returned by the specified collection's Iterator.
+ * <p>
+ * This method runs in O(n + log m) time, where m is
+ * the size of this list and n is the size of {@code c}.
+ *
+ * @param c the collection to be added to this list
+ * @return {@code true} if this list changed as a result of the call
+ * @throws NullPointerException {@inheritDoc}
+ */
+ @Override
+ public boolean addAll(final Collection<? extends E> c) {
+ if (c.isEmpty()) {
+ return false;
+ }
+ modCount += c.size();
+ final AVLNode<E> cTree = new AVLNode<E>(c);
+ root = root == null ? cTree : root.addAll(cTree, size);
+ size += c.size();
+ return true;
+ }
+
+ /**
* Sets the element at the specified index.
*
* @param index the index to set
@@ -294,7 +322,7 @@ public class TreeList<E> extends Abstrac
* Constructs a new node with a relative position.
*
* @param relativePosition the relative position of the node
- * @param obj the value for the ndoe
+ * @param obj the value for the node
* @param rightFollower the node with the value following this one
* @param leftFollower the node with the value leading this one
*/
@@ -309,6 +337,58 @@ public class TreeList<E> extends Abstrac
}
/**
+ * Constructs a new AVL tree from a collection.
+ * <p>
+ * The collection must be nonempty.
+ *
+ * @param coll a nonempty collection
+ */
+ private AVLNode(final Collection<? extends E> coll) {
+ this(coll.iterator(), 0, coll.size() - 1, 0, null, null);
+ }
+
+ /**
+ * Constructs a new AVL tree from a collection.
+ * <p>
+ * This is a recursive helper for {@link #AVLNode(Collection)}. A call
+ * to this method will construct the subtree for elements {@code start}
+ * through {@code end} of the collection, assuming the iterator
+ * {@code e} already points at element {@code start}.
+ *
+ * @param iterator an iterator over the collection, which should already point
+ * to the element at index {@code start} within the collection
+ * @param start the index of the first element in the collection that
+ * should be in this subtree
+ * @param end the index of the last element in the collection that
+ * should be in this subtree
+ * @param absolutePositionOfParent absolute position of this node's
+ * parent, or 0 if this node is the root
+ * @param prev the {@code AVLNode} corresponding to element (start - 1)
+ * of the collection, or null if start is 0
+ * @param next the {@code AVLNode} corresponding to element (end + 1)
+ * of the collection, or null if end is the last element of the collection
+ */
+ private AVLNode(final Iterator<? extends E> iterator, final int start, final int end,
+ final int absolutePositionOfParent, final AVLNode<E> prev, final AVLNode<E> next) {
+ final int mid = start + (end - start) / 2;
+ if (start < mid) {
+ left = new AVLNode<E>(iterator, start, mid - 1, mid, prev, this);
+ } else {
+ leftIsPrevious = true;
+ left = prev;
+ }
+ value = iterator.next();
+ relativePosition = mid - absolutePositionOfParent;
+ if (mid < end) {
+ right = new AVLNode<E>(iterator, mid + 1, end, mid, this, next);
+ } else {
+ rightIsNext = true;
+ right = next;
+ }
+ recalcHeight();
+ }
+
+ /**
* Gets the value.
*
* @return the value of this node
@@ -716,6 +796,119 @@ public class TreeList<E> extends Abstrac
recalcHeight();
}
+ /**
+ * Appends the elements of another tree list to this tree list by efficiently
+ * merging the two AVL trees. This operation is destructive to both trees and
+ * runs in O(log(m + n)) time.
+ *
+ * @param otherTree
+ * the root of the AVL tree to merge with this one
+ * @param currentSize
+ * the number of elements in this AVL tree
+ * @return the root of the new, merged AVL tree
+ */
+ private AVLNode<E> addAll(AVLNode<E> otherTree, final int currentSize) {
+ final AVLNode<E> maxNode = max();
+ final AVLNode<E> otherTreeMin = otherTree.min();
+
+ // We need to efficiently merge the two AVL trees while keeping them
+ // balanced (or nearly balanced). To do this, we take the shorter
+ // tree and combine it with a similar-height subtree of the taller
+ // tree. There are two symmetric cases:
+ // * this tree is taller, or
+ // * otherTree is taller.
+ if (otherTree.height > height) {
+ // CASE 1: The other tree is taller than this one. We will thus
+ // merge this tree into otherTree.
+
+ // STEP 1: Remove the maximum element from this tree.
+ final AVLNode<E> leftSubTree = removeMax();
+
+ // STEP 2: Navigate left from the root of otherTree until we
+ // find a subtree, s, that is no taller than me. (While we are
+ // navigating left, we store the nodes we encounter in a stack
+ // so that we can re-balance them in step 4.)
+ final ArrayStack<AVLNode<E>> sAncestors = new ArrayStack<AVLNode<E>>();
+ AVLNode<E> s = otherTree;
+ int sAbsolutePosition = s.relativePosition + currentSize;
+ int sParentAbsolutePosition = 0;
+ while (s != null && s.height > getHeight(leftSubTree)) {
+ sParentAbsolutePosition = sAbsolutePosition;
+ sAncestors.push(s);
+ s = s.left;
+ if (s != null) {
+ sAbsolutePosition += s.relativePosition;
+ }
+ }
+
+ // STEP 3: Replace s with a newly constructed subtree whose root
+ // is maxNode, whose left subtree is leftSubTree, and whose right
+ // subtree is s.
+ maxNode.setLeft(leftSubTree, null);
+ maxNode.setRight(s, otherTreeMin);
+ if (leftSubTree != null) {
+ leftSubTree.max().setRight(null, maxNode);
+ leftSubTree.relativePosition -= currentSize - 1;
+ }
+ if (s != null) {
+ s.min().setLeft(null, maxNode);
+ s.relativePosition = sAbsolutePosition - currentSize + 1;
+ }
+ maxNode.relativePosition = currentSize - 1 - sParentAbsolutePosition;
+ otherTree.relativePosition += currentSize;
+
+ // STEP 4: Re-balance the tree and recalculate the heights of s's ancestors.
+ s = maxNode;
+ while (!sAncestors.isEmpty()) {
+ final AVLNode<E> sAncestor = sAncestors.pop();
+ sAncestor.setLeft(s, null);
+ s = sAncestor.balance();
+ }
+ return s;
+ } else {
+ // CASE 2: This tree is taller. This is symmetric to case 1.
+ // We merge otherTree into this tree by finding a subtree s of this
+ // tree that is of similar height to otherTree and replacing it
+ // with a new subtree whose root is otherTreeMin and whose
+ // children are otherTree and s.
+
+ otherTree = otherTree.removeMin();
+
+ final ArrayStack<AVLNode<E>> sAncestors = new ArrayStack<AVLNode<E>>();
+ AVLNode<E> s = this;
+ int sAbsolutePosition = s.relativePosition;
+ int sParentAbsolutePosition = 0;
+ while (s != null && s.height > getHeight(otherTree)) {
+ sParentAbsolutePosition = sAbsolutePosition;
+ sAncestors.push(s);
+ s = s.right;
+ if (s != null) {
+ sAbsolutePosition += s.relativePosition;
+ }
+ }
+
+ otherTreeMin.setRight(otherTree, null);
+ otherTreeMin.setLeft(s, maxNode);
+ if (otherTree != null) {
+ otherTree.min().setLeft(null, otherTreeMin);
+ otherTree.relativePosition++;
+ }
+ if (s != null) {
+ s.max().setRight(null, otherTreeMin);
+ s.relativePosition = sAbsolutePosition - currentSize;
+ }
+ otherTreeMin.relativePosition = currentSize - sParentAbsolutePosition;
+
+ s = otherTreeMin;
+ while (!sAncestors.isEmpty()) {
+ final AVLNode<E> sAncestor = sAncestors.pop();
+ sAncestor.setRight(s, null);
+ s = sAncestor.balance();
+ }
+ return s;
+ }
+ }
+
// private void checkFaedelung() {
// AVLNode maxNode = left.max();
// if (!maxNode.rightIsFaedelung || maxNode.right != this) {
Modified: commons/proper/collections/trunk/src/test/java/org/apache/commons/collections4/list/TreeListTest.java
URL: http://svn.apache.org/viewvc/commons/proper/collections/trunk/src/test/java/org/apache/commons/collections4/list/TreeListTest.java?rev=1470159&r1=1470158&r2=1470159&view=diff
==============================================================================
--- commons/proper/collections/trunk/src/test/java/org/apache/commons/collections4/list/TreeListTest.java (original)
+++ commons/proper/collections/trunk/src/test/java/org/apache/commons/collections4/list/TreeListTest.java Sat Apr 20 13:11:14 2013
@@ -16,6 +16,7 @@
*/
package org.apache.commons.collections4.list;
+import java.util.ArrayList;
import java.util.List;
import java.util.ListIterator;
@@ -265,6 +266,66 @@ public class TreeListTest<E> extends Abs
// previous() after remove() should move to
// the element before the one just removed
assertEquals("A", li.previous());
- }
+ }
+
+ public void testIterationOrder() {
+ // COLLECTIONS-433:
+ // ensure that the iteration order of elements is correct
+ // when initializing the TreeList with another collection
+
+ for (int size = 1; size < 1000; size++) {
+ List<Integer> other = new ArrayList<Integer>(size);
+ for (int i = 0; i < size; i++) {
+ other.add(i);
+ }
+ TreeList<Integer> l = new TreeList<Integer>(other);
+ ListIterator<Integer> it = l.listIterator();
+ int i = 0;
+ while (it.hasNext()) {
+ Integer val = it.next();
+ assertEquals(i++, val.intValue());
+ }
+
+ while (it.hasPrevious()) {
+ Integer val = it.previous();
+ assertEquals(--i, val.intValue());
+ }
+ }
+ }
+
+ public void testIterationOrderAfterAddAll() {
+ // COLLECTIONS-433:
+ // ensure that the iteration order of elements is correct
+ // when calling addAll on the TreeList
+
+ // to simulate different cases in addAll, do different runs where
+ // the number of elements already in the list and being added by addAll differ
+
+ int size = 1000;
+ for (int i = 0; i < 100; i++) {
+ List<Integer> other = new ArrayList<Integer>(size);
+ for (int j = i; j < size; j++) {
+ other.add(j);
+ }
+ TreeList<Integer> l = new TreeList<Integer>();
+ for (int j = 0; j < i; j++) {
+ l.add(j);
+ }
+
+ l.addAll(other);
+
+ ListIterator<Integer> it = l.listIterator();
+ int cnt = 0;
+ while (it.hasNext()) {
+ Integer val = it.next();
+ assertEquals(cnt++, val.intValue());
+ }
+
+ while (it.hasPrevious()) {
+ Integer val = it.previous();
+ assertEquals(--cnt, val.intValue());
+ }
+ }
+ }
}