sdset/duo/
difference_by_key.rs

1use crate::set::Set;
2use crate::{exponential_offset_ge_by_key, SetOperation, Collection};
3
4/// Represent the _difference_ set operation that will be applied to two slices of different types.
5///
6/// # Examples
7/// ```
8/// # use sdset::Error;
9/// # fn try_main() -> Result<(), Error> {
10/// use sdset::duo::OpBuilderByKey;
11/// use sdset::{SetOperation, Set, SetBuf};
12///
13/// #[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
14/// struct Foo { a: i32, b: u8 }
15///
16/// let a = Set::new(&[
17///     Foo{ a: 1, b: 6 },
18///     Foo{ a: 1, b: 7 },
19///     Foo{ a: 1, b: 8 },
20///     Foo{ a: 2, b: 9 },
21///     Foo{ a: 2, b: 10 },
22///     Foo{ a: 3, b: 10 },
23/// ])?;
24/// let b = Set::new(&[1, 3, 4, 5]).unwrap();
25///
26/// // Return the field of Foo that will be used for comparison
27/// let f = |x: &Foo| x.a;
28///
29/// // directly use the i32 for comparison
30/// let g = |x: &i32| *x;
31///
32/// let op = OpBuilderByKey::new(a, b, f, g).difference();
33/// let res: SetBuf<Foo> = op.into_set_buf();
34///
35/// assert_eq!(res.as_slice(), &[Foo{ a: 2, b: 9 }, Foo{ a: 2, b: 10 }][..]);
36/// # Ok(()) }
37/// # try_main().unwrap();
38/// ```
39#[derive(Copy, Clone)]
40pub struct DifferenceByKey<'a, T: 'a, U: 'a, F, G, K>
41where F: Fn(&T) -> K,
42      G: Fn(&U) -> K,
43      K: Ord,
44{
45    a: &'a [T],
46    b: &'a [U],
47    f: F,
48    g: G,
49}
50
51impl<'a, T, U, F, G, K> DifferenceByKey<'a, T, U, F, G, K>
52where F: Fn(&T) -> K,
53      G: Fn(&U) -> K,
54      K: Ord,
55{
56    /// Construct one with slices checked to be sorted and deduplicated.
57    pub fn new(a: &'a Set<T>, b: &'a Set<U>, f: F, g: G) -> Self {
58        Self {
59            a: a.as_slice(),
60            b: b.as_slice(),
61            f: f,
62            g: g,
63        }
64    }
65}
66
67impl<'a, T, U, F, G, K> DifferenceByKey<'a, T, U, F, G, K>
68where F: Fn(&T) -> K,
69      G: Fn(&U) -> K,
70      K: Ord,
71{
72    fn extend_collection<C, X, E>(mut self, output: &mut C, extend: E)
73    where C: Collection<X>,
74          E: Fn(&mut C, &'a [T]),
75    {
76        while let Some(first) = self.a.first().map(|x| (self.f)(x)) {
77            self.b = exponential_offset_ge_by_key(self.b, &first, &self.g);
78
79            match self.b.first().map(|x| (self.g)(x)) {
80                Some(min) => {
81                    if min == first {
82                        self.a = exponential_offset_ge_by_key(&self.a[1..], &min, &self.f)
83                    } else {
84                        let off = self.a.iter().take_while(|&x| (self.f)(x) < min).count();
85                        extend(output, &self.a[..off]);
86
87                        self.a = &self.a[off..]
88                    }
89                },
90                None => {
91                    extend(output, self.a);
92                    break;
93                },
94            }
95        }
96    }
97}
98
99impl<'a, T, U, F, G, K> SetOperation<T> for DifferenceByKey<'a, T, U, F, G, K>
100where T: Clone,
101      F: Fn(&T) -> K,
102      G: Fn(&U) -> K,
103      K: Ord,
104{
105    fn extend_collection<C>(self, output: &mut C) where C: Collection<T> {
106        self.extend_collection(output, Collection::extend_from_slice)
107    }
108}
109
110impl<'a, T, U, F, G, K> SetOperation<&'a T> for DifferenceByKey<'a, T, U, F, G, K>
111where F: Fn(&T) -> K,
112      G: Fn(&U) -> K,
113      K: Ord,
114{
115    fn extend_collection<C>(self, output: &mut C) where C: Collection<&'a T> {
116        self.extend_collection(output, Collection::extend)
117    }
118}
119
120#[cfg(test)]
121mod tests {
122    use super::*;
123    use crate::set::{sort_dedup_vec, SetBuf};
124
125    #[derive(Debug, Clone, PartialEq, Eq)]
126    struct Foo {
127        a: i32,
128        b: i8,
129    }
130
131    #[test]
132    fn difference_empty_no_duplicates() {
133        let a = Set::new_unchecked(&[
134            Foo{ a: 1, b: 8 },
135            Foo{ a: 2, b: 9 },
136            Foo{ a: 3, b: 10 },
137            Foo{ a: 4, b: 11 },
138            Foo{ a: 5, b: 12 },
139        ]);
140        let b = Set::new(&[1, 2, 3, 4, 5]).unwrap();
141
142        let difference: SetBuf<Foo> = DifferenceByKey::new(a, b, |x| x.a, |&x| x).into_set_buf();
143
144        assert!(difference.is_empty());
145    }
146
147    #[test]
148    fn difference_empty_duplicate_relations() {
149        let a = Set::new_unchecked(&[
150            Foo{ a: 1, b: 6 },
151            Foo{ a: 1, b: 7 },
152            Foo{ a: 1, b: 8 },
153            Foo{ a: 2, b: 9 },
154            Foo{ a: 2, b: 10 },
155        ]);
156        let b = Set::new(&[1, 2, 3, 4, 5]).unwrap();
157
158        let difference: SetBuf<Foo> = DifferenceByKey::new(a, b, |x| x.a, |&x| x).into_set_buf();
159
160        assert!(difference.is_empty());
161    }
162
163    #[test]
164    fn difference_non_empty_duplicate_relations() {
165        let a = Set::new_unchecked(&[
166            Foo{ a: 1, b: 6 },
167            Foo{ a: 1, b: 7 },
168            Foo{ a: 1, b: 8 },
169            Foo{ a: 2, b: 9 },
170            Foo{ a: 2, b: 10 },
171        ]);
172        let b = Set::new(&[1, 3, 4, 5]).unwrap();
173
174        let difference: SetBuf<Foo> = DifferenceByKey::new(a, b, |x| x.a, |&x| x).into_set_buf();
175
176        assert_eq!(difference.as_slice(), &[
177            Foo{ a: 2, b: 9  },
178            Foo{ a: 2, b: 10 },
179        ][..]);
180    }
181
182    quickcheck! {
183        fn qc_difference(a: Vec<i32>, b: Vec<i64>) -> bool {
184            use std::collections::BTreeSet;
185            use std::iter::FromIterator;
186
187            let mut a = a;
188            let mut b = b;
189
190            sort_dedup_vec(&mut a);
191            sort_dedup_vec(&mut b);
192
193            let x: SetBuf<i32> = {
194                let difference = DifferenceByKey { a: &a, b: &b, f: |&x| x, g: |&x| x as i32 };
195                difference.into_set_buf()
196            };
197
198            let a = BTreeSet::from_iter(a);
199            let b = BTreeSet::from_iter(b.into_iter().map(|x| x as i32));
200            let y = a.difference(&b);
201            let y: Vec<_> = y.cloned().collect();
202
203            x.as_slice() == y.as_slice()
204        }
205    }
206}
207
208
209#[cfg(all(feature = "unstable", test))]
210mod bench {
211    extern crate test;
212    use super::*;
213    use self::test::Bencher;
214    use crate::set::SetBuf;
215
216    #[derive(Debug, Clone)]
217    pub struct Foo {
218        a: i32,
219        b: u8
220    }
221
222    impl Foo {
223        fn new(a: i32) -> Foo {
224            Foo { a, b: 0 }
225        }
226    }
227
228    #[bench]
229    fn two_slices_big(bench: &mut Bencher) {
230        let a: Vec<_> = (0..100).map(Foo::new).collect();
231        let b: Vec<_> = (1..101).collect();
232        let f = |x: &Foo| x.a;
233        let g = |x: &i32| *x;
234
235        bench.iter(|| {
236            let op = DifferenceByKey { a: &a, b: &b, f, g };
237            let res: SetBuf<Foo> = op.into_set_buf();
238            test::black_box(|| res);
239        });
240    }
241
242    #[bench]
243    fn two_slices_big2(bench: &mut Bencher) {
244        let a: Vec<_> = (0..100).map(Foo::new).collect();
245        let b: Vec<_> = (51..151).collect();
246        let f = |x: &Foo| x.a;
247        let g = |x: &i32| *x;
248
249        bench.iter(|| {
250            let op = DifferenceByKey { a: &a, b: &b, f, g };
251            let res: SetBuf<Foo> = op.into_set_buf();
252            test::black_box(|| res);
253        });
254    }
255
256    #[bench]
257    fn two_slices_big3(bench: &mut Bencher) {
258        let a: Vec<_> = (0..100).map(Foo::new).collect();
259        let b: Vec<_> = (100..200).collect();
260        let f = |x: &Foo| x.a;
261        let g = |x: &i32| *x;
262
263        bench.iter(|| {
264            let op = DifferenceByKey { a: &a, b: &b, f, g };
265            let res: SetBuf<Foo> = op.into_set_buf();
266            test::black_box(|| res);
267        });
268    }
269}
sdset/duo/difference_by_key.rs

sdset/duo/
difference_by_key.rs
