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 T where
T: ?Sized,
impl<T> BorrowMut<T> for T where
T: ?Sized,
const: unstable · sourcepub fn borrow_mut(&mut self) -> &mut T
pub fn borrow_mut(&mut self) -> &mut T
Mutably borrows from an owned value. Read more
impl<SS, SP> SupersetOf<SS> for SP where
SS: SubsetOf<SP>,
impl<SS, SP> SupersetOf<SS> for SP where
SS: SubsetOf<SP>,
pub fn to_subset(&self) -> Option<SS>
pub fn to_subset(&self) -> Option<SS>
The inverse inclusion map: attempts to construct self from the equivalent element of its
superset. Read more
pub fn is_in_subset(&self) -> bool
pub fn is_in_subset(&self) -> bool
Checks if self is actually part of its subset T (and can be converted to it).
pub fn to_subset_unchecked(&self) -> SS
pub fn to_subset_unchecked(&self) -> SS
Use with care! Same as self.to_subset but without any property checks. Always succeeds.
pub fn from_subset(element: &SS) -> SP
pub fn from_subset(element: &SS) -> SP
The inclusion map: converts self to the equivalent element of its superset.