Struct bitm::CombinedSampling

pub struct CombinedSampling<D: CombinedSamplingDensity = AdaptiveCombinedSamplingDensity> { /* private fields */ }

Fast select strategy for RankSelect101111 with about 0.39% space overhead.

Space/speed trade-off can be adjusted by the template parameter, by giving one of:

• AdaptiveCombinedSamplingDensity (default) – works well with a wide range of bit vectors,
• ConstCombinedSamplingDensity – recommended for vectors with a known ratio of set/unset bits; with default parameters, recommended for vectors filled with bit ones in about half.

The implementation generally follows 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 However, our implementation can automatically adjust the sampling density according to the content of the vector (see AdaptiveCombinedSamplingDensity).

Combined Sampling was proposed in:

• G. Navarro, E. Providel, “Fast, small, simple rank/select on bitmaps”, in: R. Klasing (Ed.), Experimental Algorithms, Springer Berlin Heidelberg, Berlin, Heidelberg, 2012, pp. 295–306

Trait Implementations

impl<D: Clone + CombinedSamplingDensity> Clone for CombinedSampling<D>

where D::SamplingDensity: Clone,

fn clone(&self) -> CombinedSampling<D>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<D: CombinedSamplingDensity> GetSize for CombinedSampling<D>

where D::SamplingDensity: GetSize,

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).

const USES_DYN_MEM: bool = true

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

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<D: CombinedSamplingDensity> Select0ForRank101111 for CombinedSampling<D>

fn new0( content: &[u64], l1ranks: &[usize], _l2ranks: &[u64], total_rank: usize ) -> Self

fn select0( &self, content: &[u64], l1ranks: &[usize], l2ranks: &[u64], rank: usize ) -> Option<usize>

unsafe fn select0_unchecked( &self, content: &[u64], l1ranks: &[usize], l2ranks: &[u64], rank: usize ) -> usize

impl<D: CombinedSamplingDensity> SelectForRank101111 for CombinedSampling<D>

fn new( content: &[u64], l1ranks: &[usize], _l2ranks: &[u64], total_rank: usize ) -> Self

fn select( &self, content: &[u64], l1ranks: &[usize], l2ranks: &[u64], rank: usize ) -> Option<usize>

unsafe fn select_unchecked( &self, content: &[u64], l1ranks: &[usize], l2ranks: &[u64], rank: usize ) -> usize