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