sdset/duo/
difference.rs

1use crate::set::Set;
2use crate::{exponential_offset_ge, SetOperation, Collection};
3
4/// Represent the _difference_ set operation that will be applied to two slices.
5///
6/// # Examples
7/// ```
8/// # use sdset::Error;
9/// # fn try_main() -> Result<(), Error> {
10/// use sdset::duo::OpBuilder;
11/// use sdset::{SetOperation, Set, SetBuf};
12///
13/// let a = Set::new(&[1, 2, 4, 6, 7])?;
14/// let b = Set::new(&[2, 3, 4, 5, 6, 7])?;
15///
16/// let op = OpBuilder::new(a, b).difference();
17///
18/// let res: SetBuf<i32> = op.into_set_buf();
19/// assert_eq!(&res[..], &[1]);
20/// # Ok(()) }
21/// # try_main().unwrap();
22/// ```
23#[derive(Copy, Clone)]
24pub struct Difference<'a, T: 'a> {
25    a: &'a [T],
26    b: &'a [T],
27}
28
29impl<'a, T> Difference<'a, T> {
30    /// Construct one with slices checked to be sorted and deduplicated.
31    pub fn new(a: &'a Set<T>, b: &'a Set<T>) -> Self {
32        Self {
33            a: a.as_slice(),
34            b: b.as_slice(),
35        }
36    }
37}
38
39impl<'a, T: Ord> Difference<'a, T> {
40    #[inline]
41    fn extend_collection<C, U, F>(mut self, output: &mut C, extend: F)
42    where C: Collection<U>,
43          F: Fn(&mut C, &'a [T])
44    {
45        while let Some(first) = self.a.first() {
46            self.b = exponential_offset_ge(self.b, first);
47            let minimum = self.b.first();
48
49            match minimum {
50                Some(min) if min == first => self.a = exponential_offset_ge(&self.a[1..], min),
51                Some(min) => {
52                    let off = self.a.iter().take_while(|&x| x < min).count();
53                    extend(output, &self.a[..off]);
54
55                    self.a = &self.a[off..];
56                },
57                None => {
58                    extend(output, self.a);
59                    break;
60                },
61            }
62        }
63    }
64}
65
66impl<'a, T: Ord + Clone> SetOperation<T> for Difference<'a, T> {
67    fn extend_collection<C>(self, output: &mut C) where C: Collection<T> {
68        self.extend_collection(output, Collection::extend_from_slice)
69    }
70}
71
72impl<'a, T: Ord> SetOperation<&'a T> for Difference<'a, T> {
73    fn extend_collection<C>(self, output: &mut C) where C: Collection<&'a T> {
74        self.extend_collection(output, Collection::extend)
75    }
76}
77
78#[cfg(test)]
79mod tests {
80    use super::*;
81    use crate::set::{sort_dedup_vec, SetBuf};
82
83    #[test]
84    fn two_slices() {
85        let a = &[1, 2, 3];
86        let b = &[2, 4];
87
88        let union_: SetBuf<i32> = Difference { a: a, b: b }.into_set_buf();
89        assert_eq!(&union_[..], &[1, 3]);
90    }
91
92    #[test]
93    fn two_slices_special_case() {
94        let a = &[1, 2, 3];
95        let b = &[3];
96
97        let union_: SetBuf<i32> = Difference { a: a, b: b }.into_set_buf();
98        assert_eq!(&union_[..], &[1, 2]);
99    }
100
101    quickcheck! {
102        fn qc_difference(a: Vec<i32>, b: Vec<i32>) -> bool {
103            use std::collections::BTreeSet;
104            use std::iter::FromIterator;
105
106            let mut a = a;
107            let mut b = b;
108
109            sort_dedup_vec(&mut a);
110            sort_dedup_vec(&mut b);
111
112            let x: SetBuf<i32> = Difference { a: &a, b: &b }.into_set_buf();
113
114            let a = BTreeSet::from_iter(a);
115            let b = BTreeSet::from_iter(b);
116            let y = a.difference(&b);
117            let y: Vec<_> = y.cloned().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 difference_: SetBuf<i32> = Difference { a: &a, b: &b }.into_set_buf();
138            test::black_box(|| difference_);
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 difference_: SetBuf<i32> = Difference { a: &a, b: &b }.into_set_buf();
149            test::black_box(|| difference_);
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 difference_: SetBuf<i32> = Difference { a: &a, b: &b }.into_set_buf();
160            test::black_box(|| difference_);
161        });
162    }
163}
sdset/duo/difference.rs

sdset/duo/
difference.rs
