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