    001/*
    002 * Licensed to the Apache Software Foundation (ASF) under one or more
    003 * contributor license agreements.  See the NOTICE file distributed with
    004 * this work for additional information regarding copyright ownership.
    005 * The ASF licenses this file to You under the Apache License, Version 2.0
    006 * (the "License"); you may not use this file except in compliance with
    007 * the License.  You may obtain a copy of the License at
    008 *
    009 *      https://www.apache.org/licenses/LICENSE-2.0
    010 *
    011 * Unless required by applicable law or agreed to in writing, software
    012 * distributed under the License is distributed on an "AS IS" BASIS,
    013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    014 * See the License for the specific language governing permissions and
    015 * limitations under the License.
    016 */
    017package org.apache.commons.collections4.bloomfilter;
    018
    019import java.util.Objects;
    020
    021/**
    022 * The interface that describes a Bloom filter.
    023 * <p>
    024 * <em>See implementation notes for {@link BitMapExtractor} and {@link IndexExtractor}.</em>
    025 * </p>
    026 * <p>
    027 * The {@code merge} operations enable bit indexes one at a time and are not atomic. If an index is out of
    028 * range an {@link IllegalArgumentException} is raised, but indexes processed before the bad one may already
    029 * have been enabled. By design the filter is not rolled back: such an exception signals misuse with bad
    030 * indexes and must not be ignored. A filter that throws during a merge should be considered invalid, since
    031 * it may hold bits that do not correspond to any valid hashed value.
    032 * </p>
    033 *
    034 * @param <T> The BloomFilter type.
    035 * @see BitMapExtractor
    036 * @see IndexExtractor
    037 * @since 4.5.0-M1
    038 */
    039public interface BloomFilter<T extends BloomFilter<T>> extends IndexExtractor, BitMapExtractor {
    040
    041    /**
    042     * The sparse characteristic used to determine the best method for matching: {@value}.
    043     * <p>
    044     * For `sparse` implementations the {@code forEachIndex(IntConsumer consumer)} method is more efficient. For non `sparse` implementations the
    045     * {@code forEachBitMap(LongConsumer consumer)} is more efficient. Implementers should determine if it is easier.
    046     * </p>
    047     */
    048    int SPARSE = 0x1;
    049
    050    /**
    051     * Gets the cardinality (number of enabled bits) of this Bloom filter.
    052     *
    053     * <p>This is also known as the Hamming value or Hamming number.</p>
    054     *
    055     * @return The cardinality of this filter
    056     */
    057    int cardinality();
    058
    059    // Query Operations
    060
    061    /**
    062     * Gets the characteristics of the filter.
    063     * <p>
    064     * Characteristics are defined as bits within the characteristics integer.
    065     * </p>
    066     *
    067     * @return The characteristics for this bloom filter.
    068     */
    069    int characteristics();
    070
    071    /**
    072     * Clears the filter to by resetting it to its initial, unpopulated state.
    073     */
    074    void clear();
    075
    076    /**
    077     * Returns {@code true} if this filter contains the bits specified in the bit maps produced by the
    078     * bitMapExtractor.
    079     *
    080     * @param bitMapExtractor The {@code BitMapExtractor} to provide the bit maps.
    081     * @return {@code true} if this filter is enabled for all bits specified by the bit maps
    082     */
    083    default boolean contains(final BitMapExtractor bitMapExtractor) {
    084        return processBitMapPairs(bitMapExtractor, (x, y) -> (x & y) == y);
    085    }
    086
    087    /**
    088     * Returns {@code true} if this filter contains the specified filter.
    089     *
    090     * <p>Specifically this
    091     * returns {@code true} if this filter is enabled for all bits that are enabled in the
    092     * {@code other} filter. Using the bit representations this is
    093     * effectively {@code (this AND other) == other}.</p>
    094     *
    095     * @param other The other Bloom filter
    096     * @return true if all enabled bits in the other filter are enabled in this filter.
    097     */
    098    default boolean contains(final BloomFilter<?> other) {
    099        Objects.requireNonNull(other, "other");
    100        return (characteristics() & SPARSE) != 0 ? contains((IndexExtractor) other) : contains((BitMapExtractor) other);
    101    }
    102
    103    /**
    104     * Returns {@code true} if this filter contains the bits specified in the hasher.
    105     *
    106     * <p>Specifically this returns {@code true} if this filter is enabled for all bit indexes
    107     * identified by the {@code hasher}. Using the bit map representations this is
    108     * effectively {@code (this AND hasher) == hasher}.</p>
    109     *
    110     * @param hasher The hasher to provide the indexes
    111     * @return true if this filter is enabled for all bits specified by the hasher
    112     */
    113    default boolean contains(final Hasher hasher) {
    114        Objects.requireNonNull(hasher, "Hasher");
    115        final Shape shape = getShape();
    116        return contains(hasher.indices(shape));
    117    }
    118
    119    /**
    120     * Returns {@code true} if this filter contains the indices specified IndexExtractor.
    121     *
    122     * <p>Specifically this returns {@code true} if this filter is enabled for all bit indexes
    123     * identified by the {@code IndexExtractor}.</p>
    124     *
    125     * @param indexExtractor The IndexExtractor to provide the indexes
    126     * @return {@code true} if this filter is enabled for all bits specified by the IndexExtractor
    127     */
    128    boolean contains(IndexExtractor indexExtractor);
    129
    130    /**
    131     * Creates a new instance of this {@link BloomFilter} with the same properties as the current one.
    132     *
    133     * @return A copy of this {@link BloomFilter}.
    134     */
    135    T copy();
    136
    137    // update operations
    138
    139    /**
    140     * Estimates the number of items in the intersection of this Bloom filter with the other bloom filter.
    141     *
    142     * <p>This method produces estimate is roughly equivalent to the number of unique Hashers that have been merged into both
    143     * of the filters by rounding the value from the calculation described in the {@link Shape} class Javadoc.</p>
    144     *
    145     * <p><em>{@code estimateIntersection} should only be called with Bloom filters of the same Shape.  If called on Bloom
    146     * filters of differing shape this method is not symmetric. If {@code other} has more bits an {@code IllegalArgumentException}
    147     * may be thrown.</em></p>
    148     *
    149     * @param other The other Bloom filter
    150     * @return 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.
    151     * @throws IllegalArgumentException if the estimated N for the union of the filters is infinite.
    152     * @see #estimateN()
    153     * @see Shape
    154     */
    155    default int estimateIntersection(final BloomFilter<?> other) {
    156        Objects.requireNonNull(other, "other");
    157        final double eThis = getShape().estimateN(cardinality());
    158        final double eOther = getShape().estimateN(other.cardinality());
    159        if (Double.isInfinite(eThis) && Double.isInfinite(eOther)) {
    160            // if both are infinite the union is infinite and we return Integer.MAX_VALUE
    161            return Integer.MAX_VALUE;
    162        }
    163        long estimate;
    164        // if one is infinite the intersection is the other.
    165        if (Double.isInfinite(eThis)) {
    166            estimate = Math.round(eOther);
    167        } else if (Double.isInfinite(eOther)) {
    168            estimate = Math.round(eThis);
    169        } else {
    170            final T union = this.copy();
    171            union.merge(other);
    172            final double eUnion = getShape().estimateN(union.cardinality());
    173            if (Double.isInfinite(eUnion)) {
    174                throw new IllegalArgumentException("The estimated N for the union of the filters is infinite");
    175            }
    176            // maximum estimate value using integer values is: 46144189292 thus
    177            // eThis + eOther cannot overflow the long value.
    178            estimate = Math.round(eThis + eOther - eUnion);
    179            estimate = estimate < 0 ? 0 : estimate;
    180        }
    181        return estimate > Integer.MAX_VALUE ? Integer.MAX_VALUE : (int) estimate;
    182    }
    183
    184    /**
    185     * Estimates the number of items in the Bloom filter.
    186     *
    187     * <p>By default this is the rounding of the {@code Shape.estimateN(cardinality)} calculation for the
    188     * shape and cardinality of this filter.</p>
    189     *
    190     * <p>This produces an estimate roughly equivalent to the number of Hashers that have been merged into the filter
    191     * by rounding the value from the calculation described in the {@link Shape} class Javadoc.</p>
    192     *
    193     * <p><em>Note:</em></p>
    194     * <ul>
    195     * <li>if cardinality == numberOfBits, then result is Integer.MAX_VALUE.</li>
    196     * <li>if cardinality &gt; numberOfBits, then an IllegalArgumentException is thrown.</li>
    197     * </ul>
    198     *
    199     * @return An estimate of the number of items in the bloom filter.  Will return Integer.MAX_VALUE if the
    200     * estimate is larger than Integer.MAX_VALUE.
    201     * @throws IllegalArgumentException if the cardinality is &gt; numberOfBits as defined in Shape.
    202     * @see Shape#estimateN(int)
    203     * @see Shape
    204     */
    205    default int estimateN() {
    206        final double d = getShape().estimateN(cardinality());
    207        if (Double.isInfinite(d)) {
    208            return Integer.MAX_VALUE;
    209        }
    210        if (Double.isNaN(d)) {
    211            throw new IllegalArgumentException("Cardinality too large: " + cardinality());
    212        }
    213        final long l = Math.round(d);
    214        return l > Integer.MAX_VALUE ? Integer.MAX_VALUE : (int) l;
    215    }
    216
    217    /**
    218     * Estimates the number of items in the union of this Bloom filter with the other bloom filter.
    219     *
    220     * <p>This produces an estimate roughly equivalent to the number of unique Hashers that have been merged into either
    221     * of the filters by rounding the value from the calculation described in the {@link Shape} class Javadoc.</p>
    222     *
    223     * <p><em>{@code estimateUnion} should only be called with Bloom filters of the same Shape.  If called on Bloom
    224     * filters of differing shape this method is not symmetric. If {@code other} has more bits an {@code IllegalArgumentException}
    225     * may be thrown.</em></p>
    226     *
    227     * @param other The other Bloom filter
    228     * @return An estimate of the number of items in the union.  Will return Integer.MAX_VALUE if the
    229     * estimate is larger than Integer.MAX_VALUE.
    230     * @see #estimateN()
    231     * @see Shape
    232     */
    233    default int estimateUnion(final BloomFilter<?> other) {
    234        Objects.requireNonNull(other, "other");
    235        final T copy = this.copy();
    236        copy.merge(other);
    237        return copy.estimateN();
    238    }
    239
    240    /**
    241     * Gets the shape that was used when the filter was built.
    242     *
    243     * @return The shape the filter was built with.
    244     */
    245    Shape getShape();
    246
    247    // Counting Operations
    248
    249    /**
    250     * Determines if all the bits are off. This is equivalent to
    251     * {@code cardinality() == 0}.
    252     *
    253     * <p>
    254     * <em>Note: This method is optimized for non-sparse filters.</em> Implementers
    255     * are encouraged to implement faster checks if possible.
    256     * </p>
    257     *
    258     * @return {@code true} if no bits are enabled, {@code false} otherwise.
    259     */
    260    default boolean isEmpty() {
    261        return processBitMaps(y -> y == 0);
    262    }
    263
    264    /**
    265     * Determines if the bloom filter is "full".
    266     *
    267     * <p>Full is defined as having no unset bits.</p>
    268     *
    269     * @return {@code true} if the filter is full, {@code false} otherwise.
    270     */
    271    default boolean isFull() {
    272        return cardinality() == getShape().getNumberOfBits();
    273    }
    274
    275    /**
    276     * Merges the specified hasher into this Bloom filter. Specifically all
    277     * bit indexes that are identified by the {@code bitMapExtractor} will be enabled in this filter.
    278     *
    279     * <p><em>Note: This method should return {@code true} even if no additional bit indexes were
    280     * enabled. A {@code false} result indicates that this filter may or may not contain all the indexes
    281     * enabled in the {@code bitMapExtractor}.</em>  This state may occur in complex Bloom filter implementations like
    282     * counting Bloom filters.</p>
    283     *
    284     * @param bitMapExtractor The BitMapExtractor to merge.
    285     * @return true if the merge was successful
    286     * @throws IllegalArgumentException if bitMapExtractor sends illegal value.
    287     */
    288    boolean merge(BitMapExtractor bitMapExtractor);
    289
    290    /**
    291     * Merges the specified Bloom filter into this Bloom filter.
    292     *
    293     * <p>Specifically all
    294     * bit indexes that are identified by the {@code other} will be enabled in this filter.</p>
    295     *
    296     * <p><em>Note: This method should return {@code true} even if no additional bit indexes were
    297     * enabled. A {@code false} result indicates that this filter may or may not contain
    298     * the {@code other} Bloom filter.</em>  This state may occur in complex Bloom filter implementations like
    299     * counting Bloom filters.</p>
    300     *
    301     * @param other The bloom filter to merge into this one.
    302     * @return true if the merge was successful
    303     */
    304    default boolean merge(final BloomFilter<?> other) {
    305        return (characteristics() & SPARSE) != 0 ? merge((IndexExtractor) other) : merge((BitMapExtractor) other);
    306    }
    307
    308    /**
    309     * Merges the specified hasher into this Bloom filter. Specifically all
    310     * bit indexes that are identified by the {@code hasher} will be enabled in this filter.
    311     *
    312     * <p><em>Note: This method should return {@code true} even if no additional bit indexes were
    313     * enabled. A {@code false} result indicates that this filter may or may not contain
    314     * the {@code hasher} values.</em>  This state may occur in complex Bloom filter implementations like
    315     * counting Bloom filters.</p>
    316     *
    317     * @param hasher The hasher to merge.
    318     * @return true if the merge was successful
    319     * @throws IllegalArgumentException if hasher produces an illegal value.
    320     */
    321    default boolean merge(final Hasher hasher) {
    322        Objects.requireNonNull(hasher, "hasher");
    323        return merge(hasher.indices(getShape()));
    324    }
    325
    326    /**
    327     * Merges the specified IndexExtractor into this Bloom filter. Specifically all
    328     * bit indexes that are identified by the {@code indexExtractor} will be enabled in this filter.
    329     *
    330     * <p><em>Note: This method should return {@code true} even if no additional bit indexes were
    331     * enabled. A {@code false} result indicates that this filter may or may not contain all the indexes of
    332     * the {@code indexExtractor}.</em>  This state may occur in complex Bloom filter implementations like
    333     * counting Bloom filters.</p>
    334     *
    335     * @param indexExtractor The IndexExtractor to merge.
    336     * @return true if the merge was successful
    337     * @throws IllegalArgumentException if indexExtractor sends illegal value.
    338     */
    339    boolean merge(IndexExtractor indexExtractor);
    340
    341    /**
    342     * Most Bloom filters create unique IndexExtractors.
    343     */
    344    @Override
    345    default IndexExtractor uniqueIndices() {
    346        return this;
    347    }
    348}