Package org.apache.commons.collections4.bloomfilter

Class SparseBloomFilter

java.lang.Object

org.apache.commons.collections4.bloomfilter.SparseBloomFilter

All Implemented Interfaces:

BitMapExtractor, BloomFilter<SparseBloomFilter>, IndexExtractor

public final class SparseBloomFilter
extends java.lang.Object
implements BloomFilter<SparseBloomFilter>

A bloom filter using a TreeSet of integers to track enabled bits. This is a standard implementation and should work well for most low cardinality Bloom filters.

Since:

4.5.0-M1

Field Summary

Fields inherited from interface org.apache.commons.collections4.bloomfilter.BloomFilter

SPARSE

Constructor Summary

Constructors

Constructor	Description
SparseBloomFilter(Shape shape)	Constructs an empty BitSetBloomFilter.

Method Summary

Modifier and Type	Method	Description
long[]	asBitMapArray()	Return a copy of the BitMapExtractor data as a bit map array.
int	cardinality()	Gets the cardinality (number of enabled bits) of this Bloom filter.
int	characteristics()	Gets the characteristics of the filter.
void	clear()	Clears the filter to by resetting it to its initial, unpopulated state.
boolean	contains(BitMapExtractor bitMapExtractor)	Returns true if this filter contains the bits specified in the bit maps produced by the bitMapExtractor.
boolean	contains(IndexExtractor indexExtractor)	Returns true if this filter contains the indices specified IndexExtractor.
SparseBloomFilter	copy()	Creates a new instance of this SparseBloomFilter with the same properties as the current one.
Shape	getShape()	Gets the shape that was used when the filter was built.
boolean	isEmpty()	Determines if all the bits are off.
boolean	merge(BitMapExtractor bitMapExtractor)	Merges the specified hasher into this Bloom filter.
boolean	merge(BloomFilter<?> other)	Merges the specified Bloom filter into this Bloom filter.
boolean	merge(Hasher hasher)	Merges the specified hasher into this Bloom filter.
boolean	merge(IndexExtractor indexExtractor)	Merges the specified IndexExtractor into this Bloom filter.
boolean	processBitMaps(java.util.function.LongPredicate consumer)	Each bit map is passed to the predicate in order.
boolean	processIndices(java.util.function.IntPredicate consumer)	Each index is passed to the predicate.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface org.apache.commons.collections4.bloomfilter.BitMapExtractor

processBitMapPairs

Methods inherited from interface org.apache.commons.collections4.bloomfilter.BloomFilter

contains, contains, estimateIntersection, estimateN, estimateUnion, isFull, uniqueIndices

Methods inherited from interface org.apache.commons.collections4.bloomfilter.IndexExtractor

asIndexArray

Constructor Detail

SparseBloomFilter

public SparseBloomFilter(Shape shape)

Constructs an empty BitSetBloomFilter.

Parameters:

shape - The shape of the filter.

Method Detail

asBitMapArray

public long[] asBitMapArray()

Description copied from interface: BitMapExtractor

Return a copy of the BitMapExtractor data as a bit map array.

The default implementation of this method is slow. It is recommended that implementing classes reimplement this method.

Specified by:

asBitMapArray in interface BitMapExtractor

Returns:

An array of bit map data.

cardinality

public int cardinality()

Description copied from interface: BloomFilter

Gets the cardinality (number of enabled bits) of this Bloom filter.

This is also known as the Hamming value or Hamming number.

Specified by:

cardinality in interface BloomFilter<SparseBloomFilter>

Returns:

the cardinality of this filter

characteristics

public int characteristics()

Description copied from interface: BloomFilter

Gets the characteristics of the filter.

Characteristics are defined as bits within the characteristics integer.

Specified by:

characteristics in interface BloomFilter<SparseBloomFilter>

Returns:

the characteristics for this bloom filter.

clear

public void clear()

Description copied from interface: BloomFilter

Clears the filter to by resetting it to its initial, unpopulated state.

Specified by:

clear in interface BloomFilter<SparseBloomFilter>

contains

public boolean contains(BitMapExtractor bitMapExtractor)

Description copied from interface: BloomFilter

Returns true if this filter contains the bits specified in the bit maps produced by the bitMapExtractor.

Specified by:

contains in interface BloomFilter<SparseBloomFilter>

Parameters:

bitMapExtractor - the BitMapExtractor to provide the bit maps.

Returns:

true if this filter is enabled for all bits specified by the bit maps

contains

public boolean contains(IndexExtractor indexExtractor)

Description copied from interface: BloomFilter

Returns true if this filter contains the indices specified IndexExtractor.

Specifically this returns true if this filter is enabled for all bit indexes identified by the IndexExtractor.

Specified by:

contains in interface BloomFilter<SparseBloomFilter>

Parameters:

indexExtractor - the IndexExtractor to provide the indexes

Returns:

true if this filter is enabled for all bits specified by the IndexExtractor

copy

public SparseBloomFilter copy()

Creates a new instance of this SparseBloomFilter with the same properties as the current one.

Specified by:

copy in interface BloomFilter<SparseBloomFilter>

Returns:

a copy of this SparseBloomFilter.

getShape

public Shape getShape()

Description copied from interface: BloomFilter

Gets the shape that was used when the filter was built.

Specified by:

getShape in interface BloomFilter<SparseBloomFilter>

Returns:

The shape the filter was built with.

isEmpty

public boolean isEmpty()

Description copied from interface: BloomFilter

Determines if all the bits are off. This is equivalent to cardinality() == 0.

Note: This method is optimized for non-sparse filters. Implementers are encouraged to implement faster checks if possible.

Specified by:

isEmpty in interface BloomFilter<SparseBloomFilter>

Returns:

true if no bits are enabled, false otherwise.

merge

public boolean merge(BitMapExtractor bitMapExtractor)

Description copied from interface: BloomFilter

Merges the specified hasher into this Bloom filter. Specifically all bit indexes that are identified by the bitMapExtractor will be enabled in this filter.

Note: This method should return true even if no additional bit indexes were enabled. A false result indicates that this filter may or may not contain all the indexes enabled in the bitMapExtractor. This state may occur in complex Bloom filter implementations like counting Bloom filters.

Specified by:

merge in interface BloomFilter<SparseBloomFilter>

Parameters:

bitMapExtractor - The BitMapExtractor to merge.

Returns:

true if the merge was successful

merge

public boolean merge(BloomFilter<?> other)

Description copied from interface: BloomFilter

Merges the specified Bloom filter into this Bloom filter.

Specifically all bit indexes that are identified by the other will be enabled in this filter.

Note: This method should return true even if no additional bit indexes were enabled. A false result indicates that this filter may or may not contain the other Bloom filter. This state may occur in complex Bloom filter implementations like counting Bloom filters.

Specified by:

merge in interface BloomFilter<SparseBloomFilter>

Parameters:

other - The bloom filter to merge into this one.

Returns:

true if the merge was successful

merge

public boolean merge(Hasher hasher)

Description copied from interface: BloomFilter

Merges the specified hasher into this Bloom filter. Specifically all bit indexes that are identified by the hasher will be enabled in this filter.

Note: This method should return true even if no additional bit indexes were enabled. A false result indicates that this filter may or may not contain the hasher values. This state may occur in complex Bloom filter implementations like counting Bloom filters.

Specified by:

merge in interface BloomFilter<SparseBloomFilter>

Parameters:

hasher - The hasher to merge.

Returns:

true if the merge was successful

merge

public boolean merge(IndexExtractor indexExtractor)

Description copied from interface: BloomFilter

Merges the specified IndexExtractor into this Bloom filter. Specifically all bit indexes that are identified by the indexExtractor will be enabled in this filter.

Note: This method should return true even if no additional bit indexes were enabled. A false result indicates that this filter may or may not contain all the indexes of the indexExtractor. This state may occur in complex Bloom filter implementations like counting Bloom filters.

Specified by:

merge in interface BloomFilter<SparseBloomFilter>

Parameters:

indexExtractor - The IndexExtractor to merge.

Returns:

true if the merge was successful

processBitMaps

public boolean processBitMaps(java.util.function.LongPredicate consumer)

Description copied from interface: BitMapExtractor

Each bit map is passed to the predicate in order. The predicate is applied to each bit map value, if the predicate returns false the execution is stopped, false is returned, and no further bit maps are processed.

If the extractor is empty this method will return true.

Any exceptions thrown by the action are relayed to the caller.

Specified by:

processBitMaps in interface BitMapExtractor

Parameters:

consumer - the function to execute

Returns:

true if all bit maps returned true, false otherwise.

processIndices

public boolean processIndices(java.util.function.IntPredicate consumer)

Description copied from interface: IndexExtractor

Each index is passed to the predicate. The predicate is applied to each index value, if the predicate returns false the execution is stopped, false is returned, and no further indices are processed.

Any exceptions thrown by the action are relayed to the caller.

Indices ordering and uniqueness is not guaranteed.

Specified by:

processIndices in interface IndexExtractor

Parameters:

consumer - the action to be performed for each non-zero bit index.

Returns:

true if all indexes return true from consumer, false otherwise.