Package org.apache.commons.collections4.bloomfilter

Class WrappedBloomFilter<T extends WrappedBloomFilter<T,​W>,​W extends BloomFilter<W>>

  • Type Parameters:
    T - The WrappedBloomFilter type.
    W - The wrapped BloomFilter type.
    All Implemented Interfaces:
    BitMapExtractor, BloomFilter<T>, IndexExtractor
    public abstract class WrappedBloomFilter<T extends WrappedBloomFilter<T,​W>,​W extends BloomFilter<W>>
extends java.lang.Object
implements BloomFilter<T>
    An abstract class to assist in implementing Bloom filter decorators.
    Since:
    4.5.0-M1

    • Field Summary

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

        SPARSE

    • Constructor Summary

      Constructors 
      Constructor Description
      WrappedBloomFilter​(W wrapped)
      Wraps a Bloom filter.

    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      long[] asBitMapArray()
      Return a copy of the BitMapExtractor data as a bit map array.
      int[] asIndexArray()
      Return a copy of the IndexExtractor data as an int 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​(BloomFilter<?> other)
      Returns true if this filter contains the specified filter.
      boolean contains​(Hasher hasher)
      Returns true if this filter contains the bits specified in the hasher.
      boolean contains​(IndexExtractor indexExtractor)
      Returns true if this filter contains the indices specified IndexExtractor.
      int estimateIntersection​(BloomFilter<?> other)
      Estimates the number of items in the intersection of this Bloom filter with the other bloom filter.
      int estimateN()
      Estimates the number of items in the Bloom filter.
      int estimateUnion​(BloomFilter<?> other)
      Estimates the number of items in the union of this Bloom filter with the other bloom filter.
      Shape getShape()
      Gets the shape that was used when the filter was built.
      protected W getWrapped()
      Gets the wrapped BloomFilter.
      boolean isFull()
      Determines if the bloom filter is "full".
      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 processBitMapPairs​(BitMapExtractor other, LongBiPredicate func)
      Applies the func to each bit map pair in order.
      boolean processBitMaps​(java.util.function.LongPredicate predicate)
      Each bit map is passed to the predicate in order.
      boolean processIndices​(java.util.function.IntPredicate predicate)
      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

    • Constructor Detail

      • WrappedBloomFilter

        public WrappedBloomFilter​(W wrapped)
        Wraps a Bloom filter. The wrapped filter is maintained as a reference not a copy. Changes in one will be reflected in the other.
        Parameters:
        wrapped - The Bloom 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.

      • asIndexArray

        public int[] asIndexArray()
        Description copied from interface: IndexExtractor
        Return a copy of the IndexExtractor data as an int array.

        Indices ordering and uniqueness is not guaranteed.

        The default implementation of this method creates an array and populates it. Implementations that have access to an index array should consider returning a copy of that array if possible.

        Specified by:
        asIndexArray in interface IndexExtractor
        Returns:
        An int array of the 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<T extends WrappedBloomFilter<T,​W>>
        Returns:
        the cardinality of this filter

      • 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<T extends WrappedBloomFilter<T,​W>>
        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​(BloomFilter<?> other)
        Description copied from interface: BloomFilter
        Returns true if this filter contains the specified filter.

        Specifically this returns true if this filter is enabled for all bits that are enabled in the other filter. Using the bit representations this is effectively (this AND other) == other.

        Specified by:
        contains in interface BloomFilter<T extends WrappedBloomFilter<T,​W>>
        Parameters:
        other - the other Bloom filter
        Returns:
        true if all enabled bits in the other filter are enabled in this filter.

      • contains

        public boolean contains​(Hasher hasher)
        Description copied from interface: BloomFilter
        Returns true if this filter contains the bits specified in the hasher.

        Specifically this returns true if this filter is enabled for all bit indexes identified by the hasher. Using the bit map representations this is effectively (this AND hasher) == hasher.

        Specified by:
        contains in interface BloomFilter<T extends WrappedBloomFilter<T,​W>>
        Parameters:
        hasher - the hasher to provide the indexes
        Returns:
        true if this filter is enabled for all bits specified by the hasher

      • 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<T extends WrappedBloomFilter<T,​W>>
        Parameters:
        indexExtractor - the IndexExtractor to provide the indexes
        Returns:
        true if this filter is enabled for all bits specified by the IndexExtractor

      • estimateIntersection

        public int estimateIntersection​(BloomFilter<?> other)
        Description copied from interface: BloomFilter
        Estimates the number of items in the intersection of this Bloom filter with the other bloom filter.

        This method produces estimate is roughly equivalent to the number of unique Hashers that have been merged into both of the filters by rounding the value from the calculation described in the Shape class Javadoc.

        estimateIntersection should only be called with Bloom filters of the same Shape. If called on Bloom filters of differing shape this method is not symmetric. If other has more bits an IllegalArgumentException may be thrown.

        Specified by:
        estimateIntersection in interface BloomFilter<T extends WrappedBloomFilter<T,​W>>
        Parameters:
        other - The other Bloom filter
        Returns:
        an estimate of the number of items in the intersection. If the calculated estimate is larger than Integer.MAX_VALUE then MAX_VALUE is returned.
        See Also:
        BloomFilter.estimateN(), Shape

      • estimateN

        public int estimateN()
        Description copied from interface: BloomFilter
        Estimates the number of items in the Bloom filter.

        By default this is the rounding of the Shape.estimateN(cardinality) calculation for the shape and cardinality of this filter.

        This produces an estimate roughly equivalent to the number of Hashers that have been merged into the filter by rounding the value from the calculation described in the Shape class Javadoc.

        Note:

        • if cardinality == numberOfBits, then result is Integer.MAX_VALUE.
        • if cardinality > numberOfBits, then an IllegalArgumentException is thrown.
        Specified by:
        estimateN in interface BloomFilter<T extends WrappedBloomFilter<T,​W>>
        Returns:
        an estimate of the number of items in the bloom filter. Will return Integer.MAX_VALUE if the estimate is larger than Integer.MAX_VALUE.
        See Also:
        Shape.estimateN(int), Shape

      • estimateUnion

        public int estimateUnion​(BloomFilter<?> other)
        Description copied from interface: BloomFilter
        Estimates the number of items in the union of this Bloom filter with the other bloom filter.

        This produces an estimate roughly equivalent to the number of unique Hashers that have been merged into either of the filters by rounding the value from the calculation described in the Shape class Javadoc.

        estimateUnion should only be called with Bloom filters of the same Shape. If called on Bloom filters of differing shape this method is not symmetric. If other has more bits an IllegalArgumentException may be thrown.

        Specified by:
        estimateUnion in interface BloomFilter<T extends WrappedBloomFilter<T,​W>>
        Parameters:
        other - The other Bloom filter
        Returns:
        an estimate of the number of items in the union. Will return Integer.MAX_VALUE if the estimate is larger than Integer.MAX_VALUE.
        See Also:
        BloomFilter.estimateN(), Shape

      • getWrapped

        protected W getWrapped()
        Gets the wrapped BloomFilter.
        Returns:
        the wrapped BloomFilter.

      • isFull

        public boolean isFull()
        Description copied from interface: BloomFilter
        Determines if the bloom filter is "full".

        Full is defined as having no unset bits.

        Specified by:
        isFull in interface BloomFilter<T extends WrappedBloomFilter<T,​W>>
        Returns:
        true if the filter is full, 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<T extends WrappedBloomFilter<T,​W>>
        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<T extends WrappedBloomFilter<T,​W>>
        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<T extends WrappedBloomFilter<T,​W>>
        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<T extends WrappedBloomFilter<T,​W>>
        Parameters:
        indexExtractor - The IndexExtractor to merge.
        Returns:
        true if the merge was successful

      • processBitMapPairs

        public boolean processBitMapPairs​(BitMapExtractor other,
                                  LongBiPredicate func)
        Description copied from interface: BitMapExtractor
        Applies the func to each bit map pair in order. Will apply all of the bit maps from the other BitMapExtractor to this extractor. If this extractor does not have as many bit maps it will provide 0 (zero) for all excess calls to the LongBiPredicate.

        The default implementation of this method uses asBitMapArray(). It is recommended that implementations of BitMapExtractor that have local arrays reimplement this method.

        Specified by:
        processBitMapPairs in interface BitMapExtractor
        Parameters:
        other - The other BitMapExtractor that provides the y values in the (x,y) pair.
        func - The function to apply.
        Returns:
        A LongPredicate that tests this BitMapExtractor's bitmap values in order.

      • processBitMaps

        public boolean processBitMaps​(java.util.function.LongPredicate predicate)
        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:
        predicate - the function to execute
        Returns:
        true if all bit maps returned true, false otherwise.

      • processIndices

        public boolean processIndices​(java.util.function.IntPredicate predicate)
        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:
        predicate - the action to be performed for each non-zero bit index.
        Returns:
        true if all indexes return true from consumer, false otherwise.