Upgrade rust/crates/itertools to 0.10.0 am: 6f798715de am: b1d1cd1ee8 am: e7475af424 am: 16514b8f27android-mainline-12.0.0_r99android-mainline-12.0.0_r98android-mainline-12.0.0_r97android-mainline-12.0.0_r96android-mainline-12.0.0_r95android-mainline-12.0.0_r94android-mainline-12.0.0_r93android-mainline-12.0.0_r92android-mainline-12.0.0_r91android-mainline-12.0.0_r90android-mainline-12.0.0_r9android-mainline-12.0.0_r89android-mainline-12.0.0_r88android-mainline-12.0.0_r87android-mainline-12.0.0_r86android-mainline-12.0.0_r85android-mainline-12.0.0_r84android-mainline-12.0.0_r83android-mainline-12.0.0_r82android-mainline-12.0.0_r81android-mainline-12.0.0_r80android-mainline-12.0.0_r8android-mainline-12.0.0_r79android-mainline-12.0.0_r78android-mainline-12.0.0_r77android-mainline-12.0.0_r76android-mainline-12.0.0_r75android-mainline-12.0.0_r74android-mainline-12.0.0_r73android-mainline-12.0.0_r72android-mainline-12.0.0_r71android-mainline-12.0.0_r70android-mainline-12.0.0_r7android-mainline-12.0.0_r69android-mainline-12.0.0_r68android-mainline-12.0.0_r67android-mainline-12.0.0_r66android-mainline-12.0.0_r65android-mainline-12.0.0_r64android-mainline-12.0.0_r63android-mainline-12.0.0_r62android-mainline-12.0.0_r61android-mainline-12.0.0_r60android-mainline-12.0.0_r6android-mainline-12.0.0_r59android-mainline-12.0.0_r58android-mainline-12.0.0_r57android-mainline-12.0.0_r56android-mainline-12.0.0_r53android-mainline-12.0.0_r52android-mainline-12.0.0_r51android-mainline-12.0.0_r50android-mainline-12.0.0_r5android-mainline-12.0.0_r49android-mainline-12.0.0_r48android-mainline-12.0.0_r47android-mainline-12.0.0_r46android-mainline-12.0.0_r45android-mainline-12.0.0_r44android-mainline-12.0.0_r43android-mainline-12.0.0_r42android-mainline-12.0.0_r41android-mainline-12.0.0_r40android-mainline-12.0.0_r39android-mainline-12.0.0_r38android-mainline-12.0.0_r37android-mainline-12.0.0_r35android-mainline-12.0.0_r34android-mainline-12.0.0_r33android-mainline-12.0.0_r32android-mainline-12.0.0_r31android-mainline-12.0.0_r30android-mainline-12.0.0_r3android-mainline-12.0.0_r29android-mainline-12.0.0_r28android-mainline-12.0.0_r27android-mainline-12.0.0_r26android-mainline-12.0.0_r25android-mainline-12.0.0_r24android-mainline-12.0.0_r23android-mainline-12.0.0_r22android-mainline-12.0.0_r21android-mainline-12.0.0_r20android-mainline-12.0.0_r2android-mainline-12.0.0_r19android-mainline-12.0.0_r18android-mainline-12.0.0_r17android-mainline-12.0.0_r16android-mainline-12.0.0_r15android-mainline-12.0.0_r14android-mainline-12.0.0_r13android-mainline-12.0.0_r126android-mainline-12.0.0_r125android-mainline-12.0.0_r124android-mainline-12.0.0_r123android-mainline-12.0.0_r122android-mainline-12.0.0_r121android-mainline-12.0.0_r120android-mainline-12.0.0_r12android-mainline-12.0.0_r119android-mainline-12.0.0_r118android-mainline-12.0.0_r117android-mainline-12.0.0_r116android-mainline-12.0.0_r115android-mainline-12.0.0_r114android-mainline-12.0.0_r113android-mainline-12.0.0_r110android-mainline-12.0.0_r11android-mainline-12.0.0_r109android-mainline-12.0.0_r108android-mainline-12.0.0_r107android-mainline-12.0.0_r106android-mainline-12.0.0_r105android-mainline-12.0.0_r104android-mainline-12.0.0_r103android-mainline-12.0.0_r102android-mainline-12.0.0_r101android-mainline-12.0.0_r100android-mainline-12.0.0_r10android-mainline-12.0.0_r1aml_wif_311811030aml_tz3_311312010aml_tet_311811050aml_sdk_311710000aml_pco_311011000aml_mpr_311911090aml_doc_310851020android12-mainline-wifi-releaseandroid12-mainline-tethering-releaseandroid12-mainline-statsd-releaseandroid12-mainline-sdkext-releaseandroid12-mainline-resolv-releaseandroid12-mainline-permission-releaseandroid12-mainline-neuralnetworks-releaseandroid12-mainline-networkstack-releaseandroid12-mainline-mediaprovider-releaseandroid12-mainline-media-swcodec-releaseandroid12-mainline-media-releaseandroid12-mainline-ipsec-releaseandroid12-mainline-extservices-releaseandroid12-mainline-documentsui-releaseandroid12-mainline-conscrypt-releaseandroid12-mainline-cellbroadcast-releaseandroid12-mainline-captiveportallogin-releaseandroid12-mainline-art-releaseandroid12-mainline-adbd-release

Original change: https://android-review.googlesource.com/c/platform/external/rust/crates/itertools/+/1662678

Change-Id: I56b01b4f2ed1b374372c6c57e71f89e0581df6b7

1 files changed, 258 insertions, 2 deletions

diff --git a/tests/test_std.rs b/tests/test_std.rs
index ba07784..d1ff815 100644
--- a/tests/test_std.rs
+++ b/tests/test_std.rs
@@ -1,8 +1,15 @@
+use paste;
 use permutohedron;
+use quickcheck as qc;
+use rand::{distributions::{Distribution, Standard}, Rng, SeedableRng, rngs::StdRng};
+use rand::{seq::SliceRandom, thread_rng};
+use std::{cmp::min, fmt::Debug, marker::PhantomData};
 use itertools as it;
 use crate::it::Itertools;
+use crate::it::ExactlyOneError;
 use crate::it::multizip;
 use crate::it::multipeek;
+use crate::it::peek_nth;
 use crate::it::free::rciter;
 use crate::it::free::put_back_n;
 use crate::it::FoldWhile;
@@ -58,6 +65,9 @@ fn unique_by() {
     let xs = ["aaa", "bbbbb", "aa", "ccc", "bbbb", "aaaaa", "cccc"];
     let ys = ["aaa", "bbbbb", "ccc"];
     it::assert_equal(ys.iter(), xs.iter().unique_by(|x| x[..2].to_string()));
+    it::assert_equal(ys.iter(), xs.iter().rev().unique_by(|x| x[..2].to_string()).rev());
+    let ys_rev = ["cccc", "aaaaa", "bbbb"];
+    it::assert_equal(ys_rev.iter(), xs.iter().unique_by(|x| x[..2].to_string()).rev());
 }
 
 #[test]
@@ -65,9 +75,16 @@ fn unique() {
     let xs = [0, 1, 2, 3, 2, 1, 3];
     let ys = [0, 1, 2, 3];
     it::assert_equal(ys.iter(), xs.iter().unique());
+    it::assert_equal(ys.iter(), xs.iter().rev().unique().rev());
+    let ys_rev = [3, 1, 2, 0];
+    it::assert_equal(ys_rev.iter(), xs.iter().unique().rev());
+
     let xs = [0, 1];
     let ys = [0, 1];
     it::assert_equal(ys.iter(), xs.iter().unique());
+    it::assert_equal(ys.iter(), xs.iter().rev().unique().rev());
+    let ys_rev = [1, 0];
+    it::assert_equal(ys_rev.iter(), xs.iter().unique().rev());
 }
 
 #[test]
@@ -99,6 +116,26 @@ fn dedup() {
 }
 
 #[test]
+fn coalesce() {
+    let data = vec![-1., -2., -3., 3., 1., 0., -1.];
+    let it = data.iter().cloned().coalesce(|x, y|
+        if (x >= 0.) == (y >= 0.) {
+            Ok(x + y)
+        } else {
+            Err((x, y))
+        }
+    );
+    itertools::assert_equal(it.clone(), vec![-6., 4., -1.]);
+    assert_eq!(
+        it.fold(vec![], |mut v, n| {
+            v.push(n);
+            v
+        }),
+        vec![-6., 4., -1.]
+    );
+}
+
+#[test]
 fn dedup_by() {
     let xs = [(0, 0), (0, 1), (1, 1), (2, 1), (0, 2), (3, 1), (0, 3), (1, 3)];
     let ys = [(0, 0), (0, 1), (0, 2), (3, 1), (0, 3)];
@@ -115,6 +152,33 @@ fn dedup_by() {
 }
 
 #[test]
+fn dedup_with_count() {
+    let xs: [i32; 8] = [0, 1, 1, 1, 2, 1, 3, 3];
+    let ys: [(usize, &i32); 5] = [(1, &0), (3, &1), (1, &2), (1, &1), (2, &3)];
+
+    it::assert_equal(ys.iter().cloned(), xs.iter().dedup_with_count());
+
+    let xs: [i32; 5] = [0, 0, 0, 0, 0];
+    let ys: [(usize, &i32); 1] = [(5, &0)];
+
+    it::assert_equal(ys.iter().cloned(), xs.iter().dedup_with_count());
+}
+
+
+#[test]
+fn dedup_by_with_count() {
+    let xs = [(0, 0), (0, 1), (1, 1), (2, 1), (0, 2), (3, 1), (0, 3), (1, 3)];
+    let ys = [(1, &(0, 0)), (3, &(0, 1)), (1, &(0, 2)), (1, &(3, 1)), (2, &(0, 3))];
+
+    it::assert_equal(ys.iter().cloned(), xs.iter().dedup_by_with_count(|x, y| x.1==y.1));
+
+    let xs = [(0, 1), (0, 2), (0, 3), (0, 4), (0, 5)];
+    let ys = [( 5, &(0, 1))];
+
+    it::assert_equal(ys.iter().cloned(), xs.iter().dedup_by_with_count(|x, y| x.0==y.0));
+}
+
+#[test]
 fn all_equal() {
     assert!("".chars().all_equal());
     assert!("A".chars().all_equal());
@@ -192,7 +256,7 @@ fn trait_pointers() {
         I: 'r + Iterator<Item=X>
     {
         type Item = X;
-        fn next(&mut self) -> Option<X>
+        fn next(&mut self) -> Option<Self::Item>
         {
             self.0.next()
         }
@@ -285,6 +349,26 @@ fn join() {
 }
 
 #[test]
+fn sorted_unstable_by() {
+    let sc = [3, 4, 1, 2].iter().cloned().sorted_by(|&a, &b| {
+        a.cmp(&b)
+    });
+    it::assert_equal(sc, vec![1, 2, 3, 4]);
+
+    let v = (0..5).sorted_unstable_by(|&a, &b| a.cmp(&b).reverse());
+    it::assert_equal(v, vec![4, 3, 2, 1, 0]);
+}
+
+#[test]
+fn sorted_unstable_by_key() {
+    let sc = [3, 4, 1, 2].iter().cloned().sorted_unstable_by_key(|&x| x);
+    it::assert_equal(sc, vec![1, 2, 3, 4]);
+
+    let v = (0..5).sorted_unstable_by_key(|&x| -x);
+    it::assert_equal(v, vec![4, 3, 2, 1, 0]);
+}
+
+#[test]
 fn sorted_by() {
     let sc = [3, 4, 1, 2].iter().cloned().sorted_by(|&a, &b| {
         a.cmp(&b)
@@ -295,6 +379,88 @@ fn sorted_by() {
     it::assert_equal(v, vec![4, 3, 2, 1, 0]);
 }
 
+qc::quickcheck! {
+    fn k_smallest_range(n: u64, m: u16, k: u16) -> () {
+        // u16 is used to constrain k and m to 0..2¹⁶,
+        //  otherwise the test could use too much memory.
+        let (k, m) = (k as u64, m as u64);
+
+        // Generate a random permutation of n..n+m
+        let i = {
+            let mut v: Vec<u64> = (n..n.saturating_add(m)).collect();
+            v.shuffle(&mut thread_rng());
+            v.into_iter()
+        };
+
+        // Check that taking the k smallest elements yields n..n+min(k, m)
+        it::assert_equal(
+            i.k_smallest(k as usize),
+            n..n.saturating_add(min(k, m))
+        );
+    }
+}
+
+#[derive(Clone, Debug)]
+struct RandIter<T: 'static + Clone + Send, R: 'static + Clone + Rng + SeedableRng + Send = StdRng> {
+    idx: usize,
+    len: usize,
+    rng: R,
+    _t: PhantomData<T>
+}
+
+impl<T: Clone + Send, R: Clone + Rng + SeedableRng + Send> Iterator for RandIter<T, R>
+where Standard: Distribution<T> {
+    type Item = T;
+    fn next(&mut self) -> Option<T> {
+        if self.idx == self.len {
+            None
+        } else {
+            self.idx += 1;
+            Some(self.rng.gen())
+        }
+    }
+}
+
+impl<T: Clone + Send, R: Clone + Rng + SeedableRng + Send> qc::Arbitrary for RandIter<T, R> {
+    fn arbitrary<G: qc::Gen>(g: &mut G) -> Self {
+        RandIter {
+            idx: 0,
+            len: g.size(),
+            rng: R::seed_from_u64(g.next_u64()),
+            _t : PhantomData{},
+        }
+    }
+}
+
+// Check that taking the k smallest is the same as
+//  sorting then taking the k first elements
+fn k_smallest_sort<I>(i: I, k: u16) -> ()
+where
+    I: Iterator + Clone,
+    I::Item: Ord + Debug,
+{
+    let j = i.clone();
+    let k = k as usize;
+    it::assert_equal(
+        i.k_smallest(k),
+        j.sorted().take(k)
+    )
+}
+
+macro_rules! generic_test {
+    ($f:ident, $($t:ty),+) => {
+        $(paste::item! {
+            qc::quickcheck! {
+                fn [< $f _ $t >](i: RandIter<$t>, k: u16) -> () {
+                    $f(i, k)
+                }
+            }
+        })+
+    };
+}
+
+generic_test!(k_smallest_sort, u8, u16, u32, u64, i8, i16, i32, i64);
+
 #[test]
 fn sorted_by_key() {
     let sc = [3, 4, 1, 2].iter().cloned().sorted_by_key(|&x| x);
@@ -328,7 +494,6 @@ fn test_multipeek() {
     assert_eq!(mp.next(), Some(5));
     assert_eq!(mp.next(), None);
     assert_eq!(mp.peek(), None);
-
 }
 
 #[test]
@@ -372,6 +537,70 @@ fn test_multipeek_peeking_next() {
 }
 
 #[test]
+fn test_peek_nth() {
+    let nums = vec![1u8,2,3,4,5];
+
+    let iter = peek_nth(nums.iter().map(|&x| x));
+    assert_eq!(nums, iter.collect::<Vec<_>>());
+
+    let mut iter = peek_nth(nums.iter().map(|&x| x));
+
+    assert_eq!(iter.peek_nth(0), Some(&1));
+    assert_eq!(iter.peek_nth(0), Some(&1));
+    assert_eq!(iter.next(), Some(1));
+
+    assert_eq!(iter.peek_nth(0), Some(&2));
+    assert_eq!(iter.peek_nth(1), Some(&3));
+    assert_eq!(iter.next(), Some(2));
+
+    assert_eq!(iter.peek_nth(0), Some(&3));
+    assert_eq!(iter.peek_nth(1), Some(&4));
+    assert_eq!(iter.peek_nth(2), Some(&5));
+    assert_eq!(iter.peek_nth(3), None);
+
+    assert_eq!(iter.next(), Some(3));
+    assert_eq!(iter.next(), Some(4));
+
+    assert_eq!(iter.peek_nth(0), Some(&5));
+    assert_eq!(iter.peek_nth(1), None);
+    assert_eq!(iter.next(), Some(5));
+    assert_eq!(iter.next(), None);
+
+    assert_eq!(iter.peek_nth(0), None);
+    assert_eq!(iter.peek_nth(1), None);
+}
+
+#[test]
+fn test_peek_nth_peeking_next() {
+    use it::PeekingNext;
+    let nums = vec![1u8,2,3,4,5,6,7];
+    let mut iter = peek_nth(nums.iter().map(|&x| x));
+
+    assert_eq!(iter.peeking_next(|&x| x != 0), Some(1));
+    assert_eq!(iter.next(), Some(2));
+
+    assert_eq!(iter.peek_nth(0), Some(&3));
+    assert_eq!(iter.peek_nth(1), Some(&4));
+    assert_eq!(iter.peeking_next(|&x| x == 3), Some(3));
+    assert_eq!(iter.peek(), Some(&4));
+
+    assert_eq!(iter.peeking_next(|&x| x != 4), None);
+    assert_eq!(iter.peeking_next(|&x| x == 4), Some(4));
+    assert_eq!(iter.peek_nth(0), Some(&5));
+    assert_eq!(iter.peek_nth(1), Some(&6));
+
+    assert_eq!(iter.peeking_next(|&x| x != 5), None);
+    assert_eq!(iter.peek(), Some(&5));
+
+    assert_eq!(iter.peeking_next(|&x| x == 5), Some(5));
+    assert_eq!(iter.peeking_next(|&x| x == 6), Some(6));
+    assert_eq!(iter.peek_nth(0), Some(&7));
+    assert_eq!(iter.peek_nth(1), None);
+    assert_eq!(iter.next(), Some(7));
+    assert_eq!(iter.peek(), None);
+}
+
+#[test]
 fn pad_using() {
     it::assert_equal((0..0).pad_using(1, |_| 1), 1..2);
 
@@ -642,6 +871,23 @@ fn combinations_with_replacement() {
 }
 
 #[test]
+fn powerset() {
+    it::assert_equal((0..0).powerset(), vec![vec![]]);
+    it::assert_equal((0..1).powerset(), vec![vec![], vec![0]]);
+    it::assert_equal((0..2).powerset(), vec![vec![], vec![0], vec![1], vec![0, 1]]);
+    it::assert_equal((0..3).powerset(), vec![
+        vec![],
+        vec![0], vec![1], vec![2],
+        vec![0, 1], vec![0, 2], vec![1, 2],
+        vec![0, 1, 2]
+    ]);
+
+    assert_eq!((0..4).powerset().count(), 1 << 4);
+    assert_eq!((0..8).powerset().count(), 1 << 8);
+    assert_eq!((0..16).powerset().count(), 1 << 16);
+}
+
+#[test]
 fn diff_mismatch() {
     let a = vec![1, 2, 3, 4];
     let b = vec![1.0, 5.0, 3.0, 4.0];
@@ -791,3 +1037,13 @@ fn tree_fold1() {
         assert_eq!(actual, expected);
     }
 }
+
+#[test]
+fn exactly_one_question_mark_syntax_works() {
+    exactly_one_question_mark_return().unwrap_err();
+}
+
+fn exactly_one_question_mark_return() -> Result<(), ExactlyOneError<std::slice::Iter<'static, ()>>> {
+    [].iter().exactly_one()?;
+    Ok(())
+}