    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.Arrays;
    020import java.util.Objects;
    021import java.util.function.IntPredicate;
    022import java.util.function.LongPredicate;
    023
    024/**
    025 * A bloom filter using an array of bit maps to track enabled bits. This is a standard
    026 * implementation and should work well for most Bloom filters.
    027 * @since 4.5
    028 */
    029public final class SimpleBloomFilter implements BloomFilter {
    030
    031    /**
    032     * The array of bit map longs that defines this Bloom filter. Will be null if the filter is empty.
    033     */
    034    private final long[] bitMap;
    035
    036    /**
    037     * The Shape of this Bloom filter.
    038     */
    039    private final Shape shape;
    040
    041    /**
    042     * The cardinality of this Bloom filter.
    043     */
    044    private int cardinality;
    045
    046    /**
    047     * Creates an empty instance.
    048     *
    049     * @param shape The shape for the filter.
    050     */
    051    public SimpleBloomFilter(final Shape shape) {
    052        Objects.requireNonNull(shape, "shape");
    053        this.shape = shape;
    054        this.bitMap = new long[BitMaps.numberOfBitMaps(shape.getNumberOfBits())];
    055        this.cardinality = 0;
    056    }
    057
    058    /**
    059     * Copy constructor for {@code copy()} use.
    060     * @param source
    061     */
    062    private SimpleBloomFilter(final SimpleBloomFilter source) {
    063        this.shape = source.shape;
    064        this.bitMap = source.bitMap.clone();
    065        this.cardinality = source.cardinality;
    066    }
    067
    068    @Override
    069    public long[] asBitMapArray() {
    070        return Arrays.copyOf(bitMap, bitMap.length);
    071    }
    072
    073    @Override
    074    public int cardinality() {
    075        // Lazy evaluation with caching
    076        int c = cardinality;
    077        if (c < 0) {
    078            cardinality = c = SetOperations.cardinality(this);
    079        }
    080        return c;
    081    }
    082
    083    @Override
    084    public int characteristics() {
    085        return 0;
    086    }
    087
    088    @Override
    089    public void clear() {
    090        Arrays.fill(bitMap, 0L);
    091        cardinality = 0;
    092    }
    093
    094    @Override
    095    public boolean contains(final IndexExtractor indexExtractor) {
    096        return indexExtractor.processIndices(idx -> BitMaps.contains(bitMap, idx));
    097    }
    098
    099    @Override
    100    public SimpleBloomFilter copy() {
    101        return new SimpleBloomFilter(this);
    102    }
    103
    104    @Override
    105    public boolean processBitMaps(final LongPredicate consumer) {
    106        Objects.requireNonNull(consumer, "consumer");
    107        for (final long l : bitMap) {
    108            if (!consumer.test(l)) {
    109                return false;
    110            }
    111        }
    112        return true;
    113    }
    114
    115    @Override
    116    public boolean processBitMapPairs(final BitMapExtractor other, final LongBiPredicate func) {
    117        final CountingLongPredicate p = new CountingLongPredicate(bitMap, func);
    118        return other.processBitMaps(p) && p.processRemaining();
    119    }
    120
    121    @Override
    122    public boolean processIndices(final IntPredicate consumer) {
    123        Objects.requireNonNull(consumer, "consumer");
    124        return IndexExtractor.fromBitMapExtractor(this).processIndices(consumer);
    125    }
    126
    127    @Override
    128    public Shape getShape() {
    129        return shape;
    130    }
    131
    132    @Override
    133    public boolean isEmpty() {
    134        return cardinality == 0 || processBitMaps(y -> y == 0);
    135    }
    136
    137    @Override
    138    public boolean merge(final BitMapExtractor bitMapExtractor) {
    139        Objects.requireNonNull(bitMapExtractor, "bitMapExtractor");
    140        try {
    141            final int[] idx = new int[1];
    142            bitMapExtractor.processBitMaps(value -> {
    143                bitMap[idx[0]++] |= value;
    144                return true;
    145            });
    146            // idx[0] will be limit+1 so decrement it
    147            idx[0]--;
    148            final int idxLimit = BitMaps.getLongIndex(shape.getNumberOfBits());
    149            if (idxLimit == idx[0]) {
    150                final long excess = bitMap[idxLimit] >> shape.getNumberOfBits();
    151                if (excess != 0) {
    152                    throw new IllegalArgumentException(
    153                            String.format("BitMapExtractor set a bit higher than the limit for the shape: %s",
    154                                    shape.getNumberOfBits()));
    155                }
    156            }
    157            cardinality = -1;
    158        } catch (final IndexOutOfBoundsException e) {
    159            throw new IllegalArgumentException(
    160                    String.format("BitMapExtractor should send at most %s maps", bitMap.length), e);
    161        }
    162        return true;
    163    }
    164
    165    @Override
    166    public boolean merge(final BloomFilter other) {
    167        Objects.requireNonNull(other, "other");
    168        if ((other.characteristics() & SPARSE) != 0) {
    169            merge((IndexExtractor) other);
    170        } else {
    171            merge((BitMapExtractor) other);
    172        }
    173        return true;
    174    }
    175
    176    @Override
    177    public boolean merge(final Hasher hasher) {
    178        Objects.requireNonNull(hasher, "hasher");
    179        return merge(hasher.indices(shape));
    180    }
    181
    182    @Override
    183    public boolean merge(final IndexExtractor indexExtractor) {
    184        Objects.requireNonNull(indexExtractor, "indexExtractor");
    185        indexExtractor.processIndices(idx -> {
    186            if (idx < 0 || idx >= shape.getNumberOfBits()) {
    187                throw new IllegalArgumentException(String.format(
    188                        "IndexExtractor should only send values in the range[0,%s)", shape.getNumberOfBits()));
    189            }
    190            BitMaps.set(bitMap, idx);
    191            return true;
    192        });
    193        cardinality = -1;
    194        return true;
    195    }
    196}