Replace Travis-CI badge with GitHub Actions CI master
authorGary Gregory <garydgregory@gmail.com>
Thu, 29 Sep 2022 18:29:28 +0000 (14:29 -0400)
committerGary Gregory <garydgregory@gmail.com>
Thu, 29 Sep 2022 18:29:28 +0000 (14:29 -0400)
55 files changed:
.github/workflows/codeql-analysis.yml
.github/workflows/coverage.yml
.github/workflows/maven.yml
.github/workflows/scorecards-analysis.yml [new file with mode: 0644]
CONTRIBUTING.md
README.md
pom.xml
src/changes/changes.xml
src/main/java/org/apache/commons/collections4/Equator.java
src/main/java/org/apache/commons/collections4/ListUtils.java
src/main/java/org/apache/commons/collections4/bloomfilter/ArrayCountingBloomFilter.java
src/main/java/org/apache/commons/collections4/bloomfilter/BloomFilter.java
src/main/java/org/apache/commons/collections4/bloomfilter/CountingBloomFilter.java
src/main/java/org/apache/commons/collections4/bloomfilter/HasherCollection.java
src/main/java/org/apache/commons/collections4/bloomfilter/IndexProducer.java
src/main/java/org/apache/commons/collections4/bloomfilter/SimpleBloomFilter.java
src/main/java/org/apache/commons/collections4/bloomfilter/SparseBloomFilter.java
src/main/java/org/apache/commons/collections4/bloomfilter/package-info.java
src/main/java/org/apache/commons/collections4/functors/ComparatorPredicate.java
src/main/java/org/apache/commons/collections4/iterators/CollatingIterator.java
src/main/java/org/apache/commons/collections4/trie/PatriciaTrie.java
src/site/xdoc/release_4_0.xml
src/test/java/org/apache/commons/collections4/bag/AbstractBagTest.java
src/test/java/org/apache/commons/collections4/bag/SynchronizedBagTest.java
src/test/java/org/apache/commons/collections4/bloomfilter/AbstractBitCountProducerTest.java
src/test/java/org/apache/commons/collections4/bloomfilter/AbstractBloomFilterTest.java
src/test/java/org/apache/commons/collections4/bloomfilter/AbstractCountingBloomFilterTest.java
src/test/java/org/apache/commons/collections4/bloomfilter/AbstractHasherTest.java
src/test/java/org/apache/commons/collections4/bloomfilter/AbstractIndexProducerTest.java
src/test/java/org/apache/commons/collections4/bloomfilter/ArrayCountingBloomFilterTest.java
src/test/java/org/apache/commons/collections4/bloomfilter/ArrayHasher.java [new file with mode: 0644]
src/test/java/org/apache/commons/collections4/bloomfilter/BitCountProducerFromArrayCountingBloomFilterTest.java
src/test/java/org/apache/commons/collections4/bloomfilter/BitCountProducerFromIndexProducerTest.java
src/test/java/org/apache/commons/collections4/bloomfilter/BitMapProducerFromSimpleBloomFilterTest.java
src/test/java/org/apache/commons/collections4/bloomfilter/BitMapProducerFromSparseBloomFilterTest.java
src/test/java/org/apache/commons/collections4/bloomfilter/DefaultBitMapProducerTest.java
src/test/java/org/apache/commons/collections4/bloomfilter/DefaultBloomFilterTest.java
src/test/java/org/apache/commons/collections4/bloomfilter/DefaultIndexProducerTest.java [new file with mode: 0644]
src/test/java/org/apache/commons/collections4/bloomfilter/EnhancedDoubleHasherTest.java
src/test/java/org/apache/commons/collections4/bloomfilter/HasherCollectionTest.java
src/test/java/org/apache/commons/collections4/bloomfilter/IndexProducerFromArrayCountingBloomFilterTest.java
src/test/java/org/apache/commons/collections4/bloomfilter/IndexProducerFromBitmapProducerTest.java
src/test/java/org/apache/commons/collections4/bloomfilter/IndexProducerFromHasherCollectionTest.java
src/test/java/org/apache/commons/collections4/bloomfilter/IndexProducerFromHasherTest.java
src/test/java/org/apache/commons/collections4/bloomfilter/IndexProducerFromIntArrayTest.java
src/test/java/org/apache/commons/collections4/bloomfilter/IndexProducerFromSimpleBloomFilterTest.java
src/test/java/org/apache/commons/collections4/bloomfilter/IndexProducerFromSparseBloomFilterTest.java
src/test/java/org/apache/commons/collections4/bloomfilter/SetOperationsTest.java
src/test/java/org/apache/commons/collections4/bloomfilter/SimpleBloomFilterTest.java
src/test/java/org/apache/commons/collections4/bloomfilter/SparseBloomFilterTest.java
src/test/java/org/apache/commons/collections4/bloomfilter/UniqueIndexProducerFromHasherCollectionTest.java
src/test/java/org/apache/commons/collections4/bloomfilter/UniqueIndexProducerFromHasherTest.java
src/test/java/org/apache/commons/collections4/bloomfilter/checkstyle.xml [deleted file]
src/test/java/org/apache/commons/collections4/collection/AbstractCollectionTest.java
src/test/java/org/apache/commons/collections4/properties/EmptyPropertiesTest.java

index 0067a01231771f08c0df88c99fc4359d47e995ad..29024680882969714ee1077de205b3e99b40e199 100644 (file)
@@ -42,7 +42,13 @@ jobs:
 
     steps:
     - name: Checkout repository
-      uses: actions/checkout@v3
+      uses: actions/checkout@v3.0.2
+    - uses: actions/cache@v3.0.8
+      with:
+        path: ~/.m2/repository
+        key: ${{ runner.os }}-maven-${{ hashFiles('**/pom.xml') }}
+        restore-keys: |
+          ${{ runner.os }}-maven-
 
     # Initializes the CodeQL tools for scanning.
     - name: Initialize CodeQL
index 0e3b4e73166431c16afbe61768962147d2dd4c60..8529d2786619c3616d02530bde84e5063313b267 100644 (file)
@@ -29,8 +29,8 @@ jobs:
         java: [ 8 ]
 
     steps:
-    - uses: actions/checkout@v3
-    - uses: actions/cache@v3.0.6
+    - uses: actions/checkout@v3.0.2
+    - uses: actions/cache@v3.0.8
       with:
         path: ~/.m2/repository
         key: ${{ runner.os }}-maven-${{ hashFiles('**/pom.xml') }}
index ec1ccff4cc93a8f2e1a52c41f941c8bd49758704..cdfc7be186f6374e615ea409e51a911e1d77614c 100644 (file)
@@ -31,8 +31,8 @@ jobs:
 #            experimental: true
         
     steps:
-    - uses: actions/checkout@v3
-    - uses: actions/cache@v3.0.6
+    - uses: actions/checkout@v3.0.2
+    - uses: actions/cache@v3.0.8
       with:
         path: ~/.m2/repository
         key: ${{ runner.os }}-maven-${{ hashFiles('**/pom.xml') }}
diff --git a/.github/workflows/scorecards-analysis.yml b/.github/workflows/scorecards-analysis.yml
new file mode 100644 (file)
index 0000000..abd6992
--- /dev/null
@@ -0,0 +1,67 @@
+# Licensed to the Apache Software Foundation (ASF) under one or more
+# contributor license agreements. See the NOTICE file distributed with
+# this work for additional information regarding copyright ownership.
+# The ASF licenses this file to You under the Apache license, Version 2.0
+# (the "License"); you may not use this file except in compliance with
+# the License. You may obtain a copy of the License at
+#
+#      http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS,
+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+# See the license for the specific language governing permissions and
+# limitations under the license.
+
+name: "Scorecards supply-chain security"
+
+on:
+  branch_protection_rule:
+  schedule:
+    - cron: "30 1 * * 6"    # Weekly on Saturdays
+  push:
+    branches: [ "master" ]
+
+permissions: read-all
+
+jobs:
+
+  analysis:
+
+    name: "Scorecards analysis"
+    runs-on: ubuntu-latest
+    permissions:
+      security-events: write    # Needed to upload the results to the code-scanning dashboard.
+      actions: read
+      contents: read
+
+    steps:
+
+      - name: "Checkout code"
+        uses: actions/checkout@2541b1294d2704b0964813337f33b291d3f8596b   # 3.0.2
+        with:
+          persist-credentials: false
+
+      - name: "Run analysis"
+        uses: ossf/scorecard-action@ce330fde6b1a5c9c75b417e7efc510b822a35564    # 1.1.2
+        with:
+          results_file: results.sarif
+          results_format: sarif
+          # A read-only PAT token, which is sufficient for the action to function.
+          # The relevant discussion: https://github.com/ossf/scorecard-action/issues/188
+          repo_token: ${{ secrets.GITHUB_TOKEN }}
+          # Publish the results for public repositories to enable scorecard badges.
+          # For more details: https://github.com/ossf/scorecard-action#publishing-results
+          publish_results: true
+
+      - name: "Upload artifact"
+        uses: actions/upload-artifact@3cea5372237819ed00197afe530f5a7ea3e805c8    # 3.1.0
+        with:
+          name: SARIF file
+          path: results.sarif
+          retention-days: 5
+
+      - name: "Upload to code-scanning"
+        uses: github/codeql-action/upload-sarif@b398f525a5587552e573b247ac661067fafa920b    # 2.1.22
+        with:
+          sarif_file: results.sarif
index 0e2ebae9cdecd2b33b2806f1a4174e9c02cedc68..7ea10b9a79c558cd7d1ff2081829d87fa35e9a31 100644 (file)
@@ -61,7 +61,7 @@ Making Changes
 --------------
 
 + Create a _topic branch_ for your isolated work.
-  * Usually you should base your branch on the `master` or `trunk` branch.
+  * Usually you should base your branch on the `master` branch.
   * A good topic branch name can be the JIRA bug id plus a keyword, e.g. `COLLECTIONS-123-InputStream`.
   * If you have submitted multiple JIRA issues, try to maintain separate branches and pull requests.
 + Make commits of logical units.
index cb0cf0df4ec9d49dd99a5559941199501c7f2b2c..6fa905a1a6e943367ab770492133b959f5d583df 100644 (file)
--- a/README.md
+++ b/README.md
 Apache Commons Collections
 ===================
 
-[![Build Status](https://travis-ci.org/apache/commons-collections.svg)](https://travis-ci.org/apache/commons-collections)
-[![Coverage Status](https://coveralls.io/repos/apache/commons-collections/badge.svg)](https://coveralls.io/r/apache/commons-collections)
-[![Maven Central](https://maven-badges.herokuapp.com/maven-central/org.apache.commons/commons-collections4/badge.svg)](https://maven-badges.herokuapp.com/maven-central/org.apache.commons/commons-collections4/)
+[![GitHub Actions Status](https://github.com/apache/commons-collections/workflows/Java%20CI/badge.svg)](https://github.com/apache/commons-collections/actions)
+[![Coverage Status](https://codecov.io/gh/apache/commons-collections/branch/master/graph/badge.svg)](https://app.codecov.io/gh/apache/commons-collections/branch/master)
+[![Maven Central](https://maven-badges.herokuapp.com/maven-central/org.apache.commons/commons-collections4/badge.svg?gav=true)](https://maven-badges.herokuapp.com/maven-central/org.apache.commons/commons-collections4/?gav=true)
 [![Javadocs](https://javadoc.io/badge/org.apache.commons/commons-collections4/4.4.svg)](https://javadoc.io/doc/org.apache.commons/commons-collections4/4.4)
+[![CodeQL](https://github.com/apache/commons-collections/workflows/CodeQL/badge.svg)](https://github.com/apache/commons-collections/actions/workflows/codeql-analysis.yml?query=workflow%3ACodeQL)
+[![OpenSSF
+Scorecard](https://api.securityscorecards.dev/projects/github.com/apache/commons-collections/badge)](https://api.securityscorecards.dev/projects/github.com/apache/commons-collections)
 
 The Apache Commons Collections package contains types that extend and augment the Java Collections Framework.
 
@@ -79,7 +82,7 @@ There are some guidelines which will make applying PRs easier for us:
 + No tabs! Please use spaces for indentation.
 + Respect the code style.
 + Create minimal diffs - disable on save actions like reformat source code or organize imports. If you feel the source code should be reformatted create a separate PR for this change.
-+ Provide JUnit tests for your changes and make sure your changes don't break any existing tests by running ```mvn clean test```.
++ Provide JUnit tests for your changes and make sure your changes don't break any existing tests by running ```mvn```.
 
 If you plan to contribute on a regular basis, please consider filing a [contributor license agreement](https://www.apache.org/licenses/#clas).
 You can learn more about contributing via GitHub in our [contribution guidelines](CONTRIBUTING.md).
diff --git a/pom.xml b/pom.xml
index 336e63a3466fe751face4d7400a3845b36bc9f8c..a004e131ec011e651b768b6309435a3f104dafdc 100644 (file)
--- a/pom.xml
+++ b/pom.xml
@@ -19,7 +19,7 @@
   <parent>
     <groupId>org.apache.commons</groupId>
     <artifactId>commons-parent</artifactId>
-    <version>53</version>
+    <version>54</version>
   </parent>
   <modelVersion>4.0.0</modelVersion>
   <artifactId>commons-collections4</artifactId>
     <commons.jira.pid>12310465</commons.jira.pid>
     <!-- The RC version used in the staging repository URL. -->
     <commons.rc.version>RC1</commons.rc.version>
-    <checkstyle.version>3.1.2</checkstyle.version>
+    <checkstyle.version>3.2.0</checkstyle.version>
     <checkstyle.dep.version>9.3</checkstyle.dep.version>
-    <commons.pmd.version>3.17.0</commons.pmd.version>
-    <commons.pmd-impl.version>6.48.0</commons.pmd-impl.version>
+    <commons.pmd.version>3.19.0</commons.pmd.version>
+    <commons.pmd-impl.version>6.49.0</commons.pmd-impl.version>
 
     <commons.site.path>collections</commons.site.path>
     <commons.scmPubUrl>https://svn.apache.org/repos/infra/websites/production/commons/content/proper/commons-collections</commons.scmPubUrl>
     <commons.scmPubCheckoutDirectory>site-content</commons.scmPubCheckoutDirectory>
     
-    <commons.rat.version>0.14</commons.rat.version>
-    <!-- Skip CLIRR in favor of JApiCmp -->
-    <clirr.skip>true</clirr.skip>
     <commons.clirr.version>2.8</commons.clirr.version>
     <commons.jacoco.version>0.8.8</commons.jacoco.version>
-    <commons.junit.version>5.9.0</commons.junit.version>
+    <commons.junit.version>5.9.1</commons.junit.version>
 
     <!-- Override commons parent version to allow build on java 17 -->
-    <commons.japicmp.version>0.15.7</commons.japicmp.version>
+    <commons.japicmp.version>0.16.0</commons.japicmp.version>
 
     <!--Commons Release Plugin -->
     <commons.bc.version>4.4</commons.bc.version>
index 0b760bca4da7c0a95ddda6ef4f6cc010612ac87a..e40a23bc279828f9d4fffc017feab81d404526da 100644 (file)
     </action>
     <!-- UPDATE -->
     <action type="update" dev="kinow" due-to="Dependabot, Gary Gregory">
-      Bump actions/cache from 2 to 3.0.6 #214 #225 #239 #266 #294.
+      Bump actions/cache from 2 to 3.0.8 #214 #225 #239 #266 #294.
     </action>
     <action type="update" dev="kinow" due-to="Dependabot, Gary Gregory">
       Bump actions/setup-java from 1.4.0 to 3 #174 #177 #186 #224 #298.
     </action>
-    <action type="update" dev="ggregory" due-to="Dependabot">
-      Update actions/checkout from 1 to 3 #166 #173 #183 #193 #262 #264 #285.
+    <action type="update" dev="ggregory" due-to="Dependabot, Gary Gregory">
+      Bump actions/checkout from 1 to 3.0.2 #166 #173 #183 #193 #262 #264 #285.
     </action>
     <action type="update" dev="kinow" due-to="Dependabot">
       Bump codecov/codecov-action from 2 to 3 #297.
       Remove the parentheses in the error message in CircularFifoQueue #107.
     </action>
     <action dev="ggregory" type="update" due-to="Gary Gregory">
-      [test] org.easymock:easymock 4.0.2 -> 4.1.
+      [test] Bump org.easymock:easymock from 4.0.2 to 4.1.
     </action>
     <action issue="COLLECTIONS-734" dev="ggregory" type="fix" due-to="Chen">
       Encountered an IllegalStateException while traversing with Flat3Map.entrySet(). #115.
     <action issue="COLLECTIONS-728" dev="ggregory" type="add" due-to="Claude Warren">
       BloomFilter contribution.
     </action>
-    <action dev="ggregory" type="update" due-to="Gary Gregory">
-      [build] Update Apache commons-parent from 48 to 51.
+    <action dev="ggregory" type="update" due-to="Gary Gregory, Dependabot">
+      [build] Update Apache commons-parent from 48 to 54, #339.
     </action>
     <action issue="COLLECTIONS-746" dev="ggregory" type="add" due-to="Gary Gregory">
       Add org.apache.commons.collections4.properties.PropertiesFactory.EMPTY_PROPERTIES.
       Bump Jacoco from 0.8.4 to 0.8.8.
     </action>
     <action dev="ggregory" type="update" due-to="Gary Gregory">
-      [test] Update org.easymock:easymock 4.1 -> 4.2.
+      [test] Bump org.easymock:easymock from 4.1 to 4.2.
     </action>
     <action issue="COLLECTIONS-747" dev="ggregory" type="fix" due-to="Gary Gregory, Walter Laan">
       MultiKey.getKeys class cast exception.
       Let org.apache.commons.collections4.properties.[Sorted]PropertiesFactory accept XML input.
     </action>
     <action type="update" dev="ggregory" due-to="Gary Gregory">
-      Update tests from Apache Commons Lang 3.9 to 3.11.
+      Bump tests from Apache Commons Lang 3.9 to 3.11.
     </action>
     <action dev="ggregory" type="update" due-to="Chen">
       Fixed the typo and deal the NPE with Objects.requireNonNull #118.
     </action>
     <action type="update" dev="ggregory" due-to="Gary Gregory">
-      Update build from checkstyle.version 3.1.0 to 3.1.1.
-      Update build from checkstyle.dep.version 8.29 to 8.31.
-      Update build from checkstyle.dep.version 8.31 to 8.32.
-      Bump checkstyle from 8.35 to 9.3 #179, #184, #192, #199, #204, #212, #218, #222, #234, #240, #243, #245, #246, #248, #257, #263, #270, #271, #277.
+      Bump maven-checkstyle-plugin 3.1.0 to 3.2.0.
+    </action>
+    <action type="update" dev="ggregory" due-to="Gary Gregory">
+      Bump checkstyle 8.29 9.3 #179, #184, #192, #199, #204, #212, #218, #222, #234, #240, #243, #245, #246, #248, #257, #263, #270, #271, #277.
     </action>
     <action dev="ggregory" type="update" due-to="Chen, Bruno P. Kinoshita, Gary Gregory, Michael Osipov">
       Better NPE messages in CollectionUtils with Objects.requireNonNull #117.
       Upgrade to JUnit v5.6.2 #136.
     </action>
     <action issue="COLLECTIONS-777" type="update" dev="ggregory" due-to="John Patrick, Gary Gregory, Dependabot">
-      Fully migrate JUnit 4.12 to 5.9.0 #324.
+      Fully migrate JUnit 4.12 to 5.9.1 #324, #338.
     </action>
     <action issue="COLLECTIONS-753" type="update" dev="ggregory" due-to="John Patrick">
       Upgrade Hamcrest to 2.2.
       Remove deprecated sudo setting. #161.
     </action>
     <action type="update" dev="ggregory" due-to="Gary Gregory">
-      Update tests from commons-io:commons-io 2.6 to 2.11.0 #180.
+      Bump tests from commons-io:commons-io 2.6 to 2.11.0 #180.
     </action>
-    <action type="update" dev="ggregory" due-to="Dependabot">
-      Update maven-pmd-plugin from 3.12.0 to 3.17.0 #167, #196, #253, #311.
+    <action type="update" dev="ggregory" due-to="Dependabot, Gary Gregory">
+      Bump maven-pmd-plugin from 3.12.0 to 3.19.0 #167, #196, #253, #311, #334.
     </action>
     <action type="update" dev="ggregory" due-to="Gary Gregory">
-      Update optional commons-codec from 1.14 to 1.15.
+      Bump optional commons-codec from 1.14 to 1.15.
     </action>
     <action type="update" dev="ggregory" due-to="Dependabot">
       Bump commons.junit.version from 5.6.2 to 5.8.2 #181 #213 #236 #252 #254 #268.
       Bump maven-pmd-plugin from 3.15.0 to 3.16.0 #286.
     </action>
     <action type="update" dev="kinow" due-to="Dependabot">
-      Bump commons-parent from 52 to 53 #299.
+      Bump commons-parent from 52 to 54 #299.
     </action>
     <action type="update" dev="kinow" due-to="Dependabot">
-      Bump japicmp from 0.15.4 to 0.15.7.
+      Bump japicmp from 0.15.4 to 0.16.0.
     </action>
     <action type="update" dev="kinow" due-to="Dependabot">
-       Bump commons.pmd-impl.version from 6.46.0 to 6.48.0 #318, #327.
+      Bump commons.pmd-impl.version from 6.46.0 to 6.49.0 #318, #327, #333.
+    </action>
+    <action type="update" dev="aherbert" due-to="Partha Protim Paul">
+      Correct test of Collection toArray(Object[]) vs toArray() to optionally ignore array order.
+      Ordering is not specified for some collections such as Bags.
     </action>
   </release>
   <release version="4.4" date="2019-07-05" description="Maintenance release.">
@@ -1062,7 +1066,7 @@ features, this release includes numerous bug fixes.
     </action>
     <action issue="COLLECTIONS-294" dev="bayard" type="fix" due-to="Benjamin Bentmann">
       "CaseInsensitiveMap" will now convert input strings to lower-case in a
-      locale-independant manner.
+      locale-independent manner.
     </action>
     <action issue="COLLECTIONS-293" dev="tn" type="add" due-to="Stephen Kestle">
       Added support for using custom "Equator" objects in "EqualPredicate".
index 63cce0f300d41b61cfde052b7e99a57e5a1f5847..db5cdf868465d6d1f9b5fd3176c1c2c1dc1a0679 100644 (file)
@@ -20,7 +20,7 @@ package org.apache.commons.collections4;
  * An equation function, which determines equality between objects of type T.
  * <p>
  * It is the functional sibling of {@link java.util.Comparator}; {@link Equator} is to
- * {@link Object} as {@link java.util.Comparator} is to {@link java.lang.Comparable}.
+ * {@link Object} as {@link java.util.Comparator} is to {@link Comparable}.
  * </p>
  *
  * @param <T> the types of object this {@link Equator} can evaluate.
index 8e95711fb99acd6c5123b7b904b70412c386f320..9c08f60682ce7bfcd19d525a3f345675cdd7bb26 100644 (file)
@@ -284,7 +284,7 @@ public class ListUtils {
 
     /**
      * Tests two lists for value-equality as per the equality contract in
-     * {@link java.util.List#equals(java.lang.Object)}.
+     * {@link java.util.List#equals(Object)}.
      * <p>
      * This method is useful for implementing {@code List} when you cannot
      * extend AbstractList. The method takes Collection instances to enable other
index a46d7665f708e804b03536537b8fea1231f74558..e76ddda44034481ca4c52262d73debfa213c6328 100644 (file)
@@ -16,6 +16,7 @@
  */
 package org.apache.commons.collections4.bloomfilter;
 
+import java.util.Arrays;
 import java.util.Objects;
 import java.util.function.IntPredicate;
 import java.util.function.LongPredicate;
@@ -104,14 +105,19 @@ public final class ArrayCountingBloomFilter implements CountingBloomFilter {
         this.counts = source.counts.clone();
     }
 
+    @Override
+    public void clear() {
+        Arrays.fill(counts, 0);
+    }
+
     @Override
     public ArrayCountingBloomFilter copy() {
         return new ArrayCountingBloomFilter(this);
     }
 
     @Override
-    public boolean isSparse() {
-        return true;
+    public int characteristics() {
+        return SPARSE;
     }
 
     @Override
@@ -119,39 +125,6 @@ public final class ArrayCountingBloomFilter implements CountingBloomFilter {
         return (int) IntStream.range(0, counts.length).filter(i -> counts[i] > 0).count();
     }
 
-    @Override
-    public boolean merge(final BloomFilter other) {
-        Objects.requireNonNull(other, "other");
-        try {
-            return add(BitCountProducer.from(other));
-        } catch (IndexOutOfBoundsException e) {
-            throw new IllegalArgumentException( e );
-        }
-    }
-
-    @Override
-    public boolean merge(final Hasher hasher) {
-        Objects.requireNonNull(hasher, "hasher");
-        try {
-            return add(BitCountProducer.from(hasher.uniqueIndices(shape)));
-        } catch (IndexOutOfBoundsException e) {
-            throw new IllegalArgumentException(
-                    String.format("Filter only accepts values in the [0,%d) range", shape.getNumberOfBits()));
-        }
-    }
-
-    @Override
-    public boolean remove(final BloomFilter other) {
-        Objects.requireNonNull(other, "other");
-        return subtract(BitCountProducer.from(other));
-    }
-
-    @Override
-    public boolean remove(final Hasher hasher) {
-        Objects.requireNonNull(hasher, "hasher");
-        return subtract(BitCountProducer.from(hasher.uniqueIndices(shape)));
-    }
-
     @Override
     public boolean add(final BitCountProducer other) {
         Objects.requireNonNull(other, "other");
index e13260b996e1ad9e269c1eb3df7fa54b6c76cd71..f939538b0e1be2d6f3e5e39471a84f52ec19c937 100644 (file)
@@ -29,6 +29,15 @@ import java.util.Objects;
  */
 public interface BloomFilter extends IndexProducer, BitMapProducer {
 
+    /**
+     * The sparse characteristic used to determine the best method for matching.
+     * <p>For `sparse` implementations
+     * the {@code forEachIndex(IntConsumer consumer)} method is more efficient.  For non `sparse` implementations
+     * the {@code forEachBitMap(LongConsumer consumer)} is more efficient.  Implementers should determine if it is easier
+     * for the implementation to produce indexes of bit map blocks.</p>
+     */
+    int SPARSE = 0x1;
+
     /**
      * Creates a new instance of the BloomFilter with the same properties as the current one.
      * @return a copy of this BloomFilter
@@ -38,17 +47,12 @@ public interface BloomFilter extends IndexProducer, BitMapProducer {
     // Query Operations
 
     /**
-     * This method is used to determine the best method for matching.
-     *
-     * <p>For `sparse` implementations
-     * the {@code forEachIndex(IntConsumer consumer)} method is more efficient.  For non `sparse` implementations
-     * the {@code forEachBitMap(LongConsumer consumer)} is more efficient.  Implementers should determine if it is easier
-     * for the implementation to produce indexes of bit map blocks.</p>
-     *
-     * @return {@code true} if the implementation is sparse {@code false} otherwise.
-     * @see BitMap
+     * Returns the characteristics of the filter.
+     * <p>
+     * Characteristics are defined as bits within the characteristics integer.
+     * @return the characteristics for this bloom filter.
      */
-    boolean isSparse();
+    int characteristics();
 
     /**
      * Gets the shape that was used when the filter was built.
@@ -56,6 +60,11 @@ public interface BloomFilter extends IndexProducer, BitMapProducer {
      */
     Shape getShape();
 
+    /**
+     * Resets the filter to its initial, unpopulated state.
+     */
+    void clear();
+
     /**
      * Returns {@code true} if this filter contains the specified filter.
      *
@@ -69,7 +78,7 @@ public interface BloomFilter extends IndexProducer, BitMapProducer {
      */
     default boolean contains(BloomFilter other) {
         Objects.requireNonNull(other, "other");
-        return isSparse() ? contains((IndexProducer) other) : contains((BitMapProducer) other);
+        return (characteristics() & SPARSE) != 0 ? contains((IndexProducer) other) : contains((BitMapProducer) other);
     }
 
     /**
@@ -126,7 +135,9 @@ public interface BloomFilter extends IndexProducer, BitMapProducer {
      * @param other The bloom filter to merge into this one.
      * @return true if the merge was successful
      */
-    boolean merge(BloomFilter other);
+    default boolean merge(BloomFilter other) {
+        return (characteristics() & SPARSE) != 0 ? merge((IndexProducer) other ) : merge((BitMapProducer) other);
+    }
 
     /**
      * Merges the specified hasher into this Bloom filter. Specifically all
@@ -134,7 +145,7 @@ public interface BloomFilter extends IndexProducer, BitMapProducer {
      *
      * <p><em>Note: This method should return {@code true} even if no additional bit indexes were
      * enabled. A {@code false} result indicates that this filter may or may not contain
-     * the {@code other} Bloom filter.</em>  This state may occur in complex Bloom filter implementations like
+     * the {@code hasher} values.</em>  This state may occur in complex Bloom filter implementations like
      * counting Bloom filters.</p>
      *
      * @param hasher The hasher to merge.
@@ -142,12 +153,39 @@ public interface BloomFilter extends IndexProducer, BitMapProducer {
      */
     default boolean merge(Hasher hasher) {
         Objects.requireNonNull(hasher, "hasher");
-        Shape shape = getShape();
-        // create the bloomfilter that is most likely to merge quickly with this one
-        BloomFilter result = isSparse() ? new SparseBloomFilter(shape, hasher) : new SimpleBloomFilter(shape, hasher);
-        return merge(result);
+        return merge(hasher.indices(getShape()));
     }
 
+    /**
+     * Merges the specified IndexProducer into this Bloom filter. Specifically all
+     * bit indexes that are identified by the {@code producer} will be enabled in this filter.
+     *
+     * <p><em>Note: This method should return {@code true} even if no additional bit indexes were
+     * enabled. A {@code false} result indicates that this filter may or may not contain all the indexes of
+     * the {@code producer}.</em>  This state may occur in complex Bloom filter implementations like
+     * counting Bloom filters.</p>
+     *
+     * @param indexProducer The IndexProducer to merge.
+     * @return true if the merge was successful
+     * @throws IllegalArgumentException if producer sends illegal value.
+     */
+    boolean merge(IndexProducer indexProducer);
+
+    /**
+     * Merges the specified hasher into this Bloom filter. Specifically all
+     * bit indexes that are identified by the {@code producer} will be enabled in this filter.
+     *
+     * <p><em>Note: This method should return {@code true} even if no additional bit indexes were
+     * enabled. A {@code false} result indicates that this filter may or may not contain all the indexes
+     * enabled in the {@code producer}.</em>  This state may occur in complex Bloom filter implementations like
+     * counting Bloom filters.</p>
+     *
+     * @param bitMapProducer The producer to merge.
+     * @return true if the merge was successful
+     * @throws IllegalArgumentException if producer sends illegal value.
+     */
+    boolean merge(BitMapProducer bitMapProducer);
+
     // Counting Operations
 
     /**
index 186c284e9352ce74d0c1588c0947c75d0432bc30..1d6f65cf5c6df8ac79012699a5b1ff2f6468365d 100644 (file)
@@ -16,6 +16,8 @@
  */
 package org.apache.commons.collections4.bloomfilter;
 
+import java.util.Objects;
+
 /**
  * The interface that describes a Bloom filter that associates a count with each
  * bit index to allow reversal of merge operations with remove operations.
@@ -77,6 +79,84 @@ public interface CountingBloomFilter extends BloomFilter, BitCountProducer {
 
     // Modification Operations
 
+    /**
+     * Merges the specified Bloom filter into this Bloom filter.
+     *
+     * <p>Specifically: all counts for the indexes identified by the {@code other} filter will be incremented by 1,</p>
+     *
+     * <p>Note: If the other filter is a counting Bloom filter the index counts are ignored and it is treated as an
+     * IndexProducer.</p>
+     *
+     * <p>This method will return {@code true} if the filter is valid after the operation.</p>
+     *
+     * @param other the other Bloom filter
+     * @return {@code true} if the removal was successful and the state is valid
+     * @see #isValid()
+     * @see #add(BitCountProducer)
+     */
+    default boolean merge(final BloomFilter other) {
+        Objects.requireNonNull(other, "other");
+        return merge((IndexProducer) other);
+    }
+
+    /**
+     * Merges the specified Hasher into this Bloom filter.
+     *
+     * <p>Specifically: all counts for the unique indexes identified by the {@code hasher} will be incremented by 1,</p>
+     *
+     * <p>This method will return {@code true} if the filter is valid after the operation.</p>
+     *
+     * @param hasher the hasher
+     * @return {@code true} if the removal was successful and the state is valid
+     * @see #isValid()
+     * @see #add(BitCountProducer)
+     */
+    default boolean merge(final Hasher hasher) {
+        Objects.requireNonNull(hasher, "hasher");
+        return merge(hasher.uniqueIndices(getShape()));
+    }
+
+    /**
+     * Merges the specified index producer into this Bloom filter.
+     *
+     * <p>Specifically: all counts for the indexes identified by the {@code indexProducer} will be incremented by 1,</p>
+     *
+     * <p>This method will return {@code true} if the filter is valid after the operation.</p>
+     *
+     * <p>Note: Indices that are returned multiple times will be incremented multiple times.</p>
+     *
+     * @param indexProducer the IndexProducer
+     * @return {@code true} if the removal was successful and the state is valid
+     * @see #isValid()
+     * @see #add(BitCountProducer)
+     */
+    default boolean merge(final IndexProducer indexProducer) {
+        Objects.requireNonNull(indexProducer, "indexProducer");
+        try {
+            return add(BitCountProducer.from(indexProducer));
+        } catch (IndexOutOfBoundsException e) {
+            throw new IllegalArgumentException(
+                    String.format("Filter only accepts values in the [0,%d) range", getShape().getNumberOfBits()), e);
+        }
+    }
+
+    /**
+     * Merges the specified BitMap producer into this Bloom filter.
+     *
+     * <p>Specifically: all counts for the indexes identified by the {@code bitMapProducer} will be incremented by 1,</p>
+     *
+     * <p>This method will return {@code true} if the filter is valid after the operation.</p>
+     *
+     * @param bitMapProducer the BitMapProducer
+     * @return {@code true} if the removal was successful and the state is valid
+     * @see #isValid()
+     * @see #add(BitCountProducer)
+     */
+    default boolean merge(final BitMapProducer bitMapProducer) {
+        Objects.requireNonNull(bitMapProducer, "bitMapProducer");
+        return merge(IndexProducer.fromBitMapProducer(bitMapProducer));
+    }
+
     /**
      * Removes the specified Bloom filter from this Bloom filter.
      *
@@ -92,12 +172,15 @@ public interface CountingBloomFilter extends BloomFilter, BitCountProducer {
      * @see #isValid()
      * @see #subtract(BitCountProducer)
      */
-    boolean remove(BloomFilter other);
+    default boolean remove(final BloomFilter other) {
+        Objects.requireNonNull(other, "other");
+        return remove((IndexProducer) other);
+    }
 
     /**
-     * Removes the specified hasher from the Bloom filter from this Bloom filter.
+     * Removes the unique values from the specified hasher from this Bloom filter.
      *
-     * <p>Specifically all counts for the indices produced by the {@code hasher} will be
+     * <p>Specifically all counts for the unique indices produced by the {@code hasher} will be
      * decremented by 1.</p>
      *
      * <p>For HasherCollections each enclosed Hasher will be considered a single item and decremented
@@ -110,7 +193,53 @@ public interface CountingBloomFilter extends BloomFilter, BitCountProducer {
      * @see #isValid()
      * @see #subtract(BitCountProducer)
      */
-    boolean remove(Hasher hasher);
+    default boolean remove(final Hasher hasher) {
+        Objects.requireNonNull(hasher, "hasher");
+        return remove(hasher.uniqueIndices(getShape()));
+    }
+
+    /**
+     * Removes the values from the specified IndexProducer from the Bloom filter from this Bloom filter.
+     *
+     * <p>Specifically all counts for the unique indices produced by the {@code hasher} will be
+     * decremented by 1.</p>
+     *
+     * <p>This method will return {@code true} if the filter is valid after the operation.</p>
+     *
+     * <p>Node: This method expects index producers that produce unique values.</p>
+     *
+     * @param indexProducer the IndexProducer to provide the indexes
+     * @return {@code true} if the removal was successful and the state is valid
+     * @see #isValid()
+     * @see #subtract(BitCountProducer)
+     */
+    default boolean remove(final IndexProducer indexProducer) {
+        Objects.requireNonNull(indexProducer, "indexProducer");
+        try {
+            return subtract(BitCountProducer.from(indexProducer));
+        } catch (IndexOutOfBoundsException e) {
+            throw new IllegalArgumentException(
+                    String.format("Filter only accepts values in the [0,%d) range", getShape().getNumberOfBits()));
+        }
+    }
+
+    /**
+     * Removes the specified BitMapProducer from this Bloom filter.
+     *
+     * <p>Specifically all counts for the indices produced by the {@code bitMapProducer} will be
+     * decremented by 1.</p>
+     *
+     * <p>This method will return {@code true} if the filter is valid after the operation.</p>
+     *
+     * @param bitMapProducer the BitMapProducer to provide the indexes
+     * @return {@code true} if the removal was successful and the state is valid
+     * @see #isValid()
+     * @see #subtract(BitCountProducer)
+     */
+    default boolean remove(final BitMapProducer bitMapProducer) {
+        Objects.requireNonNull(bitMapProducer, "bitMapProducer");
+        return remove(IndexProducer.fromBitMapProducer(bitMapProducer));
+    }
 
     /**
      * Adds the specified BitCountProducer to this Bloom filter.
index 91aa43b1eff73d9789af7d3956b0e1ebf9dd3f24..8483dfc300904e41e8a664a3783348456a4ce7f9 100644 (file)
@@ -116,11 +116,15 @@ public class HasherCollection implements Hasher {
 
     /**
      * IndexProducer that will return duplicates from the collection.
-     *
      */
-    class HasherCollectionIndexProducer implements IndexProducer {
+    private class HasherCollectionIndexProducer implements IndexProducer {
         private final Shape shape;
 
+        /**
+         * Create an instance.
+         *
+         * @param shape The shape for the filter.
+         */
         HasherCollectionIndexProducer(Shape shape) {
             this.shape = shape;
         }
index ca6ac6e8cd831ee6351139ec8657c3ad02526c02..5789285bf8074879d8fe3a4ef74252f8ed7e16c7 100644 (file)
@@ -39,7 +39,7 @@ public interface IndexProducer {
      *
      * <p>Any exceptions thrown by the action are relayed to the caller.</p>
      *
-     * <p>Indices ordering is not guaranteed</p>
+     * <p>Indices ordering and uniqueness is not guaranteed.</p>
      *
      * @param predicate the action to be performed for each non-zero bit index.
      * @return {@code true} if all indexes return true from consumer, {@code false} otherwise.
@@ -103,6 +103,9 @@ public interface IndexProducer {
 
     /**
      * Return a copy of the IndexProducer data as an int array.
+     *
+     * <p>Indices ordering and uniqueness is not guaranteed.</p>
+     *
      * <p><em>
      * The default implementation of this method is slow.  It is recommended
      * that implementing classes reimplement this method.
index b78ca999af0827bf19958c1db50d8c73afa58837..df5ee707beb87b05c6b572a3c90fcb0ca59a7b7f 100644 (file)
@@ -55,58 +55,6 @@ public final class SimpleBloomFilter implements BloomFilter {
         this.cardinality = 0;
     }
 
-    /**
-     * Creates an instance that is equivalent to {@code other}.
-     *
-     * @param other The bloom filter to copy.
-     */
-    public SimpleBloomFilter(BloomFilter other) {
-        Objects.requireNonNull(other, "other");
-        this.shape = other.getShape();
-        this.bitMap = new long[BitMap.numberOfBitMaps(shape.getNumberOfBits())];
-        this.cardinality = 0;
-        if (other.isSparse()) {
-            merge((IndexProducer) other);
-        } else {
-            merge((BitMapProducer) other);
-        }
-    }
-
-    /**
-     * Creates a populated instance.
-     * @param shape The shape for the filter.
-     * @param hasher the Hasher to initialize the filter with.
-     */
-    public SimpleBloomFilter(final Shape shape, Hasher hasher) {
-        this(shape);
-        Objects.requireNonNull(hasher, "hasher");
-        merge(hasher);
-    }
-
-    /**
-     * Creates a populated instance.
-     * @param shape The shape for the filter.
-     * @param indices the IndexProducer to initialize the filter with.
-     * @throws IllegalArgumentException if producer sends illegal value.
-     */
-    public SimpleBloomFilter(final Shape shape, IndexProducer indices) {
-        this(shape);
-        Objects.requireNonNull(indices, "indices");
-        merge(indices);
-    }
-
-    /**
-     * Creates a populated instance.
-     * @param shape The shape for the filter.
-     * @param bitMaps the BitMapProducer to initialize the filter with.
-     * @throws IllegalArgumentException if the producer returns too many or too few bit maps.
-     */
-    public SimpleBloomFilter(final Shape shape, BitMapProducer bitMaps) {
-        this(shape);
-        Objects.requireNonNull(bitMaps, "bitMaps");
-        merge(bitMaps);
-    }
-
     /**
      * Copy constructor for {@code copy()} use.
      * @param source
@@ -117,6 +65,12 @@ public final class SimpleBloomFilter implements BloomFilter {
         this.cardinality = source.cardinality;
     }
 
+    @Override
+    public void clear() {
+        Arrays.fill(bitMap, 0L);
+        cardinality = 0;
+    }
+
     @Override
     public long[] asBitMapArray() {
         return Arrays.copyOf(bitMap, bitMap.length);
@@ -133,29 +87,24 @@ public final class SimpleBloomFilter implements BloomFilter {
         return new SimpleBloomFilter(this);
     }
 
-    /**
-     * Performs a merge using an IndexProducer.
-     * @param indexProducer the IndexProducer to merge from.
-     * @throws IllegalArgumentException if producer sends illegal value.
-     */
-    private void merge(IndexProducer indexProducer) {
+    @Override
+    public boolean merge(IndexProducer indexProducer) {
+        Objects.requireNonNull(indexProducer, "indexProducer");
         indexProducer.forEachIndex(idx -> {
             if (idx < 0 || idx >= shape.getNumberOfBits()) {
                 throw new IllegalArgumentException(String.format(
-                        "IndexProducer should only send values in the range[0,%s]", shape.getNumberOfBits() - 1));
+                        "IndexProducer should only send values in the range[0,%s)", shape.getNumberOfBits()));
             }
             BitMap.set(bitMap, idx);
             return true;
         });
         cardinality = -1;
+        return true;
     }
 
-    /**
-     * Performs a merge using an BitMapProducer.
-     * @param bitMapProducer the BitMapProducer to merge from.
-     * @throws IllegalArgumentException if producer sends illegal value.
-     */
-    private void merge(BitMapProducer bitMapProducer) {
+    @Override
+    public boolean merge(BitMapProducer bitMapProducer) {
+        Objects.requireNonNull(bitMapProducer, "bitMapProducer");
         try {
             int[] idx = new int[1];
             bitMapProducer.forEachBitMap(value -> {
@@ -167,7 +116,7 @@ public final class SimpleBloomFilter implements BloomFilter {
             int idxLimit = BitMap.getLongIndex(shape.getNumberOfBits());
             if (idxLimit < idx[0]) {
                 throw new IllegalArgumentException(String.format(
-                        "BitMapProducer set a bit higher than the limit for the shape: %s", shape.getNumberOfBits()));
+                        "BitMapProducer set a bit higher than the limit for the shape: %s", shape.getNumberOfBits() - 1));
             }
             if (idxLimit == idx[0]) {
                 long excess = (bitMap[idxLimit] >> shape.getNumberOfBits());
@@ -182,19 +131,19 @@ public final class SimpleBloomFilter implements BloomFilter {
             throw new IllegalArgumentException(
                     String.format("BitMapProducer should send at most %s maps", bitMap.length), e);
         }
+        return true;
     }
 
     @Override
     public boolean merge(Hasher hasher) {
         Objects.requireNonNull(hasher, "hasher");
-        merge(hasher.indices(shape));
-        return true;
+        return merge(hasher.indices(shape));
     }
 
     @Override
     public boolean merge(BloomFilter other) {
         Objects.requireNonNull(other, "other");
-        if (other.isSparse()) {
+        if ((other.characteristics() & SPARSE) != 0) {
             merge((IndexProducer) other);
         } else {
             merge((BitMapProducer) other);
@@ -208,8 +157,8 @@ public final class SimpleBloomFilter implements BloomFilter {
     }
 
     @Override
-    public boolean isSparse() {
-        return false;
+    public int characteristics() {
+        return 0;
     }
 
     @Override
index 794e3bcdaaf4e48d8c0e715a7136e5d8f426228e..fdea9b469524c3f965c85ae839c8b8a785e7ece8 100644 (file)
@@ -49,71 +49,9 @@ public final class SparseBloomFilter implements BloomFilter {
         this.indices = new TreeSet<>();
     }
 
-    /**
-     * Creates an instance that is equivalent to {@code other}.
-     *
-     * @param other The bloom filter to copy.
-     */
-    public SparseBloomFilter(BloomFilter other) {
-        Objects.requireNonNull(other, "other");
-        this.shape = other.getShape();
-        this.indices = new TreeSet<>();
-        if (other.isSparse()) {
-            merge((IndexProducer) other);
-        } else {
-            merge(IndexProducer.fromBitMapProducer(other));
-        }
-    }
-
-    private void checkIndices(Shape shape) {
-        if (this.indices.floor(-1) != null || this.indices.ceiling(shape.getNumberOfBits()) != null) {
-            throw new IllegalArgumentException(
-                    String.format("Filter only accepts values in the [0,%d) range", shape.getNumberOfBits()));
-        }
-    }
-
-    /**
-     * Constructs a populated Bloom filter.
-     * @param shape the shape for the bloom filter.
-     * @param hasher the hasher to provide the initial data.
-     */
-    public SparseBloomFilter(final Shape shape, Hasher hasher) {
-        this(shape);
-        Objects.requireNonNull(hasher, "hasher");
-        hasher.indices(shape).forEachIndex(this::add);
-        checkIndices(shape);
-    }
-
-    /**
-     * Constructs a populated Bloom filter.
-     * @param shape the shape of the filter.
-     * @param indices an index producer for the indices to to enable.
-     * @throws IllegalArgumentException if indices contains a value greater than the number
-     * of bits in the shape.
-     */
-    public SparseBloomFilter(Shape shape, IndexProducer indices) {
-        this(shape);
-        Objects.requireNonNull(indices, "indices");
-        indices.forEachIndex(this::add);
-        checkIndices(shape);
-    }
-
-    /**
-     * Constructs a populated Bloom filter.
-     * @param shape the shape of the filter.
-     * @param bitMaps a BitMapProducer for the bit maps to add.
-     * @throws IllegalArgumentException if the bit maps contain a value greater than the number
-     * of bits in the shape.
-     */
-    public SparseBloomFilter(Shape shape, BitMapProducer bitMaps) {
-        this(shape);
-        Objects.requireNonNull(bitMaps, "bitMaps");
-        merge(IndexProducer.fromBitMapProducer(bitMaps));
-    }
-
     private SparseBloomFilter(SparseBloomFilter source) {
         shape = source.shape;
-        indices = new TreeSet<Integer>(source.indices);
+        indices = new TreeSet<>(source.indices);
     }
 
     @Override
@@ -140,23 +78,27 @@ public final class SparseBloomFilter implements BloomFilter {
         return true;
     }
 
-    /**
-     * Performs a merge using an IndexProducer.
-     * @param indexProducer the IndexProducer to merge from.
-     * @throws IllegalArgumentException if producer sends illegal value.
-     */
-    private void merge(IndexProducer indexProducer) {
+    @Override
+    public boolean merge(IndexProducer indexProducer) {
+        Objects.requireNonNull(indexProducer, "indexProducer");
         indexProducer.forEachIndex(this::add);
         if (!this.indices.isEmpty()) {
             if (this.indices.last() >= shape.getNumberOfBits()) {
                 throw new IllegalArgumentException(String.format("Value in list %s is greater than maximum value (%s)",
-                        this.indices.last(), shape.getNumberOfBits()));
+                        this.indices.last(), shape.getNumberOfBits() - 1));
             }
             if (this.indices.first() < 0) {
                 throw new IllegalArgumentException(
                         String.format("Value in list %s is less than 0", this.indices.first()));
             }
         }
+        return true;
+    }
+
+    @Override
+    public boolean merge(BitMapProducer bitMapProducer) {
+        Objects.requireNonNull(bitMapProducer, "bitMapProducer");
+        return this.merge(IndexProducer.fromBitMapProducer(bitMapProducer));
     }
 
     @Override
@@ -169,19 +111,24 @@ public final class SparseBloomFilter implements BloomFilter {
     @Override
     public boolean merge(BloomFilter other) {
         Objects.requireNonNull(other, "other");
-        IndexProducer producer = other.isSparse() ? (IndexProducer) other : IndexProducer.fromBitMapProducer(other);
+        IndexProducer producer = (other.characteristics() & SPARSE) != 0 ? (IndexProducer) other : IndexProducer.fromBitMapProducer(other);
         merge(producer);
         return true;
     }
 
+    @Override
+    public void clear() {
+        indices.clear();
+    }
+
     @Override
     public Shape getShape() {
         return shape;
     }
 
     @Override
-    public boolean isSparse() {
-        return true;
+    public int characteristics() {
+        return SPARSE;
     }
 
     @Override
@@ -208,7 +155,7 @@ public final class SparseBloomFilter implements BloomFilter {
          * because our indices are always in order we can shorten the time necessary to
          * create the longs for the consumer
          */
-        // the currenlty constructed bitMap
+        // the currently constructed bitMap
         long bitMap = 0;
         // the bitmap we are working on
         int idx = 0;
index c2072545615f928f781572bd1bbffed704e4fcd9..36d6ce91651c83c12e1e26e8ab3151705e29f7ef 100644 (file)
  *
  * <h2>Background:</h2>
  *
- * <p>The Bloom filter is a probabilistic data structure that indicates where things are not.
- * Conceptually it is a bit vector. You create a Bloom filter by creating hashes
- * and converting those to enabled bits in the vector. Multiple Bloom filters may be merged
- * together into one Bloom filter.  It is possible to test if a filter {@code B} has merged into
- * another filter {@code A} by verifying that {@code (A & B) == B}.</p>
- *
- * <p>Bloom filters are generally used where hash
- * tables would be too large, or as a filter front end for longer processes. For example
- * most browsers have a Bloom filter that is built from all known bad URLs (ones that
- * serve up malware). When you enter a URL the browser builds a Bloom filter and checks to
- * see if it is "in" the bad URL filter. If not the URL is good, if it matches, then the
- * expensive lookup on a remote system is made to see if it actually is in the list. There
- * are lots of other uses, and in most cases the reason is to perform a fast check as a
- * gateway for a longer operation. </p>
+ * <p>The Bloom filter is a probabilistic data structure that indicates where things are not. Conceptually it is a bit
+ * vector. You create a Bloom filter by creating hashes and converting those to enabled bits in the vector. Multiple
+ * Bloom filters may be merged together into one Bloom filter. It is possible to test if a filter {@code B} has merged
+ * into another filter {@code A} by verifying that {@code (A & B) == B}.</p>
+ *
+ * <p>Bloom filters are generally used where hash tables would be too large, or as a filter front end for longer processes.
+ * For example most browsers have a Bloom filter that is built from all known bad URLs (ones that serve up malware).
+ * When you enter a URL the browser builds a Bloom filter and checks to see if it is "in" the bad URL filter. If not the
+ * URL is good, if it matches, then the expensive lookup on a remote system is made to see if it actually is in the
+ * list. There are lots of other uses, and in most cases the reason is to perform a fast check as a gateway for a longer
+ * operation.</p>
  *
  * <h3>BloomFilter</h3>
  *
- * <p>The Bloom filter architecture here is designed so that the implementation of the storage of bits is abstracted.
+ * <p>The Bloom filter architecture here is designed for speed of execution, so some methods like {@code merge}, {@code remove},
+ * {@code add}, and {@code subtract} may throw exceptions.  Once an exception is thrown the state of the Bloom filter is unknown.
+ * The choice to use not use atomic transactions was made to achieve maximum performance under correct usage.</p>
+ *
+ * <p>In addition the architecture is designed so that the implementation of the storage of bits is abstracted.
  * Programs that utilize the Bloom filters may use the {@code BitMapProducer} or {@code IndexProducer} to retrieve a
- * representation of the internal structure.  Additional methods are available in the {@code BitMap} to assist in
+ * representation of the internal structure. Additional methods are available in the {@code BitMap} to assist in
  * manipulation of the representations.</p>
  *
- * <p>The bloom filter code is an interface that requires implementation of 6 methods:</p>
+ * <p>The bloom filter code is an interface that requires implementation of 9 methods:</p>
  * <ul>
- * <li>{@code cardinality()}
- * returns the number of bits enabled in the Bloom filter.</li>
+ * <li>{@link BloomFilter#cardinality()} returns the number of bits enabled in the Bloom filter.</li>
  *
- * <li>{@code contains(BitMapProducer)} which
- * returns true if the bits specified by the bit maps generated by the BitMapProducer are enabled in the Bloom filter.</li>
+ * <li>{@link BloomFilter#characteristics()} which returns an integer of characteristics flags.</li>
  *
- *  <li>{@code contains(IndexProducer)} which
- * returns true if the bits specified by the indices generated by IndexProducer are enabled in the Bloom filter.</li>
+ * <li>{@link BloomFilter#clear()} which resets the Bloomfilter to its initial empty state.</li>
  *
- * <li>{@code getShape()} which
- * returns the shape the Bloom filter was created with.</li>
-
- * <li>{@code isSparse()} which
- * returns true if an the implementation tracks indices natively, false if bit maps are used.  In cases where
- * neither are used the {@code isSparse} return value should reflect which is faster to produce.</li>
+ * <li>{@link BloomFilter#contains(IndexProducer)} which returns true if the bits specified by the indices generated by
+ * IndexProducer are enabled in the Bloom filter.</li>
+ *
+ * <li>{@link BloomFilter#copy()} which returns a fresh copy of the bitmap.</li>
+ *
+ * <li>{@link BloomFilter#getShape()} which returns the shape the Bloom filter was created with.</li>
+ *
+ * <li>{@link BloomFilter#merge(BitMapProducer)} which merges the BitMaps from the BitMapProducer into the internal
+ * representation of the Bloom filter.</li>
  *
- * <li>{@code mergeInPlace(BloomFilter)} which
- * utilizes either the {@code BitMapProducer} or {@code IndexProducer} from the argument to enable extra bits
- * in the internal representation of the Bloom filter.</li>
+ * <li>{@link BloomFilter#merge(IndexProducer)} which merges the indices from the IndexProducer into the internal
+ * representation of the Bloom filter.</li>
  * </ul>
  *
- * <p>Other methods should be implemented where they can be done so more efficiently than the default implementations.
- * </p>
+ * <p>Other methods should be implemented where they can be done so more efficiently than the default implementations.</p>
  *
  * <h3>CountingBloomFilter</h3>
  *
  * <p>The counting bloom filter extends the Bloom filter by counting the number of times a specific bit has been
- * enabled or disabled.  This allows the removal (opposite of merge) of Bloom filters at the expense of additional
+ * enabled or disabled. This allows the removal (opposite of merge) of Bloom filters at the expense of additional
  * overhead.</p>
  *
  * <h3>Shape</h3>
  *
  * <h3>Hasher</h3>
  *
- * <p>A Hasher converts bytes into a series of integers based on a Shape.  With the exception of the HasherCollecton,
- *  each hasher represents one item being added to the Bloom filter.  The HasherCollection represents the
- *  number of items as the sum of the number of items represented by the Hashers in the collection.</p>
+ * <p>A Hasher converts bytes into a series of integers based on a Shape. With the exception of the HasherCollecton,
+ * each hasher represents one item being added to the Bloom filter. The HasherCollection represents the number of
+ * items as the sum of the number of items represented by the Hashers in the collection.</p>
  *
- *  <p>The SimpleHasher uses a combinatorial generation technique to create the integers. It is easily
- *  initialized by using a standard {@code MessageDigest} or other Hash function to hash the item to insert and
- *  then splitting the hash bytes in half and considering each as a long value.</p>
+ * <p>The EnhancedDoubleHasher uses a combinatorial generation technique to create the integers. It is easily
+ * initialized by using a byte array returned by the standard {@code MessageDigest} or other hash function to
+ * initialize the Hasher. Alternatively a pair of a long values may also be used.</p>
  *
- *  <p>Other implementations of the Hasher are easy to implement, and should make use of the {@code Hasher.Filter}
- *  and/or {@code Hasher.FileredIntConsumer} classes to filter out duplicate indices.</p>
+ * <p>Other implementations of the Hasher are easy to implement, and should make use of the {@code Hasher.Filter}
+ * and/or {@code Hasher.FileredIntConsumer} classes to filter out duplicate indices when implementing
+ * {@code Hasher.uniqueIndices(Shape)}.</p>
  *
  * <h2>References</h2>
  *
  * <ol>
- * <li> https://www.eecs.harvard.edu/~michaelm/postscripts/tr-02-05.pdf</li>
- * <li> https://github.com/apache/cassandra/blob/trunk/src/java/org/apache/cassandra/utils/BloomFilter.java#L60</li>
+ * <li>https://www.eecs.harvard.edu/~michaelm/postscripts/tr-02-05.pdf</li>
+ * <li>https://github.com/apache/cassandra/blob/trunk/src/java/org/apache/cassandra/utils/BloomFilter.java#L60</li>
  * </ol>
  *
  * @since 4.5
index 86b340a7614185c3c0f1a093f348a9c36086a101..5a50c6bed9390117c35bc958a6f1012e2893e66e 100644 (file)
@@ -149,8 +149,8 @@ public class ComparatorPredicate<T> implements Predicate<T>, Serializable {
      * <li>{@code comparator.compare(object, input) &lt;= 0 &amp;&amp; criterion == LESS_OR_EQUAL}</li>
      * </ul>
      *
-     * @see org.apache.commons.collections4.Predicate#evaluate(java.lang.Object)
-     * @see java.util.Comparator#compare(java.lang.Object first, java.lang.Object second)
+     * @see org.apache.commons.collections4.Predicate#evaluate(Object)
+     * @see java.util.Comparator#compare(Object first, Object second)
      *
      * @param target  the target object to compare to
      * @return {@code true} if the comparison succeeds according to the selected criterion
index 161bfba1775e47f3303882a3e4a6be04b5696934..5dda409800bc78fe2c6059200499d88efb1fbc62 100644 (file)
@@ -202,7 +202,7 @@ public class CollatingIterator<E> implements Iterator<E> {
      * Sets the {@link Comparator} by which collation occurs. If you
      * would like to use the natural sort order (or, in other words,
      * if the elements in the iterators are implementing the
-     * {@link java.lang.Comparable} interface), then use the
+     * {@link Comparable} interface), then use the
      * {@link org.apache.commons.collections4.comparators.ComparableComparator}.
      *
      * @param comp the {@link Comparator} to set
index a1c739139b145a35b1a36465f9eed26457d784f3..8d2487d5ffe3258ea205bcff59aa6cea30d2d3e7 100644 (file)
@@ -55,14 +55,14 @@ import org.apache.commons.collections4.trie.analyzer.StringKeyAnalyzer;
  * are suited only to variable length keys.
  * </p>
  *
- * @param <E> the type of the values in this map
+ * @param <V> the type of the values in this map
  *
  * @see <a href="http://en.wikipedia.org/wiki/Radix_tree">Radix Tree</a>
  * @see <a href="http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Tree/PATRICIA">PATRICIA</a>
  * @see <a href="http://www.imperialviolet.org/binary/critbit.pdf">Crit-Bit Tree</a>
  * @since 4.0
  */
-public class PatriciaTrie<E> extends AbstractPatriciaTrie<String, E> {
+public class PatriciaTrie<V> extends AbstractPatriciaTrie<String, V> {
 
     private static final long serialVersionUID = 4446367780901817838L;
 
@@ -70,7 +70,7 @@ public class PatriciaTrie<E> extends AbstractPatriciaTrie<String, E> {
         super(new StringKeyAnalyzer());
     }
 
-    public PatriciaTrie(final Map<? extends String, ? extends E> m) {
+    public PatriciaTrie(final Map<? extends String, ? extends V> m) {
         super(new StringKeyAnalyzer(), m);
     }
 
index 9766d0865905fe5f58213fe782618f124639b138..ba57040e9a5b9fbe6ee8fc0a8e8426018d970762 100644 (file)
@@ -263,7 +263,7 @@ have changed.
 <li>"SetUniqueList#subList()#contains(Object)" will now correctly check the subList rather than the parent list. Thanks to Christian Semrau.</li>
 <li>"SetUniqueList#set(int, Object)" will now correctly enforce the uniqueness constraint. Thanks to RafaƂ Figas,Bjorn Townsend.</li>
 <li>Improved javadoc for "Unmodifiable*" classes wrt behavior when the users tries to modify the collection. Thanks to Emmanuel Bourg.</li>
-<li>"CaseInsensitiveMap" will now convert input strings to lower-case in a locale-independant manner. Thanks to Benjamin Bentmann.</li>
+<li>"CaseInsensitiveMap" will now convert input strings to lower-case in a locale-independent manner. Thanks to Benjamin Bentmann.</li>
 <li>Fixed javadoc for "ListUtils#transformedList(List)" to clarify that existing objects in the list are not transformed. Thanks to Paul Benedict.</li>
 <li>"MultiKey" will now be correctly serialized/de-serialized. Thanks to Joerg Schaible.</li>
 <li>Fixed javadoc for methods "firstKey()" and "lastKey()" in class "AbstractLinkedMap". Thanks to Lisen Mu.</li>
index 05e93dc98601b78a0eaa1efe0516538ab6fbf199..62e6df003b966097722cd69799a8e5449b8a6cdd 100644 (file)
@@ -674,6 +674,10 @@ public abstract class AbstractBagTest<T> extends AbstractCollectionTest<T> {
             super.verify();
         }
 
+        @Override
+        protected int getIterationBehaviour(){
+            return AbstractBagTest.this.getIterationBehaviour();
+        }
     }
 
     /**
index 06cd875d49eb1fb496e2ced82e760dc2ae2bb79d..e01b2d56e7b4f7741e7498b5d2bd28fd6d4b806a 100644 (file)
@@ -46,6 +46,11 @@ public class SynchronizedBagTest<T> extends AbstractBagTest<T> {
         return "4";
     }
 
+    @Override
+    protected int getIterationBehaviour(){
+        return UNORDERED;
+    }
+
 //    public void testCreate() throws Exception {
 //        Bag<T> bag = makeObject();
 //        writeExternalFormToDisk((java.io.Serializable) bag, "src/test/resources/data/test/SynchronizedBag.emptyCollection.version4.obj");
index 5894b7c376d3f7d71499a78f881272841c1ce7cd..e51f90105e7ffd1ce94c7b5be9f7079f67d77a76 100644 (file)
@@ -63,7 +63,7 @@ public abstract class AbstractBitCountProducerTest extends AbstractIndexProducer
     /**
      * Determines if empty tests should be run.  Some producers do not implement an empty
      * version.  Tests for those classes should return false.
-     * @return
+     * @return true if the empty tests are supported
      */
     protected boolean supportsEmpty() {
         return true;
index d8ceea079de6683e3e43e0dfdfbb45c087aca733..cc196a00a6031cf4aadc28a91fad76dc1718fc76 100644 (file)
  */
 package org.apache.commons.collections4.bloomfilter;
 
+import static org.junit.jupiter.api.Assertions.assertArrayEquals;
 import static org.junit.jupiter.api.Assertions.assertEquals;
 import static org.junit.jupiter.api.Assertions.assertFalse;
+import static org.junit.jupiter.api.Assertions.assertNotEquals;
 import static org.junit.jupiter.api.Assertions.assertThrows;
 import static org.junit.jupiter.api.Assertions.assertTrue;
 
 import java.util.ArrayList;
+import java.util.BitSet;
 import java.util.List;
+
 import org.junit.jupiter.api.Test;
 
 /**
@@ -69,7 +73,11 @@ public abstract class AbstractBloomFilterTest<T extends BloomFilter> {
      * @param hasher the hasher to use to create the filter.
      * @return a BloomFilter implementation.
      */
-    protected abstract T createFilter(Shape shape, Hasher hasher);
+    protected final T createFilter(Shape shape, Hasher hasher) {
+        T bf = createEmptyFilter(shape);
+        bf.merge(hasher);
+        return bf;
+    }
 
     /**
      * Create the BloomFilter implementation we are testing.
@@ -78,7 +86,11 @@ public abstract class AbstractBloomFilterTest<T extends BloomFilter> {
      * @param producer A BitMap producer to build the filter with.
      * @return a BloomFilter implementation.
      */
-    protected abstract T createFilter(Shape shape, BitMapProducer producer);
+    protected final T createFilter(Shape shape, BitMapProducer producer) {
+        T bf = createEmptyFilter(shape);
+        bf.merge(producer);
+        return bf;
+    }
 
     /**
      * Create the BloomFilter implementation we are testing.
@@ -87,57 +99,87 @@ public abstract class AbstractBloomFilterTest<T extends BloomFilter> {
      * @param producer An Index producer to build the filter with.
      * @return a BloomFilter implementation.
      */
-    protected abstract T createFilter(Shape shape, IndexProducer producer);
+    protected final T createFilter(Shape shape, IndexProducer producer) {
+        T bf = createEmptyFilter(shape);
+        bf.merge(producer);
+        return bf;
+    }
 
     /**
      *
      */
     @Test
-    public void testConstructWithBadHasher() {
+    public void testMergeWithBadHasher() {
         // value too large
+        final BloomFilter f = createEmptyFilter(getTestShape());
         assertThrows(IllegalArgumentException.class,
-                () -> createFilter(getTestShape(), new BadHasher(getTestShape().getNumberOfBits())));
+                () -> f.merge(new BadHasher(getTestShape().getNumberOfBits())));
         // negative value
-        assertThrows(IllegalArgumentException.class, () -> createFilter(getTestShape(), new BadHasher(-1)));
+        BloomFilter f2 = createEmptyFilter(getTestShape());
+        assertThrows(IllegalArgumentException.class, () -> f2.merge(new BadHasher(-1)));
     }
 
     @Test
-    public void testConstructWitBitMapProducer() {
-        long[] values = { from11Value, 0x9L };
-        BloomFilter f = createFilter(getTestShape(), BitMapProducer.fromBitMapArray(values));
-        List<Long> lst = new ArrayList<>();
-        for (long l : values) {
-            lst.add(l);
+    public void testMergeWithHasher() {
+        for (int i = 0; i < 5; i++) {
+            final BloomFilter f = createEmptyFilter(getTestShape());
+            int[] expected = DefaultIndexProducerTest.generateIntArray(getTestShape().getNumberOfHashFunctions(), getTestShape().getNumberOfBits());
+            Hasher hasher = new ArrayHasher(expected);
+            f.merge(hasher);
+            // create sorted unique array of expected values
+            assertArrayEquals(DefaultIndexProducerTest.unique(expected), f.asIndexArray( ));
         }
-        assertTrue(f.forEachBitMap(l -> {
-            return lst.remove(Long.valueOf(l));
-        }));
-        assertTrue(lst.isEmpty());
+    }
 
-        BitMapProducer badProducer = BitMapProducer.fromBitMapArray(0L, Long.MAX_VALUE);
+    @Test
+    public void testMergeWithBitMapProducer() {
+        for (int i = 0; i < 5; i++) {
+            long[] values = new long[2];
+            for (int idx :  DefaultIndexProducerTest.generateIntArray(getTestShape().getNumberOfHashFunctions(), getTestShape().getNumberOfBits())) {
+                BitMap.set(values, idx);
+            }
+            BloomFilter f = createFilter(getTestShape(), BitMapProducer.fromBitMapArray(values));
+            List<Long> lst = new ArrayList<>();
+            for (long l : values) {
+                lst.add(l);
+            }
+            assertTrue(f.forEachBitMap(l -> {
+                return lst.remove(Long.valueOf(l));
+            }));
+            assertTrue(lst.isEmpty());
+        }
         // values too large
-        assertThrows(IllegalArgumentException.class, () -> createFilter(getTestShape(), badProducer));
+        final BitMapProducer badProducer = BitMapProducer.fromBitMapArray(0L, Long.MAX_VALUE);
+        final BloomFilter bf = createEmptyFilter(getTestShape());
+        assertThrows(IllegalArgumentException.class, () -> bf.merge(badProducer));
+
+        // test where merged bits exceed expected bits but both bitmaps are the same length.
+        final BitMapProducer badProducer2 = BitMapProducer.fromBitMapArray(0x80_00_00_00_00_00_00_00L);
+        final BloomFilter bf2 = createEmptyFilter(Shape.fromKM(3, 32));
+        assertThrows(IllegalArgumentException.class, () -> bf2.merge(badProducer2));
     }
 
     @Test
-    public void testConstructWithIndexProducer() {
-        int[] values = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17 };
-        BloomFilter f = createFilter(getTestShape(), IndexProducer.fromIndexArray(values));
-        List<Integer> lst = new ArrayList<>();
-        for (int i : values) {
-            lst.add(i);
+    public void testMergeWithIndexProducer() {
+        for (int i = 0; i < 5; i++) {
+            int[] values = DefaultIndexProducerTest.generateIntArray(getTestShape().getNumberOfHashFunctions(), getTestShape().getNumberOfBits());
+            BloomFilter f = createFilter(getTestShape(), IndexProducer.fromIndexArray(values));
+            BitSet uniqueValues = DefaultIndexProducerTest.uniqueSet(values);
+            assertTrue(f.forEachIndex(idx -> {
+                final boolean result = uniqueValues.get(idx);
+                uniqueValues.clear(idx);
+                return result;
+            }));
+            assertTrue(uniqueValues.isEmpty());
         }
-        assertTrue(f.forEachIndex(i -> {
-            return lst.remove(Integer.valueOf(i));
-        }));
-        assertTrue(lst.isEmpty());
-
         // value to large
-        assertThrows(IllegalArgumentException.class, () -> createFilter(getTestShape(),
-                IndexProducer.fromIndexArray(new int[] { getTestShape().getNumberOfBits() })));
+        final BloomFilter f1 = createEmptyFilter(getTestShape());
+        assertThrows(IllegalArgumentException.class,
+                () -> f1.merge(IndexProducer.fromIndexArray(new int[] { getTestShape().getNumberOfBits() })));
         // negative value
+        final BloomFilter f2 = createEmptyFilter(getTestShape());
         assertThrows(IllegalArgumentException.class,
-                () -> createFilter(getTestShape(), IndexProducer.fromIndexArray(new int[] { -1 })));
+                () -> f2.merge(IndexProducer.fromIndexArray(new int[] { -1 })));
     }
 
     @Test
@@ -178,10 +220,16 @@ public abstract class AbstractBloomFilterTest<T extends BloomFilter> {
         assertTrue(bf4.contains(bf1));
     }
 
+    @Test
+    public void testClear() {
+        BloomFilter bf1 = createFilter(getTestShape(), from1);
+        assertNotEquals(0, bf1.cardinality());
+        bf1.clear();
+        assertEquals(0, bf1.cardinality());
+    }
+
     /**
      * Tests that the andCardinality calculations are correct.
-     *
-     * @param filterFactory the factory function to create the filter
      */
     @Test
     public final void testEstimateIntersection() {
@@ -200,8 +248,6 @@ public abstract class AbstractBloomFilterTest<T extends BloomFilter> {
 
     /**
      * Tests that the andCardinality calculations are correct.
-     *
-     * @param filterFactory the factory function to create the filter
      */
     @Test
     public final void testEstimateUnion() {
@@ -223,7 +269,7 @@ public abstract class AbstractBloomFilterTest<T extends BloomFilter> {
     @Test
     public final void testEstimateN() {
         // build a filter
-        BloomFilter filter1 = new SimpleBloomFilter(getTestShape(), from1);
+        BloomFilter filter1 = createFilter(getTestShape(), from1);
         assertEquals(1, filter1.estimateN());
 
         // the data provided above do not generate an estimate that is equivalent to the
@@ -311,20 +357,20 @@ public abstract class AbstractBloomFilterTest<T extends BloomFilter> {
         assertThrows(IllegalArgumentException.class, () -> bf1.merge(new BadHasher(-1)));
 
         // test error when bloom filter returns values out of range
-        final BloomFilter bf5 = new SimpleBloomFilter(
-                Shape.fromKM(getTestShape().getNumberOfHashFunctions(), 3 * Long.SIZE),
-                new IncrementingHasher(Long.SIZE * 2, 1));
+        BloomFilter bf5 = new SimpleBloomFilter(
+                Shape.fromKM(getTestShape().getNumberOfHashFunctions(), 3 * Long.SIZE));
+        bf5.merge(new IncrementingHasher(Long.SIZE * 2, 1));
         assertThrows(IllegalArgumentException.class, () -> bf1.merge(bf5));
 
-        final BloomFilter bf6 = new SparseBloomFilter(
-                Shape.fromKM(getTestShape().getNumberOfHashFunctions(), 3 * Long.SIZE),
-                new IncrementingHasher(Long.SIZE * 2, 1));
+        BloomFilter bf6 = new SparseBloomFilter(
+                Shape.fromKM(getTestShape().getNumberOfHashFunctions(), 3 * Long.SIZE));
+        bf6.merge(new IncrementingHasher(Long.SIZE * 2, 1));
         assertThrows(IllegalArgumentException.class, () -> bf1.merge(bf6));
     }
 
-    private void assertIndexProducerConstructor(Shape shape, int[] values, int[] expected) {
+    private void assertIndexProducerMerge(Shape shape, int[] values, int[] expected) {
         IndexProducer indices = IndexProducer.fromIndexArray(values);
-        SparseBloomFilter filter = new SparseBloomFilter(shape, indices);
+        BloomFilter filter = createFilter(shape, indices);
         List<Integer> lst = new ArrayList<>();
         filter.forEachIndex(x -> {
             lst.add(x);
@@ -342,18 +388,18 @@ public abstract class AbstractBloomFilterTest<T extends BloomFilter> {
     }
 
     @Test
-    public void testIndexProducerConstructor() {
+    public void testIndexProducerMerge() {
         Shape shape = Shape.fromKM(5, 10);
 
-        assertIndexProducerConstructor(shape, new int[] { 0, 2, 4, 6, 8 }, new int[] { 0, 2, 4, 6, 8 });
+        assertIndexProducerMerge(shape, new int[] { 0, 2, 4, 6, 8 }, new int[] { 0, 2, 4, 6, 8 });
         // test duplicate values
-        assertIndexProducerConstructor(shape, new int[] { 0, 2, 4, 2, 8 }, new int[] { 0, 2, 4, 8 });
+        assertIndexProducerMerge(shape, new int[] { 0, 2, 4, 2, 8 }, new int[] { 0, 2, 4, 8 });
         // test negative values
         assertFailedIndexProducerConstructor(shape, new int[] { 0, 2, 4, -2, 8 });
         // test index too large
         assertFailedIndexProducerConstructor(shape, new int[] { 0, 2, 4, 12, 8 });
         // test no indices
-        assertIndexProducerConstructor(shape, new int[0], new int[0]);
+        assertIndexProducerMerge(shape, new int[0], new int[0]);
     }
 
     @Test
index b7ca7dd37f1eef1ae49a788ff8b51deeddd42753..48fbd92f4fa6cafaf138d02188d237c43da745fe 100644 (file)
@@ -17,6 +17,7 @@
 package org.apache.commons.collections4.bloomfilter;
 
 import static org.junit.jupiter.api.Assertions.assertFalse;
+import static org.junit.jupiter.api.Assertions.assertThrows;
 import static org.junit.jupiter.api.Assertions.assertTrue;
 import static org.junit.jupiter.api.Assertions.assertEquals;
 
@@ -94,7 +95,8 @@ public abstract class AbstractCountingBloomFilterTest<T extends CountingBloomFil
 
     @Test
     public final void testCountingBloomFilterSpecificContains() {
-        final BloomFilter bf = new SimpleBloomFilter(getTestShape(), from1);
+        final BloomFilter bf = new SimpleBloomFilter(getTestShape());
+        bf.merge(from1);
         final CountingBloomFilter bf2 = createFilter(getTestShape(), bigHasher);
 
         assertTrue(bf.contains(bf), "BF Should contain itself");
@@ -112,7 +114,8 @@ public abstract class AbstractCountingBloomFilterTest<T extends CountingBloomFil
     public final void testCountingSpecificMerge() {
         final BloomFilter bf1 = createFilter(getTestShape(), from1);
 
-        final BloomFilter bf2 = new SimpleBloomFilter(getTestShape(), from11);
+        final BloomFilter bf2 = new SimpleBloomFilter(getTestShape());
+        bf2.merge(from11);
 
         final BloomFilter bf3 = bf1.copy();
         bf3.merge(bf2);
@@ -133,7 +136,9 @@ public abstract class AbstractCountingBloomFilterTest<T extends CountingBloomFil
         assertTrue(bf5.isValid(), "Should be valid");
 
         CountingBloomFilter bf6 = bf5.copy();
-        bf6.merge(new SimpleBloomFilter(getTestShape(), from1));
+        BloomFilter bf7 = new SimpleBloomFilter(getTestShape());
+        bf7.merge(from1);
+        bf6.merge(bf7);
         assertFalse(bf6.isValid(), "Should not be valid");
     }
 
@@ -195,10 +200,13 @@ public abstract class AbstractCountingBloomFilterTest<T extends CountingBloomFil
      */
     @Test
     public final void testRemove() {
+        BloomFilter simple = new SimpleBloomFilter(getTestShape());
+        simple.merge(from11);
+
         final CountingBloomFilter bf1 = createFilter(getTestShape(), from1);
         bf1.add(BitCountProducer.from(from11.indices(getTestShape())));
 
-        assertTrue(bf1.remove(new SimpleBloomFilter(getTestShape(), from11)), "Remove should work");
+        assertTrue(bf1.remove(simple), "Remove should work");
         assertFalse(bf1.contains(from11), "Should not contain");
         assertTrue(bf1.contains(from1), "Should contain");
 
@@ -215,17 +223,45 @@ public abstract class AbstractCountingBloomFilterTest<T extends CountingBloomFil
         assertCounts(bf2, from1Counts);
 
         // test underflow
-
         final CountingBloomFilter bf3 = createFilter(getTestShape(), from1);
-
-        final BloomFilter bf4 = new SimpleBloomFilter(getTestShape(), from11);
-
-        assertFalse(bf3.remove(bf4), "Subtract should not work");
+        assertFalse(bf3.remove(simple), "Subtract should not work");
         assertFalse(bf3.isValid(), "isValid should return false");
         assertFalse(bf3.contains(from1), "Should not contain");
-        assertFalse(bf3.contains(bf4), "Should not contain");
+        assertFalse(bf3.contains(simple), "Should not contain");
 
         assertCounts(bf3, new int[] { 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 });
+
+        // with IndexProducer
+        IndexProducer ip = from11.indices(getTestShape());
+
+        final CountingBloomFilter bf4 = createFilter(getTestShape(), from1);
+        bf4.add(BitCountProducer.from(from11.indices(getTestShape())));
+
+        assertTrue(bf4.remove(ip), "Remove should work");
+        assertFalse(bf4.contains(from11), "Should not contain");
+        assertTrue(bf4.contains(from1), "Should contain");
+
+        assertCounts(bf4, from1Counts);
+
+        // with BitMapProducer
+        final BitMapProducer bmp = BitMapProducer.fromIndexProducer(ip, getTestShape().getNumberOfBits());
+        final CountingBloomFilter bf5 = createFilter(getTestShape(), from1);
+        bf5.add(BitCountProducer.from(from11.indices(getTestShape())));
+
+        assertTrue(bf5.remove(bmp), "Remove should work");
+        assertFalse(bf5.contains(from11), "Should not contain");
+        assertTrue(bf5.contains(from1), "Should contain");
+
+        assertCounts(bf5, from1Counts);
+
+        // test producer errors
+        IndexProducer ip2 = IndexProducer.fromIndexArray(1, 2, getTestShape().getNumberOfBits());
+        final CountingBloomFilter bf6 = createFilter(getTestShape(), from1);
+        assertThrows( IllegalArgumentException.class, () -> bf6.remove(ip2));
+
+        final CountingBloomFilter bf7 = createFilter(getTestShape(), from1);
+        final BitMapProducer bmp2 = BitMapProducer.fromIndexProducer(ip2, getTestShape().getNumberOfBits());
+        assertThrows( IllegalArgumentException.class, () -> bf7.remove(bmp2));
     }
 
     @Test
@@ -247,20 +283,12 @@ public abstract class AbstractCountingBloomFilterTest<T extends CountingBloomFil
         bf1.merge(hasher);
         assertEquals(6, bf1.cardinality());
         bf1.forEachCount((x, y) -> {
-            assertEquals(1, y, "Hasher in mergeInPlace results in value not equal to 1");
-            return true;
-        });
-
-        bf1 = createEmptyFilter(shape);
-        CountingBloomFilter bf2 = bf1.copy();
-        bf2.merge(hasher);
-        assertEquals(6, bf2.cardinality());
-        bf2.forEachCount((x, y) -> {
             assertEquals(1, y, "Hasher in merge results in value not equal to 1");
             return true;
         });
 
-        bf1 = createFilter(shape, hasher);
+        bf1 = createEmptyFilter(shape);
+        bf1.merge(hasher);
         bf1.remove(hasher);
         assertEquals(0, bf1.cardinality());
         assertTrue(bf1.forEachCount((x, y) -> (false)), "Hasher in removes results in value not equal to 0");
index cd5eda18c415f0d2929d66bd3274f8c69f8b3dbd..0e9fae4109fb81d26e6a971f6e26bcbce36e6590 100644 (file)
@@ -85,7 +85,7 @@ public abstract class AbstractHasherTest extends AbstractIndexProducerTest {
             count[0]++;
             return false;
         });
-        assertEquals(1, count[0], "did not exit early" );
+        assertEquals(1, count[0], "did not exit early");
     }
 
     @Test
@@ -97,8 +97,8 @@ public abstract class AbstractHasherTest extends AbstractIndexProducerTest {
         List<Integer> full = Arrays.stream(producer.asIndexArray()).boxed().collect(Collectors.toList());
         producer = hasher.uniqueIndices(shape);
         List<Integer> unique = Arrays.stream(producer.asIndexArray()).boxed().collect(Collectors.toList());
-        assertTrue( full.size() > unique.size() );
-        Set<Integer> set = new HashSet<Integer>( unique );
-        assertEquals( set.size(), unique.size() );
+        assertTrue(full.size() > unique.size());
+        Set<Integer> set = new HashSet<>(unique);
+        assertEquals(set.size(), unique.size());
     }
 }
index 54dc01c7d49d2d9f4df98d486407c1e187d36b63..ac5a6fc230d4a37b59112fa07b1a6e2af3964aa1 100644 (file)
  */
 package org.apache.commons.collections4.bloomfilter;
 
-import static org.junit.Assert.assertEquals;
-import static org.junit.jupiter.api.Assertions.assertEquals;
 import static org.junit.jupiter.api.Assertions.assertFalse;
 import static org.junit.jupiter.api.Assertions.assertTrue;
 
-import java.util.ArrayList;
-import java.util.List;
+import java.util.Arrays;
+import java.util.BitSet;
 import java.util.function.IntPredicate;
-
+import org.junit.jupiter.api.Assertions;
+import org.junit.jupiter.api.Assumptions;
 import org.junit.jupiter.api.Test;
 
 public abstract class AbstractIndexProducerTest {
 
-    public static final IntPredicate TRUE_PREDICATE = new IntPredicate() {
+    private static final IntPredicate TRUE_PREDICATE = i -> true;
+    private static final IntPredicate FALSE_PREDICATE = i -> false;
+
+    /** Flag to indicate the {@link IndexProducer#forEachIndex(IntPredicate)} is ordered. */
+    protected static final int FOR_EACH_ORDERED = 0x1;
+    /** Flag to indicate the {@link IndexProducer#forEachIndex(IntPredicate)} is distinct. */
+    protected static final int FOR_EACH_DISTINCT = 0x2;
+    /** Flag to indicate the {@link IndexProducer#asIndexArray()} is ordered. */
+    protected static final int AS_ARRAY_ORDERED = 0x4;
+    /** Flag to indicate the {@link IndexProducer#asIndexArray()} is distinct. */
+    protected static final int AS_ARRAY_DISTINCT = 0x8;
 
-        @Override
-        public boolean test(int arg0) {
+    /**
+     * An expandable list of int values.
+     */
+    private static class IntList {
+        private int size;
+        private int[] data = {0};
+
+        /**
+         * Adds the value to the list.
+         *
+         * @param value the value
+         * @return true if the list was modified
+         */
+        boolean add(int value) {
+            if (size == data.length) {
+                data = Arrays.copyOf(data, size << 1);
+            }
+            data[size++] = value;
             return true;
         }
-    };
-
-    public static final IntPredicate FALSE_PREDICATE = new IntPredicate() {
 
-        @Override
-        public boolean test(int arg0) {
-            return false;
+        /**
+         * Convert to an array.
+         *
+         * @return the array
+         */
+        int[] toArray() {
+            return Arrays.copyOf(data, size);
         }
-    };
+    }
 
     /**
      * Creates a producer with some data.
@@ -57,13 +83,22 @@ public abstract class AbstractIndexProducerTest {
      */
     protected abstract IndexProducer createEmptyProducer();
 
+    /**
+     * Gets the behaviour flags.
+     *
+     * <p>The flags indicate if the methods {@link IndexProducer#forEachIndex(IntPredicate)}
+     * and {@link IndexProducer#asIndexArray()} output sorted or distinct indices.
+     *
+     * @return the behaviour.
+     */
+    protected abstract int getBehaviour();
+
     @Test
     public final void testForEachIndex() {
-
         IndexProducer populated = createProducer();
         IndexProducer empty = createEmptyProducer();
-        assertFalse(populated.forEachIndex(FALSE_PREDICATE), "non-empty should be false");
 
+        assertFalse(populated.forEachIndex(FALSE_PREDICATE), "non-empty should be false");
         assertTrue(empty.forEachIndex(FALSE_PREDICATE), "empty should be true");
 
         assertTrue(populated.forEachIndex(TRUE_PREDICATE), "non-empty should be true");
@@ -71,40 +106,77 @@ public abstract class AbstractIndexProducerTest {
     }
 
     @Test
-    public final void testAsIndexArray() {
-        int ary[] = createEmptyProducer().asIndexArray();
-        assertEquals(0, ary.length);
+    public final void testEmptyProducer() {
+        IndexProducer empty = createEmptyProducer();
+        int ary[] = empty.asIndexArray();
+        Assertions.assertEquals(0, ary.length);
+        assertTrue(empty.forEachIndex(i -> {
+            throw new AssertionError("forEach predictate should not be called");
+        }));
+    }
 
+    /**
+     * Test the distinct indices output from the producer are consistent.
+     */
+    @Test
+    public final void testConsistency() {
         IndexProducer producer = createProducer();
-        List<Integer> lst = new ArrayList<Integer>();
-        for (int i : producer.asIndexArray()) {
-            lst.add(i);
+        BitSet bs1 = new BitSet();
+        BitSet bs2 = new BitSet();
+        Arrays.stream(producer.asIndexArray()).forEach(bs1::set);
+        producer.forEachIndex(i -> {
+            bs2.set(i);
+            return true;
+        });
+        Assertions.assertEquals(bs1, bs2);
+    }
+
+    @Test
+    public final void testBehaviourAsIndexArray() {
+        int flags = getBehaviour();
+        Assumptions.assumeTrue((flags & (AS_ARRAY_ORDERED | AS_ARRAY_DISTINCT)) != 0);
+        int[] actual = createProducer().asIndexArray();
+        if ((flags & AS_ARRAY_ORDERED) != 0) {
+            int[] expected = Arrays.stream(actual).sorted().toArray();
+            Assertions.assertArrayEquals(expected, actual);
         }
-        assertTrue(producer.forEachIndex(new IntPredicate() {
+        if ((flags & AS_ARRAY_DISTINCT) != 0) {
+            long count = Arrays.stream(actual).distinct().count();
+            Assertions.assertEquals(count, actual.length);
+        }
+    }
 
-            @Override
-            public boolean test(int value) {
-                assertTrue(lst.remove(Integer.valueOf(value)),
-                        String.format("Instance of  %d was not found in lst", value));
-                return true;
-            }
-        }));
+    @Test
+    public final void testBehaviourForEach() {
+        int flags = getBehaviour();
+        Assumptions.assumeTrue((flags & (FOR_EACH_ORDERED | FOR_EACH_DISTINCT)) != 0);
+        IntList list = new IntList();
+        createProducer().forEachIndex(list::add);
+        int[] actual = list.toArray();
+        if ((flags & FOR_EACH_ORDERED) != 0) {
+            int[] expected = Arrays.stream(actual).sorted().toArray();
+            Assertions.assertArrayEquals(expected, actual);
+        }
+        if ((flags & FOR_EACH_DISTINCT) != 0) {
+            long count = Arrays.stream(actual).distinct().count();
+            Assertions.assertEquals(count, actual.length);
+        }
     }
 
     @Test
-    public void testForIndexEarlyExit() {
+    public void testForEachIndexEarlyExit() {
         int[] passes = new int[1];
         assertFalse(createProducer().forEachIndex(i -> {
             passes[0]++;
             return false;
         }));
-        assertEquals(1, passes[0]);
+        Assertions.assertEquals(1, passes[0]);
 
         passes[0] = 0;
         assertTrue(createEmptyProducer().forEachIndex(i -> {
             passes[0]++;
             return false;
         }));
-        assertEquals(0, passes[0]);
+        Assertions.assertEquals(0, passes[0]);
     }
 }
index 86bd638b7379a1cbe1e5615a06f6a9b706e05a4f..e7141dadea8caa58f05f97e1864ee775d394289f 100644 (file)
@@ -25,28 +25,4 @@ public class ArrayCountingBloomFilterTest extends AbstractCountingBloomFilterTes
     protected ArrayCountingBloomFilter createEmptyFilter(Shape shape) {
         return new ArrayCountingBloomFilter(shape);
     }
-
-    @Override
-    protected ArrayCountingBloomFilter createFilter(Shape shape, Hasher hasher) {
-        return createFilter(shape, hasher.uniqueIndices(shape));
-    }
-
-    @Override
-    protected ArrayCountingBloomFilter createFilter(Shape shape, BitMapProducer producer) {
-        return createFilter(shape, IndexProducer.fromBitMapProducer(producer));
-    }
-
-    @Override
-    protected ArrayCountingBloomFilter createFilter(Shape shape, IndexProducer producer) {
-        ArrayCountingBloomFilter filter = createEmptyFilter(shape);
-        try {
-            filter.add(BitCountProducer.from(producer));
-            return filter;
-        } catch (ArrayIndexOutOfBoundsException e) {
-            // since ArrayCountingBloomFilter does not ahave a constructor that takes a
-            // hasher
-            // we have to duplicate the expected results here.
-            throw new IllegalArgumentException(e);
-        }
-    }
 }
diff --git a/src/test/java/org/apache/commons/collections4/bloomfilter/ArrayHasher.java b/src/test/java/org/apache/commons/collections4/bloomfilter/ArrayHasher.java
new file mode 100644 (file)
index 0000000..babd13d
--- /dev/null
@@ -0,0 +1,65 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.commons.collections4.bloomfilter;
+
+import java.util.Objects;
+import java.util.function.IntPredicate;
+
+/**
+ * A Testing Hasher that returns the array values % shape.getNumberOfBits().
+ *
+ * @since 4.5
+ */
+public final class ArrayHasher implements Hasher {
+    final int[] values;
+
+    ArrayHasher(final int... values) {
+        this.values = values;
+    }
+
+    @Override
+    public IndexProducer indices(final Shape shape) {
+        Objects.requireNonNull(shape, "shape");
+        return new Producer(shape);
+    }
+
+    @Override
+    public IndexProducer uniqueIndices(Shape shape) {
+        return new Producer(shape);
+    }
+
+    private class Producer implements IndexProducer {
+        Shape shape;
+
+        Producer(Shape shape) {
+            this.shape = shape;
+        }
+
+        @Override
+        public boolean forEachIndex(IntPredicate consumer) {
+            int pos = 0;
+            for (int i=0; i<shape.getNumberOfHashFunctions(); i++) {
+                int result = values[pos++] % shape.getNumberOfBits();
+                pos = pos % values.length;
+                if (!consumer.test(result)) {
+                    return false;
+                }
+            }
+            return true;
+        }
+    }
+}
index 7961b6d53d9c5146806bf5003ca289338f1e3c39..331411436a608d660b7f12485a2aed5295fe6341 100644 (file)
@@ -32,4 +32,10 @@ public class BitCountProducerFromArrayCountingBloomFilterTest extends AbstractBi
     protected BitCountProducer createEmptyProducer() {
         return new ArrayCountingBloomFilter(shape);
     }
+
+    @Override
+    protected int getBehaviour() {
+        // CountingBloomFilter based on an array will be distinct and ordered
+        return FOR_EACH_DISTINCT | FOR_EACH_ORDERED | AS_ARRAY_DISTINCT | AS_ARRAY_ORDERED;
+    }
 }
index d4c2be603e68d635d51daf1c3a85789c20025515..8458dddfa3638f84e362c543c94f9b67fb43a500 100644 (file)
@@ -20,13 +20,14 @@ import static org.junit.Assert.assertEquals;
 
 import java.util.HashMap;
 import java.util.Map;
+import org.junit.jupiter.api.Disabled;
 import org.junit.jupiter.api.Test;
 
 public class BitCountProducerFromIndexProducerTest extends AbstractBitCountProducerTest {
 
     @Override
     protected BitCountProducer createProducer() {
-        return BitCountProducer.from(IndexProducer.fromIndexArray(new int[] { 0, 1, 63, 64, 127, 128 }));
+        return BitCountProducer.from(IndexProducer.fromIndexArray(new int[] { 0, 63, 1, 1, 64, 127, 128 }));
     }
 
     @Override
@@ -34,7 +35,14 @@ public class BitCountProducerFromIndexProducerTest extends AbstractBitCountProdu
         return BitCountProducer.from(IndexProducer.fromIndexArray(new int[0]));
     }
 
+    @Override
+    protected int getBehaviour() {
+        // The default method streams a BitSet so is distinct and ordered.
+        return AS_ARRAY_DISTINCT | AS_ARRAY_ORDERED;
+    }
+
     @Test
+    @Disabled("Current behaviour will return the same index twice, each with a count of 1")
     public final void testFromIndexProducer() {
 
         BitCountProducer producer = createProducer();
@@ -47,7 +55,7 @@ public class BitCountProducerFromIndexProducerTest extends AbstractBitCountProdu
 
         assertEquals(6, m.size());
         assertEquals(Integer.valueOf(1), m.get(0));
-        assertEquals(Integer.valueOf(1), m.get(1));
+        assertEquals(Integer.valueOf(2), m.get(1));
         assertEquals(Integer.valueOf(1), m.get(63));
         assertEquals(Integer.valueOf(1), m.get(64));
         assertEquals(Integer.valueOf(1), m.get(127));
index aa000797e5206ac1381d4d915be3c78eefa95f05..96f121f0ad914354df629f4a264b16a6a78bed47 100644 (file)
@@ -23,7 +23,9 @@ public class BitMapProducerFromSimpleBloomFilterTest extends AbstractBitMapProdu
     @Override
     protected BitMapProducer createProducer() {
         Hasher hasher = new IncrementingHasher(0, 1);
-        return new SimpleBloomFilter(shape, hasher);
+        BloomFilter bf = new SimpleBloomFilter(shape);
+        bf.merge(hasher);
+        return bf;
     }
 
     @Override
index 0c80b6d0d30bd8e4d0d6b9dc2967ee8643e04ba7..7d22dee12c39ee065244e7023ea303c677d81e63 100644 (file)
@@ -23,7 +23,9 @@ public class BitMapProducerFromSparseBloomFilterTest extends AbstractBitMapProdu
     @Override
     protected BitMapProducer createProducer() {
         Hasher hasher = new IncrementingHasher(0, 1);
-        return new SparseBloomFilter(shape, hasher);
+        BloomFilter bf = new SparseBloomFilter(shape);
+        bf.merge(hasher);
+        return bf;
     }
 
     @Override
index e7af149b1b5fe7acb1f6d8794548271946d5d63a..8a037225815fb6abdff028383dfafcdd2d9a35d0 100644 (file)
  */
 package org.apache.commons.collections4.bloomfilter;
 
+import static org.junit.jupiter.api.Assertions.assertArrayEquals;
+import static org.junit.jupiter.api.Assertions.assertTrue;
+
+import java.util.concurrent.ThreadLocalRandom;
 import java.util.function.LongPredicate;
 
+import org.junit.jupiter.api.Test;
+
 public class DefaultBitMapProducerTest extends AbstractBitMapProducerTest {
 
+    long[] values = generateLongArray( 5 );
+
     @Override
     protected BitMapProducer createProducer() {
-        return new DefaultBitMapProducer(new long[] { 1L, 2L });
+        return new DefaultBitMapProducer(values);
     }
 
     @Override
@@ -52,4 +60,31 @@ public class DefaultBitMapProducerTest extends AbstractBitMapProducerTest {
             return true;
         }
     }
+
+    /**
+     * Generates an array of random long values.
+     * @param size the number of values to generate
+     * @return the array of random values.
+     */
+    public static long[] generateLongArray(int size) {
+        return ThreadLocalRandom.current().longs(size).toArray();
+    }
+
+    @Test
+    public void testFromIndexProducer() {
+        int[] expected = DefaultIndexProducerTest.generateIntArray(10, 256);
+        IndexProducer ip = IndexProducer.fromIndexArray(expected);
+        long[] ary = BitMapProducer.fromIndexProducer(ip, 256).asBitMapArray();
+        for (int idx : expected) {
+            assertTrue( BitMap.contains(ary, idx));
+        }
+    }
+
+    @Test
+    public void testFromBitMapArray() {
+        int nOfBitMaps = BitMap.numberOfBitMaps(256);
+        long[] expected = generateLongArray( nOfBitMaps );
+        long[] ary = BitMapProducer.fromBitMapArray(expected).asBitMapArray();
+        assertArrayEquals( expected, ary );
+    }
 }
index 26862bb1942fbc4f4a4da7b766904fc79d323041..eb23d84a3227954d8208c9127055044b30c2fb4f 100644 (file)
@@ -34,21 +34,6 @@ public class DefaultBloomFilterTest extends AbstractBloomFilterTest<DefaultBloom
         return new SparseDefaultBloomFilter(shape);
     }
 
-    @Override
-    protected AbstractDefaultBloomFilter createFilter(final Shape shape, final Hasher hasher) {
-        return new SparseDefaultBloomFilter(shape, hasher);
-    }
-
-    @Override
-    protected AbstractDefaultBloomFilter createFilter(final Shape shape, final BitMapProducer producer) {
-        return new SparseDefaultBloomFilter(shape, producer);
-    }
-
-    @Override
-    protected AbstractDefaultBloomFilter createFilter(final Shape shape, final IndexProducer producer) {
-        return new SparseDefaultBloomFilter(shape, producer);
-    }
-
     @Test
     public void testDefaultBloomFilterSimpleSpecificMerge() {
         AbstractDefaultBloomFilter filter = new SparseDefaultBloomFilter(Shape.fromKM(3, 150));
@@ -62,14 +47,14 @@ public class DefaultBloomFilterTest extends AbstractBloomFilterTest<DefaultBloom
     public void testDefaultBloomFilterSparseSpecificMerge() {
         Shape shape = Shape.fromKM(3, 150);
         AbstractDefaultBloomFilter filter = new SparseDefaultBloomFilter(shape);
-        AbstractDefaultBloomFilter filter2 = new SparseDefaultBloomFilter(shape, new IncrementingHasher(0, 1));
+        AbstractDefaultBloomFilter filter2 = createFilter(shape, new IncrementingHasher(0, 1));
         BloomFilter newFilter = filter.copy();
         newFilter.merge(filter2);
         assertEquals(3, newFilter.cardinality());
     }
 
     @Test
-    public void testHasherBasedMergeInPlaceWithDifferingSparseness() {
+    public void testHasherBasedMergeWithDifferingSparseness() {
         Hasher hasher = new IncrementingHasher(1, 1);
 
         BloomFilter bf1 = new NonSparseDefaultBloomFilter(getTestShape());
@@ -92,24 +77,9 @@ public class DefaultBloomFilterTest extends AbstractBloomFilterTest<DefaultBloom
             this.indices = new TreeSet<>();
         }
 
-        AbstractDefaultBloomFilter(Shape shape, Hasher hasher) {
-            this(shape, hasher.indices(shape));
-        }
-
-        AbstractDefaultBloomFilter(Shape shape, BitMapProducer producer) {
-            this(shape, IndexProducer.fromBitMapProducer(producer));
-        }
-
-        AbstractDefaultBloomFilter(Shape shape, IndexProducer producer) {
-            this(shape);
-            producer.forEachIndex((i) -> {
-                indices.add(i);
-                return true;
-            });
-            if (this.indices.floor(-1) != null || this.indices.ceiling(shape.getNumberOfBits()) != null) {
-                throw new IllegalArgumentException(
-                        String.format("Filter only accepts values in the [0,%d) range", shape.getNumberOfBits()));
-            }
+        @Override
+        public void clear() {
+            indices.clear();
         }
 
         @Override
@@ -142,12 +112,7 @@ public class DefaultBloomFilterTest extends AbstractBloomFilterTest<DefaultBloom
             return contains(IndexProducer.fromBitMapProducer(bitMapProducer));
         }
 
-        @Override
-        public boolean merge(BloomFilter other) {
-            other.forEachIndex((i) -> {
-                indices.add(i);
-                return true;
-            });
+        private void checkIndicesRange() {
             if (!indices.isEmpty()) {
                 if (indices.last() >= shape.getNumberOfBits()) {
                     throw new IllegalArgumentException(String.format("Value in list %s is greater than maximum value (%s)",
@@ -158,36 +123,38 @@ public class DefaultBloomFilterTest extends AbstractBloomFilterTest<DefaultBloom
                             String.format("Value in list %s is less than 0", indices.first()));
                 }
             }
-            return true;
         }
 
         @Override
-        public int cardinality() {
-            return indices.size();
+        public boolean merge(IndexProducer indexProducer) {
+            boolean result = indexProducer.forEachIndex(x -> {
+                indices.add(x);
+                return true;
+            });
+            checkIndicesRange();
+            return result;
         }
-    }
 
-    static class SparseDefaultBloomFilter extends AbstractDefaultBloomFilter {
-
-        SparseDefaultBloomFilter(Shape shape, BitMapProducer producer) {
-            super(shape, producer);
+        @Override
+        public boolean merge(BitMapProducer bitMapProducer){
+            return merge(IndexProducer.fromBitMapProducer(bitMapProducer));
         }
 
-        SparseDefaultBloomFilter(Shape shape, Hasher hasher) {
-            super(shape, hasher);
+        @Override
+        public int cardinality() {
+            return indices.size();
         }
+    }
 
-        SparseDefaultBloomFilter(Shape shape, IndexProducer producer) {
-            super(shape, producer);
-        }
+    static class SparseDefaultBloomFilter extends AbstractDefaultBloomFilter {
 
         SparseDefaultBloomFilter(Shape shape) {
             super(shape);
         }
 
         @Override
-        public boolean isSparse() {
-            return true;
+        public int characteristics() {
+            return SPARSE;
         }
 
         @Override
@@ -200,25 +167,13 @@ public class DefaultBloomFilterTest extends AbstractBloomFilterTest<DefaultBloom
 
     static class NonSparseDefaultBloomFilter extends AbstractDefaultBloomFilter {
 
-        NonSparseDefaultBloomFilter(Shape shape, BitMapProducer producer) {
-            super(shape, producer);
-        }
-
-        NonSparseDefaultBloomFilter(Shape shape, Hasher hasher) {
-            super(shape, hasher);
-        }
-
-        NonSparseDefaultBloomFilter(Shape shape, IndexProducer producer) {
-            super(shape, producer);
-        }
-
         NonSparseDefaultBloomFilter(Shape shape) {
             super(shape);
         }
 
         @Override
-        public boolean isSparse() {
-            return false;
+        public int characteristics() {
+            return 0;
         }
 
         @Override
diff --git a/src/test/java/org/apache/commons/collections4/bloomfilter/DefaultIndexProducerTest.java b/src/test/java/org/apache/commons/collections4/bloomfilter/DefaultIndexProducerTest.java
new file mode 100644 (file)
index 0000000..dc0ca7f
--- /dev/null
@@ -0,0 +1,105 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.commons.collections4.bloomfilter;
+
+import static org.junit.jupiter.api.Assertions.assertArrayEquals;
+
+import java.util.Arrays;
+import java.util.BitSet;
+import java.util.concurrent.ThreadLocalRandom;
+import java.util.function.IntPredicate;
+
+import org.junit.jupiter.api.Test;
+
+public class DefaultIndexProducerTest extends AbstractIndexProducerTest {
+
+    private int[] values = generateIntArray(10, 512);
+
+    @Override
+    protected IndexProducer createProducer() {
+        return IndexProducer.fromIndexArray(values);
+    }
+
+    @Override
+    protected IndexProducer createEmptyProducer() {
+        return new IndexProducer() {
+
+            @Override
+            public boolean forEachIndex(IntPredicate predicate) {
+                return true;
+            }
+        };
+    }
+
+    @Override
+    protected int getBehaviour() {
+        // The default method streams a BitSet so is distinct and ordered.
+        return AS_ARRAY_DISTINCT | AS_ARRAY_ORDERED;
+    }
+
+    /**
+     * Generates an array of integers.
+     * @param size the size of the array
+     * @param bound the upper bound (exclusive) of the values in the array.
+     * @return an array of int.
+     */
+    public static int[] generateIntArray(int size, int bound) {
+        return ThreadLocalRandom.current().ints(size, 0, bound).toArray();
+    }
+
+    /**
+     * Creates a BitSet of indices.
+     * @param ary the array
+     * @return the set.
+     */
+    public static BitSet uniqueSet(int[] ary) {
+        final BitSet bs = new BitSet();
+        Arrays.stream(ary).forEach(bs::set);
+        return bs;
+    }
+
+    /**
+     * Creates a sorted unique array of ints.
+     * @param ary the array to sort and make unique
+     * @return the sorted unique array.
+     */
+    public static int[] unique(int[] ary) {
+        return Arrays.stream(ary).distinct().sorted().toArray();
+    }
+
+    @Test
+    public void testFromBitMapProducer() {
+        for (int i = 0; i < 5; i++) {
+            int[] expected = generateIntArray(7, 256);
+            long[] bits = new long[BitMap.numberOfBitMaps(256)];
+            for (int bitIndex : expected) {
+                BitMap.set(bits, bitIndex);
+            }
+            IndexProducer ip = IndexProducer.fromBitMapProducer(BitMapProducer.fromBitMapArray(bits));
+            assertArrayEquals(unique(expected), ip.asIndexArray());
+        }
+    }
+
+    @Test
+    public void testFromIndexArray() {
+        for (int i = 0; i < 5; i++) {
+            int[] expected = generateIntArray(10, 256);
+            IndexProducer ip = IndexProducer.fromIndexArray(expected);
+            assertArrayEquals(unique(expected), ip.asIndexArray());
+        }
+    }
+}
index 2c028bf02f364e9de7d64fad577088448b2e2b69..49afb7b28019472a92e996402e1dc30c2351f7c4 100644 (file)
@@ -35,6 +35,12 @@ public class EnhancedDoubleHasherTest extends AbstractHasherTest {
         return NullHasher.INSTANCE;
     }
 
+    @Override
+    protected int getBehaviour() {
+        // Allows duplicates and may be unordered
+        return 0;
+    }
+
     @Override
     protected int getHasherSize(Hasher hasher) {
         return 1;
@@ -43,39 +49,39 @@ public class EnhancedDoubleHasherTest extends AbstractHasherTest {
     @Test
     public void testByteConstructor() {
         // single value become increment.
-        EnhancedDoubleHasher hasher = new EnhancedDoubleHasher( new byte[] { 1 } );
-        assertEquals( 0, hasher.getInitial() );
-        assertEquals( 0x01_00_00_00_00_00_00_00L, hasher.getIncrement() );
+        EnhancedDoubleHasher hasher = new EnhancedDoubleHasher(new byte[] {1});
+        assertEquals(0, hasher.getInitial());
+        assertEquals(0x01_00_00_00_00_00_00_00L, hasher.getIncrement());
 
         // 2 bytes become initial and increment.
-        hasher = new EnhancedDoubleHasher( new byte[] { 1, 2 } );
-        assertEquals( 0x01_00_00_00_00_00_00_00L, hasher.getInitial() );
-        assertEquals( 0x200000000000000L, hasher.getIncrement() );
+        hasher = new EnhancedDoubleHasher(new byte[] {1, 2});
+        assertEquals(0x01_00_00_00_00_00_00_00L, hasher.getInitial());
+        assertEquals(0x02_00_00_00_00_00_00_00L, hasher.getIncrement());
 
         // odd values place extra byte in increment.
-        hasher = new EnhancedDoubleHasher( new byte[] { 1, 2, 3 } );
-        assertEquals( 0x01_00_00_00_00_00_00_00L, hasher.getInitial() );
-        assertEquals( 0x203000000000000L, hasher.getIncrement() );
+        hasher = new EnhancedDoubleHasher(new byte[] {1, 2, 3});
+        assertEquals(0x01_00_00_00_00_00_00_00L, hasher.getInitial());
+        assertEquals(0x02_03_00_00_00_00_00_00L, hasher.getIncrement());
 
         // even short split
-        hasher = new EnhancedDoubleHasher( new byte[] {0, 1, 0, 2 } );
-        assertEquals( 0x01_00_00_00_00_00_00L, hasher.getInitial() );
-        assertEquals( 0x02_00_00_00_00_00_00L, hasher.getIncrement() );
+        hasher = new EnhancedDoubleHasher(new byte[] {0, 1, 0, 2});
+        assertEquals(0x01_00_00_00_00_00_00L, hasher.getInitial());
+        assertEquals(0x02_00_00_00_00_00_00L, hasher.getIncrement());
 
         // longs are parse correctly
-        hasher = new EnhancedDoubleHasher( new byte[] { 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 2 } );
-        assertEquals( 1, hasher.getInitial() );
-        assertEquals( 2, hasher.getIncrement() );
+        hasher = new EnhancedDoubleHasher(new byte[] {0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 2});
+        assertEquals(1, hasher.getInitial());
+        assertEquals(2, hasher.getIncrement());
 
         // excess bytes are ignored before mid point and at end
-        hasher = new EnhancedDoubleHasher( new byte[] { 0, 0, 0, 0, 0, 0, 0, 1, 5, 5, 0, 0, 0, 0, 0, 0, 0, 2, 5, 5 } );
-        assertEquals( 1, hasher.getInitial() );
-        assertEquals( 2, hasher.getIncrement() );
+        hasher = new EnhancedDoubleHasher(new byte[] {0, 0, 0, 0, 0, 0, 0, 1, 5, 5, 0, 0, 0, 0, 0, 0, 0, 2, 5, 5});
+        assertEquals(1, hasher.getInitial());
+        assertEquals(2, hasher.getIncrement());
 
         // odd extra bytes are accounted for correctly
-        hasher = new EnhancedDoubleHasher( new byte[] { 0, 0, 0, 0, 0, 0, 0, 1, 5, 1, 0, 0, 0, 0, 0, 0, 2, 5, 5 } );
-        assertEquals( 1, hasher.getInitial() );
-        assertEquals( 0x01_00_00_00_00_00_00_02L, hasher.getIncrement() );
+        hasher = new EnhancedDoubleHasher(new byte[] {0, 0, 0, 0, 0, 0, 0, 1, 5, 1, 0, 0, 0, 0, 0, 0, 2, 5, 5});
+        assertEquals(1, hasher.getInitial());
+        assertEquals(0x01_00_00_00_00_00_00_02L, hasher.getIncrement());
 
         // test empty buffer
         assertThrows(IllegalArgumentException.class, () -> new EnhancedDoubleHasher(new byte[0]));
index 997ee01a210bc678a58eb32a8c4171ce53f5cd56..894115c5966fdeaf6fd95dc9725614b766650663 100644 (file)
@@ -41,14 +41,24 @@ public class HasherCollectionTest extends AbstractHasherTest {
         return new HasherCollection();
     }
 
+    @Override
+    protected int getBehaviour() {
+        // Allows duplicates and may be unordered
+        return 0;
+    }
+
     @Override
     protected int getHasherSize(Hasher hasher) {
         return ((HasherCollection) hasher).getHashers().size();
     }
 
     protected void nestedTest(HasherCollectionTest nestedTest) {
-        nestedTest.testAsIndexArray();
         nestedTest.testForEachIndex();
+        nestedTest.testEmptyProducer();
+        nestedTest.testConsistency();
+        nestedTest.testBehaviourAsIndexArray();
+        nestedTest.testBehaviourForEach();
+        nestedTest.testForEachIndexEarlyExit();
         nestedTest.testAdd();
     }
 
index 0ea2c60795a4d0d63be631647ac63f5e9a19bb9a..4b7cbb8c84ae217c90dc9fc90379ca00c6b92671 100644 (file)
@@ -32,4 +32,9 @@ public class IndexProducerFromArrayCountingBloomFilterTest extends AbstractIndex
     protected IndexProducer createEmptyProducer() {
         return new ArrayCountingBloomFilter(shape);
     }
+
+    @Override
+    protected int getBehaviour() {
+        return FOR_EACH_DISTINCT | FOR_EACH_ORDERED | AS_ARRAY_DISTINCT | AS_ARRAY_ORDERED;
+    }
 }
index a208d3a2f99152dad12e37c48f797176df456074..e844183efa2ce6d1b72c4f07b28d0355e292d60c 100644 (file)
@@ -49,6 +49,12 @@ public class IndexProducerFromBitmapProducerTest extends AbstractIndexProducerTe
         return IndexProducer.fromBitMapProducer(producer);
     }
 
+    @Override
+    protected int getBehaviour() {
+        // Bit maps will be distinct. Conversion to indices should be ordered.
+        return FOR_EACH_DISTINCT | FOR_EACH_ORDERED | AS_ARRAY_DISTINCT | AS_ARRAY_ORDERED;
+    }
+
     @Test
     public final void testFromBitMapProducerTest() {
         IndexProducer underTest = createProducer();
index 1376a4bfc01067d7d0b0d35c7ac00324c3d1af4c..044e727b2447561d347d8d406fc52ee0d2b69d78 100644 (file)
@@ -27,4 +27,10 @@ public class IndexProducerFromHasherCollectionTest extends AbstractIndexProducer
     protected IndexProducer createEmptyProducer() {
         return new HasherCollection().indices(Shape.fromKM(17, 72));
     }
+
+    @Override
+    protected int getBehaviour() {
+        // HasherCollection allows duplicates and may be unordered
+        return 0;
+    }
 }
index 683b3705e2dee24086f9102c2b64d593c691619c..0e7368dee809ee642b06cb754541dff4c5934d62 100644 (file)
@@ -27,4 +27,10 @@ public class IndexProducerFromHasherTest extends AbstractIndexProducerTest {
     protected IndexProducer createEmptyProducer() {
         return NullHasher.INSTANCE.indices(Shape.fromKM(17, 72));
     }
+
+    @Override
+    protected int getBehaviour() {
+        // Hasher allows duplicates and may be unordered
+        return 0;
+    }
 }
index 4755d24a85fba880424c87f7f4eb1c1756774918..2ad9ee5c1e8d4417a2e6db86d97d7e572473d6e1 100644 (file)
@@ -25,6 +25,12 @@ public class IndexProducerFromIntArrayTest extends AbstractIndexProducerTest {
 
     @Override
     protected IndexProducer createProducer() {
-        return IndexProducer.fromIndexArray(new int[] { 1, 2, 3, 4, 5 });
+        return IndexProducer.fromIndexArray(new int[] { 6, 8, 1, 2, 4, 4, 5 });
+    }
+
+    @Override
+    protected int getBehaviour() {
+        // Delegates to the default asIndexArray which is distinct and ordered
+        return AS_ARRAY_DISTINCT | AS_ARRAY_ORDERED;
     }
 }
index d62ac959e071201bf4ad5a991dcbab479315fb01..e8da24a8da44d835b7e9c4851b9303e57df6eb86 100644 (file)
@@ -23,11 +23,19 @@ public class IndexProducerFromSimpleBloomFilterTest extends AbstractIndexProduce
     @Override
     protected IndexProducer createProducer() {
         Hasher hasher = new IncrementingHasher(0, 1);
-        return new SparseBloomFilter(shape, hasher);
+        BloomFilter bf = new SimpleBloomFilter(shape);
+        bf.merge(hasher);
+        return bf;
     }
 
     @Override
     protected IndexProducer createEmptyProducer() {
-        return new SparseBloomFilter(shape);
+        return new SimpleBloomFilter(shape);
+    }
+
+    @Override
+    protected int getBehaviour() {
+        // BloomFilter based on a bit map array will be distinct and ordered
+        return FOR_EACH_DISTINCT | FOR_EACH_ORDERED | AS_ARRAY_DISTINCT | AS_ARRAY_ORDERED;
     }
 }
index b51e01b40b8452b5bddb117be1b6a9fb3f8d5fa8..59823f329e9d0337b68c681886c4c0852358682e 100644 (file)
@@ -23,11 +23,22 @@ public class IndexProducerFromSparseBloomFilterTest extends AbstractIndexProduce
     @Override
     protected IndexProducer createProducer() {
         Hasher hasher = new IncrementingHasher(0, 1);
-        return new SimpleBloomFilter(shape, hasher);
+        BloomFilter bf = new SparseBloomFilter(shape);
+        bf.merge(hasher);
+        return bf;
+
     }
 
     @Override
     protected IndexProducer createEmptyProducer() {
-        return new SimpleBloomFilter(shape);
+        return new SparseBloomFilter(shape);
+    }
+
+    @Override
+    protected int getBehaviour() {
+        // A sparse BloomFilter will be distinct but it may not be ordered.
+        // Currently the ordered behaviour is asserted as the implementation uses
+        // an ordered TreeSet. This may change in the future.
+        return FOR_EACH_DISTINCT | FOR_EACH_ORDERED | AS_ARRAY_DISTINCT | AS_ARRAY_ORDERED;
     }
 }
index 890e22f8f5052d82b025c436b8cfcd6d1c849336..98a62604f7dba011a82b7c5e6548366cf7cff6d1 100644 (file)
@@ -49,22 +49,34 @@ public class SetOperationsTest {
         assertEquals(expected, operation.applyAsDouble(filter2, filter1), "op(filter2, filter1)");
     }
 
+    private BloomFilter createFilter(Shape shape, Hasher hasher) {
+        BloomFilter bf = new SimpleBloomFilter(shape);
+        bf.merge(hasher);
+        return bf;
+    }
+
+    private BloomFilter createFilter(Shape shape, IndexProducer producer) {
+        BloomFilter bf = new SparseBloomFilter(shape);
+        bf.merge(producer);
+        return bf;
+    }
+
     /**
      * Tests that the Cosine similarity is correctly calculated.
      */
     @Test
     public final void testCosineDistance() {
 
-        BloomFilter filter1 = new SimpleBloomFilter(shape, from1);
-        BloomFilter filter2 = new SimpleBloomFilter(shape, from1);
+        BloomFilter filter1 = createFilter(shape, from1);
+        BloomFilter filter2 = createFilter(shape, from1);
 
         // identical filters should have no distance.
         double expected =  0;
         assertSymmetricOperation(expected, SetOperations::cosineDistance, filter1, filter2);
 
         Shape shape2 = Shape.fromKM(2, 72);
-        filter1 = new SimpleBloomFilter(shape2, from1);
-        filter2 = new SimpleBloomFilter(shape2, new IncrementingHasher(2, 1));
+        filter1 = createFilter(shape2, from1);
+        filter2 = createFilter(shape2, new IncrementingHasher(2, 1));
 
         int dotProduct = /* [1,2] & [2,3] = [2] = */ 1;
         int cardinalityA = 2;
@@ -72,8 +84,8 @@ public class SetOperationsTest {
         expected = 1 - (dotProduct / Math.sqrt(cardinalityA * cardinalityB));
         assertSymmetricOperation(expected, SetOperations::cosineDistance, filter1, filter2);
 
-        filter1 = new SimpleBloomFilter(shape, from1);
-        filter2 = new SimpleBloomFilter(shape, from11);
+        filter1 = createFilter(shape, from1);
+        filter2 = createFilter(shape, from11);
         dotProduct = /* [1..17] & [11..27] = [] = */ 7;
         cardinalityA = 17;
         cardinalityB = 17;
@@ -81,20 +93,19 @@ public class SetOperationsTest {
         assertSymmetricOperation(expected, SetOperations::cosineDistance, filter1, filter2);
 
         // test with no values
-        filter1 = new SimpleBloomFilter(shape, from1);
+        filter1 = createFilter(shape, from1);
         filter2 = new SimpleBloomFilter(shape);
-        BloomFilter filter3 = new SimpleBloomFilter(shape);
 
         dotProduct = /* [1,2] & [] = [] = */ 0;
         cardinalityA = 2;
         cardinalityB = 0;
-        expected = /* 1 - (dotProduct/Math.sqrt( cardinalityA * cardinalityB )) = */ 1.0;
+        expected = /* 1 - (dotProduct/Math.sqrt(cardinalityA * cardinalityB)) = */ 1.0;
         assertSymmetricOperation(expected, SetOperations::cosineDistance, filter1, filter2);
 
         dotProduct = /* [] & [] = [] = */ 0;
         cardinalityA = 0;
         cardinalityB = 0;
-        expected = /* 1 - (dotProduct/Math.sqrt( cardinalityA * cardinalityB )) = */ 1.0;
+        expected = /* 1 - (dotProduct/Math.sqrt(cardinalityA * cardinalityB)) = */ 1.0;
         assertSymmetricOperation(expected, SetOperations::cosineDistance, filter1, filter2);
     }
 
@@ -103,27 +114,27 @@ public class SetOperationsTest {
      */
     @Test
     public final void testCosineSimilarity() {
-        BloomFilter filter1 = new SimpleBloomFilter(shape, from1);
-        BloomFilter filter2 = new SimpleBloomFilter(shape, from1);
+        BloomFilter filter1 = createFilter(shape, from1);
+        BloomFilter filter2 = createFilter(shape, from1);
 
         int dotProduct = /* [1..17] & [1..17] = [1..17] = */ 17;
         int cardinalityA = 17;
         int cardinalityB = 17;
-        double expected = /* dotProduct/Sqrt( cardinalityA * cardinalityB ) = */ 1.0;
+        double expected = /* dotProduct/Sqrt(cardinalityA * cardinalityB) = */ 1.0;
         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);
+        filter2 = createFilter(shape, from11);
         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);
+        BloomFilter filter3 = createFilter(shape, from1);
         assertSymmetricOperation(0.0, SetOperations::cosineSimilarity, filter1, filter2);
         assertSymmetricOperation(0.0, SetOperations::cosineSimilarity, filter1, filter3);
     }
@@ -133,13 +144,13 @@ public class SetOperationsTest {
      */
     @Test
     public final void testHammingDistance() {
-        final BloomFilter filter1 = new SimpleBloomFilter(shape, from1);
-        BloomFilter filter2 = new SimpleBloomFilter(shape, from1);
+        final BloomFilter filter1 = createFilter(shape, from1);
+        BloomFilter filter2 = createFilter(shape, from1);
 
         int hammingDistance = /* [1..17] ^ [1..17] = [] = */ 0;
         assertSymmetricOperation(hammingDistance, SetOperations::hammingDistance, filter1, filter2);
 
-        filter2 = new SimpleBloomFilter(shape, from11);
+        filter2 = createFilter(shape, from11);
         hammingDistance = /* [1..17] ^ [11..27] = [1..10][17-27] = */ 20;
         assertSymmetricOperation(hammingDistance, SetOperations::hammingDistance, filter1, filter2);
     }
@@ -149,13 +160,13 @@ public class SetOperationsTest {
      */
     @Test
     public final void testJaccardDistance() {
-        BloomFilter filter1 = new SimpleBloomFilter(shape, from1);
-        BloomFilter filter2 = new SimpleBloomFilter(shape, from1);
+        BloomFilter filter1 = createFilter(shape, from1);
+        BloomFilter filter2 = createFilter(shape, from1);
 
         // 1 - jaccardSimilarity -- see jaccardSimilarityTest
         assertSymmetricOperation(0.0, SetOperations::jaccardDistance, filter1, filter2);
 
-        filter2 = new SimpleBloomFilter(shape, from11);
+        filter2 = createFilter(shape, from11);
         double intersection = /* [1..17] & [11..27] = [11..17] = */ 7.0;
         int union = /* [1..17] | [11..27] = [1..27] = */ 27;
         double expected = 1 - (intersection / union);
@@ -164,7 +175,7 @@ public class SetOperationsTest {
         // test no values
         filter1 = new SimpleBloomFilter(shape);
         filter2 = new SimpleBloomFilter(shape);
-        BloomFilter filter3 = new SimpleBloomFilter(shape, from1);
+        BloomFilter filter3 = createFilter(shape, from1);
 
         // 1 - jaccardSimilarity -- see jaccardSimilarityTest
         assertSymmetricOperation(1.0, SetOperations::jaccardDistance, filter1, filter2);
@@ -176,15 +187,15 @@ public class SetOperationsTest {
      */
     @Test
     public final void testJaccardSimilarity() {
-        BloomFilter filter1 = new SimpleBloomFilter(shape, from1);
-        BloomFilter filter2 = new SimpleBloomFilter(shape, from1);
+        BloomFilter filter1 = createFilter(shape, from1);
+        BloomFilter filter2 = createFilter(shape, from1);
 
         double intersection = /* [1..17] & [1..17] = [1..17] = */ 17.0;
         int union = /* [1..17] | [1..17] = [1..17] = */ 17;
         double expected = intersection / union;
         assertSymmetricOperation(expected, SetOperations::jaccardSimilarity, filter1, filter2);
 
-        filter2 = new SimpleBloomFilter(shape, from11);
+        filter2 = createFilter(shape, from11);
         intersection = /* [1..17] & [11..27] = [11..17] = */ 7.0;
         union = /* [1..17] | [11..27] = [1..27] = */ 27;
         expected = intersection / union;
@@ -193,7 +204,6 @@ public class SetOperationsTest {
         // test no values
         filter1 = new SimpleBloomFilter(shape);
         filter2 = new SimpleBloomFilter(shape);
-        BloomFilter filter3 = new SimpleBloomFilter(shape, from1);
         assertSymmetricOperation(0.0, SetOperations::jaccardSimilarity, filter1, filter2);
 
         intersection = /* [] & [1..17] = [] = */ 0.0;
@@ -205,16 +215,16 @@ public class SetOperationsTest {
     @Test
     public final void testOrCardinality() {
         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 }));
+        BloomFilter filter1 = createFilter(shape, IndexProducer.fromIndexArray(new int[] { 1, 63, 64 }));
+        BloomFilter filter2 = createFilter(shape, IndexProducer.fromIndexArray(new int[] { 5, 64, 69 }));
         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 }));
+        filter1 = createFilter(shape, IndexProducer.fromIndexArray(new int[] { 1, 63 }));
+        filter2 = createFilter(shape, IndexProducer.fromIndexArray(new int[] { 5, 64, 69 }));
         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 }));
+        filter1 = createFilter(shape, IndexProducer.fromIndexArray(new int[] { 5, 63 }));
+        filter2 = createFilter(shape, IndexProducer.fromIndexArray(new int[] { 5, 64, 69 }));
         assertSymmetricOperation(4, SetOperations::orCardinality, filter1, filter2);
     }
 
@@ -222,32 +232,32 @@ public class SetOperationsTest {
     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 }));
+        BloomFilter filter1 = createFilter(shape, IndexProducer.fromIndexArray(new int[] { 1, 63, 64 }));
+        BloomFilter filter2 = createFilter(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 }));
+        filter1 = createFilter(shape, IndexProducer.fromIndexArray(new int[] { 1, 63 }));
+        filter2 = createFilter(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 }));
+        filter1 = createFilter(shape, IndexProducer.fromIndexArray(new int[] { 5, 63 }));
+        filter2 = createFilter(shape2, IndexProducer.fromIndexArray(new int[] { 5, 64, 169 }));
         assertSymmetricOperation(4, SetOperations::orCardinality, filter1, filter2);
     }
 
     @Test
     public final void testAndCardinality() {
         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 }));
+        BloomFilter filter1 = createFilter(shape, IndexProducer.fromIndexArray(new int[] { 1, 63, 64 }));
+        BloomFilter filter2 = createFilter(shape, IndexProducer.fromIndexArray(new int[] { 5, 64, 69 }));
         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 }));
+        filter1 = createFilter(shape, IndexProducer.fromIndexArray(new int[] { 1, 63 }));
+        filter2 = createFilter(shape, IndexProducer.fromIndexArray(new int[] { 5, 64, 69 }));
         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 }));
+        filter1 = createFilter(shape, IndexProducer.fromIndexArray(new int[] { 5, 63 }));
+        filter2 = createFilter(shape, IndexProducer.fromIndexArray(new int[] { 5, 64, 69 }));
         assertSymmetricOperation(1, SetOperations::andCardinality, filter1, filter2);
     }
 
@@ -255,37 +265,37 @@ public class SetOperationsTest {
     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 }));
+        BloomFilter filter1 = createFilter(shape, IndexProducer.fromIndexArray(new int[] { 1, 63, 64 }));
+        BloomFilter filter2 = createFilter(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 }));
+        filter1 = createFilter(shape, IndexProducer.fromIndexArray(new int[] { 1, 63 }));
+        filter2 = createFilter(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 }));
+        filter1 = createFilter(shape, IndexProducer.fromIndexArray(new int[] { 5, 63 }));
+        filter2 = createFilter(shape2, IndexProducer.fromIndexArray(new int[] { 5, 64, 169 }));
         assertSymmetricOperation(1, SetOperations::andCardinality, filter1, filter2);
     }
 
     @Test
     public final void testXorCardinality() {
         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 }));
+        BloomFilter filter1 = createFilter(shape, IndexProducer.fromIndexArray(new int[] { 1, 63, 64 }));
+        BloomFilter filter2 = createFilter(shape, IndexProducer.fromIndexArray(new int[] { 5, 64, 69 }));
         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 }));
+        filter1 = createFilter(shape, IndexProducer.fromIndexArray(new int[] { 1, 63 }));
+        filter2 = createFilter(shape, IndexProducer.fromIndexArray(new int[] { 5, 64, 69 }));
         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 }));
+        filter1 = createFilter(shape, IndexProducer.fromIndexArray(new int[] { 5, 63 }));
+        filter2 = createFilter(shape, IndexProducer.fromIndexArray(new int[] { 5, 64, 69 }));
         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 }));
+        filter1 = createFilter(bigShape, IndexProducer.fromIndexArray(new int[] { 1, 63, 185}));
+        filter2 = createFilter(shape, IndexProducer.fromIndexArray(new int[] { 5, 63, 69 }));
         assertSymmetricOperation(4, SetOperations::xorCardinality, filter1, filter2);
     }
 
@@ -294,16 +304,16 @@ public class SetOperationsTest {
         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 }));
+        BloomFilter filter1 = createFilter(shape, IndexProducer.fromIndexArray(new int[] { 1, 63, 64 }));
+        BloomFilter filter2 = createFilter(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 }));
+        filter1 = createFilter(shape, IndexProducer.fromIndexArray(new int[] { 1, 63 }));
+        filter2 = createFilter(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 }));
+        filter1 = createFilter(shape, IndexProducer.fromIndexArray(new int[] { 5, 63 }));
+        filter2 = createFilter(shape2, IndexProducer.fromIndexArray(new int[] { 5, 64, 169 }));
         assertSymmetricOperation(3, SetOperations::xorCardinality, filter1, filter2);
     }
 
index 15aeea62cb291fa86757af6c74ca3515d52e9b10..b37c0ffe86ea75b14b0ca17a17abbaef21822a06 100644 (file)
@@ -16,7 +16,6 @@
  */
 package org.apache.commons.collections4.bloomfilter;
 
-import org.junit.jupiter.api.Test;
 
 /**
  * Tests for the {@link SimpleBloomFilter}.
@@ -26,63 +25,4 @@ public class SimpleBloomFilterTest extends AbstractBloomFilterTest<SimpleBloomFi
     protected SimpleBloomFilter createEmptyFilter(final Shape shape) {
         return new SimpleBloomFilter(shape);
     }
-
-    @Override
-    protected SimpleBloomFilter createFilter(final Shape shape, final Hasher hasher) {
-        return new SimpleBloomFilter(shape, hasher);
-    }
-
-    @Override
-    protected SimpleBloomFilter createFilter(final Shape shape, final BitMapProducer producer) {
-        return new SimpleBloomFilter(shape, producer);
-    }
-
-    @Override
-    protected SimpleBloomFilter createFilter(final Shape shape, final IndexProducer producer) {
-        return new SimpleBloomFilter(shape, producer);
-    }
-
-    private void executeNestedTest(SimpleBloomFilterTest nestedTest) {
-        nestedTest.testAsBitMapArray();
-        nestedTest.testContains();
-        nestedTest.testEstimateIntersection();
-        nestedTest.testEstimateN();
-        nestedTest.testEstimateUnion();
-        nestedTest.testIsFull();
-        nestedTest.testMerge();
-    }
-
-    @Test
-    public void testConstructors() {
-
-        // // copy of Sparse
-        SimpleBloomFilterTest nestedTest = new SimpleBloomFilterTest() {
-
-            @Override
-            protected SimpleBloomFilter createEmptyFilter(Shape shape) {
-                return new SimpleBloomFilter(new SparseBloomFilter(shape));
-            }
-
-            @Override
-            protected SimpleBloomFilter createFilter(Shape shape, Hasher hasher) {
-                return new SimpleBloomFilter(new SparseBloomFilter(shape, hasher));
-            }
-        };
-        executeNestedTest(nestedTest);
-
-        // copy of Simple
-        nestedTest = new SimpleBloomFilterTest() {
-
-            @Override
-            protected SimpleBloomFilter createEmptyFilter(Shape shape) {
-                return new SimpleBloomFilter(new SimpleBloomFilter(shape));
-            }
-
-            @Override
-            protected SimpleBloomFilter createFilter(Shape shape, Hasher hasher) {
-                return new SimpleBloomFilter(new SimpleBloomFilter(shape, hasher));
-            }
-        };
-        executeNestedTest(nestedTest);
-    }
 }
index d3645f1e8aae998219af8d7d1721d207191bf841..95484d967c9b27dd6e747bc4f6abfa068561747b 100644 (file)
@@ -31,64 +31,6 @@ public class SparseBloomFilterTest extends AbstractBloomFilterTest<SparseBloomFi
         return new SparseBloomFilter(shape);
     }
 
-    @Override
-    protected SparseBloomFilter createFilter(final Shape shape, final Hasher hasher) {
-        return new SparseBloomFilter(shape, hasher);
-    }
-
-    @Override
-    protected SparseBloomFilter createFilter(final Shape shape, final BitMapProducer producer) {
-        return new SparseBloomFilter(shape, producer);
-    }
-
-    @Override
-    protected SparseBloomFilter createFilter(final Shape shape, final IndexProducer producer) {
-        return new SparseBloomFilter(shape, producer);
-    }
-
-    private void executeNestedTest(SparseBloomFilterTest nestedTest) {
-        nestedTest.testContains();
-        nestedTest.testEstimateIntersection();
-        nestedTest.testEstimateN();
-        nestedTest.testEstimateUnion();
-        nestedTest.testIsFull();
-        nestedTest.testMerge();
-    }
-
-    @Test
-    public void testConstructors() {
-
-        // copy of Sparse
-        SparseBloomFilterTest nestedTest = new SparseBloomFilterTest() {
-
-            @Override
-            protected SparseBloomFilter createEmptyFilter(Shape shape) {
-                return new SparseBloomFilter(new SparseBloomFilter(shape));
-            }
-
-            @Override
-            protected SparseBloomFilter createFilter(Shape shape, Hasher hasher) {
-                return new SparseBloomFilter(new SparseBloomFilter(shape, hasher));
-            }
-        };
-        executeNestedTest(nestedTest);
-
-        // copy of Simple
-        nestedTest = new SparseBloomFilterTest() {
-
-            @Override
-            protected SparseBloomFilter createEmptyFilter(Shape shape) {
-                return new SparseBloomFilter(new SimpleBloomFilter(shape));
-            }
-
-            @Override
-            protected SparseBloomFilter createFilter(Shape shape, Hasher hasher) {
-                return new SparseBloomFilter(new SimpleBloomFilter(shape, hasher));
-            }
-        };
-        executeNestedTest(nestedTest);
-    }
-
     @Test
     public void testBitMapProducerEdgeCases() {
         int[] values = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 65, 66, 67, 68, 69, 70, 71 };
@@ -140,9 +82,10 @@ public class SparseBloomFilterTest extends AbstractBloomFilterTest<SparseBloomFi
     }
 
     @Test
-    public void testBloomFilterBasedMergeInPlaceEdgeCases() {
+    public void testBloomFilterBasedMergeEdgeCases() {
         BloomFilter bf1 = createEmptyFilter(getTestShape());
-        BloomFilter bf2 = new SimpleBloomFilter(getTestShape(), from1);
+        BloomFilter bf2 = new SimpleBloomFilter(getTestShape());
+        bf2.merge(from1);
         bf1.merge(bf2);
         assertTrue(bf2.forEachBitMapPair(bf1, (x, y) -> x == y));
     }
index 99ef6f200a2037b74b3702704c7820da1c0bea24..54eeec90dbe94a69e8b97f3bea2590e0e1f707ce 100644 (file)
@@ -27,4 +27,13 @@ public class UniqueIndexProducerFromHasherCollectionTest extends AbstractIndexPr
     protected IndexProducer createEmptyProducer() {
         return new HasherCollection().uniqueIndices(Shape.fromKM(17, 72));
     }
+
+    @Override
+    protected int getBehaviour() {
+        // Note:
+        // Do not return FOR_EACH_DISTINCT | AS_ARRAY_DISTINCT.
+        // Despite this being a unique index test, the HasherCollection will return a unique
+        // index from each hasher. The result is there may still be duplicates.
+        return 0;
+    }
 }
index 84c17b60f8a78fca631b8faa320034a36d4424b4..94d13e4d922bf22ff8c0eabc141ee8acd9322bbc 100644 (file)
@@ -27,4 +27,10 @@ public class UniqueIndexProducerFromHasherTest extends AbstractIndexProducerTest
     protected IndexProducer createEmptyProducer() {
         return NullHasher.INSTANCE.indices(Shape.fromKM(17, 72));
     }
+
+    @Override
+    protected int getBehaviour() {
+        // Should be unique but may be unordered
+        return FOR_EACH_DISTINCT | AS_ARRAY_DISTINCT;
+    }
 }
diff --git a/src/test/java/org/apache/commons/collections4/bloomfilter/checkstyle.xml b/src/test/java/org/apache/commons/collections4/bloomfilter/checkstyle.xml
deleted file mode 100644 (file)
index 0b79c22..0000000
+++ /dev/null
@@ -1,67 +0,0 @@
-<?xml version="1.0"?>
-<!--
-Licensed to the Apache Software Foundation (ASF) under one or more
-contributor license agreements.  See the NOTICE file distributed with
-this work for additional information regarding copyright ownership.
-The ASF licenses this file to You under the Apache License, Version 2.0
-(the "License"); you may not use this file except in compliance with
-the License.  You may obtain a copy of the License at
-
-     http://www.apache.org/licenses/LICENSE-2.0
-
-Unless required by applicable law or agreed to in writing, software
-distributed under the License is distributed on an "AS IS" BASIS,
-WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-See the License for the specific language governing permissions and
-limitations under the License.
--->
-
-<!DOCTYPE module PUBLIC
-      "-//Checkstyle//DTD Checkstyle Configuration 1.2//EN"
-      "https://checkstyle.org/dtds/configuration_1_2.dtd">
-
-<!-- Apache Commons Collections customization of default Checkstyle behavior -->
-<module name="Checker">
-  <property name="localeLanguage" value="en"/>
-  <module name="JavadocPackage"/>
-  <module name="NewlineAtEndOfFile">
-    <property name="lineSeparator" value="lf" />
-  </module>
-  <module name="FileTabCharacter">
-    <property name="fileExtensions" value="java,xml"/>
-  </module>
-  <module name="RegexpSingleline">
-    <!-- \s matches whitespace character, $ matches end of line. -->
-    <property name="format" value="\s+$"/>
-    <property name="message" value="Line has trailing spaces."/>
-  </module>
-  <module name="SuppressionFilter">
-    <property name="file" value="${checkstyle.suppressions.file}"/>
-  </module>
-  <module name="Header">
-    <property name="headerFile" value="${checkstyle.header.file}"/>
-  </module>
-  <module name="TreeWalker">
-    <module name="AvoidStarImport"/>
-    <module name="IllegalImport"/>
-    <module name="RedundantImport"/>
-    <module name="UnusedImports"/>
-    <module name="NeedBraces"/>
-    <module name="JavadocMethod">
-      <property name="accessModifiers" value="protected" />
-    </module>
-    <module name="ModifierOrder"/>
-    <module name="RedundantModifier"/>
-    <module name="UpperEll" />
-    <module name="LeftCurly"/>
-    <module name="NeedBraces"/>
-    <module name="RightCurly"/>
-    <module name="GenericWhitespace"/>
-    <module name="WhitespaceAfter"/>
-    <module name="NoWhitespaceBefore"/>
-    <module name="Indentation">
-      <!-- Indentation style recommended by Oracle -->
-      <property name="caseIndent" value="0"/>
-    </module>
- </module>
-</module>
index 6896fb5f6c389f7af7bea45b1e79d28f0a9c7253..fa6e20122d45ee76ffca74bbe83f573292ff1c55 100644 (file)
@@ -39,6 +39,7 @@ import java.util.Objects;
 import java.util.function.Predicate;
 
 import org.apache.commons.collections4.AbstractObjectTest;
+import org.junit.jupiter.api.Assertions;
 import org.junit.jupiter.api.Test;
 
 /**
@@ -70,6 +71,13 @@ import org.junit.jupiter.api.Test;
  * <li>{@link #isFailFastSupported()}
  * </ul>
  * <p>
+ * <b>Indicate Collection Behaviour</b>
+ * <p>
+ * Override these if your collection makes specific behaviour guarantees:
+ * <ul>
+ * <li>{@link #getIterationBehaviour()}</li>
+ * </ul>
+ * <p>
  * <b>Fixture Methods</b>
  * <p>
  * Fixtures are used to verify that the operation results in correct state
@@ -134,6 +142,13 @@ public abstract class AbstractCollectionTest<E> extends AbstractObjectTest {
     // tests on Collection.equals nor any for Collection.hashCode.
     //
 
+    /**
+     * Flag to indicate the collection makes no ordering guarantees for the iterator. If this is not used
+     * then the behaviour is assumed to be ordered and the output order of the iterator is matched by
+     * the toArray method.
+     */
+    protected static final int UNORDERED = 0x1;
+
     // These fields are used by reset() and verify(), and any test
     // method that tests a modification.
 
@@ -487,6 +502,18 @@ public abstract class AbstractCollectionTest<E> extends AbstractObjectTest {
         };
     }
 
+    /**
+     * Return a flag specifying the iteration behaviour of the collection.
+     * This is used to change the assertions used by specific tests.
+     * The default implementation returns 0 which indicates ordered iteration behaviour.
+     *
+     * @return the iteration behaviour
+     * @see #UNORDERED
+     */
+    protected int getIterationBehaviour(){
+        return 0;
+    }
+
     // Tests
     /**
      *  Tests {@link Collection#add(Object)}.
@@ -1095,9 +1122,12 @@ public abstract class AbstractCollectionTest<E> extends AbstractObjectTest {
 
         array = getCollection().toArray(new Object[0]);
         a = getCollection().toArray();
-        assertEquals("toArrays should be equal",
-                     Arrays.asList(array), Arrays.asList(a));
 
+        if ((getIterationBehaviour() & UNORDERED) != 0) {
+            assertUnorderedArrayEquals(array, a, "toArray(Object[]) and toArray()");
+        } else {
+            assertEquals("toArrays should be equal", Arrays.asList(array), Arrays.asList(a));
+        }
         // Figure out if they're all the same class
         // TODO: It'd be nicer to detect a common superclass
         final HashSet<Class<?>> classes = new HashSet<>();
@@ -1116,12 +1146,50 @@ public abstract class AbstractCollectionTest<E> extends AbstractObjectTest {
         array = getCollection().toArray(a);
         assertEquals("toArray(Object[]) should return correct array type",
                 a.getClass(), array.getClass());
-        assertEquals("type-specific toArrays should be equal",
-                Arrays.asList(array),
-                Arrays.asList(getCollection().toArray()));
+
+        if ((getIterationBehaviour() & UNORDERED) != 0) {
+            assertUnorderedArrayEquals(array, getCollection().toArray(), "type-specific toArray(T[]) and toArray()");
+        } else {
+            assertEquals("type-specific toArrays should be equal",
+                    Arrays.asList(array),
+                    Arrays.asList(getCollection().toArray()));
+        }
         verify();
     }
 
+    /**
+     * Assert the arrays contain the same elements, ignoring the order.
+     *
+     * <p>Note this does not test the arrays are deeply equal. Array elements are compared
+     * using {@link Object#equals(Object)}.
+     *
+     * @param a1 First array
+     * @param a2 Second array
+     * @param msg Failure message prefix
+     */
+    private static void assertUnorderedArrayEquals(Object[] a1, Object[] a2, String msg) {
+        Assertions.assertEquals(a1.length, a2.length, () -> msg + ": length");
+        final int size = a1.length;
+        // Track values that have been matched once (and only once)
+        final boolean[] matched = new boolean[size];
+        NEXT_OBJECT:
+        for (final Object o : a1) {
+            for (int i = 0; i < size; i++) {
+                if (matched[i]) {
+                    // skip values already matched
+                    continue;
+                }
+                if (Objects.equals(o, a2[i])) {
+                    // values matched
+                    matched[i] = true;
+                    // continue to the outer loop
+                    continue NEXT_OBJECT;
+                }
+            }
+            fail(msg + ": array 2 does not have object: " + o);
+        }
+    }
+
     /**
      *  Tests {@code toString} on a collection.
      */
index 90ac04f992ea0812f273aad8122c63ca100b6d36..243ab6009298ecafc5314ecf5ea540daac9082d5 100644 (file)
@@ -31,16 +31,39 @@ import java.io.ByteArrayOutputStream;
 import java.io.IOException;
 import java.io.PrintStream;
 import java.io.PrintWriter;
+import java.io.UnsupportedEncodingException;
 import java.nio.charset.StandardCharsets;
 import java.util.HashMap;
 import java.util.Properties;
-
 import org.apache.commons.io.input.NullReader;
 import org.apache.commons.lang3.ArrayUtils;
 import org.junit.jupiter.api.Test;
 
 public class EmptyPropertiesTest {
 
+    /**
+     * Returns the first line from multi-lined string separated by a line separator character
+     *
+     * @param x the multi-lined String
+     * @return the first line from x
+     */
+    private String getFirstLine(final String x) {
+        return x.split("\\R", 2)[0];
+    }
+
+    private PrintStream newPrintStream(final ByteArrayOutputStream baos) throws UnsupportedEncodingException {
+        return new PrintStream(baos, true, StandardCharsets.UTF_8.name());
+    }
+
+    private String removeLine2(final ByteArrayOutputStream baos) {
+        return removeLine2(toString(baos));
+    }
+
+    private String removeLine2(final String x) {
+        final String[] s = x.split("\\R", 2);
+        return s[0] + System.lineSeparator() + (s.length > 2 ? s[2] : "");
+    }
+
     @Test
     public void testClear() {
         PropertiesFactory.EMPTY_PROPERTIES.clear();
@@ -133,8 +156,7 @@ public class EmptyPropertiesTest {
 
     @Test
     public void testHashCode() {
-        assertEquals(PropertiesFactory.EMPTY_PROPERTIES.hashCode(),
-            PropertiesFactory.EMPTY_PROPERTIES.hashCode());
+        assertEquals(PropertiesFactory.EMPTY_PROPERTIES.hashCode(), PropertiesFactory.EMPTY_PROPERTIES.hashCode());
         // Should be equals?
         // assertEquals(PropertiesFactory.EMPTY_PROPERTIES.hashCode(), new Properties().hashCode());
     }
@@ -184,7 +206,8 @@ public class EmptyPropertiesTest {
 
     @Test
     public void testLoadFromXML() throws IOException {
-        assertThrows(UnsupportedOperationException.class, () -> PropertiesFactory.EMPTY_PROPERTIES.loadFromXML(new ByteArrayInputStream(ArrayUtils.EMPTY_BYTE_ARRAY)));
+        assertThrows(UnsupportedOperationException.class,
+            () -> PropertiesFactory.EMPTY_PROPERTIES.loadFromXML(new ByteArrayInputStream(ArrayUtils.EMPTY_BYTE_ARRAY)));
     }
 
     @Test
@@ -265,35 +288,25 @@ public class EmptyPropertiesTest {
             PropertiesFactory.INSTANCE.createProperties().store(expected, comments);
 
             // Properties.store stores the specified comment appended with current time stamp in the next line
-            String expectedComment = getFirstLine(expected.toString("UTF-8"));
-            String actualComment = getFirstLine(actual.toString("UTF-8"));
-            assertEquals(expectedComment, actualComment, () ->
-                    String.format("Expected String '%s' with length '%s'", expectedComment, expectedComment.length()));
+            final String expectedComment = getFirstLine(expected.toString("UTF-8"));
+            final String actualComment = getFirstLine(actual.toString("UTF-8"));
+            assertEquals(expectedComment, actualComment,
+                () -> String.format("Expected String '%s' with length '%s'", expectedComment, expectedComment.length()));
             expected.reset();
             try (PrintStream out = new PrintStream(expected)) {
                 new Properties().store(out, comments);
             }
-            String[] expectedLines = expected.toString(StandardCharsets.UTF_8.displayName()).split("\\n");
-            String[] actualLines = actual.toString(StandardCharsets.UTF_8.displayName()).split("\\n");
+            final String[] expectedLines = expected.toString(StandardCharsets.UTF_8.displayName()).split("\\n");
+            final String[] actualLines = actual.toString(StandardCharsets.UTF_8.displayName()).split("\\n");
             assertEquals(expectedLines.length, actualLines.length);
             // The assertion below checks that the comment is the same in both files
             assertEquals(expectedLines[0], actualLines[0]);
             // N.B.: We must not expect expectedLines[1] and actualLines[1] to have the same value as
-            //       it contains the timestamp of when the data was written to the stream, which makes
-            //       this test brittle, causing intermitent failures, see COLLECTIONS-812
+            // it contains the timestamp of when the data was written to the stream, which makes
+            // this test brittle, causing intermitent failures, see COLLECTIONS-812
         }
     }
 
-    /**
-     * Returns the first line from multi-lined string separated by a line separator character
-     * @param x the multi-lined String
-     * @return the first line from x
-     */
-    private String getFirstLine(final String x) {
-        return x.split("\\R", 2)[0];
-    }
-
-
     @Test
     public void testSetProperty() {
         assertThrows(UnsupportedOperationException.class, () -> PropertiesFactory.EMPTY_PROPERTIES.setProperty("Key", "Value"));
@@ -306,63 +319,91 @@ public class EmptyPropertiesTest {
 
     @Test
     public void testStoreToOutputStream() throws IOException {
+        // Note: The second line is always a comment with a timestamp.
         final String comments = "Hello world!";
         // actual
         final ByteArrayOutputStream actual = new ByteArrayOutputStream();
-        PropertiesFactory.EMPTY_PROPERTIES.store(new PrintStream(actual), comments);
+        try (PrintStream ps = newPrintStream(actual)) {
+            PropertiesFactory.EMPTY_PROPERTIES.store(ps, comments);
+        }
         // expected
         final ByteArrayOutputStream expected = new ByteArrayOutputStream();
-        PropertiesFactory.INSTANCE.createProperties().store(new PrintStream(expected), comments);
-        assertArrayEquals(expected.toByteArray(), actual.toByteArray());
+        try (PrintStream ps = newPrintStream(expected)) {
+            PropertiesFactory.INSTANCE.createProperties().store(ps, comments);
+        }
+        assertEquals(removeLine2(expected), removeLine2(actual));
         expected.reset();
-        new Properties().store(new PrintStream(expected), comments);
-        assertArrayEquals(expected.toByteArray(), actual.toByteArray());
+        try (PrintStream ps = newPrintStream(expected)) {
+            new Properties().store(ps, comments);
+        }
+        assertEquals(removeLine2(expected), removeLine2(actual), () -> removeLine2(actual));
     }
 
     @Test
     public void testStoreToPrintWriter() throws IOException {
+        // Note: The second line is always a comment with a timestamp.
         final String comments = "Hello world!";
         // actual
         final ByteArrayOutputStream actual = new ByteArrayOutputStream();
-        PropertiesFactory.EMPTY_PROPERTIES.store(new PrintWriter(actual), comments);
+        try (PrintStream ps = newPrintStream(actual)) {
+            PropertiesFactory.EMPTY_PROPERTIES.store(ps, comments);
+        }
         // expected
         final ByteArrayOutputStream expected = new ByteArrayOutputStream();
-        PropertiesFactory.INSTANCE.createProperties().store(new PrintWriter(expected), comments);
-        assertArrayEquals(expected.toByteArray(), actual.toByteArray());
+        try (PrintStream ps = newPrintStream(expected)) {
+            PropertiesFactory.INSTANCE.createProperties().store(ps, comments);
+        }
+        assertEquals(removeLine2(expected), removeLine2(actual));
         expected.reset();
-        new Properties().store(new PrintWriter(expected), comments);
-        assertArrayEquals(expected.toByteArray(), actual.toByteArray());
+        try (PrintStream ps = newPrintStream(expected)) {
+            new Properties().store(ps, comments);
+        }
+        assertEquals(removeLine2(expected), removeLine2(actual));
     }
 
     @Test
     public void testStoreToXMLOutputStream() throws IOException {
+        // Note: The second line is always a comment with a timestamp.
         final String comments = "Hello world!";
         // actual
         final ByteArrayOutputStream actual = new ByteArrayOutputStream();
-        PropertiesFactory.EMPTY_PROPERTIES.storeToXML(new PrintStream(actual), comments);
+        try (PrintStream ps = newPrintStream(actual)) {
+            PropertiesFactory.EMPTY_PROPERTIES.storeToXML(ps, comments);
+        }
         // expected
         final ByteArrayOutputStream expected = new ByteArrayOutputStream();
-        PropertiesFactory.INSTANCE.createProperties().storeToXML(new PrintStream(expected), comments);
-        assertArrayEquals(expected.toByteArray(), actual.toByteArray());
+        try (PrintStream ps = newPrintStream(expected)) {
+            PropertiesFactory.INSTANCE.createProperties().storeToXML(ps, comments);
+        }
+        assertEquals(toString(expected), toString(actual));
         expected.reset();
-        new Properties().storeToXML(new PrintStream(expected), comments);
-        assertArrayEquals(expected.toByteArray(), actual.toByteArray());
+        try (PrintStream ps = new PrintStream(expected)) {
+            new Properties().storeToXML(ps, comments);
+        }
+        assertEquals(removeLine2(expected), removeLine2(actual));
     }
 
     @Test
     public void testStoreToXMLOutputStreamWithEncoding() throws IOException {
+        // Note: The second line is always a comment with a timestamp.
         final String comments = "Hello world!";
         final String encoding = StandardCharsets.UTF_8.name();
         // actual
         final ByteArrayOutputStream actual = new ByteArrayOutputStream();
-        PropertiesFactory.EMPTY_PROPERTIES.storeToXML(new PrintStream(actual), comments, encoding);
+        try (PrintStream ps = newPrintStream(actual)) {
+            PropertiesFactory.EMPTY_PROPERTIES.storeToXML(ps, comments, encoding);
+        }
         // expected
         final ByteArrayOutputStream expected = new ByteArrayOutputStream();
-        PropertiesFactory.INSTANCE.createProperties().storeToXML(new PrintStream(expected), comments, encoding);
-        assertArrayEquals(expected.toByteArray(), actual.toByteArray());
+        try (PrintStream ps = newPrintStream(expected)) {
+            PropertiesFactory.INSTANCE.createProperties().storeToXML(ps, comments, encoding);
+        }
+        assertEquals(removeLine2(expected), removeLine2(actual));
         expected.reset();
-        new Properties().storeToXML(new PrintStream(expected), comments, encoding);
-        assertArrayEquals(expected.toByteArray(), actual.toByteArray());
+        try (PrintStream ps = newPrintStream(expected)) {
+            new Properties().storeToXML(ps, comments, encoding);
+        }
+        assertEquals(removeLine2(expected), removeLine2(actual));
     }
 
     @Test
@@ -379,4 +420,8 @@ public class EmptyPropertiesTest {
     public void testValues() {
         assertTrue(PropertiesFactory.EMPTY_PROPERTIES.isEmpty());
     }
+
+    private String toString(final ByteArrayOutputStream expected) {
+        return new String(expected.toByteArray(), StandardCharsets.UTF_8);
+    }
 }