Author: tn
Date: Sun Jun 3 10:22:04 2012
New Revision: 1345644
URL: http://svn.apache.org/viewvc?rev=1345644&view=rev
Log:
[COLLECTIONS-406] Improved ListUtils.subtract to O(n) performance. Thanks to
Adrian Nistor for reporting and providing a patch.
Modified:
commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/ListUtils.java
commons/proper/collections/trunk/src/test/java/org/apache/commons/collections/TestListUtils.java
Modified:
commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/ListUtils.java
URL:
http://svn.apache.org/viewvc/commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/ListUtils.java?rev=1345644&r1=1345643&r2=1345644&view=diff
==============================================================================
---
commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/ListUtils.java
(original)
+++
commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/ListUtils.java
Sun Jun 3 10:22:04 2012
@@ -23,6 +23,7 @@ import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
+import org.apache.commons.collections.bag.HashBag;
import org.apache.commons.collections.list.FixedSizeList;
import org.apache.commons.collections.list.LazyList;
import org.apache.commons.collections.list.PredicatedList;
@@ -106,9 +107,12 @@ public class ListUtils {
* @throws NullPointerException if either list is null
*/
public static <E> List<E> subtract(final List<E> list1, final List<?
extends E> list2) {
- final ArrayList<E> result = new ArrayList<E>(list1);
- for (E e : list2) {
- result.remove(e);
+ final ArrayList<E> result = new ArrayList<E>();
+ final HashBag<E> bag = new HashBag<E>(list2);
+ for (final E e : list1) {
+ if (!bag.remove(e, 1)) {
+ result.add(e);
+ }
}
return result;
}
Modified:
commons/proper/collections/trunk/src/test/java/org/apache/commons/collections/TestListUtils.java
URL:
http://svn.apache.org/viewvc/commons/proper/collections/trunk/src/test/java/org/apache/commons/collections/TestListUtils.java?rev=1345644&r1=1345643&r2=1345644&view=diff
==============================================================================
---
commons/proper/collections/trunk/src/test/java/org/apache/commons/collections/TestListUtils.java
(original)
+++
commons/proper/collections/trunk/src/test/java/org/apache/commons/collections/TestListUtils.java
Sun Jun 3 10:22:04 2012
@@ -234,6 +234,53 @@ public class TestListUtils extends BulkT
} catch(NullPointerException npe) {} // this is what we want
}
+ public void testSubtract() {
+ List<String> list = new ArrayList<String>();
+ list.add(a);
+ list.add(b);
+ list.add(a);
+ list.add(x);
+
+ List<String> sub = new ArrayList<String>();
+ sub.add(a);
+
+ List<String> result = ListUtils.subtract(list, sub);
+ assertTrue(result.size() == 3);
+
+ List<String> expected = new ArrayList<String>();
+ expected.add(b);
+ expected.add(a);
+ expected.add(x);
+
+ assertEquals(expected, result);
+
+ try {
+ ListUtils.subtract(list, null);
+ fail("expecting NullPointerException");
+ } catch(NullPointerException npe) {} // this is what we want
+ }
+
+ public void testSubtractNullElement() {
+ List<String> list = new ArrayList<String>();
+ list.add(a);
+ list.add(null);
+ list.add(null);
+ list.add(x);
+
+ List<String> sub = new ArrayList<String>();
+ sub.add(null);
+
+ List<String> result = ListUtils.subtract(list, sub);
+ assertTrue(result.size() == 3);
+
+ List<String> expected = new ArrayList<String>();
+ expected.add(a);
+ expected.add(null);
+ expected.add(x);
+
+ assertEquals(expected, result);
+ }
+
/**
* Tests the <code>indexOf</code> method in <code>ListUtils</code> class..
*/
