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
133
134
135

//! A very simple bitset that is guaranteed to be stored
//! in little-endian. If you can't think of a reason you
//! need this, this crate probably isn't for you. Usage
//! is pretty self-explanatory.

#[cfg(test)]
mod test;

const U32_BITS: usize = std::mem::size_of::<u32>() * 8;

/// A little-endian bitset
pub struct BitSet {
    chunks: Vec<u32>,
    num_bits: usize,
}

impl BitSet {
    /// Calculates the number of chunks to store bits with
    ///
    /// # Arguments
    ///
    /// `num_bits`: The number of bits
    #[inline]
    fn calc_chunks(num_bits: usize) -> usize {
        (num_bits + U32_BITS - 1) / U32_BITS
    }

    /// Calculates the mask of the last chunk's bits
    ///
    /// # Arguments
    ///
    /// `num_bits`: The number of bits
    #[inline]
    fn last_mask(num_bits: usize) -> u32 {
        !(!1 << ((num_bits - 1) % U32_BITS))
    }

    /// Creates a bitset from the chunks
    ///
    /// # Arguments
    ///
    /// `chunks`: The raw little-endian bit chunks
    ///
    /// `num_bits`: The number of bits
    pub fn from_bits(chunks: Vec<u32>, num_bits: usize) -> Self {
        #[cfg(debug_assertions)]
        assert!(num_bits > 0);
        #[cfg(debug_assertions)]
        assert_eq!(Self::calc_chunks(num_bits), chunks.len());
        #[cfg(debug_assertions)]
        assert_eq!(chunks[chunks.len() - 1] & !Self::last_mask(num_bits), 0);
        Self { chunks, num_bits }
    }

    /// Unsets a bit at the index
    ///
    /// # Arguments
    ///
    /// `idx`: The index
    pub fn reset(&mut self, idx: usize) {
        #[cfg(debug_assertions)]
        assert!(idx / U32_BITS < self.chunks.len());
        #[cfg(debug_assertions)]
        assert!(idx < self.num_bits);
        let chunk = &mut self.chunks[idx / U32_BITS];
        let chunk_pos = idx % U32_BITS;
        *chunk = (*chunk & !(1 << chunk_pos)).to_le();
    }

    /// Resets all bits to 0
    pub fn reset_all(&mut self) {
        for chunk in &mut self.chunks {
            *chunk = 0;
        }
    }

    /// Sets a bit at the index
    ///
    /// # Arguments
    ///
    /// `idx`: The index
    pub fn set(&mut self, idx: usize) {
        #[cfg(debug_assertions)]
        assert!(idx / U32_BITS < self.chunks.len());
        #[cfg(debug_assertions)]
        assert!(idx < self.num_bits);
        let chunk = &mut self.chunks[idx / U32_BITS];
        let chunk_pos = idx % U32_BITS;
        *chunk = (*chunk | 1 << chunk_pos).to_le();
    }

    /// Sets all bits to 1
    pub fn set_all(&mut self) {
        for chunk in &mut self.chunks {
            *chunk = u32::MAX;
        }
        let num_chunks = self.chunks.len();
        self.chunks[num_chunks - 1] = Self::last_mask(self.num_bits);
    }

    /// Tests the bit at the index
    ///
    /// # Arguments
    ///
    /// `idx`: The index
    pub fn test(&self, idx: usize) -> bool {
        #[cfg(debug_assertions)]
        assert!(idx / U32_BITS < self.chunks.len());
        #[cfg(debug_assertions)]
        assert!(idx < self.num_bits);
        let chunk = self.chunks[idx / U32_BITS].to_le();
        let chunk_pos = idx % U32_BITS;
        ((chunk >> chunk_pos) & 1) == 1
    }

    /// Creates an empty bitset with a capacity
    ///
    /// # Arguments
    ///
    /// `num_bits`: The number of bits to store
    pub fn with_capacity(num_bits: usize) -> Self {
        #[cfg(debug_assertions)]
        assert!(num_bits > 0);
        let num_chunks = Self::calc_chunks(num_bits);
        let mut chunks = Vec::with_capacity(num_chunks);
        chunks.resize(num_chunks, 0);
        Self { chunks, num_bits }
    }
}

impl From<BitSet> for Vec<u32> {
    fn from(bitset: BitSet) -> Self {
        bitset.chunks
    }
}