Struct SparseRSVec 

pub struct SparseRSVec { /* private fields */ }

A succinct representation of a sparse vector with rank and select support. It is a thin wrapper around an EliasFanoVec that compresses the indices of 1-bits.

Therefore, no select0 function is provided. However, the constructor from_bitvec_inverted can be used to cheaply invert the input BitVec, reversing the roles of 1-bits and 0-bits.

Examples

use vers_vecs::SparseRSVec;

let sparse = SparseRSVec::new(&[1, 3, 5, 7, 9], 12);
assert_eq!(sparse.get(5), Some(1));
assert_eq!(sparse.get(11), Some(0));
assert_eq!(sparse.get(12), None);

assert_eq!(sparse.rank1(5), 2);
assert_eq!(sparse.select1(2), 5);

It cn also be constructed from a BitVec directly:

use vers_vecs::SparseRSVec;
use vers_vecs::BitVec;

let mut bv = BitVec::from_zeros(12);
bv.flip_bit(6);
bv.flip_bit(7);

let sparse = SparseRSVec::from_bitvec(&bv);
assert_eq!(sparse.rank1(5), 0);
assert_eq!(sparse.select1(0), 6);

Implementations

impl SparseRSVec

pub fn new(input: &[u64], len: u64) -> Self

Creates a new SparseRSVec from a sequence of set bits represented as indices. The input must be sorted in ascending order and free of duplicates.

The length of the vector must be passed as well, as it cannot be inferred from the input, if the last bit in the vector is not set.

Parameters

• input: The positions of set bits, or unset bits if the sparse vector should compress zeros.
• len: The length of the vector, which is needed if the last bit is not in the input slice.

pub fn from_bitvec(input: &BitVec) -> Self

Creates a new SparseRSVec from a BitVec, by compressing the sparse 1-bits.

Parameters

• input: The input BitVec to compress.

pub fn from_bitvec_inverted(input: &BitVec) -> Self

Creates a new SparseRSVec from a BitVec. However, before compressing the 1-bits, the input is inverted. This means that the sparse vector will compress the 0-bits instead of the 1-bits, and the rank1 and select1 functions will return the number of 0-bits and the position of 0-bits.

This is a convenience function to allow for easy creation of sparse vectors that compress zeros, despite the lack of a select0 function.

However, do note that get will return the inverted value of the bit at position i from the original BitVec.

Parameters

• input: The input BitVec to compress.

Example

use vers_vecs::SparseRSVec;
use vers_vecs::BitVec;

let mut bv = BitVec::from_ones(12);
// set 6 and 7 to 0
bv.flip_bit(6);
bv.flip_bit(7);

let sparse = SparseRSVec::from_bitvec_inverted(&bv);
// now select1 gives the position of 0-bits
assert_eq!(sparse.select1(1), 7);

pub fn is_set_unchecked(&self, i: u64) -> bool

Returns true if the bit at position i is set.

If i is out of bounds the function produces incorrect results. Use is_set for a checked version.

pub fn is_set(&self, i: u64) -> Option<bool>

Returns true if the bit at position i is set.

Returns None if i is out of bounds.

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

Gets the bit at position i. Returns 1 if the bit is set, 0 if it is not set.

Panics

If i is out of bounds the function might panic or produce incorrect results. Use get for a checked version.

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

Gets the bit at position i. Returns Some(1) if the bit is set, Some(0) if it is not set, and None if i is out of bounds.

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

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

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

pub fn rank1(&self, i: u64) -> u64

Returns the number of 1-bits in the vector up to position i.

If i is out of bounds, the number of 1-bits in the vector is returned.

pub fn rank0(&self, i: u64) -> u64

Returns the number of 0-bits in the vector up to position i.

If i is out of bounds, the number of 0-bits in the vector is returned.

pub fn iter1(&self) -> impl Iterator<Item = u64> + '_

Returns an iterator over the 1-bits in the vector. The iterator yields the positions of the 1-bits in ascending order.

pub fn len(&self) -> u64

Returns the length of the bit vector if it was uncompressed.

pub fn is_empty(&self) -> bool

Returns true if the vector is empty.

pub fn heap_size(&self) -> usize

Returns the number of bytes used by the vector on the heap. Does not include allocated memory that isn’t used.

Trait Implementations

impl Clone for SparseRSVec

fn clone(&self) -> SparseRSVec

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl Debug for SparseRSVec

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

Formats the value using the given formatter.

impl<'de> Deserialize<'de> for SparseRSVec

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

where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl FlatType for SparseRSVec

where EliasFanoVec: MemSize + FlatType, u64: MemSize + FlatType,

type Flat = False

impl<'a> From<&'a BitVec> for SparseRSVec

fn from(input: &'a BitVec) -> Self

Converts to this type from the input type.

impl From<BitVec> for SparseRSVec

fn from(input: BitVec) -> Self

Converts to this type from the input type.

impl MemDbgImpl for SparseRSVec

where EliasFanoVec: MemDbgImpl + FlatType, u64: MemDbgImpl + FlatType,

fn _mem_dbg_rec_on( &self, _memdbg_writer: &mut impl Write, _memdbg_total_size: usize, _memdbg_max_depth: usize, _memdbg_prefix: &mut String, _memdbg_is_last: bool, _memdbg_flags: DbgFlags, _memdbg_refs: &mut HashSet<usize>, ) -> Result

fn _mem_dbg_depth_on( &self, writer: &mut impl Write, total_size: usize, max_depth: usize, prefix: &mut String, field_name: Option<&str>, is_last: bool, padded_size: usize, flags: DbgFlags, dbg_refs: &mut HashSet<usize>, ) -> Result<(), Error>

fn _mem_dbg_depth_on_impl( &self, writer: &mut impl Write, total_size: usize, max_depth: usize, prefix: &mut String, field_name: Option<&str>, is_last: bool, padded_size: usize, flags: DbgFlags, dbg_refs: &mut HashSet<usize>, ref_display: RefDisplay, ) -> Result<(), Error>

Internal implementation for depth display.

impl MemSize for SparseRSVec

where EliasFanoVec: MemSize + FlatType, u64: MemSize + FlatType,

fn mem_size_rec( &self, _memsize_flags: SizeFlags, _memsize_refs: &mut HashMap<usize, usize>, ) -> usize

Recursive implementation that tracks visited references for deduplication.

fn mem_size(&self, flags: SizeFlags) -> usize

Returns the (recursively computed) overall memory size of the structure in bytes.

impl Serialize for SparseRSVec

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

where __S: Serializer,

Serialize this value into the given Serde serializer.