Crate 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>()](https://laysakura.github.io/fid-rs/fid_rs/fid/struct.Fid.html#implementations)	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).

Re-exports

pub use fid::Fid;

Modules

fid