iset 0.3.3

Map and set with interval keys (x..y).
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
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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132

use alloc::vec::Vec;

/// i >> IX_SHIFT is the same as i / 8.
const IX_SHIFT: usize = 3;
/// i & IX_MASK is the same as i % 8.
const IX_MASK: usize = 7;
/// Starting capacity (in bytes).
const START_CAPACITY: usize = 8;

#[inline]
fn get_byte_len(bit_len: usize) -> usize {
    (bit_len >> IX_SHIFT) + (bit_len & IX_MASK > 0) as usize
}

#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
#[derive(Clone, Debug)]
pub(crate) struct BitVec {
    len: usize,
    data: Vec<u8>,
}

impl BitVec {
    pub fn new() -> Self {
        Self {
            len: 0,
            data: Vec::with_capacity(START_CAPACITY),
        }
    }

    pub fn with_capacity(capacity: usize) -> Self {
        Self {
            len: 0,
            data: Vec::with_capacity(get_byte_len(capacity)),
        }
    }

    pub fn from_elem(len: usize, elem: bool) -> Self {
        let fill = if elem { u8::MAX } else { 0 };
        Self {
            len,
            data: alloc::vec![fill; get_byte_len(len)],
        }
    }

    #[inline]
    pub fn len(&self) -> usize {
        self.len
    }

    #[inline]
    pub fn is_empty(&self) -> bool {
        self.len == 0
    }

    #[inline]
    pub fn shrink_to_fit(&mut self) {
        self.data.shrink_to_fit()
    }

    pub fn clear(&mut self) {
        self.data.clear();
        self.len = 0;
    }

    #[inline]
    pub fn get(&self, i: usize) -> bool {
        debug_assert!(i < self.len);
        let j = i >> IX_SHIFT;
        let k = i & IX_MASK;
        self.data[j] >> k & 1 == 1
    }

    #[inline]
    pub fn get_tail(&self, i: usize) -> bool {
        self.get(self.len - 1 - i)
    }

    #[inline]
    pub fn set0(&mut self, i: usize) {
        debug_assert!(i < self.len);
        let j = i >> IX_SHIFT;
        let k = i & IX_MASK;
        self.data[j] &= !(1 << k);
    }

    #[inline]
    pub fn set1(&mut self, i: usize) {
        debug_assert!(i < self.len);
        let j = i >> IX_SHIFT;
        let k = i & IX_MASK;
        self.data[j] |= 1 << k;
    }

    #[inline]
    pub fn set(&mut self, i: usize, value: bool) {
        if value {
            self.set1(i)
        } else {
            self.set0(i);
        }
    }

    pub fn push(&mut self, value: bool) {
        if self.len & IX_MASK == 0 {
            self.data.push(0);
        }
        self.len += 1;
        self.set(self.len - 1, value);
    }

    pub fn pop(&mut self) -> bool {
        debug_assert!(self.len > 0);
        self.len -= 1;
        let j = self.len >> IX_SHIFT;
        let k = self.len & IX_MASK;
        let value = self.data[j] >> k & 1 == 1;
        if k == 0 {
            self.data.pop();
        }
        value
    }

    pub fn swap_remove(&mut self, i: usize) -> bool {
        debug_assert!(i < self.len);
        let old_val = self.get(i);
        if i + 1 != self.len {
            self.set(i, self.get(self.len - 1));
        }
        self.pop();
        old_val
    }
}