pub struct RsDict { /* private fields */ }
Expand description
Data structure for efficiently computing both rank and select queries
Implementations§
source§impl RsDict
impl RsDict
sourcepub fn from_blocks(blocks: impl Iterator<Item = u64>) -> Self
pub fn from_blocks(blocks: impl Iterator<Item = u64>) -> Self
Create a dictionary from a bitset, specified as an iterator of 64-bit blocks. This function is equivalent to pushing each bit one at a time but is much faster.
sourcepub fn heap_size(&self) -> usize
pub fn heap_size(&self) -> usize
Return the size of the heap allocations associated with the RsDict
.
sourcepub fn with_capacity(n: usize) -> Self
pub fn with_capacity(n: usize) -> Self
Create a new RsDict
with the given capacity preallocated.
sourcepub fn rank(&self, pos: u64, bit: bool) -> u64
pub fn rank(&self, pos: u64, bit: bool) -> u64
Non-inclusive rank: Count the number of bit
values left of pos
. Panics if pos
is
out-of-bounds.
sourcepub fn bit_and_one_rank(&self, pos: u64) -> (bool, u64)
pub fn bit_and_one_rank(&self, pos: u64) -> (bool, u64)
Query the pos
th bit (zero-indexed) of the underlying bit and the number of set bits to the
left of pos
in a single operation. This method is faster than calling get_bit(pos)
and
rank(pos, true)
separately.
sourcepub fn inclusive_rank(&self, pos: u64, bit: bool) -> u64
pub fn inclusive_rank(&self, pos: u64, bit: bool) -> u64
Inclusive rank: Count the number of bit
values at indices less than or equal to
pos
. Panics if pos
is out-of-bounds.
sourcepub fn select(&self, rank: u64, bit: bool) -> Option<u64>
pub fn select(&self, rank: u64, bit: bool) -> Option<u64>
Compute the position of the rank
th instance of bit
(zero-indexed), returning None
if
there are not rank + 1
instances of bit
in the array.
sourcepub fn select0(&self, rank: u64) -> Option<u64>
pub fn select0(&self, rank: u64) -> Option<u64>
Specialized version of RsDict::select
for finding positions of zeros.
sourcepub fn select1(&self, rank: u64) -> Option<u64>
pub fn select1(&self, rank: u64) -> Option<u64>
Specialized version of RsDict::select
for finding positions of ones.
sourcepub fn count_ones(&self) -> usize
pub fn count_ones(&self) -> usize
Count the number of set bits in the underlying bitmap.
sourcepub fn count_zeros(&self) -> usize
pub fn count_zeros(&self) -> usize
Count the number of unset bits in the underlying bitmap.
Trait Implementations§
source§impl Ord for RsDict
impl Ord for RsDict
source§impl PartialOrd for RsDict
impl PartialOrd for RsDict
1.0.0 · source§fn le(&self, other: &Rhs) -> bool
fn le(&self, other: &Rhs) -> bool
self
and other
) and is used by the <=
operator. Read more