High performance FID (Fully Indexable Dictionary) library.
Master API Docs | Released API Docs | Benchmark Results | Changelog
To use fid-rs, add the following to your Cargo.toml file:
[dependencies]
fid-rs = "0.1" # NOTE: Replace to latest minor version.use fid_rs::Fid;
let fid = Fid::from("0100_1"); // Tips: Fid::from::<&str>() ignores '_'.
// Basic operations ---------------------
assert_eq!(fid[0], false); // [0]1001; 0th bit is '0' (false)
assert_eq!(fid[1], true); // 0[1]001; 1st bit is '1' (true)
assert_eq!(fid[4], true); // 0100[1]; 4th bit is '1' (true)
assert_eq!(fid.rank(0), 0); // [0]1001; Range [0, 0] has no '1'
assert_eq!(fid.rank(3), 1); // [0100]1; Range [0, 3] has 1 '1'
assert_eq!(fid.rank(4), 2); // [01001]; Range [0, 4] has 2 '1's
assert_eq!(fid.select(0), Some(0)); // []01001; Minimum i where range [0, i] has 0 '1's is i=0
assert_eq!(fid.select(1), Some(1)); // 0[1]001; Minimum i where range [0, i] has 1 '1's is i=1
assert_eq!(fid.select(2), Some(4)); // 0100[1]; Minimum i where range [0, i] has 2 '1's is i=4
assert_eq!(fid.select(3), None); // There is no i where range [0, i] has 3 '1's
// rank0, select0 -----------------------
assert_eq!(fid.rank0(0), 1); // [0]1001; Range [0, 0] has no '0'
assert_eq!(fid.rank0(3), 3); // [0100]1; Range [0, 3] has 3 '0's
assert_eq!(fid.rank0(4), 3); // [01001]; Range [0, 4] has 3 '0's
assert_eq!(fid.select0(0), Some(0)); // []01001; Minimum i where range [0, i] has 0 '0's is i=0
assert_eq!(fid.select0(1), Some(0)); // [0]1001; Minimum i where range [0, i] has 1 '0's is i=0
assert_eq!(fid.select0(2), Some(2)); // 01[0]01; Minimum i where range [0, i] has 2 '0's is i=2
assert_eq!(fid.select0(4), None); // There is no i where range [0, i] has 4 '0'suse fid_rs::Fid;
// Most human-friendly way: Fid::from::<&str>()
let fid = Fid::from("0100_1");
// Complex construction in simple way: Fid::from::<&[bool]>()
let mut arr = [false; 5];
arr[1] = true;
arr[4] = true;
let fid = Fid::from(&arr[..]);use fid_rs::Fid;
let fid = Fid::from("0100_1");
for bit in fid.iter() {
println!("{}", bit);
}
// =>
// false
// true
// false
// false
// trueuse fid_rs::Fid;
let fid = Fid::from("0100_1");
assert_eq!(fid.len(), 5);- Arbitrary length support with minimum working memory: fid-rs provides virtually arbitrary size of FID. It is carefully designed to use as small memory space as possible.
- Parallel build of FID: Build operations (
Fid::from()) takes O(N) time. It is parallelized and achieves nearly optimal scale-out. - No memory copy while/after build operations: After internally creating bit vector representation, any operation does not do memory copy.
- Latest benchmark results are always accessible: fid-rs is continuously benchmarked in Travis CI using Criterion.rs. Graphical benchmark results are published here.
When the length of a Fid is N:
| Operation | Time-complexity | Space-complexity |
|---|---|---|
| Fid::from::<&str>() | O(N) | N + o(N) |
| Fid::from::<&[bool]>() | O(N) | N + o(N) |
| Index<u64> | O(1) | 0 |
| Fid::rank() | O(1) | O(1) |
| Fid::rank0() | O(1) | O(1) |
| Fid::select() | O(log N) | O(1) |
| Fid::select0() | O(log N) | O(1) |
(Actually, select()'s time-complexity can be O(1) with complex implementation but fid-rs, like many other libraries, uses binary search of rank()'s result).
fid-rs uses semantic versioning.
Since current major version is 0, minor version update might involve breaking public API change (although it is carefully avoided).
fid-rs is continuously tested with these Rust versions in Travis CI:
- 1.33.0
- Latest stable version
- Beta version
- Nightly build
So it expectedly works with Rust 1.33.0 and any newer versions.
Older versions may also work, but are not tested or guaranteed.
Any kind of pull requests are appreciated.
README.mdis generated from$ cargo readmecommand. Do not manually updateREADME.mdbut editsrc/lib.rsand then$ cargo readme > README.md.- Travis CI automatically does the following commit & push to your pull-requests:
$ cargo readme > README.md$ cargo fmt --all
MIT OR Apache-2.0