1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

/// Supports fast rank queries.
///
/// Associated type `Over` gives the type that we can query about. For
/// example, `RankSupport<Over=bool>` lets us rank `0` and `1`, whereas
/// `RankSupport<Over=u8>` will rank arbitrary bytes.
pub trait RankSupport {
    /// The type of value to rank.
    type Over: Copy;

    /// Returns the rank of the given value at a given position.
    ///
    /// This is the number of occurrences of `value` up to and including
    /// that position.
    ///
    /// # Panics
    ///
    /// Panics if `position >= self.limit()`.
    fn rank(&self, position: u64, value: Self::Over) -> u64;

    /// The size of the vector being ranked.
    fn limit(&self) -> u64;
}

/// Supports fast rank queries over `bool`s.
pub trait BitRankSupport: RankSupport<Over = bool> {
    /// Returns the rank of 1 at the given position.
    ///
    /// This is the number of occurrences of 1 up to and including that
    /// position.
    fn rank1(&self, position: u64) -> u64 {
        self.rank(position, true)
    }

    /// Returns the rank of 0 at the given position.
    ///
    /// This is the number of occurrences of 0 up to and including that
    /// position.
    fn rank0(&self, position: u64) -> u64 {
        position + 1 - self.rank1(position)
    }
}