This is an automated email from the ASF dual-hosted git repository.
ggregory pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/commons-collections.git
The following commit(s) were added to refs/heads/master by this push:
new 81834a637 Move EnhancedDoubleHasher.mod() to a public BitMap API (#396)
81834a637 is described below
commit 81834a637df3cb09f582dc7fde6372eefa709fab
Author: Claude Warren <[email protected]>
AuthorDate: Tue Jun 13 15:48:18 2023 +0100
Move EnhancedDoubleHasher.mod() to a public BitMap API (#396)
* Made mod() public
* Moved mod() method to BitMap class.
* Add Javadoc since tag
* Added mod() tests and updated documentation.
* fixed formatting issues
---------
Co-authored-by: Gary Gregory <[email protected]>
---
.../commons/collections4/bloomfilter/BitMap.java | 20 ++++++++++++++++++++
.../bloomfilter/EnhancedDoubleHasher.java | 20 ++------------------
.../commons/collections4/bloomfilter/BitMapTest.java | 16 ++++++++++++++++
.../bloomfilter/EnhancedDoubleHasherTest.java | 2 +-
.../collections4/bloomfilter/IncrementingHasher.java | 4 ++--
5 files changed, 41 insertions(+), 21 deletions(-)
diff --git
a/src/main/java/org/apache/commons/collections4/bloomfilter/BitMap.java
b/src/main/java/org/apache/commons/collections4/bloomfilter/BitMap.java
index 14366f96d..8180af708 100644
--- a/src/main/java/org/apache/commons/collections4/bloomfilter/BitMap.java
+++ b/src/main/java/org/apache/commons/collections4/bloomfilter/BitMap.java
@@ -113,4 +113,24 @@ public class BitMap {
// this will identify an incorrect bit.
return 1L << bitIndex;
}
+
+ /**
+ * Performs a modulus calculation on an unsigned long and an positive
integer divisor.
+ *
+ * <p><em>If the divisor is negative the behavior is not defined.</em></p>
+ *
+ * @param dividend a unsigned long value to calculate the modulus of.
+ * @param divisor the divisor for the modulus calculation, must be
positive.
+ * @return the remainder or modulus value.
+ * @since 4.5
+ */
+ public static int mod(final long dividend, final int divisor) {
+ // See Hacker's Delight (2nd ed), section 9.3.
+ // Assume divisor is positive.
+ // Divide half the unsigned number and then double the quotient result.
+ final long quotient = (dividend >>> 1) / divisor << 1;
+ final long remainder = dividend - quotient * divisor;
+ // remainder in [0, 2 * divisor)
+ return (int) (remainder >= divisor ? remainder - divisor : remainder);
+ }
}
diff --git
a/src/main/java/org/apache/commons/collections4/bloomfilter/EnhancedDoubleHasher.java
b/src/main/java/org/apache/commons/collections4/bloomfilter/EnhancedDoubleHasher.java
index d4091cdd2..c490ad6c5 100644
---
a/src/main/java/org/apache/commons/collections4/bloomfilter/EnhancedDoubleHasher.java
+++
b/src/main/java/org/apache/commons/collections4/bloomfilter/EnhancedDoubleHasher.java
@@ -129,22 +129,6 @@ public class EnhancedDoubleHasher implements Hasher {
return increment;
}
- /**
- * Performs a modulus calculation on an unsigned long and an integer
divisor.
- * @param dividend a unsigned long value to calculate the modulus of.
- * @param divisor the divisor for the modulus calculation (must be
strictly positive).
- * @return the remainder or modulus value.
- */
- static int mod(final long dividend, final int divisor) {
- // See Hacker's Delight (2nd ed), section 9.3.
- // Assume divisor is positive.
- // Divide half the unsigned number and then double the quotient result.
- final long quotient = (dividend >>> 1) / divisor << 1;
- final long remainder = dividend - quotient * divisor;
- // remainder in [0, 2 * divisor)
- return (int) (remainder >= divisor ? remainder - divisor : remainder);
- }
-
@Override
public IndexProducer indices(final Shape shape) {
Objects.requireNonNull(shape, "shape");
@@ -168,8 +152,8 @@ public class EnhancedDoubleHasher implements Hasher {
// The final hash is:
// hash[i] = ( h1(x) - i*h2(x) - (i*i*i - i)/6 ) wrapped in
[0, bits)
- int index = mod(initial, bits);
- int inc = mod(increment, bits);
+ int index = BitMap.mod(initial, bits);
+ int inc = BitMap.mod(increment, bits);
final int k = shape.getNumberOfHashFunctions();
if (k > bits) {
diff --git
a/src/test/java/org/apache/commons/collections4/bloomfilter/BitMapTest.java
b/src/test/java/org/apache/commons/collections4/bloomfilter/BitMapTest.java
index a0b7b8a92..ab0444e99 100644
--- a/src/test/java/org/apache/commons/collections4/bloomfilter/BitMapTest.java
+++ b/src/test/java/org/apache/commons/collections4/bloomfilter/BitMapTest.java
@@ -16,6 +16,7 @@
*/
package org.apache.commons.collections4.bloomfilter;
+import static org.junit.Assert.assertNotEquals;
import static org.junit.jupiter.api.Assertions.assertEquals;
import static org.junit.jupiter.api.Assertions.assertFalse;
import static org.junit.jupiter.api.Assertions.assertThrows;
@@ -102,4 +103,19 @@ public class BitMapTest {
ary[1] = 1;
assertTrue(BitMap.contains(ary, 64));
}
+
+ private void assertMod(long l, int i) {
+ assertEquals(Math.floorMod(l, i), BitMap.mod(l, i));
+ }
+
+ @Test
+ public final void testMod() {
+ assertMod(Long.MAX_VALUE, Integer.MAX_VALUE);
+ assertMod(Long.MAX_VALUE, Integer.MAX_VALUE-1);
+ assertThrows(ArithmeticException.class, () ->
BitMap.mod(Long.MAX_VALUE, 0));
+ assertMod(Long.MAX_VALUE-1, Integer.MAX_VALUE);
+ assertMod(Long.MAX_VALUE-1, Integer.MAX_VALUE-1);
+ assertMod(0, Integer.MAX_VALUE);
+ assertNotEquals(Math.floorMod(5, -1), BitMap.mod(5, -1));
+ }
}
diff --git
a/src/test/java/org/apache/commons/collections4/bloomfilter/EnhancedDoubleHasherTest.java
b/src/test/java/org/apache/commons/collections4/bloomfilter/EnhancedDoubleHasherTest.java
index 112b4def6..107a06320 100644
---
a/src/test/java/org/apache/commons/collections4/bloomfilter/EnhancedDoubleHasherTest.java
+++
b/src/test/java/org/apache/commons/collections4/bloomfilter/EnhancedDoubleHasherTest.java
@@ -99,7 +99,7 @@ public class EnhancedDoubleHasherTest extends
AbstractHasherTest {
for (final long dividend : new long[] {-1, -2, -3, -6378683,
-23567468136887892L, Long.MIN_VALUE, 345, 678686,
67868768686878924L, Long.MAX_VALUE}) {
for (final int divisor : new int[] {1, 2, 3, 5, 13,
Integer.MAX_VALUE}) {
- assertEquals((int) Long.remainderUnsigned(dividend, divisor),
EnhancedDoubleHasher.mod(dividend, divisor),
+ assertEquals((int) Long.remainderUnsigned(dividend, divisor),
BitMap.mod(dividend, divisor),
() -> String.format("failure with dividend=%s and
divisor=%s.", dividend, divisor));
}
}
diff --git
a/src/test/java/org/apache/commons/collections4/bloomfilter/IncrementingHasher.java
b/src/test/java/org/apache/commons/collections4/bloomfilter/IncrementingHasher.java
index 94b77c5d5..ac0fd5111 100644
---
a/src/test/java/org/apache/commons/collections4/bloomfilter/IncrementingHasher.java
+++
b/src/test/java/org/apache/commons/collections4/bloomfilter/IncrementingHasher.java
@@ -66,8 +66,8 @@ final class IncrementingHasher implements Hasher {
// This avoids any modulus operation inside the while loop. It
uses a long index
// to avoid overflow.
- long index = EnhancedDoubleHasher.mod(initial, bits);
- final int inc = EnhancedDoubleHasher.mod(increment, bits);
+ long index = BitMap.mod(initial, bits);
+ final int inc = BitMap.mod(increment, bits);
for (int functionalCount = 0; functionalCount <
shape.getNumberOfHashFunctions(); functionalCount++) {
if (!consumer.test((int) index)) {
