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