sdset/duo/
symmetric_difference.rs

1use std::cmp::Ordering;
2use crate::set::Set;
3use crate::{SetOperation, Collection};
4
5/// Represent the _symmetric difference_ set operation that will be applied to two slices.
6///
7/// # Examples
8/// ```
9/// # use sdset::Error;
10/// # fn try_main() -> Result<(), Error> {
11/// use sdset::duo::OpBuilder;
12/// use sdset::{SetOperation, Set, SetBuf};
13///
14/// let a = Set::new(&[1, 2, 4, 6, 7])?;
15/// let b = Set::new(&[2, 3, 4, 5, 6, 7])?;
16///
17/// let op = OpBuilder::new(a, b).symmetric_difference();
18///
19/// let res: SetBuf<i32> = op.into_set_buf();
20/// assert_eq!(&res[..], &[1, 3, 5]);
21/// # Ok(()) }
22/// # try_main().unwrap();
23/// ```
24#[derive(Copy, Clone)]
25pub struct SymmetricDifference<'a, T: 'a> {
26    a: &'a [T],
27    b: &'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(a: &'a Set<T>, b: &'a Set<T>) -> Self {
33        Self {
34            a: a.as_slice(),
35            b: b.as_slice(),
36        }
37    }
38}
39
40impl<'a, T: Ord> SymmetricDifference<'a, T> {
41    #[inline]
42    fn extend_collection<C, U, F>(mut self, output: &mut C, extend: F)
43    where C: Collection<U>,
44          F: Fn(&mut C, &'a [T])
45    {
46        loop {
47            match (self.a.first(), self.b.first()) {
48                (Some(a), Some(b)) => {
49                    match a.cmp(b) {
50                        Ordering::Less => {
51                            let off = self.a.iter().take_while(|&e| e < b).count();
52                            extend(output, &self.a[..off]);
53                            self.a = &self.a[off..];
54                        },
55                        Ordering::Equal => {
56                            let off = self.a.iter().zip(self.b.iter()).take_while(|(a, b)| a == b).count();
57                            self.a = &self.a[off..];
58                            self.b = &self.b[off..];
59                        },
60                        Ordering::Greater => {
61                            let off = self.b.iter().take_while(|&e| e < a).count();
62                            extend(output, &self.b[..off]);
63                            self.b = &self.b[off..];
64                        },
65                    }
66                },
67                (None, Some(_)) => {
68                    extend(output, self.b);
69                    break;
70                },
71                (Some(_), None) => {
72                    extend(output, self.a);
73                    break;
74                },
75                (None, None) => break,
76            }
77        }
78    }
79}
80
81impl<'a, T: Ord + Clone> SetOperation<T> for SymmetricDifference<'a, T> {
82    fn extend_collection<C>(self, output: &mut C) where C: Collection<T> {
83        self.extend_collection(output, Collection::extend_from_slice)
84    }
85}
86
87impl<'a, T: Ord> SetOperation<&'a T> for SymmetricDifference<'a, T> {
88    fn extend_collection<C>(self, output: &mut C) where C: Collection<&'a T> {
89        self.extend_collection(output, Collection::extend)
90    }
91}
92
93#[cfg(test)]
94mod tests {
95    use super::*;
96    use crate::set::{sort_dedup_vec, SetBuf};
97
98    quickcheck! {
99        fn qc_symmetric_difference(a: Vec<i32>, b: Vec<i32>) -> bool {
100            use std::collections::BTreeSet;
101            use std::iter::FromIterator;
102
103            let mut a = a;
104            let mut b = b;
105
106            sort_dedup_vec(&mut a);
107            sort_dedup_vec(&mut b);
108
109            let x: SetBuf<i32> = SymmetricDifference { a: &a, b: &b }.into_set_buf();
110
111            let a = BTreeSet::from_iter(a);
112            let b = BTreeSet::from_iter(b);
113            let y = a.symmetric_difference(&b);
114            let y: Vec<_> = y.cloned().collect();
115
116            x.as_slice() == y.as_slice()
117        }
118    }
119}
120
121#[cfg(all(feature = "unstable", test))]
122mod bench {
123    extern crate test;
124    use super::*;
125    use self::test::Bencher;
126    use crate::set::SetBuf;
127
128    #[bench]
129    fn two_slices_big(bench: &mut Bencher) {
130        let a: Vec<_> = (0..100).collect();
131        let b: Vec<_> = (1..101).collect();
132
133        bench.iter(|| {
134            let symmetric_difference_: SetBuf<i32> = SymmetricDifference { a: &a, b: &b }.into_set_buf();
135            test::black_box(|| symmetric_difference_);
136        });
137    }
138
139    #[bench]
140    fn two_slices_big2(bench: &mut Bencher) {
141        let a: Vec<_> = (0..100).collect();
142        let b: Vec<_> = (51..151).collect();
143
144        bench.iter(|| {
145            let symmetric_difference_: SetBuf<i32> = SymmetricDifference { a: &a, b: &b }.into_set_buf();
146            test::black_box(|| symmetric_difference_);
147        });
148    }
149
150    #[bench]
151    fn two_slices_big3(bench: &mut Bencher) {
152        let a: Vec<_> = (0..100).collect();
153        let b: Vec<_> = (100..200).collect();
154
155        bench.iter(|| {
156            let symmetric_difference_: SetBuf<i32> = SymmetricDifference { a: &a, b: &b }.into_set_buf();
157            test::black_box(|| symmetric_difference_);
158        });
159    }
160}
sdset/duo/symmetric_difference.rs

sdset/duo/
symmetric_difference.rs
