Struct indexed_bitvec::IndexedBits

pub struct IndexedBits<T: Deref<Target = [u8]>> { /* private fields */ }

Bits stored with extra index data for fast rank and select.

Implementations

impl<T: Deref<Target = [u8]>> IndexedBits<T>

pub fn build_index(bits: Bits<T>) -> Self

Build the index for a sequence of bits.

This is an expensive operation which will examine all of the data input.

pub fn bits(&self) -> Bits<&[u8]>

pub fn decompose(self) -> Bits<T>

Discard the index and get the original bit sequence storage back.

pub fn count_ones(&self) -> u64

Count the set bits (fast O(1)).

pub fn count_zeros(&self) -> u64

Count the unset bits (fast O(1)).

pub fn rank_ones(&self, idx: u64) -> Option<u64>

Count the set bits before a position in the bits (O(1)).

Returns None it the index is out of bounds.

pub fn rank_zeros(&self, idx: u64) -> Option<u64>

Count the unset bits before a position in the bits (O(1)).

Returns None it the index is out of bounds.

pub fn select_ones(&self, target_rank: u64) -> Option<u64>

Find the position of a set bit by its rank (O(log n)).

Returns None if no suitable bit is found. It is always the case otherwise that rank_ones(result) == Some(target_rank) and get(result) == Some(true).

pub fn select_zeros(&self, target_rank: u64) -> Option<u64>

Find the position of an unset bit by its rank (O(log n)).

Returns None if no suitable bit is found. It is always the case otherwise that rank_zeros(result) == Some(target_rank) and get(result) == Some(false).

Trait Implementations

impl<T: Clone + Deref<Target = [u8]>> Clone for IndexedBits<T>

fn clone(&self) -> IndexedBits<T>

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<T: Debug + Deref<Target = [u8]>> Debug for IndexedBits<T>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.