# [−][src]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 |