Crate quadrank 

BiRank & QuadRank

This crate provides data structures for rank queries over binary and size-4 alphabets. The main entrypoints are BiRank and QuadRank, and usually you won’t need anything else. They are aliases for instantiations of binary::BiRank and quad::QuadRank, which implement the binary::BiRanker and quad::QuadRanker traits respectively.

By default, the smallest variants are used. Type aliases are provided for larger but possibly slightly faster variants.

See also the GitHub README.

Indexing and safety

In this library, rank(pos) counts the number of 1-bits in the first pos bits of the input. I.e., it counts the number of 1-bits before position pos.

For performance, we only provide BiRanker::rank_unchecked and QuadRanker::rank1_unchecked. In general (for external implementations of the trait), this requires 0 <= pos < n when the input consists of n symbols (bits or 2-bit characters), but both BiRank and QuadRank also support pos == n.

Example

use quadrank::{BiRank, BiRanker};
use quadrank::{QuadRank, QuadRanker};

let packed = [0xf0f0f0f0f0f0f0f0, u64::MAX];
let rank = <BiRank>::new_packed(&packed);
unsafe {
    assert_eq!(rank.rank_unchecked(0), 0);
    assert_eq!(rank.rank_unchecked(4), 0);
    assert_eq!(rank.rank_unchecked(8), 4);
    assert_eq!(rank.rank_unchecked(64), 32);
    assert_eq!(rank.rank_unchecked(128), 96);
}

// ACTG maps to 0123 in that specific order.
let dna = b"ACGCGCGACTTACGCAT";
let n = dna.len(); // 17
let rank = <QuadRank>::new_ascii_dna(dna);
unsafe {
    assert_eq!(rank.rank1_unchecked(0, 0), 0);
    assert_eq!(rank.rank4_unchecked(0), [0; 4]);
    assert_eq!(rank.rank1_unchecked(n, 0), 4);
    assert_eq!(rank.rank4_unchecked(n), [4, 6, 3, 4]);
}

Re-exports

pub use binary::BiRank;

pub use binary::BiRanker;

pub use quad::QuadRank;

pub use quad::QuadRanker;

Modules

binary

Rank over binary alphabet.

quad

Rank over size-4 alphabet.

Type Aliases

BiRank16

Binary rank structure with 3.28% space overhead. Smallest, and usually sufficiently fast.

BiRank16x2

Binary rank structure with 6.72% space overhead.

BiRank32x2

Binary rank structure with 14.3% space overhead.

BiRank64x2

Binary rank structure with 33.3 space overhead.

QuadRank16

Quad rank structure with 14.40% space overhead. Smallest, and usually sufficiently fast.

QuadRank64

Quad rank structure with 100% space overhead.

QuadRank24_8

Quad rank structure with 33% space overhead.