1use quickcheck as qc;
2use rand::{distributions::{Distribution, Standard}, Rng, SeedableRng, rngs::StdRng};
3use rand::{seq::SliceRandom, thread_rng};
4use std::{cmp::min, fmt::Debug, marker::PhantomData};
5use itertools as it;
6use crate::it::Itertools;
7use crate::it::ExactlyOneError;
8use crate::it::multizip;
9use crate::it::multipeek;
10use crate::it::peek_nth;
11use crate::it::free::rciter;
12use crate::it::free::put_back_n;
13use crate::it::FoldWhile;
14use crate::it::cloned;
15use crate::it::iproduct;
16use crate::it::izip;
17
18#[test]
19fn 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]
36fn 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]
61fn 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]
71fn 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]
95fn 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]
105fn 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]
122fn 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]
134fn 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]
150fn 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]
170fn 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]
186fn 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]
200fn 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]
213fn 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]
224fn 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]
231fn 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]
242fn 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]
269fn 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]
290fn 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]
322fn 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]
331fn 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]
346fn 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]
354fn 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]
361fn kmerge_empty() {
362 let its = (0..4).map(|_| 0..0);
363 assert_eq!(its.kmerge().next(), None);
364}
365
366#[test]
367fn 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]
373fn 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]
379fn 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]
390fn 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]
401fn 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]
410fn 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
420qc::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)]
442struct 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
449impl<T: Clone + Send, R: Clone + Rng + SeedableRng + Send> Iterator for RandIter<T, R>
450where Standard: Distribution<T> {
451 type Item = 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
462impl<T: Clone + Send, R: Clone + Rng + SeedableRng + Send> qc::Arbitrary for RandIter<T, R> {
463 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
475fn k_smallest_sort<I>(i: I, k: u16)
476where
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
488macro_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
500generic_test!(k_smallest_sort, u8, u16, u32, u64, i8, i16, i32, i64);
501
502#[test]
503fn 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]
512fn 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]
536fn 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]
562fn 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]
576fn 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]
602fn 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]
636fn 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]
666fn 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]
679fn 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]
756fn 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]
810fn 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]
826fn 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]
841fn concat_empty() {
842 let data: Vec<Vec<()>> = Vec::new();
843 assert_eq!(data.into_iter().concat(), Vec::new())
844}
845
846#[test]
847fn 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]
853fn 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]
882fn 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]
891fn 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]
897fn 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]
903fn 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]
936fn 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]
953fn 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]
967fn 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]
981fn 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]
994fn 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]
1042fn 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]
1082fn 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]
1098fn 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]
1106fn 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]
1123fn 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]
1152fn exactly_one_question_mark_syntax_works() {
1153 exactly_one_question_mark_return().unwrap_err();
1154}
1155
1156fn exactly_one_question_mark_return() -> Result<(), ExactlyOneError<std::slice::Iter<'static, ()>>> {
1157 [].iter().exactly_one()?;
1158 Ok(())
1159}
1160
1161#[test]
1162fn 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