commons-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From t.@apache.org
Subject svn commit: r1345644 - in /commons/proper/collections/trunk/src: main/java/org/apache/commons/collections/ListUtils.java test/java/org/apache/commons/collections/TestListUtils.java
Date Sun, 03 Jun 2012 10:22:04 GMT
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..
      */



Mime
View raw message