Struct bio::data_structures::rank_select::RankSelect
source · pub struct RankSelect { /* private fields */ }
Expand description
A rank/select data structure.
Implementations§
source§impl 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§
source§impl Clone for RankSelect
impl Clone for RankSelect
source§fn clone(&self) -> RankSelect
fn clone(&self) -> RankSelect
Returns a copy of the value. Read more
1.0.0 · source§fn clone_from(&mut self, source: &Self)
fn clone_from(&mut self, source: &Self)
Performs copy-assignment from
source
. Read moresource§impl Debug for RankSelect
impl Debug for RankSelect
source§impl Default for RankSelect
impl Default for RankSelect
source§fn default() -> RankSelect
fn default() -> RankSelect
Returns the “default value” for a type. Read more
source§impl<'de> Deserialize<'de> for RankSelect
impl<'de> Deserialize<'de> for RankSelect
source§fn 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
source§impl Hash for RankSelect
impl Hash for RankSelect
source§impl Ord for RankSelect
impl Ord for RankSelect
source§fn cmp(&self, other: &RankSelect) -> Ordering
fn cmp(&self, other: &RankSelect) -> Ordering
1.21.0 · source§fn max(self, other: Self) -> Selfwhere
Self: Sized,
fn max(self, other: Self) -> Selfwhere Self: Sized,
Compares and returns the maximum of two values. Read more
source§impl PartialEq<RankSelect> for RankSelect
impl PartialEq<RankSelect> for RankSelect
source§fn eq(&self, other: &RankSelect) -> bool
fn eq(&self, other: &RankSelect) -> bool
This method tests for
self
and other
values to be equal, and is used
by ==
.source§impl PartialOrd<RankSelect> for RankSelect
impl PartialOrd<RankSelect> for RankSelect
source§fn partial_cmp(&self, other: &RankSelect) -> Option<Ordering>
fn partial_cmp(&self, other: &RankSelect) -> Option<Ordering>
1.0.0 · source§fn le(&self, other: &Rhs) -> bool
fn le(&self, other: &Rhs) -> bool
This method tests less than or equal to (for
self
and other
) and is used by the <=
operator. Read moresource§impl Serialize for RankSelect
impl Serialize for RankSelect
impl Eq for RankSelect
impl StructuralEq for RankSelect
impl StructuralPartialEq 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§
source§impl<T> BorrowMut<T> for Twhere
T: ?Sized,
impl<T> BorrowMut<T> for Twhere T: ?Sized,
source§fn borrow_mut(&mut self) -> &mut T
fn borrow_mut(&mut self) -> &mut T
Mutably borrows from an owned value. Read more
source§impl<Q, K> Equivalent<K> for Qwhere
Q: Eq + ?Sized,
K: Borrow<Q> + ?Sized,
impl<Q, K> Equivalent<K> for Qwhere Q: Eq + ?Sized, K: Borrow<Q> + ?Sized,
source§fn equivalent(&self, key: &K) -> bool
fn equivalent(&self, key: &K) -> bool
Compare self to
key
and return true
if they are equal.§impl<SS, SP> SupersetOf<SS> for SPwhere
SS: SubsetOf<SP>,
impl<SS, SP> SupersetOf<SS> for SPwhere SS: SubsetOf<SP>,
§fn to_subset(&self) -> Option<SS>
fn to_subset(&self) -> Option<SS>
The inverse inclusion map: attempts to construct
self
from the equivalent element of its
superset. Read more§fn is_in_subset(&self) -> bool
fn is_in_subset(&self) -> bool
Checks if
self
is actually part of its subset T
(and can be converted to it).§fn to_subset_unchecked(&self) -> SS
fn to_subset_unchecked(&self) -> SS
Use with care! Same as
self.to_subset
but without any property checks. Always succeeds.§fn from_subset(element: &SS) -> SP
fn from_subset(element: &SS) -> SP
The inclusion map: converts
self
to the equivalent element of its superset.