orestes.bloomfilter.memory

Class BloomFilterMemory<T>

java.lang.Object

orestes.bloomfilter.memory.BloomFilterMemory<T>

All Implemented Interfaces:

java.io.Serializable, java.lang.Cloneable, BloomFilter<T>

public class BloomFilterMemory<T>
extends java.lang.Object
implements BloomFilter<T>

See Also:

Serialized Form

Field Summary

Fields

Modifier and Type	Field and Description
protected java.util.BitSet	bloom

Constructor Summary

Constructors

Constructor and Description
BloomFilterMemory(FilterBuilder config)

Method Summary

Modifier and Type	Method and Description
boolean	add(byte[] element) Adds the passed value to the filter.
void	clear() Removes all elements from the filter (i.e. resets all bits to zero).
BloomFilter<T>	clone() Constructs a deep copy of the Bloom filter
FilterBuilder	config() Returns the configuration/builder of the Bloom filter.
boolean	contains(byte[] element) Tests whether an element is present in the filter (subject to the specified false positive rate).
boolean	equals(java.lang.Object o)
protected boolean	getBit(int index)
java.util.BitSet	getBitSet() Return the underyling bit vector of the Bloom filter.
boolean	intersect(BloomFilter<T> other) Performs the intersection operation on two compatible bloom filters.
boolean	isEmpty() Returns true if the Bloom filter does not contain any elements
protected void	setBit(int index, boolean to)
java.lang.String	toString()
boolean	union(BloomFilter<T> other) Performs the union operation on two compatible bloom filters.

Methods inherited from class java.lang.Object

finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Methods inherited from interface orestes.bloomfilter.BloomFilter

add, addAll, asString, compatible, contains, contains, containsAll, getBitsPerElement, getBitZeroProbability, getEstimatedFalsePositiveProbability, getEstimatedPopulation, getExpectedElements, getFalsePositiveProbability, getFalsePositiveProbability, getHashes, getSize, hash, hash, population, remove, toBytes

Field Detail

bloom

protected java.util.BitSet bloom

Constructor Detail

BloomFilterMemory

public BloomFilterMemory(FilterBuilder config)

Method Detail

config

public FilterBuilder config()

Description copied from interface: BloomFilter

Returns the configuration/builder of the Bloom filter.

Specified by:

config in interface BloomFilter<T>

Returns:

the configuration/builder of the Bloom filter.

add

public boolean add(byte[] element)

Description copied from interface: BloomFilter

Adds the passed value to the filter.

Specified by:

add in interface BloomFilter<T>

Parameters:

element - value to add

Returns:

true if the value did not previously exist in the filter. Note, that a false positive may occur, thus the value may not have already been in the filter, but it hashed to a set of bits already in the filter.

clear

public void clear()

Description copied from interface: BloomFilter

Removes all elements from the filter (i.e. resets all bits to zero).

Specified by:

clear in interface BloomFilter<T>

contains

public boolean contains(byte[] element)

Description copied from interface: BloomFilter

Tests whether an element is present in the filter (subject to the specified false positive rate).

Specified by:

contains in interface BloomFilter<T>

Returns:

true if the element is contained

getBit

protected boolean getBit(int index)

setBit

protected void setBit(int index,
                      boolean to)

getBitSet

public java.util.BitSet getBitSet()

Description copied from interface: BloomFilter

Return the underyling bit vector of the Bloom filter.

Specified by:

getBitSet in interface BloomFilter<T>

Returns:

the underyling bit vector of the Bloom filter.

union

public boolean union(BloomFilter<T> other)

Description copied from interface: BloomFilter

Performs the union operation on two compatible bloom filters. This is achieved through a bitwise OR operation on their bit vectors. This operations is lossless, i.e. no elements are lost and the bloom filter is the same that would have resulted if all elements wer directly inserted in just one bloom filter.

Specified by:

union in interface BloomFilter<T>

Parameters:

other - the other bloom filter

Returns:

true if this bloom filter could successfully be updated through the union with the provided bloom filter

intersect

public boolean intersect(BloomFilter<T> other)

Description copied from interface: BloomFilter

Performs the intersection operation on two compatible bloom filters. This is achieved through a bitwise AND operation on their bit vectors. The operations doesn't introduce any false negatives but it does raise the false positive probability. The the false positive probability in the resulting Bloom filter is at most the false-positive probability in one of the constituent bloom filters

Specified by:

intersect in interface BloomFilter<T>

Parameters:

other - the other bloom filter

Returns:

true if this bloom filter could successfully be updated through the intersection with the provided bloom filter

isEmpty

public boolean isEmpty()

Description copied from interface: BloomFilter

Returns true if the Bloom filter does not contain any elements

Specified by:

isEmpty in interface BloomFilter<T>

Returns:

true if the Bloom filter does not contain any elements

clone

public BloomFilter<T> clone()

Description copied from interface: BloomFilter

Constructs a deep copy of the Bloom filter

Specified by:

clone in interface BloomFilter<T>

Overrides:

clone in class java.lang.Object

Returns:

a cloned Bloom filter

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object

equals

public boolean equals(java.lang.Object o)

Overrides:

equals in class java.lang.Object