BitIndexUpdatingInterval.java

  1. /*
  2.  * Licensed to the Apache Software Foundation (ASF) under one or more
  3.  * contributor license agreements.  See the NOTICE file distributed with
  4.  * this work for additional information regarding copyright ownership.
  5.  * The ASF licenses this file to You under the Apache License, Version 2.0
  6.  * (the "License"); you may not use this file except in compliance with
  7.  * the License.  You may obtain a copy of the License at
  8.  *
  9.  *      http://www.apache.org/licenses/LICENSE-2.0
  10.  *
  11.  * Unless required by applicable law or agreed to in writing, software
  12.  * distributed under the License is distributed on an "AS IS" BASIS,
  13.  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  14.  * See the License for the specific language governing permissions and
  15.  * limitations under the License.
  16.  */
  17. package org.apache.commons.numbers.arrays;

  19. /**
  20.  * An {@link UpdatingInterval} backed by a fixed size of bits.
  21.  *
  22.  * <p>This is a specialised class to implement a reduced API similar to a
  23.  * {@link java.util.BitSet}. It uses no bounds range checks and supports only
  24.  * the methods required to implement the {@link UpdatingInterval} API.
  25.  *
  26.  * <p>An offset is supported to allow the fixed size to cover a range of indices starting
  27.  * above 0 with the most efficient usage of storage.
  28.  *
  29.  * <p>See the BloomFilter code in Commons Collections for use of long[] data to store
  30.  * bits.
  31.  *
  32.  * @since 1.2
  33.  */
  34. final class BitIndexUpdatingInterval implements UpdatingInterval {
  35.     /** All 64-bits bits set. */
  36.     private static final long LONG_MASK = -1L;
  37.     /** A bit shift to apply to an integer to divided by 64 (2^6). */
  38.     private static final int DIVIDE_BY_64 = 6;

  40.     /** Bit indexes. */
  41.     private final long[] data;

  43.     /** Index offset. */
  44.     private final int offset;
  45.     /** Left bound of the support. */
  46.     private int left;
  47.     /** Right bound of the support. */
  48.     private int right;

  50.     /**
  51.      * Create an instance to store indices within the range {@code [left, right]}.
  52.      * The range is not validated.
  53.      *
  54.      * @param left Lower bound (inclusive).
  55.      * @param right Upper bound (inclusive).
  56.      */
  57.     BitIndexUpdatingInterval(int left, int right) {
  58.         this.offset = left;
  59.         this.left = left;
  60.         this.right = right;
  61.         // Allocate storage to store index==right
  62.         // Note: This may allow directly writing to index > right if there
  63.         // is extra capacity.
  64.         data = new long[getLongIndex(right - offset) + 1];
  65.     }

  67.     /**
  68.      * Create an instance with the range {@code [left, right]} and reusing the provided
  69.      * index {@code data}.
  70.      *
  71.      * @param data Data.
  72.      * @param offset Index offset.
  73.      * @param left Lower bound (inclusive).
  74.      * @param right Upper bound (inclusive).
  75.      */
  76.     private BitIndexUpdatingInterval(long[] data, int offset, int left, int right) {
  77.         this.data = data;
  78.         this.offset = offset;
  79.         this.left = left;
  80.         this.right = right;
  81.     }

  83.     /**
  84.      * Gets the filter index for the specified bit index assuming the filter is using
  85.      * 64-bit longs to store bits starting at index 0.
  86.      *
  87.      * <p>The index is assumed to be positive. For a positive index the result will match
  88.      * {@code bitIndex / 64}.</p>
  89.      *
  90.      * <p><em>The divide is performed using bit shifts. If the input is negative the
  91.      * behavior is not defined.</em></p>
  92.      *
  93.      * @param bitIndex the bit index (assumed to be positive)
  94.      * @return the index of the bit map in an array of bit maps.
  95.      */
  96.     private static int getLongIndex(final int bitIndex) {
  97.         // An integer divide by 64 is equivalent to a shift of 6 bits if the integer is
  98.         // positive.
  99.         // We do not explicitly check for a negative here. Instead we use a
  100.         // signed shift. Any negative index will produce a negative value
  101.         // by sign-extension and if used as an index into an array it will throw an
  102.         // exception.
  103.         return bitIndex >> DIVIDE_BY_64;
  104.     }

  106.     /**
  107.      * Gets the filter bit mask for the specified bit index assuming the filter is using
  108.      * 64-bit longs to store bits starting at index 0. The returned value is a
  109.      * {@code long} with only 1 bit set.
  110.      *
  111.      * <p>The index is assumed to be positive. For a positive index the result will match
  112.      * {@code 1L << (bitIndex % 64)}.</p>
  113.      *
  114.      * <p><em>If the input is negative the behavior is not defined.</em></p>
  115.      *
  116.      * @param bitIndex the bit index (assumed to be positive)
  117.      * @return the filter bit
  118.      */
  119.     private static long getLongBit(final int bitIndex) {
  120.         // Bit shifts only use the first 6 bits. Thus it is not necessary to mask this
  121.         // using 0x3f (63) or compute bitIndex % 64.
  122.         // Note: If the index is negative the shift will be (64 - (bitIndex & 0x3f)) and
  123.         // this will identify an incorrect bit.
  124.         return 1L << bitIndex;
  125.     }

  127.     /**
  128.      * Sets the bit at the specified index to {@code true}.
  129.      *
  130.      * <p>Warning: This has no range checks.
  131.      *
  132.      * @param bitIndex the bit index (assumed to be positive)
  133.      */
  134.     void set(int bitIndex) {
  135.         // WARNING: No range checks !!!
  136.         final int index = bitIndex - offset;
  137.         final int i = getLongIndex(index);
  138.         final long m = getLongBit(index);
  139.         data[i] |= m;
  140.     }

  142.     /**
  143.      * Returns the index of the first bit that is set to {@code true} that occurs on or
  144.      * after the specified starting index.
  145.      *
  146.      * <p>Warning: This has no range checks. It is assumed that {@code left <= k <= right},
  147.      * that is there is a set bit on or after {@code k}.
  148.      *
  149.      * @param k Index to start checking from (inclusive).
  150.      * @return the index of the next set bit
  151.      */
  152.     private int nextIndex(int k) {
  153.         // left <= k <= right

  155.         final int index = k - offset;
  156.         int i = getLongIndex(index);

  158.         // Mask bits after the bit index
  159.         // mask = 11111000 = -1L << (index % 64)
  160.         long bits = data[i] & (LONG_MASK << index);
  161.         for (;;) {
  162.             if (bits != 0) {
  163.                 //(i+1)       i
  164.                 // |    index |
  165.                 // |      |   |
  166.                 // 0  001010000
  167.                 return i * Long.SIZE + Long.numberOfTrailingZeros(bits) + offset;
  168.             }
  169.             // Unsupported: the interval should contain k
  170.             //if (++i == data.length)
  171.             //    return right + 1
  172.             bits = data[++i];
  173.         }
  174.     }

  176.     /**
  177.      * Returns the index of the first bit that is set to {@code true} that occurs on or
  178.      * before the specified starting index.
  179.      *
  180.      * <p>Warning: This has no range checks. It is assumed that {@code left <= k <= right},
  181.      * that is there is a set bit on or before {@code k}.
  182.      *
  183.      * @param k Index to start checking from (inclusive).
  184.      * @return the index of the previous set bit
  185.      */
  186.     private int previousIndex(int k) {
  187.         // left <= k <= right

  189.         final int index = k - offset;
  190.         int i = getLongIndex(index);

  192.         // Mask bits before the bit index
  193.         // mask = 00011111 = -1L >>> (64 - ((index + 1) % 64))
  194.         long bits = data[i] & (LONG_MASK >>> -(index + 1));
  195.         for (;;) {
  196.             if (bits != 0) {
  197.                 //(i+1)       i
  198.                 // |  index   |
  199.                 // |    |     |
  200.                 // 0  001010000
  201.                 return (i + 1) * Long.SIZE - Long.numberOfLeadingZeros(bits) - 1 + offset;
  202.             }
  203.             // Unsupported: the interval should contain k
  204.             //if (i == 0)
  205.             //    return left - 1
  206.             bits = data[--i];
  207.         }
  208.     }

  210.     @Override
  211.     public int left() {
  212.         return left;
  213.     }

  215.     @Override
  216.     public int right() {
  217.         return right;
  218.     }

  220.     @Override
  221.     public int updateLeft(int k) {
  222.         // Assume left < k= < right
  223.         return left = nextIndex(k);
  224.     }

  226.     @Override
  227.     public int updateRight(int k) {
  228.         // Assume left <= k < right
  229.         return right = previousIndex(k);
  230.     }

  232.     @Override
  233.     public UpdatingInterval splitLeft(int ka, int kb) {
  234.         // Assume left < ka <= kb < right
  235.         final int lower = left;
  236.         left = nextIndex(kb + 1);
  237.         return new BitIndexUpdatingInterval(data, offset, lower, previousIndex(ka - 1));
  238.     }
  239. }
Created with JaCoCo 0.8.12.202403310830Code Coverage Report for Apache Commons Numbers 1.2