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}