You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@commons.apache.org by GitBox <gi...@apache.org> on 2020/02/17 21:44:43 UTC
[GitHub] [commons-collections] Claudenw opened a new pull request #131:
Added caching hasher
Claudenw opened a new pull request #131: Added caching hasher
URL: https://github.com/apache/commons-collections/pull/131
Fix for COLLECTIONS-750
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
[GitHub] [commons-collections] aherbert commented on a change in pull
request #131: Added caching hasher
Posted by GitBox <gi...@apache.org>.
aherbert commented on a change in pull request #131: Added caching hasher
URL: https://github.com/apache/commons-collections/pull/131#discussion_r387513930
##########
File path: src/main/java/org/apache/commons/collections4/bloomfilter/hasher/CachingHasher.java
##########
@@ -0,0 +1,233 @@
+/*
+ * 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.hasher;
+
+import java.nio.charset.StandardCharsets;
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.List;
+import java.util.NoSuchElementException;
+import java.util.PrimitiveIterator;
+
+import org.apache.commons.collections4.bloomfilter.hasher.HashFunctionIdentity.ProcessType;
+
+/**
+ * An implementation of Hasher that attempts to leak as little data as possible.
+ * Each item in the hasher is represented by two (2) longs. So this Hasher will
+ * still indicate how many items are in the hasher but will not leak the buffers
+ * that are being hashed as the @code DynamicHasher} does.
+ * <p>
+ * This hasher only accepts HashFunctions that are cyclic in nature.
+ * </p>
+ * @see DynamicHasher
+ * @see ProcessType
+ */
+public class CachingHasher implements Hasher {
+
+ /**
+ * The list of byte arrays that are to be hashed.
+ */
+ private final List<long[]> buffers;
+
+ /**
+ * The hash function identity
+ */
+ private final HashFunctionIdentity functionIdentity;
+
+ /**
+ * Constructs a CachingHasher from a list of arrays of hash values.
+ * <p>
+ * The list of hash values comprises a @code{List<long[]>} where each @code{long[]}
+ * is comprises two (2) values that are the result of hashing the original buffer. Thus a
+ * CachingHasher that was built from five (5) buffers will have five arrays of two @code{longs}
Review comment:
{@code long}s
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
[GitHub] [commons-collections] aherbert commented on a change in pull
request #131: Added caching hasher
Posted by GitBox <gi...@apache.org>.
aherbert commented on a change in pull request #131: Added caching hasher
URL: https://github.com/apache/commons-collections/pull/131#discussion_r387520802
##########
File path: src/test/java/org/apache/commons/collections4/bloomfilter/hasher/CachingHasherTest.java
##########
@@ -0,0 +1,241 @@
+/*
+ * 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.hasher;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertTrue;
+import static org.junit.Assert.fail;
+
+import java.util.List;
+import java.util.NoSuchElementException;
+import java.util.PrimitiveIterator;
+import java.util.PrimitiveIterator.OfInt;
+
+import org.apache.commons.collections4.bloomfilter.hasher.function.MD5Cyclic;
+import org.junit.Before;
+import org.junit.Test;
+
+/**
+ * Tests the {@link CachingHasher}.
+ */
+public class CachingHasherTest {
+ private CachingHasher.Builder builder;
+ private Shape shape;
+
+ private final HashFunctionIdentity testFunction = new HashFunctionIdentity() {
+
+ @Override
+ public String getName() {
+ return "Test Function";
+ }
+
+ @Override
+ public ProcessType getProcessType() {
+ return ProcessType.CYCLIC;
+ }
+
+ @Override
+ public String getProvider() {
+ return "Apache Commons Collection Tests";
+ }
+
+ @Override
+ public long getSignature() {
+ return 0;
+ }
+
+ @Override
+ public Signedness getSignedness() {
+ return Signedness.SIGNED;
+ }
+ };
+
+ /**
+ * Sets up the CachingHasher.
+ */
+ @Before
+ public void setup() {
+ builder = new CachingHasher.Builder(new MD5Cyclic());
+ shape = new Shape(new MD5Cyclic(), 3, 72, 17);
+ }
+
+ /**
+ * Tests that the expected bits are returned from hashing.
+ */
+ @Test
+ public void testGetBits() {
+
+ final int[] expected = { 6, 69, 44, 19, 10, 57, 48, 23, 70, 61, 36, 11, 2, 49, 24, 15, 62 };
+
+ final Hasher hasher = builder.with("Hello").build();
+
+ final OfInt iter = hasher.getBits(shape);
+
+ for (final int element : expected) {
+ assertTrue(iter.hasNext());
+ assertEquals(element, iter.nextInt());
+ }
+ assertFalse(iter.hasNext());
+ }
+
+ /**
+ * Tests that bits from multiple hashes are returned correctly.
+ */
+ @Test
+ public void testGetBits_MultipleHashes() {
+ final int[] expected = { 6, 69, 44, 19, 10, 57, 48, 23, 70, 61, 36, 11, 2, 49, 24, 15, 62, 1, 63, 53, 43, 17, 7,
+ 69, 59, 49, 39, 13, 3, 65, 55, 45, 35, 25 };
+
+ final Hasher hasher = builder.with("Hello").with("World").build();
+
+ final OfInt iter = hasher.getBits(shape);
+
+ for (final int element : expected) {
+ assertTrue(iter.hasNext());
+ assertEquals(element, iter.nextInt());
+ }
+ assertFalse(iter.hasNext());
+ try {
+ iter.next();
+ fail("Should have thown NoSuchElementException");
+ } catch (final NoSuchElementException ignore) {
+ // do nothing
+ }
+ }
+
+ /**
+ * Tests that retrieving bits for the wrong shape throws an exception.
+ */
+ @Test
+ public void testGetBits_WongShape() {
+
+ final Hasher hasher = builder.with("Hello").build();
+
+ try {
+ hasher.getBits(new Shape(testFunction, 3, 72, 17));
+ fail("Should have thown IllegalArgumentException");
+ } catch (final IllegalArgumentException expected) {
+ // do nothing
+ }
+ }
+
+ /**
+ * Tests if isEmpty() reports correctly and the iterator returns no values.
+ */
+ @Test
+ public void testIsEmpty() {
+ CachingHasher hasher = builder.build();
+ assertTrue(hasher.isEmpty());
+ final OfInt iter = hasher.getBits(shape);
+ assertFalse(iter.hasNext());
+ try {
+ iter.next();
+ fail("Should have thown NoSuchElementException");
+ } catch (final NoSuchElementException expected) {
+ // do nothing
+ }
+
+ assertFalse(builder.with("Hello").build().isEmpty());
+ }
+
+ @Test
+ public void testNonCyclicHashFunction() {
+ HashFunctionIdentity hfi = new HashFunctionIdentity() {
Review comment:
Cleaner to use HashFunctionIdentityImpl here.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
[GitHub] [commons-collections] Claudenw commented on a change in pull
request #131: Added caching hasher
Posted by GitBox <gi...@apache.org>.
Claudenw commented on a change in pull request #131: Added caching hasher
URL: https://github.com/apache/commons-collections/pull/131#discussion_r389242745
##########
File path: src/main/java/org/apache/commons/collections4/bloomfilter/hasher/CachingHasher.java
##########
@@ -0,0 +1,233 @@
+/*
+ * 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.hasher;
+
+import java.nio.charset.StandardCharsets;
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.List;
+import java.util.NoSuchElementException;
+import java.util.PrimitiveIterator;
+
+import org.apache.commons.collections4.bloomfilter.hasher.HashFunctionIdentity.ProcessType;
+
+/**
+ * An implementation of Hasher that attempts to leak as little data as possible.
+ * Each item in the hasher is represented by two (2) longs. So this Hasher will
+ * still indicate how many items are in the hasher but will not leak the buffers
+ * that are being hashed as the @code DynamicHasher} does.
+ * <p>
+ * This hasher only accepts HashFunctions that are cyclic in nature.
+ * </p>
+ * @see DynamicHasher
+ * @see ProcessType
+ */
+public class CachingHasher implements Hasher {
+
+ /**
+ * The list of byte arrays that are to be hashed.
+ */
+ private final List<long[]> buffers;
+
+ /**
+ * The hash function identity
+ */
+ private final HashFunctionIdentity functionIdentity;
+
+ /**
+ * Constructs a CachingHasher from a list of arrays of hash values.
+ * <p>
+ * The list of hash values comprises a @code{List<long[]>} where each @code{long[]}
+ * is comprises two (2) values that are the result of hashing the original buffer. Thus a
+ * CachingHasher that was built from five (5) buffers will have five arrays of two @code{longs}
+ * each.
+ * </p>
+ * @param functionIdentity The identity of the function.
+ * @param buffers a list of @code{long} arrays comprising two (2) values.
+ * @throws IllegalArgumentException if the name does not indicate a cyclic
+ * hashing function.
+ */
+ public CachingHasher(HashFunctionIdentity functionIdentity, List<long[]> buffers) {
+ this.functionIdentity = checkIdentity(functionIdentity);
+ this.buffers = new ArrayList<long[]>(buffers);
+ }
+
+ /**
+ * Constructs a CachingHasher from an array of arrys of hash values.
+ *
+ * @param functionIdentity The identity of the function.
+ * @param buffers an array of @code{long} arrays comprising two (2) values.
+ * @throws IllegalArgumentException if the name does not indicate a cyclic
+ * hashing function.
+ */
+ public CachingHasher(HashFunctionIdentity functionIdentity, long[][] buffers) {
+ this.functionIdentity = checkIdentity(functionIdentity);
+ this.buffers = Arrays.asList(buffers);
+ }
+
+ /**
+ * Checks that the name is valid for this hasher.
+ *
+ * @param functionIdentity the Function Identity to check.
+ */
+ private static HashFunctionIdentity checkIdentity(HashFunctionIdentity functionIdentity) {
+ if (functionIdentity.getProcessType() != ProcessType.CYCLIC) {
+ throw new IllegalArgumentException("Only cyclic hash functions may be used in a caching hasher");
+ }
+ return functionIdentity;
+ }
+
+ @Override
+ public HashFunctionIdentity getHashFunctionIdentity() {
+ return functionIdentity;
+ }
+
+ @Override
+ public boolean isEmpty() {
+ return buffers.isEmpty();
+ }
+
+
+ @Override
+ public PrimitiveIterator.OfInt getBits(Shape shape) {
+ HashFunctionValidator.checkAreEqual(getHashFunctionIdentity(),
+ shape.getHashFunctionIdentity());
+ return new IntIterator(shape);
+ }
+
+ /**
+ * Gets the long representations of the buffers.
+ * <p>
+ * This method returns the long representations of the buffers. This is commonly used
+ * to transmit the Hasher from one system to another.
+ * </p>
+ * @return a copy if the long buffer representation.
+ */
+ public List<long[]> getBuffers() {
+ return new ArrayList<long[]>( buffers );
+ }
+
+ /**
+ * The iterator of integers.
+ */
+ private class IntIterator implements PrimitiveIterator.OfInt {
+ private int buffer = 0;
+ private int funcCount = 0;
+ private final Shape shape;
+ private long accumulator;
+
+ /**
+ * Creates iterator with the specified shape.
+ *
+ * @param shape
+ */
+ private IntIterator(Shape shape) {
+ this.shape = shape;
+ this.accumulator = buffers.isEmpty() ? 0 : buffers.get(0)[0];
+ }
+
+ @Override
+ public boolean hasNext() {
+ if (buffers.isEmpty()) {
+ return false;
+ }
+ return buffer < buffers.size() - 1 || funcCount < shape.getNumberOfHashFunctions();
+ }
+
+ @Override
+ public int nextInt() {
+ if (hasNext()) {
+ if (funcCount >= shape.getNumberOfHashFunctions()) {
+ funcCount = 0;
+ buffer++;
+ accumulator = buffers.get(buffer)[0];
+ }
+ int result = (int) Math.floorMod(accumulator, (long) shape.getNumberOfBits());
+ funcCount++;
+ accumulator += buffers.get(buffer)[1];
+ return result;
+ }
+ throw new NoSuchElementException();
+ }
+
+ }
+
+ /**
+ * The builder for CachingHashers.
+ *
+ * @since 4.5
+ */
+ public static class Builder implements Hasher.Builder {
+ /**
+ * The list of byte[] that are to be hashed.
+ */
+ private List<byte[]> buffers;
+
+ /**
+ * The function that the resulting DynamicHasher will use.
+ */
+ private HashFunction function;
+
+ /**
+ * Constructs a CachingHashers builder.
+ *
+ * @param function the function implementation.
+ * @throws IllegalArgumentException if the function is not a cyclic implementation.
+ */
+ public Builder(HashFunction function) {
+ checkIdentity(function);
+ this.function = function;
+ this.buffers = new ArrayList<byte[]>();
+
+ }
+
+ /**
+ * Builds the hasher.
+ *
+ * @return A CachingHashers with the specified name, function and buffers.
+ */
+ @Override
+ public CachingHasher build() throws IllegalArgumentException {
+ List<long[]> cache = new ArrayList<long[]>();
Review comment:
fixed
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
[GitHub] [commons-collections] aherbert commented on a change in pull
request #131: Added caching hasher
Posted by GitBox <gi...@apache.org>.
aherbert commented on a change in pull request #131: Added caching hasher
URL: https://github.com/apache/commons-collections/pull/131#discussion_r387517823
##########
File path: src/main/java/org/apache/commons/collections4/bloomfilter/hasher/HashFunctionValidator.java
##########
@@ -20,7 +20,7 @@
/**
* Contains validation for hash functions.
*/
-final class HashFunctionValidator {
+public final class HashFunctionValidator {
Review comment:
Why make this public here? That would fix it in the API. Currently it is only used internally.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
[GitHub] [commons-collections] aherbert commented on a change in pull
request #131: Added caching hasher
Posted by GitBox <gi...@apache.org>.
aherbert commented on a change in pull request #131: Added caching hasher
URL: https://github.com/apache/commons-collections/pull/131#discussion_r387521443
##########
File path: src/test/java/org/apache/commons/collections4/bloomfilter/hasher/CachingHasherTest.java
##########
@@ -0,0 +1,241 @@
+/*
+ * 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.hasher;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertTrue;
+import static org.junit.Assert.fail;
+
+import java.util.List;
+import java.util.NoSuchElementException;
+import java.util.PrimitiveIterator;
+import java.util.PrimitiveIterator.OfInt;
+
+import org.apache.commons.collections4.bloomfilter.hasher.function.MD5Cyclic;
+import org.junit.Before;
+import org.junit.Test;
+
+/**
+ * Tests the {@link CachingHasher}.
+ */
+public class CachingHasherTest {
+ private CachingHasher.Builder builder;
+ private Shape shape;
+
+ private final HashFunctionIdentity testFunction = new HashFunctionIdentity() {
+
+ @Override
+ public String getName() {
+ return "Test Function";
+ }
+
+ @Override
+ public ProcessType getProcessType() {
+ return ProcessType.CYCLIC;
+ }
+
+ @Override
+ public String getProvider() {
+ return "Apache Commons Collection Tests";
+ }
+
+ @Override
+ public long getSignature() {
+ return 0;
+ }
+
+ @Override
+ public Signedness getSignedness() {
+ return Signedness.SIGNED;
+ }
+ };
+
+ /**
+ * Sets up the CachingHasher.
+ */
+ @Before
+ public void setup() {
+ builder = new CachingHasher.Builder(new MD5Cyclic());
+ shape = new Shape(new MD5Cyclic(), 3, 72, 17);
+ }
+
+ /**
+ * Tests that the expected bits are returned from hashing.
+ */
+ @Test
+ public void testGetBits() {
+
+ final int[] expected = { 6, 69, 44, 19, 10, 57, 48, 23, 70, 61, 36, 11, 2, 49, 24, 15, 62 };
+
+ final Hasher hasher = builder.with("Hello").build();
+
+ final OfInt iter = hasher.getBits(shape);
+
+ for (final int element : expected) {
+ assertTrue(iter.hasNext());
+ assertEquals(element, iter.nextInt());
+ }
+ assertFalse(iter.hasNext());
+ }
+
+ /**
+ * Tests that bits from multiple hashes are returned correctly.
+ */
+ @Test
+ public void testGetBits_MultipleHashes() {
+ final int[] expected = { 6, 69, 44, 19, 10, 57, 48, 23, 70, 61, 36, 11, 2, 49, 24, 15, 62, 1, 63, 53, 43, 17, 7,
+ 69, 59, 49, 39, 13, 3, 65, 55, 45, 35, 25 };
+
+ final Hasher hasher = builder.with("Hello").with("World").build();
+
+ final OfInt iter = hasher.getBits(shape);
+
+ for (final int element : expected) {
+ assertTrue(iter.hasNext());
+ assertEquals(element, iter.nextInt());
+ }
+ assertFalse(iter.hasNext());
+ try {
+ iter.next();
+ fail("Should have thown NoSuchElementException");
+ } catch (final NoSuchElementException ignore) {
+ // do nothing
+ }
+ }
+
+ /**
+ * Tests that retrieving bits for the wrong shape throws an exception.
+ */
+ @Test
+ public void testGetBits_WongShape() {
+
+ final Hasher hasher = builder.with("Hello").build();
+
+ try {
+ hasher.getBits(new Shape(testFunction, 3, 72, 17));
+ fail("Should have thown IllegalArgumentException");
+ } catch (final IllegalArgumentException expected) {
+ // do nothing
+ }
+ }
+
+ /**
+ * Tests if isEmpty() reports correctly and the iterator returns no values.
+ */
+ @Test
+ public void testIsEmpty() {
+ CachingHasher hasher = builder.build();
+ assertTrue(hasher.isEmpty());
+ final OfInt iter = hasher.getBits(shape);
+ assertFalse(iter.hasNext());
+ try {
+ iter.next();
+ fail("Should have thown NoSuchElementException");
+ } catch (final NoSuchElementException expected) {
+ // do nothing
+ }
+
+ assertFalse(builder.with("Hello").build().isEmpty());
+ }
+
+ @Test
+ public void testNonCyclicHashFunction() {
+ HashFunctionIdentity hfi = new HashFunctionIdentity() {
+
+ @Override
+ public String getName() {
+ return "Testing-NonCyclic-Hash";
+ }
+
+ @Override
+ public ProcessType getProcessType() {
+ return ProcessType.ITERATIVE;
+ }
+
+ @Override
+ public String getProvider() {
+ return "Apache Commons Collection Testing";
+ }
+
+ @Override
+ public long getSignature() {
+ return 0;
+ }
+
+ @Override
+ public Signedness getSignedness() {
+ return Signedness.SIGNED;
+ }
+ };
+
+ try {
+ new CachingHasher(hfi, new long[][] { { 1, 4 }, { 3, 6 } });
+ fail("Should have thrown exception");
+ } catch (IllegalArgumentException expected) {
+ // do nothing.
+ }
+
+ }
+
+ @Test
+ public void testGetBuffers() {
+ final CachingHasher hasher = builder.with("Hello").build();
+
+ List<long[]> buffers = hasher.getBuffers();
+ HashFunctionIdentity id = hasher.getHashFunctionIdentity();
+
+ CachingHasher hasher2 = new CachingHasher( id, buffers );
+
+ PrimitiveIterator.OfInt iter1 = hasher.getBits(shape);
+ PrimitiveIterator.OfInt iter2 = hasher2.getBits(shape);
+
+ while (iter1.hasNext())
+ {
+ assertTrue( "Too few values in second hasher", iter2.hasNext());
+ assertEquals( "Wrong value", iter1.next(), iter2.next() );
+ }
+ assertFalse( "Second hasher has too many values", iter2.hasNext());
+ }
+
+ @Test
+ public void testConstructorWithLongArray() {
+ final CachingHasher hasher = builder.with("Hello").build();
+
+ List<long[]> buffers = hasher.getBuffers();
+ assertEquals( 1, buffers.size() );
+
+ long[][] ary = new long[1][];
+ ary[0] = buffers.get(0);
+
+ HashFunctionIdentity id = hasher.getHashFunctionIdentity();
+
+
+ CachingHasher hasher2 = new CachingHasher( id, ary );
+
+ PrimitiveIterator.OfInt iter1 = hasher.getBits(shape);
+ PrimitiveIterator.OfInt iter2 = hasher2.getBits(shape);
+
+ while (iter1.hasNext())
+ {
Review comment:
Another `{` on the wrong line
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
[GitHub] [commons-collections] aherbert commented on a change in pull
request #131: Added caching hasher
Posted by GitBox <gi...@apache.org>.
aherbert commented on a change in pull request #131: Added caching hasher
URL: https://github.com/apache/commons-collections/pull/131#discussion_r387521613
##########
File path: src/test/java/org/apache/commons/collections4/bloomfilter/hasher/CachingHasherTest.java
##########
@@ -0,0 +1,241 @@
+/*
+ * 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.hasher;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertTrue;
+import static org.junit.Assert.fail;
+
+import java.util.List;
+import java.util.NoSuchElementException;
+import java.util.PrimitiveIterator;
+import java.util.PrimitiveIterator.OfInt;
+
+import org.apache.commons.collections4.bloomfilter.hasher.function.MD5Cyclic;
+import org.junit.Before;
+import org.junit.Test;
+
+/**
+ * Tests the {@link CachingHasher}.
+ */
+public class CachingHasherTest {
+ private CachingHasher.Builder builder;
+ private Shape shape;
+
+ private final HashFunctionIdentity testFunction = new HashFunctionIdentity() {
+
+ @Override
+ public String getName() {
+ return "Test Function";
+ }
+
+ @Override
+ public ProcessType getProcessType() {
+ return ProcessType.CYCLIC;
+ }
+
+ @Override
+ public String getProvider() {
+ return "Apache Commons Collection Tests";
+ }
+
+ @Override
+ public long getSignature() {
+ return 0;
+ }
+
+ @Override
+ public Signedness getSignedness() {
+ return Signedness.SIGNED;
+ }
+ };
+
+ /**
+ * Sets up the CachingHasher.
+ */
+ @Before
+ public void setup() {
+ builder = new CachingHasher.Builder(new MD5Cyclic());
+ shape = new Shape(new MD5Cyclic(), 3, 72, 17);
+ }
+
+ /**
+ * Tests that the expected bits are returned from hashing.
+ */
+ @Test
+ public void testGetBits() {
+
+ final int[] expected = { 6, 69, 44, 19, 10, 57, 48, 23, 70, 61, 36, 11, 2, 49, 24, 15, 62 };
+
+ final Hasher hasher = builder.with("Hello").build();
+
+ final OfInt iter = hasher.getBits(shape);
+
+ for (final int element : expected) {
+ assertTrue(iter.hasNext());
+ assertEquals(element, iter.nextInt());
+ }
+ assertFalse(iter.hasNext());
+ }
+
+ /**
+ * Tests that bits from multiple hashes are returned correctly.
+ */
+ @Test
+ public void testGetBits_MultipleHashes() {
+ final int[] expected = { 6, 69, 44, 19, 10, 57, 48, 23, 70, 61, 36, 11, 2, 49, 24, 15, 62, 1, 63, 53, 43, 17, 7,
+ 69, 59, 49, 39, 13, 3, 65, 55, 45, 35, 25 };
+
+ final Hasher hasher = builder.with("Hello").with("World").build();
+
+ final OfInt iter = hasher.getBits(shape);
+
+ for (final int element : expected) {
+ assertTrue(iter.hasNext());
+ assertEquals(element, iter.nextInt());
+ }
+ assertFalse(iter.hasNext());
+ try {
+ iter.next();
+ fail("Should have thown NoSuchElementException");
+ } catch (final NoSuchElementException ignore) {
+ // do nothing
+ }
+ }
+
+ /**
+ * Tests that retrieving bits for the wrong shape throws an exception.
+ */
+ @Test
+ public void testGetBits_WongShape() {
+
Review comment:
empty line
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
[GitHub] [commons-collections] aherbert commented on a change in pull
request #131: Added caching hasher
Posted by GitBox <gi...@apache.org>.
aherbert commented on a change in pull request #131: Added caching hasher
URL: https://github.com/apache/commons-collections/pull/131#discussion_r387519064
##########
File path: src/test/java/org/apache/commons/collections4/bloomfilter/hasher/CachingHasherTest.java
##########
@@ -0,0 +1,241 @@
+/*
+ * 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.hasher;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertTrue;
+import static org.junit.Assert.fail;
+
+import java.util.List;
+import java.util.NoSuchElementException;
+import java.util.PrimitiveIterator;
+import java.util.PrimitiveIterator.OfInt;
+
+import org.apache.commons.collections4.bloomfilter.hasher.function.MD5Cyclic;
+import org.junit.Before;
+import org.junit.Test;
+
+/**
+ * Tests the {@link CachingHasher}.
+ */
+public class CachingHasherTest {
+ private CachingHasher.Builder builder;
+ private Shape shape;
+
+ private final HashFunctionIdentity testFunction = new HashFunctionIdentity() {
+
+ @Override
+ public String getName() {
+ return "Test Function";
+ }
+
+ @Override
+ public ProcessType getProcessType() {
+ return ProcessType.CYCLIC;
+ }
+
+ @Override
+ public String getProvider() {
+ return "Apache Commons Collection Tests";
+ }
+
+ @Override
+ public long getSignature() {
+ return 0;
+ }
+
+ @Override
+ public Signedness getSignedness() {
+ return Signedness.SIGNED;
+ }
+ };
+
+ /**
+ * Sets up the CachingHasher.
+ */
+ @Before
+ public void setup() {
+ builder = new CachingHasher.Builder(new MD5Cyclic());
+ shape = new Shape(new MD5Cyclic(), 3, 72, 17);
+ }
+
+ /**
+ * Tests that the expected bits are returned from hashing.
+ */
+ @Test
+ public void testGetBits() {
+
Review comment:
Empty line
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
[GitHub] [commons-collections] Claudenw commented on a change in pull
request #131: Added caching hasher
Posted by GitBox <gi...@apache.org>.
Claudenw commented on a change in pull request #131: Added caching hasher
URL: https://github.com/apache/commons-collections/pull/131#discussion_r389242984
##########
File path: src/test/java/org/apache/commons/collections4/bloomfilter/hasher/CachingHasherTest.java
##########
@@ -0,0 +1,241 @@
+/*
+ * 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.hasher;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertTrue;
+import static org.junit.Assert.fail;
+
+import java.util.List;
+import java.util.NoSuchElementException;
+import java.util.PrimitiveIterator;
+import java.util.PrimitiveIterator.OfInt;
+
+import org.apache.commons.collections4.bloomfilter.hasher.function.MD5Cyclic;
+import org.junit.Before;
+import org.junit.Test;
+
+/**
+ * Tests the {@link CachingHasher}.
+ */
+public class CachingHasherTest {
+ private CachingHasher.Builder builder;
+ private Shape shape;
+
+ private final HashFunctionIdentity testFunction = new HashFunctionIdentity() {
+
+ @Override
+ public String getName() {
+ return "Test Function";
+ }
+
+ @Override
+ public ProcessType getProcessType() {
+ return ProcessType.CYCLIC;
+ }
+
+ @Override
+ public String getProvider() {
+ return "Apache Commons Collection Tests";
+ }
+
+ @Override
+ public long getSignature() {
+ return 0;
+ }
+
+ @Override
+ public Signedness getSignedness() {
+ return Signedness.SIGNED;
+ }
+ };
+
+ /**
+ * Sets up the CachingHasher.
+ */
+ @Before
+ public void setup() {
+ builder = new CachingHasher.Builder(new MD5Cyclic());
+ shape = new Shape(new MD5Cyclic(), 3, 72, 17);
+ }
+
+ /**
+ * Tests that the expected bits are returned from hashing.
+ */
+ @Test
+ public void testGetBits() {
+
+ final int[] expected = { 6, 69, 44, 19, 10, 57, 48, 23, 70, 61, 36, 11, 2, 49, 24, 15, 62 };
+
+ final Hasher hasher = builder.with("Hello").build();
+
+ final OfInt iter = hasher.getBits(shape);
+
+ for (final int element : expected) {
+ assertTrue(iter.hasNext());
+ assertEquals(element, iter.nextInt());
+ }
+ assertFalse(iter.hasNext());
+ }
+
+ /**
+ * Tests that bits from multiple hashes are returned correctly.
+ */
+ @Test
+ public void testGetBits_MultipleHashes() {
+ final int[] expected = { 6, 69, 44, 19, 10, 57, 48, 23, 70, 61, 36, 11, 2, 49, 24, 15, 62, 1, 63, 53, 43, 17, 7,
+ 69, 59, 49, 39, 13, 3, 65, 55, 45, 35, 25 };
+
+ final Hasher hasher = builder.with("Hello").with("World").build();
+
+ final OfInt iter = hasher.getBits(shape);
+
+ for (final int element : expected) {
+ assertTrue(iter.hasNext());
+ assertEquals(element, iter.nextInt());
+ }
+ assertFalse(iter.hasNext());
+ try {
+ iter.next();
+ fail("Should have thown NoSuchElementException");
+ } catch (final NoSuchElementException ignore) {
+ // do nothing
+ }
+ }
+
+ /**
+ * Tests that retrieving bits for the wrong shape throws an exception.
+ */
+ @Test
+ public void testGetBits_WongShape() {
+
+ final Hasher hasher = builder.with("Hello").build();
+
+ try {
+ hasher.getBits(new Shape(testFunction, 3, 72, 17));
+ fail("Should have thown IllegalArgumentException");
+ } catch (final IllegalArgumentException expected) {
+ // do nothing
+ }
+ }
+
+ /**
+ * Tests if isEmpty() reports correctly and the iterator returns no values.
+ */
+ @Test
+ public void testIsEmpty() {
+ CachingHasher hasher = builder.build();
+ assertTrue(hasher.isEmpty());
+ final OfInt iter = hasher.getBits(shape);
+ assertFalse(iter.hasNext());
+ try {
+ iter.next();
+ fail("Should have thown NoSuchElementException");
+ } catch (final NoSuchElementException expected) {
+ // do nothing
+ }
+
+ assertFalse(builder.with("Hello").build().isEmpty());
+ }
+
+ @Test
+ public void testNonCyclicHashFunction() {
+ HashFunctionIdentity hfi = new HashFunctionIdentity() {
+
+ @Override
+ public String getName() {
+ return "Testing-NonCyclic-Hash";
+ }
+
+ @Override
+ public ProcessType getProcessType() {
+ return ProcessType.ITERATIVE;
+ }
+
+ @Override
+ public String getProvider() {
+ return "Apache Commons Collection Testing";
+ }
+
+ @Override
+ public long getSignature() {
+ return 0;
+ }
+
+ @Override
+ public Signedness getSignedness() {
+ return Signedness.SIGNED;
+ }
+ };
+
+ try {
+ new CachingHasher(hfi, new long[][] { { 1, 4 }, { 3, 6 } });
+ fail("Should have thrown exception");
+ } catch (IllegalArgumentException expected) {
+ // do nothing.
+ }
+
+ }
+
+ @Test
+ public void testGetBuffers() {
+ final CachingHasher hasher = builder.with("Hello").build();
+
+ List<long[]> buffers = hasher.getBuffers();
+ HashFunctionIdentity id = hasher.getHashFunctionIdentity();
+
+ CachingHasher hasher2 = new CachingHasher( id, buffers );
+
+ PrimitiveIterator.OfInt iter1 = hasher.getBits(shape);
+ PrimitiveIterator.OfInt iter2 = hasher2.getBits(shape);
+
+ while (iter1.hasNext())
+ {
+ assertTrue( "Too few values in second hasher", iter2.hasNext());
+ assertEquals( "Wrong value", iter1.next(), iter2.next() );
+ }
+ assertFalse( "Second hasher has too many values", iter2.hasNext());
+ }
+
+ @Test
+ public void testConstructorWithLongArray() {
+ final CachingHasher hasher = builder.with("Hello").build();
+
+ List<long[]> buffers = hasher.getBuffers();
+ assertEquals( 1, buffers.size() );
+
+ long[][] ary = new long[1][];
+ ary[0] = buffers.get(0);
+
+ HashFunctionIdentity id = hasher.getHashFunctionIdentity();
+
+
+ CachingHasher hasher2 = new CachingHasher( id, ary );
+
+ PrimitiveIterator.OfInt iter1 = hasher.getBits(shape);
+ PrimitiveIterator.OfInt iter2 = hasher2.getBits(shape);
+
+ while (iter1.hasNext())
+ {
Review comment:
fixed
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
[GitHub] [commons-collections] Claudenw commented on a change in pull
request #131: WIP: Added caching hasher
Posted by GitBox <gi...@apache.org>.
Claudenw commented on a change in pull request #131: WIP: Added caching hasher
URL: https://github.com/apache/commons-collections/pull/131#discussion_r381572097
##########
File path: src/main/java/org/apache/commons/collections4/bloomfilter/hasher/CachingHasher.java
##########
@@ -0,0 +1,227 @@
+/*
+ * 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.hasher;
+
+import java.nio.charset.StandardCharsets;
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.List;
+import java.util.NoSuchElementException;
+import java.util.PrimitiveIterator;
+
+import org.apache.commons.collections4.bloomfilter.hasher.HashFunction;
+import org.apache.commons.collections4.bloomfilter.hasher.HashFunctionIdentity;
+import org.apache.commons.collections4.bloomfilter.hasher.Hasher;
+import org.apache.commons.collections4.bloomfilter.hasher.Shape;
+import org.apache.commons.collections4.bloomfilter.hasher.HashFunctionIdentity.ProcessType;
+
+/**
+ * An implementation of Hasher that attempts to leak as little data as possible.
+ * Each item in the hasher is represented by two (2) longs. So this Hasher will
+ * still indicate how many items are in the hasher but will not leak the buffers
+ * that are being hashed as the @code DynamicHasher} does.
+ * <p>
+ * This hasher only accepts HashFunctions that are cyclic in nature.
+ * </p>
+ * @see DynamicHasher
+ * @see ProcessType
+ */
+public class CachingHasher implements Hasher {
+
+ /**
+ * The list of byte arrays that are to be hashed.
+ */
+ private final List<long[]> buffers;
+
+ /**
+ * The hash function identity
+ */
+ private final HashFunctionIdentity functionIdentity;
+
+ /**
+ * Constructs a CachingHasher from a list of arrays of hash values.
+ * <p>
+ * The list of hash values comprises a @code{List<long[]>} where each @code{long[]}
+ * is comprises two (2) values that are the result of hashing the original buffer. Thus a
+ * CachingHasher that was built from five (5) buffers will have five arrays of two @code{longs} each.
+ *
+ * @param functionIdentity The identity of the function.
+ * @param buffers a list of @code{long} arrays comprising two (2) values.
+ * @throws IllegalArgumentException if the name does not indicate a cyclic
+ * hashing function.
+ */
+ public CachingHasher(HashFunctionIdentity functionIdentity, List<long[]> buffers) {
+ this.functionIdentity = checkIdentity(functionIdentity);
+ this.buffers = new ArrayList<long[]>(buffers);
+ }
+
+ /**
+ * Constructs a CachingHasher from an array of arrys of hash values.
+ *
+ * @param functionIdentity The identity of the function.
+ * @param buffers an array of @code{long} arrays comprising two (2) values.
+ * @throws IllegalArgumentException if the name does not indicate a cyclic
+ * hashing function.
+ */
+ public CachingHasher(HashFunctionIdentity functionIdentity, long[][] buffers) {
+ this.functionIdentity = checkIdentity(functionIdentity);
+ this.buffers = Arrays.asList(buffers);
+ }
+
+ /**
+ * Check that the name is valid for this hasher.
Review comment:
fixed.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
[GitHub] [commons-collections] Claudenw commented on a change in pull
request #131: Added caching hasher
Posted by GitBox <gi...@apache.org>.
Claudenw commented on a change in pull request #131: Added caching hasher
URL: https://github.com/apache/commons-collections/pull/131#discussion_r389242640
##########
File path: src/main/java/org/apache/commons/collections4/bloomfilter/hasher/CachingHasher.java
##########
@@ -0,0 +1,233 @@
+/*
+ * 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.hasher;
+
+import java.nio.charset.StandardCharsets;
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.List;
+import java.util.NoSuchElementException;
+import java.util.PrimitiveIterator;
+
+import org.apache.commons.collections4.bloomfilter.hasher.HashFunctionIdentity.ProcessType;
+
+/**
+ * An implementation of Hasher that attempts to leak as little data as possible.
+ * Each item in the hasher is represented by two (2) longs. So this Hasher will
+ * still indicate how many items are in the hasher but will not leak the buffers
+ * that are being hashed as the @code DynamicHasher} does.
Review comment:
fixed
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
[GitHub] [commons-collections] Claudenw commented on a change in pull
request #131: Added caching hasher
Posted by GitBox <gi...@apache.org>.
Claudenw commented on a change in pull request #131: Added caching hasher
URL: https://github.com/apache/commons-collections/pull/131#discussion_r389242956
##########
File path: src/test/java/org/apache/commons/collections4/bloomfilter/hasher/CachingHasherTest.java
##########
@@ -0,0 +1,241 @@
+/*
+ * 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.hasher;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertTrue;
+import static org.junit.Assert.fail;
+
+import java.util.List;
+import java.util.NoSuchElementException;
+import java.util.PrimitiveIterator;
+import java.util.PrimitiveIterator.OfInt;
+
+import org.apache.commons.collections4.bloomfilter.hasher.function.MD5Cyclic;
+import org.junit.Before;
+import org.junit.Test;
+
+/**
+ * Tests the {@link CachingHasher}.
+ */
+public class CachingHasherTest {
+ private CachingHasher.Builder builder;
+ private Shape shape;
+
+ private final HashFunctionIdentity testFunction = new HashFunctionIdentity() {
Review comment:
fixed
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
[GitHub] [commons-collections] aherbert commented on a change in pull
request #131: Added caching hasher
Posted by GitBox <gi...@apache.org>.
aherbert commented on a change in pull request #131: Added caching hasher
URL: https://github.com/apache/commons-collections/pull/131#discussion_r387516406
##########
File path: src/main/java/org/apache/commons/collections4/bloomfilter/hasher/CachingHasher.java
##########
@@ -0,0 +1,233 @@
+/*
+ * 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.hasher;
+
+import java.nio.charset.StandardCharsets;
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.List;
+import java.util.NoSuchElementException;
+import java.util.PrimitiveIterator;
+
+import org.apache.commons.collections4.bloomfilter.hasher.HashFunctionIdentity.ProcessType;
+
+/**
+ * An implementation of Hasher that attempts to leak as little data as possible.
+ * Each item in the hasher is represented by two (2) longs. So this Hasher will
+ * still indicate how many items are in the hasher but will not leak the buffers
+ * that are being hashed as the @code DynamicHasher} does.
+ * <p>
+ * This hasher only accepts HashFunctions that are cyclic in nature.
+ * </p>
+ * @see DynamicHasher
+ * @see ProcessType
+ */
+public class CachingHasher implements Hasher {
+
+ /**
+ * The list of byte arrays that are to be hashed.
+ */
+ private final List<long[]> buffers;
+
+ /**
+ * The hash function identity
+ */
+ private final HashFunctionIdentity functionIdentity;
+
+ /**
+ * Constructs a CachingHasher from a list of arrays of hash values.
+ * <p>
+ * The list of hash values comprises a @code{List<long[]>} where each @code{long[]}
+ * is comprises two (2) values that are the result of hashing the original buffer. Thus a
+ * CachingHasher that was built from five (5) buffers will have five arrays of two @code{longs}
+ * each.
+ * </p>
+ * @param functionIdentity The identity of the function.
+ * @param buffers a list of @code{long} arrays comprising two (2) values.
+ * @throws IllegalArgumentException if the name does not indicate a cyclic
+ * hashing function.
+ */
+ public CachingHasher(HashFunctionIdentity functionIdentity, List<long[]> buffers) {
+ this.functionIdentity = checkIdentity(functionIdentity);
+ this.buffers = new ArrayList<long[]>(buffers);
+ }
+
+ /**
+ * Constructs a CachingHasher from an array of arrys of hash values.
+ *
+ * @param functionIdentity The identity of the function.
+ * @param buffers an array of @code{long} arrays comprising two (2) values.
+ * @throws IllegalArgumentException if the name does not indicate a cyclic
+ * hashing function.
+ */
+ public CachingHasher(HashFunctionIdentity functionIdentity, long[][] buffers) {
+ this.functionIdentity = checkIdentity(functionIdentity);
+ this.buffers = Arrays.asList(buffers);
+ }
+
+ /**
+ * Checks that the name is valid for this hasher.
+ *
+ * @param functionIdentity the Function Identity to check.
+ */
+ private static HashFunctionIdentity checkIdentity(HashFunctionIdentity functionIdentity) {
+ if (functionIdentity.getProcessType() != ProcessType.CYCLIC) {
+ throw new IllegalArgumentException("Only cyclic hash functions may be used in a caching hasher");
+ }
+ return functionIdentity;
+ }
+
+ @Override
+ public HashFunctionIdentity getHashFunctionIdentity() {
+ return functionIdentity;
+ }
+
+ @Override
+ public boolean isEmpty() {
+ return buffers.isEmpty();
+ }
+
+
+ @Override
+ public PrimitiveIterator.OfInt getBits(Shape shape) {
+ HashFunctionValidator.checkAreEqual(getHashFunctionIdentity(),
+ shape.getHashFunctionIdentity());
+ return new IntIterator(shape);
+ }
+
+ /**
+ * Gets the long representations of the buffers.
+ * <p>
+ * This method returns the long representations of the buffers. This is commonly used
+ * to transmit the Hasher from one system to another.
+ * </p>
+ * @return a copy if the long buffer representation.
+ */
+ public List<long[]> getBuffers() {
+ return new ArrayList<long[]>( buffers );
+ }
+
+ /**
+ * The iterator of integers.
+ */
+ private class IntIterator implements PrimitiveIterator.OfInt {
+ private int buffer = 0;
+ private int funcCount = 0;
+ private final Shape shape;
+ private long accumulator;
+
+ /**
+ * Creates iterator with the specified shape.
+ *
+ * @param shape
+ */
+ private IntIterator(Shape shape) {
+ this.shape = shape;
+ this.accumulator = buffers.isEmpty() ? 0 : buffers.get(0)[0];
+ }
+
+ @Override
+ public boolean hasNext() {
+ if (buffers.isEmpty()) {
+ return false;
+ }
+ return buffer < buffers.size() - 1 || funcCount < shape.getNumberOfHashFunctions();
+ }
+
+ @Override
+ public int nextInt() {
+ if (hasNext()) {
+ if (funcCount >= shape.getNumberOfHashFunctions()) {
+ funcCount = 0;
+ buffer++;
+ accumulator = buffers.get(buffer)[0];
+ }
+ int result = (int) Math.floorMod(accumulator, (long) shape.getNumberOfBits());
+ funcCount++;
+ accumulator += buffers.get(buffer)[1];
+ return result;
+ }
+ throw new NoSuchElementException();
+ }
+
+ }
+
+ /**
+ * The builder for CachingHashers.
+ *
+ * @since 4.5
+ */
+ public static class Builder implements Hasher.Builder {
+ /**
+ * The list of byte[] that are to be hashed.
+ */
+ private List<byte[]> buffers;
+
+ /**
+ * The function that the resulting DynamicHasher will use.
+ */
+ private HashFunction function;
+
+ /**
+ * Constructs a CachingHashers builder.
+ *
+ * @param function the function implementation.
+ * @throws IllegalArgumentException if the function is not a cyclic implementation.
+ */
+ public Builder(HashFunction function) {
+ checkIdentity(function);
+ this.function = function;
+ this.buffers = new ArrayList<byte[]>();
+
+ }
+
+ /**
+ * Builds the hasher.
+ *
+ * @return A CachingHashers with the specified name, function and buffers.
+ */
+ @Override
+ public CachingHasher build() throws IllegalArgumentException {
+ List<long[]> cache = new ArrayList<long[]>();
+ for (byte[] buff : buffers) {
+ long[] result = new long[2];
+ result[0] = function.apply(buff, 0);
+ result[1] = function.apply(buff, 1) - result[0];
+ cache.add(result);
+ }
+ return new CachingHasher(function, cache);
+ }
+
+ @Override
+ public final Builder with(byte property) {
+ return with(new byte[] { property });
+ }
+
+ @Override
+ public final Builder with(byte[] property) {
+ buffers.add(property);
+ return this;
+ }
+
+ @Override
+ public final Builder with(String property) {
+ return with(property.getBytes(StandardCharsets.UTF_8));
+ }
+
Review comment:
Remove empty line
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
[GitHub] [commons-collections] Claudenw commented on a change in pull
request #131: Added caching hasher
Posted by GitBox <gi...@apache.org>.
Claudenw commented on a change in pull request #131: Added caching hasher
URL: https://github.com/apache/commons-collections/pull/131#discussion_r389242932
##########
File path: src/test/java/org/apache/commons/collections4/bloomfilter/hasher/CachingHasherBuilderTest.java
##########
@@ -0,0 +1,103 @@
+/*
+ * 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.hasher;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertTrue;
+
+import java.util.PrimitiveIterator.OfInt;
+
+import org.apache.commons.collections4.bloomfilter.hasher.function.MD5Cyclic;
+import org.junit.Before;
+import org.junit.Test;
+
+/**
+ * {@link CachingHasher.Builder} tests.
+ */
+public class CachingHasherBuilderTest {
+
+ private CachingHasher.Builder builder;
+ private final Shape shape = new Shape(new MD5Cyclic(), 1, Integer.MAX_VALUE, 1);
+
+ /**
+ * Tests that hashing a byte works as expected.
+ */
+ @Test
+ public void buildTest_byte() {
+ final CachingHasher hasher = builder.with((byte) 0x1).build();
+
+ final int expected = 1483089307;
+
+ final OfInt iter = hasher.getBits(shape);
+
+ assertTrue(iter.hasNext());
+ assertEquals(expected, iter.nextInt());
+ assertFalse(iter.hasNext());
+ }
+
+ /**
+ * Tests that hashing a byte array works as expected.
+ */
+ @Test
+ public void buildTest_byteArray() {
+ final CachingHasher hasher = builder.with("Hello".getBytes()).build();
+ final int expected = 1519797563;
+
+ final OfInt iter = hasher.getBits(shape);
+
+ assertTrue(iter.hasNext());
+ assertEquals(expected, iter.nextInt());
+ assertFalse(iter.hasNext());
+ }
+
+ /**
+ * Tests that an empty hasher works as expected.
+ */
+ @Test
+ public void buildTest_Empty() {
+ final CachingHasher hasher = builder.build();
+
+ final OfInt iter = hasher.getBits(shape);
+
+ assertFalse(iter.hasNext());
+ }
+
+ /**
+ * Tests that hashing a string works as expected.
+ */
+ @Test
+ public void buildTest_String() {
+ final CachingHasher hasher = builder.with("Hello").build();
+ final int expected = 1519797563;
+
+ final OfInt iter = hasher.getBits(shape);
+
+ assertTrue(iter.hasNext());
+ assertEquals(expected, iter.nextInt());
+ assertFalse(iter.hasNext());
+ }
+
+ /**
+ * Sets up the builder for testing.
+ */
+ @Before
Review comment:
fixed
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
[GitHub] [commons-collections] aherbert commented on issue #131: Added
caching hasher
Posted by GitBox <gi...@apache.org>.
aherbert commented on issue #131: Added caching hasher
URL: https://github.com/apache/commons-collections/pull/131#issuecomment-587175102
You need to update your fork of the apache repo from the current master, then branch from your forked master, do your new stuff and then PR from the recently forked branch.
Assuming you are in your forked repo and origin points to github.com/claudenw/commons-collections/
```
git checkout master
git remote add upstream git://github.com/apache/commons-collections/
git fetch upstream
git pull upstream master
git push
```
That should sync your fork with apache master. Then branch a topic and work as usual:
```
git checkout -b topic-branch-name
```
When you PR from the topic branch it should only have the few recent commits you made after diverging from master.
There are other ways to do it but keeping a fork up to date from which you branch has a lot of examples on the web.
The alternative is to clone apache's git repo and always leave it on master. You just update it by using git pull. Then you set upstream as your git fork. To do work you create a branch and set the tracking branch on your upstream:
Assuming origin points to github.com/apache/commons-collections/
```
git pull
git remote add upstream git://github.com/claudenw/commons-collections/
git checkout -b topic-branch-name
git push --set-upstream upstream topic-branch-name
```
Then all commits will go to your github fork.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
[GitHub] [commons-collections] aherbert commented on a change in pull
request #131: Added caching hasher
Posted by GitBox <gi...@apache.org>.
aherbert commented on a change in pull request #131: Added caching hasher
URL: https://github.com/apache/commons-collections/pull/131#discussion_r387513578
##########
File path: src/main/java/org/apache/commons/collections4/bloomfilter/hasher/CachingHasher.java
##########
@@ -0,0 +1,233 @@
+/*
+ * 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.hasher;
+
+import java.nio.charset.StandardCharsets;
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.List;
+import java.util.NoSuchElementException;
+import java.util.PrimitiveIterator;
+
+import org.apache.commons.collections4.bloomfilter.hasher.HashFunctionIdentity.ProcessType;
+
+/**
+ * An implementation of Hasher that attempts to leak as little data as possible.
+ * Each item in the hasher is represented by two (2) longs. So this Hasher will
+ * still indicate how many items are in the hasher but will not leak the buffers
+ * that are being hashed as the @code DynamicHasher} does.
Review comment:
Correct the {@code ...} tag
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
[GitHub] [commons-collections] Claudenw commented on a change in pull
request #131: Added caching hasher
Posted by GitBox <gi...@apache.org>.
Claudenw commented on a change in pull request #131: Added caching hasher
URL: https://github.com/apache/commons-collections/pull/131#discussion_r389242559
##########
File path: src/main/java/org/apache/commons/collections4/bloomfilter/hasher/HashFunctionValidator.java
##########
@@ -20,7 +20,7 @@
/**
* Contains validation for hash functions.
*/
-final class HashFunctionValidator {
+public final class HashFunctionValidator {
Review comment:
reversed - unintended for this pull
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
[GitHub] [commons-collections] Claudenw commented on a change in pull
request #131: Added caching hasher
Posted by GitBox <gi...@apache.org>.
Claudenw commented on a change in pull request #131: Added caching hasher
URL: https://github.com/apache/commons-collections/pull/131#discussion_r389242645
##########
File path: src/main/java/org/apache/commons/collections4/bloomfilter/hasher/CachingHasher.java
##########
@@ -0,0 +1,233 @@
+/*
+ * 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.hasher;
+
+import java.nio.charset.StandardCharsets;
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.List;
+import java.util.NoSuchElementException;
+import java.util.PrimitiveIterator;
+
+import org.apache.commons.collections4.bloomfilter.hasher.HashFunctionIdentity.ProcessType;
+
+/**
+ * An implementation of Hasher that attempts to leak as little data as possible.
+ * Each item in the hasher is represented by two (2) longs. So this Hasher will
+ * still indicate how many items are in the hasher but will not leak the buffers
+ * that are being hashed as the @code DynamicHasher} does.
+ * <p>
+ * This hasher only accepts HashFunctions that are cyclic in nature.
+ * </p>
+ * @see DynamicHasher
+ * @see ProcessType
+ */
+public class CachingHasher implements Hasher {
+
+ /**
+ * The list of byte arrays that are to be hashed.
+ */
+ private final List<long[]> buffers;
+
+ /**
+ * The hash function identity
+ */
+ private final HashFunctionIdentity functionIdentity;
+
+ /**
+ * Constructs a CachingHasher from a list of arrays of hash values.
+ * <p>
+ * The list of hash values comprises a @code{List<long[]>} where each @code{long[]}
Review comment:
fixed
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
[GitHub] [commons-collections] aherbert commented on a change in pull
request #131: Added caching hasher
Posted by GitBox <gi...@apache.org>.
aherbert commented on a change in pull request #131: Added caching hasher
URL: https://github.com/apache/commons-collections/pull/131#discussion_r387520915
##########
File path: src/test/java/org/apache/commons/collections4/bloomfilter/hasher/CachingHasherTest.java
##########
@@ -0,0 +1,241 @@
+/*
+ * 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.hasher;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertTrue;
+import static org.junit.Assert.fail;
+
+import java.util.List;
+import java.util.NoSuchElementException;
+import java.util.PrimitiveIterator;
+import java.util.PrimitiveIterator.OfInt;
+
+import org.apache.commons.collections4.bloomfilter.hasher.function.MD5Cyclic;
+import org.junit.Before;
+import org.junit.Test;
+
+/**
+ * Tests the {@link CachingHasher}.
+ */
+public class CachingHasherTest {
+ private CachingHasher.Builder builder;
+ private Shape shape;
+
+ private final HashFunctionIdentity testFunction = new HashFunctionIdentity() {
Review comment:
Cleaner to use HashFunctionIdentityImpl here.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
[GitHub] [commons-collections] aherbert commented on issue #131: Added
caching hasher
Posted by GitBox <gi...@apache.org>.
aherbert commented on issue #131: Added caching hasher
URL: https://github.com/apache/commons-collections/pull/131#issuecomment-600187614
A second way to fix this is to update the CachingHasher to generate its own HashFunctionIdentity and not use the one of the HashFunction.
This should be combined with the HashFunctionIdentity.getSignature() method being changed to call the HashFunction.apply(byte[], int) method multiple times to simulate iteration of the HashFunction as a generator. The signature for example could be the result of the XOR of the first 3 outputs from the apply method with seeds 0, 1, 2.
Thus a BloomFilter can then check an input Hasher has the same signature and this removes the requirement to test equality as a match of name, process type and signedness. The output from the hashing function is the defacto signature of the hash function.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
[GitHub] [commons-collections] Claudenw commented on a change in pull
request #131: Added caching hasher
Posted by GitBox <gi...@apache.org>.
Claudenw commented on a change in pull request #131: Added caching hasher
URL: https://github.com/apache/commons-collections/pull/131#discussion_r389242724
##########
File path: src/main/java/org/apache/commons/collections4/bloomfilter/hasher/CachingHasher.java
##########
@@ -0,0 +1,233 @@
+/*
+ * 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.hasher;
+
+import java.nio.charset.StandardCharsets;
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.List;
+import java.util.NoSuchElementException;
+import java.util.PrimitiveIterator;
+
+import org.apache.commons.collections4.bloomfilter.hasher.HashFunctionIdentity.ProcessType;
+
+/**
+ * An implementation of Hasher that attempts to leak as little data as possible.
+ * Each item in the hasher is represented by two (2) longs. So this Hasher will
+ * still indicate how many items are in the hasher but will not leak the buffers
+ * that are being hashed as the @code DynamicHasher} does.
+ * <p>
+ * This hasher only accepts HashFunctions that are cyclic in nature.
+ * </p>
+ * @see DynamicHasher
+ * @see ProcessType
+ */
+public class CachingHasher implements Hasher {
+
+ /**
+ * The list of byte arrays that are to be hashed.
+ */
+ private final List<long[]> buffers;
+
+ /**
+ * The hash function identity
+ */
+ private final HashFunctionIdentity functionIdentity;
+
+ /**
+ * Constructs a CachingHasher from a list of arrays of hash values.
+ * <p>
+ * The list of hash values comprises a @code{List<long[]>} where each @code{long[]}
+ * is comprises two (2) values that are the result of hashing the original buffer. Thus a
+ * CachingHasher that was built from five (5) buffers will have five arrays of two @code{longs}
+ * each.
+ * </p>
+ * @param functionIdentity The identity of the function.
+ * @param buffers a list of @code{long} arrays comprising two (2) values.
+ * @throws IllegalArgumentException if the name does not indicate a cyclic
+ * hashing function.
+ */
+ public CachingHasher(HashFunctionIdentity functionIdentity, List<long[]> buffers) {
+ this.functionIdentity = checkIdentity(functionIdentity);
+ this.buffers = new ArrayList<long[]>(buffers);
+ }
+
+ /**
+ * Constructs a CachingHasher from an array of arrys of hash values.
+ *
+ * @param functionIdentity The identity of the function.
+ * @param buffers an array of @code{long} arrays comprising two (2) values.
Review comment:
fixed
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
[GitHub] [commons-collections] Claudenw commented on a change in pull
request #131: Added caching hasher
Posted by GitBox <gi...@apache.org>.
Claudenw commented on a change in pull request #131: Added caching hasher
URL: https://github.com/apache/commons-collections/pull/131#discussion_r389242913
##########
File path: src/main/java/org/apache/commons/collections4/bloomfilter/hasher/CachingHasher.java
##########
@@ -0,0 +1,233 @@
+/*
+ * 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.hasher;
+
+import java.nio.charset.StandardCharsets;
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.List;
+import java.util.NoSuchElementException;
+import java.util.PrimitiveIterator;
+
+import org.apache.commons.collections4.bloomfilter.hasher.HashFunctionIdentity.ProcessType;
+
+/**
+ * An implementation of Hasher that attempts to leak as little data as possible.
+ * Each item in the hasher is represented by two (2) longs. So this Hasher will
+ * still indicate how many items are in the hasher but will not leak the buffers
+ * that are being hashed as the @code DynamicHasher} does.
+ * <p>
+ * This hasher only accepts HashFunctions that are cyclic in nature.
+ * </p>
+ * @see DynamicHasher
+ * @see ProcessType
+ */
+public class CachingHasher implements Hasher {
+
+ /**
+ * The list of byte arrays that are to be hashed.
+ */
+ private final List<long[]> buffers;
+
+ /**
+ * The hash function identity
+ */
+ private final HashFunctionIdentity functionIdentity;
+
+ /**
+ * Constructs a CachingHasher from a list of arrays of hash values.
+ * <p>
+ * The list of hash values comprises a @code{List<long[]>} where each @code{long[]}
+ * is comprises two (2) values that are the result of hashing the original buffer. Thus a
+ * CachingHasher that was built from five (5) buffers will have five arrays of two @code{longs}
+ * each.
+ * </p>
+ * @param functionIdentity The identity of the function.
+ * @param buffers a list of @code{long} arrays comprising two (2) values.
+ * @throws IllegalArgumentException if the name does not indicate a cyclic
+ * hashing function.
+ */
+ public CachingHasher(HashFunctionIdentity functionIdentity, List<long[]> buffers) {
+ this.functionIdentity = checkIdentity(functionIdentity);
+ this.buffers = new ArrayList<long[]>(buffers);
+ }
+
+ /**
+ * Constructs a CachingHasher from an array of arrys of hash values.
+ *
+ * @param functionIdentity The identity of the function.
+ * @param buffers an array of @code{long} arrays comprising two (2) values.
+ * @throws IllegalArgumentException if the name does not indicate a cyclic
+ * hashing function.
+ */
+ public CachingHasher(HashFunctionIdentity functionIdentity, long[][] buffers) {
+ this.functionIdentity = checkIdentity(functionIdentity);
+ this.buffers = Arrays.asList(buffers);
+ }
+
+ /**
+ * Checks that the name is valid for this hasher.
+ *
+ * @param functionIdentity the Function Identity to check.
+ */
+ private static HashFunctionIdentity checkIdentity(HashFunctionIdentity functionIdentity) {
+ if (functionIdentity.getProcessType() != ProcessType.CYCLIC) {
+ throw new IllegalArgumentException("Only cyclic hash functions may be used in a caching hasher");
+ }
+ return functionIdentity;
+ }
+
+ @Override
+ public HashFunctionIdentity getHashFunctionIdentity() {
+ return functionIdentity;
+ }
+
+ @Override
+ public boolean isEmpty() {
+ return buffers.isEmpty();
+ }
+
+
+ @Override
+ public PrimitiveIterator.OfInt getBits(Shape shape) {
+ HashFunctionValidator.checkAreEqual(getHashFunctionIdentity(),
+ shape.getHashFunctionIdentity());
+ return new IntIterator(shape);
+ }
+
+ /**
+ * Gets the long representations of the buffers.
+ * <p>
+ * This method returns the long representations of the buffers. This is commonly used
+ * to transmit the Hasher from one system to another.
+ * </p>
+ * @return a copy if the long buffer representation.
+ */
+ public List<long[]> getBuffers() {
+ return new ArrayList<long[]>( buffers );
+ }
+
+ /**
+ * The iterator of integers.
+ */
+ private class IntIterator implements PrimitiveIterator.OfInt {
+ private int buffer = 0;
+ private int funcCount = 0;
+ private final Shape shape;
+ private long accumulator;
+
+ /**
+ * Creates iterator with the specified shape.
+ *
+ * @param shape
+ */
+ private IntIterator(Shape shape) {
+ this.shape = shape;
+ this.accumulator = buffers.isEmpty() ? 0 : buffers.get(0)[0];
+ }
+
+ @Override
+ public boolean hasNext() {
+ if (buffers.isEmpty()) {
+ return false;
+ }
+ return buffer < buffers.size() - 1 || funcCount < shape.getNumberOfHashFunctions();
+ }
+
+ @Override
+ public int nextInt() {
+ if (hasNext()) {
+ if (funcCount >= shape.getNumberOfHashFunctions()) {
+ funcCount = 0;
+ buffer++;
+ accumulator = buffers.get(buffer)[0];
+ }
+ int result = (int) Math.floorMod(accumulator, (long) shape.getNumberOfBits());
+ funcCount++;
+ accumulator += buffers.get(buffer)[1];
+ return result;
+ }
+ throw new NoSuchElementException();
+ }
+
+ }
+
+ /**
+ * The builder for CachingHashers.
+ *
+ * @since 4.5
+ */
+ public static class Builder implements Hasher.Builder {
+ /**
+ * The list of byte[] that are to be hashed.
+ */
+ private List<byte[]> buffers;
+
+ /**
+ * The function that the resulting DynamicHasher will use.
+ */
+ private HashFunction function;
+
+ /**
+ * Constructs a CachingHashers builder.
+ *
+ * @param function the function implementation.
+ * @throws IllegalArgumentException if the function is not a cyclic implementation.
+ */
+ public Builder(HashFunction function) {
+ checkIdentity(function);
+ this.function = function;
+ this.buffers = new ArrayList<byte[]>();
+
+ }
+
+ /**
+ * Builds the hasher.
+ *
+ * @return A CachingHashers with the specified name, function and buffers.
+ */
+ @Override
+ public CachingHasher build() throws IllegalArgumentException {
+ List<long[]> cache = new ArrayList<long[]>();
+ for (byte[] buff : buffers) {
+ long[] result = new long[2];
+ result[0] = function.apply(buff, 0);
+ result[1] = function.apply(buff, 1) - result[0];
+ cache.add(result);
+ }
+ return new CachingHasher(function, cache);
+ }
+
+ @Override
+ public final Builder with(byte property) {
+ return with(new byte[] { property });
+ }
+
+ @Override
+ public final Builder with(byte[] property) {
+ buffers.add(property);
+ return this;
+ }
+
+ @Override
+ public final Builder with(String property) {
+ return with(property.getBytes(StandardCharsets.UTF_8));
+ }
+
Review comment:
fixed
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
[GitHub] [commons-collections] Claudenw commented on a change in pull
request #131: Added caching hasher
Posted by GitBox <gi...@apache.org>.
Claudenw commented on a change in pull request #131: Added caching hasher
URL: https://github.com/apache/commons-collections/pull/131#discussion_r389242973
##########
File path: src/test/java/org/apache/commons/collections4/bloomfilter/hasher/CachingHasherTest.java
##########
@@ -0,0 +1,241 @@
+/*
+ * 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.hasher;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertTrue;
+import static org.junit.Assert.fail;
+
+import java.util.List;
+import java.util.NoSuchElementException;
+import java.util.PrimitiveIterator;
+import java.util.PrimitiveIterator.OfInt;
+
+import org.apache.commons.collections4.bloomfilter.hasher.function.MD5Cyclic;
+import org.junit.Before;
+import org.junit.Test;
+
+/**
+ * Tests the {@link CachingHasher}.
+ */
+public class CachingHasherTest {
+ private CachingHasher.Builder builder;
+ private Shape shape;
+
+ private final HashFunctionIdentity testFunction = new HashFunctionIdentity() {
+
+ @Override
+ public String getName() {
+ return "Test Function";
+ }
+
+ @Override
+ public ProcessType getProcessType() {
+ return ProcessType.CYCLIC;
+ }
+
+ @Override
+ public String getProvider() {
+ return "Apache Commons Collection Tests";
+ }
+
+ @Override
+ public long getSignature() {
+ return 0;
+ }
+
+ @Override
+ public Signedness getSignedness() {
+ return Signedness.SIGNED;
+ }
+ };
+
+ /**
+ * Sets up the CachingHasher.
+ */
+ @Before
+ public void setup() {
+ builder = new CachingHasher.Builder(new MD5Cyclic());
+ shape = new Shape(new MD5Cyclic(), 3, 72, 17);
+ }
+
+ /**
+ * Tests that the expected bits are returned from hashing.
+ */
+ @Test
+ public void testGetBits() {
+
+ final int[] expected = { 6, 69, 44, 19, 10, 57, 48, 23, 70, 61, 36, 11, 2, 49, 24, 15, 62 };
+
+ final Hasher hasher = builder.with("Hello").build();
+
+ final OfInt iter = hasher.getBits(shape);
+
+ for (final int element : expected) {
+ assertTrue(iter.hasNext());
+ assertEquals(element, iter.nextInt());
+ }
+ assertFalse(iter.hasNext());
+ }
+
+ /**
+ * Tests that bits from multiple hashes are returned correctly.
+ */
+ @Test
+ public void testGetBits_MultipleHashes() {
+ final int[] expected = { 6, 69, 44, 19, 10, 57, 48, 23, 70, 61, 36, 11, 2, 49, 24, 15, 62, 1, 63, 53, 43, 17, 7,
+ 69, 59, 49, 39, 13, 3, 65, 55, 45, 35, 25 };
+
+ final Hasher hasher = builder.with("Hello").with("World").build();
+
+ final OfInt iter = hasher.getBits(shape);
+
+ for (final int element : expected) {
+ assertTrue(iter.hasNext());
+ assertEquals(element, iter.nextInt());
+ }
+ assertFalse(iter.hasNext());
+ try {
+ iter.next();
+ fail("Should have thown NoSuchElementException");
+ } catch (final NoSuchElementException ignore) {
+ // do nothing
+ }
+ }
+
+ /**
+ * Tests that retrieving bits for the wrong shape throws an exception.
+ */
+ @Test
+ public void testGetBits_WongShape() {
+
+ final Hasher hasher = builder.with("Hello").build();
+
+ try {
+ hasher.getBits(new Shape(testFunction, 3, 72, 17));
+ fail("Should have thown IllegalArgumentException");
+ } catch (final IllegalArgumentException expected) {
+ // do nothing
+ }
+ }
+
+ /**
+ * Tests if isEmpty() reports correctly and the iterator returns no values.
+ */
+ @Test
+ public void testIsEmpty() {
+ CachingHasher hasher = builder.build();
+ assertTrue(hasher.isEmpty());
+ final OfInt iter = hasher.getBits(shape);
+ assertFalse(iter.hasNext());
+ try {
+ iter.next();
+ fail("Should have thown NoSuchElementException");
+ } catch (final NoSuchElementException expected) {
+ // do nothing
+ }
+
+ assertFalse(builder.with("Hello").build().isEmpty());
+ }
+
+ @Test
+ public void testNonCyclicHashFunction() {
+ HashFunctionIdentity hfi = new HashFunctionIdentity() {
+
+ @Override
+ public String getName() {
+ return "Testing-NonCyclic-Hash";
+ }
+
+ @Override
+ public ProcessType getProcessType() {
+ return ProcessType.ITERATIVE;
+ }
+
+ @Override
+ public String getProvider() {
+ return "Apache Commons Collection Testing";
+ }
+
+ @Override
+ public long getSignature() {
+ return 0;
+ }
+
+ @Override
+ public Signedness getSignedness() {
+ return Signedness.SIGNED;
+ }
+ };
+
+ try {
+ new CachingHasher(hfi, new long[][] { { 1, 4 }, { 3, 6 } });
+ fail("Should have thrown exception");
+ } catch (IllegalArgumentException expected) {
+ // do nothing.
+ }
+
+ }
+
+ @Test
+ public void testGetBuffers() {
+ final CachingHasher hasher = builder.with("Hello").build();
+
+ List<long[]> buffers = hasher.getBuffers();
+ HashFunctionIdentity id = hasher.getHashFunctionIdentity();
+
+ CachingHasher hasher2 = new CachingHasher( id, buffers );
+
+ PrimitiveIterator.OfInt iter1 = hasher.getBits(shape);
+ PrimitiveIterator.OfInt iter2 = hasher2.getBits(shape);
+
+ while (iter1.hasNext())
Review comment:
fixed
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
[GitHub] [commons-collections] aherbert commented on a change in pull
request #131: Added caching hasher
Posted by GitBox <gi...@apache.org>.
aherbert commented on a change in pull request #131: Added caching hasher
URL: https://github.com/apache/commons-collections/pull/131#discussion_r387521241
##########
File path: src/test/java/org/apache/commons/collections4/bloomfilter/hasher/CachingHasherTest.java
##########
@@ -0,0 +1,241 @@
+/*
+ * 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.hasher;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertTrue;
+import static org.junit.Assert.fail;
+
+import java.util.List;
+import java.util.NoSuchElementException;
+import java.util.PrimitiveIterator;
+import java.util.PrimitiveIterator.OfInt;
+
+import org.apache.commons.collections4.bloomfilter.hasher.function.MD5Cyclic;
+import org.junit.Before;
+import org.junit.Test;
+
+/**
+ * Tests the {@link CachingHasher}.
+ */
+public class CachingHasherTest {
+ private CachingHasher.Builder builder;
+ private Shape shape;
+
+ private final HashFunctionIdentity testFunction = new HashFunctionIdentity() {
+
+ @Override
+ public String getName() {
+ return "Test Function";
+ }
+
+ @Override
+ public ProcessType getProcessType() {
+ return ProcessType.CYCLIC;
+ }
+
+ @Override
+ public String getProvider() {
+ return "Apache Commons Collection Tests";
+ }
+
+ @Override
+ public long getSignature() {
+ return 0;
+ }
+
+ @Override
+ public Signedness getSignedness() {
+ return Signedness.SIGNED;
+ }
+ };
+
+ /**
+ * Sets up the CachingHasher.
+ */
+ @Before
+ public void setup() {
+ builder = new CachingHasher.Builder(new MD5Cyclic());
+ shape = new Shape(new MD5Cyclic(), 3, 72, 17);
+ }
+
+ /**
+ * Tests that the expected bits are returned from hashing.
+ */
+ @Test
+ public void testGetBits() {
+
+ final int[] expected = { 6, 69, 44, 19, 10, 57, 48, 23, 70, 61, 36, 11, 2, 49, 24, 15, 62 };
+
+ final Hasher hasher = builder.with("Hello").build();
+
+ final OfInt iter = hasher.getBits(shape);
+
+ for (final int element : expected) {
+ assertTrue(iter.hasNext());
+ assertEquals(element, iter.nextInt());
+ }
+ assertFalse(iter.hasNext());
+ }
+
+ /**
+ * Tests that bits from multiple hashes are returned correctly.
+ */
+ @Test
+ public void testGetBits_MultipleHashes() {
+ final int[] expected = { 6, 69, 44, 19, 10, 57, 48, 23, 70, 61, 36, 11, 2, 49, 24, 15, 62, 1, 63, 53, 43, 17, 7,
+ 69, 59, 49, 39, 13, 3, 65, 55, 45, 35, 25 };
+
+ final Hasher hasher = builder.with("Hello").with("World").build();
+
+ final OfInt iter = hasher.getBits(shape);
+
+ for (final int element : expected) {
+ assertTrue(iter.hasNext());
+ assertEquals(element, iter.nextInt());
+ }
+ assertFalse(iter.hasNext());
+ try {
+ iter.next();
+ fail("Should have thown NoSuchElementException");
+ } catch (final NoSuchElementException ignore) {
+ // do nothing
+ }
+ }
+
+ /**
+ * Tests that retrieving bits for the wrong shape throws an exception.
+ */
+ @Test
+ public void testGetBits_WongShape() {
+
+ final Hasher hasher = builder.with("Hello").build();
+
+ try {
+ hasher.getBits(new Shape(testFunction, 3, 72, 17));
+ fail("Should have thown IllegalArgumentException");
+ } catch (final IllegalArgumentException expected) {
+ // do nothing
+ }
+ }
+
+ /**
+ * Tests if isEmpty() reports correctly and the iterator returns no values.
+ */
+ @Test
+ public void testIsEmpty() {
+ CachingHasher hasher = builder.build();
+ assertTrue(hasher.isEmpty());
+ final OfInt iter = hasher.getBits(shape);
+ assertFalse(iter.hasNext());
+ try {
+ iter.next();
+ fail("Should have thown NoSuchElementException");
+ } catch (final NoSuchElementException expected) {
+ // do nothing
+ }
+
+ assertFalse(builder.with("Hello").build().isEmpty());
+ }
+
+ @Test
+ public void testNonCyclicHashFunction() {
+ HashFunctionIdentity hfi = new HashFunctionIdentity() {
+
+ @Override
+ public String getName() {
+ return "Testing-NonCyclic-Hash";
+ }
+
+ @Override
+ public ProcessType getProcessType() {
+ return ProcessType.ITERATIVE;
+ }
+
+ @Override
+ public String getProvider() {
+ return "Apache Commons Collection Testing";
+ }
+
+ @Override
+ public long getSignature() {
+ return 0;
+ }
+
+ @Override
+ public Signedness getSignedness() {
+ return Signedness.SIGNED;
+ }
+ };
+
+ try {
+ new CachingHasher(hfi, new long[][] { { 1, 4 }, { 3, 6 } });
+ fail("Should have thrown exception");
+ } catch (IllegalArgumentException expected) {
+ // do nothing.
+ }
+
+ }
+
+ @Test
+ public void testGetBuffers() {
+ final CachingHasher hasher = builder.with("Hello").build();
+
+ List<long[]> buffers = hasher.getBuffers();
+ HashFunctionIdentity id = hasher.getHashFunctionIdentity();
+
+ CachingHasher hasher2 = new CachingHasher( id, buffers );
+
+ PrimitiveIterator.OfInt iter1 = hasher.getBits(shape);
+ PrimitiveIterator.OfInt iter2 = hasher2.getBits(shape);
+
+ while (iter1.hasNext())
Review comment:
This should have failed checkstyle. Have you based on the current master?
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
[GitHub] [commons-collections] aherbert commented on issue #131: Added
caching hasher
Posted by GitBox <gi...@apache.org>.
aherbert commented on issue #131: Added caching hasher
URL: https://github.com/apache/commons-collections/pull/131#issuecomment-600184152
This class makes a big assumption on how a CYCLIC HashFunction produces long output.
If the function does not increment the first long output from the hash function (with seed = 0) using a fixed increment to produce all the other values then this CachingHasher will create different indexes from a DynamicHasher using the same CYCLIC hash function.
For instance if the CYCLIC function creates further output using multiplications and rotations.
Consequently you can add this CachingHasher to a BloomFilter that uses the same HashFunctionIdentity but the CachingHasher output will be inconsistent with items that may have already been added with a different hasher using the same HashFunction.
Either:
- You test the cyclic hash function by calling it once to get the increment (as is currently done) and then again to test if your prediction for the next output is correct based on the assumption of a fixed increment.
- You make it clear in the javadoc that this function can output different indexes than a DynamicHasher when the cyclic function is not using a fixed increment.
This is an example where the removal of the hashing functionality from within the BloomFilter can lead to a comprised internal state due to lack of encapsulation.
If a cyclic hash function is mandated to use a fixed increment to generate subsequent hash values then this is not a problem. But it should be added to the ProcessType javadoc.
I was interpreting the ProcessType as either you use the entire byte[] representation of the object for each seeded hash (iterative) or you do not (cyclic). There is nothing in there to indicate it uses summation. It currently states:
```
Subsequent calls with a non-zero seed use the state to generate a new value.
```
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
[GitHub] [commons-collections] aherbert commented on a change in pull
request #131: Added caching hasher
Posted by GitBox <gi...@apache.org>.
aherbert commented on a change in pull request #131: Added caching hasher
URL: https://github.com/apache/commons-collections/pull/131#discussion_r387515514
##########
File path: src/main/java/org/apache/commons/collections4/bloomfilter/hasher/CachingHasher.java
##########
@@ -0,0 +1,233 @@
+/*
+ * 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.hasher;
+
+import java.nio.charset.StandardCharsets;
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.List;
+import java.util.NoSuchElementException;
+import java.util.PrimitiveIterator;
+
+import org.apache.commons.collections4.bloomfilter.hasher.HashFunctionIdentity.ProcessType;
+
+/**
+ * An implementation of Hasher that attempts to leak as little data as possible.
+ * Each item in the hasher is represented by two (2) longs. So this Hasher will
+ * still indicate how many items are in the hasher but will not leak the buffers
+ * that are being hashed as the @code DynamicHasher} does.
+ * <p>
+ * This hasher only accepts HashFunctions that are cyclic in nature.
+ * </p>
+ * @see DynamicHasher
+ * @see ProcessType
+ */
+public class CachingHasher implements Hasher {
+
+ /**
+ * The list of byte arrays that are to be hashed.
+ */
+ private final List<long[]> buffers;
+
+ /**
+ * The hash function identity
+ */
+ private final HashFunctionIdentity functionIdentity;
+
+ /**
+ * Constructs a CachingHasher from a list of arrays of hash values.
+ * <p>
+ * The list of hash values comprises a @code{List<long[]>} where each @code{long[]}
+ * is comprises two (2) values that are the result of hashing the original buffer. Thus a
+ * CachingHasher that was built from five (5) buffers will have five arrays of two @code{longs}
+ * each.
+ * </p>
+ * @param functionIdentity The identity of the function.
+ * @param buffers a list of @code{long} arrays comprising two (2) values.
+ * @throws IllegalArgumentException if the name does not indicate a cyclic
+ * hashing function.
+ */
+ public CachingHasher(HashFunctionIdentity functionIdentity, List<long[]> buffers) {
+ this.functionIdentity = checkIdentity(functionIdentity);
+ this.buffers = new ArrayList<long[]>(buffers);
+ }
+
+ /**
+ * Constructs a CachingHasher from an array of arrys of hash values.
+ *
+ * @param functionIdentity The identity of the function.
+ * @param buffers an array of @code{long} arrays comprising two (2) values.
+ * @throws IllegalArgumentException if the name does not indicate a cyclic
+ * hashing function.
+ */
+ public CachingHasher(HashFunctionIdentity functionIdentity, long[][] buffers) {
+ this.functionIdentity = checkIdentity(functionIdentity);
+ this.buffers = Arrays.asList(buffers);
+ }
+
+ /**
+ * Checks that the name is valid for this hasher.
+ *
+ * @param functionIdentity the Function Identity to check.
+ */
+ private static HashFunctionIdentity checkIdentity(HashFunctionIdentity functionIdentity) {
+ if (functionIdentity.getProcessType() != ProcessType.CYCLIC) {
+ throw new IllegalArgumentException("Only cyclic hash functions may be used in a caching hasher");
+ }
+ return functionIdentity;
+ }
+
+ @Override
+ public HashFunctionIdentity getHashFunctionIdentity() {
+ return functionIdentity;
+ }
+
+ @Override
+ public boolean isEmpty() {
+ return buffers.isEmpty();
+ }
+
+
+ @Override
+ public PrimitiveIterator.OfInt getBits(Shape shape) {
+ HashFunctionValidator.checkAreEqual(getHashFunctionIdentity(),
+ shape.getHashFunctionIdentity());
+ return new IntIterator(shape);
+ }
+
+ /**
+ * Gets the long representations of the buffers.
+ * <p>
Review comment:
A bit more doc would help here, i.e. the List<long[]> will contains zero or more entries, each entry is a non-null array of length two containing the 64-bit pair output from the cyclic hash function.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
[GitHub] [commons-collections] Claudenw commented on a change in pull
request #131: Added caching hasher
Posted by GitBox <gi...@apache.org>.
Claudenw commented on a change in pull request #131: Added caching hasher
URL: https://github.com/apache/commons-collections/pull/131#discussion_r389242733
##########
File path: src/main/java/org/apache/commons/collections4/bloomfilter/hasher/CachingHasher.java
##########
@@ -0,0 +1,233 @@
+/*
+ * 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.hasher;
+
+import java.nio.charset.StandardCharsets;
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.List;
+import java.util.NoSuchElementException;
+import java.util.PrimitiveIterator;
+
+import org.apache.commons.collections4.bloomfilter.hasher.HashFunctionIdentity.ProcessType;
+
+/**
+ * An implementation of Hasher that attempts to leak as little data as possible.
+ * Each item in the hasher is represented by two (2) longs. So this Hasher will
+ * still indicate how many items are in the hasher but will not leak the buffers
+ * that are being hashed as the @code DynamicHasher} does.
+ * <p>
+ * This hasher only accepts HashFunctions that are cyclic in nature.
+ * </p>
+ * @see DynamicHasher
+ * @see ProcessType
+ */
+public class CachingHasher implements Hasher {
+
+ /**
+ * The list of byte arrays that are to be hashed.
+ */
+ private final List<long[]> buffers;
+
+ /**
+ * The hash function identity
+ */
+ private final HashFunctionIdentity functionIdentity;
+
+ /**
+ * Constructs a CachingHasher from a list of arrays of hash values.
+ * <p>
+ * The list of hash values comprises a @code{List<long[]>} where each @code{long[]}
+ * is comprises two (2) values that are the result of hashing the original buffer. Thus a
+ * CachingHasher that was built from five (5) buffers will have five arrays of two @code{longs}
+ * each.
+ * </p>
+ * @param functionIdentity The identity of the function.
+ * @param buffers a list of @code{long} arrays comprising two (2) values.
+ * @throws IllegalArgumentException if the name does not indicate a cyclic
+ * hashing function.
+ */
+ public CachingHasher(HashFunctionIdentity functionIdentity, List<long[]> buffers) {
+ this.functionIdentity = checkIdentity(functionIdentity);
+ this.buffers = new ArrayList<long[]>(buffers);
+ }
+
+ /**
+ * Constructs a CachingHasher from an array of arrys of hash values.
+ *
+ * @param functionIdentity The identity of the function.
+ * @param buffers an array of @code{long} arrays comprising two (2) values.
+ * @throws IllegalArgumentException if the name does not indicate a cyclic
+ * hashing function.
+ */
+ public CachingHasher(HashFunctionIdentity functionIdentity, long[][] buffers) {
+ this.functionIdentity = checkIdentity(functionIdentity);
+ this.buffers = Arrays.asList(buffers);
+ }
+
+ /**
+ * Checks that the name is valid for this hasher.
+ *
+ * @param functionIdentity the Function Identity to check.
+ */
+ private static HashFunctionIdentity checkIdentity(HashFunctionIdentity functionIdentity) {
+ if (functionIdentity.getProcessType() != ProcessType.CYCLIC) {
+ throw new IllegalArgumentException("Only cyclic hash functions may be used in a caching hasher");
+ }
+ return functionIdentity;
+ }
+
+ @Override
+ public HashFunctionIdentity getHashFunctionIdentity() {
+ return functionIdentity;
+ }
+
+ @Override
+ public boolean isEmpty() {
+ return buffers.isEmpty();
+ }
+
+
+ @Override
+ public PrimitiveIterator.OfInt getBits(Shape shape) {
+ HashFunctionValidator.checkAreEqual(getHashFunctionIdentity(),
+ shape.getHashFunctionIdentity());
+ return new IntIterator(shape);
+ }
+
+ /**
+ * Gets the long representations of the buffers.
+ * <p>
Review comment:
fixed
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
[GitHub] [commons-collections] aherbert commented on a change in pull
request #131: Added caching hasher
Posted by GitBox <gi...@apache.org>.
aherbert commented on a change in pull request #131: Added caching hasher
URL: https://github.com/apache/commons-collections/pull/131#discussion_r387513815
##########
File path: src/main/java/org/apache/commons/collections4/bloomfilter/hasher/CachingHasher.java
##########
@@ -0,0 +1,233 @@
+/*
+ * 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.hasher;
+
+import java.nio.charset.StandardCharsets;
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.List;
+import java.util.NoSuchElementException;
+import java.util.PrimitiveIterator;
+
+import org.apache.commons.collections4.bloomfilter.hasher.HashFunctionIdentity.ProcessType;
+
+/**
+ * An implementation of Hasher that attempts to leak as little data as possible.
+ * Each item in the hasher is represented by two (2) longs. So this Hasher will
+ * still indicate how many items are in the hasher but will not leak the buffers
+ * that are being hashed as the @code DynamicHasher} does.
+ * <p>
+ * This hasher only accepts HashFunctions that are cyclic in nature.
+ * </p>
+ * @see DynamicHasher
+ * @see ProcessType
+ */
+public class CachingHasher implements Hasher {
+
+ /**
+ * The list of byte arrays that are to be hashed.
+ */
+ private final List<long[]> buffers;
+
+ /**
+ * The hash function identity
+ */
+ private final HashFunctionIdentity functionIdentity;
+
+ /**
+ * Constructs a CachingHasher from a list of arrays of hash values.
+ * <p>
+ * The list of hash values comprises a @code{List<long[]>} where each @code{long[]}
Review comment:
{@code List<long[]>} and {@code long[]}
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
[GitHub] [commons-collections] aherbert commented on a change in pull
request #131: Added caching hasher
Posted by GitBox <gi...@apache.org>.
aherbert commented on a change in pull request #131: Added caching hasher
URL: https://github.com/apache/commons-collections/pull/131#discussion_r387514135
##########
File path: src/main/java/org/apache/commons/collections4/bloomfilter/hasher/CachingHasher.java
##########
@@ -0,0 +1,233 @@
+/*
+ * 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.hasher;
+
+import java.nio.charset.StandardCharsets;
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.List;
+import java.util.NoSuchElementException;
+import java.util.PrimitiveIterator;
+
+import org.apache.commons.collections4.bloomfilter.hasher.HashFunctionIdentity.ProcessType;
+
+/**
+ * An implementation of Hasher that attempts to leak as little data as possible.
+ * Each item in the hasher is represented by two (2) longs. So this Hasher will
+ * still indicate how many items are in the hasher but will not leak the buffers
+ * that are being hashed as the @code DynamicHasher} does.
+ * <p>
+ * This hasher only accepts HashFunctions that are cyclic in nature.
+ * </p>
+ * @see DynamicHasher
+ * @see ProcessType
+ */
+public class CachingHasher implements Hasher {
+
+ /**
+ * The list of byte arrays that are to be hashed.
+ */
+ private final List<long[]> buffers;
+
+ /**
+ * The hash function identity
+ */
+ private final HashFunctionIdentity functionIdentity;
+
+ /**
+ * Constructs a CachingHasher from a list of arrays of hash values.
+ * <p>
+ * The list of hash values comprises a @code{List<long[]>} where each @code{long[]}
+ * is comprises two (2) values that are the result of hashing the original buffer. Thus a
+ * CachingHasher that was built from five (5) buffers will have five arrays of two @code{longs}
+ * each.
+ * </p>
+ * @param functionIdentity The identity of the function.
+ * @param buffers a list of @code{long} arrays comprising two (2) values.
+ * @throws IllegalArgumentException if the name does not indicate a cyclic
+ * hashing function.
+ */
+ public CachingHasher(HashFunctionIdentity functionIdentity, List<long[]> buffers) {
+ this.functionIdentity = checkIdentity(functionIdentity);
+ this.buffers = new ArrayList<long[]>(buffers);
+ }
+
+ /**
+ * Constructs a CachingHasher from an array of arrys of hash values.
+ *
+ * @param functionIdentity The identity of the function.
+ * @param buffers an array of @code{long} arrays comprising two (2) values.
Review comment:
I don't think the (2) adds anything.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
[GitHub] [commons-collections] Claudenw commented on a change in pull
request #131: Added caching hasher
Posted by GitBox <gi...@apache.org>.
Claudenw commented on a change in pull request #131: Added caching hasher
URL: https://github.com/apache/commons-collections/pull/131#discussion_r389242994
##########
File path: src/test/java/org/apache/commons/collections4/bloomfilter/hasher/CachingHasherTest.java
##########
@@ -0,0 +1,241 @@
+/*
+ * 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.hasher;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertTrue;
+import static org.junit.Assert.fail;
+
+import java.util.List;
+import java.util.NoSuchElementException;
+import java.util.PrimitiveIterator;
+import java.util.PrimitiveIterator.OfInt;
+
+import org.apache.commons.collections4.bloomfilter.hasher.function.MD5Cyclic;
+import org.junit.Before;
+import org.junit.Test;
+
+/**
+ * Tests the {@link CachingHasher}.
+ */
+public class CachingHasherTest {
+ private CachingHasher.Builder builder;
+ private Shape shape;
+
+ private final HashFunctionIdentity testFunction = new HashFunctionIdentity() {
+
+ @Override
+ public String getName() {
+ return "Test Function";
+ }
+
+ @Override
+ public ProcessType getProcessType() {
+ return ProcessType.CYCLIC;
+ }
+
+ @Override
+ public String getProvider() {
+ return "Apache Commons Collection Tests";
+ }
+
+ @Override
+ public long getSignature() {
+ return 0;
+ }
+
+ @Override
+ public Signedness getSignedness() {
+ return Signedness.SIGNED;
+ }
+ };
+
+ /**
+ * Sets up the CachingHasher.
+ */
+ @Before
+ public void setup() {
+ builder = new CachingHasher.Builder(new MD5Cyclic());
+ shape = new Shape(new MD5Cyclic(), 3, 72, 17);
+ }
+
+ /**
+ * Tests that the expected bits are returned from hashing.
+ */
+ @Test
+ public void testGetBits() {
+
+ final int[] expected = { 6, 69, 44, 19, 10, 57, 48, 23, 70, 61, 36, 11, 2, 49, 24, 15, 62 };
+
+ final Hasher hasher = builder.with("Hello").build();
+
+ final OfInt iter = hasher.getBits(shape);
+
+ for (final int element : expected) {
+ assertTrue(iter.hasNext());
+ assertEquals(element, iter.nextInt());
+ }
+ assertFalse(iter.hasNext());
+ }
+
+ /**
+ * Tests that bits from multiple hashes are returned correctly.
+ */
+ @Test
+ public void testGetBits_MultipleHashes() {
+ final int[] expected = { 6, 69, 44, 19, 10, 57, 48, 23, 70, 61, 36, 11, 2, 49, 24, 15, 62, 1, 63, 53, 43, 17, 7,
+ 69, 59, 49, 39, 13, 3, 65, 55, 45, 35, 25 };
+
+ final Hasher hasher = builder.with("Hello").with("World").build();
+
+ final OfInt iter = hasher.getBits(shape);
+
+ for (final int element : expected) {
+ assertTrue(iter.hasNext());
+ assertEquals(element, iter.nextInt());
+ }
+ assertFalse(iter.hasNext());
+ try {
+ iter.next();
+ fail("Should have thown NoSuchElementException");
+ } catch (final NoSuchElementException ignore) {
+ // do nothing
+ }
+ }
+
+ /**
+ * Tests that retrieving bits for the wrong shape throws an exception.
+ */
+ @Test
+ public void testGetBits_WongShape() {
+
Review comment:
fixed
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
[GitHub] [commons-collections] aherbert commented on a change in pull
request #131: Added caching hasher
Posted by GitBox <gi...@apache.org>.
aherbert commented on a change in pull request #131: Added caching hasher
URL: https://github.com/apache/commons-collections/pull/131#discussion_r387516238
##########
File path: src/main/java/org/apache/commons/collections4/bloomfilter/hasher/CachingHasher.java
##########
@@ -0,0 +1,233 @@
+/*
+ * 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.hasher;
+
+import java.nio.charset.StandardCharsets;
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.List;
+import java.util.NoSuchElementException;
+import java.util.PrimitiveIterator;
+
+import org.apache.commons.collections4.bloomfilter.hasher.HashFunctionIdentity.ProcessType;
+
+/**
+ * An implementation of Hasher that attempts to leak as little data as possible.
+ * Each item in the hasher is represented by two (2) longs. So this Hasher will
+ * still indicate how many items are in the hasher but will not leak the buffers
+ * that are being hashed as the @code DynamicHasher} does.
+ * <p>
+ * This hasher only accepts HashFunctions that are cyclic in nature.
+ * </p>
+ * @see DynamicHasher
+ * @see ProcessType
+ */
+public class CachingHasher implements Hasher {
+
+ /**
+ * The list of byte arrays that are to be hashed.
+ */
+ private final List<long[]> buffers;
+
+ /**
+ * The hash function identity
+ */
+ private final HashFunctionIdentity functionIdentity;
+
+ /**
+ * Constructs a CachingHasher from a list of arrays of hash values.
+ * <p>
+ * The list of hash values comprises a @code{List<long[]>} where each @code{long[]}
+ * is comprises two (2) values that are the result of hashing the original buffer. Thus a
+ * CachingHasher that was built from five (5) buffers will have five arrays of two @code{longs}
+ * each.
+ * </p>
+ * @param functionIdentity The identity of the function.
+ * @param buffers a list of @code{long} arrays comprising two (2) values.
+ * @throws IllegalArgumentException if the name does not indicate a cyclic
+ * hashing function.
+ */
+ public CachingHasher(HashFunctionIdentity functionIdentity, List<long[]> buffers) {
+ this.functionIdentity = checkIdentity(functionIdentity);
+ this.buffers = new ArrayList<long[]>(buffers);
+ }
+
+ /**
+ * Constructs a CachingHasher from an array of arrys of hash values.
+ *
+ * @param functionIdentity The identity of the function.
+ * @param buffers an array of @code{long} arrays comprising two (2) values.
+ * @throws IllegalArgumentException if the name does not indicate a cyclic
+ * hashing function.
+ */
+ public CachingHasher(HashFunctionIdentity functionIdentity, long[][] buffers) {
+ this.functionIdentity = checkIdentity(functionIdentity);
+ this.buffers = Arrays.asList(buffers);
+ }
+
+ /**
+ * Checks that the name is valid for this hasher.
+ *
+ * @param functionIdentity the Function Identity to check.
+ */
+ private static HashFunctionIdentity checkIdentity(HashFunctionIdentity functionIdentity) {
+ if (functionIdentity.getProcessType() != ProcessType.CYCLIC) {
+ throw new IllegalArgumentException("Only cyclic hash functions may be used in a caching hasher");
+ }
+ return functionIdentity;
+ }
+
+ @Override
+ public HashFunctionIdentity getHashFunctionIdentity() {
+ return functionIdentity;
+ }
+
+ @Override
+ public boolean isEmpty() {
+ return buffers.isEmpty();
+ }
+
+
+ @Override
+ public PrimitiveIterator.OfInt getBits(Shape shape) {
+ HashFunctionValidator.checkAreEqual(getHashFunctionIdentity(),
+ shape.getHashFunctionIdentity());
+ return new IntIterator(shape);
+ }
+
+ /**
+ * Gets the long representations of the buffers.
+ * <p>
+ * This method returns the long representations of the buffers. This is commonly used
+ * to transmit the Hasher from one system to another.
+ * </p>
+ * @return a copy if the long buffer representation.
+ */
+ public List<long[]> getBuffers() {
+ return new ArrayList<long[]>( buffers );
+ }
+
+ /**
+ * The iterator of integers.
+ */
+ private class IntIterator implements PrimitiveIterator.OfInt {
+ private int buffer = 0;
+ private int funcCount = 0;
+ private final Shape shape;
+ private long accumulator;
+
+ /**
+ * Creates iterator with the specified shape.
+ *
+ * @param shape
+ */
+ private IntIterator(Shape shape) {
+ this.shape = shape;
+ this.accumulator = buffers.isEmpty() ? 0 : buffers.get(0)[0];
+ }
+
+ @Override
+ public boolean hasNext() {
+ if (buffers.isEmpty()) {
+ return false;
+ }
+ return buffer < buffers.size() - 1 || funcCount < shape.getNumberOfHashFunctions();
+ }
+
+ @Override
+ public int nextInt() {
+ if (hasNext()) {
+ if (funcCount >= shape.getNumberOfHashFunctions()) {
+ funcCount = 0;
+ buffer++;
+ accumulator = buffers.get(buffer)[0];
+ }
+ int result = (int) Math.floorMod(accumulator, (long) shape.getNumberOfBits());
+ funcCount++;
+ accumulator += buffers.get(buffer)[1];
+ return result;
+ }
+ throw new NoSuchElementException();
+ }
+
+ }
+
+ /**
+ * The builder for CachingHashers.
+ *
+ * @since 4.5
+ */
+ public static class Builder implements Hasher.Builder {
+ /**
+ * The list of byte[] that are to be hashed.
+ */
+ private List<byte[]> buffers;
+
+ /**
+ * The function that the resulting DynamicHasher will use.
+ */
+ private HashFunction function;
+
+ /**
+ * Constructs a CachingHashers builder.
+ *
+ * @param function the function implementation.
+ * @throws IllegalArgumentException if the function is not a cyclic implementation.
+ */
+ public Builder(HashFunction function) {
+ checkIdentity(function);
+ this.function = function;
+ this.buffers = new ArrayList<byte[]>();
+
+ }
+
+ /**
+ * Builds the hasher.
+ *
+ * @return A CachingHashers with the specified name, function and buffers.
+ */
+ @Override
+ public CachingHasher build() throws IllegalArgumentException {
+ List<long[]> cache = new ArrayList<long[]>();
Review comment:
use final
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
[GitHub] [commons-collections] aherbert commented on a change in pull
request #131: Added caching hasher
Posted by GitBox <gi...@apache.org>.
aherbert commented on a change in pull request #131: Added caching hasher
URL: https://github.com/apache/commons-collections/pull/131#discussion_r387516780
##########
File path: src/main/java/org/apache/commons/collections4/bloomfilter/hasher/HashFunctionIdentityImpl.java
##########
@@ -51,7 +51,8 @@ public HashFunctionIdentityImpl(final HashFunctionIdentity identity) {
* @param process the processes of the hash function.
* @param signature the signature for the hash function.
*/
- public HashFunctionIdentityImpl(final String provider, final String name, final Signedness signedness, final ProcessType process,
+ public HashFunctionIdentityImpl(final String provider, final String name, final Signedness signedness,
Review comment:
No need for the line wrap here. It is unrelated to the PR.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
[GitHub] [commons-collections] garydgregory commented on a change in pull
request #131: Added caching hasher
Posted by GitBox <gi...@apache.org>.
garydgregory commented on a change in pull request #131: Added caching hasher
URL: https://github.com/apache/commons-collections/pull/131#discussion_r380753300
##########
File path: src/main/java/org/apache/commons/collections4/bloomfilter/hasher/CachingHasher.java
##########
@@ -0,0 +1,227 @@
+/*
+ * 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.hasher;
+
+import java.nio.charset.StandardCharsets;
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.List;
+import java.util.NoSuchElementException;
+import java.util.PrimitiveIterator;
+
+import org.apache.commons.collections4.bloomfilter.hasher.HashFunction;
+import org.apache.commons.collections4.bloomfilter.hasher.HashFunctionIdentity;
+import org.apache.commons.collections4.bloomfilter.hasher.Hasher;
+import org.apache.commons.collections4.bloomfilter.hasher.Shape;
+import org.apache.commons.collections4.bloomfilter.hasher.HashFunctionIdentity.ProcessType;
+
+/**
+ * An implementation of Hasher that attempts to leak as little data as possible.
+ * Each item in the hasher is represented by two (2) longs. So this Hasher will
+ * still indicate how many items are in the hasher but will not leak the buffers
+ * that are being hashed as the @code DynamicHasher} does.
+ * <p>
+ * This hasher only accepts HashFunctions that are cyclic in nature.
+ * </p>
+ * @see DynamicHasher
+ * @see ProcessType
+ */
+public class CachingHasher implements Hasher {
+
+ /**
+ * The list of byte arrays that are to be hashed.
+ */
+ private final List<long[]> buffers;
+
+ /**
+ * The hash function identity
+ */
+ private final HashFunctionIdentity functionIdentity;
+
+ /**
+ * Constructs a CachingHasher from a list of arrays of hash values.
+ * <p>
+ * The list of hash values comprises a @code{List<long[]>} where each @code{long[]}
+ * is comprises two (2) values that are the result of hashing the original buffer. Thus a
+ * CachingHasher that was built from five (5) buffers will have five arrays of two @code{longs} each.
+ *
Review comment:
Close HTML tags.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
[GitHub] [commons-collections] Claudenw commented on issue #131: Added
caching hasher
Posted by GitBox <gi...@apache.org>.
Claudenw commented on issue #131: Added caching hasher
URL: https://github.com/apache/commons-collections/pull/131#issuecomment-587171142
I seem to have an issue with far to many commits showing up in this pull request (only the last 2 are real) can someone point me to how to get rid of the other 99?
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
[GitHub] [commons-collections] Claudenw commented on issue #131: Added
caching hasher
Posted by GitBox <gi...@apache.org>.
Claudenw commented on issue #131: Added caching hasher
URL: https://github.com/apache/commons-collections/pull/131#issuecomment-600138859
> Needs a matching unit test class ;-)
done
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
[GitHub] [commons-collections] Claudenw commented on a change in pull
request #131: Added caching hasher
Posted by GitBox <gi...@apache.org>.
Claudenw commented on a change in pull request #131: Added caching hasher
URL: https://github.com/apache/commons-collections/pull/131#discussion_r389242584
##########
File path: src/main/java/org/apache/commons/collections4/bloomfilter/hasher/HashFunctionIdentityImpl.java
##########
@@ -51,7 +51,8 @@ public HashFunctionIdentityImpl(final HashFunctionIdentity identity) {
* @param process the processes of the hash function.
* @param signature the signature for the hash function.
*/
- public HashFunctionIdentityImpl(final String provider, final String name, final Signedness signedness, final ProcessType process,
+ public HashFunctionIdentityImpl(final String provider, final String name, final Signedness signedness,
Review comment:
reversed
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
[GitHub] [commons-collections] aherbert commented on a change in pull
request #131: Added caching hasher
Posted by GitBox <gi...@apache.org>.
aherbert commented on a change in pull request #131: Added caching hasher
URL: https://github.com/apache/commons-collections/pull/131#discussion_r387518406
##########
File path: src/test/java/org/apache/commons/collections4/bloomfilter/hasher/CachingHasherBuilderTest.java
##########
@@ -0,0 +1,103 @@
+/*
+ * 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.hasher;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertTrue;
+
+import java.util.PrimitiveIterator.OfInt;
+
+import org.apache.commons.collections4.bloomfilter.hasher.function.MD5Cyclic;
+import org.junit.Before;
+import org.junit.Test;
+
+/**
+ * {@link CachingHasher.Builder} tests.
+ */
+public class CachingHasherBuilderTest {
+
+ private CachingHasher.Builder builder;
+ private final Shape shape = new Shape(new MD5Cyclic(), 1, Integer.MAX_VALUE, 1);
+
+ /**
+ * Tests that hashing a byte works as expected.
+ */
+ @Test
+ public void buildTest_byte() {
+ final CachingHasher hasher = builder.with((byte) 0x1).build();
+
+ final int expected = 1483089307;
+
+ final OfInt iter = hasher.getBits(shape);
+
+ assertTrue(iter.hasNext());
+ assertEquals(expected, iter.nextInt());
+ assertFalse(iter.hasNext());
+ }
+
+ /**
+ * Tests that hashing a byte array works as expected.
+ */
+ @Test
+ public void buildTest_byteArray() {
+ final CachingHasher hasher = builder.with("Hello".getBytes()).build();
+ final int expected = 1519797563;
+
+ final OfInt iter = hasher.getBits(shape);
+
+ assertTrue(iter.hasNext());
+ assertEquals(expected, iter.nextInt());
+ assertFalse(iter.hasNext());
+ }
+
+ /**
+ * Tests that an empty hasher works as expected.
+ */
+ @Test
+ public void buildTest_Empty() {
+ final CachingHasher hasher = builder.build();
+
+ final OfInt iter = hasher.getBits(shape);
+
+ assertFalse(iter.hasNext());
+ }
+
+ /**
+ * Tests that hashing a string works as expected.
+ */
+ @Test
+ public void buildTest_String() {
+ final CachingHasher hasher = builder.with("Hello").build();
+ final int expected = 1519797563;
+
+ final OfInt iter = hasher.getBits(shape);
+
+ assertTrue(iter.hasNext());
+ assertEquals(expected, iter.nextInt());
+ assertFalse(iter.hasNext());
+ }
+
+ /**
+ * Sets up the builder for testing.
+ */
+ @Before
Review comment:
Move this to the top of the test
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
[GitHub] [commons-collections] garydgregory commented on a change in pull
request #131: Added caching hasher
Posted by GitBox <gi...@apache.org>.
garydgregory commented on a change in pull request #131: Added caching hasher
URL: https://github.com/apache/commons-collections/pull/131#discussion_r380753495
##########
File path: src/main/java/org/apache/commons/collections4/bloomfilter/hasher/CachingHasher.java
##########
@@ -0,0 +1,227 @@
+/*
+ * 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.hasher;
+
+import java.nio.charset.StandardCharsets;
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.List;
+import java.util.NoSuchElementException;
+import java.util.PrimitiveIterator;
+
+import org.apache.commons.collections4.bloomfilter.hasher.HashFunction;
+import org.apache.commons.collections4.bloomfilter.hasher.HashFunctionIdentity;
+import org.apache.commons.collections4.bloomfilter.hasher.Hasher;
+import org.apache.commons.collections4.bloomfilter.hasher.Shape;
+import org.apache.commons.collections4.bloomfilter.hasher.HashFunctionIdentity.ProcessType;
+
+/**
+ * An implementation of Hasher that attempts to leak as little data as possible.
+ * Each item in the hasher is represented by two (2) longs. So this Hasher will
+ * still indicate how many items are in the hasher but will not leak the buffers
+ * that are being hashed as the @code DynamicHasher} does.
+ * <p>
+ * This hasher only accepts HashFunctions that are cyclic in nature.
+ * </p>
+ * @see DynamicHasher
+ * @see ProcessType
+ */
+public class CachingHasher implements Hasher {
+
+ /**
+ * The list of byte arrays that are to be hashed.
+ */
+ private final List<long[]> buffers;
+
+ /**
+ * The hash function identity
+ */
+ private final HashFunctionIdentity functionIdentity;
+
+ /**
+ * Constructs a CachingHasher from a list of arrays of hash values.
+ * <p>
+ * The list of hash values comprises a @code{List<long[]>} where each @code{long[]}
+ * is comprises two (2) values that are the result of hashing the original buffer. Thus a
+ * CachingHasher that was built from five (5) buffers will have five arrays of two @code{longs} each.
+ *
+ * @param functionIdentity The identity of the function.
+ * @param buffers a list of @code{long} arrays comprising two (2) values.
+ * @throws IllegalArgumentException if the name does not indicate a cyclic
+ * hashing function.
+ */
+ public CachingHasher(HashFunctionIdentity functionIdentity, List<long[]> buffers) {
+ this.functionIdentity = checkIdentity(functionIdentity);
+ this.buffers = new ArrayList<long[]>(buffers);
+ }
+
+ /**
+ * Constructs a CachingHasher from an array of arrys of hash values.
+ *
+ * @param functionIdentity The identity of the function.
+ * @param buffers an array of @code{long} arrays comprising two (2) values.
+ * @throws IllegalArgumentException if the name does not indicate a cyclic
+ * hashing function.
+ */
+ public CachingHasher(HashFunctionIdentity functionIdentity, long[][] buffers) {
+ this.functionIdentity = checkIdentity(functionIdentity);
+ this.buffers = Arrays.asList(buffers);
+ }
+
+ /**
+ * Check that the name is valid for this hasher.
Review comment:
"Check" -> "Checks".
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
[GitHub] [commons-collections] Claudenw commented on a change in pull
request #131: Added caching hasher
Posted by GitBox <gi...@apache.org>.
Claudenw commented on a change in pull request #131: Added caching hasher
URL: https://github.com/apache/commons-collections/pull/131#discussion_r389242943
##########
File path: src/test/java/org/apache/commons/collections4/bloomfilter/hasher/CachingHasherTest.java
##########
@@ -0,0 +1,241 @@
+/*
+ * 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.hasher;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertTrue;
+import static org.junit.Assert.fail;
+
+import java.util.List;
+import java.util.NoSuchElementException;
+import java.util.PrimitiveIterator;
+import java.util.PrimitiveIterator.OfInt;
+
+import org.apache.commons.collections4.bloomfilter.hasher.function.MD5Cyclic;
+import org.junit.Before;
+import org.junit.Test;
+
+/**
+ * Tests the {@link CachingHasher}.
+ */
+public class CachingHasherTest {
+ private CachingHasher.Builder builder;
+ private Shape shape;
+
+ private final HashFunctionIdentity testFunction = new HashFunctionIdentity() {
+
+ @Override
+ public String getName() {
+ return "Test Function";
+ }
+
+ @Override
+ public ProcessType getProcessType() {
+ return ProcessType.CYCLIC;
+ }
+
+ @Override
+ public String getProvider() {
+ return "Apache Commons Collection Tests";
+ }
+
+ @Override
+ public long getSignature() {
+ return 0;
+ }
+
+ @Override
+ public Signedness getSignedness() {
+ return Signedness.SIGNED;
+ }
+ };
+
+ /**
+ * Sets up the CachingHasher.
+ */
+ @Before
+ public void setup() {
+ builder = new CachingHasher.Builder(new MD5Cyclic());
+ shape = new Shape(new MD5Cyclic(), 3, 72, 17);
+ }
+
+ /**
+ * Tests that the expected bits are returned from hashing.
+ */
+ @Test
+ public void testGetBits() {
+
+ final int[] expected = { 6, 69, 44, 19, 10, 57, 48, 23, 70, 61, 36, 11, 2, 49, 24, 15, 62 };
+
+ final Hasher hasher = builder.with("Hello").build();
+
+ final OfInt iter = hasher.getBits(shape);
+
+ for (final int element : expected) {
+ assertTrue(iter.hasNext());
+ assertEquals(element, iter.nextInt());
+ }
+ assertFalse(iter.hasNext());
+ }
+
+ /**
+ * Tests that bits from multiple hashes are returned correctly.
+ */
+ @Test
+ public void testGetBits_MultipleHashes() {
+ final int[] expected = { 6, 69, 44, 19, 10, 57, 48, 23, 70, 61, 36, 11, 2, 49, 24, 15, 62, 1, 63, 53, 43, 17, 7,
+ 69, 59, 49, 39, 13, 3, 65, 55, 45, 35, 25 };
+
+ final Hasher hasher = builder.with("Hello").with("World").build();
+
+ final OfInt iter = hasher.getBits(shape);
+
+ for (final int element : expected) {
+ assertTrue(iter.hasNext());
+ assertEquals(element, iter.nextInt());
+ }
+ assertFalse(iter.hasNext());
+ try {
+ iter.next();
+ fail("Should have thown NoSuchElementException");
+ } catch (final NoSuchElementException ignore) {
+ // do nothing
+ }
+ }
+
+ /**
+ * Tests that retrieving bits for the wrong shape throws an exception.
+ */
+ @Test
+ public void testGetBits_WongShape() {
+
+ final Hasher hasher = builder.with("Hello").build();
+
+ try {
+ hasher.getBits(new Shape(testFunction, 3, 72, 17));
+ fail("Should have thown IllegalArgumentException");
+ } catch (final IllegalArgumentException expected) {
+ // do nothing
+ }
+ }
+
+ /**
+ * Tests if isEmpty() reports correctly and the iterator returns no values.
+ */
+ @Test
+ public void testIsEmpty() {
+ CachingHasher hasher = builder.build();
+ assertTrue(hasher.isEmpty());
+ final OfInt iter = hasher.getBits(shape);
+ assertFalse(iter.hasNext());
+ try {
+ iter.next();
+ fail("Should have thown NoSuchElementException");
+ } catch (final NoSuchElementException expected) {
+ // do nothing
+ }
+
+ assertFalse(builder.with("Hello").build().isEmpty());
+ }
+
+ @Test
+ public void testNonCyclicHashFunction() {
+ HashFunctionIdentity hfi = new HashFunctionIdentity() {
Review comment:
fixed
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services