3 unstable releases
0.2.0 | Apr 14, 2024 |
---|---|
0.1.1 | Apr 25, 2019 |
0.1.0 | Apr 25, 2019 |
#55 in Compression
134,283 downloads per month
Used in 41 crates
(via louds-rs)
71KB
1.5K
SLoC
fid-rs
High performance FID (Fully Indexable Dictionary) library.
Master API Docs | Released API Docs | Benchmark Results | Changelog
Quickstart
To use fid-rs, add the following to your Cargo.toml
file:
[dependencies]
fid-rs = "0.1" # NOTE: Replace to latest minor version.
Usage Overview
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's
Constructors
use 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[..]);
Iterator
use fid_rs::Fid;
let fid = Fid::from("0100_1");
for bit in fid.iter() {
println!("{}", bit);
}
// =>
// false
// true
// false
// false
// true
Utility Methods
use fid_rs::Fid;
let fid = Fid::from("0100_1");
assert_eq!(fid.len(), 5);
Features
- 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.
Complexity
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).
Versions
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).
Rust Version Supports
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.
Contributing
Any kind of pull requests are appreciated.
Guidelines
README.md
is generated from$ cargo readme
command. Do not manually updateREADME.md
but editsrc/lib.rs
and then$ cargo readme > README.md
.- Travis CI automatically does the following commit & push to your pull-requests:
$ cargo readme > README.md
$ cargo fmt --all
License
MIT OR Apache-2.0
Dependencies
~1–30MB
~388K SLoC