Struct RankBitBox 

pub struct RankBitBox { /* private fields */ }

A boxed bit slice that supports a constant-time rank operation.

This can be used to “shrink” a large vector, where you only need to keep certain elements, and you want to continue to use the index in the large vector to identify each element.

First you create a new smaller vector, keeping only the elements of the large vector that you care about. Now you need a way to translate an index into the large vector (which no longer exists) into the corresponding index into the smaller vector. To do that, you create a bit slice, containing a bit for every element of the original large vector. Each bit in the bit slice indicates whether that element of the large vector was kept in the smaller vector. And the rank of the bit gives us the index of the element in the smaller vector.

However, the naive implementation of rank is O(n) in the size of the bit slice. To address that, we use a standard trick: we divide the bit slice into 64-bit chunks, and when constructing the bit slice, precalculate the rank of the first bit in each chunk. Then, to calculate the rank of an arbitrary bit, we first grab the precalculated rank of the chunk that bit belongs to, and add the rank of the bit within its (fixed-sized) chunk.

This trick adds O(1.5) bits of overhead per large vector element on 64-bit platforms, and O(2) bits of overhead on 32-bit platforms.

Implementations

impl RankBitBox

pub fn bits_with_capacity(cap: usize) -> RankBitBoxVec

pub fn from_bits(bits: RankBitBoxVec) -> Self

pub fn len(&self) -> usize

pub fn is_empty(&self) -> bool

pub fn get_bit(&self, index: usize) -> Option<bool>

pub fn iter_ones(&self) -> impl DoubleEndedIterator<Item = usize> + '_

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

Returns the number of bits before (and not including) the given index that are set.

Trait Implementations

impl Clone for RankBitBox

fn clone(&self) -> RankBitBox

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl Debug for RankBitBox

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

Formats the value using the given formatter.

impl Eq for RankBitBox

impl GetSize for RankBitBox

fn get_heap_size(&self) -> usize

Determines how many bytes this object occupies inside the heap.

fn get_heap_size_with_tracker<TRACKER: GetSizeTracker>( &self, tracker: TRACKER, ) -> (usize, TRACKER)

Determines how many bytes this object occupies inside the heap while using a tracker.

fn get_stack_size() -> usize

Determines how may bytes this object occupies inside the stack.

fn get_size(&self) -> usize

Determines the total size of the object.

fn get_size_with_tracker<T>(&self, tracker: T) -> (usize, T)

where T: GetSizeTracker,

Determines the total size of the object while using a tracker.

impl Hash for RankBitBox

fn hash<__H: Hasher>(&self, state: &mut __H)

Feeds this value into the given Hasher.

fn hash_slice<H>(data: &[Self], state: &mut H)

where H: Hasher, Self: Sized,

Feeds a slice of this type into the given Hasher.

impl PartialEq for RankBitBox

fn eq(&self, other: &RankBitBox) -> bool

Equality operator ==.

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

Inequality operator !=.

impl StructuralPartialEq for RankBitBox