    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 *      https://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.function.IntPredicate;
    020
    021/**
    022 * A convenience class for Hasher implementations to filter out duplicate indices.
    023 *
    024 * <p><em>If the index is negative the behavior is not defined.</em></p>
    025 *
    026 * <p>This is conceptually a unique filter implemented as an {@link IntPredicate}.</p>
    027 *
    028 * @since 4.5.0-M1
    029 */
    030public final class IndexFilter {
    031
    032    /**
    033     * An IndexTracker implementation that uses an array of integers to track whether or not a
    034     * number has been seen. Suitable for Shapes that have few hash functions.
    035     *
    036     * @since 4.5.0
    037     */
    038    static class ArrayTracker implements IntPredicate {
    039        private final int[] seen;
    040        private int populated;
    041
    042        /**
    043         * Constructs the tracker based on the shape.
    044         *
    045         * @param shape The shape to build the tracker for.
    046         */
    047        ArrayTracker(final Shape shape) {
    048            seen = new int[shape.getNumberOfHashFunctions()];
    049        }
    050
    051        @Override
    052        public boolean test(final int number) {
    053            if (number < 0) {
    054                throw new IndexOutOfBoundsException("number may not be less than zero. " + number);
    055            }
    056            for (int i = 0; i < populated; i++) {
    057                if (seen[i] == number) {
    058                    return false;
    059                }
    060            }
    061            seen[populated++] = number;
    062            return true;
    063        }
    064    }
    065
    066    /**
    067     * An IndexTracker implementation that uses an array of bit maps to track whether or not a
    068     * number has been seen.
    069     */
    070    static class BitMapTracker implements IntPredicate {
    071        private final long[] bits;
    072
    073        /**
    074         * Constructs a bit map based tracker for the specified shape.
    075         *
    076         * @param shape The shape that is being generated.
    077         */
    078        BitMapTracker(final Shape shape) {
    079            bits = BitMaps.newBitMap(shape);
    080        }
    081
    082        @Override
    083        public boolean test(final int number) {
    084            final boolean retval = !BitMaps.contains(bits, number);
    085            BitMaps.set(bits, number);
    086            return retval;
    087        }
    088    }
    089
    090    /**
    091     * Creates an instance optimized for the specified shape.
    092     *
    093     * @param shape The shape that is being generated.
    094     * @param consumer The consumer to accept the values.
    095     * @return An IndexFilter optimized for the specified shape.
    096     */
    097    public static IntPredicate create(final Shape shape, final IntPredicate consumer) {
    098        return new IndexFilter(shape, consumer)::test;
    099    }
    100
    101    private final IntPredicate tracker;
    102
    103    private final int size;
    104
    105    private final IntPredicate consumer;
    106
    107    /**
    108     * Creates an instance optimized for the specified shape.
    109     *
    110     * @param shape The shape that is being generated.
    111     * @param consumer The consumer to accept the values.
    112     */
    113    private IndexFilter(final Shape shape, final IntPredicate consumer) {
    114        this.size = shape.getNumberOfBits();
    115        this.consumer = consumer;
    116        if (BitMaps.numberOfBitMaps(shape) * Long.BYTES < (long) shape.getNumberOfHashFunctions() * Integer.BYTES) {
    117            this.tracker = new BitMapTracker(shape);
    118        } else {
    119            this.tracker = new ArrayTracker(shape);
    120        }
    121    }
    122
    123    /**
    124     * Test if the number should be processed by the {@code consumer}.
    125     *
    126     * <p>If the number has <em>not</em> been seen before it is passed to the {@code consumer} and the result returned.
    127     * If the number has been seen before the {@code consumer} is not called and {@code true} returned.</p>
    128     *
    129     * <p><em>If the input is not in the range [0,size) an IndexOutOfBoundsException exception is thrown.</em></p>
    130     *
    131     * @param number The number to check.
    132     * @return {@code true} if processing should continue, {@code false} otherwise.
    133     */
    134    public boolean test(final int number) {
    135        if (number >= size) {
    136            throw new IndexOutOfBoundsException(String.format("number too large %d >= %d", number, size));
    137        }
    138        if (tracker.test(number)) {
    139            return consumer.test(number);
    140        }
    141        return true;
    142    }
    143}