sdset/duo/
union.rs

1use std::cmp::{self, Ordering};
2use crate::set::Set;
3use crate::{SetOperation, Collection};
4
5/// Represent the _union_ 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).union();
18///
19/// let res: SetBuf<i32> = op.into_set_buf();
20/// assert_eq!(&res[..], &[1, 2, 3, 4, 5, 6, 7]);
21/// # Ok(()) }
22/// # try_main().unwrap();
23/// ```
24#[derive(Copy, Clone)]
25pub struct Union<'a, T: 'a> {
26    a: &'a [T],
27    b: &'a [T],
28}
29
30impl<'a, T> Union<'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> Union<'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        let min_len = cmp::max(self.a.len(), self.b.len());
47        output.reserve(min_len);
48
49        while !self.a.is_empty() && !self.b.is_empty() {
50            let a = &self.a[0];
51            let b = &self.b[0];
52
53            match a.cmp(&b) {
54                 Ordering::Less => {
55                    let off = self.a.iter().take_while(|&x| x < b).count();
56                    extend(output, &self.a[..off]);
57
58                    self.a = &self.a[off..];
59                 },
60                 Ordering::Equal => {
61                    let off = self.a.iter().zip(self.b.iter()).take_while(|(a, b)| a == b).count();
62                    extend(output, &self.a[..off]);
63
64                    self.a = &self.a[off..];
65                    self.b = &self.b[off..];
66                 },
67                 Ordering::Greater => {
68                    let off = self.b.iter().take_while(|&x| x < a).count();
69                    extend(output, &self.b[..off]);
70
71                    self.b = &self.b[off..];
72                 },
73             }
74        }
75
76        extend(output, self.a);
77        extend(output, self.b);
78    }
79}
80
81impl<'a, T: Ord + Clone> SetOperation<T> for Union<'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 Union<'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    #[test]
99    fn union_two_slices_easy() {
100        let a = &[1, 2, 3];
101        let b = &[2, 3, 4];
102
103        let union_: SetBuf<i32> = Union { a: a, b: b }.into_set_buf();
104
105        assert_eq!(&union_[..], &[1, 2, 3, 4]);
106    }
107
108    #[test]
109    fn union_two_slices_second_empty() {
110        let a = &[1, 2, 3];
111        let b = &[];
112
113        let union_: SetBuf<i32> = Union { a: a, b: b }.into_set_buf();
114
115        assert_eq!(&union_[..], &[1, 2, 3]);
116    }
117
118    #[test]
119    fn union_two_slices_first_empty() {
120        let a = &[];
121        let b = &[2, 3, 4];
122
123        let union_: SetBuf<i32> = Union { a: a, b: b }.into_set_buf();
124
125        assert_eq!(&union_[..], &[2, 3, 4]);
126    }
127
128    #[test]
129    fn union_two_slices_same_elem() {
130        let a = &[1];
131        let b = &[1];
132
133        let union_: SetBuf<i32> = Union { a: a, b: b }.into_set_buf();
134
135        assert_eq!(&union_[..], &[1]);
136    }
137
138    quickcheck! {
139        fn qc_union(a: Vec<i32>, b: Vec<i32>) -> bool {
140            use std::collections::BTreeSet;
141            use std::iter::FromIterator;
142
143            let mut a = a;
144            let mut b = b;
145
146            sort_dedup_vec(&mut a);
147            sort_dedup_vec(&mut b);
148
149            let x: SetBuf<i32> = Union { a: &a, b: &b }.into_set_buf();
150
151            let a = BTreeSet::from_iter(a);
152            let b = BTreeSet::from_iter(b);
153            let y = a.union(&b);
154            let y: Vec<_> = y.cloned().collect();
155
156            x.as_slice() == y.as_slice()
157        }
158    }
159}
160
161#[cfg(all(feature = "unstable", test))]
162mod bench {
163    extern crate test;
164    use super::*;
165    use self::test::Bencher;
166    use crate::set::SetBuf;
167
168    #[bench]
169    fn two_slices_big(bench: &mut Bencher) {
170        let a: Vec<_> = (0..100).collect();
171        let b: Vec<_> = (1..101).collect();
172
173        bench.iter(|| {
174            let union_: SetBuf<i32> = Union { a: &a, b: &b }.into_set_buf();
175            test::black_box(|| union_);
176        });
177    }
178
179    #[bench]
180    fn two_slices_big2(bench: &mut Bencher) {
181        let a: Vec<_> = (0..100).collect();
182        let b: Vec<_> = (51..151).collect();
183
184        bench.iter(|| {
185            let union_: SetBuf<i32> = Union { a: &a, b: &b }.into_set_buf();
186            test::black_box(|| union_);
187        });
188    }
189
190    #[bench]
191    fn two_slices_big3(bench: &mut Bencher) {
192        let a: Vec<_> = (0..100).collect();
193        let b: Vec<_> = (100..200).collect();
194
195        bench.iter(|| {
196            let union_: SetBuf<i32> = Union { a: &a, b: &b }.into_set_buf();
197            test::black_box(|| union_);
198        });
199    }
200}
sdset/duo/union.rs

sdset/duo/
union.rs
