    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.LongPredicate;
    022
    023/**
    024 * Produces bit map longs for a Bloom filter.
    025 *
    026 * Each bit map is a little-endian long value representing a block of bits of in a filter.
    027 *
    028 * <p>The returned array will have length {@code ceil(m / 64)} where {@code m} is the
    029 * number of bits in the filter and {@code ceil} is the ceiling function.
    030 * Bits 0-63 are in the first long. A value of 1 at a bit position indicates the bit
    031 * index is enabled.
    032 * </p><p><em>
    033 * The default implementations of the {@code makePredicate()} and {@code asBitMapArray} methods
    034 * are slow and should be reimplemented in the implementing classes where possible.</em></p>
    035 *
    036 * @since 4.5
    037 */
    038@FunctionalInterface
    039public interface BitMapProducer {
    040
    041    /**
    042     * Creates a BitMapProducer from an array of Long.
    043     * @param bitMaps the bit maps to return.
    044     * @return a BitMapProducer.
    045     */
    046    static BitMapProducer fromBitMapArray(final long... bitMaps) {
    047        return new BitMapProducer() {
    048            @Override
    049            public long[] asBitMapArray() {
    050                return Arrays.copyOf(bitMaps, bitMaps.length);
    051            }
    052
    053            @Override
    054            public boolean forEachBitMap(final LongPredicate predicate) {
    055                for (final long word : bitMaps) {
    056                    if (!predicate.test(word)) {
    057                        return false;
    058                    }
    059                }
    060                return true;
    061            }
    062
    063            @Override
    064            public boolean forEachBitMapPair(final BitMapProducer other, final LongBiPredicate func) {
    065                final CountingLongPredicate p = new CountingLongPredicate(bitMaps, func);
    066                return other.forEachBitMap(p) && p.forEachRemaining();
    067            }
    068        };
    069    }
    070
    071    /**
    072     * Creates a BitMapProducer from an IndexProducer.
    073     * @param producer the IndexProducer that specifies the indexes of the bits to enable.
    074     * @param numberOfBits the number of bits in the Bloom filter.
    075     * @return A BitMapProducer that produces the bit maps equivalent of the Indices from the producer.
    076     */
    077    static BitMapProducer fromIndexProducer(final IndexProducer producer, final int numberOfBits) {
    078        Objects.requireNonNull(producer, "producer");
    079        Objects.requireNonNull(numberOfBits, "numberOfBits");
    080
    081        final long[] result = new long[BitMap.numberOfBitMaps(numberOfBits)];
    082        producer.forEachIndex(i -> {
    083            BitMap.set(result, i);
    084            return true;
    085        });
    086        return fromBitMapArray(result);
    087    }
    088
    089    /**
    090     * Return a copy of the BitMapProducer data as a bit map array.
    091     * <p>
    092     * The default implementation of this method is slow. It is recommended
    093     * that implementing classes reimplement this method.
    094     * </p>
    095     * @return An array of bit map data.
    096     */
    097    default long[] asBitMapArray() {
    098        class Bits {
    099            private long[] data = new long[16];
    100            private int size;
    101
    102            boolean add(final long bits) {
    103                if (size == data.length) {
    104                    // This will throw an out-of-memory error if there are too many bits.
    105                    // Since bits are addressed using 32-bit signed integer indices
    106                    // the maximum length should be ~2^31 / 2^6 = ~2^25.
    107                    // Any more is a broken implementation.
    108                    data = Arrays.copyOf(data, size * 2);
    109                }
    110                data[size++] = bits;
    111                return true;
    112            }
    113
    114            long[] toArray() {
    115                // Edge case to avoid a large array copy
    116                return size == data.length ? data : Arrays.copyOf(data, size);
    117            }
    118        }
    119        final Bits bits = new Bits();
    120        forEachBitMap(bits::add);
    121        return bits.toArray();
    122    }
    123
    124    /**
    125     * Each bit map is passed to the predicate in order. The predicate is applied to each
    126     * bit map value, if the predicate returns {@code false} the execution is stopped, {@code false}
    127     * is returned, and no further bit maps are processed.
    128     *
    129     * <p>If the producer is empty this method will return true.</p>
    130     *
    131     * <p>Any exceptions thrown by the action are relayed to the caller.</p>
    132     *
    133     * @param predicate the function to execute
    134     * @return {@code true} if all bit maps returned {@code true}, {@code false} otherwise.
    135     * @throws NullPointerException if the specified consumer is null
    136     */
    137    boolean forEachBitMap(LongPredicate predicate);
    138
    139    /**
    140     * Applies the {@code func} to each bit map pair in order. Will apply all of the bit maps from the other
    141     * BitMapProducer to this producer. If this producer does not have as many bit maps it will provide 0 (zero)
    142     * for all excess calls to the LongBiPredicate.
    143     * <p>
    144     * <em>The default implementation of this method uses {@code asBitMapArray()}. It is recommended that implementations
    145     * of BitMapProducer that have local arrays reimplement this method.</em></p>
    146     *
    147     * @param other The other BitMapProducer that provides the y values in the (x,y) pair.
    148     * @param func The function to apply.
    149     * @return A LongPredicate that tests this BitMapProducers bitmap values in order.
    150     */
    151    default boolean forEachBitMapPair(final BitMapProducer other, final LongBiPredicate func) {
    152        final CountingLongPredicate p = new CountingLongPredicate(asBitMapArray(), func);
    153        return other.forEachBitMap(p) && p.forEachRemaining();
    154    }
    155}