negatable_set/
lib.rs

1use core::{
2    fmt,
3    fmt::{Debug, Write},
4    hash::Hash,
5    mem,
6    ops::{BitAnd, BitAndAssign, BitOr, BitOrAssign, BitXor, BitXorAssign, Not, Sub, SubAssign},
7};
8#[cfg(feature = "serde")]
9use serde::{
10    de::{Deserialize, Deserializer},
11    ser::{Serialize, Serializer},
12};
13#[cfg(feature = "vc")]
14use smallvec::Array;
15use std::{
16    collections::{BTreeSet, HashSet},
17    hash::BuildHasher,
18};
19#[cfg(feature = "vc")]
20use vec_collections::VecSet;
21#[cfg(test)]
22#[macro_use]
23mod test_macros;
24
25#[derive(Default)]
26pub struct NegatableSet<I> {
27    elements: I,
28    negated: bool,
29}
30
31#[cfg(feature = "serde")]
32impl<A> Serialize for NegatableSet<A>
33where
34    A: MutableSet + Serialize,
35{
36    fn serialize<S: Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error> {
37        (&self.elements, &self.negated).serialize(serializer)
38    }
39}
40
41#[cfg(feature = "serde")]
42impl<'de, A> Deserialize<'de> for NegatableSet<A>
43where
44    A: MutableSet + Deserialize<'de>,
45{
46    fn deserialize<D: Deserializer<'de>>(deserializer: D) -> Result<Self, D::Error> {
47        let (elements, negated) = <(A, bool)>::deserialize(deserializer)?;
48        Ok(Self::new(elements, negated))
49    }
50}
51
52impl<I: Clone> Clone for NegatableSet<I> {
53    fn clone(&self) -> Self {
54        Self {
55            elements: self.elements.clone(),
56            negated: self.negated,
57        }
58    }
59}
60
61impl<I: Hash> Hash for NegatableSet<I> {
62    fn hash<H: core::hash::Hasher>(&self, state: &mut H) {
63        self.elements.hash(state);
64        self.negated.hash(state);
65    }
66}
67
68impl<I: PartialEq> PartialEq for NegatableSet<I> {
69    fn eq(&self, other: &Self) -> bool {
70        self.elements == other.elements && self.negated == other.negated
71    }
72}
73
74impl<I: Eq> Eq for NegatableSet<I> {}
75
76impl<I: MutableSet> Debug for NegatableSet<I> {
77    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
78        if self.negated {
79            f.write_char('!')?;
80        }
81        f.debug_set().entries(self.elements.iter()).finish()
82    }
83}
84
85impl<I: MutableSet + Default> NegatableSet<I> {
86    pub fn constant(value: bool) -> Self {
87        Self::new(I::default(), value)
88    }
89
90    pub fn empty() -> Self {
91        false.into()
92    }
93
94    pub fn all() -> Self {
95        true.into()
96    }
97}
98
99impl<I: MutableSet> NegatableSet<I> {
100    fn new(elements: I, negated: bool) -> Self {
101        Self { elements, negated }
102    }
103
104    pub fn is_empty(&self) -> bool {
105        !self.negated && self.elements.is_empty()
106    }
107
108    pub fn is_all(&self) -> bool {
109        self.negated && self.elements.is_empty()
110    }
111
112    pub fn into_elements(self) -> I {
113        self.elements
114    }
115
116    pub fn elements(&self) -> &I {
117        &self.elements
118    }
119
120    pub fn elements_mut(&mut self) -> &mut I {
121        &mut self.elements
122    }
123}
124
125pub trait MutableSet {
126    type Item: Debug + 'static;
127
128    fn iter<'a>(&'a self) -> Box<dyn Iterator<Item = &'a Self::Item> + 'a>;
129
130    fn is_empty(&self) -> bool;
131
132    fn contains(&self, value: &Self::Item) -> bool;
133
134    fn insert(&mut self, value: Self::Item);
135
136    fn remove(&mut self, value: &Self::Item);
137
138    fn is_subset(&self, rhs: &Self) -> bool;
139
140    fn is_superset(&self, rhs: &Self) -> bool;
141
142    fn is_disjoint(&self, rhs: &Self) -> bool;
143}
144
145#[cfg(feature = "vc")]
146impl<T: Ord + Debug + 'static, A: Array<Item = T>> MutableSet for VecSet<A> {
147    type Item = T;
148
149    fn iter<'a>(&'a self) -> Box<dyn Iterator<Item = &'a Self::Item> + 'a> {
150        Box::new(VecSet::iter(self))
151    }
152
153    fn is_empty(&self) -> bool {
154        VecSet::is_empty(self)
155    }
156
157    fn contains(&self, value: &Self::Item) -> bool {
158        VecSet::contains(self, value)
159    }
160
161    fn insert(&mut self, value: Self::Item) {
162        VecSet::insert(self, value)
163    }
164
165    fn remove(&mut self, value: &Self::Item) {
166        VecSet::remove(self, value)
167    }
168
169    fn is_subset(&self, rhs: &Self) -> bool {
170        VecSet::is_subset(self, rhs)
171    }
172
173    fn is_superset(&self, rhs: &Self) -> bool {
174        VecSet::is_superset(self, rhs)
175    }
176
177    fn is_disjoint(&self, rhs: &Self) -> bool {
178        VecSet::is_disjoint(self, rhs)
179    }
180}
181
182impl<T: Ord + Debug + 'static> MutableSet for BTreeSet<T> {
183    type Item = T;
184
185    fn iter<'a>(&'a self) -> Box<dyn Iterator<Item = &'a Self::Item> + 'a> {
186        Box::new(BTreeSet::iter(self))
187    }
188
189    fn is_empty(&self) -> bool {
190        BTreeSet::is_empty(self)
191    }
192
193    fn contains(&self, value: &Self::Item) -> bool {
194        BTreeSet::contains(self, value)
195    }
196
197    fn insert(&mut self, value: Self::Item) {
198        BTreeSet::insert(self, value);
199    }
200
201    fn remove(&mut self, value: &Self::Item) {
202        BTreeSet::remove(self, value);
203    }
204
205    fn is_subset(&self, rhs: &Self) -> bool {
206        BTreeSet::is_subset(self, rhs)
207    }
208
209    fn is_superset(&self, rhs: &Self) -> bool {
210        BTreeSet::is_superset(self, rhs)
211    }
212
213    fn is_disjoint(&self, rhs: &Self) -> bool {
214        BTreeSet::is_disjoint(self, rhs)
215    }
216}
217
218impl<T: Hash + Eq + Debug + 'static, S: BuildHasher + Default> MutableSet for HashSet<T, S> {
219    type Item = T;
220
221    fn iter<'a>(&'a self) -> Box<dyn Iterator<Item = &'a Self::Item> + 'a> {
222        Box::new(HashSet::iter(self))
223    }
224
225    fn is_empty(&self) -> bool {
226        HashSet::is_empty(self)
227    }
228
229    fn contains(&self, value: &Self::Item) -> bool {
230        HashSet::contains(self, value)
231    }
232
233    fn insert(&mut self, value: Self::Item) {
234        HashSet::insert(self, value);
235    }
236
237    fn remove(&mut self, value: &Self::Item) {
238        HashSet::remove(self, value);
239    }
240
241    fn is_subset(&self, rhs: &Self) -> bool {
242        HashSet::is_subset(self, rhs)
243    }
244
245    fn is_superset(&self, rhs: &Self) -> bool {
246        HashSet::is_superset(self, rhs)
247    }
248
249    fn is_disjoint(&self, rhs: &Self) -> bool {
250        HashSet::is_disjoint(self, rhs)
251    }
252}
253
254impl<I: MutableSet + Default> From<bool> for NegatableSet<I> {
255    fn from(value: bool) -> Self {
256        Self::constant(value)
257    }
258}
259
260impl<I: MutableSet> From<I> for NegatableSet<I> {
261    fn from(value: I) -> Self {
262        Self::new(value, false)
263    }
264}
265
266impl<I: MutableSet> NegatableSet<I> {
267    pub fn contains(&self, value: &I::Item) -> bool {
268        self.negated ^ self.elements.contains(value)
269    }
270
271    pub fn insert(&mut self, that: I::Item) {
272        if !self.negated {
273            self.elements.insert(that)
274        } else {
275            self.elements.remove(&that)
276        }
277    }
278
279    pub fn is_superset(&self, that: &Self) -> bool {
280        !self.is_subset(that)
281    }
282
283    pub fn is_subset(&self, that: &Self) -> bool {
284        match (self.negated, that.negated) {
285            (false, false) => self.elements.is_subset(&that.elements),
286            (false, true) => self.elements.is_disjoint(&that.elements),
287            (true, false) => false,
288            (true, true) => self.elements.is_superset(&that.elements),
289        }
290    }
291
292    pub fn is_disjoint(&self, that: &Self) -> bool {
293        match (self.negated, that.negated) {
294            (false, false) => self.elements.is_disjoint(&that.elements),
295            (false, true) => self.elements.is_subset(&that.elements),
296            (true, false) => self.elements.is_superset(&that.elements),
297            (true, true) => false,
298        }
299    }
300}
301
302impl<I: MutableSet> NegatableSet<I>
303where
304    I::Item: Ord + Clone,
305{
306    pub fn remove(&mut self, that: &I::Item) {
307        if self.negated {
308            self.elements.insert(that.clone())
309        } else {
310            self.elements.remove(that)
311        }
312    }
313}
314
315impl<'a, I: MutableSet + 'a> BitAnd for &'a NegatableSet<I>
316where
317    &'a I: BitAnd<Output = I>,
318    &'a I: BitOr<Output = I>,
319    &'a I: Sub<Output = I>,
320{
321    type Output = NegatableSet<I>;
322    fn bitand(self, that: Self) -> Self::Output {
323        match (self.negated, that.negated) {
324            // intersection of elements
325            (false, false) => Self::Output::new(&self.elements & &that.elements, false),
326            // remove elements from self
327            (false, true) => Self::Output::new(&self.elements - &that.elements, false),
328            // remove elements from that
329            (true, false) => Self::Output::new(&that.elements - &self.elements, false),
330            // union of elements
331            (true, true) => Self::Output::new(&that.elements | &self.elements, true),
332        }
333    }
334}
335
336impl<I: MutableSet> BitAndAssign for NegatableSet<I>
337where
338    I: BitAndAssign,
339    I: BitOrAssign,
340    I: SubAssign,
341{
342    fn bitand_assign(&mut self, that: Self) {
343        match (self.negated, that.negated) {
344            // intersection of elements
345            (false, false) => {
346                self.elements &= that.elements;
347                self.negated = false;
348            }
349            // remove elements from self
350            (false, true) => {
351                self.elements -= that.elements;
352                self.negated = false;
353            }
354            // remove elements from that
355            (true, false) => {
356                let mut that = that;
357                mem::swap(&mut that.elements, &mut self.elements);
358                self.elements -= that.elements;
359                self.negated = false;
360            }
361            // union of elements
362            (true, true) => {
363                self.elements |= that.elements;
364                self.negated = true;
365            }
366        };
367    }
368}
369
370impl<'a, I: MutableSet> BitOr for &'a NegatableSet<I>
371where
372    &'a I: BitAnd<Output = I>,
373    &'a I: BitOr<Output = I>,
374    &'a I: Sub<Output = I>,
375{
376    type Output = NegatableSet<I>;
377    fn bitor(self, that: Self) -> Self::Output {
378        match (self.negated, that.negated) {
379            // union of elements
380            (false, false) => Self::Output::new(&self.elements | &that.elements, false),
381            // remove holes from that
382            (false, true) => Self::Output::new(&that.elements - &self.elements, true),
383            // remove holes from self
384            (true, false) => Self::Output::new(&self.elements - &that.elements, true),
385            // intersection of holes
386            (true, true) => Self::Output::new(&that.elements & &self.elements, true),
387        }
388    }
389}
390
391impl<I: MutableSet> BitOrAssign for NegatableSet<I>
392where
393    I: BitAndAssign,
394    I: BitOrAssign,
395    I: SubAssign,
396{
397    fn bitor_assign(&mut self, that: Self) {
398        match (self.negated, that.negated) {
399            // union of elements
400            (false, false) => {
401                self.elements |= that.elements;
402                self.negated = false;
403            }
404            // remove holes from that
405            (false, true) => {
406                let mut that = that;
407                mem::swap(&mut that.elements, &mut self.elements);
408                self.elements -= that.elements;
409                self.negated = true;
410            }
411            // remove holes from self
412            (true, false) => {
413                self.elements -= that.elements;
414                self.negated = true;
415            }
416            // intersection of holes
417            (true, true) => {
418                self.elements &= that.elements;
419                self.negated = true;
420            }
421        };
422    }
423}
424
425impl<'a, I: MutableSet> BitXor for &'a NegatableSet<I>
426where
427    &'a I: BitXor<Output = I>,
428{
429    type Output = NegatableSet<I>;
430    fn bitxor(self, that: Self) -> Self::Output {
431        Self::Output::new(&self.elements ^ &that.elements, self.negated ^ that.negated)
432    }
433}
434
435impl<I: MutableSet> BitXorAssign for NegatableSet<I>
436where
437    I: BitXorAssign,
438{
439    fn bitxor_assign(&mut self, that: Self) {
440        self.elements ^= that.elements;
441        self.negated ^= that.negated;
442    }
443}
444
445#[allow(clippy::suspicious_arithmetic_impl)]
446impl<'a, I: MutableSet> Sub for &'a NegatableSet<I>
447where
448    &'a I: BitAnd<Output = I>,
449    &'a I: BitOr<Output = I>,
450    &'a I: Sub<Output = I>,
451{
452    type Output = NegatableSet<I>;
453    fn sub(self, that: Self) -> Self::Output {
454        match (self.negated, that.negated) {
455            // intersection of elements
456            (false, false) => Self::Output::new(&self.elements - &that.elements, false),
457            // keep only holes of that
458            (false, true) => Self::Output::new(&self.elements & &that.elements, false),
459            // add holes from that
460            (true, false) => Self::Output::new(&self.elements | &that.elements, true),
461            // union of elements
462            (true, true) => Self::Output::new(&that.elements - &self.elements, false),
463        }
464    }
465}
466
467impl<I: MutableSet> SubAssign for NegatableSet<I>
468where
469    I: BitAndAssign,
470    I: BitOrAssign,
471    I: SubAssign,
472{
473    fn sub_assign(&mut self, that: Self) {
474        match (self.negated, that.negated) {
475            // intersection of elements
476            (false, false) => {
477                self.elements -= that.elements;
478                self.negated = false;
479            }
480            // keep only holes of that
481            (false, true) => {
482                self.elements &= that.elements;
483                self.negated = false;
484            }
485            // add holes from that
486            (true, false) => {
487                self.elements |= that.elements;
488                self.negated = true;
489            }
490            // union of elements
491            (true, true) => {
492                let mut that = that;
493                mem::swap(&mut that.elements, &mut self.elements);
494                self.elements -= that.elements;
495                self.negated = false;
496            }
497        }
498    }
499}
500
501impl<'a, I: MutableSet + Clone> Not for &'a NegatableSet<I> {
502    type Output = NegatableSet<I>;
503    fn not(self) -> Self::Output {
504        Self::Output::new(self.elements.clone(), !self.negated)
505    }
506}
507
508impl<I: MutableSet + Clone> Not for NegatableSet<I> {
509    type Output = NegatableSet<I>;
510    fn not(self) -> Self::Output {
511        Self::Output::new(self.elements, !self.negated)
512    }
513}
514
515#[cfg(test)]
516mod tests {
517    #[allow(dead_code)]
518    use super::*;
519    use quickcheck::*;
520    use quickcheck_macros::quickcheck;
521    use vec_collections::VecSet;
522
523    #[cfg(feature = "vc")]
524    type Test = NegatableSet<VecSet<[i64; 4]>>;
525
526    #[cfg(feature = "vc")]
527    impl<T: Arbitrary + Ord + Copy + Default + Debug> Arbitrary for NegatableSet<VecSet<[T; 4]>> {
528        fn arbitrary<G: Gen>(g: &mut G) -> Self {
529            let mut elements: Vec<T> = Arbitrary::arbitrary(g);
530            elements.truncate(2);
531            let negated: bool = Arbitrary::arbitrary(g);
532            NegatableSet::new(elements.into(), negated)
533        }
534    }
535
536    impl<T: Arbitrary + Ord + Copy + Default + Debug> Arbitrary for NegatableSet<BTreeSet<T>> {
537        fn arbitrary<G: Gen>(g: &mut G) -> Self {
538            let mut elements: Vec<T> = Arbitrary::arbitrary(g);
539            elements.truncate(2);
540            let negated: bool = Arbitrary::arbitrary(g);
541            NegatableSet::new(elements.into_iter().collect(), negated)
542        }
543    }
544
545    #[allow(dead_code)]
546    /// just a helper to get good output when a check fails
547    fn print_on_failure_unary<E: Debug, R: Eq + Debug>(x: E, expected: R, actual: R) -> bool {
548        let res = expected == actual;
549        if !res {
550            println!("x:{:?} expected:{:?} actual:{:?}", x, expected, actual);
551        }
552        res
553    }
554
555    #[cfg(feature = "vc")]
556    fn binary_op(a: &Test, b: &Test, r: &Test, op: impl Fn(bool, bool) -> bool) -> bool {
557        let mut samples: BTreeSet<i64> = BTreeSet::new();
558        samples.extend(a.elements.iter().cloned());
559        samples.extend(b.elements.iter().cloned());
560        samples.insert(core::i64::MIN);
561        samples.iter().all(|e| {
562            let expected = op(a.contains(e), b.contains(e));
563            let actual = r.contains(e);
564            if expected != actual {
565                println!(
566                    "{:?}!={:?} at {:?} {:?} {:?} {:?}",
567                    expected, actual, e, a, b, r
568                );
569            }
570            expected == actual
571        })
572    }
573
574    #[cfg(feature = "vc")]
575    fn binary_property(a: &Test, b: &Test, r: bool, op: impl Fn(bool, bool) -> bool) -> bool {
576        let mut samples: BTreeSet<i64> = BTreeSet::new();
577        samples.extend(a.elements.iter().cloned());
578        samples.extend(b.elements.iter().cloned());
579        samples.insert(core::i64::MIN);
580        if r {
581            samples.iter().all(|e| {
582                let expected = op(a.contains(e), b.contains(e));
583                if !expected {
584                    println!(
585                        "{:?} is false at {:?}\na {:?}\nb {:?}\nr {:?}",
586                        expected, e, a, b, r
587                    );
588                }
589                expected
590            })
591        } else {
592            samples.iter().any(|e| !op(a.contains(e), b.contains(e)))
593        }
594    }
595
596    quickcheck::quickcheck! {
597
598        #[cfg(feature = "serde")]
599        fn serde_roundtrip(reference: NegatableSet<BTreeSet<u64>>) -> bool {
600            let bytes = serde_json::to_vec(&reference).unwrap();
601            let deser = serde_json::from_slice(&bytes).unwrap();
602            reference == deser
603        }
604
605        #[cfg(feature = "vc")]
606        fn is_disjoint_sample(a: Test, b: Test) -> bool {
607            binary_property(&a, &b, a.is_disjoint(&b), |a, b| !(a & b))
608        }
609
610        #[cfg(feature = "vc")]
611        fn is_subset_sample(a: Test, b: Test) -> bool {
612            binary_property(&a, &b, a.is_subset(&b), |a, b| !a | b)
613        }
614
615        #[cfg(feature = "vc")]
616        fn union_sample(a: Test, b: Test) -> bool {
617            binary_op(&a, &b, &(&a | &b), |a, b| a | b)
618        }
619
620        #[cfg(feature = "vc")]
621        fn intersection_sample(a: Test, b: Test) -> bool {
622            binary_op(&a, &b, &(&a & &b), |a, b| a & b)
623        }
624
625        #[cfg(feature = "vc")]
626        fn xor_sample(a: Test, b: Test) -> bool {
627            binary_op(&a, &b, &(&a ^ &b), |a, b| a ^ b)
628        }
629
630        #[cfg(feature = "vc")]
631        fn diff_sample(a: Test, b: Test) -> bool {
632            binary_op(&a, &b, &(&a - &b), |a, b| a & !b)
633        }
634    }
635
636    #[cfg(feature = "vc")]
637    bitop_assign_consistent!(Test);
638
639    #[cfg(feature = "vc")]
640    bitop_symmetry!(Test);
641
642    #[cfg(feature = "vc")]
643    bitop_empty!(Test);
644
645    #[cfg(feature = "vc")]
646    bitop_sub_not_all!(Test);
647}
negatable_set/lib.rs

negatable_set/
lib.rs
