Source code

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 *      http://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 BitMapProducer and IndexProducer.</em>
025 * </p>
026 * @see BitMapProducer
027 * @see IndexProducer
028 * @since 4.5
029 */
030public interface BloomFilter extends IndexProducer, BitMapProducer {
031
032    /**
033     * The sparse characteristic used to determine the best method for matching.
034     * <p>For `sparse` implementations
035     * the {@code forEachIndex(IntConsumer consumer)} method is more efficient. For non `sparse` implementations
036     * the {@code forEachBitMap(LongConsumer consumer)} is more efficient. Implementers should determine if it is easier
037     * for the implementation to produce indexes of bit map blocks.</p>
038     */
039    int SPARSE = 0x1;
040
041    /**
042     * Gets the cardinality (number of enabled bits) of this Bloom filter.
043     *
044     * <p>This is also known as the Hamming value or Hamming number.</p>
045     *
046     * @return the cardinality of this filter
047     */
048    int cardinality();
049
050    // Query Operations
051
052    /**
053     * Returns the characteristics of the filter.
054     * <p>
055     * Characteristics are defined as bits within the characteristics integer.
056     * @return the characteristics for this bloom filter.
057     */
058    int characteristics();
059
060    /**
061     * Resets the filter to its initial, unpopulated state.
062     */
063    void clear();
064
065    /**
066     * Returns {@code true} if this filter contains the bits specified in the bit maps produced by the
067     * bitMapProducer.
068     *
069     * @param bitMapProducer the {@code BitMapProducer} to provide the bit maps.
070     * @return {@code true} if this filter is enabled for all bits specified by the bit maps
071     */
072    default boolean contains(final BitMapProducer bitMapProducer) {
073        return forEachBitMapPair(bitMapProducer, (x, y) -> (x & y) == y);
074    }
075
076    /**
077     * Returns {@code true} if this filter contains the specified filter.
078     *
079     * <p>Specifically this
080     * returns {@code true} if this filter is enabled for all bits that are enabled in the
081     * {@code other} filter. Using the bit representations this is
082     * effectively {@code (this AND other) == other}.</p>
083     *
084     * @param other the other Bloom filter
085     * @return true if all enabled bits in the other filter are enabled in this filter.
086     */
087    default boolean contains(final BloomFilter other) {
088        Objects.requireNonNull(other, "other");
089        return (characteristics() & SPARSE) != 0 ? contains((IndexProducer) other) : contains((BitMapProducer) other);
090    }
091
092    /**
093     * Returns {@code true} if this filter contains the bits specified in the hasher.
094     *
095     * <p>Specifically this returns {@code true} if this filter is enabled for all bit indexes
096     * identified by the {@code hasher}. Using the bit map representations this is
097     * effectively {@code (this AND hasher) == hasher}.</p>
098     *
099     * @param hasher the hasher to provide the indexes
100     * @return true if this filter is enabled for all bits specified by the hasher
101     */
102    default boolean contains(final Hasher hasher) {
103        Objects.requireNonNull(hasher, "Hasher");
104        final Shape shape = getShape();
105        return contains(hasher.indices(shape));
106    }
107
108    /**
109     * Returns {@code true} if this filter contains the indices specified IndexProducer.
110     *
111     * <p>Specifically this returns {@code true} if this filter is enabled for all bit indexes
112     * identified by the {@code IndexProducer}.</p>
113     *
114     * @param indexProducer the IndexProducer to provide the indexes
115     * @return {@code true} if this filter is enabled for all bits specified by the IndexProducer
116     */
117    boolean contains(IndexProducer indexProducer);
118
119    /**
120     * Creates a new instance of the BloomFilter with the same properties as the current one.
121     * @return a copy of this BloomFilter
122     */
123    BloomFilter copy();
124
125    // update operations
126
127    /**
128     * Estimates the number of items in the intersection of this Bloom filter with the other bloom filter.
129     *
130     * <p>This method produces estimate is roughly equivalent to the number of unique Hashers that have been merged into both
131     * of the filters by rounding the value from the calculation described in the {@link Shape} class Javadoc.</p>
132     *
133     * <p><em>{@code estimateIntersection} should only be called with Bloom filters of the same Shape.  If called on Bloom
134     * filters of differing shape this method is not symmetric. If {@code other} has more bits an {@code IllegalArgumentException}
135     * may be thrown.</em></p>
136     *
137     * @param other The other Bloom filter
138     * @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.
139     * @throws IllegalArgumentException if the estimated N for the union of the filters is infinite.
140     * @see #estimateN()
141     * @see Shape
142     */
143    default int estimateIntersection(final BloomFilter other) {
144        Objects.requireNonNull(other, "other");
145        final double eThis = getShape().estimateN(cardinality());
146        final double eOther = getShape().estimateN(other.cardinality());
147        if (Double.isInfinite(eThis) && Double.isInfinite(eOther)) {
148            // if both are infinite the union is infinite and we return Integer.MAX_VALUE
149            return Integer.MAX_VALUE;
150        }
151        long estimate;
152        // if one is infinite the intersection is the other.
153        if (Double.isInfinite(eThis)) {
154            estimate = Math.round(eOther);
155        } else if (Double.isInfinite(eOther)) {
156            estimate = Math.round(eThis);
157        } else {
158            final BloomFilter union = this.copy();
159            union.merge(other);
160            final double eUnion = getShape().estimateN(union.cardinality());
161            if (Double.isInfinite(eUnion)) {
162                throw new IllegalArgumentException("The estimated N for the union of the filters is infinite");
163            }
164            // maximum estimate value using integer values is: 46144189292 thus
165            // eThis + eOther can not overflow the long value.
166            estimate = Math.round(eThis + eOther - eUnion);
167            estimate = estimate < 0 ? 0 : estimate;
168        }
169        return estimate>Integer.MAX_VALUE?Integer.MAX_VALUE:(int) estimate;
170    }
171
172    /**
173     * Estimates the number of items in the Bloom filter.
174     *
175     * <p>By default this is the rounding of the {@code Shape.estimateN(cardinality)} calculation for the
176     * shape and cardinality of this filter.</p>
177     *
178     * <p>This produces an estimate roughly equivalent to the number of Hashers that have been merged into the filter
179     * by rounding the value from the calculation described in the {@link Shape} class Javadoc.</p>
180     *
181     * <p><em>Note:</em></p>
182     * <ul>
183     * <li>if cardinality == numberOfBits, then result is Integer.MAX_VALUE.</li>
184     * <li>if cardinality &gt; numberOfBits, then an IllegalArgumentException is thrown.</li>
185     * </ul>
186     *
187     * @return an estimate of the number of items in the bloom filter.  Will return Integer.MAX_VALUE if the
188     * estimate is larger than Integer.MAX_VALUE.
189     * @throws IllegalArgumentException if the cardinality is &gt; numberOfBits as defined in Shape.
190     * @see Shape#estimateN(int)
191     * @see Shape
192     */
193    default int estimateN() {
194        final double d = getShape().estimateN(cardinality());
195        if (Double.isInfinite(d)) {
196            return Integer.MAX_VALUE;
197        }
198        if (Double.isNaN(d)) {
199            throw new IllegalArgumentException("Cardinality too large: " + cardinality());
200        }
201        final long l = Math.round(d);
202        return l > Integer.MAX_VALUE ? Integer.MAX_VALUE : (int) l;
203    }
204
205    /**
206     * Estimates the number of items in the union of this Bloom filter with the other bloom filter.
207     *
208     * <p>This produces an estimate roughly equivalent to the number of unique Hashers that have been merged into either
209     * of the filters by rounding the value from the calculation described in the {@link Shape} class Javadoc.</p>
210     *
211     * <p><em>{@code estimateUnion} should only be called with Bloom filters of the same Shape.  If called on Bloom
212     * filters of differing shape this method is not symmetric. If {@code other} has more bits an {@code IllegalArgumentException}
213     * may be thrown.</em></p>
214     *
215     * @param other The other Bloom filter
216     * @return an estimate of the number of items in the union.  Will return Integer.MAX_VALUE if the
217     * estimate is larger than Integer.MAX_VALUE.
218     * @see #estimateN()
219     * @see Shape
220     */
221    default int estimateUnion(final BloomFilter other) {
222        Objects.requireNonNull(other, "other");
223        final BloomFilter cpy = this.copy();
224        cpy.merge(other);
225        return cpy.estimateN();
226    }
227
228    /**
229     * Gets the shape that was used when the filter was built.
230     * @return The shape the filter was built with.
231     */
232    Shape getShape();
233
234    // Counting Operations
235
236    /**
237     * Determines if all the bits are off. This is equivalent to
238     * {@code cardinality() == 0}.
239     *
240     * <p>
241     * <em>Note: This method is optimised for non-sparse filters.</em> Implementers
242     * are encouraged to implement faster checks if possible.
243     * </p>
244     *
245     * @return {@code true} if no bits are enabled, {@code false} otherwise.
246     */
247    default boolean isEmpty() {
248        return forEachBitMap(y -> y == 0);
249    }
250
251    /**
252     * Determines if the bloom filter is "full".
253     *
254     * <p>Full is defined as having no unset bits.</p>
255     *
256     * @return {@code true} if the filter is full, {@code false} otherwise.
257     */
258    default boolean isFull() {
259        return cardinality() == getShape().getNumberOfBits();
260    }
261
262    /**
263     * Merges the specified hasher into this Bloom filter. Specifically all
264     * bit indexes that are identified by the {@code producer} will be enabled in this filter.
265     *
266     * <p><em>Note: This method should return {@code true} even if no additional bit indexes were
267     * enabled. A {@code false} result indicates that this filter may or may not contain all the indexes
268     * enabled in the {@code producer}.</em>  This state may occur in complex Bloom filter implementations like
269     * counting Bloom filters.</p>
270     *
271     * @param bitMapProducer The producer to merge.
272     * @return true if the merge was successful
273     * @throws IllegalArgumentException if producer sends illegal value.
274     */
275    boolean merge(BitMapProducer bitMapProducer);
276
277    /**
278     * Merges the specified Bloom filter into this Bloom filter.
279     *
280     * <p>Specifically all
281     * bit indexes that are identified by the {@code other} will be enabled in this filter.</p>
282     *
283     * <p><em>Note: This method should return {@code true} even if no additional bit indexes were
284     * enabled. A {@code false} result indicates that this filter may or may not contain
285     * the {@code other} Bloom filter.</em>  This state may occur in complex Bloom filter implementations like
286     * counting Bloom filters.</p>
287     *
288     * @param other The bloom filter to merge into this one.
289     * @return true if the merge was successful
290     */
291    default boolean merge(final BloomFilter other) {
292        return (characteristics() & SPARSE) != 0 ? merge((IndexProducer) other) : merge((BitMapProducer) other);
293    }
294
295    /**
296     * Merges the specified hasher into this Bloom filter. Specifically all
297     * bit indexes that are identified by the {@code hasher} will be enabled in this filter.
298     *
299     * <p><em>Note: This method should return {@code true} even if no additional bit indexes were
300     * enabled. A {@code false} result indicates that this filter may or may not contain
301     * the {@code hasher} values.</em>  This state may occur in complex Bloom filter implementations like
302     * counting Bloom filters.</p>
303     *
304     * @param hasher The hasher to merge.
305     * @return true if the merge was successful
306     * @throws IllegalArgumentException if hasher produces an illegal value.
307     */
308    default boolean merge(final Hasher hasher) {
309        Objects.requireNonNull(hasher, "hasher");
310        return merge(hasher.indices(getShape()));
311    }
312
313    /**
314     * Merges the specified IndexProducer into this Bloom filter. Specifically all
315     * bit indexes that are identified by the {@code producer} will be enabled in this filter.
316     *
317     * <p><em>Note: This method should return {@code true} even if no additional bit indexes were
318     * enabled. A {@code false} result indicates that this filter may or may not contain all the indexes of
319     * the {@code producer}.</em>  This state may occur in complex Bloom filter implementations like
320     * counting Bloom filters.</p>
321     *
322     * @param indexProducer The IndexProducer to merge.
323     * @return true if the merge was successful
324     * @throws IllegalArgumentException if producer sends illegal value.
325     */
326    boolean merge(IndexProducer indexProducer);
327
328    /**
329     * Most Bloom filters create unique IndexProducers.
330     */
331    @Override
332    default IndexProducer uniqueIndices() {
333        return this;
334    }
335}