You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@commons.apache.org by ah...@apache.org on 2022/08/10 09:27:29 UTC
[commons-collections] branch master updated: Collections 827: Add tests using or, and and xor with different length filters. (#328)
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
The following commit(s) were added to refs/heads/master by this push:
new 2af77aaa6 Collections 827: Add tests using or, and and xor with different length filters. (#328)
2af77aaa6 is described below
commit 2af77aaa6b5c39af49f18e8c1014f8e7e3958753
Author: Claude Warren <cl...@apache.org>
AuthorDate: Wed Aug 10 10:27:24 2022 +0100
Collections 827: Add tests using or, and and xor with different length filters. (#328)
* added missing tests
* simplified test framework
---
.../bloomfilter/SetOperationsTest.java | 171 ++++++++++++---------
1 file changed, 99 insertions(+), 72 deletions(-)
diff --git a/src/test/java/org/apache/commons/collections4/bloomfilter/SetOperationsTest.java b/src/test/java/org/apache/commons/collections4/bloomfilter/SetOperationsTest.java
index f958cdcc9..890e22f8f 100644
--- a/src/test/java/org/apache/commons/collections4/bloomfilter/SetOperationsTest.java
+++ b/src/test/java/org/apache/commons/collections4/bloomfilter/SetOperationsTest.java
@@ -18,6 +18,9 @@ package org.apache.commons.collections4.bloomfilter;
import static org.junit.jupiter.api.Assertions.assertEquals;
+import java.util.function.ToDoubleBiFunction;
+import java.util.function.ToIntBiFunction;
+
import org.junit.jupiter.api.Test;
/**
@@ -33,6 +36,19 @@ public class SetOperationsTest {
protected final long bigHashValue = 0xFFFFFFEL;
private final Shape shape = Shape.fromKM(17, 72);
+
+ private static void assertSymmetricOperation(int expected, ToIntBiFunction<BloomFilter, BloomFilter> operation,
+ BloomFilter filter1, BloomFilter filter2) {
+ assertEquals(expected, operation.applyAsInt(filter1, filter2), "op(filter1, filter2)");
+ assertEquals(expected, operation.applyAsInt(filter2, filter1), "op(filter2, filter1)");
+ }
+
+ private static void assertSymmetricOperation(double expected, ToDoubleBiFunction<BloomFilter, BloomFilter> operation,
+ BloomFilter filter1, BloomFilter filter2) {
+ assertEquals(expected, operation.applyAsDouble(filter1, filter2), "op(filter1, filter2)");
+ assertEquals(expected, operation.applyAsDouble(filter2, filter1), "op(filter2, filter1)");
+ }
+
/**
* Tests that the Cosine similarity is correctly calculated.
*/
@@ -44,8 +60,7 @@ public class SetOperationsTest {
// identical filters should have no distance.
double expected = 0;
- assertEquals(expected, SetOperations.cosineDistance(filter1, filter2));
- assertEquals(expected, SetOperations.cosineDistance(filter2, filter1));
+ assertSymmetricOperation(expected, SetOperations::cosineDistance, filter1, filter2);
Shape shape2 = Shape.fromKM(2, 72);
filter1 = new SimpleBloomFilter(shape2, from1);
@@ -55,8 +70,7 @@ public class SetOperationsTest {
int cardinalityA = 2;
int cardinalityB = 2;
expected = 1 - (dotProduct / Math.sqrt(cardinalityA * cardinalityB));
- assertEquals(expected, SetOperations.cosineDistance(filter1, filter2));
- assertEquals(expected, SetOperations.cosineDistance(filter2, filter1));
+ assertSymmetricOperation(expected, SetOperations::cosineDistance, filter1, filter2);
filter1 = new SimpleBloomFilter(shape, from1);
filter2 = new SimpleBloomFilter(shape, from11);
@@ -64,8 +78,7 @@ public class SetOperationsTest {
cardinalityA = 17;
cardinalityB = 17;
expected = 1 - (dotProduct / Math.sqrt(cardinalityA * cardinalityB));
- assertEquals(expected, SetOperations.cosineDistance(filter1, filter2));
- assertEquals(expected, SetOperations.cosineDistance(filter2, filter1));
+ assertSymmetricOperation(expected, SetOperations::cosineDistance, filter1, filter2);
// test with no values
filter1 = new SimpleBloomFilter(shape, from1);
@@ -76,15 +89,13 @@ public class SetOperationsTest {
cardinalityA = 2;
cardinalityB = 0;
expected = /* 1 - (dotProduct/Math.sqrt( cardinalityA * cardinalityB )) = */ 1.0;
- assertEquals(expected, SetOperations.cosineDistance(filter1, filter2));
- assertEquals(expected, SetOperations.cosineDistance(filter2, filter1));
+ assertSymmetricOperation(expected, SetOperations::cosineDistance, filter1, filter2);
dotProduct = /* [] & [] = [] = */ 0;
cardinalityA = 0;
cardinalityB = 0;
expected = /* 1 - (dotProduct/Math.sqrt( cardinalityA * cardinalityB )) = */ 1.0;
- assertEquals(1.0, SetOperations.cosineDistance(filter2, filter3));
- assertEquals(1.0, SetOperations.cosineDistance(filter3, filter2));
+ assertSymmetricOperation(expected, SetOperations::cosineDistance, filter1, filter2);
}
/**
@@ -99,27 +110,22 @@ public class SetOperationsTest {
int cardinalityA = 17;
int cardinalityB = 17;
double expected = /* dotProduct/Sqrt( cardinalityA * cardinalityB ) = */ 1.0;
- assertEquals(expected, SetOperations.cosineSimilarity(filter1, filter2));
- assertEquals(expected, SetOperations.cosineSimilarity(filter2, filter1));
+ assertSymmetricOperation(expected, SetOperations::cosineSimilarity, filter1, filter2);
dotProduct = /* [1..17] & [11..27] = [11..17] = */ 7;
cardinalityA = 17;
cardinalityB = 17;
expected = dotProduct / Math.sqrt(cardinalityA * cardinalityB);
filter2 = new SimpleBloomFilter(shape, from11);
- assertEquals(expected, SetOperations.cosineSimilarity(filter1, filter2));
- assertEquals(expected, SetOperations.cosineSimilarity(filter2, filter1));
+ assertSymmetricOperation(expected, SetOperations::cosineSimilarity, filter1, filter2);
// test no values
filter1 = new SimpleBloomFilter(shape);
filter2 = new SimpleBloomFilter(shape);
// build a filter
BloomFilter filter3 = new SimpleBloomFilter(shape, from1);
-
- assertEquals(0.0, SetOperations.cosineSimilarity(filter1, filter2));
- assertEquals(0.0, SetOperations.cosineSimilarity(filter2, filter1));
- assertEquals(0.0, SetOperations.cosineSimilarity(filter1, filter3));
- assertEquals(0.0, SetOperations.cosineSimilarity(filter3, filter1));
+ assertSymmetricOperation(0.0, SetOperations::cosineSimilarity, filter1, filter2);
+ assertSymmetricOperation(0.0, SetOperations::cosineSimilarity, filter1, filter3);
}
/**
@@ -131,13 +137,11 @@ public class SetOperationsTest {
BloomFilter filter2 = new SimpleBloomFilter(shape, from1);
int hammingDistance = /* [1..17] ^ [1..17] = [] = */ 0;
- assertEquals(hammingDistance, SetOperations.hammingDistance(filter1, filter2));
- assertEquals(hammingDistance, SetOperations.hammingDistance(filter2, filter1));
+ assertSymmetricOperation(hammingDistance, SetOperations::hammingDistance, filter1, filter2);
filter2 = new SimpleBloomFilter(shape, from11);
hammingDistance = /* [1..17] ^ [11..27] = [1..10][17-27] = */ 20;
- assertEquals(hammingDistance, SetOperations.hammingDistance(filter1, filter2));
- assertEquals(hammingDistance, SetOperations.hammingDistance(filter2, filter1));
+ assertSymmetricOperation(hammingDistance, SetOperations::hammingDistance, filter1, filter2);
}
/**
@@ -149,15 +153,13 @@ public class SetOperationsTest {
BloomFilter filter2 = new SimpleBloomFilter(shape, from1);
// 1 - jaccardSimilarity -- see jaccardSimilarityTest
-
- assertEquals(0.0, SetOperations.jaccardDistance(filter1, filter2));
- assertEquals(0.0, SetOperations.jaccardDistance(filter2, filter1));
+ assertSymmetricOperation(0.0, SetOperations::jaccardDistance, filter1, filter2);
filter2 = new SimpleBloomFilter(shape, from11);
double intersection = /* [1..17] & [11..27] = [11..17] = */ 7.0;
int union = /* [1..17] | [11..27] = [1..27] = */ 27;
- assertEquals(1 - (intersection / union), SetOperations.jaccardDistance(filter1, filter2));
- assertEquals(1 - (intersection / union), SetOperations.jaccardDistance(filter2, filter1));
+ double expected = 1 - (intersection / union);
+ assertSymmetricOperation(expected, SetOperations::jaccardDistance, filter1, filter2);
// test no values
filter1 = new SimpleBloomFilter(shape);
@@ -165,10 +167,8 @@ public class SetOperationsTest {
BloomFilter filter3 = new SimpleBloomFilter(shape, from1);
// 1 - jaccardSimilarity -- see jaccardSimilarityTest
- assertEquals(1.0, SetOperations.jaccardDistance(filter1, filter2));
- assertEquals(1.0, SetOperations.jaccardDistance(filter2, filter1));
- assertEquals(1.0, SetOperations.jaccardDistance(filter1, filter3));
- assertEquals(1.0, SetOperations.jaccardDistance(filter3, filter1));
+ assertSymmetricOperation(1.0, SetOperations::jaccardDistance, filter1, filter2);
+ assertSymmetricOperation(1.0, SetOperations::jaccardDistance, filter1, filter3);
}
/**
@@ -181,28 +181,25 @@ public class SetOperationsTest {
double intersection = /* [1..17] & [1..17] = [1..17] = */ 17.0;
int union = /* [1..17] | [1..17] = [1..17] = */ 17;
-
- assertEquals(intersection / union, SetOperations.jaccardSimilarity(filter1, filter2));
- assertEquals(intersection / union, SetOperations.jaccardSimilarity(filter2, filter1));
+ double expected = intersection / union;
+ assertSymmetricOperation(expected, SetOperations::jaccardSimilarity, filter1, filter2);
filter2 = new SimpleBloomFilter(shape, from11);
intersection = /* [1..17] & [11..27] = [11..17] = */ 7.0;
union = /* [1..17] | [11..27] = [1..27] = */ 27;
- assertEquals(intersection / union, SetOperations.jaccardSimilarity(filter1, filter2));
- assertEquals(intersection / union, SetOperations.jaccardSimilarity(filter2, filter1));
+ expected = intersection / union;
+ assertSymmetricOperation(expected, SetOperations::jaccardSimilarity, filter1, filter2);
// test no values
filter1 = new SimpleBloomFilter(shape);
filter2 = new SimpleBloomFilter(shape);
BloomFilter filter3 = new SimpleBloomFilter(shape, from1);
-
- assertEquals(0.0, SetOperations.jaccardSimilarity(filter1, filter2));
- assertEquals(0.0, SetOperations.jaccardSimilarity(filter2, filter1));
+ assertSymmetricOperation(0.0, SetOperations::jaccardSimilarity, filter1, filter2);
intersection = /* [] & [1..17] = [] = */ 0.0;
union = /* [] | [1..17] = [] = */ 17;
- assertEquals(intersection / union, SetOperations.jaccardSimilarity(filter1, filter3));
- assertEquals(intersection / union, SetOperations.jaccardSimilarity(filter3, filter1));
+ expected = intersection / union;
+ assertSymmetricOperation(expected, SetOperations::jaccardSimilarity, filter1, filter2);
}
@Test
@@ -210,24 +207,32 @@ public class SetOperationsTest {
Shape shape = Shape.fromKM(3, 128);
SparseBloomFilter filter1 = new SparseBloomFilter(shape, IndexProducer.fromIndexArray(new int[] { 1, 63, 64 }));
SparseBloomFilter filter2 = new SparseBloomFilter(shape, IndexProducer.fromIndexArray(new int[] { 5, 64, 69 }));
- assertEquals(5, SetOperations.orCardinality(filter1, filter2));
- assertEquals(5, SetOperations.orCardinality(filter2, filter1));
+ assertSymmetricOperation(5, SetOperations::orCardinality, filter1, filter2);
filter1 = new SparseBloomFilter(shape, IndexProducer.fromIndexArray(new int[] { 1, 63 }));
filter2 = new SparseBloomFilter(shape, IndexProducer.fromIndexArray(new int[] { 5, 64, 69 }));
- assertEquals(5, SetOperations.orCardinality(filter1, filter2));
- assertEquals(5, SetOperations.orCardinality(filter2, filter1));
+ assertSymmetricOperation(5, SetOperations::orCardinality, filter1, filter2);
filter1 = new SparseBloomFilter(shape, IndexProducer.fromIndexArray(new int[] { 5, 63 }));
filter2 = new SparseBloomFilter(shape, IndexProducer.fromIndexArray(new int[] { 5, 64, 69 }));
- assertEquals(4, SetOperations.orCardinality(filter1, filter2));
- assertEquals(4, SetOperations.orCardinality(filter2, filter1));
+ assertSymmetricOperation(4, SetOperations::orCardinality, filter1, filter2);
+ }
- Shape bigShape = Shape.fromKM(3, 192);
- filter1 = new SparseBloomFilter(bigShape, IndexProducer.fromIndexArray(new int[] { 1, 63, 185}));
- filter2 = new SparseBloomFilter(shape, IndexProducer.fromIndexArray(new int[] { 5, 63, 69 }));
- assertEquals(5, SetOperations.orCardinality(filter1, filter2));
- assertEquals(5, SetOperations.orCardinality(filter2, filter1));
+ @Test
+ public final void testOrCardinalityWithDifferentLengthFilters() {
+ Shape shape = Shape.fromKM(3, 128);
+ Shape shape2 = Shape.fromKM(3, 192);
+ SparseBloomFilter filter1 = new SparseBloomFilter(shape, IndexProducer.fromIndexArray(new int[] { 1, 63, 64 }));
+ SparseBloomFilter filter2 = new SparseBloomFilter(shape2, IndexProducer.fromIndexArray(new int[] { 5, 64, 169 }));
+ assertSymmetricOperation(5, SetOperations::orCardinality, filter1, filter2);
+
+ filter1 = new SparseBloomFilter(shape, IndexProducer.fromIndexArray(new int[] { 1, 63 }));
+ filter2 = new SparseBloomFilter(shape2, IndexProducer.fromIndexArray(new int[] { 5, 64, 169 }));
+ assertSymmetricOperation(5, SetOperations::orCardinality, filter1, filter2);
+
+ filter1 = new SparseBloomFilter(shape, IndexProducer.fromIndexArray(new int[] { 5, 63 }));
+ filter2 = new SparseBloomFilter(shape2, IndexProducer.fromIndexArray(new int[] { 5, 64, 169 }));
+ assertSymmetricOperation(4, SetOperations::orCardinality, filter1, filter2);
}
@Test
@@ -235,24 +240,32 @@ public class SetOperationsTest {
Shape shape = Shape.fromKM(3, 128);
SparseBloomFilter filter1 = new SparseBloomFilter(shape, IndexProducer.fromIndexArray(new int[] { 1, 63, 64 }));
SparseBloomFilter filter2 = new SparseBloomFilter(shape, IndexProducer.fromIndexArray(new int[] { 5, 64, 69 }));
- assertEquals(1, SetOperations.andCardinality(filter1, filter2));
- assertEquals(1, SetOperations.andCardinality(filter2, filter1));
+ assertSymmetricOperation(1, SetOperations::andCardinality, filter1, filter2);
filter1 = new SparseBloomFilter(shape, IndexProducer.fromIndexArray(new int[] { 1, 63 }));
filter2 = new SparseBloomFilter(shape, IndexProducer.fromIndexArray(new int[] { 5, 64, 69 }));
- assertEquals(0, SetOperations.andCardinality(filter1, filter2));
- assertEquals(0, SetOperations.andCardinality(filter2, filter1));
+ assertSymmetricOperation(0, SetOperations::andCardinality, filter1, filter2);
filter1 = new SparseBloomFilter(shape, IndexProducer.fromIndexArray(new int[] { 5, 63 }));
filter2 = new SparseBloomFilter(shape, IndexProducer.fromIndexArray(new int[] { 5, 64, 69 }));
- assertEquals(1, SetOperations.andCardinality(filter1, filter2));
- assertEquals(1, SetOperations.andCardinality(filter2, filter1));
+ assertSymmetricOperation(1, SetOperations::andCardinality, filter1, filter2);
+ }
- Shape bigShape = Shape.fromKM(3, 192);
- filter1 = new SparseBloomFilter(bigShape, IndexProducer.fromIndexArray(new int[] { 1, 63, 185}));
- filter2 = new SparseBloomFilter(shape, IndexProducer.fromIndexArray(new int[] { 5, 63, 69 }));
- assertEquals(1, SetOperations.andCardinality(filter1, filter2));
- assertEquals(1, SetOperations.andCardinality(filter2, filter1));
+ @Test
+ public final void testAndCardinalityWithDifferentLengthFilters() {
+ Shape shape = Shape.fromKM(3, 128);
+ Shape shape2 = Shape.fromKM(3, 192);
+ SparseBloomFilter filter1 = new SparseBloomFilter(shape, IndexProducer.fromIndexArray(new int[] { 1, 63, 64 }));
+ SparseBloomFilter filter2 = new SparseBloomFilter(shape2, IndexProducer.fromIndexArray(new int[] { 5, 64, 169 }));
+ assertSymmetricOperation(1, SetOperations::andCardinality, filter1, filter2);
+
+ filter1 = new SparseBloomFilter(shape, IndexProducer.fromIndexArray(new int[] { 1, 63 }));
+ filter2 = new SparseBloomFilter(shape2, IndexProducer.fromIndexArray(new int[] { 5, 64, 169 }));
+ assertSymmetricOperation(0, SetOperations::andCardinality, filter1, filter2);
+
+ filter1 = new SparseBloomFilter(shape, IndexProducer.fromIndexArray(new int[] { 5, 63 }));
+ filter2 = new SparseBloomFilter(shape2, IndexProducer.fromIndexArray(new int[] { 5, 64, 169 }));
+ assertSymmetricOperation(1, SetOperations::andCardinality, filter1, filter2);
}
@Test
@@ -260,24 +273,38 @@ public class SetOperationsTest {
Shape shape = Shape.fromKM(3, 128);
SparseBloomFilter filter1 = new SparseBloomFilter(shape, IndexProducer.fromIndexArray(new int[] { 1, 63, 64 }));
SparseBloomFilter filter2 = new SparseBloomFilter(shape, IndexProducer.fromIndexArray(new int[] { 5, 64, 69 }));
- assertEquals(4, SetOperations.xorCardinality(filter1, filter2));
- assertEquals(4, SetOperations.xorCardinality(filter2, filter1));
+ assertSymmetricOperation(4, SetOperations::xorCardinality, filter1, filter2);
filter1 = new SparseBloomFilter(shape, IndexProducer.fromIndexArray(new int[] { 1, 63 }));
filter2 = new SparseBloomFilter(shape, IndexProducer.fromIndexArray(new int[] { 5, 64, 69 }));
- assertEquals(5, SetOperations.xorCardinality(filter1, filter2));
- assertEquals(5, SetOperations.xorCardinality(filter2, filter1));
+ assertSymmetricOperation(5, SetOperations::xorCardinality, filter1, filter2);
filter1 = new SparseBloomFilter(shape, IndexProducer.fromIndexArray(new int[] { 5, 63 }));
filter2 = new SparseBloomFilter(shape, IndexProducer.fromIndexArray(new int[] { 5, 64, 69 }));
- assertEquals(3, SetOperations.xorCardinality(filter1, filter2));
- assertEquals(3, SetOperations.xorCardinality(filter2, filter1));
+ assertSymmetricOperation(3, SetOperations::xorCardinality, filter1, filter2);
Shape bigShape = Shape.fromKM(3, 192);
filter1 = new SparseBloomFilter(bigShape, IndexProducer.fromIndexArray(new int[] { 1, 63, 185}));
filter2 = new SparseBloomFilter(shape, IndexProducer.fromIndexArray(new int[] { 5, 63, 69 }));
- assertEquals(4, SetOperations.xorCardinality(filter1, filter2));
- assertEquals(4, SetOperations.xorCardinality(filter2, filter1));
+ assertSymmetricOperation(4, SetOperations::xorCardinality, filter1, filter2);
+ }
+
+ @Test
+ public final void testXorCardinalityWithDifferentLengthFilters() {
+ Shape shape = Shape.fromKM(3, 128);
+ Shape shape2 = Shape.fromKM(3, 192);
+
+ SparseBloomFilter filter1 = new SparseBloomFilter(shape, IndexProducer.fromIndexArray(new int[] { 1, 63, 64 }));
+ SparseBloomFilter filter2 = new SparseBloomFilter(shape2, IndexProducer.fromIndexArray(new int[] { 5, 64, 169 }));
+ assertSymmetricOperation(4, SetOperations::xorCardinality, filter1, filter2);
+
+ filter1 = new SparseBloomFilter(shape, IndexProducer.fromIndexArray(new int[] { 1, 63 }));
+ filter2 = new SparseBloomFilter(shape2, IndexProducer.fromIndexArray(new int[] { 5, 64, 169 }));
+ assertSymmetricOperation(5, SetOperations::xorCardinality, filter1, filter2);
+
+ filter1 = new SparseBloomFilter(shape, IndexProducer.fromIndexArray(new int[] { 5, 63 }));
+ filter2 = new SparseBloomFilter(shape2, IndexProducer.fromIndexArray(new int[] { 5, 64, 169 }));
+ assertSymmetricOperation(3, SetOperations::xorCardinality, filter1, filter2);
}