quadrank/
lib.rs

1//! # BiRank & QuadRank
2//!
3//! This crate provides data structures for `rank` queries over binary and size-4 alphabets.
4//! The main entrypoints are [`BiRank`] and [`QuadRank`], and usually you won't need anything else.
5//! They are aliases for instantiations of [`binary::BiRank`] and [`quad::QuadRank`],
6//! which implement the [`binary::BiRanker`] and [`quad::QuadRanker`] traits respectively.
7//!
8//! By default, the smallest variants are used.
9//! Type aliases are provided for larger but possibly slightly faster variants.
10//!
11//! See also the [GitHub README](https://github.com/ragnargrootkoerkamp/quadrank).
12//!
13//! ## Indexing and safety
14//!
15//! In this library, `rank(pos)` counts the number of 1-bits in the first `pos` bits of the input.
16//! I.e., it counts the number of 1-bits _before_ position `pos`.
17//!
18//! For performance, we only provide [`BiRanker::rank_unchecked`] and [`QuadRanker::rank1_unchecked`].
19//! In general (for external implementations of the trait),
20//! this requires `0 <= pos < n` when the input consists of `n` symbols (bits or 2-bit characters),
21//! but both [`BiRank`] and [`QuadRank`] also support `pos == n`.
22//!
23//! ## Example
24//!
25//! ```
26//! use quadrank::{BiRank, BiRanker};
27//! use quadrank::{QuadRank, QuadRanker};
28//!
29//! let packed = [0xf0f0f0f0f0f0f0f0, u64::MAX];
30//! let rank = <BiRank>::new_packed(&packed);
31//! unsafe {
32//!     assert_eq!(rank.rank_unchecked(0), 0);
33//!     assert_eq!(rank.rank_unchecked(4), 0);
34//!     assert_eq!(rank.rank_unchecked(8), 4);
35//!     assert_eq!(rank.rank_unchecked(64), 32);
36//!     assert_eq!(rank.rank_unchecked(128), 96);
37//! }
38//!
39//! // ACTG maps to 0123 in that specific order.
40//! let dna = b"ACGCGCGACTTACGCAT";
41//! let n = dna.len(); // 17
42//! let rank = <QuadRank>::new_ascii_dna(dna);
43//! unsafe {
44//!     assert_eq!(rank.rank1_unchecked(0, 0), 0);
45//!     assert_eq!(rank.rank4_unchecked(0), [0; 4]);
46//!     assert_eq!(rank.rank1_unchecked(n, 0), 4);
47//!     assert_eq!(rank.rank4_unchecked(n), [4, 6, 3, 4]);
48//! }
49//! ```
50
51/// Rank over binary alphabet.
52pub mod binary;
53/// Rank over size-4 alphabet.
54pub mod quad;
55
56/// Implementations of [`binary::BiRanker`] and [`quad::QuadRanker`] for external crates.
57///
58/// Each module re-exports the relevant types.
59#[cfg(feature = "ext")]
60pub mod ext {
61    pub mod bio;
62    pub mod bitm;
63    pub mod genedex;
64    pub mod qwt;
65    pub mod rsdict;
66    pub mod succinct;
67    pub mod sucds;
68    pub mod sux;
69    pub mod vers;
70}
71
72pub use binary::{BiRank, BiRanker};
73pub use quad::{QuadRank, QuadRanker};
74
75// Type aliases
76/// Binary rank structure with 3.28% space overhead.
77/// Smallest, and usually sufficiently fast.
78pub type BiRank16 = binary::BiRank<binary::blocks::BinaryBlock16>;
79/// Binary rank structure with 6.72% space overhead.
80pub type BiRank16x2 = binary::BiRank<binary::blocks::BinaryBlock16x2>;
81/// Binary rank structure with 14.3% space overhead.
82pub type BiRank32x2 = binary::BiRank<binary::blocks::BinaryBlock32x2>;
83/// Binary rank structure with 33.3 space overhead.
84pub type BiRank64x2 = binary::BiRank<binary::blocks::BinaryBlock64x2>;
85
86/// Quad rank structure with 14.40% space overhead.
87/// Smallest, and usually sufficiently fast.
88pub type QuadRank16 = quad::QuadRank<quad::blocks::QuadBlock16>;
89/// Quad rank structure with 33% space overhead.
90pub type QuadRank24_8 = quad::QuadRank<quad::blocks::QuadBlock24_8>;
91/// Quad rank structure with 100% space overhead.
92pub type QuadRank64 = quad::QuadRank<quad::blocks::QuadBlock64>;
quadrank/lib.rs

quadrank/
lib.rs
