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");
+ // }
}
