index_set/
bitset_mut.rs

1/// A trait for a mutate values in a bit set.
2pub trait BitSetMut<T> {
3    /// Clears the set
4    ///
5    /// # Example
6    ///
7    /// ```rust
8    /// use index_set::{BitSet, BitSetMut};
9    ///
10    /// let mut bitset: [u32; 4] = [0; 4];
11    /// bitset.insert(0);
12    /// assert!(!BitSet::is_empty(&bitset[..]));
13    ///
14    /// bitset.clear();
15    /// assert!(BitSet::is_empty(&bitset[..]));
16    /// ```
17    fn clear(&mut self);
18
19    /// Inserts the value into the set.
20    ///
21    /// Returns `Ok(true)` if the value was already set.
22    /// Returns `Err(usize)` if the set cannot hold the value, where `usize` is the index of the slot.
23    ///
24    /// # Example
25    ///
26    /// ```rust
27    /// use index_set::{BitSet, BitSetMut};
28    ///
29    /// let mut bitset: [u32; 4] = [0; 4];
30    /// bitset.insert(0);
31    /// assert_eq!(bitset.has(0), true);
32    /// ```
33    fn insert(&mut self, _: T) -> Result<bool, usize>;
34
35    /// Removes the value from the set
36    ///
37    /// Returns `Some(true)` if the value was already set.
38    /// Returns `None` if the set cannot hold the value.
39    ///
40    /// # Example
41    ///
42    /// ```rust
43    /// use index_set::{BitSet, BitSetMut};
44    ///
45    /// let mut bitset: [u32; 4] = [0; 4];
46    /// bitset.insert(42);
47    /// assert_eq!(bitset.has(42), true);
48    ///
49    /// bitset.remove(42);
50    /// assert_eq!(bitset.has(42), false);
51    /// ```
52    fn remove(&mut self, _: T) -> Option<bool>;
53}
54
55impl<T> BitSetMut<T> for Vec<T>
56where
57    T: Default + Clone,
58    [T]: BitSetMut<T>,
59{
60    #[inline]
61    fn clear(&mut self) {
62        Vec::clear(self);
63    }
64
65    fn insert(&mut self, value: T) -> Result<bool, usize> {
66        match self.as_mut_slice().insert(value.clone()) {
67            Ok(has) => Ok(has),
68            Err(slot_index) => {
69                self.resize(slot_index + 1, T::default());
70                self.as_mut_slice().insert(value)
71            }
72        }
73    }
74
75    #[inline]
76    fn remove(&mut self, value: T) -> Option<bool> {
77        self.as_mut_slice().remove(value)
78    }
79}
80
81macro_rules! impl_deref_mut {
82    ($($target: ty),*) => {$(
83        impl<Set, T> BitSetMut<T> for $target
84        where
85            Set: BitSetMut<T> + ?Sized,
86        {
87            #[inline]
88            fn clear(&mut self) {
89                BitSetMut::clear(&mut **self)
90            }
91
92            #[inline]
93            fn insert(&mut self, index: T) -> Result<bool, usize> {
94                BitSetMut::insert(&mut **self, index)
95            }
96
97            #[inline]
98            fn remove(&mut self, index: T) -> Option<bool> {
99                BitSetMut::remove(&mut **self, index)
100            }
101        }
102    )*}
103}
104
105impl_deref_mut! {
106    &mut Set, Box<Set>
107}
108
109macro_rules! impl_bit_set_mut {
110    [$($ty:tt),*] => {$(
111        impl BitSetMut<$ty> for [$ty] {
112            fn clear(&mut self) {
113                for slot in self {
114                    *slot = 0;
115                }
116            }
117
118            #[inline]
119            fn insert(&mut self, index: $ty) -> Result<bool, usize> {
120                let slot_idx = usize::try_from(index / $ty::BITS as $ty).unwrap();
121                let mask = 1 << (index % $ty::BITS as $ty);
122                let slot = self.get_mut(slot_idx).ok_or(slot_idx)?;
123
124                let old_value = *slot & mask != 0;
125                *slot |= mask;
126                Ok(old_value)
127            }
128
129            #[inline]
130            fn remove(&mut self, index: $ty) -> Option<bool> {
131                let slot_idx = usize::try_from(index / $ty::BITS as $ty).ok()?;
132                let mask = 1 << (index % $ty::BITS as $ty);
133                let slot = self.get_mut(slot_idx)?;
134
135                let old_value = *slot & mask != 0;
136                *slot &= !mask;
137                Some(old_value)
138            }
139        }
140    )*};
141}
142
143impl_bit_set_mut! {
144    u16, u32, u64, usize, u128
145}
index_set/bitset_mut.rs

index_set/
bitset_mut.rs
