[commons-collections] 01/03: Update the AbstractBloomFilter to not use BitSet for cardinality.

[ah...@apache.org]

This is an automated email from the ASF dual-hosted git repository.

aherbert pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/commons-collections.git

commit 9a496dc61cee95257b3a266a4d52138bea7f7e9a
Author: Alex Herbert <ah...@apache.org>
AuthorDate: Mon Feb 24 23:01:39 2020 +0000

    Update the AbstractBloomFilter to not use BitSet for cardinality.
    
    The cardinality can be performed without memory allocation using
    Long.bitCount.
---
 .../bloomfilter/AbstractBloomFilter.java           | 78 +++++++++++-----------
 1 file changed, 39 insertions(+), 39 deletions(-)

diff --git a/src/main/java/org/apache/commons/collections4/bloomfilter/AbstractBloomFilter.java b/src/main/java/org/apache/commons/collections4/bloomfilter/AbstractBloomFilter.java
index e568bf5..9bbeb43 100644
--- a/src/main/java/org/apache/commons/collections4/bloomfilter/AbstractBloomFilter.java
+++ b/src/main/java/org/apache/commons/collections4/bloomfilter/AbstractBloomFilter.java
@@ -16,8 +16,8 @@
  */
 package org.apache.commons.collections4.bloomfilter;
 
-import java.util.BitSet;
 import java.util.PrimitiveIterator.OfInt;
+import java.util.function.LongBinaryOperator;
 
 import org.apache.commons.collections4.bloomfilter.hasher.HashFunctionIdentity;
 import org.apache.commons.collections4.bloomfilter.hasher.Hasher;
@@ -66,11 +66,11 @@ public abstract class AbstractBloomFilter implements BloomFilter {
         final long[] mine = getBits();
         final long[] theirs = other.getBits();
         final int limit = Integer.min(mine.length, theirs.length);
-        final long[] result = new long[limit];
+        int count = 0;
         for (int i = 0; i < limit; i++) {
-            result[i] = mine[i] & theirs[i];
+            count += Long.bitCount(mine[i] & theirs[i]);
         }
-        return BitSet.valueOf(result).cardinality();
+        return count;
     }
 
     /**
@@ -80,7 +80,11 @@ public abstract class AbstractBloomFilter implements BloomFilter {
      */
     @Override
     public int cardinality() {
-        return BitSet.valueOf(getBits()).cardinality();
+        int count = 0;
+        for (final long bits : getBits()) {
+            count += Long.bitCount(bits);
+        }
+        return count;
     }
 
     /**
@@ -182,27 +186,8 @@ public abstract class AbstractBloomFilter implements BloomFilter {
 
     @Override
     public int orCardinality(final BloomFilter other) {
-        verifyShape(other);
-        final long[] mine = getBits();
-        final long[] theirs = other.getBits();
-        long[] remainder = null;
-        long[] result = null;
-        if (mine.length > theirs.length) {
-            result = new long[mine.length];
-            remainder = mine;
-        } else {
-            result = new long[theirs.length];
-            remainder = theirs;
-
-        }
-        final int limit = Integer.min(mine.length, theirs.length);
-        for (int i = 0; i < limit; i++) {
-            result[i] = mine[i] | theirs[i];
-        }
-        if (limit < result.length) {
-            System.arraycopy(remainder, limit, result, limit, result.length - limit);
-        }
-        return BitSet.valueOf(result).cardinality();
+        // Logical OR
+        return opCardinality(other, (a, b) -> a | b);
     }
 
     /**
@@ -253,26 +238,41 @@ public abstract class AbstractBloomFilter implements BloomFilter {
      */
     @Override
     public int xorCardinality(final BloomFilter other) {
+        // Logical XOR
+        return opCardinality(other, (a, b) -> a ^ b);
+    }
+
+    /**
+     * Perform the operation on the matched longs from this filter and the other filter
+     * and count the cardinality.
+     *
+     * <p>The remaining unmatched longs from the larger filter are always counted. This
+     * method is suitable for OR and XOR cardinality.
+     *
+     * @param other the other Bloom filter.
+     * @param operation the operation (e.g. OR, XOR)
+     * @return the cardinality
+     */
+    private int opCardinality(final BloomFilter other, LongBinaryOperator operation) {
         verifyShape(other);
         final long[] mine = getBits();
         final long[] theirs = other.getBits();
-        long[] remainder = null;
-        long[] result = null;
+        long[] small;
+        long[] big;
         if (mine.length > theirs.length) {
-            result = new long[mine.length];
-            remainder = mine;
+            big = mine;
+            small = theirs;
         } else {
-            result = new long[theirs.length];
-            remainder = theirs;
-
+            small = mine;
+            big = theirs;
         }
-        final int limit = Integer.min(mine.length, theirs.length);
-        for (int i = 0; i < limit; i++) {
-            result[i] = mine[i] ^ theirs[i];
+        int count = 0;
+        for (int i = 0; i < small.length; i++) {
+            count += Long.bitCount(operation.applyAsLong(small[i], big[i]));
         }
-        if (limit < result.length) {
-            System.arraycopy(remainder, limit, result, limit, result.length - limit);
+        for (int i = small.length; i < big.length; i++) {
+            count += Long.bitCount(big[i]);
         }
-        return BitSet.valueOf(result).cardinality();
+        return count;
     }
 }