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}