commons-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From t.@apache.org
Subject 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
Date Sat, 20 Apr 2013 13:11:14 GMT
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());
+            }
+        }        
+    }
 
 }



Mime
View raw message