1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

//! FID (Fully Indexable Dictionary) implementation for Rust
//! 
//! This crate provides a succinct bit vector that supports two kinds of bit operations in constant-time:
//! 
//! - `rank(i)` computes the number of 0s (or 1s) in [0..i)
//! - `select(r)` locates the (r+1)-th position of 0 (or 1).
//! 
//! Structures supporting these two operations are called FID (fully indexable dictionary).
//! 
//! # Basic usage
//! 
//! ```
//! use fid::{BitVector, FID};
//! 
//! let mut bv = BitVector::new();
//! // 01101101
//! 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);
//! ```
//! 
//! # About implementation
//! 
//! Compression and computation algorithms for `BitVector` are originally from [1] and its practical implementation ideas are from [2].
//! 
//! [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](https://github.com/hillbig/rsdic)

pub mod bit_vector;
pub mod bit_array;
pub mod fid;

pub use bit_array::BitArray;
pub use bit_vector::BitVector;
pub use fid::FID;