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}
;
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
;
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();
26 assert
!((i
, j
, k
) == v
[(i
* 2 * 2 + j
* 2 + k
) as usize]);
30 for (_
, _
, _
, _
) in iproduct
!(0..3, 0..2, 0..2, 0..3) {
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]);
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]);
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)));
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)));
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());
72 let xs
= [0, 1, 2, 3, 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());
79 let xs
= [0, 1, 0, 1];
81 it
::assert_equal(ys
.iter(), xs
.iter().duplicates());
82 it
::assert_equal(ys
.iter(), xs
.iter().rev().duplicates().rev());
84 it
::assert_equal(ys_rev
.iter(), xs
.iter().duplicates().rev());
86 let xs
= vec
![0, 1, 2, 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());
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());
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());
115 it
::assert_equal(ys
.iter(), xs
.iter().unique());
116 it
::assert_equal(ys
.iter(), xs
.iter().rev().unique().rev());
118 it
::assert_equal(ys_rev
.iter(), xs
.iter().unique().rev());
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());
128 let ys
= [0, 1, 2, 3];
129 let mut it
= ys
[..0].iter().copied().intersperse(1);
130 assert
!(it
.next() == None
);
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];
140 it
::assert_equal(ys
.iter(), xs
.iter().dedup());
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
);
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.) {
159 itertools
::assert_equal(it
.clone(), vec
![-6., 4., -1.]);
161 it
.fold(vec
![], |mut v
, n
| {
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)];
176 it
::assert_equal(ys
.iter(), xs
.iter().dedup_by(|x
, y
| x
.0==y
.0));
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
);
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)];
190 it
::assert_equal(ys
.iter().cloned(), xs
.iter().dedup_with_count());
192 let xs
: [i32; 5] = [0, 0, 0, 0, 0];
193 let ys
: [(usize, &i32); 1] = [(5, &0)];
195 it
::assert_equal(ys
.iter().cloned(), xs
.iter().dedup_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))];
204 it
::assert_equal(ys
.iter().cloned(), xs
.iter().dedup_by_with_count(|x
, y
| x
.1==y
.1));
206 let xs
= [(0, 1), (0, 2), (0, 3), (0, 4), (0, 5)];
207 let ys
= [( 5, &(0, 1))];
209 it
::assert_equal(ys
.iter().cloned(), xs
.iter().dedup_by_with_count(|x
, y
| x
.0==y
.0));
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());
225 assert
!("ABCDEFGH".chars().all_unique());
226 assert
!(!"ABCDEFGA".chars().all_unique());
227 assert
!(::std
::iter
::empty
::<usize>().all_unique());
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());
238 it
::assert_equal(pb
, xs
.iter().cloned());
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
);
259 let (t1
, t2
) = xs
.iter().cloned().tee();
260 it
::assert_equal(t1
, xs
.iter().cloned());
261 it
::assert_equal(t2
, xs
.iter().cloned());
263 let (t1
, t2
) = xs
.iter().cloned().tee();
264 it
::assert_equal(t1
.zip(t2
), xs
.iter().cloned().zip(xs
.iter().cloned()));
270 let xs
= [0, 1, 1, 1, 2, 1, 3, 5, 6];
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
);
283 let r1
= rciter(0..5);
284 let mut z
= izip
!(&r1
, r1
);
285 assert_eq
!(z
.next(), Some((0, 1)));
290 fn trait_pointers() {
291 struct ByRef
<'r
, I
: ?Sized
>(&'r
mut I
) ;
293 impl<'r
, X
, I
: ?Sized
> Iterator
for ByRef
<'r
, I
> where
294 I
: 'r
+ Iterator
<Item
=X
>
297 fn next(&mut self) -> Option
<Self::Item
>
303 let mut it
= Box
::new(0..10) as Box
<dyn Iterator
<Item
=i32>>;
304 assert_eq
!(it
.next(), Some(0));
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));
312 let mut r
= ByRef(jt
);
313 assert_eq
!(r
.next(), Some(2));
316 assert_eq
!(jt
.find_position(|x
| *x
== 4), Some((1, 4)));
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());
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());
347 let its
= (0..4).map(|s
| (s
..10).step(4));
349 it
::assert_equal(its
.kmerge(), 0..10);
355 let its
= vec
![3, 2, 1, 0].into_iter().map(|s
| (s
..10).step(4));
357 it
::assert_equal(its
.kmerge(), 0..10);
362 let its
= (0..4).map(|_
| 0..0);
363 assert_eq
!(its
.kmerge().next(), None
);
367 fn kmerge_size_hint() {
368 let its
= (0..5).map(|_
| (0..10));
369 assert_eq
!(its
.kmerge().size_hint(), (50, Some(50)));
373 fn kmerge_empty_size_hint() {
374 let its
= (0..5).map(|_
| (0..0));
375 assert_eq
!(its
.kmerge().size_hint(), (0, Some(0)));
380 let many
= [1, 2, 3];
382 let none
: Vec
<i32> = vec
![];
384 assert_eq
!(many
.iter().join(", "), "1, 2, 3");
385 assert_eq
!( one
.iter().join(", "), "1");
386 assert_eq
!(none
.iter().join(", "), "");
390 fn sorted_unstable_by() {
391 let sc
= [3, 4, 1, 2].iter().cloned().sorted_by(|&a
, &b
| {
394 it
::assert_equal(sc
, vec
![1, 2, 3, 4]);
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]);
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]);
405 let v
= (0..5).sorted_unstable_by_key(|&x
| -x
);
406 it
::assert_equal(v
, vec
![4, 3, 2, 1, 0]);
411 let sc
= [3, 4, 1, 2].iter().cloned().sorted_by(|&a
, &b
| {
414 it
::assert_equal(sc
, vec
![1, 2, 3, 4]);
416 let v
= (0..5).sorted_by(|&a
, &b
| a
.cmp(&b
).reverse());
417 it
::assert_equal(v
, vec
![4, 3, 2, 1, 0]);
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);
426 // Generate a random permutation of n..n+m
428 let mut v
: Vec
<u64> = (n
..n
.saturating_add(m
)).collect();
429 v
.shuffle(&mut thread_rng());
433 // Check that taking the k smallest elements yields n..n+min(k, m)
435 i
.k_smallest(k
as usize),
436 n
..n
.saturating_add(min(k
, m
))
441 #[derive(Clone, Debug)]
442 struct RandIter
<T
: '
static + Clone
+ Send
, R
: '
static + Clone
+ Rng
+ SeedableRng
+ Send
= StdRng
> {
449 impl<T
: Clone
+ Send
, R
: Clone
+ Rng
+ SeedableRng
+ Send
> Iterator
for RandIter
<T
, R
>
450 where Standard
: Distribution
<T
> {
452 fn next(&mut self) -> Option
<T
> {
453 if self.idx
== self.len
{
462 impl<T
: Clone
+ Send
, R
: Clone
+ Rng
+ SeedableRng
+ Send
> qc
::Arbitrary
for RandIter
<T
, R
> {
463 fn arbitrary
<G
: qc
::Gen
>(g
: &mut G
) -> Self {
467 rng
: R
::seed_from_u64(g
.next_u64()),
473 // Check that taking the k smallest is the same as
474 // sorting then taking the k first elements
475 fn k_smallest_sort
<I
>(i
: I
, k
: u16)
478 I
::Item
: Ord
+ Debug
,
488 macro_rules
! generic_test
{
489 ($f
:ident
, $
($t
:ty
),+) => {
492 fn [< $f _ $t
>](i
: RandIter
<$t
>, k
: u16) -> () {
500 generic_test
!(k_smallest_sort
, u8, u16, u32, u64, i8, i16, i32, i64);
504 let sc
= [3, 4, 1, 2].iter().cloned().sorted_by_key(|&x
| x
);
505 it
::assert_equal(sc
, vec
![1, 2, 3, 4]);
507 let v
= (0..5).sorted_by_key(|&x
| -x
);
508 it
::assert_equal(v
, vec
![4, 3, 2, 1, 0]);
512 fn sorted_by_cached_key() {
513 // Track calls to key function
516 let sorted
= [3, 4, 1, 2].iter().cloned().sorted_by_cached_key(|&x
| {
520 it
::assert_equal(sorted
, vec
![1, 2, 3, 4]);
521 // Check key function called once per element
522 assert_eq
!(ncalls
, 4);
526 let sorted
= (0..5).sorted_by_cached_key(|&x
| {
530 it
::assert_equal(sorted
, vec
![4, 3, 2, 1, 0]);
531 // Check key function called once per element
532 assert_eq
!(ncalls
, 5);
536 fn test_multipeek() {
537 let nums
= vec
![1u8,2,3,4,5];
539 let mp
= multipeek(nums
.iter().copied());
540 assert_eq
!(nums
, mp
.collect
::<Vec
<_
>>());
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
);
562 fn test_multipeek_reset() {
563 let data
= [1, 2, 3, 4];
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));
571 assert_eq
!(mp
.peek(), Some(&2));
572 assert_eq
!(mp
.next(), Some(2));
576 fn test_multipeek_peeking_next() {
577 use crate::it
::PeekingNext
;
578 let nums
= vec
![1u8,2,3,4,5,6,7];
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
);
603 let nums
= vec
![1u8,2,3,4,5];
605 let iter
= peek_nth(nums
.iter().copied());
606 assert_eq
!(nums
, iter
.collect
::<Vec
<_
>>());
608 let mut iter
= peek_nth(nums
.iter().copied());
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));
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));
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
);
623 assert_eq
!(iter
.next(), Some(3));
624 assert_eq
!(iter
.next(), Some(4));
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
);
631 assert_eq
!(iter
.peek_nth(0), None
);
632 assert_eq
!(iter
.peek_nth(1), None
);
636 fn test_peek_nth_peeking_next() {
638 let nums
= vec
![1u8,2,3,4,5,6,7];
639 let mut iter
= peek_nth(nums
.iter().copied());
641 assert_eq
!(iter
.peeking_next(|&x
| x
!= 0), Some(1));
642 assert_eq
!(iter
.next(), Some(2));
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));
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));
654 assert_eq
!(iter
.peeking_next(|&x
| x
!= 5), None
);
655 assert_eq
!(iter
.peek(), Some(&5));
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
);
667 it
::assert_equal((0..0).pad_using(1, |_
| 1), 1..2);
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]);
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]);
680 for (ch1
, sub
) in &"AABBCCC".chars().group_by(|&x
| x
) {
682 assert_eq
!(ch1
, ch2
);
686 for (ch1
, sub
) in &"AAABBBCCCCDDDD".chars().group_by(|&x
| x
) {
688 assert_eq
!(ch1
, ch2
);
695 let toupper
= |ch
: &char| ch
.to_uppercase().next().unwrap();
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();
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()),
710 assert_eq
!(key
, subs
[idx
].0);
711 it
::assert_equal(&mut subs
[idx
].1, text
);
715 let groups
= "AAABBBCCCCDDDD".chars().group_by(|&x
| x
);
716 let mut subs
= groups
.into_iter().map(|(_
, g
)| g
).collect_vec();
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
)) {
729 // check that the key closure is called exactly n times
733 for (_
, sub
) in &text
.chars().group_by(|&x
| { ntimes += 1; x}
) {
737 assert_eq
!(ntimes
, text
.len());
743 for _
in &text
.chars().group_by(|&x
| { ntimes += 1; x}
) {
745 assert_eq
!(ntimes
, text
.len());
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());
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
));
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();
766 it
::assert_equal(&[0, 0, 0, 1, 1], gs
.into_iter().flat_map(|(_
, g
)| g
));
768 let grouper
= data
.iter().group_by(|k
| *k
);
769 let mut groups
= Vec
::new();
770 for (k
, group
) in &grouper
{
775 it
::assert_equal(&mut groups
[0], &[1, 1]);
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() {
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]);
794 // use groups as chunks
795 let data
= vec
![0, 0, 0, 1, 1, 0, 0, 2, 2, 3, 3];
797 let grouper
= data
.iter().group_by(move |_
| { let k = i / 3; i += 1; k }
);
798 for (i
, group
) in &grouper
{
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]),
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
);
815 for (key
, group
) in &grouper
{
816 if let Some(gr
) = last
.take() {
818 assert
!(elt
!= key
&& i32::abs(elt
- key
) == 1);
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() {
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]),
842 let data
: Vec
<Vec
<()>> = Vec
::new();
843 assert_eq
!(data
.into_iter().concat(), Vec
::new())
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])
854 assert
!((1..3).combinations(5).next().is_none());
856 let it
= (1..3).combinations(2);
857 it
::assert_equal(it
, vec
![
861 let it
= (1..5).combinations(2);
862 it
::assert_equal(it
, vec
![
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)]);
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]]);
882 fn combinations_of_too_short() {
884 assert
!((0..0).combinations(i
).next().is_none());
885 assert
!((0..i
- 1).combinations(i
).next().is_none());
891 fn combinations_zero() {
892 it
::assert_equal((1..3).combinations(0), vec
![vec
![]]);
893 it
::assert_equal((0..0).combinations(0), vec
![vec
![]]);
897 fn permutations_zero() {
898 it
::assert_equal((1..3).permutations(0), vec
![vec
![]]);
899 it
::assert_equal((0..0).permutations(0), vec
![vec
![]]);
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
908 (0..3).combinations_with_replacement(2),
920 (0..3).combinations_with_replacement(0),
923 // Zero size on empty pool
925 (0..0).combinations_with_replacement(0),
930 (0..0).combinations_with_replacement(2),
931 <Vec
<Vec
<_
>>>::new(),
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
![
942 vec
![0], vec
![1], vec
![2],
943 vec
![0, 1], vec
![0, 2], vec
![1, 2],
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);
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
);
960 Some(it
::Diff
::FirstMismatch(1, _
, from_diff
)) =>
961 from_diff
.collect
::<Vec
<_
>>() == vec
![5, 3, 4],
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
);
974 Some(it
::Diff
::Longer(_
, remaining
)) =>
975 remaining
.collect
::<Vec
<_
>>() == vec
![5, 6],
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
);
988 Some(it
::Diff
::Shorter(len
, _
)) => len
== 2,
995 use std
::cmp
::Ordering
;
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);
1002 impl PartialOrd
<Val
> for Val
{
1003 fn partial_cmp(&self, other
: &Val
) -> Option
<Ordering
> {
1004 self.0.partial_cmp(&other
.0)
1009 fn cmp(&self, other
: &Val
) -> Ordering
{
1010 self.0.cmp(&other
.0)
1014 assert_eq
!(None
::<u32>.iter().min_set(), Vec
::<&u32>::new());
1015 assert_eq
!(None
::<u32>.iter().max_set(), Vec
::<&u32>::new());
1017 assert_eq
!(Some(1u32).iter().min_set(), vec
![&1]);
1018 assert_eq
!(Some(1u32).iter().max_set(), vec
![&1]);
1020 let data
= vec
![Val(0, 1), Val(2, 0), Val(0, 2), Val(1, 0), Val(2, 1)];
1022 let min_set
= data
.iter().min_set();
1023 assert_eq
!(min_set
, vec
![&Val(0, 1), &Val(0, 2)]);
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)]);
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)]);
1031 let max_set
= data
.iter().max_set();
1032 assert_eq
!(max_set
, vec
![&Val(2, 0), &Val(2, 1)]);
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)]);
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)]);
1043 use std
::cmp
::Ordering
;
1044 use crate::it
::MinMaxResult
;
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);
1051 impl PartialOrd
<Val
> for Val
{
1052 fn partial_cmp(&self, other
: &Val
) -> Option
<Ordering
> {
1053 self.0.partial_cmp(&other
.0)
1058 fn cmp(&self, other
: &Val
) -> Ordering
{
1059 self.0.cmp(&other
.0)
1063 assert_eq
!(None
::<Option
<u32>>.iter().minmax(), MinMaxResult
::NoElements
);
1065 assert_eq
!(Some(1u32).iter().minmax(), MinMaxResult
::OneElement(&1));
1067 let data
= vec
![Val(0, 1), Val(2, 0), Val(0, 2), Val(1, 0), Val(2, 1)];
1069 let minmax
= data
.iter().minmax();
1070 assert_eq
!(minmax
, MinMaxResult
::MinMax(&Val(0, 1), &Val(2, 1)));
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));
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));
1083 let data
= [0, 1, 2, 3];
1084 let ans1
= "0, 1, 2, 3";
1085 let ans2
= "0--1--2--3";
1087 let t1
= format
!("{}", data
.iter().format(", "));
1088 assert_eq
!(t1
, ans1
);
1089 let t2
= format
!("{:?}", data
.iter().format("--"));
1090 assert_eq
!(t2
, ans2
);
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");
1099 let ns
= (1..10).map(|x
| if x
% 5 != 0 { Some(x) }
else { None }
)
1101 it
::assert_equal(ns
, vec
![1, 2, 3, 4]);
1104 #[allow(deprecated)]
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
| {
1111 let new_sum
= acc
+ item
;
1113 FoldWhile
::Continue(new_sum
)
1115 FoldWhile
::Done(acc
)
1118 assert_eq
!(iterations
, 6);
1119 assert_eq
!(sum
, 15);
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",
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
);
1152 fn exactly_one_question_mark_syntax_works() {
1153 exactly_one_question_mark_return().unwrap_err();
1156 fn exactly_one_question_mark_return() -> Result
<(), ExactlyOneError
<std
::slice
::Iter
<'
static, ()>>> {
1157 [].iter().exactly_one()?
;
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]));