Struct bio::data_structures::rank_select::RankSelect
source · pub struct RankSelect { /* private fields */ }
Expand description
A rank/select data structure.
Implementations
sourceimpl RankSelect
impl RankSelect
sourcepub fn new(bits: BitVec<u8>, k: usize) -> RankSelect
pub fn new(bits: BitVec<u8>, 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).
sourcepub fn rank_1(&self, i: u64) -> Option<u64>
pub fn rank_1(&self, i: u64) -> Option<u64>
Get the 1-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.
sourcepub fn rank_0(&self, i: u64) -> Option<u64>
pub fn rank_0(&self, i: u64) -> Option<u64>
Get the 0-rank of a given bit, i.e. the number of 0-bits in the bitvector up to i (inclusive). Complexity: O(k).
Arguments
i
- Position of the bit to determine the rank for.
sourcepub fn select_1(&self, j: u64) -> Option<u64>
pub fn select_1(&self, j: u64) -> Option<u64>
Get the smallest bit with a given 1-rank. Complexity: O(log (n / k) + k).
Arguments
j
- The rank to find the smallest bit for.
Trait Implementations
sourceimpl<'de> Deserialize<'de> for RankSelect
impl<'de> Deserialize<'de> for RankSelect
sourcefn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error>where
__D: Deserializer<'de>,
fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error>where
__D: Deserializer<'de>,
Deserialize this value from the given Serde deserializer. Read more
sourceimpl Serialize for RankSelect
impl Serialize for RankSelect
Auto Trait Implementations
impl RefUnwindSafe for RankSelect
impl Send for RankSelect
impl Sync for RankSelect
impl Unpin for RankSelect
impl UnwindSafe for RankSelect
Blanket Implementations
sourceimpl<T> BorrowMut<T> for Twhere
T: ?Sized,
impl<T> BorrowMut<T> for Twhere
T: ?Sized,
const: unstable · sourcefn borrow_mut(&mut self) -> &mut T
fn borrow_mut(&mut self) -> &mut T
Mutably borrows from an owned value. Read more