bit_array_rs/
lib.rs

1/*
2 * Copyright (c) Peter Bjorklund. All rights reserved. https://github.com/piot/bit-array-rs
3 * Licensed under the MIT License. See LICENSE in the project root for license information.
4 */
5use std::ops::Index;
6use std::vec::Vec;
7
8type BitArrayAtom = u64;
9const BIT_ARRAY_BITS_IN_ATOM: usize = 64;
10
11#[derive(Clone)]
12pub struct BitArray {
13    array: Vec<BitArrayAtom>,
14    bit_count: usize,
15    number_of_bits_set: usize,
16}
17
18impl BitArray {
19    /// Initializes a new `BitArray`.
20    ///
21    /// # Arguments
22    ///
23    /// * `bit_count` - The maximum number of bits in the array.
24    /// # Panics
25    ///
26    /// This function will panic if `bit_count` is zero.
27    #[must_use]
28    pub fn new(bit_count: usize) -> Self {
29        assert_ne!(bit_count, 0, "bit_count must be greater than zero");
30        let atom_count = bit_count.div_ceil(BIT_ARRAY_BITS_IN_ATOM);
31        let array = vec![0; atom_count];
32
33        Self {
34            array,
35            bit_count,
36            number_of_bits_set: 0,
37        }
38    }
39
40    /// Resets all bits in the array.
41    pub fn reset(&mut self) {
42        self.array.fill(0);
43        self.number_of_bits_set = 0;
44    }
45
46    /// Checks if all bits are set.
47    ///
48    /// # Returns
49    ///
50    /// * `true` if all bits in the array are set, otherwise `false`.
51    #[inline]
52    #[must_use]
53    pub const fn all_set(&self) -> bool {
54        self.bit_count == self.number_of_bits_set
55    }
56
57    /// Finds the first bit that is not set in the array.
58    ///
59    /// # Returns
60    ///
61    /// * The index of the first unset bit, or `None` if all bits are set.
62    #[must_use]
63    pub fn first_unset_bit(&self) -> Option<usize> {
64        for (i, &atom) in self.array.iter().enumerate() {
65            if atom != u64::MAX {
66                return (0..BIT_ARRAY_BITS_IN_ATOM).find_map(|bit| {
67                    if atom & (1 << bit) == 0 {
68                        Some(i * BIT_ARRAY_BITS_IN_ATOM + bit)
69                    } else {
70                        None
71                    }
72                });
73            }
74        }
75        None
76    }
77
78    /// Finds the first bit that is set in the array.
79    ///
80    /// # Returns
81    ///
82    /// * The index of the first set bit, or `None` if no bits are set.
83    #[must_use]
84    pub fn first_set_bit(&self) -> Option<usize> {
85        for (i, &atom) in self.array.iter().enumerate() {
86            if atom != 0 {
87                return (0..BIT_ARRAY_BITS_IN_ATOM).find_map(|bit| {
88                    if atom & (1 << bit) != 0 {
89                        Some(i * BIT_ARRAY_BITS_IN_ATOM + bit)
90                    } else {
91                        None
92                    }
93                });
94            }
95        }
96        None
97    }
98
99    /// Returns the number of bits that are currently set to `1`.
100    ///
101    /// # Returns
102    ///
103    /// The number of bits that are set in the `BitArray`.
104    #[inline]
105    #[must_use]
106    pub const fn count_set_bits(&self) -> usize {
107        self.number_of_bits_set
108    }
109
110    /// Returns the total number of bits in the `BitArray`.
111    ///
112    /// # Returns
113    ///
114    /// The total number of bits in the `BitArray`.
115    #[inline]
116    #[must_use]
117    pub const fn bit_count(&self) -> usize {
118        self.bit_count
119    }
120
121    /// Sets the bit at the given index.
122    ///
123    /// # Arguments
124    ///
125    /// * `index` - The zero-based index of the bit to set.
126    ///
127    /// # Panics
128    ///
129    /// This function will panic if the index is out of bounds.
130    #[inline]
131    pub fn set(&mut self, index: usize) {
132        assert!(index < self.bit_count, "Index out of bounds");
133
134        let array_index = index / BIT_ARRAY_BITS_IN_ATOM;
135        let bit_index = index % BIT_ARRAY_BITS_IN_ATOM;
136        let mask = 1 << bit_index;
137
138        if self.array[array_index] & mask == 0 {
139            self.number_of_bits_set += 1;
140        }
141
142        self.array[array_index] |= mask;
143    }
144
145    /// Unsets (clears) the bit at the given index.
146    ///
147    /// # Arguments
148    ///
149    /// * `index` - The zero-based index of the bit to clear.
150    ///
151    /// # Panics
152    ///
153    /// This function will panic if the index is out of bounds.
154    #[inline]
155    pub fn unset(&mut self, index: usize) {
156        assert!(index < self.bit_count, "Index out of bounds");
157
158        let array_index = index / BIT_ARRAY_BITS_IN_ATOM;
159        let bit_index = index % BIT_ARRAY_BITS_IN_ATOM;
160        let mask = 1 << bit_index;
161
162        if self.array[array_index] & mask != 0 {
163            self.number_of_bits_set -= 1;
164        }
165
166        self.array[array_index] &= !mask;
167    }
168
169    /// Sets or unsets the bit at the given index based on the value of `set`.
170    ///
171    /// # Arguments
172    ///
173    /// * `index` - The zero-based index of the bit to modify.
174    /// * `set` - If `true`, the bit will be set (1). If `false`, the bit will be unset (0).
175    ///
176    /// # Panics
177    ///
178    /// This function will panic if the index is out of bounds.
179    pub fn set_bit(&mut self, index: usize, set: bool) {
180        assert!(index < self.bit_count, "Index out of bounds");
181
182        let array_index = index / BIT_ARRAY_BITS_IN_ATOM;
183        let bit_index = index % BIT_ARRAY_BITS_IN_ATOM;
184        let mask = 1 << bit_index;
185
186        if set {
187            if self.array[array_index] & mask == 0 {
188                self.number_of_bits_set += 1;
189            }
190            self.array[array_index] |= mask;
191        } else {
192            if self.array[array_index] & mask != 0 {
193                self.number_of_bits_set -= 1;
194            }
195            self.array[array_index] &= !mask;
196        }
197    }
198
199    /// Returns the atom value that is located at the specified index.
200    ///
201    /// # Arguments
202    ///
203    /// * `from_index` - The index from which to start reading.
204    ///
205    /// # Returns
206    ///
207    /// The atom value at the specified index.
208    #[must_use]
209    pub fn atom_from_index(&self, from_index: usize) -> BitArrayAtom {
210        let mut result: u64 = 0;
211
212        for i in 0..BIT_ARRAY_BITS_IN_ATOM {
213            let index = from_index + (BIT_ARRAY_BITS_IN_ATOM - 1) - i;
214            result <<= 1;
215            if index < self.bit_count {
216                result |= u64::from(self.get(index));
217            }
218        }
219
220        result
221    }
222
223    /// Returns the bit value at the specified index.
224    ///
225    /// # Arguments
226    ///
227    /// * `index` - The bit index to read from.
228    ///
229    /// # Returns
230    ///
231    /// The read bit value (0 or 1).
232    ///
233    /// # Panics
234    ///
235    /// This function will panic if the index is out of bounds.
236    #[must_use]
237    pub fn get(&self, index: usize) -> bool {
238        assert!(index < self.bit_count, "Index out of bounds");
239
240        let array_index = index / BIT_ARRAY_BITS_IN_ATOM;
241        let bit_index = index % BIT_ARRAY_BITS_IN_ATOM;
242
243        ((self.array[array_index] >> bit_index) & 0x1) != 0
244    }
245}
246
247impl Index<usize> for BitArray {
248    type Output = bool;
249    /// Provides indexed access to individual bits in the `BitArray`.
250    ///
251    /// # Arguments
252    ///
253    /// * `index` - The zero-based index of the bit to access.
254    ///
255    /// # Returns
256    ///
257    /// A reference to a boolean value (`true` or `false`) representing the state of the bit
258    /// at the specified index.
259    ///
260    /// # Panics
261    ///
262    /// This function will panic if the `index` is out of bounds.
263    ///
264    /// # Example
265    ///
266    /// ```
267    /// use bit_array_rs::BitArray;
268    /// let mut bit_array = BitArray::new(16);
269    /// bit_array.set(3);
270    /// assert_eq!(bit_array[3], true);
271    /// assert_eq!(bit_array[0], false);
272    /// ```
273    fn index(&self, index: usize) -> &Self::Output {
274        if self.get(index) {
275            &true
276        } else {
277            &false
278        }
279    }
280}
281
282impl std::fmt::Debug for BitArray {
283    /// Formats the `BitArray` as a binary string with groups of 8 bits separated by a space.
284    ///
285    /// # Arguments
286    ///
287    /// * `f` - The formatter used to output the debug string.
288    ///
289    /// # Returns
290    ///
291    /// A `Result` indicating whether the formatting was successful.
292    ///
293    /// # Example
294    ///
295    /// ```
296    /// use bit_array_rs::BitArray;
297    /// let mut bit_array = BitArray::new(16);
298    /// bit_array.set(3);
299    /// bit_array.set(7);
300    /// bit_array.set(9);
301    /// bit_array.set(15);
302    ///
303    /// assert_eq!(format!("{:?}", bit_array), "00010001 01000001");
304    /// ```
305    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
306        for i in 0..self.bit_count {
307            if i > 0 && i % 8 == 0 {
308                write!(f, " ")?;
309            }
310            write!(f, "{}", u8::from(self.get(i)))?;
311        }
312        Ok(())
313    }
314}
315
316impl std::fmt::Display for BitArray {
317    /// Formats the `BitArray` as a continuous binary string without any spaces.
318    ///
319    /// # Arguments
320    ///
321    /// * `f` - The formatter used to output the display string.
322    ///
323    /// # Returns
324    ///
325    /// A `Result` indicating whether the formatting was successful.
326    ///
327    /// # Example
328    ///
329    /// ```
330    /// use bit_array_rs::BitArray;
331    /// let mut bit_array = BitArray::new(16);
332    /// bit_array.set(3);
333    /// bit_array.set(7);
334    /// bit_array.set(9);
335    /// bit_array.set(15);
336    ///
337    /// assert_eq!(format!("{}", bit_array), "0001000101000001");
338    /// ```
339    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
340        for i in 0..self.bit_count {
341            write!(f, "{}", u8::from(self.get(i)))?;
342        }
343        Ok(())
344    }
345}