Struct columnar::sums::rank_select::RankSelect

pub struct RankSelect<CC = Vec<u64>, VC = Vec<u64>, WC = u64> {
    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: Container<u64>, VC: Container<u64>> RankSelect<CC, VC>

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

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

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

impl<CC: Len + IndexAs<u64>, VC: Len + IndexAs<u64>, WC: Copy + CopyAs<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 index of the rankth set bit, should one exist.

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

pub fn len(&self) -> usize

impl<CC: Push<u64> + Len + IndexAs<u64>, VC: Push<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>

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

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

fn length_in_words(&self) -> usize

The number of u64 words required to record self as aligned bytes.

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 copy 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<'de, CC, VC, WC> Deserialize<'de> for RankSelect<CC, VC, WC>

where CC: Deserialize<'de>, VC: Deserialize<'de>, WC: Deserialize<'de>,

fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error>

where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

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

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

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

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

fn heap_size(&self) -> (usize, usize)

Active (len) and allocated (cap) heap sizes in bytes. This should not include the size of self itself.

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, VC, WC> Serialize for RankSelect<CC, VC, WC>

where CC: Serialize, VC: Serialize, WC: Serialize,

fn serialize<__S>(&self, __serializer: __S) -> Result<__S::Ok, __S::Error>

where __S: Serializer,

Serialize this value into the given Serde serializer.

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

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