slice_group_by/binary_group/
mod.rs

1mod binary_group;
2mod binary_group_by;
3mod binary_group_by_key;
4
5pub use self::binary_group::{BinaryGroup, BinaryGroupMut};
6pub use self::binary_group_by::{BinaryGroupBy, BinaryGroupByMut};
7pub use self::binary_group_by_key::{BinaryGroupByKey, BinaryGroupByKeyMut};
8
9#[cfg(test)]
10mod tests {
11    use super::*;
12
13    #[derive(Debug, Eq)]
14    enum Guard {
15        Valid(i32),
16        Invalid(i32),
17    }
18
19    impl PartialEq for Guard {
20        fn eq(&self, other: &Self) -> bool {
21            match (self, other) {
22                (Guard::Valid(_), Guard::Valid(_)) => true,
23                (a, b) => panic!("denied read on Guard::Invalid variant ({:?}, {:?})", a, b),
24            }
25        }
26    }
27
28    #[test]
29    fn one_big_group() {
30        let slice = &[1, 1, 1, 1];
31
32        let mut iter = BinaryGroup::new(slice);
33
34        assert_eq!(iter.next(), Some(&[1, 1, 1, 1][..]));
35        assert_eq!(iter.next(), None);
36    }
37
38    #[test]
39    fn two_equal_groups() {
40        let slice = &[1, 1, 1, 1, 2, 2, 2, 2];
41
42        let mut iter = BinaryGroup::new(slice);
43
44        assert_eq!(iter.next(), Some(&[1, 1, 1, 1][..]));
45        assert_eq!(iter.next(), Some(&[2, 2, 2, 2][..]));
46        assert_eq!(iter.next(), None);
47    }
48
49    #[test]
50    fn two_little_equal_groups() {
51        let slice = &[1, 2];
52
53        let mut iter = BinaryGroup::new(slice);
54
55        assert_eq!(iter.next(), Some(&[1][..]));
56        assert_eq!(iter.next(), Some(&[2][..]));
57        assert_eq!(iter.next(), None);
58    }
59
60    #[test]
61    fn three_groups() {
62        let slice = &[1, 1, 1, 2, 2, 2, 3, 3];
63
64        let mut iter = BinaryGroup::new(slice);
65
66        assert_eq!(iter.next(), Some(&[1, 1, 1][..]));
67        assert_eq!(iter.next(), Some(&[2, 2, 2][..]));
68        assert_eq!(iter.next(), Some(&[3, 3][..]));
69        assert_eq!(iter.next(), None);
70    }
71
72    #[test]
73    fn three_little_groups() {
74        let slice = &[1, 2, 3];
75
76        let mut iter = BinaryGroup::new(slice);
77
78        assert_eq!(iter.next(), Some(&[1][..]));
79        assert_eq!(iter.next(), Some(&[2][..]));
80        assert_eq!(iter.next(), Some(&[3][..]));
81        assert_eq!(iter.next(), None);
82    }
83
84    #[test]
85    fn overflow() {
86        let slice = &[Guard::Invalid(0), Guard::Valid(1), Guard::Valid(2), Guard::Invalid(3)];
87
88        let mut iter = BinaryGroup::new(&slice[1..3]);
89
90        assert_eq!(iter.next(), Some(&[Guard::Valid(1), Guard::Valid(2)][..]));
91        assert_eq!(iter.next(), None);
92    }
93
94    #[test]
95    fn last_three_little_groups() {
96        let slice = &[1, 2, 3];
97
98        let iter = BinaryGroup::new(slice);
99
100        assert_eq!(iter.last(), Some(&[3][..]));
101    }
102
103    #[test]
104    fn last_three_groups() {
105        let slice = &[1, 1, 1, 2, 2, 2, 3, 3];
106
107        let iter = BinaryGroup::new(slice);
108
109        assert_eq!(iter.last(), Some(&[3, 3][..]));
110    }
111
112    #[test]
113    fn last_overflow() {
114        let slice = &[Guard::Invalid(0), Guard::Valid(1), Guard::Valid(2), Guard::Invalid(3)];
115
116        println!("{:?}", (&slice[1..3]).as_ptr());
117
118        let iter = BinaryGroup::new(&slice[1..3]);
119
120        assert_eq!(iter.last(), Some(&[Guard::Valid(1), Guard::Valid(2)][..]));
121    }
122
123    #[test]
124    fn back_empty_slice() {
125        let slice: &[i32] = &[];
126
127        let mut iter = BinaryGroup::new(slice);
128
129        assert_eq!(iter.next_back(), None);
130    }
131
132    #[test]
133    fn back_one_little_group() {
134        let slice = &[1];
135
136        let mut iter = BinaryGroup::new(slice);
137
138        assert_eq!(iter.next_back(), Some(&[1][..]));
139        assert_eq!(iter.next_back(), None);
140        assert_eq!(iter.next(), None);
141    }
142
143    #[test]
144    fn back_three_little_groups() {
145        let slice = &[1, 2, 3];
146
147        let mut iter = BinaryGroup::new(slice);
148
149        assert_eq!(iter.next_back(), Some(&[3][..]));
150        assert_eq!(iter.next_back(), Some(&[2][..]));
151        assert_eq!(iter.next_back(), Some(&[1][..]));
152        assert_eq!(iter.next_back(), None);
153    }
154
155    #[test]
156    fn back_three_groups() {
157        let slice = &[1, 1, 1, 2, 2, 2, 3, 3];
158
159        let mut iter = BinaryGroup::new(slice);
160
161        assert_eq!(iter.next_back(), Some(&[3, 3][..]));
162        assert_eq!(iter.next_back(), Some(&[2, 2, 2][..]));
163        assert_eq!(iter.next_back(), Some(&[1, 1, 1][..]));
164        assert_eq!(iter.next_back(), None);
165    }
166
167    #[test]
168    fn double_ended_dont_cross() {
169        let slice = &[1, 1, 1, 2, 2, 2, 3, 3];
170
171        let mut iter = BinaryGroup::new(slice);
172
173        assert_eq!(iter.next(), Some(&[1, 1, 1][..]));
174        assert_eq!(iter.next_back(), Some(&[3, 3][..]));
175        assert_eq!(iter.next(), Some(&[2, 2, 2][..]));
176        assert_eq!(iter.next_back(), None);
177        assert_eq!(iter.next(), None);
178    }
179
180    #[test]
181    fn fused_iterator() {
182        let slice = &[1, 2, 3];
183
184        let mut iter = BinaryGroup::new(slice);
185
186        assert_eq!(iter.next(), Some(&[1][..]));
187        assert_eq!(iter.next(), Some(&[2][..]));
188        assert_eq!(iter.next(), Some(&[3][..]));
189        assert_eq!(iter.next(), None);
190        assert_eq!(iter.next(), None);
191    }
192
193    #[test]
194    fn back_fused_iterator() {
195        let slice = &[1, 2, 3];
196
197        let mut iter = BinaryGroup::new(slice);
198
199        assert_eq!(iter.next_back(), Some(&[3][..]));
200        assert_eq!(iter.next_back(), Some(&[2][..]));
201        assert_eq!(iter.next_back(), Some(&[1][..]));
202        assert_eq!(iter.next_back(), None);
203        assert_eq!(iter.next_back(), None);
204    }
205}
206
207#[cfg(all(feature = "nightly", test))]
208mod bench {
209    extern crate test;
210    extern crate rand;
211
212    use super::*;
213    use self::rand::{Rng, SeedableRng};
214    use self::rand::rngs::StdRng;
215    use self::rand::distributions::Alphanumeric;
216
217    #[bench]
218    fn vector_16_000_sorted(b: &mut test::Bencher) {
219        let mut rng = StdRng::from_seed([42; 32]);
220
221        let len = 16_000;
222        let mut vec = Vec::with_capacity(len);
223        for _ in 0..len {
224            vec.push(rng.sample(Alphanumeric));
225        }
226
227        vec.sort_unstable();
228
229        b.iter(|| {
230            let group_by = BinaryGroup::new(vec.as_slice());
231            test::black_box(group_by.count())
232        })
233    }
234
235    #[bench]
236    fn vector_little_sorted(b: &mut test::Bencher) {
237        let mut rng = StdRng::from_seed([42; 32]);
238
239        let len = 30;
240        let mut vec = Vec::with_capacity(len);
241        for _ in 0..len {
242            vec.push(rng.sample(Alphanumeric));
243        }
244
245        vec.sort_unstable();
246
247        b.iter(|| {
248            let group_by = BinaryGroup::new(vec.as_slice());
249            test::black_box(group_by.count())
250        })
251    }
252
253    #[bench]
254    fn vector_16_000_one_group(b: &mut test::Bencher) {
255        let vec = vec![1; 16_000];
256
257        b.iter(|| {
258            let group_by = BinaryGroup::new(vec.as_slice());
259            test::black_box(group_by.count())
260        })
261    }
262
263    #[bench]
264    fn rev_vector_16_000_sorted(b: &mut test::Bencher) {
265        let mut rng = StdRng::from_seed([42; 32]);
266
267        let len = 16_000;
268        let mut vec = Vec::with_capacity(len);
269        for _ in 0..len {
270            vec.push(rng.sample(Alphanumeric));
271        }
272
273        vec.sort_unstable();
274
275        b.iter(|| {
276            let group_by = BinaryGroup::new(vec.as_slice());
277            test::black_box(group_by.rev().count())
278        })
279    }
280
281    #[bench]
282    fn rev_vector_16_000_one_group(b: &mut test::Bencher) {
283        let vec = vec![1; 16_000];
284
285        b.iter(|| {
286            let group_by = BinaryGroup::new(vec.as_slice());
287            test::black_box(group_by.rev().count())
288        })
289    }
290}
slice_group_by/binary_group/mod.rs

slice_group_by/binary_group/
mod.rs
