pub trait Rank: ImpliedSet {
// Required method
fn rank(&self, value: u64) -> usize;
// Provided methods
fn rank_1(&self, value: u64) -> usize { ... }
fn rank_0(&self, value: u64) -> usize { ... }
fn rank_2(&self, value_1: u64, value_2: u64) -> (usize, usize) { ... }
fn contains(&self, value: u64) -> bool { ... }
fn access_and_rank(&self, value: u64) -> (usize, bool) { ... }
}
Expand description
Operations for sets supporting rank.
The Rank trait exists for data structures that support the rank operation, which for a given value, returns the number of elements in the implied set with a value less than the given one.
There are a few auxiliary functions which have default implementations in terms of rank, but which may have more efficient implementations for a given underlying representation.
Note that the domain is over u64 and the range over usize.
Required Methods§
Provided Methods§
sourcefn rank_1(&self, value: u64) -> usize
fn rank_1(&self, value: u64) -> usize
rank_1
is an alias for rank
, which may be useful to distinguish it
from rank_0
in contexts where both are used.
sourcefn rank_0(&self, value: u64) -> usize
fn rank_0(&self, value: u64) -> usize
Return the number of elements less than value
that are not in the set.
s.rank_0(x) == x - s.rank_1(x)
and vice versa.
sourcefn rank_2(&self, value_1: u64, value_2: u64) -> (usize, usize)
fn rank_2(&self, value_1: u64, value_2: u64) -> (usize, usize)
Compute the ranks of two elements of the domain. Implementations may assume that the two elements are close in value, or close in rank.
It is a requirement that value_1
is strictly less than value_2
.
sourcefn access_and_rank(&self, value: u64) -> (usize, bool)
fn access_and_rank(&self, value: u64) -> (usize, bool)
Return the rank of value
and whether it is contained in the implied set.