Struct RankSelect 

pub struct RankSelect<CC = Vec<u64>, VC = Vec<u64>, WC = [u64; 2]> {
    pub counts: CC,
    pub values: Bools<VC, WC>,
}

A store for maintaining Vec<bool> with fast rank and select access.

The design is to have u64 running counts for each block of 1024 bits, which are roughly the size of a cache line. This is roughly 6% overhead, above the bits themselves, which seems pretty solid.

Fields

counts: CC

Counts of the number of cumulative set (true) bits, after each block of 1024 bits.

values: Bools<VC, WC>

The bits themselves.

Implementations

impl<CC: BorrowIndexAs<u64>, VC: BorrowIndexAs<u64>> RankSelect<CC, VC>

pub fn borrow<'a>( &'a self, ) -> RankSelect<CC::Borrowed<'a>, VC::Borrowed<'a>, &'a [u64]>

pub fn reborrow<'b, 'a: 'b>( thing: RankSelect<CC::Borrowed<'a>, VC::Borrowed<'a>, &'a [u64]>, ) -> RankSelect<CC::Borrowed<'b>, VC::Borrowed<'b>, &'b [u64]>

impl<CC, VC: Len + IndexAs<u64>, WC: IndexAs<u64>> RankSelect<CC, VC, WC>

pub fn get(&self, index: usize) -> bool

impl<CC: Len + IndexAs<u64>, VC: Len + IndexAs<u64>, WC: IndexAs<u64>> RankSelect<CC, VC, WC>

pub fn rank(&self, index: usize) -> usize

The number of set bits strictly preceding index.

This number is accumulated first by reading out of self.counts at the correct position, then by summing the ones in strictly prior u64 entries, then by counting the ones in the masked u64 in which the bit lives.

pub fn select(&self, rank: u64) -> Option<usize>

The position of the rank-th set bit (0-indexed), if it exists.

select(0) returns the position of the first set bit. In general, select(rank(p)) == p when p is the position of a set bit, mirroring the convention of Self::rank (which counts bits strictly before its argument).

impl<CC: Len + IndexAs<u64>, VC: Len + IndexAs<u64>, WC: IndexAs<u64>> RankSelect<CC, VC, WC>

pub fn cursor(&self) -> Cursor<'_, CC, VC, WC>

Create a forward cursor positioned at bit 0.

impl<CC, VC: Len, WC: IndexAs<u64>> RankSelect<CC, VC, WC>

pub fn len(&self) -> usize

impl<CC: for<'a> Push<&'a u64> + Len + IndexAs<u64>, VC: for<'a> Push<&'a u64> + Len + IndexAs<u64>> RankSelect<CC, VC>

pub fn push(&mut self, bit: bool)

Trait Implementations

impl<'a, CC: AsBytes<'a>, VC: AsBytes<'a>> AsBytes<'a> for RankSelect<CC, VC, &'a [u64]>

const SLICE_COUNT: usize

The number of byte slices this type produces.

fn get_byte_slice(&self, index: usize) -> (u64, &'a [u8])

Returns the index-th byte slice (alignment, data) by random access.

fn as_bytes(&self) -> impl Iterator<Item = (u64, &'a [u8])>

Presents self as a sequence of byte slices, with their required alignment.

impl<CC: Clear, VC: Clear> Clear for RankSelect<CC, VC>

fn clear(&mut self)

Clears self, without changing its capacity.

impl<CC: Clone, VC: Clone, WC: Clone> Clone for RankSelect<CC, VC, WC>

fn clone(&self) -> RankSelect<CC, VC, WC>

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<CC: Debug, VC: Debug, WC: Debug> Debug for RankSelect<CC, VC, WC>

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

Formats the value using the given formatter.

impl<CC: Default, VC: Default, WC: Default> Default for RankSelect<CC, VC, WC>

fn default() -> RankSelect<CC, VC, WC>

Returns the “default value” for a type.

impl<'a, CC: FromBytes<'a>, VC: FromBytes<'a>> FromBytes<'a> for RankSelect<CC, VC, &'a [u64]>

const SLICE_COUNT: usize

The number of byte slices this type consumes when reconstructed.

fn from_bytes(bytes: &mut impl Iterator<Item = &'a [u8]>) -> Self

Reconstructs self from a sequence of correctly aligned and sized bytes slices.

fn from_store(store: &DecodedStore<'a>, offset: &mut usize) -> Self

Reconstructs self from a DecodedStore, using direct random access at a given offset.

fn element_sizes(sizes: &mut Vec<usize>) -> Result<(), String>

Reports the element sizes (in bytes) for each slice this type consumes.

fn validate(slices: &[(&[u64], u8)]) -> Result<(), String>

where Self: Sized,

Validates that the given slices are compatible with this type.

impl<CC: PartialEq, VC: PartialEq, WC: PartialEq> PartialEq for RankSelect<CC, VC, WC>

fn eq(&self, other: &RankSelect<CC, VC, WC>) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<CC: Copy, VC: Copy, WC: Copy> Copy for RankSelect<CC, VC, WC>

impl<CC, VC, WC> StructuralPartialEq for RankSelect<CC, VC, WC>