Class BitIndexUpdatingInterval
- All Implemented Interfaces:
UpdatingInterval
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
FieldsModifier and TypeFieldDescriptionprivate final long[]
Bit indexes.private static final int
A bit shift to apply to an integer to divided by 64 (2^6).private int
Left bound of the support.private static final long
All 64-bits bits set.private final int
Index offset.private int
Right bound of the support. -
Constructor Summary
ConstructorsModifierConstructorDescription(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 indexdata
. -
Method Summary
Modifier and TypeMethodDescriptionprivate 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 totrue
that occurs on or after the specified starting index.private int
previousIndex
(int k) Returns the index of the first bit that is set totrue
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 totrue
.splitLeft
(int ka, int kb) Split the interval using two splitting indices.int
updateLeft
(int k) Update the left bound of the interval sok <= left
.int
updateRight
(int k) Update the right bound of the interval soright <= k
.
-
Field Details
-
LONG_MASK
private static final long LONG_MASKAll 64-bits bits set.- See Also:
-
DIVIDE_BY_64
private static final int DIVIDE_BY_64A bit shift to apply to an integer to divided by 64 (2^6).- See Also:
-
data
private final long[] dataBit indexes. -
offset
private final int offsetIndex offset. -
left
private int leftLeft bound of the support. -
right
private int rightRight bound of the support.
-
-
Constructor Details
-
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 indexdata
.- Parameters:
data
- Data.offset
- Index offset.left
- Lower bound (inclusive).right
- Upper bound (inclusive).
-
-
Method Details
-
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 along
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 totrue
.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 totrue
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 afterk
.- 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 totrue
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 beforek
.- 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 interfaceUpdatingInterval
- Returns:
- start of the interval
-
right
public int right()Description copied from interface:UpdatingInterval
The end (inclusive) of the interval.- Specified by:
right
in interfaceUpdatingInterval
- Returns:
- end of the interval
-
updateLeft
public int updateLeft(int k) Description copied from interface:UpdatingInterval
Update the left bound of the interval sok <= left
.Note: Requires
left < k <= right
, i.e. there exists a valid interval above the index.l-----------k----------r |--> l
- Specified by:
updateLeft
in interfaceUpdatingInterval
- 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 soright <= k
.Note: Requires
left <= k < right
, i.e. there exists a valid interval below the index.l-----------k----------r r <--|
- Specified by:
updateRight
in interfaceUpdatingInterval
- Parameters:
k
- Index to start checking from (inclusive).- Returns:
- the new right
-
splitLeft
Description copied from interface:UpdatingInterval
Split the interval using two splitting indices. Returns the left interval that occurs before the specified split indexka
, and updates the current interval left bound to after the specified split indexkb
.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
orkb >= right
the result is undefined.- Specified by:
splitLeft
in interfaceUpdatingInterval
- Parameters:
ka
- Split index.kb
- Split index.- Returns:
- the left interval
-