You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@commons.apache.org by tn...@apache.org on 2012/06/23 13:31:55 UTC
svn commit: r1353111 -
/commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/CollectionUtils.java
Author: tn
Date: Sat Jun 23 11:31:54 2012
New Revision: 1353111
URL: http://svn.apache.org/viewvc?rev=1353111&view=rev
Log:
[COLLECTIONS-412] Improved performance of CollectionUtils#subtract. Thanks to Adrian Nistor for report and patch.
Modified:
commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/CollectionUtils.java
Modified: commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/CollectionUtils.java
URL: http://svn.apache.org/viewvc/commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/CollectionUtils.java?rev=1353111&r1=1353110&r2=1353111&view=diff
==============================================================================
--- commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/CollectionUtils.java (original)
+++ commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/CollectionUtils.java Sat Jun 23 11:31:54 2012
@@ -28,6 +28,7 @@ import java.util.ListIterator;
import java.util.Map;
import java.util.Set;
+import org.apache.commons.collections.bag.HashBag;
import org.apache.commons.collections.collection.PredicatedCollection;
import org.apache.commons.collections.collection.SynchronizedCollection;
import org.apache.commons.collections.collection.TransformedCollection;
@@ -245,6 +246,12 @@ public class CollectionUtils {
* Returns a new {@link Collection} containing <i>a</i> minus a subset of
* <i>b</i>. Only the elements of <i>b</i> that satisfy the predicate
* condition, <i>p</i> are subtracted from <i>a</i>.
+ *
+ * <p>The cardinality of each element <i>e</i> in the returned {@link Collection}
+ * that satisfies the predicate condition will be the cardinality of <i>e</i> in <i>a</i>
+ * minus the cardinality of <i>e</i> in <i>b</i>, or zero, whichever is greater.</p>
+ * <p>The cardinality of each element <i>e</i> in the returned {@link Collection} that does <b>not</b>
+ * satisfy the predicate condition will be equal to the cardinality of <i>e</i> in <i>a</i>.</p>
*
* @param a the collection to subtract from, must not be null
* @param b the collection to subtract, must not be null
@@ -256,12 +263,19 @@ public class CollectionUtils {
* @since 4.0
* @see Collection#removeAll
*/
- public static <O> Collection<O> subtract(final Iterable<? extends O> a, final Iterable<? extends O> b, final Predicate<O> p) {
- ArrayList<O> list = new ArrayList<O>();
- addAll(list, a);
+ public static <O> Collection<O> subtract(final Iterable<? extends O> a,
+ final Iterable<? extends O> b,
+ final Predicate<O> p) {
+ final ArrayList<O> list = new ArrayList<O>();
+ final HashBag<O> bag = new HashBag<O>();
for (O element : b) {
if (p.evaluate(element)) {
- list.remove(element);
+ bag.add(element);
+ }
+ }
+ for (O element : a) {
+ if (!bag.remove(element, 1)) {
+ list.add(element);
}
}
return list;