sdset/multi/
symmetric_difference.rs

1use crate::set::{Set, vec_sets_into_slices};
2use crate::two_minimums::{two_minimums, Minimums::*};
3use crate::{SetOperation, Collection};
4
5/// Represent the _symmetric difference_ set operation that will be applied to the slices.
6///
7/// # Examples
8/// ```
9/// # use sdset::Error;
10/// # fn try_main() -> Result<(), Error> {
11/// use sdset::multi::OpBuilder;
12/// use sdset::{SetOperation, Set, SetBuf};
13///
14/// let a = Set::new(&[1, 2, 4])?;
15/// let b = Set::new(&[2, 3, 5, 7])?;
16/// let c = Set::new(&[4, 6, 7])?;
17///
18/// let op = OpBuilder::from_vec(vec![a, b, c]).symmetric_difference();
19///
20/// let res: SetBuf<i32> = op.into_set_buf();
21/// assert_eq!(&res[..], &[1, 3, 5, 6]);
22/// # Ok(()) }
23/// # try_main().unwrap();
24/// ```
25#[derive(Clone)]
26pub struct SymmetricDifference<'a, T: 'a> {
27    slices: Vec<&'a [T]>,
28}
29
30impl<'a, T> SymmetricDifference<'a, T> {
31    /// Construct one with slices checked to be sorted and deduplicated.
32    pub fn new(slices: Vec<&'a Set<T>>) -> Self {
33        Self {
34            slices: vec_sets_into_slices(slices),
35        }
36    }
37}
38
39impl<'a, T: Ord> SymmetricDifference<'a, T> {
40    #[inline]
41    fn extend_collection<C, U, F, G>(mut self, output: &mut C, extend: F, push: G)
42    where C: Collection<U>,
43          F: Fn(&mut C, &'a [T]),
44          G: Fn(&mut C, &'a T),
45    {
46        loop {
47            match two_minimums(&self.slices) {
48                Two((i, f), (_, s)) => {
49                    if f != s {
50                        let off = self.slices[i].iter().take_while(|&e| e < s).count();
51                        extend(output, &self.slices[i][..off]);
52                        self.slices[i] = &self.slices[i][off..];
53                    }
54                    else {
55                        let mut count = 0;
56                        for slice in self.slices.iter_mut() {
57                            if slice.first() == Some(f) {
58                                count += 1;
59                                *slice = &slice[1..];
60                            }
61                        }
62                        // if count is odd
63                        if count % 2 != 0 {
64                            push(output, f);
65                        }
66                    }
67                },
68                One((i, _)) => {
69                    extend(output, self.slices[i]);
70                    break;
71                },
72                Nothing => break,
73            }
74        }
75    }
76}
77
78impl<'a, T: Ord + Clone> SetOperation<T> for SymmetricDifference<'a, T> {
79    fn extend_collection<C>(self, output: &mut C) where C: Collection<T> {
80        self.extend_collection(output, Collection::extend_from_slice, |v, x| v.push(x.clone()));
81    }
82}
83
84impl<'a, T: Ord> SetOperation<&'a T> for SymmetricDifference<'a, T> {
85    fn extend_collection<C>(self, output: &mut C) where C: Collection<&'a T> {
86        self.extend_collection(output, Collection::extend, Collection::push);
87    }
88}
89
90#[cfg(test)]
91mod tests {
92    use super::*;
93    use crate::set::{sort_dedup_vec, SetBuf};
94
95    quickcheck! {
96        fn qc_symmetric_difference(xss: Vec<Vec<i32>>) -> bool {
97            use std::collections::BTreeSet;
98            use std::iter::FromIterator;
99
100            // FIXME temporary hack (can have mutable parameters!)
101            let mut xss = xss;
102
103            for xs in &mut xss {
104                sort_dedup_vec(xs);
105            }
106
107            let x: SetBuf<i32> = {
108                let xss = xss.iter().map(|xs| xs.as_slice()).collect();
109                SymmetricDifference { slices: xss }.into_set_buf()
110            };
111
112            let mut y = BTreeSet::new();
113            for v in xss {
114                let x = BTreeSet::from_iter(v.iter().cloned());
115                y = y.symmetric_difference(&x).cloned().collect();
116            }
117            let y: Vec<_> = y.into_iter().collect();
118
119            x.as_slice() == y.as_slice()
120        }
121    }
122}
123
124#[cfg(all(feature = "unstable", test))]
125mod bench {
126    extern crate test;
127    use super::*;
128    use self::test::Bencher;
129    use crate::set::SetBuf;
130
131    #[bench]
132    fn two_slices_big(bench: &mut Bencher) {
133        let a: Vec<_> = (0..100).collect();
134        let b: Vec<_> = (1..101).collect();
135
136        bench.iter(|| {
137            let symdiff_: SetBuf<i32> = SymmetricDifference { slices: vec![&a, &b] }.into_set_buf();
138            test::black_box(|| symdiff_);
139        });
140    }
141
142    #[bench]
143    fn two_slices_big2(bench: &mut Bencher) {
144        let a: Vec<_> = (0..100).collect();
145        let b: Vec<_> = (51..151).collect();
146
147        bench.iter(|| {
148            let symdiff_: SetBuf<i32> = SymmetricDifference { slices: vec![&a, &b] }.into_set_buf();
149            test::black_box(|| symdiff_);
150        });
151    }
152
153    #[bench]
154    fn two_slices_big3(bench: &mut Bencher) {
155        let a: Vec<_> = (0..100).collect();
156        let b: Vec<_> = (100..200).collect();
157
158        bench.iter(|| {
159            let symdiff_: SetBuf<i32> = SymmetricDifference { slices: vec![&a, &b] }.into_set_buf();
160            test::black_box(|| symdiff_);
161        });
162    }
163
164    #[bench]
165    fn three_slices_big(bench: &mut Bencher) {
166        let a: Vec<_> = (0..100).collect();
167        let b: Vec<_> = (1..101).collect();
168        let c: Vec<_> = (2..102).collect();
169
170        bench.iter(|| {
171            let symdiff_: SetBuf<i32> = SymmetricDifference { slices: vec![&a, &b, &c] }.into_set_buf();
172            test::black_box(|| symdiff_);
173        });
174    }
175
176    #[bench]
177    fn three_slices_big2(bench: &mut Bencher) {
178        let a: Vec<_> = (0..100).collect();
179        let b: Vec<_> = (34..134).collect();
180        let c: Vec<_> = (66..167).collect();
181
182        bench.iter(|| {
183            let symdiff_: SetBuf<i32> = SymmetricDifference { slices: vec![&a, &b, &c] }.into_set_buf();
184            test::black_box(|| symdiff_);
185        });
186    }
187
188    #[bench]
189    fn three_slices_big3(bench: &mut Bencher) {
190        let a: Vec<_> = (0..100).collect();
191        let b: Vec<_> = (100..200).collect();
192        let c: Vec<_> = (200..300).collect();
193
194        bench.iter(|| {
195            let symdiff_: SetBuf<i32> = SymmetricDifference { slices: vec![&a, &b, &c] }.into_set_buf();
196            test::black_box(|| symdiff_);
197        });
198    }
199}
sdset/multi/symmetric_difference.rs

sdset/multi/
symmetric_difference.rs
