Debian Codegraph @

.cargo/vendor/itertools/tests/test_std.rs

raw
1 #![allow(unstable_name_collisions)]
2
3 use crate::it::cloned;
4 use crate::it::free::put_back_n;
5 use crate::it::free::rciter;
6 use crate::it::iproduct;
7 use crate::it::izip;
8 use crate::it::multipeek;
9 use crate::it::multizip;
10 use crate::it::peek_nth;
11 use crate::it::repeat_n;
12 use crate::it::ExactlyOneError;
13 use crate::it::FoldWhile;
14 use crate::it::Itertools;
15 use itertools as it;
16 use quickcheck as qc;
17 use rand::{
18 distributions::{Distribution, Standard},
19 rngs::StdRng,
20 Rng, SeedableRng,
21 };
22 use rand::{seq::SliceRandom, thread_rng};
23 use std::{cmp::min, fmt::Debug, marker::PhantomData};
24
25 #[test]
26 fn product3() {
27 let prod = iproduct!(0..3, 0..2, 0..2);
28 assert_eq!(prod.size_hint(), (12, Some(12)));
29 let v = prod.collect_vec();
30 for i in 0..3 {
31 for j in 0..2 {
32 for k in 0..2 {
33 assert!((i, j, k) == v[(i * 2 * 2 + j * 2 + k) as usize]);
34 }
35 }
36 }
37 for (_, _, _, _) in iproduct!(0..3, 0..2, 0..2, 0..3) { /* test compiles */ }
38 }
39
40 #[test]
41 fn interleave_shortest() {
42 let v0: Vec<i32> = vec![0, 2, 4];
43 let v1: Vec<i32> = vec![1, 3, 5, 7];
44 let it = v0.into_iter().interleave_shortest(v1);
45 assert_eq!(it.size_hint(), (6, Some(6)));
46 assert_eq!(it.collect_vec(), vec![0, 1, 2, 3, 4, 5]);
47
48 let v0: Vec<i32> = vec![0, 2, 4, 6, 8];
49 let v1: Vec<i32> = vec![1, 3, 5];
50 let it = v0.into_iter().interleave_shortest(v1);
51 assert_eq!(it.size_hint(), (7, Some(7)));
52 assert_eq!(it.collect_vec(), vec![0, 1, 2, 3, 4, 5, 6]);
53
54 let i0 = ::std::iter::repeat(0);
55 let v1: Vec<_> = vec![1, 3, 5];
56 let it = i0.interleave_shortest(v1);
57 assert_eq!(it.size_hint(), (7, Some(7)));
58
59 let v0: Vec<_> = vec![0, 2, 4];
60 let i1 = ::std::iter::repeat(1);
61 let it = v0.into_iter().interleave_shortest(i1);
62 assert_eq!(it.size_hint(), (6, Some(6)));
63 }
64
65 #[test]
66 fn duplicates_by() {
67 let xs = ["aaa", "bbbbb", "aa", "ccc", "bbbb", "aaaaa", "cccc"];
68 let ys = ["aa", "bbbb", "cccc"];
69 it::assert_equal(ys.iter(), xs.iter().duplicates_by(|x| x[..2].to_string()));
70 it::assert_equal(
71 ys.iter(),
72 xs.iter().rev().duplicates_by(|x| x[..2].to_string()).rev(),
73 );
74 let ys_rev = ["ccc", "aa", "bbbbb"];
75 it::assert_equal(
76 ys_rev.iter(),
77 xs.iter().duplicates_by(|x| x[..2].to_string()).rev(),
78 );
79 }
80
81 #[test]
82 fn duplicates() {
83 let xs = [0, 1, 2, 3, 2, 1, 3];
84 let ys = [2, 1, 3];
85 it::assert_equal(ys.iter(), xs.iter().duplicates());
86 it::assert_equal(ys.iter(), xs.iter().rev().duplicates().rev());
87 let ys_rev = [3, 2, 1];
88 it::assert_equal(ys_rev.iter(), xs.iter().duplicates().rev());
89
90 let xs = [0, 1, 0, 1];
91 let ys = [0, 1];
92 it::assert_equal(ys.iter(), xs.iter().duplicates());
93 it::assert_equal(ys.iter(), xs.iter().rev().duplicates().rev());
94 let ys_rev = [1, 0];
95 it::assert_equal(ys_rev.iter(), xs.iter().duplicates().rev());
96
97 let xs = [0, 1, 2, 1, 2];
98 let ys = vec![1, 2];
99 assert_eq!(ys, xs.iter().duplicates().cloned().collect_vec());
100 assert_eq!(
101 ys,
102 xs.iter().rev().duplicates().rev().cloned().collect_vec()
103 );
104 let ys_rev = vec![2, 1];
105 assert_eq!(ys_rev, xs.iter().duplicates().rev().cloned().collect_vec());
106 }
107
108 #[test]
109 fn unique_by() {
110 let xs = ["aaa", "bbbbb", "aa", "ccc", "bbbb", "aaaaa", "cccc"];
111 let ys = ["aaa", "bbbbb", "ccc"];
112 it::assert_equal(ys.iter(), xs.iter().unique_by(|x| x[..2].to_string()));
113 it::assert_equal(
114 ys.iter(),
115 xs.iter().rev().unique_by(|x| x[..2].to_string()).rev(),
116 );
117 let ys_rev = ["cccc", "aaaaa", "bbbb"];
118 it::assert_equal(
119 ys_rev.iter(),
120 xs.iter().unique_by(|x| x[..2].to_string()).rev(),
121 );
122 }
123
124 #[test]
125 fn unique() {
126 let xs = [0, 1, 2, 3, 2, 1, 3];
127 let ys = [0, 1, 2, 3];
128 it::assert_equal(ys.iter(), xs.iter().unique());
129 it::assert_equal(ys.iter(), xs.iter().rev().unique().rev());
130 let ys_rev = [3, 1, 2, 0];
131 it::assert_equal(ys_rev.iter(), xs.iter().unique().rev());
132
133 let xs = [0, 1];
134 let ys = [0, 1];
135 it::assert_equal(ys.iter(), xs.iter().unique());
136 it::assert_equal(ys.iter(), xs.iter().rev().unique().rev());
137 let ys_rev = [1, 0];
138 it::assert_equal(ys_rev.iter(), xs.iter().unique().rev());
139 }
140
141 #[test]
142 fn intersperse() {
143 let xs = ["a", "", "b", "c"];
144 let v: Vec<&str> = xs.iter().cloned().intersperse(", ").collect();
145 let text: String = v.concat();
146 assert_eq!(text, "a, , b, c".to_string());
147
148 let ys = [0, 1, 2, 3];
149 let mut it = ys[..0].iter().copied().intersperse(1);
150 assert!(it.next().is_none());
151 }
152
153 #[test]
154 fn dedup() {
155 let xs = [0, 1, 1, 1, 2, 1, 3, 3];
156 let ys = [0, 1, 2, 1, 3];
157 it::assert_equal(ys.iter(), xs.iter().dedup());
158 let xs = [0, 0, 0, 0, 0];
159 let ys = [0];
160 it::assert_equal(ys.iter(), xs.iter().dedup());
161
162 let xs = [0, 1, 1, 1, 2, 1, 3, 3];
163 let ys = [0, 1, 2, 1, 3];
164 let mut xs_d = Vec::new();
165 xs.iter().dedup().fold((), |(), &elt| xs_d.push(elt));
166 assert_eq!(&xs_d, &ys);
167 }
168
169 #[test]
170 fn coalesce() {
171 let data = [-1., -2., -3., 3., 1., 0., -1.];
172 let it = data.iter().cloned().coalesce(|x, y| {
173 if (x >= 0.) == (y >= 0.) {
174 Ok(x + y)
175 } else {
176 Err((x, y))
177 }
178 });
179 itertools::assert_equal(it.clone(), vec![-6., 4., -1.]);
180 assert_eq!(
181 it.fold(vec![], |mut v, n| {
182 v.push(n);
183 v
184 }),
185 vec![-6., 4., -1.]
186 );
187 }
188
189 #[test]
190 fn dedup_by() {
191 let xs = [
192 (0, 0),
193 (0, 1),
194 (1, 1),
195 (2, 1),
196 (0, 2),
197 (3, 1),
198 (0, 3),
199 (1, 3),
200 ];
201 let ys = [(0, 0), (0, 1), (0, 2), (3, 1), (0, 3)];
202 it::assert_equal(ys.iter(), xs.iter().dedup_by(|x, y| x.1 == y.1));
203 let xs = [(0, 1), (0, 2), (0, 3), (0, 4), (0, 5)];
204 let ys = [(0, 1)];
205 it::assert_equal(ys.iter(), xs.iter().dedup_by(|x, y| x.0 == y.0));
206
207 let xs = [
208 (0, 0),
209 (0, 1),
210 (1, 1),
211 (2, 1),
212 (0, 2),
213 (3, 1),
214 (0, 3),
215 (1, 3),
216 ];
217 let ys = [(0, 0), (0, 1), (0, 2), (3, 1), (0, 3)];
218 let mut xs_d = Vec::new();
219 xs.iter()
220 .dedup_by(|x, y| x.1 == y.1)
221 .fold((), |(), &elt| xs_d.push(elt));
222 assert_eq!(&xs_d, &ys);
223 }
224
225 #[test]
226 fn dedup_with_count() {
227 let xs: [i32; 8] = [0, 1, 1, 1, 2, 1, 3, 3];
228 let ys: [(usize, &i32); 5] = [(1, &0), (3, &1), (1, &2), (1, &1), (2, &3)];
229
230 it::assert_equal(ys.iter().cloned(), xs.iter().dedup_with_count());
231
232 let xs: [i32; 5] = [0, 0, 0, 0, 0];
233 let ys: [(usize, &i32); 1] = [(5, &0)];
234
235 it::assert_equal(ys.iter().cloned(), xs.iter().dedup_with_count());
236 }
237
238 #[test]
239 fn dedup_by_with_count() {
240 let xs = [
241 (0, 0),
242 (0, 1),
243 (1, 1),
244 (2, 1),
245 (0, 2),
246 (3, 1),
247 (0, 3),
248 (1, 3),
249 ];
250 let ys = [
251 (1, &(0, 0)),
252 (3, &(0, 1)),
253 (1, &(0, 2)),
254 (1, &(3, 1)),
255 (2, &(0, 3)),
256 ];
257
258 it::assert_equal(
259 ys.iter().cloned(),
260 xs.iter().dedup_by_with_count(|x, y| x.1 == y.1),
261 );
262
263 let xs = [(0, 1), (0, 2), (0, 3), (0, 4), (0, 5)];
264 let ys = [(5, &(0, 1))];
265
266 it::assert_equal(
267 ys.iter().cloned(),
268 xs.iter().dedup_by_with_count(|x, y| x.0 == y.0),
269 );
270 }
271
272 #[test]
273 fn all_equal() {
274 assert!("".chars().all_equal());
275 assert!("A".chars().all_equal());
276 assert!(!"AABBCCC".chars().all_equal());
277 assert!("AAAAAAA".chars().all_equal());
278 for (_key, mut sub) in &"AABBCCC".chars().chunk_by(|&x| x) {
279 assert!(sub.all_equal());
280 }
281 }
282
283 #[test]
284 fn all_equal_value() {
285 assert_eq!("".chars().all_equal_value(), Err(None));
286 assert_eq!("A".chars().all_equal_value(), Ok('A'));
287 assert_eq!("AABBCCC".chars().all_equal_value(), Err(Some(('A', 'B'))));
288 assert_eq!("AAAAAAA".chars().all_equal_value(), Ok('A'));
289 {
290 let mut it = [1, 2, 3].iter().copied();
291 let result = it.all_equal_value();
292 assert_eq!(result, Err(Some((1, 2))));
293 let remaining = it.next();
294 assert_eq!(remaining, Some(3));
295 assert!(it.next().is_none());
296 }
297 }
298
299 #[test]
300 fn all_unique() {
301 assert!("ABCDEFGH".chars().all_unique());
302 assert!(!"ABCDEFGA".chars().all_unique());
303 assert!(::std::iter::empty::<usize>().all_unique());
304 }
305
306 #[test]
307 fn test_put_back_n() {
308 let xs = [0, 1, 1, 1, 2, 1, 3, 3];
309 let mut pb = put_back_n(xs.iter().cloned());
310 pb.next();
311 pb.next();
312 pb.put_back(1);
313 pb.put_back(0);
314 it::assert_equal(pb, xs.iter().cloned());
315 }
316
317 #[test]
318 fn tee() {
319 let xs = [0, 1, 2, 3];
320 let (mut t1, mut t2) = xs.iter().cloned().tee();
321 assert_eq!(t1.next(), Some(0));
322 assert_eq!(t2.next(), Some(0));
323 assert_eq!(t1.next(), Some(1));
324 assert_eq!(t1.next(), Some(2));
325 assert_eq!(t1.next(), Some(3));
326 assert_eq!(t1.next(), None);
327 assert_eq!(t2.next(), Some(1));
328 assert_eq!(t2.next(), Some(2));
329 assert_eq!(t1.next(), None);
330 assert_eq!(t2.next(), Some(3));
331 assert_eq!(t2.next(), None);
332 assert_eq!(t1.next(), None);
333 assert_eq!(t2.next(), None);
334
335 let (t1, t2) = xs.iter().cloned().tee();
336 it::assert_equal(t1, xs.iter().cloned());
337 it::assert_equal(t2, xs.iter().cloned());
338
339 let (t1, t2) = xs.iter().cloned().tee();
340 it::assert_equal(t1.zip(t2), xs.iter().cloned().zip(xs.iter().cloned()));
341 }
342
343 #[test]
344 fn test_rciter() {
345 let xs = [0, 1, 1, 1, 2, 1, 3, 5, 6];
346
347 let mut r1 = rciter(xs.iter().cloned());
348 let mut r2 = r1.clone();
349 assert_eq!(r1.next(), Some(0));
350 assert_eq!(r2.next(), Some(1));
351 let mut z = r1.zip(r2);
352 assert_eq!(z.next(), Some((1, 1)));
353 assert_eq!(z.next(), Some((2, 1)));
354 assert_eq!(z.next(), Some((3, 5)));
355 assert_eq!(z.next(), None);
356
357 // test intoiterator
358 let r1 = rciter(0..5);
359 let mut z = izip!(&r1, r1);
360 assert_eq!(z.next(), Some((0, 1)));
361 }
362
363 #[test]
364 fn trait_pointers() {
365 struct ByRef<'r, I: ?Sized>(&'r mut I);
366
367 impl<'r, X, I> Iterator for ByRef<'r, I>
368 where
369 I: ?Sized + 'r + Iterator<Item = X>,
370 {
371 type Item = X;
372 fn next(&mut self) -> Option<Self::Item> {
373 self.0.next()
374 }
375 }
376
377 let mut it = Box::new(0..10) as Box<dyn Iterator<Item = i32>>;
378 assert_eq!(it.next(), Some(0));
379
380 {
381 let jt: &mut dyn Iterator<Item = i32> = &mut *it;
382 assert_eq!(jt.next(), Some(1));
383
384 {
385 let mut r = ByRef(jt);
386 assert_eq!(r.next(), Some(2));
387 }
388
389 assert_eq!(jt.find_position(|x| *x == 4), Some((1, 4)));
390 jt.for_each(|_| ());
391 }
392 }
393
394 #[test]
395 fn merge_by() {
396 let odd: Vec<(u32, &str)> = vec![(1, "hello"), (3, "world"), (5, "!")];
397 let even = [(2, "foo"), (4, "bar"), (6, "baz")];
398 let expected = [
399 (1, "hello"),
400 (2, "foo"),
401 (3, "world"),
402 (4, "bar"),
403 (5, "!"),
404 (6, "baz"),
405 ];
406 let results = odd.iter().merge_by(even.iter(), |a, b| a.0 <= b.0);
407 it::assert_equal(results, expected.iter());
408 }
409
410 #[test]
411 fn merge_by_btree() {
412 use std::collections::BTreeMap;
413 let mut bt1 = BTreeMap::new();
414 bt1.insert("hello", 1);
415 bt1.insert("world", 3);
416 let mut bt2 = BTreeMap::new();
417 bt2.insert("foo", 2);
418 bt2.insert("bar", 4);
419 let results = bt1.into_iter().merge_by(bt2, |a, b| a.0 <= b.0);
420 let expected = vec![("bar", 4), ("foo", 2), ("hello", 1), ("world", 3)];
421 it::assert_equal(results, expected);
422 }
423
424 #[test]
425 fn kmerge() {
426 let its = (0..4).map(|s| (s..10).step_by(4));
427
428 it::assert_equal(its.kmerge(), 0..10);
429 }
430
431 #[test]
432 fn kmerge_2() {
433 let its = vec![3, 2, 1, 0].into_iter().map(|s| (s..10).step_by(4));
434
435 it::assert_equal(its.kmerge(), 0..10);
436 }
437
438 #[test]
439 fn kmerge_empty() {
440 let its = (0..4).map(|_| 0..0);
441 assert_eq!(its.kmerge().next(), None);
442 }
443
444 #[test]
445 fn kmerge_size_hint() {
446 let its = (0..5).map(|_| (0..10));
447 assert_eq!(its.kmerge().size_hint(), (50, Some(50)));
448 }
449
450 #[test]
451 fn kmerge_empty_size_hint() {
452 let its = (0..5).map(|_| (0..0));
453 assert_eq!(its.kmerge().size_hint(), (0, Some(0)));
454 }
455
456 #[test]
457 fn join() {
458 let many = [1, 2, 3];
459 let one = [1];
460 let none: Vec<i32> = vec![];
461
462 assert_eq!(many.iter().join(", "), "1, 2, 3");
463 assert_eq!(one.iter().join(", "), "1");
464 assert_eq!(none.iter().join(", "), "");
465 }
466
467 #[test]
468 fn sorted_unstable_by() {
469 let sc = [3, 4, 1, 2].iter().cloned().sorted_by(|&a, &b| a.cmp(&b));
470 it::assert_equal(sc, vec![1, 2, 3, 4]);
471
472 let v = (0..5).sorted_unstable_by(|&a, &b| a.cmp(&b).reverse());
473 it::assert_equal(v, vec![4, 3, 2, 1, 0]);
474 }
475
476 #[test]
477 fn sorted_unstable_by_key() {
478 let sc = [3, 4, 1, 2].iter().cloned().sorted_unstable_by_key(|&x| x);
479 it::assert_equal(sc, vec![1, 2, 3, 4]);
480
481 let v = (0..5).sorted_unstable_by_key(|&x| -x);
482 it::assert_equal(v, vec![4, 3, 2, 1, 0]);
483 }
484
485 #[test]
486 fn sorted_by() {
487 let sc = [3, 4, 1, 2].iter().cloned().sorted_by(|&a, &b| a.cmp(&b));
488 it::assert_equal(sc, vec![1, 2, 3, 4]);
489
490 let v = (0..5).sorted_by(|&a, &b| a.cmp(&b).reverse());
491 it::assert_equal(v, vec![4, 3, 2, 1, 0]);
492 }
493
494 #[cfg(not(miri))]
495 qc::quickcheck! {
496 fn k_smallest_range(n: i64, m: u16, k: u16) -> () {
497 // u16 is used to constrain k and m to 0..2¹⁶,
498 // otherwise the test could use too much memory.
499 let (k, m) = (k as usize, m as u64);
500
501 let mut v: Vec<_> = (n..n.saturating_add(m as _)).collect();
502 // Generate a random permutation of n..n+m
503 v.shuffle(&mut thread_rng());
504
505 // Construct the right answers for the top and bottom elements
506 let mut sorted = v.clone();
507 sorted.sort();
508 // how many elements are we checking
509 let num_elements = min(k, m as _);
510
511 // Compute the top and bottom k in various combinations
512 let sorted_smallest = sorted[..num_elements].iter().cloned();
513 let smallest = v.iter().cloned().k_smallest(k);
514 let smallest_by = v.iter().cloned().k_smallest_by(k, Ord::cmp);
515 let smallest_by_key = v.iter().cloned().k_smallest_by_key(k, |&x| x);
516
517 let sorted_largest = sorted[sorted.len() - num_elements..].iter().rev().cloned();
518 let largest = v.iter().cloned().k_largest(k);
519 let largest_by = v.iter().cloned().k_largest_by(k, Ord::cmp);
520 let largest_by_key = v.iter().cloned().k_largest_by_key(k, |&x| x);
521
522 // Check the variations produce the same answers and that they're right
523 it::assert_equal(smallest, sorted_smallest.clone());
524 it::assert_equal(smallest_by, sorted_smallest.clone());
525 it::assert_equal(smallest_by_key, sorted_smallest);
526
527 it::assert_equal(largest, sorted_largest.clone());
528 it::assert_equal(largest_by, sorted_largest.clone());
529 it::assert_equal(largest_by_key, sorted_largest);
530 }
531
532 fn k_smallest_relaxed_range(n: i64, m: u16, k: u16) -> () {
533 // u16 is used to constrain k and m to 0..2¹⁶,
534 // otherwise the test could use too much memory.
535 let (k, m) = (k as usize, m as u64);
536
537 let mut v: Vec<_> = (n..n.saturating_add(m as _)).collect();
538 // Generate a random permutation of n..n+m
539 v.shuffle(&mut thread_rng());
540
541 // Construct the right answers for the top and bottom elements
542 let mut sorted = v.clone();
543 sorted.sort();
544 // how many elements are we checking
545 let num_elements = min(k, m as _);
546
547 // Compute the top and bottom k in various combinations
548 let sorted_smallest = sorted[..num_elements].iter().cloned();
549 let smallest = v.iter().cloned().k_smallest_relaxed(k);
550 let smallest_by = v.iter().cloned().k_smallest_relaxed_by(k, Ord::cmp);
551 let smallest_by_key = v.iter().cloned().k_smallest_relaxed_by_key(k, |&x| x);
552
553 let sorted_largest = sorted[sorted.len() - num_elements..].iter().rev().cloned();
554 let largest = v.iter().cloned().k_largest_relaxed(k);
555 let largest_by = v.iter().cloned().k_largest_relaxed_by(k, Ord::cmp);
556 let largest_by_key = v.iter().cloned().k_largest_relaxed_by_key(k, |&x| x);
557
558 // Check the variations produce the same answers and that they're right
559 it::assert_equal(smallest, sorted_smallest.clone());
560 it::assert_equal(smallest_by, sorted_smallest.clone());
561 it::assert_equal(smallest_by_key, sorted_smallest);
562
563 it::assert_equal(largest, sorted_largest.clone());
564 it::assert_equal(largest_by, sorted_largest.clone());
565 it::assert_equal(largest_by_key, sorted_largest);
566 }
567 }
568
569 #[derive(Clone, Debug)]
570 struct RandIter<T: 'static + Clone + Send, R: 'static + Clone + Rng + SeedableRng + Send = StdRng> {
571 idx: usize,
572 len: usize,
573 rng: R,
574 _t: PhantomData<T>,
575 }
576
577 impl<T: Clone + Send, R: Clone + Rng + SeedableRng + Send> Iterator for RandIter<T, R>
578 where
579 Standard: Distribution<T>,
580 {
581 type Item = T;
582 fn next(&mut self) -> Option<T> {
583 if self.idx == self.len {
584 None
585 } else {
586 self.idx += 1;
587 Some(self.rng.gen())
588 }
589 }
590 }
591
592 impl<T: Clone + Send, R: Clone + Rng + SeedableRng + Send> qc::Arbitrary for RandIter<T, R> {
593 fn arbitrary<G: qc::Gen>(g: &mut G) -> Self {
594 Self {
595 idx: 0,
596 len: g.size(),
597 rng: R::seed_from_u64(g.next_u64()),
598 _t: PhantomData {},
599 }
600 }
601 }
602
603 // Check that taking the k smallest is the same as
604 // sorting then taking the k first elements
605 fn k_smallest_sort<I>(i: I, k: u16)
606 where
607 I: Iterator + Clone,
608 I::Item: Ord + Debug,
609 {
610 let j = i.clone();
611 let i1 = i.clone();
612 let j1 = i.clone();
613 let k = k as usize;
614 it::assert_equal(i.k_smallest(k), j.sorted().take(k));
615 it::assert_equal(i1.k_smallest_relaxed(k), j1.sorted().take(k));
616 }
617
618 // Similar to `k_smallest_sort` but for our custom heap implementation.
619 fn k_smallest_by_sort<I>(i: I, k: u16)
620 where
621 I: Iterator + Clone,
622 I::Item: Ord + Debug,
623 {
624 let j = i.clone();
625 let i1 = i.clone();
626 let j1 = i.clone();
627 let k = k as usize;
628 it::assert_equal(i.k_smallest_by(k, Ord::cmp), j.sorted().take(k));
629 it::assert_equal(i1.k_smallest_relaxed_by(k, Ord::cmp), j1.sorted().take(k));
630 }
631
632 macro_rules! generic_test {
633 ($f:ident, $($t:ty),+) => {
634 $(paste::item! {
635 qc::quickcheck! {
636 fn [< $f _ $t >](i: RandIter<$t>, k: u16) -> () {
637 $f(i, k)
638 }
639 }
640 })+
641 };
642 }
643
644 #[cfg(not(miri))]
645 generic_test!(k_smallest_sort, u8, u16, u32, u64, i8, i16, i32, i64);
646 #[cfg(not(miri))]
647 generic_test!(k_smallest_by_sort, u8, u16, u32, u64, i8, i16, i32, i64);
648
649 #[test]
650 fn sorted_by_key() {
651 let sc = [3, 4, 1, 2].iter().cloned().sorted_by_key(|&x| x);
652 it::assert_equal(sc, vec![1, 2, 3, 4]);
653
654 let v = (0..5).sorted_by_key(|&x| -x);
655 it::assert_equal(v, vec![4, 3, 2, 1, 0]);
656 }
657
658 #[test]
659 fn sorted_by_cached_key() {
660 // Track calls to key function
661 let mut ncalls = 0;
662
663 let sorted = [3, 4, 1, 2].iter().cloned().sorted_by_cached_key(|&x| {
664 ncalls += 1;
665 x.to_string()
666 });
667 it::assert_equal(sorted, vec![1, 2, 3, 4]);
668 // Check key function called once per element
669 assert_eq!(ncalls, 4);
670
671 let mut ncalls = 0;
672
673 let sorted = (0..5).sorted_by_cached_key(|&x| {
674 ncalls += 1;
675 -x
676 });
677 it::assert_equal(sorted, vec![4, 3, 2, 1, 0]);
678 // Check key function called once per element
679 assert_eq!(ncalls, 5);
680 }
681
682 #[test]
683 fn test_multipeek() {
684 let nums = vec![1u8, 2, 3, 4, 5];
685
686 let mp = multipeek(nums.iter().copied());
687 assert_eq!(nums, mp.collect::<Vec<_>>());
688
689 let mut mp = multipeek(nums.iter().copied());
690 assert_eq!(mp.peek(), Some(&1));
691 assert_eq!(mp.next(), Some(1));
692 assert_eq!(mp.peek(), Some(&2));
693 assert_eq!(mp.peek(), Some(&3));
694 assert_eq!(mp.next(), Some(2));
695 assert_eq!(mp.peek(), Some(&3));
696 assert_eq!(mp.peek(), Some(&4));
697 assert_eq!(mp.peek(), Some(&5));
698 assert_eq!(mp.peek(), None);
699 assert_eq!(mp.next(), Some(3));
700 assert_eq!(mp.next(), Some(4));
701 assert_eq!(mp.peek(), Some(&5));
702 assert_eq!(mp.peek(), None);
703 assert_eq!(mp.next(), Some(5));
704 assert_eq!(mp.next(), None);
705 assert_eq!(mp.peek(), None);
706 }
707
708 #[test]
709 fn test_multipeek_reset() {
710 let data = [1, 2, 3, 4];
711
712 let mut mp = multipeek(cloned(&data));
713 assert_eq!(mp.peek(), Some(&1));
714 assert_eq!(mp.next(), Some(1));
715 assert_eq!(mp.peek(), Some(&2));
716 assert_eq!(mp.peek(), Some(&3));
717 mp.reset_peek();
718 assert_eq!(mp.peek(), Some(&2));
719 assert_eq!(mp.next(), Some(2));
720 }
721
722 #[test]
723 fn test_multipeek_peeking_next() {
724 use crate::it::PeekingNext;
725 let nums = [1u8, 2, 3, 4, 5, 6, 7];
726
727 let mut mp = multipeek(nums.iter().copied());
728 assert_eq!(mp.peeking_next(|&x| x != 0), Some(1));
729 assert_eq!(mp.next(), Some(2));
730 assert_eq!(mp.peek(), Some(&3));
731 assert_eq!(mp.peek(), Some(&4));
732 assert_eq!(mp.peeking_next(|&x| x == 3), Some(3));
733 assert_eq!(mp.peek(), Some(&4));
734 assert_eq!(mp.peeking_next(|&x| x != 4), None);
735 assert_eq!(mp.peeking_next(|&x| x == 4), Some(4));
736 assert_eq!(mp.peek(), Some(&5));
737 assert_eq!(mp.peek(), Some(&6));
738 assert_eq!(mp.peeking_next(|&x| x != 5), None);
739 assert_eq!(mp.peek(), Some(&7));
740 assert_eq!(mp.peeking_next(|&x| x == 5), Some(5));
741 assert_eq!(mp.peeking_next(|&x| x == 6), Some(6));
742 assert_eq!(mp.peek(), Some(&7));
743 assert_eq!(mp.peek(), None);
744 assert_eq!(mp.next(), Some(7));
745 assert_eq!(mp.peek(), None);
746 }
747
748 #[test]
749 fn test_repeat_n_peeking_next() {
750 use crate::it::PeekingNext;
751 let mut rn = repeat_n(0, 5);
752 assert_eq!(rn.peeking_next(|&x| x != 0), None);
753 assert_eq!(rn.peeking_next(|&x| x <= 0), Some(0));
754 assert_eq!(rn.next(), Some(0));
755 assert_eq!(rn.peeking_next(|&x| x <= 0), Some(0));
756 assert_eq!(rn.peeking_next(|&x| x != 0), None);
757 assert_eq!(rn.peeking_next(|&x| x >= 0), Some(0));
758 assert_eq!(rn.next(), Some(0));
759 assert_eq!(rn.peeking_next(|&x| x <= 0), None);
760 assert_eq!(rn.next(), None);
761 }
762
763 #[test]
764 fn test_peek_nth() {
765 let nums = vec![1u8, 2, 3, 4, 5];
766
767 let iter = peek_nth(nums.iter().copied());
768 assert_eq!(nums, iter.collect::<Vec<_>>());
769
770 let mut iter = peek_nth(nums.iter().copied());
771
772 assert_eq!(iter.peek_nth(0), Some(&1));
773 assert_eq!(iter.peek_nth(0), Some(&1));
774 assert_eq!(iter.next(), Some(1));
775
776 assert_eq!(iter.peek_nth(0), Some(&2));
777 assert_eq!(iter.peek_nth(1), Some(&3));
778 assert_eq!(iter.next(), Some(2));
779
780 assert_eq!(iter.peek_nth(0), Some(&3));
781 assert_eq!(iter.peek_nth(1), Some(&4));
782 assert_eq!(iter.peek_nth(2), Some(&5));
783 assert_eq!(iter.peek_nth(3), None);
784
785 assert_eq!(iter.next(), Some(3));
786 assert_eq!(iter.next(), Some(4));
787
788 assert_eq!(iter.peek_nth(0), Some(&5));
789 assert_eq!(iter.peek_nth(1), None);
790 assert_eq!(iter.next(), Some(5));
791 assert_eq!(iter.next(), None);
792
793 assert_eq!(iter.peek_nth(0), None);
794 assert_eq!(iter.peek_nth(1), None);
795 }
796
797 #[test]
798 fn test_peek_nth_peeking_next() {
799 use it::PeekingNext;
800 let nums = [1u8, 2, 3, 4, 5, 6, 7];
801 let mut iter = peek_nth(nums.iter().copied());
802
803 assert_eq!(iter.peeking_next(|&x| x != 0), Some(1));
804 assert_eq!(iter.next(), Some(2));
805
806 assert_eq!(iter.peek_nth(0), Some(&3));
807 assert_eq!(iter.peek_nth(1), Some(&4));
808 assert_eq!(iter.peeking_next(|&x| x == 3), Some(3));
809 assert_eq!(iter.peek(), Some(&4));
810
811 assert_eq!(iter.peeking_next(|&x| x != 4), None);
812 assert_eq!(iter.peeking_next(|&x| x == 4), Some(4));
813 assert_eq!(iter.peek_nth(0), Some(&5));
814 assert_eq!(iter.peek_nth(1), Some(&6));
815
816 assert_eq!(iter.peeking_next(|&x| x != 5), None);
817 assert_eq!(iter.peek(), Some(&5));
818
819 assert_eq!(iter.peeking_next(|&x| x == 5), Some(5));
820 assert_eq!(iter.peeking_next(|&x| x == 6), Some(6));
821 assert_eq!(iter.peek_nth(0), Some(&7));
822 assert_eq!(iter.peek_nth(1), None);
823 assert_eq!(iter.next(), Some(7));
824 assert_eq!(iter.peek(), None);
825 }
826
827 #[test]
828 fn test_peek_nth_next_if() {
829 let nums = [1u8, 2, 3, 4, 5, 6, 7];
830 let mut iter = peek_nth(nums.iter().copied());
831
832 assert_eq!(iter.next_if(|&x| x != 0), Some(1));
833 assert_eq!(iter.next(), Some(2));
834
835 assert_eq!(iter.peek_nth(0), Some(&3));
836 assert_eq!(iter.peek_nth(1), Some(&4));
837 assert_eq!(iter.next_if_eq(&3), Some(3));
838 assert_eq!(iter.peek(), Some(&4));
839
840 assert_eq!(iter.next_if(|&x| x != 4), None);
841 assert_eq!(iter.next_if_eq(&4), Some(4));
842 assert_eq!(iter.peek_nth(0), Some(&5));
843 assert_eq!(iter.peek_nth(1), Some(&6));
844
845 assert_eq!(iter.next_if(|&x| x != 5), None);
846 assert_eq!(iter.peek(), Some(&5));
847
848 assert_eq!(iter.next_if(|&x| x % 2 == 1), Some(5));
849 assert_eq!(iter.next_if_eq(&6), Some(6));
850 assert_eq!(iter.peek_nth(0), Some(&7));
851 assert_eq!(iter.peek_nth(1), None);
852 assert_eq!(iter.next(), Some(7));
853 assert_eq!(iter.peek(), None);
854 }
855
856 #[test]
857 fn pad_using() {
858 it::assert_equal((0..0).pad_using(1, |_| 1), 1..2);
859
860 let v: Vec<usize> = vec![0, 1, 2];
861 let r = v.into_iter().pad_using(5, |n| n);
862 it::assert_equal(r, vec![0, 1, 2, 3, 4]);
863
864 let v: Vec<usize> = vec![0, 1, 2];
865 let r = v.into_iter().pad_using(1, |_| panic!());
866 it::assert_equal(r, vec![0, 1, 2]);
867 }
868
869 #[test]
870 fn chunk_by() {
871 for (ch1, sub) in &"AABBCCC".chars().chunk_by(|&x| x) {
872 for ch2 in sub {
873 assert_eq!(ch1, ch2);
874 }
875 }
876
877 for (ch1, sub) in &"AAABBBCCCCDDDD".chars().chunk_by(|&x| x) {
878 for ch2 in sub {
879 assert_eq!(ch1, ch2);
880 if ch1 == 'C' {
881 break;
882 }
883 }
884 }
885
886 let toupper = |ch: &char| ch.to_uppercase().next().unwrap();
887
888 // try all possible orderings
889 for indices in permutohedron::Heap::new(&mut [0, 1, 2, 3]) {
890 let chunks = "AaaBbbccCcDDDD".chars().chunk_by(&toupper);
891 let mut subs = chunks.into_iter().collect_vec();
892
893 for &idx in &indices[..] {
894 let (key, text) = match idx {
895 0 => ('A', "Aaa".chars()),
896 1 => ('B', "Bbb".chars()),
897 2 => ('C', "ccCc".chars()),
898 3 => ('D', "DDDD".chars()),
899 _ => unreachable!(),
900 };
901 assert_eq!(key, subs[idx].0);
902 it::assert_equal(&mut subs[idx].1, text);
903 }
904 }
905
906 let chunks = "AAABBBCCCCDDDD".chars().chunk_by(|&x| x);
907 let mut subs = chunks.into_iter().map(|(_, g)| g).collect_vec();
908
909 let sd = subs.pop().unwrap();
910 let sc = subs.pop().unwrap();
911 let sb = subs.pop().unwrap();
912 let sa = subs.pop().unwrap();
913 for (a, b, c, d) in multizip((sa, sb, sc, sd)) {
914 assert_eq!(a, 'A');
915 assert_eq!(b, 'B');
916 assert_eq!(c, 'C');
917 assert_eq!(d, 'D');
918 }
919
920 // check that the key closure is called exactly n times
921 {
922 let mut ntimes = 0;
923 let text = "AABCCC";
924 for (_, sub) in &text.chars().chunk_by(|&x| {
925 ntimes += 1;
926 x
927 }) {
928 for _ in sub {}
929 }
930 assert_eq!(ntimes, text.len());
931 }
932
933 {
934 let mut ntimes = 0;
935 let text = "AABCCC";
936 for _ in &text.chars().chunk_by(|&x| {
937 ntimes += 1;
938 x
939 }) {}
940 assert_eq!(ntimes, text.len());
941 }
942
943 {
944 let text = "ABCCCDEEFGHIJJKK";
945 let gr = text.chars().chunk_by(|&x| x);
946 it::assert_equal(gr.into_iter().flat_map(|(_, sub)| sub), text.chars());
947 }
948 }
949
950 #[test]
951 fn chunk_by_lazy_2() {
952 let data = [0, 1];
953 let chunks = data.iter().chunk_by(|k| *k);
954 let gs = chunks.into_iter().collect_vec();
955 it::assert_equal(data.iter(), gs.into_iter().flat_map(|(_k, g)| g));
956
957 let data = [0, 1, 1, 0, 0];
958 let chunks = data.iter().chunk_by(|k| *k);
959 let mut gs = chunks.into_iter().collect_vec();
960 gs[1..].reverse();
961 it::assert_equal(&[0, 0, 0, 1, 1], gs.into_iter().flat_map(|(_, g)| g));
962
963 let grouper = data.iter().chunk_by(|k| *k);
964 let mut chunks = Vec::new();
965 for (k, chunk) in &grouper {
966 if *k == 1 {
967 chunks.push(chunk);
968 }
969 }
970 it::assert_equal(&mut chunks[0], &[1, 1]);
971
972 let data = [0, 0, 0, 1, 1, 0, 0, 2, 2, 3, 3];
973 let grouper = data.iter().chunk_by(|k| *k);
974 let mut chunks = Vec::new();
975 for (i, (_, chunk)) in grouper.into_iter().enumerate() {
976 if i < 2 {
977 chunks.push(chunk);
978 } else if i < 4 {
979 for _ in chunk {}
980 } else {
981 chunks.push(chunk);
982 }
983 }
984 it::assert_equal(&mut chunks[0], &[0, 0, 0]);
985 it::assert_equal(&mut chunks[1], &[1, 1]);
986 it::assert_equal(&mut chunks[2], &[3, 3]);
987
988 let data = [0, 0, 0, 1, 1, 0, 0, 2, 2, 3, 3];
989 let mut i = 0;
990 let grouper = data.iter().chunk_by(move |_| {
991 let k = i / 3;
992 i += 1;
993 k
994 });
995 for (i, chunk) in &grouper {
996 match i {
997 0 => it::assert_equal(chunk, &[0, 0, 0]),
998 1 => it::assert_equal(chunk, &[1, 1, 0]),
999 2 => it::assert_equal(chunk, &[0, 2, 2]),
1000 3 => it::assert_equal(chunk, &[3, 3]),
1001 _ => unreachable!(),
1002 }
1003 }
1004 }
1005
1006 #[test]
1007 fn chunk_by_lazy_3() {
1008 // test consuming each chunk on the lap after it was produced
1009 let data = [0, 0, 0, 1, 1, 0, 0, 1, 1, 2, 2];
1010 let grouper = data.iter().chunk_by(|elt| *elt);
1011 let mut last = None;
1012 for (key, chunk) in &grouper {
1013 if let Some(gr) = last.take() {
1014 for elt in gr {
1015 assert!(elt != key && i32::abs(elt - key) == 1);
1016 }
1017 }
1018 last = Some(chunk);
1019 }
1020 }
1021
1022 #[test]
1023 fn chunks() {
1024 let data = [0, 0, 0, 1, 1, 0, 0, 2, 2, 3, 3];
1025 let grouper = data.iter().chunks(3);
1026 for (i, chunk) in grouper.into_iter().enumerate() {
1027 match i {
1028 0 => it::assert_equal(chunk, &[0, 0, 0]),
1029 1 => it::assert_equal(chunk, &[1, 1, 0]),
1030 2 => it::assert_equal(chunk, &[0, 2, 2]),
1031 3 => it::assert_equal(chunk, &[3, 3]),
1032 _ => unreachable!(),
1033 }
1034 }
1035 }
1036
1037 #[test]
1038 fn concat_empty() {
1039 let data: Vec<Vec<()>> = Vec::new();
1040 assert_eq!(data.into_iter().concat(), Vec::new())
1041 }
1042
1043 #[test]
1044 fn concat_non_empty() {
1045 let data = vec![vec![1, 2, 3], vec![4, 5, 6], vec![7, 8, 9]];
1046 assert_eq!(data.into_iter().concat(), vec![1, 2, 3, 4, 5, 6, 7, 8, 9])
1047 }
1048
1049 #[test]
1050 fn combinations() {
1051 assert!((1..3).combinations(5).next().is_none());
1052
1053 let it = (1..3).combinations(2);
1054 it::assert_equal(it, vec![vec![1, 2]]);
1055
1056 let it = (1..5).combinations(2);
1057 it::assert_equal(
1058 it,
1059 vec![
1060 vec![1, 2],
1061 vec![1, 3],
1062 vec![1, 4],
1063 vec![2, 3],
1064 vec![2, 4],
1065 vec![3, 4],
1066 ],
1067 );
1068
1069 it::assert_equal((0..0).tuple_combinations::<(_, _)>(), <Vec<_>>::new());
1070 it::assert_equal((0..1).tuple_combinations::<(_, _)>(), <Vec<_>>::new());
1071 it::assert_equal((0..2).tuple_combinations::<(_, _)>(), vec![(0, 1)]);
1072
1073 it::assert_equal((0..0).combinations(2), <Vec<Vec<_>>>::new());
1074 it::assert_equal((0..1).combinations(1), vec![vec![0]]);
1075 it::assert_equal((0..2).combinations(1), vec![vec![0], vec![1]]);
1076 it::assert_equal((0..2).combinations(2), vec![vec![0, 1]]);
1077 }
1078
1079 #[test]
1080 fn combinations_of_too_short() {
1081 for i in 1..10 {
1082 assert!((0..0).combinations(i).next().is_none());
1083 assert!((0..i - 1).combinations(i).next().is_none());
1084 }
1085 }
1086
1087 #[test]
1088 fn combinations_zero() {
1089 it::assert_equal((1..3).combinations(0), vec![vec![]]);
1090 it::assert_equal((0..0).combinations(0), vec![vec![]]);
1091 }
1092
1093 fn binomial(n: usize, k: usize) -> usize {
1094 if k > n {
1095 0
1096 } else {
1097 (n - k + 1..=n).product::<usize>() / (1..=k).product::<usize>()
1098 }
1099 }
1100
1101 #[test]
1102 fn combinations_range_count() {
1103 for n in 0..=7 {
1104 for k in 0..=7 {
1105 let len = binomial(n, k);
1106 let mut it = (0..n).combinations(k);
1107 assert_eq!(len, it.clone().count());
1108 assert_eq!(len, it.size_hint().0);
1109 assert_eq!(Some(len), it.size_hint().1);
1110 for count in (0..len).rev() {
1111 let elem = it.next();
1112 assert!(elem.is_some());
1113 assert_eq!(count, it.clone().count());
1114 assert_eq!(count, it.size_hint().0);
1115 assert_eq!(Some(count), it.size_hint().1);
1116 }
1117 let should_be_none = it.next();
1118 assert!(should_be_none.is_none());
1119 }
1120 }
1121 }
1122
1123 #[test]
1124 fn combinations_inexact_size_hints() {
1125 for k in 0..=7 {
1126 let mut numbers = (0..18).filter(|i| i % 2 == 0); // 9 elements
1127 let mut it = numbers.clone().combinations(k);
1128 let real_n = numbers.clone().count();
1129 let len = binomial(real_n, k);
1130 assert_eq!(len, it.clone().count());
1131
1132 let mut nb_loaded = 0;
1133 let sh = numbers.size_hint();
1134 assert_eq!(binomial(sh.0 + nb_loaded, k), it.size_hint().0);
1135 assert_eq!(sh.1.map(|n| binomial(n + nb_loaded, k)), it.size_hint().1);
1136
1137 for next_count in 1..=len {
1138 let elem = it.next();
1139 assert!(elem.is_some());
1140 assert_eq!(len - next_count, it.clone().count());
1141 if next_count == 1 {
1142 // The very first time, the lazy buffer is prefilled.
1143 nb_loaded = numbers.by_ref().take(k).count();
1144 } else {
1145 // Then it loads one item each time until exhausted.
1146 let nb = numbers.next();
1147 if nb.is_some() {
1148 nb_loaded += 1;
1149 }
1150 }
1151 let sh = numbers.size_hint();
1152 if next_count > real_n - k + 1 {
1153 assert_eq!(0, sh.0);
1154 assert_eq!(Some(0), sh.1);
1155 assert_eq!(real_n, nb_loaded);
1156 // Once it's fully loaded, size hints of `it` are exacts.
1157 }
1158 assert_eq!(binomial(sh.0 + nb_loaded, k) - next_count, it.size_hint().0);
1159 assert_eq!(
1160 sh.1.map(|n| binomial(n + nb_loaded, k) - next_count),
1161 it.size_hint().1
1162 );
1163 }
1164 let should_be_none = it.next();
1165 assert!(should_be_none.is_none());
1166 }
1167 }
1168
1169 #[test]
1170 fn permutations_zero() {
1171 it::assert_equal((1..3).permutations(0), vec![vec![]]);
1172 it::assert_equal((0..0).permutations(0), vec![vec![]]);
1173 }
1174
1175 #[test]
1176 fn permutations_range_count() {
1177 for n in 0..=4 {
1178 for k in 0..=4 {
1179 let len = if k <= n { (n - k + 1..=n).product() } else { 0 };
1180 let mut it = (0..n).permutations(k);
1181 assert_eq!(len, it.clone().count());
1182 assert_eq!(len, it.size_hint().0);
1183 assert_eq!(Some(len), it.size_hint().1);
1184 for count in (0..len).rev() {
1185 let elem = it.next();
1186 assert!(elem.is_some());
1187 assert_eq!(count, it.clone().count());
1188 assert_eq!(count, it.size_hint().0);
1189 assert_eq!(Some(count), it.size_hint().1);
1190 }
1191 let should_be_none = it.next();
1192 assert!(should_be_none.is_none());
1193 }
1194 }
1195 }
1196
1197 #[test]
1198 fn permutations_overflowed_size_hints() {
1199 let mut it = std::iter::repeat(()).permutations(2);
1200 assert_eq!(it.size_hint().0, usize::MAX);
1201 assert_eq!(it.size_hint().1, None);
1202 for nb_generated in 1..=1000 {
1203 it.next();
1204 assert!(it.size_hint().0 >= usize::MAX - nb_generated);
1205 assert_eq!(it.size_hint().1, None);
1206 }
1207 }
1208
1209 #[test]
1210 #[cfg(not(miri))]
1211 fn combinations_with_replacement() {
1212 // Pool smaller than n
1213 it::assert_equal((0..1).combinations_with_replacement(2), vec![vec![0, 0]]);
1214 // Pool larger than n
1215 it::assert_equal(
1216 (0..3).combinations_with_replacement(2),
1217 vec![
1218 vec![0, 0],
1219 vec![0, 1],
1220 vec![0, 2],
1221 vec![1, 1],
1222 vec![1, 2],
1223 vec![2, 2],
1224 ],
1225 );
1226 // Zero size
1227 it::assert_equal((0..3).combinations_with_replacement(0), vec![vec![]]);
1228 // Zero size on empty pool
1229 it::assert_equal((0..0).combinations_with_replacement(0), vec![vec![]]);
1230 // Empty pool
1231 it::assert_equal(
1232 (0..0).combinations_with_replacement(2),
1233 <Vec<Vec<_>>>::new(),
1234 );
1235 }
1236
1237 #[test]
1238 fn combinations_with_replacement_range_count() {
1239 for n in 0..=4 {
1240 for k in 0..=4 {
1241 let len = binomial(usize::saturating_sub(n + k, 1), k);
1242 let mut it = (0..n).combinations_with_replacement(k);
1243 assert_eq!(len, it.clone().count());
1244 assert_eq!(len, it.size_hint().0);
1245 assert_eq!(Some(len), it.size_hint().1);
1246 for count in (0..len).rev() {
1247 let elem = it.next();
1248 assert!(elem.is_some());
1249 assert_eq!(count, it.clone().count());
1250 assert_eq!(count, it.size_hint().0);
1251 assert_eq!(Some(count), it.size_hint().1);
1252 }
1253 let should_be_none = it.next();
1254 assert!(should_be_none.is_none());
1255 }
1256 }
1257 }
1258
1259 #[test]
1260 fn powerset() {
1261 it::assert_equal((0..0).powerset(), vec![vec![]]);
1262 it::assert_equal((0..1).powerset(), vec![vec![], vec![0]]);
1263 it::assert_equal(
1264 (0..2).powerset(),
1265 vec![vec![], vec![0], vec![1], vec![0, 1]],
1266 );
1267 it::assert_equal(
1268 (0..3).powerset(),
1269 vec![
1270 vec![],
1271 vec![0],
1272 vec![1],
1273 vec![2],
1274 vec![0, 1],
1275 vec![0, 2],
1276 vec![1, 2],
1277 vec![0, 1, 2],
1278 ],
1279 );
1280
1281 assert_eq!((0..4).powerset().count(), 1 << 4);
1282 assert_eq!((0..8).powerset().count(), 1 << 8);
1283 assert_eq!((0..16).powerset().count(), 1 << 16);
1284
1285 for n in 0..=4 {
1286 let mut it = (0..n).powerset();
1287 let len = 2_usize.pow(n);
1288 assert_eq!(len, it.clone().count());
1289 assert_eq!(len, it.size_hint().0);
1290 assert_eq!(Some(len), it.size_hint().1);
1291 for count in (0..len).rev() {
1292 let elem = it.next();
1293 assert!(elem.is_some());
1294 assert_eq!(count, it.clone().count());
1295 assert_eq!(count, it.size_hint().0);
1296 assert_eq!(Some(count), it.size_hint().1);
1297 }
1298 let should_be_none = it.next();
1299 assert!(should_be_none.is_none());
1300 }
1301 }
1302
1303 #[test]
1304 fn diff_mismatch() {
1305 let a = [1, 2, 3, 4];
1306 let b = vec![1.0, 5.0, 3.0, 4.0];
1307 let b_map = b.into_iter().map(|f| f as i32);
1308 let diff = it::diff_with(a.iter(), b_map, |a, b| *a == b);
1309
1310 assert!(match diff {
1311 Some(it::Diff::FirstMismatch(1, _, from_diff)) =>
1312 from_diff.collect::<Vec<_>>() == vec![5, 3, 4],
1313 _ => false,
1314 });
1315 }
1316
1317 #[test]
1318 fn diff_longer() {
1319 let a = [1, 2, 3, 4];
1320 let b = vec![1.0, 2.0, 3.0, 4.0, 5.0, 6.0];
1321 let b_map = b.into_iter().map(|f| f as i32);
1322 let diff = it::diff_with(a.iter(), b_map, |a, b| *a == b);
1323
1324 assert!(match diff {
1325 Some(it::Diff::Longer(_, remaining)) => remaining.collect::<Vec<_>>() == vec![5, 6],
1326 _ => false,
1327 });
1328 }
1329
1330 #[test]
1331 fn diff_shorter() {
1332 let a = [1, 2, 3, 4];
1333 let b = vec![1.0, 2.0];
1334 let b_map = b.into_iter().map(|f| f as i32);
1335 let diff = it::diff_with(a.iter(), b_map, |a, b| *a == b);
1336
1337 assert!(match diff {
1338 Some(it::Diff::Shorter(len, _)) => len == 2,
1339 _ => false,
1340 });
1341 }
1342
1343 #[test]
1344 fn extrema_set() {
1345 use std::cmp::Ordering;
1346
1347 // A peculiar type: Equality compares both tuple items, but ordering only the
1348 // first item. Used to distinguish equal elements.
1349 #[derive(Clone, Debug, PartialEq, Eq)]
1350 struct Val(u32, u32);
1351
1352 impl PartialOrd<Self> for Val {
1353 fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
1354 Some(self.cmp(other))
1355 }
1356 }
1357
1358 impl Ord for Val {
1359 fn cmp(&self, other: &Self) -> Ordering {
1360 self.0.cmp(&other.0)
1361 }
1362 }
1363
1364 assert_eq!(None::<u32>.iter().min_set(), Vec::<&u32>::new());
1365 assert_eq!(None::<u32>.iter().max_set(), Vec::<&u32>::new());
1366
1367 assert_eq!(Some(1u32).iter().min_set(), vec![&1]);
1368 assert_eq!(Some(1u32).iter().max_set(), vec![&1]);
1369
1370 let data = [Val(0, 1), Val(2, 0), Val(0, 2), Val(1, 0), Val(2, 1)];
1371
1372 let min_set = data.iter().min_set();
1373 assert_eq!(min_set, vec![&Val(0, 1), &Val(0, 2)]);
1374
1375 let min_set_by_key = data.iter().min_set_by_key(|v| v.1);
1376 assert_eq!(min_set_by_key, vec![&Val(2, 0), &Val(1, 0)]);
1377
1378 let min_set_by = data.iter().min_set_by(|x, y| x.1.cmp(&y.1));
1379 assert_eq!(min_set_by, vec![&Val(2, 0), &Val(1, 0)]);
1380
1381 let max_set = data.iter().max_set();
1382 assert_eq!(max_set, vec![&Val(2, 0), &Val(2, 1)]);
1383
1384 let max_set_by_key = data.iter().max_set_by_key(|v| v.1);
1385 assert_eq!(max_set_by_key, vec![&Val(0, 2)]);
1386
1387 let max_set_by = data.iter().max_set_by(|x, y| x.1.cmp(&y.1));
1388 assert_eq!(max_set_by, vec![&Val(0, 2)]);
1389 }
1390
1391 #[test]
1392 fn minmax() {
1393 use crate::it::MinMaxResult;
1394 use std::cmp::Ordering;
1395
1396 // A peculiar type: Equality compares both tuple items, but ordering only the
1397 // first item. This is so we can check the stability property easily.
1398 #[derive(Clone, Debug, PartialEq, Eq)]
1399 struct Val(u32, u32);
1400
1401 impl PartialOrd<Self> for Val {
1402 fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
1403 Some(self.cmp(other))
1404 }
1405 }
1406
1407 impl Ord for Val {
1408 fn cmp(&self, other: &Self) -> Ordering {
1409 self.0.cmp(&other.0)
1410 }
1411 }
1412
1413 assert_eq!(
1414 None::<Option<u32>>.iter().minmax(),
1415 MinMaxResult::NoElements
1416 );
1417
1418 assert_eq!(Some(1u32).iter().minmax(), MinMaxResult::OneElement(&1));
1419
1420 let data = [Val(0, 1), Val(2, 0), Val(0, 2), Val(1, 0), Val(2, 1)];
1421
1422 let minmax = data.iter().minmax();
1423 assert_eq!(minmax, MinMaxResult::MinMax(&Val(0, 1), &Val(2, 1)));
1424
1425 let (min, max) = data.iter().minmax_by_key(|v| v.1).into_option().unwrap();
1426 assert_eq!(min, &Val(2, 0));
1427 assert_eq!(max, &Val(0, 2));
1428
1429 let (min, max) = data
1430 .iter()
1431 .minmax_by(|x, y| x.1.cmp(&y.1))
1432 .into_option()
1433 .unwrap();
1434 assert_eq!(min, &Val(2, 0));
1435 assert_eq!(max, &Val(0, 2));
1436 }
1437
1438 #[test]
1439 fn format() {
1440 let data = [0, 1, 2, 3];
1441 let ans1 = "0, 1, 2, 3";
1442 let ans2 = "0--1--2--3";
1443
1444 let t1 = format!("{}", data.iter().format(", "));
1445 assert_eq!(t1, ans1);
1446 let t2 = format!("{:?}", data.iter().format("--"));
1447 assert_eq!(t2, ans2);
1448
1449 let dataf = [1.1, 5.71828, -22.];
1450 let t3 = format!("{:.2e}", dataf.iter().format(", "));
1451 assert_eq!(t3, "1.10e0, 5.72e0, -2.20e1");
1452 }
1453
1454 #[test]
1455 fn while_some() {
1456 let ns = (1..10)
1457 .map(|x| if x % 5 != 0 { Some(x) } else { None })
1458 .while_some();
1459 it::assert_equal(ns, vec![1, 2, 3, 4]);
1460 }
1461
1462 #[test]
1463 fn fold_while() {
1464 let mut iterations = 0;
1465 let vec = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
1466 let sum = vec
1467 .into_iter()
1468 .fold_while(0, |acc, item| {
1469 iterations += 1;
1470 let new_sum = acc + item;
1471 if new_sum <= 20 {
1472 FoldWhile::Continue(new_sum)
1473 } else {
1474 FoldWhile::Done(acc)
1475 }
1476 })
1477 .into_inner();
1478 assert_eq!(iterations, 6);
1479 assert_eq!(sum, 15);
1480 }
1481
1482 #[test]
1483 fn tree_reduce() {
1484 let x = [
1485 "",
1486 "0",
1487 "0 1 x",
1488 "0 1 x 2 x",
1489 "0 1 x 2 3 x x",
1490 "0 1 x 2 3 x x 4 x",
1491 "0 1 x 2 3 x x 4 5 x x",
1492 "0 1 x 2 3 x x 4 5 x 6 x x",
1493 "0 1 x 2 3 x x 4 5 x 6 7 x x x",
1494 "0 1 x 2 3 x x 4 5 x 6 7 x x x 8 x",
1495 "0 1 x 2 3 x x 4 5 x 6 7 x x x 8 9 x x",
1496 "0 1 x 2 3 x x 4 5 x 6 7 x x x 8 9 x 10 x x",
1497 "0 1 x 2 3 x x 4 5 x 6 7 x x x 8 9 x 10 11 x x x",
1498 "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",
1499 "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",
1500 "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",
1501 "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",
1502 ];
1503 for (i, &s) in x.iter().enumerate() {
1504 let expected = if s.is_empty() {
1505 None
1506 } else {
1507 Some(s.to_string())
1508 };
1509 let num_strings = (0..i).map(|x| x.to_string());
1510 let actual = num_strings.tree_reduce(|a, b| format!("{} {} x", a, b));
1511 assert_eq!(actual, expected);
1512 }
1513 }
1514
1515 #[test]
1516 fn exactly_one_question_mark_syntax_works() {
1517 exactly_one_question_mark_return().unwrap_err();
1518 }
1519
1520 fn exactly_one_question_mark_return() -> Result<(), ExactlyOneError<std::slice::Iter<'static, ()>>>
1521 {
1522 [].iter().exactly_one()?;
1523 Ok(())
1524 }
1525
1526 #[test]
1527 fn multiunzip() {
1528 let (a, b, c): (Vec<_>, Vec<_>, Vec<_>) = [(0, 1, 2), (3, 4, 5), (6, 7, 8)]
1529 .iter()
1530 .cloned()
1531 .multiunzip();
1532 assert_eq!((a, b, c), (vec![0, 3, 6], vec![1, 4, 7], vec![2, 5, 8]));
1533 let (): () = [(), (), ()].iter().cloned().multiunzip();
1534 #[allow(clippy::type_complexity)]
1535 let t: (
1536 Vec<_>,
1537 Vec<_>,
1538 Vec<_>,
1539 Vec<_>,
1540 Vec<_>,
1541 Vec<_>,
1542 Vec<_>,
1543 Vec<_>,
1544 Vec<_>,
1545 Vec<_>,
1546 Vec<_>,
1547 Vec<_>,
1548 ) = [(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11)]
1549 .iter()
1550 .cloned()
1551 .multiunzip();
1552 assert_eq!(
1553 t,
1554 (
1555 vec![0],
1556 vec![1],
1557 vec![2],
1558 vec![3],
1559 vec![4],
1560 vec![5],
1561 vec![6],
1562 vec![7],
1563 vec![8],
1564 vec![9],
1565 vec![10],
1566 vec![11]
1567 )
1568 );
1569 }