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 update README.md but edit src/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