Class BitIndexUpdatingInterval

  • All Implemented Interfaces:
    UpdatingInterval

    final class BitIndexUpdatingInterval
    extends java.lang.Object
    implements UpdatingInterval
    An UpdatingInterval backed by a fixed size of bits.

    This is a specialised class to implement a reduced API similar to a BitSet. It uses no bounds range checks and supports only the methods required to implement the UpdatingInterval API.

    An offset is supported to allow the fixed size to cover a range of indices starting above 0 with the most efficient usage of storage.

    See the BloomFilter code in Commons Collections for use of long[] data to store bits.

    Since:
    1.2
    • Field Summary

      Fields 
      Modifier and Type Field Description
      private long[] data
      Bit indexes.
      private static int DIVIDE_BY_64
      A bit shift to apply to an integer to divided by 64 (2^6).
      private int left
      Left bound of the support.
      private static long LONG_MASK
      All 64-bits bits set.
      private int offset
      Index offset.
      private int right
      Right bound of the support.
    • Constructor Summary

      Constructors 
      Modifier Constructor Description
      (package private) BitIndexUpdatingInterval​(int left, int right)
      Create an instance to store indices within the range [left, right].
      private BitIndexUpdatingInterval​(long[] data, int offset, int left, int right)
      Create an instance with the range [left, right] and reusing the provided index data.
    • Method Summary

      All Methods Static Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      private static long getLongBit​(int bitIndex)
      Gets the filter bit mask for the specified bit index assuming the filter is using 64-bit longs to store bits starting at index 0.
      private static int getLongIndex​(int bitIndex)
      Gets the filter index for the specified bit index assuming the filter is using 64-bit longs to store bits starting at index 0.
      int left()
      The start (inclusive) of the interval.
      private int nextIndex​(int k)
      Returns the index of the first bit that is set to true that occurs on or after the specified starting index.
      private int previousIndex​(int k)
      Returns the index of the first bit that is set to true that occurs on or before the specified starting index.
      int right()
      The end (inclusive) of the interval.
      (package private) void set​(int bitIndex)
      Sets the bit at the specified index to true.
      UpdatingInterval splitLeft​(int ka, int kb)
      Split the interval using two splitting indices.
      int updateLeft​(int k)
      Update the left bound of the interval so k <= left.
      int updateRight​(int k)
      Update the right bound of the interval so right <= k.
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
    • Field Detail

      • DIVIDE_BY_64

        private static final int DIVIDE_BY_64
        A bit shift to apply to an integer to divided by 64 (2^6).
        See Also:
        Constant Field Values
      • data

        private final long[] data
        Bit indexes.
      • offset

        private final int offset
        Index offset.
      • left

        private int left
        Left bound of the support.
      • right

        private int right
        Right bound of the support.
    • Constructor Detail

      • BitIndexUpdatingInterval

        BitIndexUpdatingInterval​(int left,
                                 int right)
        Create an instance to store indices within the range [left, right]. The range is not validated.
        Parameters:
        left - Lower bound (inclusive).
        right - Upper bound (inclusive).
      • BitIndexUpdatingInterval

        private BitIndexUpdatingInterval​(long[] data,
                                         int offset,
                                         int left,
                                         int right)
        Create an instance with the range [left, right] and reusing the provided index data.
        Parameters:
        data - Data.
        offset - Index offset.
        left - Lower bound (inclusive).
        right - Upper bound (inclusive).
    • Method Detail

      • getLongIndex

        private static int getLongIndex​(int bitIndex)
        Gets the filter index for the specified bit index assuming the filter is using 64-bit longs to store bits starting at index 0.

        The index is assumed to be positive. For a positive index the result will match bitIndex / 64.

        The divide is performed using bit shifts. If the input is negative the behavior is not defined.

        Parameters:
        bitIndex - the bit index (assumed to be positive)
        Returns:
        the index of the bit map in an array of bit maps.
      • getLongBit

        private static long getLongBit​(int bitIndex)
        Gets the filter bit mask for the specified bit index assuming the filter is using 64-bit longs to store bits starting at index 0. The returned value is a long with only 1 bit set.

        The index is assumed to be positive. For a positive index the result will match 1L << (bitIndex % 64).

        If the input is negative the behavior is not defined.

        Parameters:
        bitIndex - the bit index (assumed to be positive)
        Returns:
        the filter bit
      • set

        void set​(int bitIndex)
        Sets the bit at the specified index to true.

        Warning: This has no range checks.

        Parameters:
        bitIndex - the bit index (assumed to be positive)
      • nextIndex

        private int nextIndex​(int k)
        Returns the index of the first bit that is set to true that occurs on or after the specified starting index.

        Warning: This has no range checks. It is assumed that left <= k <= right, that is there is a set bit on or after k.

        Parameters:
        k - Index to start checking from (inclusive).
        Returns:
        the index of the next set bit
      • previousIndex

        private int previousIndex​(int k)
        Returns the index of the first bit that is set to true that occurs on or before the specified starting index.

        Warning: This has no range checks. It is assumed that left <= k <= right, that is there is a set bit on or before k.

        Parameters:
        k - Index to start checking from (inclusive).
        Returns:
        the index of the previous set bit
      • left

        public int left()
        Description copied from interface: UpdatingInterval
        The start (inclusive) of the interval.
        Specified by:
        left in interface UpdatingInterval
        Returns:
        start of the interval
      • right

        public int right()
        Description copied from interface: UpdatingInterval
        The end (inclusive) of the interval.
        Specified by:
        right in interface UpdatingInterval
        Returns:
        end of the interval
      • updateLeft

        public int updateLeft​(int k)
        Description copied from interface: UpdatingInterval
        Update the left bound of the interval so k <= left.

        Note: Requires left < k <= right, i.e. there exists a valid interval above the index.

        
         l-----------k----------r
                     |--> l
         
        Specified by:
        updateLeft in interface UpdatingInterval
        Parameters:
        k - Index to start checking from (inclusive).
        Returns:
        the new left
      • updateRight

        public int updateRight​(int k)
        Description copied from interface: UpdatingInterval
        Update the right bound of the interval so right <= k.

        Note: Requires left <= k < right, i.e. there exists a valid interval below the index.

        
         l-----------k----------r
                r <--|
         
        Specified by:
        updateRight in interface UpdatingInterval
        Parameters:
        k - Index to start checking from (inclusive).
        Returns:
        the new right
      • splitLeft

        public UpdatingInterval splitLeft​(int ka,
                                          int kb)
        Description copied from interface: UpdatingInterval
        Split the interval using two splitting indices. Returns the left interval that occurs before the specified split index ka, and updates the current interval left bound to after the specified split index kb.

        Note: Requires left < ka <= kb < right, i.e. there exists a valid interval both above and below the splitting indices.

        
         l-----------ka-kb----------r
              r1 <--|     |--> l1
        
         r1 < ka
         l1 > kb
         

        If ka <= left or kb >= right the result is undefined.

        Specified by:
        splitLeft in interface UpdatingInterval
        Parameters:
        ka - Split index.
        kb - Split index.
        Returns:
        the left interval