CountingBloomFilter.java
/*
* Licensed to the Apache Software Foundation (ASF) under one or more
* contributor license agreements. See the NOTICE file distributed with
* this work for additional information regarding copyright ownership.
* The ASF licenses this file to You under the Apache License, Version 2.0
* (the "License"); you may not use this file except in compliance with
* the License. You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
package org.apache.commons.collections4.bloomfilter;
import java.util.Objects;
/**
* The interface that describes a Bloom filter that associates a count with each
* bit index rather than a bit. This allows reversal of merge operations with
* remove operations.
*
* <p>A counting Bloom filter is expected to function identically to a standard
* Bloom filter that is the merge of all the Bloom filters that have been added
* to and not later subtracted from the counting Bloom filter. The functional
* state of a CountingBloomFilter at the start and end of a series of merge and
* subsequent remove operations of the same Bloom filters, irrespective of
* remove order, is expected to be the same.</p>
*
* <p>Removal of a filter that has not previously been merged results in an
* invalid state where the cells no longer represent a sum of merged Bloom
* filters. It is impossible to validate merge and remove exactly without
* explicitly storing all filters. Consequently such an operation may go
* undetected. The CountingBloomFilter maintains a state flag that is used as a
* warning that an operation was performed that resulted in invalid cells and
* thus an invalid state. For example this may occur if a cell for an index was
* set to negative following a remove operation.</p>
*
* <p>Implementations should document the expected state of the filter after an
* operation that generates invalid cells, and any potential recovery options.
* An implementation may support a reversal of the operation to restore the
* state to that prior to the operation. In the event that invalid cells are
* adjusted to a valid range then it should be documented if there has been
* irreversible information loss.</p>
*
* <p>Implementations may choose to throw an exception during an operation that
* generates invalid cells. Implementations should document the expected state
* of the filter after such an operation. For example are the cells not updated,
* partially updated or updated entirely before the exception is raised.</p>
*
* @see CellProducer
* @since 4.5
*/
public interface CountingBloomFilter extends BloomFilter, CellProducer {
// Query Operations
/**
* Adds the specified CellProducer to this Bloom filter.
*
* <p>Specifically
* all cells for the indexes identified by the {@code other} will be incremented
* by their corresponding values in the {@code other}.</p>
*
* <p>This method will return {@code true} if the filter is valid after the operation.</p>
*
* @param other the CellProducer to add.
* @return {@code true} if the addition was successful and the state is valid
* @see #isValid()
* @see #subtract(CellProducer)
*/
boolean add(CellProducer other);
/**
* Creates a new instance of the CountingBloomFilter with the same properties as the current one.
* @return a copy of this CountingBloomFilter
*/
@Override
CountingBloomFilter copy();
/**
* Returns the maximum allowable value for a cell count in this Counting filter.
* @return the maximum allowable value for a cell count in this Counting filter.
*/
int getMaxCell();
/**
* Determines the maximum number of times the BitMapProducer could have been merged into this
* counting filter.
* @param bitMapProducer the BitMapProducer to provide the indices.
* @return the maximum number of times the BitMapProducer could have been inserted.
*/
default int getMaxInsert(final BitMapProducer bitMapProducer) {
if (!contains(bitMapProducer)) {
return 0;
}
final long[] bitMaps = bitMapProducer.asBitMapArray();
final int[] max = { Integer.MAX_VALUE };
forEachCell((x, y) -> {
if ((bitMaps[BitMap.getLongIndex(x)] & BitMap.getLongBit(x)) != 0) {
max[0] = max[0] <= y ? max[0] : y;
}
return true;
});
return max[0];
}
/**
* Determines the maximum number of times the Bloom filter could have been merged
* into this counting filter.
* @param bloomFilter the Bloom filter the check for.
* @return the maximum number of times the Bloom filter could have been inserted.
*/
default int getMaxInsert(final BloomFilter bloomFilter) {
return getMaxInsert((BitMapProducer) bloomFilter);
}
/**
* Determines the maximum number of times the Cell Producer could have been add.
* @param cellProducer the producer of cells.
* @return the maximum number of times the CellProducer could have been inserted.
*/
int getMaxInsert(CellProducer cellProducer);
/**
* Determines the maximum number of times the Hasher could have been merged into this
* counting filter.
* @param hasher the Hasher to provide the indices.
* @return the maximum number of times the hasher could have been inserted.
*/
default int getMaxInsert(final Hasher hasher) {
return getMaxInsert(hasher.indices(getShape()));
}
// Modification Operations
/**
* Determines the maximum number of times the IndexProducer could have been merged
* into this counting filter.
* <p>To determine how many times an indxProducer could have been added create a CellProducer
* from the indexProducer and check that</p>
* @param idxProducer the producer to drive the count check.
* @return the maximum number of times the IndexProducer could have been inserted.
* @see #getMaxInsert(CellProducer)
*/
default int getMaxInsert(final IndexProducer idxProducer) {
return getMaxInsert(CellProducer.from(idxProducer.uniqueIndices()) );
}
/**
* Returns {@code true} if the internal state is valid.
*
* <p>This flag is a warning that an addition or
* subtraction of cells from this filter resulted in an invalid cell for one or more
* indexes. For example this may occur if a cell for an index was
* set to negative following a subtraction operation, or overflows the value specified by {@code getMaxCell()} following an
* addition operation.</p>
*
* <p>A counting Bloom filter that has an invalid state is no longer ensured to function
* identically to a standard Bloom filter instance that is the merge of all the Bloom filters
* that have been added to and not later subtracted from this counting Bloom filter.</p>
*
* <p>Note: The change to an invalid state may or may not be reversible. Implementations
* are expected to document their policy on recovery from an addition or removal operation
* that generated an invalid state.</p>
*
* @return {@code true} if the state is valid
*/
boolean isValid();
/**
* Merges the specified BitMap producer into this Bloom filter.
*
* <p>Specifically: all cells for the indexes identified by the {@code bitMapProducer} will be incremented by 1.</p>
*
* <p>This method will return {@code true} if the filter is valid after the operation.</p>
*
* @param bitMapProducer the BitMapProducer
* @return {@code true} if the removal was successful and the state is valid
* @see #isValid()
* @see #add(CellProducer)
*/
@Override
default boolean merge(final BitMapProducer bitMapProducer) {
Objects.requireNonNull(bitMapProducer, "bitMapProducer");
return merge(IndexProducer.fromBitMapProducer(bitMapProducer));
}
/**
* Merges the specified Bloom filter into this Bloom filter.
*
* <p>Specifically: all cells for the indexes identified by the {@code other} filter will be incremented by 1.</p>
*
* <p>Note: If the other filter is a counting Bloom filter the other filter's cells are ignored and it is treated as an
* IndexProducer.</p>
*
* <p>This method will return {@code true} if the filter is valid after the operation.</p>
*
* @param other the other Bloom filter
* @return {@code true} if the removal was successful and the state is valid
* @see #isValid()
* @see #add(CellProducer)
*/
@Override
default boolean merge(final BloomFilter other) {
Objects.requireNonNull(other, "other");
return merge((IndexProducer) other);
}
/**
* Merges the specified Hasher into this Bloom filter.
*
* <p>Specifically: all cells for the unique indexes identified by the {@code hasher} will be incremented by 1.</p>
*
* <p>This method will return {@code true} if the filter is valid after the operation.</p>
*
* @param hasher the hasher
* @return {@code true} if the removal was successful and the state is valid
* @see #isValid()
* @see #add(CellProducer)
*/
@Override
default boolean merge(final Hasher hasher) {
Objects.requireNonNull(hasher, "hasher");
return merge(hasher.indices(getShape()));
}
/**
* Merges the specified index producer into this Bloom filter.
*
* <p>Specifically: all unique cells for the indices identified by the {@code indexProducer} will be incremented by 1.</p>
*
* <p>This method will return {@code true} if the filter is valid after the operation.</p>
*
* <p>Note: If indices that are returned multiple times should be incremented multiple times convert the IndexProducer
* to a CellProducer and add that.</p>
*
* @param indexProducer the IndexProducer
* @return {@code true} if the removal was successful and the state is valid
* @see #isValid()
* @see #add(CellProducer)
*/
@Override
default boolean merge(final IndexProducer indexProducer) {
Objects.requireNonNull(indexProducer, "indexProducer");
try {
return add(CellProducer.from(indexProducer.uniqueIndices()));
} catch (final IndexOutOfBoundsException e) {
throw new IllegalArgumentException(
String.format("Filter only accepts values in the [0,%d) range", getShape().getNumberOfBits()), e);
}
}
/**
* Removes the specified BitMapProducer from this Bloom filter.
*
* <p>Specifically all cells for the indices produced by the {@code bitMapProducer} will be
* decremented by 1.</p>
*
* <p>This method will return {@code true} if the filter is valid after the operation.</p>
*
* @param bitMapProducer the BitMapProducer to provide the indexes
* @return {@code true} if the removal was successful and the state is valid
* @see #isValid()
* @see #subtract(CellProducer)
*/
default boolean remove(final BitMapProducer bitMapProducer) {
Objects.requireNonNull(bitMapProducer, "bitMapProducer");
return remove(IndexProducer.fromBitMapProducer(bitMapProducer));
}
/**
* Removes the specified Bloom filter from this Bloom filter.
*
* <p>Specifically: all cells for the indexes identified by the {@code other} filter will be decremented by 1.</p>
*
* <p>Note: If the other filter is a counting Bloom filter the other filter's cells are ignored and it is treated as an
* IndexProducer.</p>
*
* <p>This method will return {@code true} if the filter is valid after the operation.</p>
*
* @param other the other Bloom filter
* @return {@code true} if the removal was successful and the state is valid
* @see #isValid()
* @see #subtract(CellProducer)
*/
default boolean remove(final BloomFilter other) {
Objects.requireNonNull(other, "other");
return remove((IndexProducer) other);
}
/**
* Removes the unique values from the specified hasher from this Bloom filter.
*
* <p>Specifically all cells for the unique indices produced by the {@code hasher} will be
* decremented by 1.</p>
*
* <p>This method will return {@code true} if the filter is valid after the operation.</p>
*
* @param hasher the hasher to provide the indexes
* @return {@code true} if the removal was successful and the state is valid
* @see #isValid()
* @see #subtract(CellProducer)
*/
default boolean remove(final Hasher hasher) {
Objects.requireNonNull(hasher, "hasher");
return remove(hasher.indices(getShape()));
}
/**
* Removes the values from the specified IndexProducer from the Bloom filter from this Bloom filter.
*
* <p>Specifically all cells for the unique indices produced by the {@code hasher} will be
* decremented by 1.</p>
*
* <p>This method will return {@code true} if the filter is valid after the operation.</p>
*
* <p>Note: If indices that are returned multiple times should be decremented multiple times convert the IndexProducer
* to a CellProducer and subtract that.</p>
*
* @param indexProducer the IndexProducer to provide the indexes
* @return {@code true} if the removal was successful and the state is valid
* @see #isValid()
* @see #subtract(CellProducer)
*/
default boolean remove(final IndexProducer indexProducer) {
Objects.requireNonNull(indexProducer, "indexProducer");
try {
return subtract(CellProducer.from(indexProducer.uniqueIndices()));
} catch (final IndexOutOfBoundsException e) {
throw new IllegalArgumentException(
String.format("Filter only accepts values in the [0,%d) range", getShape().getNumberOfBits()));
}
}
/**
* Adds the specified CellProducer to this Bloom filter.
*
* <p>Specifically
* all cells for the indexes identified by the {@code other} will be decremented
* by their corresponding values in the {@code other}.</p>
*
* <p>This method will return true if the filter is valid after the operation.</p>
*
* @param other the CellProducer to subtract.
* @return {@code true} if the subtraction was successful and the state is valid
* @see #isValid()
* @see #add(CellProducer)
*/
boolean subtract(CellProducer other);
@Override
default IndexProducer uniqueIndices() {
return this;
}
}