[−][src]Struct rsdict::RsDict
Data structure for efficiently computing both rank and select queries
Implementations
impl RsDict
[src]
pub fn from_blocks(blocks: impl Iterator<Item = u64>) -> Self
[src]
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.
pub fn new() -> Self
[src]
Create a new RsDict
with zero capacity.
pub fn with_capacity(n: usize) -> Self
[src]
Create a new RsDict
with the given capacity preallocated.
pub fn rank(&self, pos: u64, bit: bool) -> u64
[src]
Non-inclusive rank: Count the number of bit
values left of pos
. Panics if pos
is
out-of-bounds.
pub fn bit_and_one_rank(&self, pos: u64) -> (bool, u64)
[src]
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.
pub fn inclusive_rank(&self, pos: u64, bit: bool) -> u64
[src]
Inclusive rank: Count the number of bit
values at indices less than or equal to
pos
. Panics if pos
is out-of-bounds.
pub fn select(&self, rank: u64, bit: bool) -> Option<u64>
[src]
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.
pub fn select0(&self, rank: u64) -> Option<u64>
[src]
Specialized version of RsDict::select
for finding positions of zeros.
pub fn select1(&self, rank: u64) -> Option<u64>
[src]
Specialized version of RsDict::select
for finding positions of ones.
pub fn len(&self) -> usize
[src]
Return the length of the underlying bitmap.
pub fn is_empty(&self) -> bool
[src]
Return whether the underlying bitmap is empty.
pub fn count_ones(&self) -> usize
[src]
Count the number of set bits in the underlying bitmap.
pub fn count_zeros(&self) -> usize
[src]
Count the number of unset bits in the underlying bitmap.
pub fn push(&mut self, bit: bool)
[src]
Push a bit at the end of the underlying bitmap.
pub fn get_bit(&self, pos: u64) -> bool
[src]
Query the pos
th bit (zero-indexed) of the underlying bitmap.
pub fn iter(&self) -> impl Iterator<Item = bool> + '_
[src]
Iterate over the bits in the bitset.
Trait Implementations
impl Clone for RsDict
[src]
impl Debug for RsDict
[src]
impl Eq for RsDict
[src]
impl Ord for RsDict
[src]
fn cmp(&self, rhs: &Self) -> Ordering
[src]
#[must_use]fn max(self, other: Self) -> Self
1.21.0[src]
#[must_use]fn min(self, other: Self) -> Self
1.21.0[src]
#[must_use]fn clamp(self, min: Self, max: Self) -> Self
[src]
impl PartialEq<RsDict> for RsDict
[src]
impl PartialOrd<RsDict> for RsDict
[src]
Auto Trait Implementations
impl RefUnwindSafe for RsDict
impl Send for RsDict
impl Sync for RsDict
impl Unpin for RsDict
impl UnwindSafe for RsDict
Blanket Implementations
impl<T> Any for T where
T: 'static + ?Sized,
[src]
T: 'static + ?Sized,
impl<T> Borrow<T> for T where
T: ?Sized,
[src]
T: ?Sized,
impl<T> BorrowMut<T> for T where
T: ?Sized,
[src]
T: ?Sized,
fn borrow_mut(&mut self) -> &mut T
[src]
impl<T> From<T> for T
[src]
impl<T, U> Into<U> for T where
U: From<T>,
[src]
U: From<T>,
impl<T> ToOwned for T where
T: Clone,
[src]
T: Clone,
type Owned = T
The resulting type after obtaining ownership.
fn to_owned(&self) -> T
[src]
fn clone_into(&self, target: &mut T)
[src]
impl<T, U> TryFrom<U> for T where
U: Into<T>,
[src]
U: Into<T>,
type Error = Infallible
The type returned in the event of a conversion error.
fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>
[src]
impl<T, U> TryInto<U> for T where
U: TryFrom<T>,
[src]
U: TryFrom<T>,