compacts-bits 0.2.1

succinct bit vector
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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110

#[cfg(test)]
#[macro_use]
mod macros;

mod seq16;
mod seq64;
mod rle16;
mod range;
mod iter;

#[cfg(test)]
mod tests;

pub use self::iter::*;

use std::ops::RangeInclusive;
use std::mem;

pub(crate) const CAPACITY: usize = 1 << 16;
const CAP32: u32 = CAPACITY as u32;

#[derive(Clone, Debug, Default, PartialEq)]
pub(crate) struct Seq<T> {
    pub(crate) weight: u32,
    pub(crate) vector: Vec<T>,
}

#[derive(Clone, Debug, Default, PartialEq)]
pub(crate) struct Rle<T> {
    pub(crate) weight: u32,
    pub(crate) ranges: Vec<RangeInclusive<T>>,
}

pub(crate) type Seq16 = Seq<u16>;
pub(crate) type Seq64 = Seq<u64>;
pub(crate) type Rle16 = Rle<u16>;

impl<T> Seq<T> {
    pub fn len(&self) -> usize {
        self.vector.len()
    }
    pub fn is_empty(&self) -> bool {
        self.weight == 0 && self.len() == 0
    }

    pub fn count_ones(&self) -> u32 {
        self.weight
    }
    pub fn count_zeros(&self) -> u32 {
        CAP32 - self.count_ones()
    }

    pub fn load_factor(&self) -> f64 {
        self.count_ones() as f64 / CAP32 as f64
    }

    pub fn shrink_to_fit(&mut self) {
        self.vector.shrink_to_fit()
    }
}

impl<T> Rle<T> {
    pub fn len(&self) -> usize {
        self.ranges.len()
    }
    pub fn is_empty(&self) -> bool {
        self.weight == 0 && self.len() == 0
    }

    pub fn count_ones(&self) -> u32 {
        self.weight
    }
    pub fn count_zeros(&self) -> u32 {
        CAP32 - self.count_ones()
    }

    pub fn load_factor(&self) -> f64 {
        self.count_ones() as f64 / CAP32 as f64
    }

    pub fn shrink_to_fit(&mut self) {
        self.ranges.shrink_to_fit()
    }
}

impl Seq16 {
    pub fn size_in_bytes(weight: usize) -> usize {
        weight * mem::size_of::<u16>() + mem::size_of::<u32>()
    }
    pub fn mem_size(&self) -> usize {
        Self::size_in_bytes(self.weight as usize)
    }
}
impl Seq64 {
    pub fn size_in_bytes(len: usize) -> usize {
        len * mem::size_of::<u64>() + mem::size_of::<u32>()
    }
    pub fn mem_size(&self) -> usize {
        // seq64 has fixed size
        Self::size_in_bytes(1024)
    }
}
impl Rle16 {
    pub fn size_in_bytes(runlen: usize) -> usize {
        runlen * mem::size_of::<RangeInclusive<u16>>() + mem::size_of::<u32>()
    }
    pub fn mem_size(&self) -> usize {
        Self::size_in_bytes(self.ranges.len())
    }
}