1mod linear_group;
2mod linear_group_by;
3mod linear_group_by_key;
4
5pub use self::linear_group::{LinearGroup, LinearGroupMut};
6pub use self::linear_group_by::{LinearGroupBy, LinearGroupByMut};
7pub use self::linear_group_by_key::{LinearGroupByKey, LinearGroupByKeyMut};
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 = LinearGroup::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 = LinearGroup::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 = LinearGroup::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, 3, 3, 2, 2, 2];
63
64 let mut iter = LinearGroup::new(slice);
65
66 assert_eq!(iter.next(), Some(&[1, 1, 1][..]));
67 assert_eq!(iter.next(), Some(&[3, 3][..]));
68 assert_eq!(iter.next(), Some(&[2, 2, 2][..]));
69 assert_eq!(iter.next(), None);
70 }
71
72 #[test]
73 fn three_little_groups() {
74 let slice = &[1, 3, 2];
75
76 let mut iter = LinearGroup::new(slice);
77
78 assert_eq!(iter.next(), Some(&[1][..]));
79 assert_eq!(iter.next(), Some(&[3][..]));
80 assert_eq!(iter.next(), Some(&[2][..]));
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 = LinearGroup::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, 3, 2];
97
98 let iter = LinearGroup::new(slice);
99
100 assert_eq!(iter.last(), Some(&[2][..]));
101 }
102
103 #[test]
104 fn last_three_groups() {
105 let slice = &[1, 1, 1, 3, 3, 2, 2, 2];
106
107 let iter = LinearGroup::new(slice);
108
109 assert_eq!(iter.last(), Some(&[2, 2, 2][..]));
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 = LinearGroup::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 = LinearGroup::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 = LinearGroup::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, 3, 2];
146
147 let mut iter = LinearGroup::new(slice);
148
149 assert_eq!(iter.next_back(), Some(&[2][..]));
150 assert_eq!(iter.next_back(), Some(&[3][..]));
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, 3, 3, 2, 2, 2];
158
159 let mut iter = LinearGroup::new(slice);
160
161 assert_eq!(iter.next_back(), Some(&[2, 2, 2][..]));
162 assert_eq!(iter.next_back(), Some(&[3, 3][..]));
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, 3, 3, 2, 2, 2];
170
171 let mut iter = LinearGroup::new(slice);
172
173 assert_eq!(iter.next(), Some(&[1, 1, 1][..]));
174 assert_eq!(iter.next_back(), Some(&[2, 2, 2][..]));
175 assert_eq!(iter.next(), Some(&[3, 3][..]));
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 = LinearGroup::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 = LinearGroup::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 fn panic_param_ord(a: &i32, b: &i32) -> bool {
207 if a < b { true }
208 else { panic!("params are not in the right order") }
209 }
210
211 #[test]
212 fn predicate_call_param_order() {
213 let slice = &[1, 2, 3, 4, 5];
214
215 let mut iter = LinearGroupBy::new(slice, panic_param_ord);
216
217 assert_eq!(iter.next(), Some(&[1, 2, 3, 4, 5][..]));
218 assert_eq!(iter.next(), None);
219 }
220
221 #[test]
222 fn rev_predicate_call_param_order() {
223 let slice = &[1, 2, 3, 4, 5];
224
225 let mut iter = LinearGroupBy::new(slice, panic_param_ord);
226
227 assert_eq!(iter.next_back(), Some(&[1, 2, 3, 4, 5][..]));
228 assert_eq!(iter.next_back(), None);
229 }
230
231 #[test]
232 fn group_by_key_mut() {
233 let slice = &mut [1, 2, 4, 5, 7, 8, 8];
234
235 let mut iter = LinearGroupByKeyMut::new(slice, |i: &i32| *i % 2);
236
237 assert_eq!(iter.next(), Some(&mut [1][..]));
238 assert_eq!(iter.next(), Some(&mut [2, 4][..]));
239 assert_eq!(iter.next(), Some(&mut [5, 7][..]));
240 assert_eq!(iter.next(), Some(&mut [8, 8][..]));
241 assert_eq!(iter.next(), None);
242 }
243}
244
245#[cfg(all(feature = "nightly", test))]
246mod bench {
247 extern crate test;
248 extern crate rand;
249
250 use super::*;
251 use self::rand::{Rng, SeedableRng};
252 use self::rand::rngs::StdRng;
253 use self::rand::distributions::Alphanumeric;
254
255 #[bench]
256 fn vector_16_000(b: &mut test::Bencher) {
257 let mut rng = StdRng::from_seed([42; 32]);
258
259 let len = 16_000;
260 let mut vec = Vec::with_capacity(len);
261 for _ in 0..len {
262 vec.push(rng.sample(Alphanumeric));
263 }
264
265 b.iter(|| {
266 let group_by = LinearGroup::new(vec.as_slice());
267 test::black_box(group_by.count())
268 })
269 }
270
271 #[bench]
272 fn vector_16_000_sorted(b: &mut test::Bencher) {
273 let mut rng = StdRng::from_seed([42; 32]);
274
275 let len = 16_000;
276 let mut vec = Vec::with_capacity(len);
277 for _ in 0..len {
278 vec.push(rng.sample(Alphanumeric));
279 }
280
281 vec.sort_unstable();
282
283 b.iter(|| {
284 let group_by = LinearGroup::new(vec.as_slice());
285 test::black_box(group_by.count())
286 })
287 }
288
289 #[bench]
290 fn vector_little_sorted(b: &mut test::Bencher) {
291 let mut rng = StdRng::from_seed([42; 32]);
292
293 let len = 30;
294 let mut vec = Vec::with_capacity(len);
295 for _ in 0..len {
296 vec.push(rng.sample(Alphanumeric));
297 }
298
299 vec.sort_unstable();
300
301 b.iter(|| {
302 let group_by = LinearGroup::new(vec.as_slice());
303 test::black_box(group_by.count())
304 })
305 }
306
307 #[bench]
308 fn vector_16_000_one_group(b: &mut test::Bencher) {
309 let vec = vec![1; 16_000];
310
311 b.iter(|| {
312 let group_by = LinearGroup::new(vec.as_slice());
313 test::black_box(group_by.count())
314 })
315 }
316
317 #[bench]
318 fn rev_vector_16_000(b: &mut test::Bencher) {
319 let mut rng = StdRng::from_seed([42; 32]);
320
321 let len = 16_000;
322 let mut vec = Vec::with_capacity(len);
323 for _ in 0..len {
324 vec.push(rng.sample(Alphanumeric));
325 }
326
327 b.iter(|| {
328 let group_by = LinearGroup::new(vec.as_slice());
329 test::black_box(group_by.rev().count())
330 })
331 }
332
333 #[bench]
334 fn rev_vector_16_000_one_group(b: &mut test::Bencher) {
335 let vec = vec![1; 16_000];
336
337 b.iter(|| {
338 let group_by = LinearGroup::new(vec.as_slice());
339 test::black_box(group_by.rev().count())
340 })
341 }
342}