1 use quickcheck as qc;
2 use rand::{distributions::{Distribution, Standard}, Rng, SeedableRng, rngs::StdRng};
3 use rand::{seq::SliceRandom, thread_rng};
4 use std::{cmp::min, fmt::Debug, marker::PhantomData};
5 use itertools as it;
6 use crate::it::Itertools;
7 use crate::it::ExactlyOneError;
8 use crate::it::multizip;
9 use crate::it::multipeek;
10 use crate::it::peek_nth;
11 use crate::it::free::rciter;
12 use crate::it::free::put_back_n;
13 use crate::it::FoldWhile;
14 use crate::it::cloned;
15 use crate::it::iproduct;
16 use crate::it::izip;
17
18 #[test]
product3()19 fn product3() {
20 let prod = iproduct!(0..3, 0..2, 0..2);
21 assert_eq!(prod.size_hint(), (12, Some(12)));
22 let v = prod.collect_vec();
23 for i in 0..3 {
24 for j in 0..2 {
25 for k in 0..2 {
26 assert!((i, j, k) == v[(i * 2 * 2 + j * 2 + k) as usize]);
27 }
28 }
29 }
30 for (_, _, _, _) in iproduct!(0..3, 0..2, 0..2, 0..3) {
31 /* test compiles */
32 }
33 }
34
35 #[test]
interleave_shortest()36 fn interleave_shortest() {
37 let v0: Vec<i32> = vec![0, 2, 4];
38 let v1: Vec<i32> = vec![1, 3, 5, 7];
39 let it = v0.into_iter().interleave_shortest(v1.into_iter());
40 assert_eq!(it.size_hint(), (6, Some(6)));
41 assert_eq!(it.collect_vec(), vec![0, 1, 2, 3, 4, 5]);
42
43 let v0: Vec<i32> = vec![0, 2, 4, 6, 8];
44 let v1: Vec<i32> = vec![1, 3, 5];
45 let it = v0.into_iter().interleave_shortest(v1.into_iter());
46 assert_eq!(it.size_hint(), (7, Some(7)));
47 assert_eq!(it.collect_vec(), vec![0, 1, 2, 3, 4, 5, 6]);
48
49 let i0 = ::std::iter::repeat(0);
50 let v1: Vec<_> = vec![1, 3, 5];
51 let it = i0.interleave_shortest(v1.into_iter());
52 assert_eq!(it.size_hint(), (7, Some(7)));
53
54 let v0: Vec<_> = vec![0, 2, 4];
55 let i1 = ::std::iter::repeat(1);
56 let it = v0.into_iter().interleave_shortest(i1);
57 assert_eq!(it.size_hint(), (6, Some(6)));
58 }
59
60 #[test]
duplicates_by()61 fn duplicates_by() {
62 let xs = ["aaa", "bbbbb", "aa", "ccc", "bbbb", "aaaaa", "cccc"];
63 let ys = ["aa", "bbbb", "cccc"];
64 it::assert_equal(ys.iter(), xs.iter().duplicates_by(|x| x[..2].to_string()));
65 it::assert_equal(ys.iter(), xs.iter().rev().duplicates_by(|x| x[..2].to_string()).rev());
66 let ys_rev = ["ccc", "aa", "bbbbb"];
67 it::assert_equal(ys_rev.iter(), xs.iter().duplicates_by(|x| x[..2].to_string()).rev());
68 }
69
70 #[test]
duplicates()71 fn duplicates() {
72 let xs = [0, 1, 2, 3, 2, 1, 3];
73 let ys = [2, 1, 3];
74 it::assert_equal(ys.iter(), xs.iter().duplicates());
75 it::assert_equal(ys.iter(), xs.iter().rev().duplicates().rev());
76 let ys_rev = [3, 2, 1];
77 it::assert_equal(ys_rev.iter(), xs.iter().duplicates().rev());
78
79 let xs = [0, 1, 0, 1];
80 let ys = [0, 1];
81 it::assert_equal(ys.iter(), xs.iter().duplicates());
82 it::assert_equal(ys.iter(), xs.iter().rev().duplicates().rev());
83 let ys_rev = [1, 0];
84 it::assert_equal(ys_rev.iter(), xs.iter().duplicates().rev());
85
86 let xs = vec![0, 1, 2, 1, 2];
87 let ys = vec![1, 2];
88 assert_eq!(ys, xs.iter().duplicates().cloned().collect_vec());
89 assert_eq!(ys, xs.iter().rev().duplicates().rev().cloned().collect_vec());
90 let ys_rev = vec![2, 1];
91 assert_eq!(ys_rev, xs.iter().duplicates().rev().cloned().collect_vec());
92 }
93
94 #[test]
unique_by()95 fn unique_by() {
96 let xs = ["aaa", "bbbbb", "aa", "ccc", "bbbb", "aaaaa", "cccc"];
97 let ys = ["aaa", "bbbbb", "ccc"];
98 it::assert_equal(ys.iter(), xs.iter().unique_by(|x| x[..2].to_string()));
99 it::assert_equal(ys.iter(), xs.iter().rev().unique_by(|x| x[..2].to_string()).rev());
100 let ys_rev = ["cccc", "aaaaa", "bbbb"];
101 it::assert_equal(ys_rev.iter(), xs.iter().unique_by(|x| x[..2].to_string()).rev());
102 }
103
104 #[test]
unique()105 fn unique() {
106 let xs = [0, 1, 2, 3, 2, 1, 3];
107 let ys = [0, 1, 2, 3];
108 it::assert_equal(ys.iter(), xs.iter().unique());
109 it::assert_equal(ys.iter(), xs.iter().rev().unique().rev());
110 let ys_rev = [3, 1, 2, 0];
111 it::assert_equal(ys_rev.iter(), xs.iter().unique().rev());
112
113 let xs = [0, 1];
114 let ys = [0, 1];
115 it::assert_equal(ys.iter(), xs.iter().unique());
116 it::assert_equal(ys.iter(), xs.iter().rev().unique().rev());
117 let ys_rev = [1, 0];
118 it::assert_equal(ys_rev.iter(), xs.iter().unique().rev());
119 }
120
121 #[test]
intersperse()122 fn intersperse() {
123 let xs = ["a", "", "b", "c"];
124 let v: Vec<&str> = xs.iter().cloned().intersperse(", ").collect();
125 let text: String = v.concat();
126 assert_eq!(text, "a, , b, c".to_string());
127
128 let ys = [0, 1, 2, 3];
129 let mut it = ys[..0].iter().copied().intersperse(1);
130 assert!(it.next() == None);
131 }
132
133 #[test]
dedup()134 fn dedup() {
135 let xs = [0, 1, 1, 1, 2, 1, 3, 3];
136 let ys = [0, 1, 2, 1, 3];
137 it::assert_equal(ys.iter(), xs.iter().dedup());
138 let xs = [0, 0, 0, 0, 0];
139 let ys = [0];
140 it::assert_equal(ys.iter(), xs.iter().dedup());
141
142 let xs = [0, 1, 1, 1, 2, 1, 3, 3];
143 let ys = [0, 1, 2, 1, 3];
144 let mut xs_d = Vec::new();
145 xs.iter().dedup().fold((), |(), &elt| xs_d.push(elt));
146 assert_eq!(&xs_d, &ys);
147 }
148
149 #[test]
coalesce()150 fn coalesce() {
151 let data = vec![-1., -2., -3., 3., 1., 0., -1.];
152 let it = data.iter().cloned().coalesce(|x, y|
153 if (x >= 0.) == (y >= 0.) {
154 Ok(x + y)
155 } else {
156 Err((x, y))
157 }
158 );
159 itertools::assert_equal(it.clone(), vec![-6., 4., -1.]);
160 assert_eq!(
161 it.fold(vec![], |mut v, n| {
162 v.push(n);
163 v
164 }),
165 vec![-6., 4., -1.]
166 );
167 }
168
169 #[test]
dedup_by()170 fn dedup_by() {
171 let xs = [(0, 0), (0, 1), (1, 1), (2, 1), (0, 2), (3, 1), (0, 3), (1, 3)];
172 let ys = [(0, 0), (0, 1), (0, 2), (3, 1), (0, 3)];
173 it::assert_equal(ys.iter(), xs.iter().dedup_by(|x, y| x.1==y.1));
174 let xs = [(0, 1), (0, 2), (0, 3), (0, 4), (0, 5)];
175 let ys = [(0, 1)];
176 it::assert_equal(ys.iter(), xs.iter().dedup_by(|x, y| x.0==y.0));
177
178 let xs = [(0, 0), (0, 1), (1, 1), (2, 1), (0, 2), (3, 1), (0, 3), (1, 3)];
179 let ys = [(0, 0), (0, 1), (0, 2), (3, 1), (0, 3)];
180 let mut xs_d = Vec::new();
181 xs.iter().dedup_by(|x, y| x.1==y.1).fold((), |(), &elt| xs_d.push(elt));
182 assert_eq!(&xs_d, &ys);
183 }
184
185 #[test]
dedup_with_count()186 fn dedup_with_count() {
187 let xs: [i32; 8] = [0, 1, 1, 1, 2, 1, 3, 3];
188 let ys: [(usize, &i32); 5] = [(1, &0), (3, &1), (1, &2), (1, &1), (2, &3)];
189
190 it::assert_equal(ys.iter().cloned(), xs.iter().dedup_with_count());
191
192 let xs: [i32; 5] = [0, 0, 0, 0, 0];
193 let ys: [(usize, &i32); 1] = [(5, &0)];
194
195 it::assert_equal(ys.iter().cloned(), xs.iter().dedup_with_count());
196 }
197
198
199 #[test]
dedup_by_with_count()200 fn dedup_by_with_count() {
201 let xs = [(0, 0), (0, 1), (1, 1), (2, 1), (0, 2), (3, 1), (0, 3), (1, 3)];
202 let ys = [(1, &(0, 0)), (3, &(0, 1)), (1, &(0, 2)), (1, &(3, 1)), (2, &(0, 3))];
203
204 it::assert_equal(ys.iter().cloned(), xs.iter().dedup_by_with_count(|x, y| x.1==y.1));
205
206 let xs = [(0, 1), (0, 2), (0, 3), (0, 4), (0, 5)];
207 let ys = [( 5, &(0, 1))];
208
209 it::assert_equal(ys.iter().cloned(), xs.iter().dedup_by_with_count(|x, y| x.0==y.0));
210 }
211
212 #[test]
all_equal()213 fn all_equal() {
214 assert!("".chars().all_equal());
215 assert!("A".chars().all_equal());
216 assert!(!"AABBCCC".chars().all_equal());
217 assert!("AAAAAAA".chars().all_equal());
218 for (_key, mut sub) in &"AABBCCC".chars().group_by(|&x| x) {
219 assert!(sub.all_equal());
220 }
221 }
222
223 #[test]
all_unique()224 fn all_unique() {
225 assert!("ABCDEFGH".chars().all_unique());
226 assert!(!"ABCDEFGA".chars().all_unique());
227 assert!(::std::iter::empty::<usize>().all_unique());
228 }
229
230 #[test]
test_put_back_n()231 fn test_put_back_n() {
232 let xs = [0, 1, 1, 1, 2, 1, 3, 3];
233 let mut pb = put_back_n(xs.iter().cloned());
234 pb.next();
235 pb.next();
236 pb.put_back(1);
237 pb.put_back(0);
238 it::assert_equal(pb, xs.iter().cloned());
239 }
240
241 #[test]
tee()242 fn tee() {
243 let xs = [0, 1, 2, 3];
244 let (mut t1, mut t2) = xs.iter().cloned().tee();
245 assert_eq!(t1.next(), Some(0));
246 assert_eq!(t2.next(), Some(0));
247 assert_eq!(t1.next(), Some(1));
248 assert_eq!(t1.next(), Some(2));
249 assert_eq!(t1.next(), Some(3));
250 assert_eq!(t1.next(), None);
251 assert_eq!(t2.next(), Some(1));
252 assert_eq!(t2.next(), Some(2));
253 assert_eq!(t1.next(), None);
254 assert_eq!(t2.next(), Some(3));
255 assert_eq!(t2.next(), None);
256 assert_eq!(t1.next(), None);
257 assert_eq!(t2.next(), None);
258
259 let (t1, t2) = xs.iter().cloned().tee();
260 it::assert_equal(t1, xs.iter().cloned());
261 it::assert_equal(t2, xs.iter().cloned());
262
263 let (t1, t2) = xs.iter().cloned().tee();
264 it::assert_equal(t1.zip(t2), xs.iter().cloned().zip(xs.iter().cloned()));
265 }
266
267
268 #[test]
test_rciter()269 fn test_rciter() {
270 let xs = [0, 1, 1, 1, 2, 1, 3, 5, 6];
271
272 let mut r1 = rciter(xs.iter().cloned());
273 let mut r2 = r1.clone();
274 assert_eq!(r1.next(), Some(0));
275 assert_eq!(r2.next(), Some(1));
276 let mut z = r1.zip(r2);
277 assert_eq!(z.next(), Some((1, 1)));
278 assert_eq!(z.next(), Some((2, 1)));
279 assert_eq!(z.next(), Some((3, 5)));
280 assert_eq!(z.next(), None);
281
282 // test intoiterator
283 let r1 = rciter(0..5);
284 let mut z = izip!(&r1, r1);
285 assert_eq!(z.next(), Some((0, 1)));
286 }
287
288 #[allow(deprecated)]
289 #[test]
trait_pointers()290 fn trait_pointers() {
291 struct ByRef<'r, I: ?Sized>(&'r mut I) ;
292
293 impl<'r, X, I: ?Sized> Iterator for ByRef<'r, I> where
294 I: 'r + Iterator<Item=X>
295 {
296 type Item = X;
297 fn next(&mut self) -> Option<Self::Item>
298 {
299 self.0.next()
300 }
301 }
302
303 let mut it = Box::new(0..10) as Box<dyn Iterator<Item=i32>>;
304 assert_eq!(it.next(), Some(0));
305
306 {
307 /* make sure foreach works on non-Sized */
308 let jt: &mut dyn Iterator<Item = i32> = &mut *it;
309 assert_eq!(jt.next(), Some(1));
310
311 {
312 let mut r = ByRef(jt);
313 assert_eq!(r.next(), Some(2));
314 }
315
316 assert_eq!(jt.find_position(|x| *x == 4), Some((1, 4)));
317 jt.foreach(|_| ());
318 }
319 }
320
321 #[test]
merge_by()322 fn merge_by() {
323 let odd : Vec<(u32, &str)> = vec![(1, "hello"), (3, "world"), (5, "!")];
324 let even = vec![(2, "foo"), (4, "bar"), (6, "baz")];
325 let expected = vec![(1, "hello"), (2, "foo"), (3, "world"), (4, "bar"), (5, "!"), (6, "baz")];
326 let results = odd.iter().merge_by(even.iter(), |a, b| a.0 <= b.0);
327 it::assert_equal(results, expected.iter());
328 }
329
330 #[test]
merge_by_btree()331 fn merge_by_btree() {
332 use std::collections::BTreeMap;
333 let mut bt1 = BTreeMap::new();
334 bt1.insert("hello", 1);
335 bt1.insert("world", 3);
336 let mut bt2 = BTreeMap::new();
337 bt2.insert("foo", 2);
338 bt2.insert("bar", 4);
339 let results = bt1.into_iter().merge_by(bt2.into_iter(), |a, b| a.0 <= b.0 );
340 let expected = vec![("bar", 4), ("foo", 2), ("hello", 1), ("world", 3)];
341 it::assert_equal(results, expected.into_iter());
342 }
343
344 #[allow(deprecated)]
345 #[test]
kmerge()346 fn kmerge() {
347 let its = (0..4).map(|s| (s..10).step(4));
348
349 it::assert_equal(its.kmerge(), 0..10);
350 }
351
352 #[allow(deprecated)]
353 #[test]
kmerge_2()354 fn kmerge_2() {
355 let its = vec![3, 2, 1, 0].into_iter().map(|s| (s..10).step(4));
356
357 it::assert_equal(its.kmerge(), 0..10);
358 }
359
360 #[test]
kmerge_empty()361 fn kmerge_empty() {
362 let its = (0..4).map(|_| 0..0);
363 assert_eq!(its.kmerge().next(), None);
364 }
365
366 #[test]
kmerge_size_hint()367 fn kmerge_size_hint() {
368 let its = (0..5).map(|_| (0..10));
369 assert_eq!(its.kmerge().size_hint(), (50, Some(50)));
370 }
371
372 #[test]
kmerge_empty_size_hint()373 fn kmerge_empty_size_hint() {
374 let its = (0..5).map(|_| (0..0));
375 assert_eq!(its.kmerge().size_hint(), (0, Some(0)));
376 }
377
378 #[test]
join()379 fn join() {
380 let many = [1, 2, 3];
381 let one = [1];
382 let none: Vec<i32> = vec![];
383
384 assert_eq!(many.iter().join(", "), "1, 2, 3");
385 assert_eq!( one.iter().join(", "), "1");
386 assert_eq!(none.iter().join(", "), "");
387 }
388
389 #[test]
sorted_unstable_by()390 fn sorted_unstable_by() {
391 let sc = [3, 4, 1, 2].iter().cloned().sorted_by(|&a, &b| {
392 a.cmp(&b)
393 });
394 it::assert_equal(sc, vec![1, 2, 3, 4]);
395
396 let v = (0..5).sorted_unstable_by(|&a, &b| a.cmp(&b).reverse());
397 it::assert_equal(v, vec![4, 3, 2, 1, 0]);
398 }
399
400 #[test]
sorted_unstable_by_key()401 fn sorted_unstable_by_key() {
402 let sc = [3, 4, 1, 2].iter().cloned().sorted_unstable_by_key(|&x| x);
403 it::assert_equal(sc, vec![1, 2, 3, 4]);
404
405 let v = (0..5).sorted_unstable_by_key(|&x| -x);
406 it::assert_equal(v, vec![4, 3, 2, 1, 0]);
407 }
408
409 #[test]
sorted_by()410 fn sorted_by() {
411 let sc = [3, 4, 1, 2].iter().cloned().sorted_by(|&a, &b| {
412 a.cmp(&b)
413 });
414 it::assert_equal(sc, vec![1, 2, 3, 4]);
415
416 let v = (0..5).sorted_by(|&a, &b| a.cmp(&b).reverse());
417 it::assert_equal(v, vec![4, 3, 2, 1, 0]);
418 }
419
420 qc::quickcheck! {
421 fn k_smallest_range(n: u64, m: u16, k: u16) -> () {
422 // u16 is used to constrain k and m to 0..2¹⁶,
423 // otherwise the test could use too much memory.
424 let (k, m) = (k as u64, m as u64);
425
426 // Generate a random permutation of n..n+m
427 let i = {
428 let mut v: Vec<u64> = (n..n.saturating_add(m)).collect();
429 v.shuffle(&mut thread_rng());
430 v.into_iter()
431 };
432
433 // Check that taking the k smallest elements yields n..n+min(k, m)
434 it::assert_equal(
435 i.k_smallest(k as usize),
436 n..n.saturating_add(min(k, m))
437 );
438 }
439 }
440
441 #[derive(Clone, Debug)]
442 struct RandIter<T: 'static + Clone + Send, R: 'static + Clone + Rng + SeedableRng + Send = StdRng> {
443 idx: usize,
444 len: usize,
445 rng: R,
446 _t: PhantomData<T>
447 }
448
449 impl<T: Clone + Send, R: Clone + Rng + SeedableRng + Send> Iterator for RandIter<T, R>
450 where Standard: Distribution<T> {
451 type Item = T;
next(&mut self) -> Option<T>452 fn next(&mut self) -> Option<T> {
453 if self.idx == self.len {
454 None
455 } else {
456 self.idx += 1;
457 Some(self.rng.gen())
458 }
459 }
460 }
461
462 impl<T: Clone + Send, R: Clone + Rng + SeedableRng + Send> qc::Arbitrary for RandIter<T, R> {
arbitrary<G: qc::Gen>(g: &mut G) -> Self463 fn arbitrary<G: qc::Gen>(g: &mut G) -> Self {
464 RandIter {
465 idx: 0,
466 len: g.size(),
467 rng: R::seed_from_u64(g.next_u64()),
468 _t : PhantomData{},
469 }
470 }
471 }
472
473 // Check that taking the k smallest is the same as
474 // sorting then taking the k first elements
k_smallest_sort<I>(i: I, k: u16) where I: Iterator + Clone, I::Item: Ord + Debug,475 fn k_smallest_sort<I>(i: I, k: u16)
476 where
477 I: Iterator + Clone,
478 I::Item: Ord + Debug,
479 {
480 let j = i.clone();
481 let k = k as usize;
482 it::assert_equal(
483 i.k_smallest(k),
484 j.sorted().take(k)
485 )
486 }
487
488 macro_rules! generic_test {
489 ($f:ident, $($t:ty),+) => {
490 $(paste::item! {
491 qc::quickcheck! {
492 fn [< $f _ $t >](i: RandIter<$t>, k: u16) -> () {
493 $f(i, k)
494 }
495 }
496 })+
497 };
498 }
499
500 generic_test!(k_smallest_sort, u8, u16, u32, u64, i8, i16, i32, i64);
501
502 #[test]
sorted_by_key()503 fn sorted_by_key() {
504 let sc = [3, 4, 1, 2].iter().cloned().sorted_by_key(|&x| x);
505 it::assert_equal(sc, vec![1, 2, 3, 4]);
506
507 let v = (0..5).sorted_by_key(|&x| -x);
508 it::assert_equal(v, vec![4, 3, 2, 1, 0]);
509 }
510
511 #[test]
sorted_by_cached_key()512 fn sorted_by_cached_key() {
513 // Track calls to key function
514 let mut ncalls = 0;
515
516 let sorted = [3, 4, 1, 2].iter().cloned().sorted_by_cached_key(|&x| {
517 ncalls += 1;
518 x.to_string()
519 });
520 it::assert_equal(sorted, vec![1, 2, 3, 4]);
521 // Check key function called once per element
522 assert_eq!(ncalls, 4);
523
524 let mut ncalls = 0;
525
526 let sorted = (0..5).sorted_by_cached_key(|&x| {
527 ncalls += 1;
528 -x
529 });
530 it::assert_equal(sorted, vec![4, 3, 2, 1, 0]);
531 // Check key function called once per element
532 assert_eq!(ncalls, 5);
533 }
534
535 #[test]
test_multipeek()536 fn test_multipeek() {
537 let nums = vec![1u8,2,3,4,5];
538
539 let mp = multipeek(nums.iter().copied());
540 assert_eq!(nums, mp.collect::<Vec<_>>());
541
542 let mut mp = multipeek(nums.iter().copied());
543 assert_eq!(mp.peek(), Some(&1));
544 assert_eq!(mp.next(), Some(1));
545 assert_eq!(mp.peek(), Some(&2));
546 assert_eq!(mp.peek(), Some(&3));
547 assert_eq!(mp.next(), Some(2));
548 assert_eq!(mp.peek(), Some(&3));
549 assert_eq!(mp.peek(), Some(&4));
550 assert_eq!(mp.peek(), Some(&5));
551 assert_eq!(mp.peek(), None);
552 assert_eq!(mp.next(), Some(3));
553 assert_eq!(mp.next(), Some(4));
554 assert_eq!(mp.peek(), Some(&5));
555 assert_eq!(mp.peek(), None);
556 assert_eq!(mp.next(), Some(5));
557 assert_eq!(mp.next(), None);
558 assert_eq!(mp.peek(), None);
559 }
560
561 #[test]
test_multipeek_reset()562 fn test_multipeek_reset() {
563 let data = [1, 2, 3, 4];
564
565 let mut mp = multipeek(cloned(&data));
566 assert_eq!(mp.peek(), Some(&1));
567 assert_eq!(mp.next(), Some(1));
568 assert_eq!(mp.peek(), Some(&2));
569 assert_eq!(mp.peek(), Some(&3));
570 mp.reset_peek();
571 assert_eq!(mp.peek(), Some(&2));
572 assert_eq!(mp.next(), Some(2));
573 }
574
575 #[test]
test_multipeek_peeking_next()576 fn test_multipeek_peeking_next() {
577 use crate::it::PeekingNext;
578 let nums = vec![1u8,2,3,4,5,6,7];
579
580 let mut mp = multipeek(nums.iter().copied());
581 assert_eq!(mp.peeking_next(|&x| x != 0), Some(1));
582 assert_eq!(mp.next(), Some(2));
583 assert_eq!(mp.peek(), Some(&3));
584 assert_eq!(mp.peek(), Some(&4));
585 assert_eq!(mp.peeking_next(|&x| x == 3), Some(3));
586 assert_eq!(mp.peek(), Some(&4));
587 assert_eq!(mp.peeking_next(|&x| x != 4), None);
588 assert_eq!(mp.peeking_next(|&x| x == 4), Some(4));
589 assert_eq!(mp.peek(), Some(&5));
590 assert_eq!(mp.peek(), Some(&6));
591 assert_eq!(mp.peeking_next(|&x| x != 5), None);
592 assert_eq!(mp.peek(), Some(&7));
593 assert_eq!(mp.peeking_next(|&x| x == 5), Some(5));
594 assert_eq!(mp.peeking_next(|&x| x == 6), Some(6));
595 assert_eq!(mp.peek(), Some(&7));
596 assert_eq!(mp.peek(), None);
597 assert_eq!(mp.next(), Some(7));
598 assert_eq!(mp.peek(), None);
599 }
600
601 #[test]
test_peek_nth()602 fn test_peek_nth() {
603 let nums = vec![1u8,2,3,4,5];
604
605 let iter = peek_nth(nums.iter().copied());
606 assert_eq!(nums, iter.collect::<Vec<_>>());
607
608 let mut iter = peek_nth(nums.iter().copied());
609
610 assert_eq!(iter.peek_nth(0), Some(&1));
611 assert_eq!(iter.peek_nth(0), Some(&1));
612 assert_eq!(iter.next(), Some(1));
613
614 assert_eq!(iter.peek_nth(0), Some(&2));
615 assert_eq!(iter.peek_nth(1), Some(&3));
616 assert_eq!(iter.next(), Some(2));
617
618 assert_eq!(iter.peek_nth(0), Some(&3));
619 assert_eq!(iter.peek_nth(1), Some(&4));
620 assert_eq!(iter.peek_nth(2), Some(&5));
621 assert_eq!(iter.peek_nth(3), None);
622
623 assert_eq!(iter.next(), Some(3));
624 assert_eq!(iter.next(), Some(4));
625
626 assert_eq!(iter.peek_nth(0), Some(&5));
627 assert_eq!(iter.peek_nth(1), None);
628 assert_eq!(iter.next(), Some(5));
629 assert_eq!(iter.next(), None);
630
631 assert_eq!(iter.peek_nth(0), None);
632 assert_eq!(iter.peek_nth(1), None);
633 }
634
635 #[test]
test_peek_nth_peeking_next()636 fn test_peek_nth_peeking_next() {
637 use it::PeekingNext;
638 let nums = vec![1u8,2,3,4,5,6,7];
639 let mut iter = peek_nth(nums.iter().copied());
640
641 assert_eq!(iter.peeking_next(|&x| x != 0), Some(1));
642 assert_eq!(iter.next(), Some(2));
643
644 assert_eq!(iter.peek_nth(0), Some(&3));
645 assert_eq!(iter.peek_nth(1), Some(&4));
646 assert_eq!(iter.peeking_next(|&x| x == 3), Some(3));
647 assert_eq!(iter.peek(), Some(&4));
648
649 assert_eq!(iter.peeking_next(|&x| x != 4), None);
650 assert_eq!(iter.peeking_next(|&x| x == 4), Some(4));
651 assert_eq!(iter.peek_nth(0), Some(&5));
652 assert_eq!(iter.peek_nth(1), Some(&6));
653
654 assert_eq!(iter.peeking_next(|&x| x != 5), None);
655 assert_eq!(iter.peek(), Some(&5));
656
657 assert_eq!(iter.peeking_next(|&x| x == 5), Some(5));
658 assert_eq!(iter.peeking_next(|&x| x == 6), Some(6));
659 assert_eq!(iter.peek_nth(0), Some(&7));
660 assert_eq!(iter.peek_nth(1), None);
661 assert_eq!(iter.next(), Some(7));
662 assert_eq!(iter.peek(), None);
663 }
664
665 #[test]
pad_using()666 fn pad_using() {
667 it::assert_equal((0..0).pad_using(1, |_| 1), 1..2);
668
669 let v: Vec<usize> = vec![0, 1, 2];
670 let r = v.into_iter().pad_using(5, |n| n);
671 it::assert_equal(r, vec![0, 1, 2, 3, 4]);
672
673 let v: Vec<usize> = vec![0, 1, 2];
674 let r = v.into_iter().pad_using(1, |_| panic!());
675 it::assert_equal(r, vec![0, 1, 2]);
676 }
677
678 #[test]
group_by()679 fn group_by() {
680 for (ch1, sub) in &"AABBCCC".chars().group_by(|&x| x) {
681 for ch2 in sub {
682 assert_eq!(ch1, ch2);
683 }
684 }
685
686 for (ch1, sub) in &"AAABBBCCCCDDDD".chars().group_by(|&x| x) {
687 for ch2 in sub {
688 assert_eq!(ch1, ch2);
689 if ch1 == 'C' {
690 break;
691 }
692 }
693 }
694
695 let toupper = |ch: &char| ch.to_uppercase().next().unwrap();
696
697 // try all possible orderings
698 for indices in permutohedron::Heap::new(&mut [0, 1, 2, 3]) {
699 let groups = "AaaBbbccCcDDDD".chars().group_by(&toupper);
700 let mut subs = groups.into_iter().collect_vec();
701
702 for &idx in &indices[..] {
703 let (key, text) = match idx {
704 0 => ('A', "Aaa".chars()),
705 1 => ('B', "Bbb".chars()),
706 2 => ('C', "ccCc".chars()),
707 3 => ('D', "DDDD".chars()),
708 _ => unreachable!(),
709 };
710 assert_eq!(key, subs[idx].0);
711 it::assert_equal(&mut subs[idx].1, text);
712 }
713 }
714
715 let groups = "AAABBBCCCCDDDD".chars().group_by(|&x| x);
716 let mut subs = groups.into_iter().map(|(_, g)| g).collect_vec();
717
718 let sd = subs.pop().unwrap();
719 let sc = subs.pop().unwrap();
720 let sb = subs.pop().unwrap();
721 let sa = subs.pop().unwrap();
722 for (a, b, c, d) in multizip((sa, sb, sc, sd)) {
723 assert_eq!(a, 'A');
724 assert_eq!(b, 'B');
725 assert_eq!(c, 'C');
726 assert_eq!(d, 'D');
727 }
728
729 // check that the key closure is called exactly n times
730 {
731 let mut ntimes = 0;
732 let text = "AABCCC";
733 for (_, sub) in &text.chars().group_by(|&x| { ntimes += 1; x}) {
734 for _ in sub {
735 }
736 }
737 assert_eq!(ntimes, text.len());
738 }
739
740 {
741 let mut ntimes = 0;
742 let text = "AABCCC";
743 for _ in &text.chars().group_by(|&x| { ntimes += 1; x}) {
744 }
745 assert_eq!(ntimes, text.len());
746 }
747
748 {
749 let text = "ABCCCDEEFGHIJJKK";
750 let gr = text.chars().group_by(|&x| x);
751 it::assert_equal(gr.into_iter().flat_map(|(_, sub)| sub), text.chars());
752 }
753 }
754
755 #[test]
group_by_lazy_2()756 fn group_by_lazy_2() {
757 let data = vec![0, 1];
758 let groups = data.iter().group_by(|k| *k);
759 let gs = groups.into_iter().collect_vec();
760 it::assert_equal(data.iter(), gs.into_iter().flat_map(|(_k, g)| g));
761
762 let data = vec![0, 1, 1, 0, 0];
763 let groups = data.iter().group_by(|k| *k);
764 let mut gs = groups.into_iter().collect_vec();
765 gs[1..].reverse();
766 it::assert_equal(&[0, 0, 0, 1, 1], gs.into_iter().flat_map(|(_, g)| g));
767
768 let grouper = data.iter().group_by(|k| *k);
769 let mut groups = Vec::new();
770 for (k, group) in &grouper {
771 if *k == 1 {
772 groups.push(group);
773 }
774 }
775 it::assert_equal(&mut groups[0], &[1, 1]);
776
777 let data = vec![0, 0, 0, 1, 1, 0, 0, 2, 2, 3, 3];
778 let grouper = data.iter().group_by(|k| *k);
779 let mut groups = Vec::new();
780 for (i, (_, group)) in grouper.into_iter().enumerate() {
781 if i < 2 {
782 groups.push(group);
783 } else if i < 4 {
784 for _ in group {
785 }
786 } else {
787 groups.push(group);
788 }
789 }
790 it::assert_equal(&mut groups[0], &[0, 0, 0]);
791 it::assert_equal(&mut groups[1], &[1, 1]);
792 it::assert_equal(&mut groups[2], &[3, 3]);
793
794 // use groups as chunks
795 let data = vec![0, 0, 0, 1, 1, 0, 0, 2, 2, 3, 3];
796 let mut i = 0;
797 let grouper = data.iter().group_by(move |_| { let k = i / 3; i += 1; k });
798 for (i, group) in &grouper {
799 match i {
800 0 => it::assert_equal(group, &[0, 0, 0]),
801 1 => it::assert_equal(group, &[1, 1, 0]),
802 2 => it::assert_equal(group, &[0, 2, 2]),
803 3 => it::assert_equal(group, &[3, 3]),
804 _ => unreachable!(),
805 }
806 }
807 }
808
809 #[test]
group_by_lazy_3()810 fn group_by_lazy_3() {
811 // test consuming each group on the lap after it was produced
812 let data = vec![0, 0, 0, 1, 1, 0, 0, 1, 1, 2, 2];
813 let grouper = data.iter().group_by(|elt| *elt);
814 let mut last = None;
815 for (key, group) in &grouper {
816 if let Some(gr) = last.take() {
817 for elt in gr {
818 assert!(elt != key && i32::abs(elt - key) == 1);
819 }
820 }
821 last = Some(group);
822 }
823 }
824
825 #[test]
chunks()826 fn chunks() {
827 let data = vec![0, 0, 0, 1, 1, 0, 0, 2, 2, 3, 3];
828 let grouper = data.iter().chunks(3);
829 for (i, chunk) in grouper.into_iter().enumerate() {
830 match i {
831 0 => it::assert_equal(chunk, &[0, 0, 0]),
832 1 => it::assert_equal(chunk, &[1, 1, 0]),
833 2 => it::assert_equal(chunk, &[0, 2, 2]),
834 3 => it::assert_equal(chunk, &[3, 3]),
835 _ => unreachable!(),
836 }
837 }
838 }
839
840 #[test]
concat_empty()841 fn concat_empty() {
842 let data: Vec<Vec<()>> = Vec::new();
843 assert_eq!(data.into_iter().concat(), Vec::new())
844 }
845
846 #[test]
concat_non_empty()847 fn concat_non_empty() {
848 let data = vec![vec![1,2,3], vec![4,5,6], vec![7,8,9]];
849 assert_eq!(data.into_iter().concat(), vec![1,2,3,4,5,6,7,8,9])
850 }
851
852 #[test]
combinations()853 fn combinations() {
854 assert!((1..3).combinations(5).next().is_none());
855
856 let it = (1..3).combinations(2);
857 it::assert_equal(it, vec![
858 vec![1, 2],
859 ]);
860
861 let it = (1..5).combinations(2);
862 it::assert_equal(it, vec![
863 vec![1, 2],
864 vec![1, 3],
865 vec![1, 4],
866 vec![2, 3],
867 vec![2, 4],
868 vec![3, 4],
869 ]);
870
871 it::assert_equal((0..0).tuple_combinations::<(_, _)>(), <Vec<_>>::new());
872 it::assert_equal((0..1).tuple_combinations::<(_, _)>(), <Vec<_>>::new());
873 it::assert_equal((0..2).tuple_combinations::<(_, _)>(), vec![(0, 1)]);
874
875 it::assert_equal((0..0).combinations(2), <Vec<Vec<_>>>::new());
876 it::assert_equal((0..1).combinations(1), vec![vec![0]]);
877 it::assert_equal((0..2).combinations(1), vec![vec![0], vec![1]]);
878 it::assert_equal((0..2).combinations(2), vec![vec![0, 1]]);
879 }
880
881 #[test]
combinations_of_too_short()882 fn combinations_of_too_short() {
883 for i in 1..10 {
884 assert!((0..0).combinations(i).next().is_none());
885 assert!((0..i - 1).combinations(i).next().is_none());
886 }
887 }
888
889
890 #[test]
combinations_zero()891 fn combinations_zero() {
892 it::assert_equal((1..3).combinations(0), vec![vec![]]);
893 it::assert_equal((0..0).combinations(0), vec![vec![]]);
894 }
895
896 #[test]
permutations_zero()897 fn permutations_zero() {
898 it::assert_equal((1..3).permutations(0), vec![vec![]]);
899 it::assert_equal((0..0).permutations(0), vec![vec![]]);
900 }
901
902 #[test]
combinations_with_replacement()903 fn combinations_with_replacement() {
904 // Pool smaller than n
905 it::assert_equal((0..1).combinations_with_replacement(2), vec![vec![0, 0]]);
906 // Pool larger than n
907 it::assert_equal(
908 (0..3).combinations_with_replacement(2),
909 vec![
910 vec![0, 0],
911 vec![0, 1],
912 vec![0, 2],
913 vec![1, 1],
914 vec![1, 2],
915 vec![2, 2],
916 ],
917 );
918 // Zero size
919 it::assert_equal(
920 (0..3).combinations_with_replacement(0),
921 vec![vec![]],
922 );
923 // Zero size on empty pool
924 it::assert_equal(
925 (0..0).combinations_with_replacement(0),
926 vec![vec![]],
927 );
928 // Empty pool
929 it::assert_equal(
930 (0..0).combinations_with_replacement(2),
931 <Vec<Vec<_>>>::new(),
932 );
933 }
934
935 #[test]
powerset()936 fn powerset() {
937 it::assert_equal((0..0).powerset(), vec![vec![]]);
938 it::assert_equal((0..1).powerset(), vec![vec![], vec![0]]);
939 it::assert_equal((0..2).powerset(), vec![vec![], vec![0], vec![1], vec![0, 1]]);
940 it::assert_equal((0..3).powerset(), vec![
941 vec![],
942 vec![0], vec![1], vec![2],
943 vec![0, 1], vec![0, 2], vec![1, 2],
944 vec![0, 1, 2]
945 ]);
946
947 assert_eq!((0..4).powerset().count(), 1 << 4);
948 assert_eq!((0..8).powerset().count(), 1 << 8);
949 assert_eq!((0..16).powerset().count(), 1 << 16);
950 }
951
952 #[test]
diff_mismatch()953 fn diff_mismatch() {
954 let a = vec![1, 2, 3, 4];
955 let b = vec![1.0, 5.0, 3.0, 4.0];
956 let b_map = b.into_iter().map(|f| f as i32);
957 let diff = it::diff_with(a.iter(), b_map, |a, b| *a == b);
958
959 assert!(match diff {
960 Some(it::Diff::FirstMismatch(1, _, from_diff)) =>
961 from_diff.collect::<Vec<_>>() == vec![5, 3, 4],
962 _ => false,
963 });
964 }
965
966 #[test]
diff_longer()967 fn diff_longer() {
968 let a = vec![1, 2, 3, 4];
969 let b = vec![1.0, 2.0, 3.0, 4.0, 5.0, 6.0];
970 let b_map = b.into_iter().map(|f| f as i32);
971 let diff = it::diff_with(a.iter(), b_map, |a, b| *a == b);
972
973 assert!(match diff {
974 Some(it::Diff::Longer(_, remaining)) =>
975 remaining.collect::<Vec<_>>() == vec![5, 6],
976 _ => false,
977 });
978 }
979
980 #[test]
diff_shorter()981 fn diff_shorter() {
982 let a = vec![1, 2, 3, 4];
983 let b = vec![1.0, 2.0];
984 let b_map = b.into_iter().map(|f| f as i32);
985 let diff = it::diff_with(a.iter(), b_map, |a, b| *a == b);
986
987 assert!(match diff {
988 Some(it::Diff::Shorter(len, _)) => len == 2,
989 _ => false,
990 });
991 }
992
993 #[test]
extrema_set()994 fn extrema_set() {
995 use std::cmp::Ordering;
996
997 // A peculiar type: Equality compares both tuple items, but ordering only the
998 // first item. Used to distinguish equal elements.
999 #[derive(Clone, Debug, PartialEq, Eq)]
1000 struct Val(u32, u32);
1001
1002 impl PartialOrd<Val> for Val {
1003 fn partial_cmp(&self, other: &Val) -> Option<Ordering> {
1004 self.0.partial_cmp(&other.0)
1005 }
1006 }
1007
1008 impl Ord for Val {
1009 fn cmp(&self, other: &Val) -> Ordering {
1010 self.0.cmp(&other.0)
1011 }
1012 }
1013
1014 assert_eq!(None::<u32>.iter().min_set(), Vec::<&u32>::new());
1015 assert_eq!(None::<u32>.iter().max_set(), Vec::<&u32>::new());
1016
1017 assert_eq!(Some(1u32).iter().min_set(), vec![&1]);
1018 assert_eq!(Some(1u32).iter().max_set(), vec![&1]);
1019
1020 let data = vec![Val(0, 1), Val(2, 0), Val(0, 2), Val(1, 0), Val(2, 1)];
1021
1022 let min_set = data.iter().min_set();
1023 assert_eq!(min_set, vec![&Val(0, 1), &Val(0, 2)]);
1024
1025 let min_set_by_key = data.iter().min_set_by_key(|v| v.1);
1026 assert_eq!(min_set_by_key, vec![&Val(2, 0), &Val(1, 0)]);
1027
1028 let min_set_by = data.iter().min_set_by(|x, y| x.1.cmp(&y.1));
1029 assert_eq!(min_set_by, vec![&Val(2, 0), &Val(1, 0)]);
1030
1031 let max_set = data.iter().max_set();
1032 assert_eq!(max_set, vec![&Val(2, 0), &Val(2, 1)]);
1033
1034 let max_set_by_key = data.iter().max_set_by_key(|v| v.1);
1035 assert_eq!(max_set_by_key, vec![&Val(0, 2)]);
1036
1037 let max_set_by = data.iter().max_set_by(|x, y| x.1.cmp(&y.1));
1038 assert_eq!(max_set_by, vec![&Val(0, 2)]);
1039 }
1040
1041 #[test]
minmax()1042 fn minmax() {
1043 use std::cmp::Ordering;
1044 use crate::it::MinMaxResult;
1045
1046 // A peculiar type: Equality compares both tuple items, but ordering only the
1047 // first item. This is so we can check the stability property easily.
1048 #[derive(Clone, Debug, PartialEq, Eq)]
1049 struct Val(u32, u32);
1050
1051 impl PartialOrd<Val> for Val {
1052 fn partial_cmp(&self, other: &Val) -> Option<Ordering> {
1053 self.0.partial_cmp(&other.0)
1054 }
1055 }
1056
1057 impl Ord for Val {
1058 fn cmp(&self, other: &Val) -> Ordering {
1059 self.0.cmp(&other.0)
1060 }
1061 }
1062
1063 assert_eq!(None::<Option<u32>>.iter().minmax(), MinMaxResult::NoElements);
1064
1065 assert_eq!(Some(1u32).iter().minmax(), MinMaxResult::OneElement(&1));
1066
1067 let data = vec![Val(0, 1), Val(2, 0), Val(0, 2), Val(1, 0), Val(2, 1)];
1068
1069 let minmax = data.iter().minmax();
1070 assert_eq!(minmax, MinMaxResult::MinMax(&Val(0, 1), &Val(2, 1)));
1071
1072 let (min, max) = data.iter().minmax_by_key(|v| v.1).into_option().unwrap();
1073 assert_eq!(min, &Val(2, 0));
1074 assert_eq!(max, &Val(0, 2));
1075
1076 let (min, max) = data.iter().minmax_by(|x, y| x.1.cmp(&y.1)).into_option().unwrap();
1077 assert_eq!(min, &Val(2, 0));
1078 assert_eq!(max, &Val(0, 2));
1079 }
1080
1081 #[test]
format()1082 fn format() {
1083 let data = [0, 1, 2, 3];
1084 let ans1 = "0, 1, 2, 3";
1085 let ans2 = "0--1--2--3";
1086
1087 let t1 = format!("{}", data.iter().format(", "));
1088 assert_eq!(t1, ans1);
1089 let t2 = format!("{:?}", data.iter().format("--"));
1090 assert_eq!(t2, ans2);
1091
1092 let dataf = [1.1, 5.71828, -22.];
1093 let t3 = format!("{:.2e}", dataf.iter().format(", "));
1094 assert_eq!(t3, "1.10e0, 5.72e0, -2.20e1");
1095 }
1096
1097 #[test]
while_some()1098 fn while_some() {
1099 let ns = (1..10).map(|x| if x % 5 != 0 { Some(x) } else { None })
1100 .while_some();
1101 it::assert_equal(ns, vec![1, 2, 3, 4]);
1102 }
1103
1104 #[allow(deprecated)]
1105 #[test]
fold_while()1106 fn fold_while() {
1107 let mut iterations = 0;
1108 let vec = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
1109 let sum = vec.into_iter().fold_while(0, |acc, item| {
1110 iterations += 1;
1111 let new_sum = acc + item;
1112 if new_sum <= 20 {
1113 FoldWhile::Continue(new_sum)
1114 } else {
1115 FoldWhile::Done(acc)
1116 }
1117 }).into_inner();
1118 assert_eq!(iterations, 6);
1119 assert_eq!(sum, 15);
1120 }
1121
1122 #[test]
tree_fold1()1123 fn tree_fold1() {
1124 let x = [
1125 "",
1126 "0",
1127 "0 1 x",
1128 "0 1 x 2 x",
1129 "0 1 x 2 3 x x",
1130 "0 1 x 2 3 x x 4 x",
1131 "0 1 x 2 3 x x 4 5 x x",
1132 "0 1 x 2 3 x x 4 5 x 6 x x",
1133 "0 1 x 2 3 x x 4 5 x 6 7 x x x",
1134 "0 1 x 2 3 x x 4 5 x 6 7 x x x 8 x",
1135 "0 1 x 2 3 x x 4 5 x 6 7 x x x 8 9 x x",
1136 "0 1 x 2 3 x x 4 5 x 6 7 x x x 8 9 x 10 x x",
1137 "0 1 x 2 3 x x 4 5 x 6 7 x x x 8 9 x 10 11 x x x",
1138 "0 1 x 2 3 x x 4 5 x 6 7 x x x 8 9 x 10 11 x x 12 x x",
1139 "0 1 x 2 3 x x 4 5 x 6 7 x x x 8 9 x 10 11 x x 12 13 x x x",
1140 "0 1 x 2 3 x x 4 5 x 6 7 x x x 8 9 x 10 11 x x 12 13 x 14 x x x",
1141 "0 1 x 2 3 x x 4 5 x 6 7 x x x 8 9 x 10 11 x x 12 13 x 14 15 x x x x",
1142 ];
1143 for (i, &s) in x.iter().enumerate() {
1144 let expected = if s.is_empty() { None } else { Some(s.to_string()) };
1145 let num_strings = (0..i).map(|x| x.to_string());
1146 let actual = num_strings.tree_fold1(|a, b| format!("{} {} x", a, b));
1147 assert_eq!(actual, expected);
1148 }
1149 }
1150
1151 #[test]
exactly_one_question_mark_syntax_works()1152 fn exactly_one_question_mark_syntax_works() {
1153 exactly_one_question_mark_return().unwrap_err();
1154 }
1155
exactly_one_question_mark_return() -> Result<(), ExactlyOneError<std::slice::Iter<'static, ()>>>1156 fn exactly_one_question_mark_return() -> Result<(), ExactlyOneError<std::slice::Iter<'static, ()>>> {
1157 [].iter().exactly_one()?;
1158 Ok(())
1159 }
1160
1161 #[test]
multiunzip()1162 fn multiunzip() {
1163 let (a, b, c): (Vec<_>, Vec<_>, Vec<_>) = [(0, 1, 2), (3, 4, 5), (6, 7, 8)].iter().cloned().multiunzip();
1164 assert_eq!((a, b, c), (vec![0, 3, 6], vec![1, 4, 7], vec![2, 5, 8]));
1165 let (): () = [(), (), ()].iter().cloned().multiunzip();
1166 let t: (Vec<_>, Vec<_>, Vec<_>, Vec<_>, Vec<_>, Vec<_>, Vec<_>, Vec<_>, Vec<_>, Vec<_>, Vec<_>, Vec<_>) = [(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11)].iter().cloned().multiunzip();
1167 assert_eq!(t, (vec![0], vec![1], vec![2], vec![3], vec![4], vec![5], vec![6], vec![7], vec![8], vec![9], vec![10], vec![11]));
1168 }
1169