Struct vers_vecs::bit_vec::fast_rs_vec::RsVec

pub struct RsVec { /* private fields */ }

A bitvector that supports constant-time rank and select queries and is optimized for fast queries. The bitvector is stored as a vector of u64s. The bit-vector stores meta-data for constant-time rank and select queries, which takes sub-linear additional space. The space overhead is 28 bits per 512 bits of user data (~5.47%).

Example

use vers_vecs::{BitVec, RsVec};

let mut bit_vec = BitVec::new();
bit_vec.append_word(u64::MAX);

let rs_vec = RsVec::from_bit_vec(bit_vec);
assert_eq!(rs_vec.rank1(64), 64);
assert_eq!(rs_vec.select1(64), 64);

Implementations

impl RsVec

pub fn from_bit_vec(vec: BitVec) -> RsVec

Build an RsVec from a BitVec. This will consume the BitVec. Since RsVecs are immutable, this is the only way to construct an RsVec.

pub fn rank0(&self, pos: usize) -> usize

Return the 0-rank of the bit at the given position. The 0-rank is the number of 0-bits in the vector up to but excluding the bit at the given position. Calling this function with an index larger than the length of the bit-vector will report the total number of 0-bits in the bit-vector.

Parameters

• pos: The position of the bit to return the rank of.

Compatibility

This function forcibly enables the popcnt x86 CPU feature.

pub fn rank1(&self, pos: usize) -> usize

Return the 1-rank of the bit at the given position. The 1-rank is the number of 1-bits in the vector up to but excluding the bit at the given position. Calling this function with an index larger than the length of the bit-vector will report the total number of 1-bits in the bit-vector.

Parameters

• pos: The position of the bit to return the rank of.

Compatibility

This function forcibly enables the popcnt x86 CPU feature.

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

Return the position of the 0-bit with the given rank. See rank0. The following holds: select0(rank0(pos)) == pos

If the rank is larger than the number of 0-bits in the vector, the vector length is returned.

Compatibility

This function forcibly enables the bmi2 x86 CPU feature. If this feature is not available on the CPU, this function will not work.

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

Return the position of the 1-bit with the given rank. See rank1. The following holds: select1(rank1(pos)) == pos

If the rank is larger than the number of 1-bits in the bit-vector, the vector length is returned.

Compatibility

This function forcibly enables the bmi2 x86 CPU feature. If this feature is not available on the CPU, this function will not work.

pub fn len(&self) -> usize

Return the length of the vector, i.e. the number of bits it contains.

pub fn is_empty(&self) -> bool

Return whether the vector is empty.

pub fn get(&self, pos: usize) -> Option<u64>

Return the bit at the given position. The bit takes the least significant bit of the returned u64 word. If the position is larger than the length of the vector, None is returned.

pub fn get_unchecked(&self, pos: usize) -> u64

Return the bit at the given position. The bit takes the least significant bit of the returned u64 word.

Panics

This function may panic if pos >= self.len() (alternatively, it may return garbage).

pub fn heap_size(&self) -> usize

Returns the number of bytes used on the heap for this vector. This does not include allocated space that is not used (e.g. by the allocation behavior of Vec).

Trait Implementations

impl Clone for RsVec

fn clone(&self) -> RsVec

Returns a copy of the value.

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

Performs copy-assignment from source.

impl Debug for RsVec

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

Formats the value using the given formatter.