    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.BitSet;
    021import java.util.Objects;
    022import java.util.function.IntPredicate;
    023import java.util.function.LongPredicate;
    024
    025/**
    026 * An object that produces indices of a Bloom filter.
    027 * <p><em>
    028 * The default implementation of {@code asIndexArray} is slow. Implementers should reimplement the
    029 * method where possible.</em></p>
    030 *
    031 * @since 4.5.0-M2
    032 */
    033@FunctionalInterface
    034public interface IndexExtractor {
    035
    036    /**
    037     * Creates an IndexExtractor from a {@code BitMapExtractor}.
    038     *
    039     * @param bitMapExtractor the {@code BitMapExtractor}
    040     * @return a new {@code IndexExtractor}.
    041     */
    042    static IndexExtractor fromBitMapExtractor(final BitMapExtractor bitMapExtractor) {
    043        Objects.requireNonNull(bitMapExtractor, "bitMapExtractor");
    044        return consumer -> {
    045            final LongPredicate longPredicate = new LongPredicate() {
    046                int wordIdx;
    047
    048                @Override
    049                public boolean test(long word) {
    050                    int i = wordIdx;
    051                    while (word != 0) {
    052                        if ((word & 1) == 1 && !consumer.test(i)) {
    053                            return false;
    054                        }
    055                        word >>>= 1;
    056                        i++;
    057                    }
    058                    wordIdx += 64;
    059                    return true;
    060                }
    061            };
    062            return bitMapExtractor.processBitMaps(longPredicate::test);
    063        };
    064    }
    065
    066    /**
    067     * Creates an IndexExtractor from an array of integers.
    068     *
    069     * @param values the index values
    070     * @return an IndexExtractor that uses the values.
    071     */
    072    static IndexExtractor fromIndexArray(final int... values) {
    073        return new IndexExtractor() {
    074
    075            @Override
    076            public int[] asIndexArray() {
    077                return values.clone();
    078            }
    079
    080            @Override
    081            public boolean processIndices(final IntPredicate predicate) {
    082                for (final int value : values) {
    083                    if (!predicate.test(value)) {
    084                        return false;
    085                    }
    086                }
    087                return true;
    088            }
    089        };
    090    }
    091
    092    /**
    093     * Return a copy of the IndexExtractor data as an int array.
    094     *
    095     * <p>Indices ordering and uniqueness is not guaranteed.</p>
    096     *
    097     * <p><em>
    098     * The default implementation of this method creates an array and populates
    099     * it.  Implementations that have access to an index array should consider
    100     * returning a copy of that array if possible.
    101     * </em></p>
    102     *
    103     * @return An int array of the data.
    104     */
    105    default int[] asIndexArray() {
    106        class Indices {
    107            private int[] data = new int[32];
    108            private int size;
    109
    110            boolean add(final int index) {
    111                data = IndexUtils.ensureCapacityForAdd(data, size);
    112                data[size++] = index;
    113                return true;
    114            }
    115
    116            int[] toArray() {
    117                // Edge case to avoid a large array copy
    118                return size == data.length ? data : Arrays.copyOf(data, size);
    119            }
    120        }
    121        final Indices indices = new Indices();
    122        processIndices(indices::add);
    123        return indices.toArray();
    124    }
    125
    126    /**
    127     * Each index is passed to the predicate. The predicate is applied to each
    128     * index value, if the predicate returns {@code false} the execution is stopped, {@code false}
    129     * is returned, and no further indices are processed.
    130     *
    131     * <p>Any exceptions thrown by the action are relayed to the caller.</p>
    132     *
    133     * <p>Indices ordering and uniqueness is not guaranteed.</p>
    134     *
    135     * @param predicate the action to be performed for each non-zero bit index.
    136     * @return {@code true} if all indexes return true from consumer, {@code false} otherwise.
    137     * @throws NullPointerException if the specified action is null
    138     */
    139    boolean processIndices(IntPredicate predicate);
    140
    141    /**
    142     * Creates an IndexExtractor comprising the unique indices for this extractor.
    143     *
    144     * <p>By default creates a new extractor with some overhead to remove
    145     * duplicates.  IndexExtractors that return unique indices by default
    146     * should override this to return {@code this}.</p>
    147     *
    148     * <p>The default implementation will filter the indices from this instance
    149     * and return them in ascending order.</p>
    150     *
    151     * @return the IndexExtractor of unique values.
    152     * @throws IndexOutOfBoundsException if any index is less than zero.
    153     */
    154    default IndexExtractor uniqueIndices() {
    155        final BitSet bitSet = new BitSet();
    156        processIndices(i -> {
    157            bitSet.set(i);
    158            return true;
    159        });
    160
    161        return new IndexExtractor() {
    162            @Override
    163            public boolean processIndices(final IntPredicate predicate) {
    164                for (int idx = bitSet.nextSetBit(0); idx >= 0; idx = bitSet.nextSetBit(idx + 1)) {
    165                    if (!predicate.test(idx)) {
    166                        return false;
    167                    }
    168                }
    169                return true;
    170            }
    171
    172            @Override
    173            public IndexExtractor uniqueIndices() {
    174                return this;
    175            }
    176        };
    177    }
    178}