1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128
//! High performance FID (Fully Indexable Dictionary) library. //! //! [Master API Docs](https://laysakura.github.io/fid-rs/fid_rs/) //! | //! [Released API Docs](https://docs.rs/crate/fid-rs) //! | //! [Benchmark Results](https://laysakura.github.io/fid-rs/criterion/report/) //! | //! [Changelog](https://github.com/laysakura/fid-rs/blob/master/CHANGELOG.md) //! //! [](https://travis-ci.com/laysakura/fid-rs) //! [](https://crates.io/crates/fid-rs) //! [](https://crates.io/crates/fid-rs) //! [](https://github.com/laysakura/fid-rs#rust-version-supports) //! [](https://github.com/laysakura/fid-rs/blob/master/LICENSE-MIT) //! [](https://github.com/laysakura/fid-rs/blob/master/LICENSE-APACHE) //! //! # Quickstart //! //! To use fid-rs, add the following to your `Cargo.toml` file: //! //! ```toml //! [dependencies] //! fid-rs = "0.1" # NOTE: Replace to latest minor version. //! ``` //! //! ## Usage Overview //! //! ```rust //! 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 //! //! ```rust //! 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 //! //! ```rust //! use fid_rs::Fid; //! //! let fid = Fid::from("0100_1"); //! //! for bit in fid.iter() { //! println!("{}", bit); //! } //! // => //! // false //! // true //! // false //! // false //! // true //! ``` //! //! ## Utility Methods //! //! ```rust //! 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](https://crates.io/crates/criterion). Graphical benchmark results are published [here](https://laysakura.github.io/fid-rs/criterion/report/). //! //! ## Complexity //! //! When the length of a `Fid` is _N_: //! //! | Operation | Time-complexity | Space-complexity | //! |-----------|-----------------|------------------| //! | [Fid::from::<&str>()](https://laysakura.github.io/fid-rs/fid_rs/fid/struct.Fid.html#implementations) | _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>](https://laysakura.github.io/fid-rs/fid_rs/fid/struct.Fid.html#impl-Index<u64>) | _O(1)_ | _0_ | //! | [Fid::rank()](https://laysakura.github.io/fid-rs/fid_rs/fid/struct.Fid.html#method.rank) | _O(1)_ | _O(1)_ | //! | [Fid::rank0()](https://laysakura.github.io/fid-rs/fid_rs/fid/struct.Fid.html#method.rank0) | _O(1)_ | _O(1)_ | //! | [Fid::select()](https://laysakura.github.io/fid-rs/fid_rs/fid/struct.Fid.html#method.select) | _O(log N)_ | _O(1)_ | //! | [Fid::select0()](https://laysakura.github.io/fid-rs/fid_rs/fid/struct.Fid.html#method.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). pub use fid::Fid; pub mod fid; mod internal_data_structure;