commons-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From brentwor...@apache.org
Subject svn commit: r1377491 - in /commons/proper/collections/trunk/src: changes/changes.xml main/java/org/apache/commons/collections/set/ListOrderedSet.java test/java/org/apache/commons/collections/set/ListOrderedSetTest.java
Date Sun, 26 Aug 2012 19:29:48 GMT
Author: brentworden
Date: Sun Aug 26 19:29:47 2012
New Revision: 1377491

URL: http://svn.apache.org/viewvc?rev=1377491&view=rev
Log:
COLLECTIONS-426 patch applied.

Modified:
    commons/proper/collections/trunk/src/changes/changes.xml
    commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/set/ListOrderedSet.java
    commons/proper/collections/trunk/src/test/java/org/apache/commons/collections/set/ListOrderedSetTest.java

Modified: commons/proper/collections/trunk/src/changes/changes.xml
URL: http://svn.apache.org/viewvc/commons/proper/collections/trunk/src/changes/changes.xml?rev=1377491&r1=1377490&r2=1377491&view=diff
==============================================================================
--- commons/proper/collections/trunk/src/changes/changes.xml (original)
+++ commons/proper/collections/trunk/src/changes/changes.xml Sun Aug 26 19:29:47 2012
@@ -78,6 +78,9 @@
     <action issue="COLLECTIONS-427" dev="brentworden" type="fix" due-to="Mert Guldur">
       Fixed performance issue in "SetUniqueList#retainAll" method for large collections.
     </action>
+    <action issue="COLLECTIONS-426" dev="brentworden" type="fix" due-to="Adrian Nistor">
+      Fixed performance issue in "ListOrderedSet#retainAll" method for large collections.
+    </action>
   </release>
   </body>
 </document>

Modified: commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/set/ListOrderedSet.java
URL: http://svn.apache.org/viewvc/commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/set/ListOrderedSet.java?rev=1377491&r1=1377490&r2=1377491&view=diff
==============================================================================
--- commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/set/ListOrderedSet.java
(original)
+++ commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/set/ListOrderedSet.java
Sun Aug 26 19:29:47 2012
@@ -29,27 +29,30 @@ import org.apache.commons.collections.it
 import org.apache.commons.collections.list.UnmodifiableList;
 
 /**
- * Decorates another <code>Set</code> to ensure that the order of addition
- * is retained and used by the iterator.
+ * Decorates another <code>Set</code> to ensure that the order of addition is
+ * retained and used by the iterator.
  * <p>
  * If an object is added to the set for a second time, it will remain in the
- * original position in the iteration.
- * The order can be observed from the set via the iterator or toArray methods.
+ * original position in the iteration. The order can be observed from the set
+ * via the iterator or toArray methods.
  * <p>
  * The ListOrderedSet also has various useful direct methods. These include many
- * from <code>List</code>, such as <code>get(int)</code>, <code>remove(int)</code>
- * and <code>indexOf(int)</code>. An unmodifiable <code>List</code>
view of
- * the set can be obtained via <code>asList()</code>.
+ * from <code>List</code>, such as <code>get(int)</code>,
+ * <code>remove(int)</code> and <code>indexOf(int)</code>. An unmodifiable
+ * <code>List</code> view of the set can be obtained via <code>asList()</code>.
  * <p>
  * This class cannot implement the <code>List</code> interface directly as
- * various interface methods (notably equals/hashCode) are incompatible with a set.
+ * various interface methods (notably equals/hashCode) are incompatible with a
+ * set.
  * <p>
  * This class is Serializable from Commons Collections 3.1.
- *
+ * 
  * @since 3.0
  * @version $Id$
  */
-public class ListOrderedSet<E> extends AbstractSerializableSetDecorator<E> implements
Set<E> {
+public class ListOrderedSet<E>
+    extends AbstractSerializableSetDecorator<E>
+    implements Set<E> {
 
     /** Serialization version */
     private static final long serialVersionUID = -228664372470420141L;
@@ -58,13 +61,14 @@ public class ListOrderedSet<E> extends A
     protected final List<E> setOrder;
 
     /**
-     * Factory method to create an ordered set specifying the list and set to use.
+     * Factory method to create an ordered set specifying the list and set to
+     * use.
      * <p>
      * The list and set must both be empty.
-     *
+     * 
      * @param <E> the element type
-     * @param set  the set to decorate, must be empty and not null
-     * @param list  the list to decorate, must be empty and not null
+     * @param set the set to decorate, must be empty and not null
+     * @param list the list to decorate, must be empty and not null
      * @return a new ordered set
      * @throws IllegalArgumentException if set or list is null
      * @throws IllegalArgumentException if either the set or list is not empty
@@ -87,9 +91,9 @@ public class ListOrderedSet<E> extends A
      * Factory method to create an ordered set.
      * <p>
      * An <code>ArrayList</code> is used to retain order.
-     *
+     * 
      * @param <E> the element type
-     * @param set  the set to decorate, must not be null
+     * @param set the set to decorate, must not be null
      * @return a new ordered set
      * @throws IllegalArgumentException if set is null
      */
@@ -98,15 +102,16 @@ public class ListOrderedSet<E> extends A
     }
 
     /**
-     * Factory method to create an ordered set using the supplied list to retain order.
+     * Factory method to create an ordered set using the supplied list to retain
+     * order.
      * <p>
      * A <code>HashSet</code> is used for the set behaviour.
      * <p>
      * NOTE: If the list contains duplicates, the duplicates are removed,
      * altering the specified list.
-     *
+     * 
      * @param <E> the element type
-     * @param list  the list to decorate, must not be null
+     * @param list the list to decorate, must not be null
      * @return a new ordered set
      * @throws IllegalArgumentException if list is null
      */
@@ -120,11 +125,11 @@ public class ListOrderedSet<E> extends A
         return new ListOrderedSet<E>(set, list);
     }
 
-    //-----------------------------------------------------------------------
+    // -----------------------------------------------------------------------
     /**
-     * Constructs a new empty <code>ListOrderedSet</code> using
-     * a <code>HashSet</code> and an <code>ArrayList</code> internally.
-     *
+     * Constructs a new empty <code>ListOrderedSet</code> using a
+     * <code>HashSet</code> and an <code>ArrayList</code> internally.
+     * 
      * @since 3.1
      */
     public ListOrderedSet() {
@@ -134,8 +139,8 @@ public class ListOrderedSet<E> extends A
 
     /**
      * Constructor that wraps (not copies).
-     *
-     * @param set  the set to decorate, must not be null
+     * 
+     * @param set the set to decorate, must not be null
      * @throws IllegalArgumentException if set is null
      */
     protected ListOrderedSet(Set<E> set) {
@@ -144,12 +149,13 @@ public class ListOrderedSet<E> extends A
     }
 
     /**
-     * Constructor that wraps (not copies) the Set and specifies the list to use.
+     * Constructor that wraps (not copies) the Set and specifies the list to
+     * use.
      * <p>
      * The set and list must both be correctly initialised to the same elements.
-     *
-     * @param set  the set to decorate, must not be null
-     * @param list  the list to decorate, must not be null
+     * 
+     * @param set the set to decorate, must not be null
+     * @param list the list to decorate, must not be null
      * @throws IllegalArgumentException if set or list is null
      */
     protected ListOrderedSet(Set<E> set, List<E> list) {
@@ -160,17 +166,17 @@ public class ListOrderedSet<E> extends A
         setOrder = list;
     }
 
-    //-----------------------------------------------------------------------
+    // -----------------------------------------------------------------------
     /**
      * Gets an unmodifiable view of the order of the Set.
-     *
+     * 
      * @return an unmodifiable list view
      */
     public List<E> asList() {
         return UnmodifiableList.unmodifiableList(setOrder);
     }
 
-    //-----------------------------------------------------------------------
+    // -----------------------------------------------------------------------
     @Override
     public void clear() {
         collection.clear();
@@ -220,20 +226,26 @@ public class ListOrderedSet<E> extends A
 
     @Override
     public boolean retainAll(Collection<?> coll) {
-        boolean result = collection.retainAll(coll);
-        if (result == false) {
+        Set<Object> collectionRetainAll = new HashSet<Object>();
+        for (Iterator<?> it = coll.iterator(); it.hasNext();) {
+            Object next = it.next();
+            if (collection.contains(next)) {
+                collectionRetainAll.add(next);
+            }
+        }
+        if (collectionRetainAll.size() == collection.size()) {
             return false;
         }
-        if (collection.size() == 0) {
-            setOrder.clear();
+        if (collectionRetainAll.size() == 0) {
+            clear();
         } else {
-            for (Iterator<E> it = setOrder.iterator(); it.hasNext();) {
-                if (!collection.contains(it.next())) {
+            for (Iterator<E> it = iterator(); it.hasNext();) {
+                if (!collectionRetainAll.contains(it.next())) {
                     it.remove();
                 }
             }
         }
-        return result;
+        return true;
     }
 
     @Override
@@ -246,13 +258,13 @@ public class ListOrderedSet<E> extends A
         return setOrder.toArray(a);
     }
 
-    //-----------------------------------------------------------------------
+    // -----------------------------------------------------------------------
     // Additional methods that comply to the {@link List} interface
-    //-----------------------------------------------------------------------
-    
+    // -----------------------------------------------------------------------
+
     /**
      * Returns the element at the specified position in this ordered set.
-     *
+     * 
      * @param index the position of the element in the ordered {@link Set}.
      * @return the element at position {@code index}
      * @see List#get(int)
@@ -262,11 +274,12 @@ public class ListOrderedSet<E> extends A
     }
 
     /**
-     * Returns the index of the first occurrence of the specified element in ordered set.
+     * Returns the index of the first occurrence of the specified element in
+     * ordered set.
      * 
      * @param object the element to search for
-     * @return the index of the first occurrence of the object, or {@code -1} if this
-     * ordered set does not contain this object
+     * @return the index of the first occurrence of the object, or {@code -1} if
+     *         this ordered set does not contain this object
      * @see List#indexOf(Object)
      */
     public int indexOf(Object object) {
@@ -274,10 +287,10 @@ public class ListOrderedSet<E> extends A
     }
 
     /**
-     * Inserts the specified element at the specified position if it is not yet contained
in this
-     * ordered set (optional operation). Shifts the element currently at this position and
any
-     * subsequent elements to the right.
-     *
+     * Inserts the specified element at the specified position if it is not yet
+     * contained in this ordered set (optional operation). Shifts the element
+     * currently at this position and any subsequent elements to the right.
+     * 
      * @param index the index at which the element is to be inserted
      * @param object the element to be inserted
      * @see List#add(int, Object)
@@ -290,9 +303,10 @@ public class ListOrderedSet<E> extends A
     }
 
     /**
-     * Inserts all elements in the specified collection not yet contained in the ordered
set at the specified
-     * position (optional operation). Shifts the element currently at the position and all
subsequent
-     * elements to the right.
+     * Inserts all elements in the specified collection not yet contained in the
+     * ordered set at the specified position (optional operation). Shifts the
+     * element currently at the position and all subsequent elements to the
+     * right.
      * 
      * @param index the position to insert the elements
      * @param coll the collection containing the elements to be inserted
@@ -311,7 +325,7 @@ public class ListOrderedSet<E> extends A
             toAdd.add(e);
             changed = true;
         }
-        
+
         if (changed) {
             setOrder.addAll(index, toAdd);
         }
@@ -320,8 +334,8 @@ public class ListOrderedSet<E> extends A
     }
 
     /**
-     * Removes the element at the specified position from the ordered set. Shifts any subsequent
-     * elements to the left.
+     * Removes the element at the specified position from the ordered set.
+     * Shifts any subsequent elements to the left.
      * 
      * @param index the index of the element to be removed
      * @return the element that has been remove from the ordered set
@@ -334,9 +348,9 @@ public class ListOrderedSet<E> extends A
     }
 
     /**
-     * Uses the underlying List's toString so that order is achieved.
-     * This means that the decorated Set's toString is not used, so
-     * any custom toStrings will be ignored.
+     * Uses the underlying List's toString so that order is achieved. This means
+     * that the decorated Set's toString is not used, so any custom toStrings
+     * will be ignored.
      * 
      * @return a string representation of the ordered set
      */
@@ -346,11 +360,13 @@ public class ListOrderedSet<E> extends A
         return setOrder.toString();
     }
 
-    //-----------------------------------------------------------------------
+    // -----------------------------------------------------------------------
     /**
      * Internal iterator handle remove.
      */
-    static class OrderedSetIterator<E> extends AbstractIteratorDecorator<E> implements
OrderedIterator<E> {
+    static class OrderedSetIterator<E>
+        extends AbstractIteratorDecorator<E>
+        implements OrderedIterator<E> {
 
         /** Object we iterate on */
         protected final Collection<E> set;

Modified: commons/proper/collections/trunk/src/test/java/org/apache/commons/collections/set/ListOrderedSetTest.java
URL: http://svn.apache.org/viewvc/commons/proper/collections/trunk/src/test/java/org/apache/commons/collections/set/ListOrderedSetTest.java?rev=1377491&r1=1377490&r2=1377491&view=diff
==============================================================================
--- commons/proper/collections/trunk/src/test/java/org/apache/commons/collections/set/ListOrderedSetTest.java
(original)
+++ commons/proper/collections/trunk/src/test/java/org/apache/commons/collections/set/ListOrderedSetTest.java
Sun Aug 26 19:29:47 2012
@@ -17,23 +17,28 @@
 package org.apache.commons.collections.set;
 
 import java.util.ArrayList;
+import java.util.Collection;
 import java.util.HashSet;
 import java.util.Iterator;
 import java.util.List;
 import java.util.Set;
 
 /**
- * Extension of {@link AbstractSetTest} for exercising the {@link ListOrderedSet}
- * implementation.
- *
+ * Extension of {@link AbstractSetTest} for exercising the
+ * {@link ListOrderedSet} implementation.
+ * 
  * @since 3.0
  * @version $Id$
  */
-public class ListOrderedSetTest<E> extends AbstractSetTest<E> {
+public class ListOrderedSetTest<E>
+    extends AbstractSetTest<E> {
 
     private static final Integer ZERO = new Integer(0);
+
     private static final Integer ONE = new Integer(1);
+
     private static final Integer TWO = new Integer(2);
+
     private static final Integer THREE = new Integer(3);
 
     public ListOrderedSetTest(String testName) {
@@ -65,12 +70,14 @@ public class ListOrderedSetTest<E> exten
         }
 
         for (int i = 0; i < 10; i += 2) {
-            assertTrue("Must be able to remove int", set.remove(Integer.toString(i)));
+            assertTrue("Must be able to remove int",
+                       set.remove(Integer.toString(i)));
         }
 
         it = set.iterator();
         for (int i = 1; i < 10; i += 2) {
-            assertEquals("Sequence is wrong after remove ", Integer.toString(i), it.next());
+            assertEquals("Sequence is wrong after remove ",
+                         Integer.toString(i), it.next());
         }
 
         for (int i = 0; i < 10; i++) {
@@ -147,7 +154,7 @@ public class ListOrderedSetTest<E> exten
         assertSame(TWO, set.get(2));
 
         list.add(0, (E) THREE); // list = [3,0,2]
-        set.remove(TWO);    //  set = [0,1]
+        set.remove(TWO); //  set = [0,1]
         set.addAll(1, list);
         assertEquals(4, set.size());
         assertSame(ZERO, set.get(0));
@@ -163,7 +170,7 @@ public class ListOrderedSetTest<E> exten
         B b = new B();
         set.add((E) a);
         assertEquals(1, set.size());
-        set.add((E) b);  // will match but not replace A as equal
+        set.add((E) b); // will match but not replace A as equal
         assertEquals(1, set.size());
         assertSame(a, set.decorated().iterator().next());
         assertSame(a, set.iterator().next());
@@ -171,11 +178,61 @@ public class ListOrderedSetTest<E> exten
         assertSame(a, set.asList().get(0));
     }
 
+    @SuppressWarnings("unchecked")
+    public void testRetainAll() {
+        List<E> list = new ArrayList<E>(10);
+        Set<E> set = new HashSet<E>(10);
+        ListOrderedSet<E> orderedSet = ListOrderedSet.listOrderedSet(set, list);
+        for (int i = 0; i < 10; ++i) {
+            orderedSet.add((E) Integer.valueOf(10 - i - 1));
+        }
+
+        Collection<E> retained = new ArrayList<E>(5);
+        for (int i = 0; i < 5; ++i) {
+            retained.add((E) Integer.valueOf(i * 2));
+        }
+
+        assertTrue(orderedSet.retainAll(retained));
+        assertEquals(5, orderedSet.size());
+        // insertion order preserved?
+        assertEquals(Integer.valueOf(8), orderedSet.get(0));
+        assertEquals(Integer.valueOf(6), orderedSet.get(1));
+        assertEquals(Integer.valueOf(4), orderedSet.get(2));
+        assertEquals(Integer.valueOf(2), orderedSet.get(3));
+        assertEquals(Integer.valueOf(0), orderedSet.get(4));
+    }
+
+    /*
+     * test case for https://issues.apache.org/jira/browse/COLLECTIONS-426
+     */
+    public void testRetainAllCollections426() {
+        int size = 100000;
+        ListOrderedSet<Integer> set = new ListOrderedSet<Integer>();
+        for (int i = 0; i < size; i++) {
+            set.add(i);
+        }
+        ArrayList<Integer> list = new ArrayList<Integer>();
+        for (int i = size; i < 2 * size; i++) {
+            list.add(i);
+        }
+
+        long start = System.currentTimeMillis();
+        set.retainAll(list);
+        long stop = System.currentTimeMillis();
+
+        // make sure retainAll completes under 5 seconds
+        // TODO if test is migrated to JUnit 4, add a Timeout rule.
+        // http://kentbeck.github.com/junit/javadoc/latest/org/junit/rules/Timeout.html
+        assertTrue((stop - start) < 5000);
+    }
+
     static class A {
+
         @Override
         public boolean equals(Object obj) {
             return (obj instanceof A || obj instanceof B);
         }
+
         @Override
         public int hashCode() {
             return 1;
@@ -183,10 +240,12 @@ public class ListOrderedSetTest<E> exten
     }
 
     static class B {
+
         @Override
         public boolean equals(Object obj) {
             return (obj instanceof A || obj instanceof B);
         }
+
         @Override
         public int hashCode() {
             return 1;
@@ -197,23 +256,28 @@ public class ListOrderedSetTest<E> exten
         try {
             ListOrderedSet.listOrderedSet((List<E>) null);
             fail();
-        } catch (IllegalArgumentException ex) {}
+        } catch (IllegalArgumentException ex) {
+        }
         try {
             ListOrderedSet.listOrderedSet((Set<E>) null);
             fail();
-        } catch (IllegalArgumentException ex) {}
+        } catch (IllegalArgumentException ex) {
+        }
         try {
             ListOrderedSet.listOrderedSet(null, null);
             fail();
-        } catch (IllegalArgumentException ex) {}
+        } catch (IllegalArgumentException ex) {
+        }
         try {
             ListOrderedSet.listOrderedSet(new HashSet<E>(), null);
             fail();
-        } catch (IllegalArgumentException ex) {}
+        } catch (IllegalArgumentException ex) {
+        }
         try {
             ListOrderedSet.listOrderedSet(null, new ArrayList<E>());
             fail();
-        } catch (IllegalArgumentException ex) {}
+        } catch (IllegalArgumentException ex) {
+        }
     }
 
     @Override
@@ -221,11 +285,11 @@ public class ListOrderedSetTest<E> exten
         return "3.1";
     }
 
-//    public void testCreate() throws Exception {
-//        resetEmpty();
-//        writeExternalFormToDisk((java.io.Serializable) collection, "D:/dev/collections/data/test/ListOrderedSet.emptyCollection.version3.1.obj");
-//        resetFull();
-//        writeExternalFormToDisk((java.io.Serializable) collection, "D:/dev/collections/data/test/ListOrderedSet.fullCollection.version3.1.obj");
-//    }
+    //    public void testCreate() throws Exception {
+    //        resetEmpty();
+    //        writeExternalFormToDisk((java.io.Serializable) collection, "D:/dev/collections/data/test/ListOrderedSet.emptyCollection.version3.1.obj");
+    //        resetFull();
+    //        writeExternalFormToDisk((java.io.Serializable) collection, "D:/dev/collections/data/test/ListOrderedSet.fullCollection.version3.1.obj");
+    //    }
 
 }



Mime
View raw message