hibitset/
ops.rs

1use std::{
2    iter::{FromIterator, IntoIterator},
3    ops::{BitAnd, BitOr, BitXor, Not},
4    usize,
5};
6
7use crate::util::*;
8
9use crate::{AtomicBitSet, BitIter, BitSet, BitSetLike, DrainableBitSet};
10
11/// `BitSetAnd` takes two [`BitSetLike`] items, and merges the masks
12/// returning a new virtual set, which represents an intersection of the
13/// two original sets.
14///
15/// [`BitSetLike`]: ../trait.BitSetLike.html
16#[derive(Debug)]
17pub struct BitSetAnd<A: BitSetLike, B: BitSetLike>(pub A, pub B);
18
19impl<A: BitSetLike, B: BitSetLike> BitSetLike for BitSetAnd<A, B> {
20    #[inline]
21    fn layer3(&self) -> usize { self.0.layer3() & self.1.layer3() }
22
23    #[inline]
24    fn layer2(&self, i: usize) -> usize { self.0.layer2(i) & self.1.layer2(i) }
25
26    #[inline]
27    fn layer1(&self, i: usize) -> usize { self.0.layer1(i) & self.1.layer1(i) }
28
29    #[inline]
30    fn layer0(&self, i: usize) -> usize { self.0.layer0(i) & self.1.layer0(i) }
31
32    #[inline]
33    fn contains(&self, i: Index) -> bool {
34        self.0.contains(i) && self.1.contains(i)
35    }
36}
37
38impl<A: DrainableBitSet, B: DrainableBitSet> DrainableBitSet
39    for BitSetAnd<A, B>
40{
41    #[inline]
42    fn remove(&mut self, i: Index) -> bool {
43        if self.contains(i) {
44            self.0.remove(i);
45            self.1.remove(i);
46            true
47        } else {
48            false
49        }
50    }
51}
52
53/// `BitSetOr` takes two [`BitSetLike`] items, and merges the masks
54/// returning a new virtual set, which represents an merged of the
55/// two original sets.
56///
57/// [`BitSetLike`]: ../trait.BitSetLike.html
58#[derive(Debug)]
59pub struct BitSetOr<A: BitSetLike, B: BitSetLike>(pub A, pub B);
60
61impl<A: BitSetLike, B: BitSetLike> BitSetLike for BitSetOr<A, B> {
62    #[inline]
63    fn layer3(&self) -> usize { self.0.layer3() | self.1.layer3() }
64
65    #[inline]
66    fn layer2(&self, i: usize) -> usize { self.0.layer2(i) | self.1.layer2(i) }
67
68    #[inline]
69    fn layer1(&self, i: usize) -> usize { self.0.layer1(i) | self.1.layer1(i) }
70
71    #[inline]
72    fn layer0(&self, i: usize) -> usize { self.0.layer0(i) | self.1.layer0(i) }
73
74    #[inline]
75    fn contains(&self, i: Index) -> bool {
76        self.0.contains(i) || self.1.contains(i)
77    }
78}
79
80impl<A: DrainableBitSet, B: DrainableBitSet> DrainableBitSet
81    for BitSetOr<A, B>
82{
83    #[inline]
84    fn remove(&mut self, i: Index) -> bool {
85        if self.contains(i) {
86            self.0.remove(i);
87            self.1.remove(i);
88            true
89        } else {
90            false
91        }
92    }
93}
94
95/// `BitSetNot` takes a [`BitSetLike`] item, and produced an inverted virtual
96/// set. Note: the implementation is sub-optimal because layers 1-3 are not
97/// active.
98///
99/// [`BitSetLike`]: ../trait.BitSetLike.html
100#[derive(Debug)]
101pub struct BitSetNot<A: BitSetLike>(pub A);
102
103impl<A: BitSetLike> BitSetLike for BitSetNot<A> {
104    #[inline]
105    fn layer3(&self) -> usize { !0 }
106
107    #[inline]
108    fn layer2(&self, _: usize) -> usize { !0 }
109
110    #[inline]
111    fn layer1(&self, _: usize) -> usize { !0 }
112
113    #[inline]
114    fn layer0(&self, i: usize) -> usize { !self.0.layer0(i) }
115
116    #[inline]
117    fn contains(&self, i: Index) -> bool { !self.0.contains(i) }
118}
119
120/// `BitSetXor` takes two [`BitSetLike`] items, and merges the masks
121/// returning a new virtual set, which represents an merged of the
122/// two original sets.
123///
124/// [`BitSetLike`]: ../trait.BitSetLike.html
125#[derive(Debug)]
126pub struct BitSetXor<A: BitSetLike, B: BitSetLike>(pub A, pub B);
127
128impl<A: BitSetLike, B: BitSetLike> BitSetLike for BitSetXor<A, B> {
129    #[inline]
130    fn layer3(&self) -> usize {
131        let xor = BitSetAnd(
132            BitSetOr(&self.0, &self.1),
133            BitSetNot(BitSetAnd(&self.0, &self.1)),
134        );
135        xor.layer3()
136    }
137
138    #[inline]
139    fn layer2(&self, id: usize) -> usize {
140        let xor = BitSetAnd(
141            BitSetOr(&self.0, &self.1),
142            BitSetNot(BitSetAnd(&self.0, &self.1)),
143        );
144        xor.layer2(id)
145    }
146
147    #[inline]
148    fn layer1(&self, id: usize) -> usize {
149        let xor = BitSetAnd(
150            BitSetOr(&self.0, &self.1),
151            BitSetNot(BitSetAnd(&self.0, &self.1)),
152        );
153        xor.layer1(id)
154    }
155
156    #[inline]
157    fn layer0(&self, id: usize) -> usize {
158        let xor = BitSetAnd(
159            BitSetOr(&self.0, &self.1),
160            BitSetNot(BitSetAnd(&self.0, &self.1)),
161        );
162        xor.layer0(id)
163    }
164
165    #[inline]
166    fn contains(&self, i: Index) -> bool {
167        BitSetAnd(
168            BitSetOr(&self.0, &self.1),
169            BitSetNot(BitSetAnd(&self.0, &self.1)),
170        )
171        .contains(i)
172    }
173}
174
175/// `BitSetAll` is a bitset with all bits set. Essentially the same as
176/// `BitSetNot(BitSet::new())` but without any allocation.
177#[derive(Debug)]
178pub struct BitSetAll;
179impl BitSetLike for BitSetAll {
180    #[inline]
181    fn layer3(&self) -> usize { usize::MAX }
182
183    #[inline]
184    fn layer2(&self, _id: usize) -> usize { usize::MAX }
185
186    #[inline]
187    fn layer1(&self, _id: usize) -> usize { usize::MAX }
188
189    #[inline]
190    fn layer0(&self, _id: usize) -> usize { usize::MAX }
191
192    #[inline]
193    fn contains(&self, _i: Index) -> bool { true }
194}
195
196macro_rules! operator {
197    ( impl < ( $( $lifetime:tt )* ) ( $( $arg:ident ),* ) > for $bitset:ty ) => {
198        impl<$( $lifetime, )* $( $arg ),*> IntoIterator for $bitset
199            where $( $arg: BitSetLike ),*
200        {
201            type Item = <BitIter<Self> as Iterator>::Item;
202            type IntoIter = BitIter<Self>;
203            fn into_iter(self) -> Self::IntoIter {
204                self.iter()
205            }
206        }
207
208        impl<$( $lifetime, )* $( $arg ),*> Not for $bitset
209            where $( $arg: BitSetLike ),*
210        {
211            type Output = BitSetNot<Self>;
212            fn not(self) -> Self::Output {
213                BitSetNot(self)
214            }
215        }
216
217        impl<$( $lifetime, )* $( $arg, )* T> BitAnd<T> for $bitset
218            where T: BitSetLike,
219                  $( $arg: BitSetLike ),*
220        {
221            type Output = BitSetAnd<Self, T>;
222            fn bitand(self, rhs: T) -> Self::Output {
223                BitSetAnd(self, rhs)
224            }
225        }
226
227        impl<$( $lifetime, )* $( $arg, )* T> BitOr<T> for $bitset
228            where T: BitSetLike,
229                  $( $arg: BitSetLike ),*
230        {
231            type Output = BitSetOr<Self, T>;
232            fn bitor(self, rhs: T) -> Self::Output {
233                BitSetOr(self, rhs)
234            }
235        }
236
237        impl<$( $lifetime, )* $( $arg, )* T> BitXor<T> for $bitset
238            where T: BitSetLike,
239                  $( $arg: BitSetLike ),*
240        {
241            type Output = BitSetXor<Self, T>;
242            fn bitxor(self, rhs: T) -> Self::Output {
243                BitSetXor(self, rhs)
244            }
245        }
246
247    }
248}
249
250operator!(impl<()()> for BitSet);
251operator!(impl<('a)()> for &'a BitSet);
252operator!(impl<()()> for AtomicBitSet);
253operator!(impl<('a)()> for &'a AtomicBitSet);
254operator!(impl<()(A)> for BitSetNot<A>);
255operator!(impl<('a)(A)> for &'a BitSetNot<A>);
256operator!(impl<()(A, B)> for BitSetAnd<A, B>);
257operator!(impl<('a)(A, B)> for &'a BitSetAnd<A, B>);
258operator!(impl<()(A, B)> for BitSetOr<A, B>);
259operator!(impl<('a)(A, B)> for &'a BitSetOr<A, B>);
260operator!(impl<()(A, B)> for BitSetXor<A, B>);
261operator!(impl<('a)(A, B)> for &'a BitSetXor<A, B>);
262operator!(impl<()()> for BitSetAll);
263operator!(impl<('a)()> for &'a BitSetAll);
264
265macro_rules! iterator {
266    ($bitset:ident) => {
267        impl FromIterator<Index> for $bitset {
268            fn from_iter<T>(iter: T) -> Self
269            where T: IntoIterator<Item = Index> {
270                let mut bitset = $bitset::new();
271                for item in iter {
272                    bitset.add(item);
273                }
274                bitset
275            }
276        }
277
278        impl<'a> FromIterator<&'a Index> for $bitset {
279            fn from_iter<T>(iter: T) -> Self
280            where T: IntoIterator<Item = &'a Index> {
281                let mut bitset = $bitset::new();
282                for item in iter {
283                    bitset.add(*item);
284                }
285                bitset
286            }
287        }
288
289        impl Extend<Index> for $bitset {
290            fn extend<T>(&mut self, iter: T)
291            where T: IntoIterator<Item = Index> {
292                for item in iter {
293                    self.add(item);
294                }
295            }
296        }
297
298        impl<'a> Extend<&'a Index> for $bitset {
299            fn extend<T>(&mut self, iter: T)
300            where T: IntoIterator<Item = &'a Index> {
301                for item in iter {
302                    self.add(*item);
303                }
304            }
305        }
306    };
307}
308
309iterator!(BitSet);
310iterator!(AtomicBitSet);
311
312#[cfg(test)]
313mod tests {
314    use crate::{BitSet, BitSetLike, BitSetXor, Index};
315
316    #[test]
317    fn operators() {
318        let mut bitset = BitSet::new();
319        bitset.add(1);
320        bitset.add(3);
321        bitset.add(5);
322        bitset.add(15);
323        bitset.add(200);
324        bitset.add(50001);
325
326        let mut other = BitSet::new();
327        other.add(1);
328        other.add(3);
329        other.add(50000);
330        other.add(50001);
331
332        {
333            let not = &bitset & !&bitset;
334            assert_eq!(not.iter().count(), 0);
335        }
336
337        {
338            let either = &bitset | &other;
339            let collected = either.iter().collect::<Vec<Index>>();
340            assert_eq!(collected, vec![1, 3, 5, 15, 200, 50000, 50001]);
341
342            let either_sanity = bitset.clone() | other.clone();
343            assert_eq!(collected, either_sanity.iter().collect::<Vec<Index>>());
344        }
345
346        {
347            let same = &bitset & &other;
348            let collected = same.iter().collect::<Vec<Index>>();
349            assert_eq!(collected, vec![1, 3, 50001]);
350
351            let same_sanity = bitset.clone() & other.clone();
352            assert_eq!(collected, same_sanity.iter().collect::<Vec<Index>>());
353        }
354
355        {
356            let exclusive = &bitset ^ &other;
357            let collected = exclusive.iter().collect::<Vec<Index>>();
358            assert_eq!(collected, vec![5, 15, 200, 50000]);
359
360            let exclusive_sanity = bitset.clone() ^ other.clone();
361            assert_eq!(
362                collected,
363                exclusive_sanity.iter().collect::<Vec<Index>>()
364            );
365        }
366    }
367
368    #[test]
369    fn xor() {
370        // 0011
371        let mut bitset = BitSet::new();
372        bitset.add(2);
373        bitset.add(3);
374        bitset.add(50000);
375
376        // 0101
377        let mut other = BitSet::new();
378        other.add(1);
379        other.add(3);
380        other.add(50000);
381        other.add(50001);
382
383        {
384            // 0110
385            let xor = BitSetXor(&bitset, &other);
386            let collected = xor.iter().collect::<Vec<Index>>();
387            assert_eq!(collected, vec![1, 2, 50001]);
388        }
389    }
390}
hibitset/ops.rs

hibitset/
ops.rs
