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 2013/04/17 21:32:35 UTC
svn commit: r1469039 - in /commons/proper/collections/trunk/src:
changes/changes.xml
main/java/org/apache/commons/collections4/CollectionUtils.java
Author: tn
Date: Wed Apr 17 19:32:34 2013
New Revision: 1469039
URL: http://svn.apache.org/r1469039
Log:
[COLLECTIONS-429] Improved CollectionUtils#containsAll with the version from the patch, added more javadoc with information on the runtime/space trade-off.
Modified:
commons/proper/collections/trunk/src/changes/changes.xml
commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/CollectionUtils.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=1469039&r1=1469038&r2=1469039&view=diff
==============================================================================
--- commons/proper/collections/trunk/src/changes/changes.xml (original)
+++ commons/proper/collections/trunk/src/changes/changes.xml Wed Apr 17 19:32:34 2013
@@ -22,6 +22,12 @@
<body>
<release version="4.0" date="TBA" description="Next release">
+ <action issue="COLLECTIONS-429,COLLECTION-434" dev="tn" type="add" due-to="Adrian Nistor, Mert Guldur">
+ Added method "CollectionUtils#containsAll(Collection, Collection)" with guaranteed
+ runtime complexity of O(n + m) and space complexity of O(n). This method may yield much
+ better performance than "Collection#containsAll(Collection)" depending on the use-case and
+ type of collection used.
+ </action>
<action issue="COLLECTIONS-285" dev="tn" type="add" due-to="Christian Gruenberg">
Added serialization support for "TreeBidiMap".
</action>
Modified: commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/CollectionUtils.java
URL: http://svn.apache.org/viewvc/commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/CollectionUtils.java?rev=1469039&r1=1469038&r2=1469039&view=diff
==============================================================================
--- commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/CollectionUtils.java (original)
+++ commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/CollectionUtils.java Wed Apr 17 19:32:34 2013
@@ -105,23 +105,6 @@ public class CollectionUtils {
return getFreq(obj, cardinalityB);
}
- /**
- * Returns the number of unique elements in collection A.
- * @return the number of unique elements in collection A
- */
- @SuppressWarnings("unused")
- public int sizeA() {
- return cardinalityA.size();
- }
-
- /**
- * Returns the number of unique elements in collection A.
- * @return the number of unique elements in collection A
- */
- public int sizeB() {
- return cardinalityB.size();
- }
-
private final int getFreq(final Object obj, final Map<?, Integer> freqMap) {
final Integer count = freqMap.get(obj);
if (count != null) {
@@ -366,9 +349,10 @@ public class CollectionUtils {
* will be returned.
* <p>
* This method is intended as a replacement for {@link Collection#containsAll(Collection)}
- * with a guaranteed runtime complexity of {@code O(n)}. Depending on the type of
+ * with a guaranteed runtime complexity of {@code O(n + m)}. Depending on the type of
* {@link Collection} provided, this method will be much faster than calling
- * {@link Collection#containsAll(Collection)} instead.
+ * {@link Collection#containsAll(Collection)} instead, though this will come at the
+ * cost of an additional space complexity O(n).
*
* @param coll1 the first collection, must not be null
* @param coll2 the second collection, must not be null
@@ -380,12 +364,30 @@ public class CollectionUtils {
if (coll2.isEmpty()) {
return true;
} else {
- final SetOperationCardinalityHelper<Object> helper =
- new SetOperationCardinalityHelper<Object>(coll1, coll2);
- for (final Object obj : helper) {
- helper.setCardinality(obj, helper.min(obj));
+ final Iterator<?> it = coll1.iterator();
+ final Set<Object> elementsAlreadySeen = new HashSet<Object>();
+ for (final Object nextElement : coll2) {
+ if (elementsAlreadySeen.contains(nextElement)) {
+ continue;
+ }
+
+ boolean foundCurrentElement = false;
+ while (it.hasNext()) {
+ final Object p = it.next();
+ elementsAlreadySeen.add(p);
+ if (nextElement == null ? p == null : nextElement.equals(p)) {
+ foundCurrentElement = true;
+ break;
+ }
+ }
+
+ if (foundCurrentElement) {
+ continue;
+ } else {
+ return false;
+ }
}
- return helper.list().size() == helper.sizeB();
+ return true;
}
}