    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 * <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     * @return An array of bit map data.
    098     */
    099    default long[] asBitMapArray() {
    100        final class Bits {
    101            private long[] data = new long[16];
    102            private int size;
    103
    104            boolean add(final long bits) {
    105                if (size == data.length) {
    106                    // This will throw an out-of-memory error if there are too many bits.
    107                    // Since bits are addressed using 32-bit signed integer indices
    108                    // the maximum length should be ~2^31 / 2^6 = ~2^25.
    109                    // Any more is a broken implementation.
    110                    data = Arrays.copyOf(data, size * 2);
    111                }
    112                data[size++] = bits;
    113                return true;
    114            }
    115
    116            long[] toArray() {
    117                // Edge case to avoid a large array copy
    118                return size == data.length ? data : Arrays.copyOf(data, size);
    119            }
    120        }
    121        final Bits bits = new Bits();
    122        processBitMaps(bits::add);
    123        return bits.toArray();
    124    }
    125
    126    /**
    127     * 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
    128     * extractor does not have as many bit maps it will provide 0 (zero) for all excess calls to the LongBiPredicate.
    129     * <p>
    130     * <em>The default implementation of this method uses {@code asBitMapArray()}. It is recommended that implementations of BitMapExtractor that have local
    131     * arrays reimplement this method.</em>
    132     * </p>
    133     *
    134     * @param other The other BitMapExtractor that provides the y values in the (x,y) pair.
    135     * @param func  The function to apply.
    136     * @return A LongPredicate that tests this BitMapExtractor's bitmap values in order.
    137     */
    138    default boolean processBitMapPairs(final BitMapExtractor other, final LongBiPredicate func) {
    139        final CountingLongPredicate p = new CountingLongPredicate(asBitMapArray(), func);
    140        return other.processBitMaps(p) && p.processRemaining();
    141    }
    142
    143    /**
    144     * Each bit map is passed to the predicate in order. The predicate is applied to each
    145     * bit map value, if the predicate returns {@code false} the execution is stopped, {@code false}
    146     * is returned, and no further bit maps are processed.
    147     *
    148     * <p>If the extractor is empty this method will return true.</p>
    149     *
    150     * <p>Any exceptions thrown by the action are relayed to the caller.</p>
    151     *
    152     * @param predicate the function to execute
    153     * @return {@code true} if all bit maps returned {@code true}, {@code false} otherwise.
    154     * @throws NullPointerException if the specified consumer is null
    155     */
    156    boolean processBitMaps(LongPredicate predicate);
    157}