Struct fid::bit_vector::BitVector [−][src]
pub struct BitVector { /* fields omitted */ }
A succinct bit vector that supports FID operations (rank and select) in constant time.
Bits are divided in small and large blocks. Each small block is identified by a class (number of 1s in the block) and an index within the class. Classes are stored in ceil(log(SBLOCK_WIDTH + 1)) bits. Indices are stored in log(C(SBLOCK_WIDTH, index)) bits with enumerative code if its compressed size is less than MAX_CODE_SIZE. Otherwise the bit pattern of the small block is explicitly stored as an index for the sake of efficiency. This idea originally comes from [2]. For each large block, we store the number of 1s up to its beginning and a pointer for the index of the first small block.
Examples
use fid::{BitVector, FID}; let mut bv = BitVector::new(); bv.push(false); bv.push(true); bv.push(true); bv.push(false); bv.push(true); bv.push(true); bv.push(false); bv.push(true); assert_eq!(bv.rank0(5), 2); assert_eq!(bv.rank1(5), 3); assert_eq!(bv.select0(2), 6); assert_eq!(bv.select1(2), 4);
References
[1] Gonzalo Navarro and Eliana Providel. 2012. Fast, small, simple rank/select on bitmaps. In Proceedings of the 11th international conference on Experimental Algorithms (SEA'12), Ralf Klasing (Ed.). Springer-Verlag, Berlin, Heidelberg, 295-306. DOI=http://dx.doi.org/10.1007/978-3-642-30850-5_26
[2] rsdic by Daisuke Okanohara. https://github.com/hillbig/rsdic
Methods
impl BitVector
[src]
impl BitVector
pub fn new() -> Self
[src]
pub fn new() -> Self
pub fn push(&mut self, b: bool)
[src]
pub fn push(&mut self, b: bool)
Appends a bit at the end of the vector.
Trait Implementations
impl Debug for BitVector
[src]
impl Debug for BitVector
fn fmt(&self, f: &mut Formatter) -> Result
[src]
fn fmt(&self, f: &mut Formatter) -> Result
Formats the value using the given formatter. Read more
impl FID for BitVector
[src]
impl FID for BitVector
fn len(&self) -> u64
[src]
fn len(&self) -> u64
Returns the total number of bits.
fn rank1(&self, i: u64) -> u64
[src]
fn rank1(&self, i: u64) -> u64
Compute the number of 0s in [0..i).
fn select1(&self, r: u64) -> u64
[src]
fn select1(&self, r: u64) -> u64
Locate the position of the (r + 1)-th 1.
fn select0(&self, r: u64) -> u64
[src]
fn select0(&self, r: u64) -> u64
Locate the position of the (r + 1)-th 0.
fn rank(&self, b: bool, i: u64) -> u64
[src]
fn rank(&self, b: bool, i: u64) -> u64
Compute the number of bits in [0..i).
fn rank0(&self, i: u64) -> u64
[src]
fn rank0(&self, i: u64) -> u64
Compute the number of 0s in [0..i).
fn select(&self, b: bool, r: u64) -> u64
[src]
fn select(&self, b: bool, r: u64) -> u64
Locate the position of the (r + 1)-th bit.