indexed_bitvec_core 4.0.0

Core operations on indexed bitvectors including (hopefully) fast rank and select operations.
Documentation 
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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

/*
   Copyright 2018 DarkOtter

   Licensed under the Apache License, Version 2.0 (the "License");
   you may not use this file except in compliance with the License.
   You may obtain a copy of the License at

       http://www.apache.org/licenses/LICENSE-2.0

   Unless required by applicable law or agreed to in writing, software
   distributed under the License is distributed on an "AS IS" BASIS,
   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   See the License for the specific language governing permissions and
   limitations under the License.
*/
//! Types and traits used to make functions generic over set/unset bits.

/// Supply to generic functions to work with/count set bits (ones).
pub enum OneBits {}
/// Supply to generic functions to work with/count unset bits (zeros).
pub enum ZeroBits {}

mod private {
    pub trait Sealed {}
    impl Sealed for super::OneBits {}
    impl Sealed for super::ZeroBits {}
}

/// Trait used to provide functionality generic across 1 or 0 bits,
/// for example rank in terms of set or unset bits.
pub trait OnesOrZeros: private::Sealed {
    /// Convert a count of ones in a range to a count of ones or zeros.
    /// The result is never larger than the number of bits supplied.
    /// It is assumed the count of ones is not larger than the number of bits.
    fn convert_count(count_ones: u64, in_bits: u64) -> u64;

    fn is_ones() -> bool;

    /// Either count_ones or count_zeros.
    fn count(of_bits: u64) -> u32;
}

impl OnesOrZeros for OneBits {
    #[inline]
    fn convert_count(count_ones: u64, _in_bits: u64) -> u64 {
        count_ones
    }

    #[inline]
    fn is_ones() -> bool {
        true
    }

    #[inline]
    fn count(of_bits: u64) -> u32 {
        of_bits.count_ones()
    }
}

impl OnesOrZeros for ZeroBits {
    #[inline]
    fn convert_count(count_ones: u64, in_bits: u64) -> u64 {
        in_bits - count_ones
    }

    #[inline]
    fn is_ones() -> bool {
        false
    }

    #[inline]
    fn count(of_bits: u64) -> u32 {
        of_bits.count_ones()
    }
}