Struct bio::data_structures::rank_select::RankSelect

pub struct RankSelect { /* fields omitted */ }

A rank/select data structure.

Methods

impl RankSelect

fn new(bits: BitVec, k: usize) -> RankSelect

Create a new instance.

Arguments

• bits - A bit vector.
• k - Determines the size (k * 32 bits) of the superblocks. A small k means faster rank query times at the expense of using more space and slower select query times. The data structure needs O(n + n log n / (k * 32)) bits with n being the bits of the given bitvector. The data structure is succinct if k is chosen as a sublinear function of n (e.g. k = (log n)² / 32).

fn rank(&self, i: usize) -> Option<u32>

Get the rank of a given bit, i.e. the number of 1-bits in the bitvector up to i (inclusive). Complexity: O(k).

Arguments

• i - Position of the bit to determine the rank for.

fn select(&self, j: u32) -> Option<usize>

Get the smallest bit with a given rank. Complexity: O(log (n / k) + k).

Arguments

• j - The rank to find the smallest bit for.