Struct sdsl::RrrVector

pub struct RrrVector<BlockStore, const BLOCK_SIZE: u16, const RANK_STORE_FREQ: u16> where
    BlockStore: Code,  { /* fields omitted */ }

$ H_0 $-compressed bit vector representation.

Arguments

• BlockStore - A random access integer vector or wavelet tree used to store the block types.
• BLOCK_SIZE - Size of a basic block.
• RANK_STORE_FREQ - A rank sample value is stored before every t_k-th basic block.

References

• Rasmus Pagh Low redundancy in dictionaries with O(1) worst case lookup time Technical Report 1998. ftp://ftp.cs.au.dk/BRICS/Reports/RS/98/28/BRICS-RS-98-28.pdf, Section 2.
• Rajeev Raman, V. Raman and S. Srinivasa Rao Succinct Indexable Dictionaries with Applications to representations of k-ary trees and multi-sets. SODA 2002.
• Francisco Claude, Gonzalo Navarro: Practical Rank/Select Queries over Arbitrary Sequences. SPIRE 2008: 176-187
• On the fly-decoding and encoding was discovered in; Gonzalo Navarro, Eliana Providel: Fast, Small, Simple Rank/Select on Bitmaps. SEA 2012

Example

let bv = sdsl::bit_vector! {1, 1, 0, 1};
let rv = sdsl::RrrVector::<sdsl::IntVector<0>, 10, 2>::new(&bv)?;

let result = rv.get_int(1, 3);
let expected = 5;
assert_eq!(result, expected);

For further examples see here.

Implementations

impl<BlockStore, const BLOCK_SIZE: u16, const RANK_STORE_FREQ: u16> RrrVector<BlockStore, BLOCK_SIZE, RANK_STORE_FREQ> where
    BlockStore: Code, 

pub fn new(bit_vector: &BitVector) -> Result<Self>

Construct a new $ H_0 $-compressed bit vector.

Arguments

• bit_vector - Uncompressed bit vector.

pub fn from_file(path: &PathBuf) -> Result<Self>

Load vector from file.

Arguments

• path - File path.

pub fn len(&self) -> usize

Returns the length of the original bit vector.

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

Get the i-th element of the original bit vector.

Arguments

• index - An index in range $ [0, \mathrm{len}()) $.

pub fn get_int(&self, index: usize, len: u8) -> usize

Get the integer value of the binary string of length len starting at position index.

Arguments

• index - Starting index of the binary representation of the integer. $ \mathrm{index} + \mathrm{len} -1 \in [0..\mathrm{size}()-1] $
• len - Length of the binary representation of the integer. $ \mathrm{len} \in [1..64] $

pub fn iter_bv(&self) -> VectorIterator<'_, Self>

Returns an iterator over the original bit vector values.

pub fn iter_int(&self, len: u8) -> RrrVectorIntIterator<'_, Self>

Returns an iterator over integer values of the binary string.

Arguments

• len - Length of the binary representation of the integer. $ \mathrm{len} \in [1..64] $

Trait Implementations

impl<BlockStore, const BLOCK_SIZE: u16, const RANK_STORE_FREQ: u16> Clone for RrrVector<BlockStore, BLOCK_SIZE, RANK_STORE_FREQ> where
    BlockStore: Code, 

fn clone(&self) -> Self

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<BlockStore, const BLOCK_SIZE: u16, const RANK_STORE_FREQ: u16> Drop for RrrVector<BlockStore, BLOCK_SIZE, RANK_STORE_FREQ> where
    BlockStore: Code, 

fn drop(&mut self)

Executes the destructor for this type.

impl<BlockStore, const BLOCK_SIZE: u16, const RANK_STORE_FREQ: u16> IO for RrrVector<BlockStore, BLOCK_SIZE, RANK_STORE_FREQ> where
    BlockStore: Code, 

fn io(&self) -> &Interface