fixed_bitset/
lib.rs

1//! A fixed-size, stack-allocated bitset.
2//!
3//! ```
4//! use fixed_bitset::Bitset;
5//! use typenum::consts::*;
6//!
7//! let mut set = Bitset::<U100>::new();
8//!
9//! set.insert(20);
10//! set.insert(70);
11//! // set.insert(100); // WILL PANIC!
12//!
13//! let values: Vec<usize> = set.iter().collect();
14//! assert_eq!(values, vec![20, 70]);
15//!
16//! let mut superset = set.clone();
17//! superset.insert(50);
18//!
19//! assert!(superset.is_superset(&set));
20//! assert!(set.is_subset(&superset));
21//!
22//!
23//! let difference = &superset - &set;
24//! assert_eq!(difference.iter().collect::<Vec<_>>(), vec![50]);
25//! assert!(difference.is_disjoint(&set));
26//! ```
27
28#![deny(missing_docs)]
29
30mod primitive;
31
32use std::ops::*;
33use std::{fmt, iter};
34
35use generic_array::{GenericArray, ArrayLength};
36use typenum::Unsigned;
37
38use self::primitive::{Primitive, CeilDiv};
39
40type CeilQuot<T, Q> = <T as CeilDiv<Q>>::Output;
41
42/// Yields the index of each set bit in this block.
43fn bits<B>(mut block: B) -> impl Iterator<Item = usize> + Clone
44    where B: Primitive
45{
46    iter::from_fn(move || {
47        if block.is_zero() {
48            None
49        } else {
50            let next_bit = block.trailing_zeros() as usize;
51            block ^= B::one() << next_bit;
52            Some(next_bit)
53        }
54    })
55}
56
57/// A set of unsigned integers whose size is fixed at compile-time.
58///
59/// A `Bitset` can only store unsigned integers less than `N`, where `N` is a compile-time integer
60/// from `typenum`. A `Bitset` uses a single bit to indicate the presence or absence of each value.
61pub struct Bitset<N, B = usize>
62    where B: Primitive,
63          N: CeilDiv<B::Size>,
64          CeilQuot<N, B::Size>: ArrayLength<B>,
65{
66    blocks: GenericArray<B, CeilQuot<N, B::Size>>,
67}
68
69impl<N, B> fmt::Debug for Bitset<N, B>
70    where B: Primitive,
71          N: Unsigned + CeilDiv<B::Size>,
72          CeilQuot<N, B::Size>: ArrayLength<B>,
73{
74    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
75        f.debug_set()
76            .entries(self.iter())
77            .finish()
78    }
79}
80
81impl<N, B> Default for Bitset<N, B>
82    where B: Primitive,
83          N: CeilDiv<B::Size>,
84          CeilQuot<N, B::Size>: ArrayLength<B>,
85{
86    fn default() -> Self {
87        Bitset {
88            blocks: Default::default(),
89        }
90    }
91}
92
93impl<N, B> Clone for Bitset<N, B>
94    where B: Primitive,
95          N: CeilDiv<B::Size>,
96          CeilQuot<N, B::Size>: ArrayLength<B>,
97{
98    fn clone(&self) -> Self {
99        Bitset {
100            blocks: self.blocks.clone(),
101        }
102    }
103}
104
105impl<N, B> Copy for Bitset<N, B>
106    where B: Primitive,
107          N: CeilDiv<B::Size>,
108          CeilQuot<N, B::Size>: ArrayLength<B>,
109          GenericArray<B, CeilQuot<N, B::Size>>: Copy,
110{}
111
112impl<N, B> PartialEq for Bitset<N, B>
113    where B: Primitive,
114          N: CeilDiv<B::Size>,
115          CeilQuot<N, B::Size>: ArrayLength<B>,
116{
117    fn eq(&self, other: &Self) -> bool {
118        self.blocks == other.blocks
119    }
120}
121
122impl<N, B> std::cmp::Eq for Bitset<N, B>
123    where B: Primitive,
124          N: CeilDiv<B::Size>,
125          CeilQuot<N, B::Size>: ArrayLength<B>,
126{}
127
128impl<N, B> iter::FromIterator<usize> for Bitset<N, B>
129    where B: Primitive,
130          N: Unsigned + CeilDiv<B::Size>,
131          CeilQuot<N, B::Size>: ArrayLength<B>,
132{
133    fn from_iter<T>(iter: T ) -> Self
134        where T: IntoIterator<Item = usize>
135    {
136        let mut ret = Self::default();
137        for n in iter.into_iter() {
138            ret.insert(n);
139        }
140
141        ret
142    }
143}
144
145impl<N, B> Bitset<N, B>
146    where B: Primitive,
147          N: Unsigned + CeilDiv<B::Size>,
148          CeilQuot<N, B::Size>: ArrayLength<B>,
149{
150    /// Returns an empty bitset.
151    pub fn new() -> Self {
152        Default::default()
153    }
154
155    /// Returns the block index and shift required to access a given bit.
156    fn loc(bit: usize) -> (usize, usize) {
157        (bit / B::SIZE, bit % B::SIZE)
158    }
159
160    /// Returns `true` if the bitset contains a value.
161    ///
162    /// Panics if `value >= N`.
163    pub fn contains(&self, value: usize) -> bool {
164        assert!(value < N::USIZE);
165        let (block, shift) = Self::loc(value);
166
167        (self.blocks[block] >> shift) & B::one() == B::one()
168    }
169
170    /// Inserts a value into the bitset.
171    ///
172    /// If that value already exists in the bitset, this function has no effect.
173    ///
174    /// Panics if `value >= N`.
175    pub fn insert(&mut self, value: usize) {
176        assert!(value < N::USIZE);
177        let (block, shift) = Self::loc(value);
178
179        self.blocks[block] |= B::one() << shift;
180    }
181
182    /// Removes a value from the bitset.
183    ///
184    /// If that value does not already exist in the bitset, this function has no effect.
185    ///
186    /// Panics if `value >= N`.
187    pub fn remove(&mut self, value: usize) {
188        assert!(value < N::USIZE);
189        let (block, shift) = Self::loc(value);
190
191        self.blocks[block] &= !(B::one() << shift);
192    }
193
194    /// Returns `true` if the bitset contains no bits.
195    pub fn is_empty(&self) -> bool {
196        self.blocks
197            .iter()
198            .all(|b| b.is_zero())
199    }
200
201    /// Returns the number of values contained in the bitset.
202    pub fn len(&self) -> usize {
203        self.blocks
204            .iter()
205            .map(|b| b.count_ones() as usize)
206            .sum()
207    }
208
209    /// Returns an iterator over the values in the bitset.
210    pub fn iter(&self) -> impl '_ + Iterator<Item = usize> + Clone {
211        self.blocks
212            .iter()
213            .cloned()
214            .enumerate()
215            .flat_map(|(i, b)| bits(b).map(move |j| B::SIZE * i + j))
216    }
217
218    /// Clears the bitset, removing all values.
219    pub fn clear(&mut self) {
220        for b in &mut self.blocks {
221            *b = B::zero();
222        }
223    }
224
225    fn apply_blocks(&mut self, other: &Self, f: impl Fn(&mut B, B)) {
226        for (a, &b) in self.blocks.iter_mut().zip(other.blocks.iter()) {
227            f(a, b);
228        }
229    }
230
231    fn iter_blocks<'a>(&'a self, other: &'a Self, f: impl 'a + Fn(B, B) -> B)
232        -> impl 'a + Iterator<Item = usize>
233    {
234        self.blocks
235            .iter()
236            .zip(other.blocks.iter())
237            .map(move |(&a, &b)| f(a, b))
238            .enumerate()
239            .flat_map(|(i, b)| bits(b).map(move |j| B::SIZE * i + j))
240    }
241
242    /// Returns an iterator over `self | other`.
243    pub fn union<'a>(&'a self, other: &'a Self) -> impl 'a + Iterator<Item = usize> {
244        self.iter_blocks(other, |a, b| a | b)
245    }
246
247    /// Returns an iterator over `self & other`.
248    pub fn intersection<'a>(&'a self, other: &'a Self) -> impl 'a + Iterator<Item = usize> {
249        self.iter_blocks(other, |a, b| a & b)
250    }
251
252    /// Returns an iterator over `self ^ other`.
253    pub fn symmetric_difference<'a>(&'a self, other: &'a Self) -> impl 'a + Iterator<Item = usize> {
254        self.iter_blocks(other, |a, b| a ^ b)
255    }
256
257    /// Returns an iterator over `self - other`.
258    pub fn difference<'a>(&'a self, other: &'a Self) -> impl 'a + Iterator<Item = usize> {
259        self.iter_blocks(other, |a, b| a & !b)
260    }
261
262    /// Returns `true` if `self` has no elements in common with `other`.
263    ///
264    /// This is more efficient than `self.intersection(other).next().is_none()`.
265    pub fn is_disjoint(&self, other: &Self) -> bool {
266        self.blocks
267            .iter()
268            .zip(other.blocks.iter())
269            .all(|(&a, &b)| (a & b).is_zero())
270    }
271
272    /// Returns `true` if every element in `self` exists in `other`.
273    pub fn is_subset(&self, other: &Self) -> bool {
274        self.blocks
275            .iter()
276            .zip(other.blocks.iter())
277            .all(|(&a, &b)| a & b == a)
278    }
279
280    /// Returns `true` if every element in `other` exists in `self`.
281    pub fn is_superset(&self, other: &Self) -> bool {
282        self.blocks
283            .iter()
284            .zip(other.blocks.iter())
285            .all(|(&a, &b)| a & b == b)
286    }
287}
288
289macro_rules! ops {
290    ($( $( #[$meta:meta] )* $OpAssign:ident, $op_assign:ident, $Op:ident, $op:ident => $f:expr ),* $(,)?) => {
291        $(
292            $(#[$meta])*
293            impl<N, B> $OpAssign<&Self> for Bitset<N, B>
294                where B: Primitive,
295                      N: Unsigned + CeilDiv<B::Size>,
296                      CeilQuot<N, B::Size>: ArrayLength<B>,
297            {
298                fn $op_assign(&mut self, other: &Self) {
299                    self.apply_blocks(other, $f);
300                }
301            }
302
303            $(#[$meta])*
304            impl<'a, 'b, N, B> $Op<&'b Bitset<N, B>> for &'a Bitset<N, B>
305                where B: Primitive,
306                      N: Unsigned + CeilDiv<B::Size>,
307                      CeilQuot<N, B::Size>: ArrayLength<B>,
308                      Bitset<N, B>: Clone,
309            {
310                type Output = Bitset<N, B>;
311
312                fn $op(self, other: &'b Bitset<N, B>) -> Self::Output {
313                    let mut ret = (*self).clone();
314                    (&mut ret).$op_assign(other);
315                    ret
316                }
317            }
318        )*
319    }
320}
321
322ops! {
323    /// Union
324    BitOrAssign,  bitor_assign,  BitOr,  bitor  => |a, b| *a |= b,
325    /// Intersection
326    BitAndAssign, bitand_assign, BitAnd, bitand => |a, b| *a &= b,
327    /// Symmetric Difference
328    BitXorAssign, bitxor_assign, BitXor, bitxor => |a, b| *a ^= b,
329    /// Difference
330    SubAssign,    sub_assign,    Sub,    sub    => |a, b| *a &= !b,
331}
fixed_bitset/lib.rs

fixed_bitset/
lib.rs
