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
019/**
020 * Contains functions to convert {@code int} indices into Bloom filter bit positions and visa versa.
021 *
022 * <p>The functions view an array of longs as a collection of bit maps each containing 64 bits. The bits are arranged
023 * in memory as a little-endian long value. This matches the requirements of the BitMapExtractor interface.</p>
024 *
025 * @since 4.5.0-M2
026 */
027public class BitMaps {
028
029    /** A bit shift to apply to an integer to divided by 64 (2^6). */
030    private static final int DIVIDE_BY_64 = 6;
031
032    /**
033     * Checks if the specified index bit is enabled in the array of bit maps.
034     * <p>
035     * If the bit specified by bitIndex is not in the bit map false is returned.
036     * </p>
037     *
038     * @param bitMaps  The array of bit maps.
039     * @param bitIndex the index of the bit to locate.
040     * @return {@code true} if the bit is enabled, {@code false} otherwise.
041     * @throws IndexOutOfBoundsException if bitIndex specifies a bit not in the range being tracked.
042     */
043    public static boolean contains(final long[] bitMaps, final int bitIndex) {
044        return (bitMaps[getLongIndex(bitIndex)] & getLongBit(bitIndex)) != 0;
045    }
046
047    /**
048     * Gets the filter bit mask for the specified bit index assuming the filter is using 64-bit
049     * longs to store bits starting at index 0. The returned value is a {@code long} with only
050     * 1 bit set.
051     *
052     * <p>The index is assumed to be positive. For a positive index the result will match
053     * {@code 1L << (bitIndex % 64)}.</p>
054     *
055     * <p><em>If the input is negative the behavior is not defined.</em></p>
056     *
057     * @param bitIndex the bit index (assumed to be positive)
058     * @return the filter bit
059     */
060    public static long getLongBit(final int bitIndex) {
061        // Bit shifts only use the first 6 bits. Thus it is not necessary to mask this
062        // using 0x3f (63) or compute bitIndex % 64.
063        // Note: If the index is negative the shift will be (64 - (bitIndex & 0x3f)) and
064        // this will identify an incorrect bit.
065        return 1L << bitIndex;
066    }
067
068    /**
069     * Gets the filter index for the specified bit index assuming the filter is using 64-bit longs
070     * to store bits starting at index 0.
071     *
072     * <p>The index is assumed to be positive. For a positive index the result will match
073     * {@code bitIndex / 64}.</p>
074     *
075     * <p><em>The divide is performed using bit shifts. If the input is negative the behavior
076     * is not defined.</em></p>
077     *
078     * @param bitIndex the bit index (assumed to be positive)
079     * @return the index of the bit map in an array of bit maps.
080     */
081    public static int getLongIndex(final int bitIndex) {
082        // An integer divide by 64 is equivalent to a shift of 6 bits if the integer is
083        // positive.
084        // We do not explicitly check for a negative here. Instead we use a
085        // signed shift. Any negative index will produce a negative value
086        // by sign-extension and if used as an index into an array it will throw an
087        // exception.
088        return bitIndex >> DIVIDE_BY_64;
089    }
090
091    /**
092     * Performs a modulus calculation on an unsigned long and a positive integer divisor.
093     *
094     * <p>This method computes the same result as {@link Long#remainderUnsigned(long, long)}
095     * but assumes that the divisor is an integer in the range 1 to 2<sup>31</sup> - 1 inclusive,
096     * that is a strictly positive integer size.
097     *
098     * <p><em>If the divisor is negative the behavior is not defined.</em></p>
099     *
100     * @param dividend an unsigned long value to calculate the modulus of.
101     * @param divisor the divisor for the modulus calculation, must be strictly positive.
102     * @return the remainder or modulus value.
103     * @throws ArithmeticException if the divisor is zero
104     * @see Long#remainderUnsigned(long, long)
105     */
106    public static int mod(final long dividend, final int divisor) {
107        // See Hacker's Delight (2nd ed), section 9.3.
108        // Assume divisor is positive.
109        // Divide half the unsigned number and then double the quotient result.
110        final long quotient = (dividend >>> 1) / divisor << 1;
111        final long remainder = dividend - quotient * divisor;
112        // remainder in [0, 2 * divisor)
113        return (int) (remainder >= divisor ? remainder - divisor : remainder);
114    }
115
116    /**
117     * Creates a new bitmap for the number of bit maps (longs) required for the numberOfBits parameter.
118     *
119     * <p><em>If the input is negative the behavior is not defined.</em></p>
120     *
121     * @param numberOfBits the number of bits to store in the array of bit maps.
122     * @return a new bitmap.
123     */
124    static long[] newBitMap(final int numberOfBits) {
125        return new long[numberOfBitMaps(numberOfBits)];
126    }
127
128    /**
129     * Creates a new bitmap for given shape parameter.
130     *
131     * @param shape the shape.
132     * @return a new bitmap.
133     */
134    static long[] newBitMap(final Shape shape) {
135        return newBitMap(shape.getNumberOfBits());
136    }
137
138    /**
139     * Calculates the number of bit maps (longs) required for the numberOfBits parameter.
140     *
141     * <p><em>If the input is negative the behavior is not defined.</em></p>
142     *
143     * @param numberOfBits the number of bits to store in the array of bit maps.
144     * @return the number of bit maps necessary.
145     */
146    public static int numberOfBitMaps(final int numberOfBits) {
147        return (numberOfBits - 1 >> DIVIDE_BY_64) + 1;
148    }
149
150    /**
151     * Calculates the number of bit maps (longs) required for the shape parameter.
152     *
153     * @param shape the shape.
154     * @return the number of bit maps necessary.
155     */
156    static int numberOfBitMaps(final Shape shape) {
157        return numberOfBitMaps(shape.getNumberOfBits());
158    }
159
160    /**
161     * Sets the bit in the bit maps.
162     * <p><em>Does not perform range checking</em></p>
163     *
164     * @param bitMaps  The array of bit maps.
165     * @param bitIndex the index of the bit to set.
166     * @throws IndexOutOfBoundsException if bitIndex specifies a bit not in the range being tracked.
167     */
168    public static void set(final long[] bitMaps, final int bitIndex) {
169        bitMaps[getLongIndex(bitIndex)] |= getLongBit(bitIndex);
170    }
171
172    /** Do not instantiate. */
173    private BitMaps() {
174    }
175}