Struct RankSelect101111 

pub struct RankSelect101111<Select = BinaryRankSearch, Select0 = BinaryRankSearch, BV = Box<[u64]>> {
    pub content: BV,
    pub l1ranks: Box<[usize]>,
    pub l2ranks: Box<[u64]>,
    /* private fields */
}

Returns number of bits set (to one) in content whose length does not exceeds 8. Returns number of bits set (to one) in content whose length does not exceeds 8. The structure that holds bit vector content and ranks structure that takes no more than 3.125% extra space. It can return the number of ones (or zeros) in first index bits of the content (see rank and rank0 method) in O(1) time. In addition, it supports select queries utilizing binary search over ranks (see BinaryRankSearch) or (optionally, at the cost of extra space overhead; about 0.39% with default settings) combined sampling (which is usually faster; see CombinedSampling).

Any type that implements the Deref trait with Target = [u64] can be used as a bit vector. It is recommended to use this structure with bit vectors allocated with alignment to the CPU cache line or 64 bytes. Such a vector can be constructed, for example, by compiling bitm with the aligned-vec feature and using implementation of crate::BitVec trait for aligned_vec::ABox<[u64]>, for example: ABox::with_zeroed_bits(number_of_bits).

The structure supports vectors up to 2⁶⁴ bits and its design is based on a 3-level (compact due to relative addressing) index that samples rank responses every 512 bits and is CPU cache friendly as the first level is small (each its entry covers 2³² bits) and the other two are interleaved.

It uses modified version of the structure described in the paper:

• Zhou D., Andersen D.G., Kaminsky M. (2013) “Space-Efficient, High-Performance Rank and Select Structures on Uncompressed Bit Sequences”. In: Bonifaci V., Demetrescu C., Marchetti-Spaccamela A. (eds) Experimental Algorithms. SEA 2013. Lecture Notes in Computer Science, vol 7933. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-38527-8_15

The modification consists of different level 2 entries that hold 4 rank values (r0 <= r1 <= r2 <= r3) relative to level 1 entry. The content of level 2 entry, listing from the least significant bits, is:

• original: r0 stored on 32 bits, r1-r0 on 10 bits, r2-r1 on 10 bits, r3-r2 on 10 bits;
• our: r0 stored on 32 bits, r3-r0 on 11 bits, r2-r0 on 11 bits, r1-r0 on 10 bits. With this layout, we can read the corresponding value in the rank query without branching.

Another modification that makes our implementation unique is the ability of the select support structure to adapt the sampling density to the content of the bit vector (see CombinedSampling and AdaptiveCombinedSamplingDensity).

For in-word selection, the structure uses the select64 function.

Fields

content: BV

l1ranks: Box<[usize]>

l2ranks: Box<[u64]>

Implementations

impl<S, S0, BV> RankSelect101111<S, S0, BV>

pub fn select_support(&self) -> &S

Returns reference to structure that support select (one) operation.

pub fn select0_support(&self) -> &S0

Returns reference to structure that support select zero operation.

impl<S: SelectForRank101111, S0: Select0ForRank101111, BV: Deref<Target = [u64]>> RankSelect101111<S, S0, BV>

pub fn build(content: BV) -> (Self, usize)

Trait Implementations

impl<S: SelectForRank101111, S0: Select0ForRank101111, BV: Deref<Target = [u64]>> AsRef<[u64]> for RankSelect101111<S, S0, BV>

fn as_ref(&self) -> &[u64]

Converts this type into a shared reference of the (usually inferred) input type.

impl<Select: Clone, Select0: Clone, BV: Clone> Clone for RankSelect101111<Select, Select0, BV>

fn clone(&self) -> RankSelect101111<Select, Select0, BV>

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<S: SelectForRank101111, S0: Select0ForRank101111, BV: Deref<Target = [u64]>> From<BV> for RankSelect101111<S, S0, BV>

fn from(value: BV) -> Self

Converts to this type from the input type.

impl<S: GetSize, S0: GetSize, BV: GetSize> GetSize for RankSelect101111<S, S0, BV>

const USES_DYN_MEM: bool = true

true if and only if the variables of this type can use dynamic (heap) memory.

fn size_bytes_dyn(&self) -> usize

Returns approximate number of bytes occupied by dynamic (heap) part of self. Same as self.size_bytes() - std::mem::size_of_val(self).

fn size_bytes_content_dyn(&self) -> usize

Returns approximate number of bytes occupied by dynamic (heap) part of self content. It usually equals to size_bytes_dyn(). However, sometimes it is smaller by the amount of memory reserved but not yet used (e.g., size_bytes_content_dyn() only takes into account the length of the vector and not its capacity).

fn size_bytes(&self) -> usize

Returns approximate, total (including heap memory) number of bytes occupied by self.

impl<S: SelectForRank101111, S0: Select0ForRank101111, BV: Deref<Target = [u64]>> Rank for RankSelect101111<S, S0, BV>

fn try_rank(&self, index: usize) -> Option<usize>

Returns the number of ones in first index bits or None if index is out of bounds.

unsafe fn rank_unchecked(&self, index: usize) -> usize

Returns the number of ones in first index bits. The result is undefined if index is out of bounds.

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

Returns the number of ones in first index bits or panics if index is out of bounds.

fn try_rank0(&self, index: usize) -> Option<usize>

Returns the number of zeros in first index bits or None if index is out of bounds.

fn rank0(&self, index: usize) -> usize

Returns the number of zeros in first index bits or panics if index is out of bounds.

unsafe fn rank0_unchecked(&self, index: usize) -> usize

Returns the number of ones in first index bits. The result is undefined if index is out of bounds.

impl<S: SelectForRank101111, S0, BV: Deref<Target = [u64]>> Select for RankSelect101111<S, S0, BV>

fn try_select(&self, rank: usize) -> Option<usize>

Returns the position of the rank-th one (counting from 0) in self or None if there are no such many ones in self.

unsafe fn select_unchecked(&self, rank: usize) -> usize

Returns the position of the rank-th one (counting from 0) in self. The result is undefined if there are no such many ones in self.

fn select(&self, rank: usize) -> usize

Returns the position of the rank-th one (counting from 0) in self or panics if there are no such many ones in self.

impl<S, S0: Select0ForRank101111, BV: Deref<Target = [u64]>> Select0 for RankSelect101111<S, S0, BV>

fn try_select0(&self, rank: usize) -> Option<usize>

Returns the position of the rank-th zero (counting from 0) in self or None if there are no such many zeros in self.

unsafe fn select0_unchecked(&self, rank: usize) -> usize

Returns the position of the rank-th zero (counting from 0) in self. The result is undefined if there are no such many zeros in self.

fn select0(&self, rank: usize) -> usize

Returns the position of the rank-th zero (counting from 0) in self or panics if there are no such many zeros in self.