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.

Example

See the example for 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.

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.

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.

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.

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 get_bits(&self, pos: usize, len: usize) -> Option<u64>

Return multiple bits at the given position. The number of bits to return is given by len. At most 64 bits can be returned. If the position at the end of the query is larger than the length of the vector, None is returned (even if the query partially overlaps with the vector). If the length of the query is larger than 64, None is returned.

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

Return multiple bits at the given position. The number of bits to return is given by len. At most 64 bits can be returned.

This function is always inlined, because it gains a lot from loop optimization and can utilize the processor pre-fetcher better if it is.

Errors

If the length of the query is larger than 64, unpredictable data will be returned. Use get_bits to properly handle this case with an Option.

Panics

If the position or interval is larger than the length of the vector, the function will either return unpredictable data, or panic.

pub fn iter0(&self) -> SelectIter<'_, true>

Get an iterator over the 0-bits in the vector that uses the select data structure to speed up iteration. It is faster than calling select0 on each rank, because the iterator exploits the linear access pattern.

See SelectIter for more information.

pub fn iter1(&self) -> SelectIter<'_, false>

Get an iterator over the 1-bits in the vector that uses the select data structure to speed up iteration. It is faster than calling select1 on each rank, because the iterator exploits the linear access pattern.

See SelectIter for more information.

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

impl RsVec

pub fn iter(&self) -> RsVecRefIter<'_>

Returns an iterator over the elements of RsVec.

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.

impl<'de> Deserialize<'de> for RsVec

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

where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl<'a> IntoIterator for &'a RsVec

type Item = u64

The type of the elements being iterated over.

type IntoIter = RsVecRefIter<'a>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<'a> IntoIterator for &'a mut RsVec

type Item = u64

The type of the elements being iterated over.

type IntoIter = RsVecRefIter<'a>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl IntoIterator for RsVec

type Item = u64

The type of the elements being iterated over.

type IntoIter = RsVecIter

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl Serialize for RsVec

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

where __S: Serializer,

Serialize this value into the given Serde serializer.