[−][src]Struct fid::BitVector
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]
pub fn new() -> Self
[src]
pub fn push(&mut self, b: bool)
[src]
Appends a bit at the end of the vector.
pub fn size(&self) -> usize
[src]
Returns the total size of the bit vector.
Trait Implementations
impl FID for BitVector
[src]
fn len(&self) -> u64
[src]
fn get(&self, i: u64) -> bool
[src]
fn rank1(&self, i: u64) -> u64
[src]
fn select1(&self, r: u64) -> u64
[src]
fn select0(&self, r: u64) -> u64
[src]
fn rank(&self, b: bool, i: u64) -> u64
[src]
Compute the number of bits in [0..i).
fn rank0(&self, i: u64) -> u64
[src]
Compute the number of 0s in [0..i).
fn select(&self, b: bool, r: u64) -> u64
[src]
Locate the position of the (r + 1)-th bit.
impl Debug for BitVector
[src]
impl Serialize for BitVector
[src]
fn serialize<__S>(&self, __serializer: __S) -> Result<__S::Ok, __S::Error> where
__S: Serializer,
[src]
__S: Serializer,
impl<'de> Deserialize<'de> for BitVector
[src]
fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error> where
__D: Deserializer<'de>,
[src]
__D: Deserializer<'de>,
Auto Trait Implementations
Blanket Implementations
impl<T, U> Into<U> for T where
U: From<T>,
[src]
U: From<T>,
impl<T> From<T> for T
[src]
impl<T, U> TryFrom<U> for T where
U: Into<T>,
[src]
U: Into<T>,
type Error = Infallible
The type returned in the event of a conversion error.
fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>
[src]
impl<T, U> TryInto<U> for T where
U: TryFrom<T>,
[src]
U: TryFrom<T>,
type Error = <U as TryFrom<T>>::Error
The type returned in the event of a conversion error.
fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>
[src]
impl<T> Borrow<T> for T where
T: ?Sized,
[src]
T: ?Sized,
impl<T> BorrowMut<T> for T where
T: ?Sized,
[src]
T: ?Sized,
fn borrow_mut(&mut self) -> &mut T
[src]
impl<T> Any for T where
T: 'static + ?Sized,
[src]
T: 'static + ?Sized,
impl<T> DeserializeOwned for T where
T: Deserialize<'de>,
[src]
T: Deserialize<'de>,