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