chore: add vendor directory

12 files changed, 5289 insertions, 0 deletions

diff --git a/vendor/itertools/tests/adaptors_no_collect.rs b/vendor/itertools/tests/adaptors_no_collect.rs
new file mode 100644
index 00000000..977224af
--- /dev/null
+++ b/vendor/itertools/tests/adaptors_no_collect.rs
@@ -0,0 +1,51 @@
+use itertools::Itertools;
+
+struct PanickingCounter {
+    curr: usize,
+    max: usize,
+}
+
+impl Iterator for PanickingCounter {
+    type Item = ();
+
+    fn next(&mut self) -> Option<Self::Item> {
+        self.curr += 1;
+
+        assert_ne!(
+            self.curr, self.max,
+            "Input iterator reached maximum of {} suggesting collection by adaptor",
+            self.max
+        );
+
+        Some(())
+    }
+}
+
+fn no_collect_test<A, T>(to_adaptor: T)
+where
+    A: Iterator,
+    T: Fn(PanickingCounter) -> A,
+{
+    let counter = PanickingCounter {
+        curr: 0,
+        max: 10_000,
+    };
+    let adaptor = to_adaptor(counter);
+
+    for _ in adaptor.take(5) {}
+}
+
+#[test]
+fn permutations_no_collect() {
+    no_collect_test(|iter| iter.permutations(5))
+}
+
+#[test]
+fn combinations_no_collect() {
+    no_collect_test(|iter| iter.combinations(5))
+}
+
+#[test]
+fn combinations_with_replacement_no_collect() {
+    no_collect_test(|iter| iter.combinations_with_replacement(5))
+}
diff --git a/vendor/itertools/tests/flatten_ok.rs b/vendor/itertools/tests/flatten_ok.rs
new file mode 100644
index 00000000..bf835b5d
--- /dev/null
+++ b/vendor/itertools/tests/flatten_ok.rs
@@ -0,0 +1,76 @@
+use itertools::{assert_equal, Itertools};
+use std::{ops::Range, vec::IntoIter};
+
+fn mix_data() -> IntoIter<Result<Range<i32>, bool>> {
+    vec![Ok(0..2), Err(false), Ok(2..4), Err(true), Ok(4..6)].into_iter()
+}
+
+fn ok_data() -> IntoIter<Result<Range<i32>, bool>> {
+    vec![Ok(0..2), Ok(2..4), Ok(4..6)].into_iter()
+}
+
+#[test]
+fn flatten_ok_mixed_expected_forward() {
+    assert_equal(
+        mix_data().flatten_ok(),
+        vec![
+            Ok(0),
+            Ok(1),
+            Err(false),
+            Ok(2),
+            Ok(3),
+            Err(true),
+            Ok(4),
+            Ok(5),
+        ],
+    );
+}
+
+#[test]
+fn flatten_ok_mixed_expected_reverse() {
+    assert_equal(
+        mix_data().flatten_ok().rev(),
+        vec![
+            Ok(5),
+            Ok(4),
+            Err(true),
+            Ok(3),
+            Ok(2),
+            Err(false),
+            Ok(1),
+            Ok(0),
+        ],
+    );
+}
+
+#[test]
+fn flatten_ok_collect_mixed_forward() {
+    assert_eq!(
+        mix_data().flatten_ok().collect::<Result<Vec<_>, _>>(),
+        Err(false)
+    );
+}
+
+#[test]
+fn flatten_ok_collect_mixed_reverse() {
+    assert_eq!(
+        mix_data().flatten_ok().rev().collect::<Result<Vec<_>, _>>(),
+        Err(true)
+    );
+}
+
+#[test]
+fn flatten_ok_collect_ok_forward() {
+    assert_eq!(
+        ok_data().flatten_ok().collect::<Result<Vec<_>, _>>(),
+        Ok((0..6).collect())
+    );
+}
+
+#[test]
+fn flatten_ok_collect_ok_reverse() {
+    assert_eq!(
+        ok_data().flatten_ok().rev().collect::<Result<Vec<_>, _>>(),
+        Ok((0..6).rev().collect())
+    );
+}
diff --git a/vendor/itertools/tests/laziness.rs b/vendor/itertools/tests/laziness.rs
new file mode 100644
index 00000000..c559d33a
--- /dev/null
+++ b/vendor/itertools/tests/laziness.rs
@@ -0,0 +1,283 @@
+#![allow(unstable_name_collisions)]
+
+use itertools::Itertools;
+
+#[derive(Debug, Clone)]
+#[must_use = "iterators are lazy and do nothing unless consumed"]
+struct Panicking;
+
+impl Iterator for Panicking {
+    type Item = u8;
+
+    fn next(&mut self) -> Option<u8> {
+        panic!("iterator adaptor is not lazy")
+    }
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        (0, Some(0))
+    }
+}
+
+impl ExactSizeIterator for Panicking {}
+
+/// ## Usage example
+/// ```compile_fail
+/// must_use_tests! {
+///     name {
+///         Panicking.name(); // Add `let _ =` only if required (encountered error).
+///     }
+///     // ...
+/// }
+/// ```
+///
+/// **TODO:** test missing `must_use` attributes better, maybe with a new lint.
+macro_rules! must_use_tests {
+    ($($(#[$attr:meta])* $name:ident $body:block)*) => {
+        $(
+            /// `#[deny(unused_must_use)]` should force us to ignore the resulting iterators
+            /// by adding `let _ = ...;` on every iterator.
+            /// If it does not, then a `must_use` attribute is missing on the associated struct.
+            ///
+            /// However, it's only helpful if we don't add `let _ =` before seeing if there is an error or not.
+            /// And it does not protect us against removed `must_use` attributes.
+            /// There is no simple way to test this yet.
+            #[deny(unused_must_use)]
+            #[test]
+            $(#[$attr])*
+            fn $name() $body
+        )*
+    };
+}
+
+must_use_tests! {
+    // Itertools trait:
+    interleave {
+        let _ = Panicking.interleave(Panicking);
+    }
+    interleave_shortest {
+        let _ = Panicking.interleave_shortest(Panicking);
+    }
+    intersperse {
+        let _ = Panicking.intersperse(0);
+    }
+    intersperse_with {
+        let _ = Panicking.intersperse_with(|| 0);
+    }
+    get {
+        let _ = Panicking.get(1..4);
+        let _ = Panicking.get(1..=4);
+        let _ = Panicking.get(1..);
+        let _ = Panicking.get(..4);
+        let _ = Panicking.get(..=4);
+        let _ = Panicking.get(..);
+    }
+    zip_longest {
+        let _ = Panicking.zip_longest(Panicking);
+    }
+    zip_eq {
+        let _ = Panicking.zip_eq(Panicking);
+    }
+    batching {
+        let _ = Panicking.batching(Iterator::next);
+    }
+    chunk_by {
+        // ChunkBy
+        let _ = Panicking.chunk_by(|x| *x);
+        // Groups
+        let _ = Panicking.chunk_by(|x| *x).into_iter();
+    }
+    chunks {
+        // IntoChunks
+        let _ = Panicking.chunks(1);
+        let _ = Panicking.chunks(2);
+        // Chunks
+        let _ = Panicking.chunks(1).into_iter();
+        let _ = Panicking.chunks(2).into_iter();
+    }
+    tuple_windows {
+        let _ = Panicking.tuple_windows::<(_,)>();
+        let _ = Panicking.tuple_windows::<(_, _)>();
+        let _ = Panicking.tuple_windows::<(_, _, _)>();
+    }
+    circular_tuple_windows {
+        let _ = Panicking.circular_tuple_windows::<(_,)>();
+        let _ = Panicking.circular_tuple_windows::<(_, _)>();
+        let _ = Panicking.circular_tuple_windows::<(_, _, _)>();
+    }
+    tuples {
+        let _ = Panicking.tuples::<(_,)>();
+        let _ = Panicking.tuples::<(_, _)>();
+        let _ = Panicking.tuples::<(_, _, _)>();
+    }
+    tee {
+        let _ = Panicking.tee();
+    }
+    map_into {
+        let _ = Panicking.map_into::<u16>();
+    }
+    map_ok {
+        let _ = Panicking.map(Ok::<u8, ()>).map_ok(|x| x + 1);
+    }
+    filter_ok {
+        let _ = Panicking.map(Ok::<u8, ()>).filter_ok(|x| x % 2 == 0);
+    }
+    filter_map_ok {
+        let _ = Panicking.map(Ok::<u8, ()>).filter_map_ok(|x| {
+            if x % 2 == 0 {
+                Some(x + 1)
+            } else {
+                None
+            }
+        });
+    }
+    flatten_ok {
+        let _ = Panicking.map(|x| Ok::<_, ()>([x])).flatten_ok();
+    }
+    merge {
+        let _ = Panicking.merge(Panicking);
+    }
+    merge_by {
+        let _ = Panicking.merge_by(Panicking, |_, _| true);
+    }
+    merge_join_by {
+        let _ = Panicking.merge_join_by(Panicking, |_, _| true);
+        let _ = Panicking.merge_join_by(Panicking, Ord::cmp);
+    }
+    #[should_panic]
+    kmerge {
+        let _ = Panicking.map(|_| Panicking).kmerge();
+    }
+    #[should_panic]
+    kmerge_by {
+        let _ = Panicking.map(|_| Panicking).kmerge_by(|_, _| true);
+    }
+    cartesian_product {
+        let _ = Panicking.cartesian_product(Panicking);
+    }
+    multi_cartesian_product {
+        let _ = vec![Panicking, Panicking, Panicking].into_iter().multi_cartesian_product();
+    }
+    coalesce {
+        let _ = Panicking.coalesce(|x, y| if x == y { Ok(x) } else { Err((x, y)) });
+    }
+    dedup {
+        let _ = Panicking.dedup();
+    }
+    dedup_by {
+        let _ = Panicking.dedup_by(|_, _| true);
+    }
+    dedup_with_count {
+        let _ = Panicking.dedup_with_count();
+    }
+    dedup_by_with_count {
+        let _ = Panicking.dedup_by_with_count(|_, _| true);
+    }
+    duplicates {
+        let _ = Panicking.duplicates();
+    }
+    duplicates_by {
+        let _ = Panicking.duplicates_by(|x| *x);
+    }
+    unique {
+        let _ = Panicking.unique();
+    }
+    unique_by {
+        let _ = Panicking.unique_by(|x| *x);
+    }
+    peeking_take_while {
+        let _ = Panicking.peekable().peeking_take_while(|x| x % 2 == 0);
+    }
+    take_while_ref {
+        let _ = Panicking.take_while_ref(|x| x % 2 == 0);
+    }
+    take_while_inclusive {
+        let _ = Panicking.take_while_inclusive(|x| x % 2 == 0);
+    }
+    while_some {
+        let _ = Panicking.map(Some).while_some();
+    }
+    tuple_combinations1 {
+        let _ = Panicking.tuple_combinations::<(_,)>();
+    }
+    #[should_panic]
+    tuple_combinations2 {
+        let _ = Panicking.tuple_combinations::<(_, _)>();
+    }
+    #[should_panic]
+    tuple_combinations3 {
+        let _ = Panicking.tuple_combinations::<(_, _, _)>();
+    }
+    combinations {
+        let _ = Panicking.combinations(0);
+        let _ = Panicking.combinations(1);
+        let _ = Panicking.combinations(2);
+    }
+    combinations_with_replacement {
+        let _ = Panicking.combinations_with_replacement(0);
+        let _ = Panicking.combinations_with_replacement(1);
+        let _ = Panicking.combinations_with_replacement(2);
+    }
+    permutations {
+        let _ = Panicking.permutations(0);
+        let _ = Panicking.permutations(1);
+        let _ = Panicking.permutations(2);
+    }
+    powerset {
+        let _ = Panicking.powerset();
+    }
+    pad_using {
+        let _ = Panicking.pad_using(25, |_| 10);
+    }
+    with_position {
+        let _ = Panicking.with_position();
+    }
+    positions {
+        let _ = Panicking.positions(|v| v % 2 == 0);
+    }
+    update {
+        let _ = Panicking.update(|n| *n += 1);
+    }
+    multipeek {
+        let _ = Panicking.multipeek();
+    }
+    // Not iterator themselves but still lazy.
+    into_grouping_map {
+        let _ = Panicking.map(|x| (x, x + 1)).into_grouping_map();
+    }
+    into_grouping_map_by {
+        let _ = Panicking.into_grouping_map_by(|x| *x);
+    }
+    // Macros:
+    iproduct {
+        let _ = itertools::iproduct!(Panicking);
+        let _ = itertools::iproduct!(Panicking, Panicking);
+        let _ = itertools::iproduct!(Panicking, Panicking, Panicking);
+    }
+    izip {
+        let _ = itertools::izip!(Panicking);
+        let _ = itertools::izip!(Panicking, Panicking);
+        let _ = itertools::izip!(Panicking, Panicking, Panicking);
+    }
+    chain {
+        let _ = itertools::chain!(Panicking);
+        let _ = itertools::chain!(Panicking, Panicking);
+        let _ = itertools::chain!(Panicking, Panicking, Panicking);
+    }
+    // Free functions:
+    multizip {
+        let _ = itertools::multizip((Panicking, Panicking));
+    }
+    put_back {
+        let _ = itertools::put_back(Panicking);
+        let _ = itertools::put_back(Panicking).with_value(15);
+    }
+    peek_nth {
+        let _ = itertools::peek_nth(Panicking);
+    }
+    put_back_n {
+        let _ = itertools::put_back_n(Panicking);
+    }
+    rciter {
+        let _ = itertools::rciter(Panicking);
+    }
+}
diff --git a/vendor/itertools/tests/macros_hygiene.rs b/vendor/itertools/tests/macros_hygiene.rs
new file mode 100644
index 00000000..e6e89555
--- /dev/null
+++ b/vendor/itertools/tests/macros_hygiene.rs
@@ -0,0 +1,27 @@
+mod alloc {}
+mod core {}
+mod either {}
+mod std {}
+
+#[test]
+fn iproduct_hygiene() {
+    let _ = itertools::iproduct!();
+    let _ = itertools::iproduct!(0..6);
+    let _ = itertools::iproduct!(0..6, 0..9);
+    let _ = itertools::iproduct!(0..6, 0..9, 0..12);
+}
+
+#[test]
+fn izip_hygiene() {
+    let _ = itertools::izip!(0..6);
+    let _ = itertools::izip!(0..6, 0..9);
+    let _ = itertools::izip!(0..6, 0..9, 0..12);
+}
+
+#[test]
+fn chain_hygiene() {
+    let _: ::std::iter::Empty<i32> = itertools::chain!();
+    let _ = itertools::chain!(0..6);
+    let _ = itertools::chain!(0..6, 0..9);
+    let _ = itertools::chain!(0..6, 0..9, 0..12);
+}
diff --git a/vendor/itertools/tests/merge_join.rs b/vendor/itertools/tests/merge_join.rs
new file mode 100644
index 00000000..776252fc
--- /dev/null
+++ b/vendor/itertools/tests/merge_join.rs
@@ -0,0 +1,101 @@
+use itertools::free::merge_join_by;
+use itertools::EitherOrBoth;
+
+#[test]
+fn empty() {
+    let left: Vec<u32> = vec![];
+    let right: Vec<u32> = vec![];
+    let expected_result: Vec<EitherOrBoth<u32>> = vec![];
+    let actual_result = merge_join_by(left, right, |l, r| l.cmp(r)).collect::<Vec<_>>();
+    assert_eq!(expected_result, actual_result);
+}
+
+#[test]
+fn left_only() {
+    let left: Vec<u32> = vec![1, 2, 3];
+    let right: Vec<u32> = vec![];
+    let expected_result: Vec<EitherOrBoth<u32>> = vec![
+        EitherOrBoth::Left(1),
+        EitherOrBoth::Left(2),
+        EitherOrBoth::Left(3),
+    ];
+    let actual_result = merge_join_by(left, right, |l, r| l.cmp(r)).collect::<Vec<_>>();
+    assert_eq!(expected_result, actual_result);
+}
+
+#[test]
+fn right_only() {
+    let left: Vec<u32> = vec![];
+    let right: Vec<u32> = vec![1, 2, 3];
+    let expected_result: Vec<EitherOrBoth<u32>> = vec![
+        EitherOrBoth::Right(1),
+        EitherOrBoth::Right(2),
+        EitherOrBoth::Right(3),
+    ];
+    let actual_result = merge_join_by(left, right, |l, r| l.cmp(r)).collect::<Vec<_>>();
+    assert_eq!(expected_result, actual_result);
+}
+
+#[test]
+fn first_left_then_right() {
+    let left: Vec<u32> = vec![1, 2, 3];
+    let right: Vec<u32> = vec![4, 5, 6];
+    let expected_result: Vec<EitherOrBoth<u32>> = vec![
+        EitherOrBoth::Left(1),
+        EitherOrBoth::Left(2),
+        EitherOrBoth::Left(3),
+        EitherOrBoth::Right(4),
+        EitherOrBoth::Right(5),
+        EitherOrBoth::Right(6),
+    ];
+    let actual_result = merge_join_by(left, right, |l, r| l.cmp(r)).collect::<Vec<_>>();
+    assert_eq!(expected_result, actual_result);
+}
+
+#[test]
+fn first_right_then_left() {
+    let left: Vec<u32> = vec![4, 5, 6];
+    let right: Vec<u32> = vec![1, 2, 3];
+    let expected_result: Vec<EitherOrBoth<u32>> = vec![
+        EitherOrBoth::Right(1),
+        EitherOrBoth::Right(2),
+        EitherOrBoth::Right(3),
+        EitherOrBoth::Left(4),
+        EitherOrBoth::Left(5),
+        EitherOrBoth::Left(6),
+    ];
+    let actual_result = merge_join_by(left, right, |l, r| l.cmp(r)).collect::<Vec<_>>();
+    assert_eq!(expected_result, actual_result);
+}
+
+#[test]
+fn interspersed_left_and_right() {
+    let left: Vec<u32> = vec![1, 3, 5];
+    let right: Vec<u32> = vec![2, 4, 6];
+    let expected_result: Vec<EitherOrBoth<u32>> = vec![
+        EitherOrBoth::Left(1),
+        EitherOrBoth::Right(2),
+        EitherOrBoth::Left(3),
+        EitherOrBoth::Right(4),
+        EitherOrBoth::Left(5),
+        EitherOrBoth::Right(6),
+    ];
+    let actual_result = merge_join_by(left, right, |l, r| l.cmp(r)).collect::<Vec<_>>();
+    assert_eq!(expected_result, actual_result);
+}
+
+#[test]
+fn overlapping_left_and_right() {
+    let left: Vec<u32> = vec![1, 3, 4, 6];
+    let right: Vec<u32> = vec![2, 3, 4, 5];
+    let expected_result: Vec<EitherOrBoth<u32>> = vec![
+        EitherOrBoth::Left(1),
+        EitherOrBoth::Right(2),
+        EitherOrBoth::Both(3, 3),
+        EitherOrBoth::Both(4, 4),
+        EitherOrBoth::Right(5),
+        EitherOrBoth::Left(6),
+    ];
+    let actual_result = merge_join_by(left, right, |l, r| l.cmp(r)).collect::<Vec<_>>();
+    assert_eq!(expected_result, actual_result);
+}
diff --git a/vendor/itertools/tests/peeking_take_while.rs b/vendor/itertools/tests/peeking_take_while.rs
new file mode 100644
index 00000000..5be97271
--- /dev/null
+++ b/vendor/itertools/tests/peeking_take_while.rs
@@ -0,0 +1,69 @@
+use itertools::Itertools;
+use itertools::{put_back, put_back_n};
+
+#[test]
+fn peeking_take_while_peekable() {
+    let mut r = (0..10).peekable();
+    r.peeking_take_while(|x| *x <= 3).count();
+    assert_eq!(r.next(), Some(4));
+}
+
+#[test]
+fn peeking_take_while_put_back() {
+    let mut r = put_back(0..10);
+    r.peeking_take_while(|x| *x <= 3).count();
+    assert_eq!(r.next(), Some(4));
+    r.peeking_take_while(|_| true).count();
+    assert_eq!(r.next(), None);
+}
+
+#[test]
+fn peeking_take_while_put_back_n() {
+    let mut r = put_back_n(6..10);
+    for elt in (0..6).rev() {
+        r.put_back(elt);
+    }
+    r.peeking_take_while(|x| *x <= 3).count();
+    assert_eq!(r.next(), Some(4));
+    r.peeking_take_while(|_| true).count();
+    assert_eq!(r.next(), None);
+}
+
+#[test]
+fn peeking_take_while_slice_iter() {
+    let v = [1, 2, 3, 4, 5, 6];
+    let mut r = v.iter();
+    r.peeking_take_while(|x| **x <= 3).count();
+    assert_eq!(r.next(), Some(&4));
+    r.peeking_take_while(|_| true).count();
+    assert_eq!(r.next(), None);
+}
+
+#[test]
+fn peeking_take_while_slice_iter_rev() {
+    let v = [1, 2, 3, 4, 5, 6];
+    let mut r = v.iter().rev();
+    r.peeking_take_while(|x| **x >= 3).count();
+    assert_eq!(r.next(), Some(&2));
+    r.peeking_take_while(|_| true).count();
+    assert_eq!(r.next(), None);
+}
+
+#[test]
+fn peeking_take_while_nested() {
+    let mut xs = (0..10).peekable();
+    let ys: Vec<_> = xs
+        .peeking_take_while(|x| *x < 6)
+        .peeking_take_while(|x| *x != 3)
+        .collect();
+    assert_eq!(ys, vec![0, 1, 2]);
+    assert_eq!(xs.next(), Some(3));
+
+    let mut xs = (4..10).peekable();
+    let ys: Vec<_> = xs
+        .peeking_take_while(|x| *x != 3)
+        .peeking_take_while(|x| *x < 6)
+        .collect();
+    assert_eq!(ys, vec![4, 5]);
+    assert_eq!(xs.next(), Some(6));
+}
diff --git a/vendor/itertools/tests/quick.rs b/vendor/itertools/tests/quick.rs
new file mode 100644
index 00000000..672901e7
--- /dev/null
+++ b/vendor/itertools/tests/quick.rs
@@ -0,0 +1,1969 @@
+//! The purpose of these tests is to cover corner cases of iterators
+//! and adaptors.
+//!
+//! In particular we test the tedious size_hint and exact size correctness.
+//!
+//! **NOTE:** Due to performance limitations, these tests are not run with miri!
+//! They cannot be relied upon to discover soundness issues.
+
+#![cfg(not(miri))]
+#![allow(deprecated, unstable_name_collisions)]
+
+use itertools::free::{
+    cloned, enumerate, multipeek, peek_nth, put_back, put_back_n, rciter, zip, zip_eq,
+};
+use itertools::Itertools;
+use itertools::{iproduct, izip, multizip, EitherOrBoth};
+use quickcheck as qc;
+use std::cmp::{max, min, Ordering};
+use std::collections::{HashMap, HashSet};
+use std::default::Default;
+use std::num::Wrapping;
+use std::ops::Range;
+
+use quickcheck::TestResult;
+use rand::seq::SliceRandom;
+use rand::Rng;
+
+/// Trait for size hint modifier types
+trait HintKind: Copy + Send + qc::Arbitrary {
+    fn loosen_bounds(&self, org_hint: (usize, Option<usize>)) -> (usize, Option<usize>);
+}
+
+/// Exact size hint variant that leaves hints unchanged
+#[derive(Clone, Copy, Debug)]
+struct Exact {}
+
+impl HintKind for Exact {
+    fn loosen_bounds(&self, org_hint: (usize, Option<usize>)) -> (usize, Option<usize>) {
+        org_hint
+    }
+}
+
+impl qc::Arbitrary for Exact {
+    fn arbitrary<G: qc::Gen>(_: &mut G) -> Self {
+        Self {}
+    }
+}
+
+/// Inexact size hint variant to simulate imprecise (but valid) size hints
+///
+/// Will always decrease the lower bound and increase the upper bound
+/// of the size hint by set amounts.
+#[derive(Clone, Copy, Debug)]
+struct Inexact {
+    underestimate: usize,
+    overestimate: usize,
+}
+
+impl HintKind for Inexact {
+    fn loosen_bounds(&self, org_hint: (usize, Option<usize>)) -> (usize, Option<usize>) {
+        let (org_lower, org_upper) = org_hint;
+        (
+            org_lower.saturating_sub(self.underestimate),
+            org_upper.and_then(move |x| x.checked_add(self.overestimate)),
+        )
+    }
+}
+
+impl qc::Arbitrary for Inexact {
+    fn arbitrary<G: qc::Gen>(g: &mut G) -> Self {
+        let ue_value = usize::arbitrary(g);
+        let oe_value = usize::arbitrary(g);
+        // Compensate for quickcheck using extreme values too rarely
+        let ue_choices = &[0, ue_value, usize::MAX];
+        let oe_choices = &[0, oe_value, usize::MAX];
+        Self {
+            underestimate: *ue_choices.choose(g).unwrap(),
+            overestimate: *oe_choices.choose(g).unwrap(),
+        }
+    }
+
+    fn shrink(&self) -> Box<dyn Iterator<Item = Self>> {
+        let underestimate_value = self.underestimate;
+        let overestimate_value = self.overestimate;
+        Box::new(underestimate_value.shrink().flat_map(move |ue_value| {
+            overestimate_value.shrink().map(move |oe_value| Self {
+                underestimate: ue_value,
+                overestimate: oe_value,
+            })
+        }))
+    }
+}
+
+/// Our base iterator that we can impl Arbitrary for
+///
+/// By default we'll return inexact bounds estimates for size_hint
+/// to make tests harder to pass.
+///
+/// NOTE: Iter is tricky and is not fused, to help catch bugs.
+/// At the end it will return None once, then return Some(0),
+/// then return None again.
+#[derive(Clone, Debug)]
+struct Iter<T, SK: HintKind = Inexact> {
+    iterator: Range<T>,
+    // fuse/done flag
+    fuse_flag: i32,
+    hint_kind: SK,
+}
+
+impl<T, HK> Iter<T, HK>
+where
+    HK: HintKind,
+{
+    fn new(it: Range<T>, hint_kind: HK) -> Self {
+        Self {
+            iterator: it,
+            fuse_flag: 0,
+            hint_kind,
+        }
+    }
+}
+
+impl<T, HK> Iterator for Iter<T, HK>
+where
+    Range<T>: Iterator,
+    <Range<T> as Iterator>::Item: Default,
+    HK: HintKind,
+{
+    type Item = <Range<T> as Iterator>::Item;
+
+    fn next(&mut self) -> Option<Self::Item> {
+        let elt = self.iterator.next();
+        if elt.is_none() {
+            self.fuse_flag += 1;
+            // check fuse flag
+            if self.fuse_flag == 2 {
+                return Some(Default::default());
+            }
+        }
+        elt
+    }
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        let org_hint = self.iterator.size_hint();
+        self.hint_kind.loosen_bounds(org_hint)
+    }
+}
+
+impl<T, HK> DoubleEndedIterator for Iter<T, HK>
+where
+    Range<T>: DoubleEndedIterator,
+    <Range<T> as Iterator>::Item: Default,
+    HK: HintKind,
+{
+    fn next_back(&mut self) -> Option<Self::Item> {
+        self.iterator.next_back()
+    }
+}
+
+impl<T> ExactSizeIterator for Iter<T, Exact>
+where
+    Range<T>: ExactSizeIterator,
+    <Range<T> as Iterator>::Item: Default,
+{
+}
+
+impl<T, HK> qc::Arbitrary for Iter<T, HK>
+where
+    T: qc::Arbitrary,
+    HK: HintKind,
+{
+    fn arbitrary<G: qc::Gen>(g: &mut G) -> Self {
+        Self::new(T::arbitrary(g)..T::arbitrary(g), HK::arbitrary(g))
+    }
+
+    fn shrink(&self) -> Box<dyn Iterator<Item = Self>> {
+        let r = self.iterator.clone();
+        let hint_kind = self.hint_kind;
+        Box::new(r.start.shrink().flat_map(move |a| {
+            r.end
+                .shrink()
+                .map(move |b| Self::new(a.clone()..b, hint_kind))
+        }))
+    }
+}
+
+/// A meta-iterator which yields `Iter<i32>`s whose start/endpoints are
+/// increased or decreased linearly on each iteration.
+#[derive(Clone, Debug)]
+struct ShiftRange<HK = Inexact> {
+    range_start: i32,
+    range_end: i32,
+    start_step: i32,
+    end_step: i32,
+    iter_count: u32,
+    hint_kind: HK,
+}
+
+impl<HK> Iterator for ShiftRange<HK>
+where
+    HK: HintKind,
+{
+    type Item = Iter<i32, HK>;
+
+    fn next(&mut self) -> Option<Self::Item> {
+        if self.iter_count == 0 {
+            return None;
+        }
+
+        let iter = Iter::new(self.range_start..self.range_end, self.hint_kind);
+
+        self.range_start += self.start_step;
+        self.range_end += self.end_step;
+        self.iter_count -= 1;
+
+        Some(iter)
+    }
+}
+
+impl ExactSizeIterator for ShiftRange<Exact> {}
+
+impl<HK> qc::Arbitrary for ShiftRange<HK>
+where
+    HK: HintKind,
+{
+    fn arbitrary<G: qc::Gen>(g: &mut G) -> Self {
+        const MAX_STARTING_RANGE_DIFF: i32 = 32;
+        const MAX_STEP_MODULO: i32 = 8;
+        const MAX_ITER_COUNT: u32 = 3;
+
+        let range_start = qc::Arbitrary::arbitrary(g);
+        let range_end = range_start + g.gen_range(0, MAX_STARTING_RANGE_DIFF + 1);
+        let start_step = g.gen_range(-MAX_STEP_MODULO, MAX_STEP_MODULO + 1);
+        let end_step = g.gen_range(-MAX_STEP_MODULO, MAX_STEP_MODULO + 1);
+        let iter_count = g.gen_range(0, MAX_ITER_COUNT + 1);
+        let hint_kind = qc::Arbitrary::arbitrary(g);
+
+        Self {
+            range_start,
+            range_end,
+            start_step,
+            end_step,
+            iter_count,
+            hint_kind,
+        }
+    }
+}
+
+fn correct_count<I, F>(get_it: F) -> bool
+where
+    I: Iterator,
+    F: Fn() -> I,
+{
+    let mut counts = vec![get_it().count()];
+
+    'outer: loop {
+        let mut it = get_it();
+
+        for _ in 0..(counts.len() - 1) {
+            if it.next().is_none() {
+                panic!("Iterator shouldn't be finished, may not be deterministic");
+            }
+        }
+
+        if it.next().is_none() {
+            break 'outer;
+        }
+
+        counts.push(it.count());
+    }
+
+    let total_actual_count = counts.len() - 1;
+
+    for (i, returned_count) in counts.into_iter().enumerate() {
+        let actual_count = total_actual_count - i;
+        if actual_count != returned_count {
+            println!(
+                "Total iterations: {} True count: {} returned count: {}",
+                i, actual_count, returned_count
+            );
+
+            return false;
+        }
+    }
+
+    true
+}
+
+fn correct_size_hint<I: Iterator>(mut it: I) -> bool {
+    // record size hint at each iteration
+    let initial_hint = it.size_hint();
+    let mut hints = Vec::with_capacity(initial_hint.0 + 1);
+    hints.push(initial_hint);
+    while let Some(_) = it.next() {
+        hints.push(it.size_hint())
+    }
+
+    let mut true_count = hints.len(); // start off +1 too much
+
+    // check all the size hints
+    for &(low, hi) in &hints {
+        true_count -= 1;
+        if low > true_count || (hi.is_some() && hi.unwrap() < true_count) {
+            println!("True size: {:?}, size hint: {:?}", true_count, (low, hi));
+            //println!("All hints: {:?}", hints);
+            return false;
+        }
+    }
+    true
+}
+
+fn exact_size<I: ExactSizeIterator>(mut it: I) -> bool {
+    // check every iteration
+    let (mut low, mut hi) = it.size_hint();
+    if Some(low) != hi {
+        return false;
+    }
+    while let Some(_) = it.next() {
+        let (xlow, xhi) = it.size_hint();
+        if low != xlow + 1 {
+            return false;
+        }
+        low = xlow;
+        hi = xhi;
+        if Some(low) != hi {
+            return false;
+        }
+    }
+    let (low, hi) = it.size_hint();
+    low == 0 && hi == Some(0)
+}
+
+// Exact size for this case, without ExactSizeIterator
+fn exact_size_for_this<I: Iterator>(mut it: I) -> bool {
+    // check every iteration
+    let (mut low, mut hi) = it.size_hint();
+    if Some(low) != hi {
+        return false;
+    }
+    while let Some(_) = it.next() {
+        let (xlow, xhi) = it.size_hint();
+        if low != xlow + 1 {
+            return false;
+        }
+        low = xlow;
+        hi = xhi;
+        if Some(low) != hi {
+            return false;
+        }
+    }
+    let (low, hi) = it.size_hint();
+    low == 0 && hi == Some(0)
+}
+
+/*
+ * NOTE: Range<i8> is broken!
+ * (all signed ranges are)
+#[quickcheck]
+fn size_range_i8(a: Iter<i8>) -> bool {
+    exact_size(a)
+}
+
+#[quickcheck]
+fn size_range_i16(a: Iter<i16>) -> bool {
+    exact_size(a)
+}
+
+#[quickcheck]
+fn size_range_u8(a: Iter<u8>) -> bool {
+    exact_size(a)
+}
+ */
+
+macro_rules! quickcheck {
+    // accept several property function definitions
+    // The property functions can use pattern matching and `mut` as usual
+    // in the function arguments, but the functions can not be generic.
+    {$($(#$attr:tt)* fn $fn_name:ident($($arg:tt)*) -> $ret:ty { $($code:tt)* })*} => (
+        $(
+            #[test]
+            $(#$attr)*
+            fn $fn_name() {
+                fn prop($($arg)*) -> $ret {
+                    $($code)*
+                }
+                ::quickcheck::quickcheck(quickcheck!(@fn prop [] $($arg)*));
+            }
+        )*
+    );
+    // parse argument list (with patterns allowed) into prop as fn(_, _) -> _
+    (@fn $f:ident [$($t:tt)*]) => {
+        $f as fn($($t),*) -> _
+    };
+    (@fn $f:ident [$($p:tt)*] : $($tail:tt)*) => {
+        quickcheck!(@fn $f [$($p)* _] $($tail)*)
+    };
+    (@fn $f:ident [$($p:tt)*] $t:tt $($tail:tt)*) => {
+        quickcheck!(@fn $f [$($p)*] $($tail)*)
+    };
+}
+
+quickcheck! {
+
+    fn size_product(a: Iter<u16>, b: Iter<u16>) -> bool {
+        correct_size_hint(a.cartesian_product(b))
+    }
+    fn size_product3(a: Iter<u16>, b: Iter<u16>, c: Iter<u16>) -> bool {
+        correct_size_hint(iproduct!(a, b, c))
+    }
+
+    fn correct_cartesian_product3(a: Iter<u16>, b: Iter<u16>, c: Iter<u16>,
+                                  take_manual: usize) -> ()
+    {
+        // test correctness of iproduct through regular iteration (take)
+        // and through fold.
+        let ac = a.clone();
+        let br = &b.clone();
+        let cr = &c.clone();
+        let answer: Vec<_> = ac.flat_map(move |ea| br.clone().flat_map(move |eb| cr.clone().map(move |ec| (ea, eb, ec)))).collect();
+        let mut product_iter = iproduct!(a, b, c);
+        let mut actual = Vec::new();
+
+        actual.extend((&mut product_iter).take(take_manual));
+        if actual.len() == take_manual {
+            product_iter.fold((), |(), elt| actual.push(elt));
+        }
+        assert_eq!(answer, actual);
+    }
+
+    fn size_multi_product(a: ShiftRange) -> bool {
+        correct_size_hint(a.multi_cartesian_product())
+    }
+    fn correct_multi_product3(a: ShiftRange, take_manual: usize) -> () {
+        // Fix no. of iterators at 3
+        let a = ShiftRange { iter_count: 3, ..a };
+
+        // test correctness of MultiProduct through regular iteration (take)
+        // and through fold.
+        let mut iters = a.clone();
+        let i0 = iters.next().unwrap();
+        let i1r = &iters.next().unwrap();
+        let i2r = &iters.next().unwrap();
+        let answer: Vec<_> = i0.flat_map(move |ei0| i1r.clone().flat_map(move |ei1| i2r.clone().map(move |ei2| vec![ei0, ei1, ei2]))).collect();
+        let mut multi_product = a.clone().multi_cartesian_product();
+        let mut actual = Vec::new();
+
+        actual.extend((&mut multi_product).take(take_manual));
+        if actual.len() == take_manual {
+            multi_product.fold((), |(), elt| actual.push(elt));
+        }
+        assert_eq!(answer, actual);
+
+        assert_eq!(answer.into_iter().last(), a.multi_cartesian_product().last());
+    }
+
+    fn correct_empty_multi_product() -> () {
+        let empty = Vec::<std::vec::IntoIter<i32>>::new().into_iter().multi_cartesian_product();
+        assert!(correct_size_hint(empty.clone()));
+        itertools::assert_equal(empty, std::iter::once(Vec::new()))
+    }
+
+    fn size_multipeek(a: Iter<u16, Exact>, s: u8) -> bool {
+        let mut it = multipeek(a);
+        // peek a few times
+        for _ in 0..s {
+            it.peek();
+        }
+        exact_size(it)
+    }
+
+    fn size_peek_nth(a: Iter<u16, Exact>, s: u8) -> bool {
+        let mut it = peek_nth(a);
+        // peek a few times
+        for n in 0..s {
+            it.peek_nth(n as usize);
+        }
+        exact_size(it)
+    }
+
+    fn equal_merge(mut a: Vec<i16>, mut b: Vec<i16>) -> bool {
+        a.sort();
+        b.sort();
+        let mut merged = a.clone();
+        merged.extend(b.iter().cloned());
+        merged.sort();
+        itertools::equal(&merged, a.iter().merge(&b))
+    }
+    fn size_merge(a: Iter<u16>, b: Iter<u16>) -> bool {
+        correct_size_hint(a.merge(b))
+    }
+    fn size_zip(a: Iter<i16, Exact>, b: Iter<i16, Exact>, c: Iter<i16, Exact>) -> bool {
+        let filt = a.clone().dedup();
+        correct_size_hint(multizip((filt, b.clone(), c.clone()))) &&
+            exact_size(multizip((a, b, c)))
+    }
+    fn size_zip_rc(a: Iter<i16>, b: Iter<i16>) -> bool {
+        let rc = rciter(a);
+        correct_size_hint(multizip((&rc, &rc, b)))
+    }
+
+    fn size_zip_macro(a: Iter<i16, Exact>, b: Iter<i16, Exact>, c: Iter<i16, Exact>) -> bool {
+        let filt = a.clone().dedup();
+        correct_size_hint(izip!(filt, b.clone(), c.clone())) &&
+            exact_size(izip!(a, b, c))
+    }
+    fn equal_kmerge(mut a: Vec<i16>, mut b: Vec<i16>, mut c: Vec<i16>) -> bool {
+        use itertools::free::kmerge;
+        a.sort();
+        b.sort();
+        c.sort();
+        let mut merged = a.clone();
+        merged.extend(b.iter().cloned());
+        merged.extend(c.iter().cloned());
+        merged.sort();
+        itertools::equal(merged.into_iter(), kmerge(vec![a, b, c]))
+    }
+
+    // Any number of input iterators
+    fn equal_kmerge_2(mut inputs: Vec<Vec<i16>>) -> bool {
+        use itertools::free::kmerge;
+        // sort the inputs
+        for input in &mut inputs {
+            input.sort();
+        }
+        let mut merged = inputs.concat();
+        merged.sort();
+        itertools::equal(merged.into_iter(), kmerge(inputs))
+    }
+
+    // Any number of input iterators
+    fn equal_kmerge_by_ge(mut inputs: Vec<Vec<i16>>) -> bool {
+        // sort the inputs
+        for input in &mut inputs {
+            input.sort();
+            input.reverse();
+        }
+        let mut merged = inputs.concat();
+        merged.sort();
+        merged.reverse();
+        itertools::equal(merged.into_iter(),
+                         inputs.into_iter().kmerge_by(|x, y| x >= y))
+    }
+
+    // Any number of input iterators
+    fn equal_kmerge_by_lt(mut inputs: Vec<Vec<i16>>) -> bool {
+        // sort the inputs
+        for input in &mut inputs {
+            input.sort();
+        }
+        let mut merged = inputs.concat();
+        merged.sort();
+        itertools::equal(merged.into_iter(),
+                         inputs.into_iter().kmerge_by(|x, y| x < y))
+    }
+
+    // Any number of input iterators
+    fn equal_kmerge_by_le(mut inputs: Vec<Vec<i16>>) -> bool {
+        // sort the inputs
+        for input in &mut inputs {
+            input.sort();
+        }
+        let mut merged = inputs.concat();
+        merged.sort();
+        itertools::equal(merged.into_iter(),
+                         inputs.into_iter().kmerge_by(|x, y| x <= y))
+    }
+    fn size_kmerge(a: Iter<i16>, b: Iter<i16>, c: Iter<i16>) -> bool {
+        use itertools::free::kmerge;
+        correct_size_hint(kmerge(vec![a, b, c]))
+    }
+    fn equal_zip_eq(a: Vec<i32>, b: Vec<i32>) -> bool {
+        let len = std::cmp::min(a.len(), b.len());
+        let a = &a[..len];
+        let b = &b[..len];
+        itertools::equal(zip_eq(a, b), zip(a, b))
+    }
+
+    #[should_panic]
+    fn zip_eq_panics(a: Vec<u8>, b: Vec<u8>) -> TestResult {
+        if a.len() == b.len() { return TestResult::discard(); }
+        zip_eq(a.iter(), b.iter()).for_each(|_| {});
+        TestResult::passed() // won't come here
+    }
+
+    fn equal_positions(a: Vec<i32>) -> bool {
+        let with_pos = a.iter().positions(|v| v % 2 == 0);
+        let without = a.iter().enumerate().filter(|(_, v)| *v % 2 == 0).map(|(i, _)| i);
+        itertools::equal(with_pos.clone(), without.clone())
+            && itertools::equal(with_pos.rev(), without.rev())
+    }
+    fn size_zip_longest(a: Iter<i16, Exact>, b: Iter<i16, Exact>) -> bool {
+        let filt = a.clone().dedup();
+        let filt2 = b.clone().dedup();
+        correct_size_hint(filt.zip_longest(b.clone())) &&
+        correct_size_hint(a.clone().zip_longest(filt2)) &&
+            exact_size(a.zip_longest(b))
+    }
+    fn size_2_zip_longest(a: Iter<i16>, b: Iter<i16>) -> bool {
+        let it = a.clone().zip_longest(b.clone());
+        let jt = a.clone().zip_longest(b.clone());
+        itertools::equal(a,
+                         it.filter_map(|elt| match elt {
+                             EitherOrBoth::Both(x, _) => Some(x),
+                             EitherOrBoth::Left(x) => Some(x),
+                             _ => None,
+                         }
+                         ))
+            &&
+        itertools::equal(b,
+                         jt.filter_map(|elt| match elt {
+                             EitherOrBoth::Both(_, y) => Some(y),
+                             EitherOrBoth::Right(y) => Some(y),
+                             _ => None,
+                         }
+                         ))
+    }
+    fn size_interleave(a: Iter<i16>, b: Iter<i16>) -> bool {
+        correct_size_hint(a.interleave(b))
+    }
+    fn exact_interleave(a: Iter<i16, Exact>, b: Iter<i16, Exact>) -> bool {
+        exact_size_for_this(a.interleave(b))
+    }
+    fn size_interleave_shortest(a: Iter<i16>, b: Iter<i16>) -> bool {
+        correct_size_hint(a.interleave_shortest(b))
+    }
+    fn exact_interleave_shortest(a: Vec<()>, b: Vec<()>) -> bool {
+        exact_size_for_this(a.iter().interleave_shortest(&b))
+    }
+    fn size_intersperse(a: Iter<i16>, x: i16) -> bool {
+        correct_size_hint(a.intersperse(x))
+    }
+    fn equal_intersperse(a: Vec<i32>, x: i32) -> bool {
+        let mut inter = false;
+        let mut i = 0;
+        for elt in a.iter().cloned().intersperse(x) {
+            if inter {
+                if elt != x { return false }
+            } else {
+                if elt != a[i] { return false }
+                i += 1;
+            }
+            inter = !inter;
+        }
+        true
+    }
+
+    fn equal_combinations_2(a: Vec<u8>) -> bool {
+        let mut v = Vec::new();
+        for (i, x) in enumerate(&a) {
+            for y in &a[i + 1..] {
+                v.push((x, y));
+            }
+        }
+        itertools::equal(a.iter().tuple_combinations::<(_, _)>(), v)
+    }
+
+    fn collect_tuple_matches_size(a: Iter<i16>) -> bool {
+        let size = a.clone().count();
+        a.collect_tuple::<(_, _, _)>().is_some() == (size == 3)
+    }
+
+    fn correct_permutations(vals: HashSet<i32>, k: usize) -> () {
+        // Test permutations only on iterators of distinct integers, to prevent
+        // false positives.
+
+        const MAX_N: usize = 5;
+
+        let n = min(vals.len(), MAX_N);
+        let vals: HashSet<i32> = vals.into_iter().take(n).collect();
+
+        let perms = vals.iter().permutations(k);
+
+        let mut actual = HashSet::new();
+
+        for perm in perms {
+            assert_eq!(perm.len(), k);
+
+            let all_items_valid = perm.iter().all(|p| vals.contains(p));
+            assert!(all_items_valid, "perm contains value not from input: {:?}", perm);
+
+            // Check that all perm items are distinct
+            let distinct_len = {
+                let perm_set: HashSet<_> = perm.iter().collect();
+                perm_set.len()
+            };
+            assert_eq!(perm.len(), distinct_len);
+
+            // Check that the perm is new
+            assert!(actual.insert(perm.clone()), "perm already encountered: {:?}", perm);
+        }
+    }
+
+    fn permutations_lexic_order(a: usize, b: usize) -> () {
+        let a = a % 6;
+        let b = b % 6;
+
+        let n = max(a, b);
+        let k = min (a, b);
+
+        let expected_first: Vec<usize> = (0..k).collect();
+        let expected_last: Vec<usize> = ((n - k)..n).rev().collect();
+
+        let mut perms = (0..n).permutations(k);
+
+        let mut curr_perm = match perms.next() {
+            Some(p) => p,
+            None => { return; }
+        };
+
+        assert_eq!(expected_first, curr_perm);
+
+        for next_perm in perms {
+            assert!(
+                next_perm > curr_perm,
+                "next perm isn't greater-than current; next_perm={:?} curr_perm={:?} n={}",
+                next_perm, curr_perm, n
+            );
+
+            curr_perm = next_perm;
+        }
+
+        assert_eq!(expected_last, curr_perm);
+
+    }
+
+    fn permutations_count(n: usize, k: usize) -> bool {
+        let n = n % 6;
+
+        correct_count(|| (0..n).permutations(k))
+    }
+
+    fn permutations_size(a: Iter<i32>, k: usize) -> bool {
+        correct_size_hint(a.take(5).permutations(k))
+    }
+
+    fn permutations_k0_yields_once(n: usize) -> () {
+        let k = 0;
+        let expected: Vec<Vec<usize>> = vec![vec![]];
+        let actual = (0..n).permutations(k).collect_vec();
+
+        assert_eq!(expected, actual);
+    }
+}
+
+quickcheck! {
+    fn correct_peek_nth(mut a: Vec<u16>) -> () {
+        let mut it = peek_nth(a.clone());
+        for start_pos in 0..a.len() + 2 {
+            for real_idx in start_pos..a.len() + 2 {
+                let peek_idx = real_idx - start_pos;
+                assert_eq!(it.peek_nth(peek_idx), a.get(real_idx));
+                assert_eq!(it.peek_nth_mut(peek_idx), a.get_mut(real_idx));
+            }
+            assert_eq!(it.next(), a.get(start_pos).copied());
+        }
+    }
+
+    fn peek_nth_mut_replace(a: Vec<u16>, b: Vec<u16>) -> () {
+        let mut it = peek_nth(a.iter());
+        for (i, m) in b.iter().enumerate().take(a.len().min(b.len())) {
+            *it.peek_nth_mut(i).unwrap() = m;
+        }
+        for (i, m) in a.iter().enumerate() {
+             assert_eq!(it.next().unwrap(), b.get(i).unwrap_or(m));
+        }
+        assert_eq!(it.next(), None);
+        assert_eq!(it.next(), None);
+    }
+
+    fn peek_nth_next_if(a: Vec<u8>) -> () {
+        let mut it = peek_nth(a.clone());
+        for (idx, mut value) in a.iter().copied().enumerate() {
+            let should_be_none = it.next_if(|x| x != &value);
+            assert_eq!(should_be_none, None);
+            if value % 5 == 0 {
+                // Sometimes, peek up to 3 further.
+                let n = value as usize % 3;
+                let nth = it.peek_nth(n);
+                assert_eq!(nth, a.get(idx + n));
+            } else if value % 5 == 1 {
+                // Sometimes, peek next element mutably.
+                if let Some(v) = it.peek_mut() {
+                    *v = v.wrapping_sub(1);
+                    let should_be_none = it.next_if_eq(&value);
+                    assert_eq!(should_be_none, None);
+                    value = value.wrapping_sub(1);
+                }
+            }
+            let eq = it.next_if_eq(&value);
+            assert_eq!(eq, Some(value));
+        }
+    }
+}
+
+quickcheck! {
+    fn dedup_via_coalesce(a: Vec<i32>) -> bool {
+        let mut b = a.clone();
+        b.dedup();
+        itertools::equal(
+            &b,
+            a
+                .iter()
+                .coalesce(|x, y| {
+                    if x==y {
+                        Ok(x)
+                    } else {
+                        Err((x, y))
+                    }
+                })
+                .fold(vec![], |mut v, n| {
+                    v.push(n);
+                    v
+                })
+        )
+    }
+}
+
+quickcheck! {
+    fn equal_dedup(a: Vec<i32>) -> bool {
+        let mut b = a.clone();
+        b.dedup();
+        itertools::equal(&b, a.iter().dedup())
+    }
+}
+
+quickcheck! {
+    fn equal_dedup_by(a: Vec<(i32, i32)>) -> bool {
+        let mut b = a.clone();
+        b.dedup_by(|x, y| x.0==y.0);
+        itertools::equal(&b, a.iter().dedup_by(|x, y| x.0==y.0))
+    }
+}
+
+quickcheck! {
+    fn size_dedup(a: Vec<i32>) -> bool {
+        correct_size_hint(a.iter().dedup())
+    }
+}
+
+quickcheck! {
+    fn size_dedup_by(a: Vec<(i32, i32)>) -> bool {
+        correct_size_hint(a.iter().dedup_by(|x, y| x.0==y.0))
+    }
+}
+
+quickcheck! {
+    fn exact_repeatn((n, x): (usize, i32)) -> bool {
+        let it = itertools::repeat_n(x, n);
+        exact_size(it)
+    }
+}
+
+quickcheck! {
+    fn size_put_back(a: Vec<u8>, x: Option<u8>) -> bool {
+        let mut it = put_back(a.into_iter());
+        if let Some(t) = x {
+            it.put_back(t);
+        }
+        correct_size_hint(it)
+    }
+}
+
+quickcheck! {
+    fn size_put_backn(a: Vec<u8>, b: Vec<u8>) -> bool {
+        let mut it = put_back_n(a.into_iter());
+        for elt in b {
+            it.put_back(elt)
+        }
+        correct_size_hint(it)
+    }
+}
+
+quickcheck! {
+    fn merge_join_by_ordering_vs_bool(a: Vec<u8>, b: Vec<u8>) -> bool {
+        use either::Either;
+        use itertools::free::merge_join_by;
+        let mut has_equal = false;
+        let it_ord = merge_join_by(a.clone(), b.clone(), Ord::cmp).flat_map(|v| match v {
+            EitherOrBoth::Both(l, r) => {
+                has_equal = true;
+                vec![Either::Left(l), Either::Right(r)]
+            }
+            EitherOrBoth::Left(l) => vec![Either::Left(l)],
+            EitherOrBoth::Right(r) => vec![Either::Right(r)],
+        });
+        let it_bool = merge_join_by(a, b, PartialOrd::le);
+        itertools::equal(it_ord, it_bool) || has_equal
+    }
+    fn merge_join_by_bool_unwrapped_is_merge_by(a: Vec<u8>, b: Vec<u8>) -> bool {
+        use either::Either;
+        use itertools::free::merge_join_by;
+        let it = a.clone().into_iter().merge_by(b.clone(), PartialOrd::ge);
+        let it_join = merge_join_by(a, b, PartialOrd::ge).map(Either::into_inner);
+        itertools::equal(it, it_join)
+    }
+}
+
+quickcheck! {
+    fn size_tee(a: Vec<u8>) -> bool {
+        let (mut t1, mut t2) = a.iter().tee();
+        t1.next();
+        t1.next();
+        t2.next();
+        exact_size(t1) && exact_size(t2)
+    }
+}
+
+quickcheck! {
+    fn size_tee_2(a: Vec<u8>) -> bool {
+        let (mut t1, mut t2) = a.iter().dedup().tee();
+        t1.next();
+        t1.next();
+        t2.next();
+        correct_size_hint(t1) && correct_size_hint(t2)
+    }
+}
+
+quickcheck! {
+    fn size_take_while_ref(a: Vec<u8>, stop: u8) -> bool {
+        correct_size_hint(a.iter().take_while_ref(|x| **x != stop))
+    }
+}
+
+quickcheck! {
+    fn equal_partition(a: Vec<i32>) -> bool {
+        let mut a = a;
+        let mut ap = a.clone();
+        let split_index = itertools::partition(&mut ap, |x| *x >= 0);
+        let parted = (0..split_index).all(|i| ap[i] >= 0) &&
+            (split_index..a.len()).all(|i| ap[i] < 0);
+
+        a.sort();
+        ap.sort();
+        parted && (a == ap)
+    }
+}
+
+quickcheck! {
+    fn size_combinations(a: Iter<i16>) -> bool {
+        let it = a.clone().tuple_combinations::<(_, _)>();
+        correct_size_hint(it.clone()) && it.count() == binomial(a.count(), 2)
+    }
+
+    fn exact_size_combinations_1(a: Vec<u8>) -> bool {
+        let it = a.iter().tuple_combinations::<(_,)>();
+        exact_size_for_this(it.clone()) && it.count() == binomial(a.len(), 1)
+    }
+    fn exact_size_combinations_2(a: Vec<u8>) -> bool {
+        let it = a.iter().tuple_combinations::<(_, _)>();
+        exact_size_for_this(it.clone()) && it.count() == binomial(a.len(), 2)
+    }
+    fn exact_size_combinations_3(mut a: Vec<u8>) -> bool {
+        a.truncate(15);
+        let it = a.iter().tuple_combinations::<(_, _, _)>();
+        exact_size_for_this(it.clone()) && it.count() == binomial(a.len(), 3)
+    }
+}
+
+fn binomial(n: usize, k: usize) -> usize {
+    if k > n {
+        0
+    } else {
+        (n - k + 1..=n).product::<usize>() / (1..=k).product::<usize>()
+    }
+}
+
+quickcheck! {
+    fn equal_combinations(it: Iter<i16>) -> bool {
+        let values = it.clone().collect_vec();
+        let mut cmb = it.tuple_combinations();
+        for i in 0..values.len() {
+            for j in i+1..values.len() {
+                let pair = (values[i], values[j]);
+                if pair != cmb.next().unwrap() {
+                    return false;
+                }
+            }
+        }
+        cmb.next().is_none()
+    }
+}
+
+quickcheck! {
+    fn size_pad_tail(it: Iter<i8>, pad: u8) -> bool {
+        correct_size_hint(it.clone().pad_using(pad as usize, |_| 0)) &&
+            correct_size_hint(it.dropping(1).rev().pad_using(pad as usize, |_| 0))
+    }
+}
+
+quickcheck! {
+    fn size_pad_tail2(it: Iter<i8, Exact>, pad: u8) -> bool {
+        exact_size(it.pad_using(pad as usize, |_| 0))
+    }
+}
+
+quickcheck! {
+    fn size_powerset(it: Iter<u8, Exact>) -> bool {
+        // Powerset cardinality gets large very quickly, limit input to keep test fast.
+        correct_size_hint(it.take(12).powerset())
+    }
+}
+
+quickcheck! {
+    fn size_duplicates(it: Iter<i8>) -> bool {
+        correct_size_hint(it.duplicates())
+    }
+}
+
+quickcheck! {
+    fn size_unique(it: Iter<i8>) -> bool {
+        correct_size_hint(it.unique())
+    }
+
+    fn count_unique(it: Vec<i8>, take_first: u8) -> () {
+        let answer = {
+            let mut v = it.clone();
+            v.sort(); v.dedup();
+            v.len()
+        };
+        let mut iter = cloned(&it).unique();
+        let first_count = (&mut iter).take(take_first as usize).count();
+        let rest_count = iter.count();
+        assert_eq!(answer, first_count + rest_count);
+    }
+}
+
+quickcheck! {
+    fn fuzz_chunk_by_lazy_1(it: Iter<u8>) -> bool {
+        let jt = it.clone();
+        let chunks = it.chunk_by(|k| *k);
+        itertools::equal(jt, chunks.into_iter().flat_map(|(_, x)| x))
+    }
+}
+
+quickcheck! {
+    fn fuzz_chunk_by_lazy_2(data: Vec<u8>) -> bool {
+        let chunks = data.iter().chunk_by(|k| *k / 10);
+        let res = itertools::equal(data.iter(), chunks.into_iter().flat_map(|(_, x)| x));
+        res
+    }
+}
+
+quickcheck! {
+    fn fuzz_chunk_by_lazy_3(data: Vec<u8>) -> bool {
+        let grouper = data.iter().chunk_by(|k| *k / 10);
+        let chunks = grouper.into_iter().collect_vec();
+        let res = itertools::equal(data.iter(), chunks.into_iter().flat_map(|(_, x)| x));
+        res
+    }
+}
+
+quickcheck! {
+    fn fuzz_chunk_by_lazy_duo(data: Vec<u8>, order: Vec<(bool, bool)>) -> bool {
+        let grouper = data.iter().chunk_by(|k| *k / 3);
+        let mut chunks1 = grouper.into_iter();
+        let mut chunks2 = grouper.into_iter();
+        let mut elts = Vec::<&u8>::new();
+        let mut old_chunks = Vec::new();
+
+        let tup1 = |(_, b)| b;
+        for &(ord, consume_now) in &order {
+            let iter = &mut [&mut chunks1, &mut chunks2][ord as usize];
+            match iter.next() {
+                Some((_, gr)) => if consume_now {
+                    for og in old_chunks.drain(..) {
+                        elts.extend(og);
+                    }
+                    elts.extend(gr);
+                } else {
+                    old_chunks.push(gr);
+                },
+                None => break,
+            }
+        }
+        for og in old_chunks.drain(..) {
+            elts.extend(og);
+        }
+        for gr in chunks1.map(&tup1) { elts.extend(gr); }
+        for gr in chunks2.map(&tup1) { elts.extend(gr); }
+        itertools::assert_equal(&data, elts);
+        true
+    }
+}
+
+quickcheck! {
+    fn chunk_clone_equal(a: Vec<u8>, size: u8) -> () {
+        let mut size = size;
+        if size == 0 {
+            size += 1;
+        }
+        let it = a.chunks(size as usize);
+        itertools::assert_equal(it.clone(), it);
+    }
+}
+
+quickcheck! {
+    fn equal_chunks_lazy(a: Vec<u8>, size: u8) -> bool {
+        let mut size = size;
+        if size == 0 {
+            size += 1;
+        }
+        let chunks = a.iter().chunks(size as usize);
+        let it = a.chunks(size as usize);
+        for (a, b) in chunks.into_iter().zip(it) {
+            if !itertools::equal(a, b) {
+                return false;
+            }
+        }
+        true
+    }
+}
+
+// tuple iterators
+quickcheck! {
+    fn equal_circular_tuple_windows_1(a: Vec<u8>) -> bool {
+        let x = a.iter().map(|e| (e,) );
+        let y = a.iter().circular_tuple_windows::<(_,)>();
+        itertools::assert_equal(x,y);
+        true
+    }
+
+    fn equal_circular_tuple_windows_2(a: Vec<u8>) -> bool {
+        let x = (0..a.len()).map(|start_idx| (
+            &a[start_idx],
+            &a[(start_idx + 1) % a.len()],
+        ));
+        let y = a.iter().circular_tuple_windows::<(_, _)>();
+        itertools::assert_equal(x,y);
+        true
+    }
+
+    fn equal_circular_tuple_windows_3(a: Vec<u8>) -> bool {
+        let x = (0..a.len()).map(|start_idx| (
+            &a[start_idx],
+            &a[(start_idx + 1) % a.len()],
+            &a[(start_idx + 2) % a.len()],
+        ));
+        let y = a.iter().circular_tuple_windows::<(_, _, _)>();
+        itertools::assert_equal(x,y);
+        true
+    }
+
+    fn equal_circular_tuple_windows_4(a: Vec<u8>) -> bool {
+        let x = (0..a.len()).map(|start_idx| (
+            &a[start_idx],
+            &a[(start_idx + 1) % a.len()],
+            &a[(start_idx + 2) % a.len()],
+            &a[(start_idx + 3) % a.len()],
+        ));
+        let y = a.iter().circular_tuple_windows::<(_, _, _, _)>();
+        itertools::assert_equal(x,y);
+        true
+    }
+
+    fn equal_cloned_circular_tuple_windows(a: Vec<u8>) -> bool {
+        let x = a.iter().circular_tuple_windows::<(_, _, _, _)>();
+        let y = x.clone();
+        itertools::assert_equal(x,y);
+        true
+    }
+
+    fn equal_cloned_circular_tuple_windows_noninitial(a: Vec<u8>) -> bool {
+        let mut x = a.iter().circular_tuple_windows::<(_, _, _, _)>();
+        let _ = x.next();
+        let y = x.clone();
+        itertools::assert_equal(x,y);
+        true
+    }
+
+    fn equal_cloned_circular_tuple_windows_complete(a: Vec<u8>) -> bool {
+        let mut x = a.iter().circular_tuple_windows::<(_, _, _, _)>();
+        for _ in x.by_ref() {}
+        let y = x.clone();
+        itertools::assert_equal(x,y);
+        true
+    }
+
+    fn circular_tuple_windows_exact_size(a: Vec<u8>) -> bool {
+        exact_size(a.iter().circular_tuple_windows::<(_, _, _, _)>())
+    }
+
+    fn equal_tuple_windows_1(a: Vec<u8>) -> bool {
+        let x = a.windows(1).map(|s| (&s[0], ));
+        let y = a.iter().tuple_windows::<(_,)>();
+        itertools::equal(x, y)
+    }
+
+    fn equal_tuple_windows_2(a: Vec<u8>) -> bool {
+        let x = a.windows(2).map(|s| (&s[0], &s[1]));
+        let y = a.iter().tuple_windows::<(_, _)>();
+        itertools::equal(x, y)
+    }
+
+    fn equal_tuple_windows_3(a: Vec<u8>) -> bool {
+        let x = a.windows(3).map(|s| (&s[0], &s[1], &s[2]));
+        let y = a.iter().tuple_windows::<(_, _, _)>();
+        itertools::equal(x, y)
+    }
+
+    fn equal_tuple_windows_4(a: Vec<u8>) -> bool {
+        let x = a.windows(4).map(|s| (&s[0], &s[1], &s[2], &s[3]));
+        let y = a.iter().tuple_windows::<(_, _, _, _)>();
+        itertools::equal(x, y)
+    }
+
+    fn tuple_windows_exact_size_1(a: Vec<u8>) -> bool {
+        exact_size(a.iter().tuple_windows::<(_,)>())
+    }
+
+    fn tuple_windows_exact_size_4(a: Vec<u8>) -> bool {
+        exact_size(a.iter().tuple_windows::<(_, _, _, _)>())
+    }
+
+    fn equal_tuples_1(a: Vec<u8>) -> bool {
+        let x = a.chunks(1).map(|s| (&s[0], ));
+        let y = a.iter().tuples::<(_,)>();
+        itertools::equal(x, y)
+    }
+
+    fn equal_tuples_2(a: Vec<u8>) -> bool {
+        let x = a.chunks(2).filter(|s| s.len() == 2).map(|s| (&s[0], &s[1]));
+        let y = a.iter().tuples::<(_, _)>();
+        itertools::equal(x, y)
+    }
+
+    fn equal_tuples_3(a: Vec<u8>) -> bool {
+        let x = a.chunks(3).filter(|s| s.len() == 3).map(|s| (&s[0], &s[1], &s[2]));
+        let y = a.iter().tuples::<(_, _, _)>();
+        itertools::equal(x, y)
+    }
+
+    fn equal_tuples_4(a: Vec<u8>) -> bool {
+        let x = a.chunks(4).filter(|s| s.len() == 4).map(|s| (&s[0], &s[1], &s[2], &s[3]));
+        let y = a.iter().tuples::<(_, _, _, _)>();
+        itertools::equal(x, y)
+    }
+
+    fn exact_tuple_buffer(a: Vec<u8>) -> bool {
+        let mut iter = a.iter().tuples::<(_, _, _, _)>();
+        (&mut iter).last();
+        let buffer = iter.into_buffer();
+        assert_eq!(buffer.len(), a.len() % 4);
+        exact_size(buffer)
+    }
+
+    fn tuples_size_hint_inexact(a: Iter<u8>) -> bool {
+        correct_size_hint(a.clone().tuples::<(_,)>())
+            && correct_size_hint(a.clone().tuples::<(_, _)>())
+            && correct_size_hint(a.tuples::<(_, _, _, _)>())
+    }
+
+    fn tuples_size_hint_exact(a: Iter<u8, Exact>) -> bool {
+        exact_size(a.clone().tuples::<(_,)>())
+            && exact_size(a.clone().tuples::<(_, _)>())
+            && exact_size(a.tuples::<(_, _, _, _)>())
+    }
+}
+
+// with_position
+quickcheck! {
+    fn with_position_exact_size_1(a: Vec<u8>) -> bool {
+        exact_size_for_this(a.iter().with_position())
+    }
+    fn with_position_exact_size_2(a: Iter<u8, Exact>) -> bool {
+        exact_size_for_this(a.with_position())
+    }
+}
+
+quickcheck! {
+    fn correct_group_map_modulo_key(a: Vec<u8>, modulo: u8) -> () {
+        let modulo = if modulo == 0 { 1 } else { modulo }; // Avoid `% 0`
+        let count = a.len();
+        let lookup = a.into_iter().map(|i| (i % modulo, i)).into_group_map();
+
+        assert_eq!(lookup.values().flat_map(|vals| vals.iter()).count(), count);
+
+        for (&key, vals) in lookup.iter() {
+            assert!(vals.iter().all(|&val| val % modulo == key));
+        }
+    }
+}
+
+/// A peculiar type: Equality compares both tuple items, but ordering only the
+/// first item.  This is so we can check the stability property easily.
+#[derive(Clone, Debug, PartialEq, Eq)]
+struct Val(u32, u32);
+
+impl PartialOrd<Self> for Val {
+    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
+        Some(self.cmp(other))
+    }
+}
+
+impl Ord for Val {
+    fn cmp(&self, other: &Self) -> Ordering {
+        self.0.cmp(&other.0)
+    }
+}
+
+impl qc::Arbitrary for Val {
+    fn arbitrary<G: qc::Gen>(g: &mut G) -> Self {
+        let (x, y) = <(u32, u32)>::arbitrary(g);
+        Self(x, y)
+    }
+    fn shrink(&self) -> Box<dyn Iterator<Item = Self>> {
+        Box::new((self.0, self.1).shrink().map(|(x, y)| Self(x, y)))
+    }
+}
+
+quickcheck! {
+    fn minmax(a: Vec<Val>) -> bool {
+        use itertools::MinMaxResult;
+
+
+        let minmax = a.iter().minmax();
+        let expected = match a.len() {
+            0 => MinMaxResult::NoElements,
+            1 => MinMaxResult::OneElement(&a[0]),
+            _ => MinMaxResult::MinMax(a.iter().min().unwrap(),
+                                      a.iter().max().unwrap()),
+        };
+        minmax == expected
+    }
+}
+
+quickcheck! {
+    fn minmax_f64(a: Vec<f64>) -> TestResult {
+        use itertools::MinMaxResult;
+
+        if a.iter().any(|x| x.is_nan()) {
+            return TestResult::discard();
+        }
+
+        let min = cloned(&a).fold1(f64::min);
+        let max = cloned(&a).fold1(f64::max);
+
+        let minmax = cloned(&a).minmax();
+        let expected = match a.len() {
+            0 => MinMaxResult::NoElements,
+            1 => MinMaxResult::OneElement(min.unwrap()),
+            _ => MinMaxResult::MinMax(min.unwrap(), max.unwrap()),
+        };
+        TestResult::from_bool(minmax == expected)
+    }
+}
+
+quickcheck! {
+    fn tree_reduce_f64(mut a: Vec<f64>) -> TestResult {
+        fn collapse_adjacent<F>(x: Vec<f64>, mut f: F) -> Vec<f64>
+            where F: FnMut(f64, f64) -> f64
+        {
+            let mut out = Vec::new();
+            for i in (0..x.len()).step_by(2) {
+                if i == x.len()-1 {
+                    out.push(x[i])
+                } else {
+                    out.push(f(x[i], x[i+1]));
+                }
+            }
+            out
+        }
+
+        if a.iter().any(|x| x.is_nan()) {
+            return TestResult::discard();
+        }
+
+        let actual = a.iter().cloned().tree_reduce(f64::atan2);
+
+        while a.len() > 1 {
+            a = collapse_adjacent(a, f64::atan2);
+        }
+        let expected = a.pop();
+
+        TestResult::from_bool(actual == expected)
+    }
+}
+
+quickcheck! {
+    fn exactly_one_i32(a: Vec<i32>) -> TestResult {
+        let ret = a.iter().cloned().exactly_one();
+        match a.len() {
+            1 => TestResult::from_bool(ret.unwrap() == a[0]),
+            _ => TestResult::from_bool(ret.unwrap_err().eq(a.iter().cloned())),
+        }
+    }
+}
+
+quickcheck! {
+    fn at_most_one_i32(a: Vec<i32>) -> TestResult {
+        let ret = a.iter().cloned().at_most_one();
+        match a.len() {
+            0 => TestResult::from_bool(ret.unwrap().is_none()),
+            1 => TestResult::from_bool(ret.unwrap() == Some(a[0])),
+            _ => TestResult::from_bool(ret.unwrap_err().eq(a.iter().cloned())),
+        }
+    }
+}
+
+quickcheck! {
+    fn consistent_grouping_map_with_by(a: Vec<u8>, modulo: u8) -> () {
+        let modulo = if modulo == 0 { 1 } else { modulo }; // Avoid `% 0`
+
+        let lookup_grouping_map = a.iter().copied().map(|i| (i % modulo, i)).into_grouping_map().collect::<Vec<_>>();
+        let lookup_grouping_map_by = a.iter().copied().into_grouping_map_by(|i| i % modulo).collect::<Vec<_>>();
+
+        assert_eq!(lookup_grouping_map, lookup_grouping_map_by);
+    }
+
+    fn correct_grouping_map_by_aggregate_modulo_key(a: Vec<u8>, modulo: u8) -> () {
+        let modulo = if modulo < 2 { 2 } else { modulo } as u64; // Avoid `% 0`
+        let lookup = a.iter()
+            .map(|&b| b as u64) // Avoid overflows
+            .into_grouping_map_by(|i| i % modulo)
+            .aggregate(|acc, &key, val| {
+                assert!(val % modulo == key);
+                if val % (modulo - 1) == 0 {
+                    None
+                } else {
+                    Some(acc.unwrap_or(0) + val)
+                }
+            });
+
+        let group_map_lookup = a.iter()
+            .map(|&b| b as u64)
+            .map(|i| (i % modulo, i))
+            .into_group_map()
+            .into_iter()
+            .filter_map(|(key, vals)| {
+                vals.into_iter().fold(None, |acc, val| {
+                    if val % (modulo - 1) == 0 {
+                        None
+                    } else {
+                        Some(acc.unwrap_or(0) + val)
+                    }
+                }).map(|new_val| (key, new_val))
+            })
+            .collect::<HashMap<_,_>>();
+        assert_eq!(lookup, group_map_lookup);
+
+        for m in 0..modulo {
+            assert_eq!(
+                lookup.get(&m).copied(),
+                a.iter()
+                    .map(|&b| b as u64)
+                    .filter(|&val| val % modulo == m)
+                    .fold(None, |acc, val| {
+                        if val % (modulo - 1) == 0 {
+                            None
+                        } else {
+                            Some(acc.unwrap_or(0) + val)
+                        }
+                    })
+            );
+        }
+    }
+
+    fn correct_grouping_map_by_fold_with_modulo_key(a: Vec<u8>, modulo: u8) -> () {
+        #[derive(Debug, Default, PartialEq)]
+        struct Accumulator {
+            acc: u64,
+        }
+
+        let modulo = if modulo == 0 { 1 } else { modulo } as u64; // Avoid `% 0`
+        let lookup = a.iter().map(|&b| b as u64) // Avoid overflows
+            .into_grouping_map_by(|i| i % modulo)
+            .fold_with(|_key, _val| Default::default(), |Accumulator { acc }, &key, val| {
+                assert!(val % modulo == key);
+                let acc = acc + val;
+                Accumulator { acc }
+            });
+
+        let group_map_lookup = a.iter()
+            .map(|&b| b as u64)
+            .map(|i| (i % modulo, i))
+            .into_group_map()
+            .into_iter()
+            .map(|(key, vals)| (key, vals.into_iter().sum())).map(|(key, acc)| (key,Accumulator { acc }))
+            .collect::<HashMap<_,_>>();
+        assert_eq!(lookup, group_map_lookup);
+
+        for (&key, &Accumulator { acc: sum }) in lookup.iter() {
+            assert_eq!(sum, a.iter().map(|&b| b as u64).filter(|&val| val % modulo == key).sum::<u64>());
+        }
+    }
+
+    fn correct_grouping_map_by_fold_modulo_key(a: Vec<u8>, modulo: u8) -> () {
+        let modulo = if modulo == 0 { 1 } else { modulo } as u64; // Avoid `% 0`
+        let lookup = a.iter().map(|&b| b as u64) // Avoid overflows
+            .into_grouping_map_by(|i| i % modulo)
+            .fold(0u64, |acc, &key, val| {
+                assert!(val % modulo == key);
+                acc + val
+            });
+
+        let group_map_lookup = a.iter()
+            .map(|&b| b as u64)
+            .map(|i| (i % modulo, i))
+            .into_group_map()
+            .into_iter()
+            .map(|(key, vals)| (key, vals.into_iter().sum()))
+            .collect::<HashMap<_,_>>();
+        assert_eq!(lookup, group_map_lookup);
+
+        for (&key, &sum) in lookup.iter() {
+            assert_eq!(sum, a.iter().map(|&b| b as u64).filter(|&val| val % modulo == key).sum::<u64>());
+        }
+    }
+
+    fn correct_grouping_map_by_reduce_modulo_key(a: Vec<u8>, modulo: u8) -> () {
+        let modulo = if modulo == 0 { 1 } else { modulo } as u64; // Avoid `% 0`
+        let lookup = a.iter().map(|&b| b as u64) // Avoid overflows
+            .into_grouping_map_by(|i| i % modulo)
+            .reduce(|acc, &key, val| {
+                assert!(val % modulo == key);
+                acc + val
+            });
+
+        let group_map_lookup = a.iter()
+            .map(|&b| b as u64)
+            .map(|i| (i % modulo, i))
+            .into_group_map()
+            .into_iter()
+            .map(|(key, vals)| (key, vals.into_iter().reduce(|acc, val| acc + val).unwrap()))
+            .collect::<HashMap<_,_>>();
+        assert_eq!(lookup, group_map_lookup);
+
+        for (&key, &sum) in lookup.iter() {
+            assert_eq!(sum, a.iter().map(|&b| b as u64).filter(|&val| val % modulo == key).sum::<u64>());
+        }
+    }
+
+    fn correct_grouping_map_by_collect_modulo_key(a: Vec<u8>, modulo: u8) -> () {
+        let modulo = if modulo == 0 { 1 } else { modulo }; // Avoid `% 0`
+        let lookup_grouping_map = a.iter().copied().into_grouping_map_by(|i| i % modulo).collect::<Vec<_>>();
+        let lookup_group_map = a.iter().copied().map(|i| (i % modulo, i)).into_group_map();
+
+        assert_eq!(lookup_grouping_map, lookup_group_map);
+    }
+
+    fn correct_grouping_map_by_max_modulo_key(a: Vec<u8>, modulo: u8) -> () {
+        let modulo = if modulo == 0 { 1 } else { modulo }; // Avoid `% 0`
+        let lookup = a.iter().copied().into_grouping_map_by(|i| i % modulo).max();
+
+        let group_map_lookup = a.iter().copied()
+            .map(|i| (i % modulo, i))
+            .into_group_map()
+            .into_iter()
+            .map(|(key, vals)| (key, vals.into_iter().max().unwrap()))
+            .collect::<HashMap<_,_>>();
+        assert_eq!(lookup, group_map_lookup);
+
+        for (&key, &max) in lookup.iter() {
+            assert_eq!(Some(max), a.iter().copied().filter(|&val| val % modulo == key).max());
+        }
+    }
+
+    fn correct_grouping_map_by_max_by_modulo_key(a: Vec<u8>, modulo: u8) -> () {
+        let modulo = if modulo == 0 { 1 } else { modulo }; // Avoid `% 0`
+        let lookup = a.iter().copied().into_grouping_map_by(|i| i % modulo).max_by(|_, v1, v2| v1.cmp(v2));
+
+        let group_map_lookup = a.iter().copied()
+            .map(|i| (i % modulo, i))
+            .into_group_map()
+            .into_iter()
+            .map(|(key, vals)| (key, vals.into_iter().max_by(|v1, v2| v1.cmp(v2)).unwrap()))
+            .collect::<HashMap<_,_>>();
+        assert_eq!(lookup, group_map_lookup);
+
+        for (&key, &max) in lookup.iter() {
+            assert_eq!(Some(max), a.iter().copied().filter(|&val| val % modulo == key).max_by(|v1, v2| v1.cmp(v2)));
+        }
+    }
+
+    fn correct_grouping_map_by_max_by_key_modulo_key(a: Vec<u8>, modulo: u8) -> () {
+        let modulo = if modulo == 0 { 1 } else { modulo }; // Avoid `% 0`
+        let lookup = a.iter().copied().into_grouping_map_by(|i| i % modulo).max_by_key(|_, &val| val);
+
+        let group_map_lookup = a.iter().copied()
+            .map(|i| (i % modulo, i))
+            .into_group_map()
+            .into_iter()
+            .map(|(key, vals)| (key, vals.into_iter().max_by_key(|&val| val).unwrap()))
+            .collect::<HashMap<_,_>>();
+        assert_eq!(lookup, group_map_lookup);
+
+        for (&key, &max) in lookup.iter() {
+            assert_eq!(Some(max), a.iter().copied().filter(|&val| val % modulo == key).max_by_key(|&val| val));
+        }
+    }
+
+    fn correct_grouping_map_by_min_modulo_key(a: Vec<u8>, modulo: u8) -> () {
+        let modulo = if modulo == 0 { 1 } else { modulo }; // Avoid `% 0`
+        let lookup = a.iter().copied().into_grouping_map_by(|i| i % modulo).min();
+
+        let group_map_lookup = a.iter().copied()
+            .map(|i| (i % modulo, i))
+            .into_group_map()
+            .into_iter()
+            .map(|(key, vals)| (key, vals.into_iter().min().unwrap()))
+            .collect::<HashMap<_,_>>();
+        assert_eq!(lookup, group_map_lookup);
+
+        for (&key, &min) in lookup.iter() {
+            assert_eq!(Some(min), a.iter().copied().filter(|&val| val % modulo == key).min());
+        }
+    }
+
+    fn correct_grouping_map_by_min_by_modulo_key(a: Vec<u8>, modulo: u8) -> () {
+        let modulo = if modulo == 0 { 1 } else { modulo }; // Avoid `% 0`
+        let lookup = a.iter().copied().into_grouping_map_by(|i| i % modulo).min_by(|_, v1, v2| v1.cmp(v2));
+
+        let group_map_lookup = a.iter().copied()
+            .map(|i| (i % modulo, i))
+            .into_group_map()
+            .into_iter()
+            .map(|(key, vals)| (key, vals.into_iter().min_by(|v1, v2| v1.cmp(v2)).unwrap()))
+            .collect::<HashMap<_,_>>();
+        assert_eq!(lookup, group_map_lookup);
+
+        for (&key, &min) in lookup.iter() {
+            assert_eq!(Some(min), a.iter().copied().filter(|&val| val % modulo == key).min_by(|v1, v2| v1.cmp(v2)));
+        }
+    }
+
+    fn correct_grouping_map_by_min_by_key_modulo_key(a: Vec<u8>, modulo: u8) -> () {
+        let modulo = if modulo == 0 { 1 } else { modulo }; // Avoid `% 0`
+        let lookup = a.iter().copied().into_grouping_map_by(|i| i % modulo).min_by_key(|_, &val| val);
+
+        let group_map_lookup = a.iter().copied()
+            .map(|i| (i % modulo, i))
+            .into_group_map()
+            .into_iter()
+            .map(|(key, vals)| (key, vals.into_iter().min_by_key(|&val| val).unwrap()))
+            .collect::<HashMap<_,_>>();
+        assert_eq!(lookup, group_map_lookup);
+
+        for (&key, &min) in lookup.iter() {
+            assert_eq!(Some(min), a.iter().copied().filter(|&val| val % modulo == key).min_by_key(|&val| val));
+        }
+    }
+
+    fn correct_grouping_map_by_minmax_modulo_key(a: Vec<u8>, modulo: u8) -> () {
+        let modulo = if modulo == 0 { 1 } else { modulo }; // Avoid `% 0`
+        let lookup = a.iter().copied().into_grouping_map_by(|i| i % modulo).minmax();
+
+        let group_map_lookup = a.iter().copied()
+            .map(|i| (i % modulo, i))
+            .into_group_map()
+            .into_iter()
+            .map(|(key, vals)| (key, vals.into_iter().minmax()))
+            .collect::<HashMap<_,_>>();
+        assert_eq!(lookup, group_map_lookup);
+
+        for (&key, &minmax) in lookup.iter() {
+            assert_eq!(minmax, a.iter().copied().filter(|&val| val % modulo == key).minmax());
+        }
+    }
+
+    fn correct_grouping_map_by_minmax_by_modulo_key(a: Vec<u8>, modulo: u8) -> () {
+        let modulo = if modulo == 0 { 1 } else { modulo }; // Avoid `% 0`
+        let lookup = a.iter().copied().into_grouping_map_by(|i| i % modulo).minmax_by(|_, v1, v2| v1.cmp(v2));
+
+        let group_map_lookup = a.iter().copied()
+            .map(|i| (i % modulo, i))
+            .into_group_map()
+            .into_iter()
+            .map(|(key, vals)| (key, vals.into_iter().minmax_by(|v1, v2| v1.cmp(v2))))
+            .collect::<HashMap<_,_>>();
+        assert_eq!(lookup, group_map_lookup);
+
+        for (&key, &minmax) in lookup.iter() {
+            assert_eq!(minmax, a.iter().copied().filter(|&val| val % modulo == key).minmax_by(|v1, v2| v1.cmp(v2)));
+        }
+    }
+
+    fn correct_grouping_map_by_minmax_by_key_modulo_key(a: Vec<u8>, modulo: u8) -> () {
+        let modulo = if modulo == 0 { 1 } else { modulo }; // Avoid `% 0`
+        let lookup = a.iter().copied().into_grouping_map_by(|i| i % modulo).minmax_by_key(|_, &val| val);
+
+        let group_map_lookup = a.iter().copied()
+            .map(|i| (i % modulo, i))
+            .into_group_map()
+            .into_iter()
+            .map(|(key, vals)| (key, vals.into_iter().minmax_by_key(|&val| val)))
+            .collect::<HashMap<_,_>>();
+        assert_eq!(lookup, group_map_lookup);
+
+        for (&key, &minmax) in lookup.iter() {
+            assert_eq!(minmax, a.iter().copied().filter(|&val| val % modulo == key).minmax_by_key(|&val| val));
+        }
+    }
+
+    fn correct_grouping_map_by_sum_modulo_key(a: Vec<u8>, modulo: u8) -> () {
+        let modulo = if modulo == 0 { 1 } else { modulo } as u64; // Avoid `% 0`
+        let lookup = a.iter().map(|&b| b as u64) // Avoid overflows
+            .into_grouping_map_by(|i| i % modulo)
+            .sum();
+
+        let group_map_lookup = a.iter().map(|&b| b as u64)
+            .map(|i| (i % modulo, i))
+            .into_group_map()
+            .into_iter()
+            .map(|(key, vals)| (key, vals.into_iter().sum()))
+            .collect::<HashMap<_,_>>();
+        assert_eq!(lookup, group_map_lookup);
+
+        for (&key, &sum) in lookup.iter() {
+            assert_eq!(sum, a.iter().map(|&b| b as u64).filter(|&val| val % modulo == key).sum::<u64>());
+        }
+    }
+
+    fn correct_grouping_map_by_product_modulo_key(a: Vec<u8>, modulo: u8) -> () {
+        let modulo = Wrapping(if modulo == 0 { 1 } else { modulo } as u64); // Avoid `% 0`
+        let lookup = a.iter().map(|&b| Wrapping(b as u64)) // Avoid overflows
+            .into_grouping_map_by(|i| i % modulo)
+            .product();
+
+        let group_map_lookup = a.iter().map(|&b| Wrapping(b as u64))
+            .map(|i| (i % modulo, i))
+            .into_group_map()
+            .into_iter()
+            .map(|(key, vals)| (key, vals.into_iter().product::<Wrapping<u64>>()))
+            .collect::<HashMap<_,_>>();
+        assert_eq!(lookup, group_map_lookup);
+
+        for (&key, &prod) in lookup.iter() {
+            assert_eq!(
+                prod,
+                a.iter()
+                    .map(|&b| Wrapping(b as u64))
+                    .filter(|&val| val % modulo == key)
+                    .product::<Wrapping<u64>>()
+            );
+        }
+    }
+
+    // This should check that if multiple elements are equally minimum or maximum
+    // then `max`, `min` and `minmax` pick the first minimum and the last maximum.
+    // This is to be consistent with `std::iter::max` and `std::iter::min`.
+    fn correct_grouping_map_by_min_max_minmax_order_modulo_key() -> () {
+        use itertools::MinMaxResult;
+
+        let lookup = (0..=10)
+            .into_grouping_map_by(|_| 0)
+            .max_by(|_, _, _| Ordering::Equal);
+
+        assert_eq!(lookup[&0], 10);
+
+        let lookup = (0..=10)
+            .into_grouping_map_by(|_| 0)
+            .min_by(|_, _, _| Ordering::Equal);
+
+        assert_eq!(lookup[&0], 0);
+
+        let lookup = (0..=10)
+            .into_grouping_map_by(|_| 0)
+            .minmax_by(|_, _, _| Ordering::Equal);
+
+        assert_eq!(lookup[&0], MinMaxResult::MinMax(0, 10));
+    }
+}
+
+quickcheck! {
+    fn counts(nums: Vec<isize>) -> TestResult {
+        let counts = nums.iter().counts();
+        for (&item, &count) in counts.iter() {
+            #[allow(clippy::absurd_extreme_comparisons)]
+            if count <= 0 {
+                return TestResult::failed();
+            }
+            if count != nums.iter().filter(|&x| x == item).count() {
+                return TestResult::failed();
+            }
+        }
+        for item in nums.iter() {
+            if !counts.contains_key(item) {
+                return TestResult::failed();
+            }
+        }
+        TestResult::passed()
+    }
+}
+
+quickcheck! {
+    fn test_double_ended_zip_2(a: Vec<u8>, b: Vec<u8>) -> TestResult {
+        let mut x =
+          multizip((a.clone().into_iter(), b.clone().into_iter()))
+            .collect_vec();
+        x.reverse();
+
+        let y =
+          multizip((a.into_iter(), b.into_iter()))
+          .rfold(Vec::new(), |mut vec, e| { vec.push(e); vec });
+
+        TestResult::from_bool(itertools::equal(x, y))
+    }
+
+    fn test_double_ended_zip_3(a: Vec<u8>, b: Vec<u8>, c: Vec<u8>) -> TestResult {
+        let mut x =
+          multizip((a.clone().into_iter(), b.clone().into_iter(), c.clone().into_iter()))
+            .collect_vec();
+        x.reverse();
+
+        let y =
+          multizip((a.into_iter(), b.into_iter(), c.into_iter()))
+          .rfold(Vec::new(), |mut vec, e| { vec.push(e); vec });
+
+        TestResult::from_bool(itertools::equal(x, y))
+    }
+}
+
+fn is_fused<I: Iterator>(mut it: I) -> bool {
+    for _ in it.by_ref() {}
+    for _ in 0..10 {
+        if it.next().is_some() {
+            return false;
+        }
+    }
+    true
+}
+
+quickcheck! {
+    fn fused_combination(a: Iter<i16>) -> bool
+    {
+        is_fused(a.clone().combinations(1)) &&
+        is_fused(a.combinations(3))
+    }
+
+    fn fused_combination_with_replacement(a: Iter<i16>) -> bool
+    {
+        is_fused(a.clone().combinations_with_replacement(1)) &&
+        is_fused(a.combinations_with_replacement(3))
+    }
+
+    fn fused_tuple_combination(a: Iter<i16>) -> bool
+    {
+        is_fused(a.clone().fuse().tuple_combinations::<(_,)>()) &&
+        is_fused(a.fuse().tuple_combinations::<(_,_,_)>())
+    }
+
+    fn fused_unique(a: Iter<i16>) -> bool
+    {
+        is_fused(a.fuse().unique())
+    }
+
+    fn fused_unique_by(a: Iter<i16>) -> bool
+    {
+        is_fused(a.fuse().unique_by(|x| x % 100))
+    }
+
+    fn fused_interleave_shortest(a: Iter<i16>, b: Iter<i16>) -> bool
+    {
+        !is_fused(a.clone().interleave_shortest(b.clone())) &&
+        is_fused(a.fuse().interleave_shortest(b.fuse()))
+    }
+
+    fn fused_product(a: Iter<i16>, b: Iter<i16>) -> bool
+    {
+        is_fused(a.fuse().cartesian_product(b.fuse()))
+    }
+
+    fn fused_merge(a: Iter<i16>, b: Iter<i16>) -> bool
+    {
+        is_fused(a.fuse().merge(b.fuse()))
+    }
+
+    fn fused_filter_ok(a: Iter<i16>) -> bool
+    {
+        is_fused(a.map(|x| if x % 2 == 0 {Ok(x)} else {Err(x)} )
+                 .filter_ok(|x| x % 3 == 0)
+                 .fuse())
+    }
+
+    fn fused_filter_map_ok(a: Iter<i16>) -> bool
+    {
+        is_fused(a.map(|x| if x % 2 == 0 {Ok(x)} else {Err(x)} )
+                 .filter_map_ok(|x| if x % 3 == 0 {Some(x / 3)} else {None})
+                 .fuse())
+    }
+
+    fn fused_positions(a: Iter<i16>) -> bool
+    {
+        !is_fused(a.clone().positions(|x|x%2==0)) &&
+        is_fused(a.fuse().positions(|x|x%2==0))
+    }
+
+    fn fused_update(a: Iter<i16>) -> bool
+    {
+        !is_fused(a.clone().update(|x|*x+=1)) &&
+        is_fused(a.fuse().update(|x|*x+=1))
+    }
+
+    fn fused_tuple_windows(a: Iter<i16>) -> bool
+    {
+        is_fused(a.fuse().tuple_windows::<(_,_)>())
+    }
+
+    fn fused_pad_using(a: Iter<i16>) -> bool
+    {
+        is_fused(a.fuse().pad_using(100,|_|0))
+    }
+}
+
+quickcheck! {
+    fn min_set_contains_min(a: Vec<(usize, char)>) -> bool {
+        let result_set = a.iter().min_set();
+        if let Some(result_element) = a.iter().min() {
+            result_set.contains(&result_element)
+        } else {
+            result_set.is_empty()
+        }
+    }
+
+    fn min_set_by_contains_min(a: Vec<(usize, char)>) -> bool {
+        let compare = |x: &&(usize, char), y: &&(usize, char)| x.1.cmp(&y.1);
+        let result_set = a.iter().min_set_by(compare);
+        if let Some(result_element) = a.iter().min_by(compare) {
+            result_set.contains(&result_element)
+        } else {
+            result_set.is_empty()
+        }
+    }
+
+    fn min_set_by_key_contains_min(a: Vec<(usize, char)>) -> bool {
+        let key = |x: &&(usize, char)| x.1;
+        let result_set = a.iter().min_set_by_key(&key);
+        if let Some(result_element) = a.iter().min_by_key(&key) {
+            result_set.contains(&result_element)
+        } else {
+            result_set.is_empty()
+        }
+    }
+
+    fn max_set_contains_max(a: Vec<(usize, char)>) -> bool {
+        let result_set = a.iter().max_set();
+        if let Some(result_element) = a.iter().max() {
+            result_set.contains(&result_element)
+        } else {
+            result_set.is_empty()
+        }
+    }
+
+    fn max_set_by_contains_max(a: Vec<(usize, char)>) -> bool {
+        let compare = |x: &&(usize, char), y: &&(usize, char)| x.1.cmp(&y.1);
+        let result_set = a.iter().max_set_by(compare);
+        if let Some(result_element) = a.iter().max_by(compare) {
+            result_set.contains(&result_element)
+        } else {
+            result_set.is_empty()
+        }
+    }
+
+    fn max_set_by_key_contains_max(a: Vec<(usize, char)>) -> bool {
+        let key = |x: &&(usize, char)| x.1;
+        let result_set = a.iter().max_set_by_key(&key);
+        if let Some(result_element) = a.iter().max_by_key(&key) {
+            result_set.contains(&result_element)
+        } else {
+            result_set.is_empty()
+        }
+    }
+
+    fn tail(v: Vec<i32>, n: u8) -> bool {
+        let n = n as usize;
+        let result = &v[v.len().saturating_sub(n)..];
+        itertools::equal(v.iter().tail(n), result)
+            && itertools::equal(v.iter().filter(|_| true).tail(n), result)
+    }
+}
diff --git a/vendor/itertools/tests/specializations.rs b/vendor/itertools/tests/specializations.rs
new file mode 100644
index 00000000..e6694c8e
--- /dev/null
+++ b/vendor/itertools/tests/specializations.rs
@@ -0,0 +1,603 @@
+//! Test specializations of methods with default impls match the behavior of the
+//! default impls.
+//!
+//! **NOTE:** Due to performance limitations, these tests are not run with miri!
+//! They cannot be relied upon to discover soundness issues.
+
+#![cfg(not(miri))]
+#![allow(unstable_name_collisions)]
+
+use itertools::Itertools;
+use quickcheck::Arbitrary;
+use quickcheck::{quickcheck, TestResult};
+use rand::Rng;
+use std::fmt::Debug;
+
+struct Unspecialized<I>(I);
+
+impl<I> Iterator for Unspecialized<I>
+where
+    I: Iterator,
+{
+    type Item = I::Item;
+
+    #[inline(always)]
+    fn next(&mut self) -> Option<Self::Item> {
+        self.0.next()
+    }
+}
+
+impl<I> DoubleEndedIterator for Unspecialized<I>
+where
+    I: DoubleEndedIterator,
+{
+    #[inline(always)]
+    fn next_back(&mut self) -> Option<Self::Item> {
+        self.0.next_back()
+    }
+}
+
+fn test_specializations<I>(it: &I)
+where
+    I::Item: Eq + Debug + Clone,
+    I: Iterator + Clone,
+{
+    macro_rules! check_specialized {
+        ($src:expr, |$it:pat| $closure:expr) => {
+            // Many iterators special-case the first elements, so we test specializations for iterators that have already been advanced.
+            let mut src = $src.clone();
+            for _ in 0..5 {
+                let $it = src.clone();
+                let v1 = $closure;
+                let $it = Unspecialized(src.clone());
+                let v2 = $closure;
+                assert_eq!(v1, v2);
+                src.next();
+            }
+        }
+    }
+    check_specialized!(it, |i| i.count());
+    check_specialized!(it, |i| i.last());
+    check_specialized!(it, |i| i.collect::<Vec<_>>());
+    check_specialized!(it, |i| {
+        let mut parameters_from_fold = vec![];
+        let fold_result = i.fold(vec![], |mut acc, v: I::Item| {
+            parameters_from_fold.push((acc.clone(), v.clone()));
+            acc.push(v);
+            acc
+        });
+        (parameters_from_fold, fold_result)
+    });
+    check_specialized!(it, |mut i| {
+        let mut parameters_from_all = vec![];
+        let first = i.next();
+        let all_result = i.all(|x| {
+            parameters_from_all.push(x.clone());
+            Some(x) == first
+        });
+        (parameters_from_all, all_result)
+    });
+    let size = it.clone().count();
+    for n in 0..size + 2 {
+        check_specialized!(it, |mut i| i.nth(n));
+    }
+    // size_hint is a bit harder to check
+    let mut it_sh = it.clone();
+    for n in 0..size + 2 {
+        let len = it_sh.clone().count();
+        let (min, max) = it_sh.size_hint();
+        assert_eq!(size - n.min(size), len);
+        assert!(min <= len);
+        if let Some(max) = max {
+            assert!(len <= max);
+        }
+        it_sh.next();
+    }
+}
+
+fn test_double_ended_specializations<I>(it: &I)
+where
+    I::Item: Eq + Debug + Clone,
+    I: DoubleEndedIterator + Clone,
+{
+    macro_rules! check_specialized {
+        ($src:expr, |$it:pat| $closure:expr) => {
+            // Many iterators special-case the first elements, so we test specializations for iterators that have already been advanced.
+            let mut src = $src.clone();
+            for step in 0..8 {
+                let $it = src.clone();
+                let v1 = $closure;
+                let $it = Unspecialized(src.clone());
+                let v2 = $closure;
+                assert_eq!(v1, v2);
+                if step % 2 == 0 {
+                    src.next();
+                } else {
+                    src.next_back();
+                }
+            }
+        }
+    }
+    check_specialized!(it, |i| {
+        let mut parameters_from_rfold = vec![];
+        let rfold_result = i.rfold(vec![], |mut acc, v: I::Item| {
+            parameters_from_rfold.push((acc.clone(), v.clone()));
+            acc.push(v);
+            acc
+        });
+        (parameters_from_rfold, rfold_result)
+    });
+    let size = it.clone().count();
+    for n in 0..size + 2 {
+        check_specialized!(it, |mut i| i.nth_back(n));
+    }
+}
+
+quickcheck! {
+    fn interleave(v: Vec<u8>, w: Vec<u8>) -> () {
+        test_specializations(&v.iter().interleave(w.iter()));
+    }
+
+    fn interleave_shortest(v: Vec<u8>, w: Vec<u8>) -> () {
+        test_specializations(&v.iter().interleave_shortest(w.iter()));
+    }
+
+    fn batching(v: Vec<u8>) -> () {
+        test_specializations(&v.iter().batching(Iterator::next));
+    }
+
+    fn tuple_windows(v: Vec<u8>) -> () {
+        test_specializations(&v.iter().tuple_windows::<(_,)>());
+        test_specializations(&v.iter().tuple_windows::<(_, _)>());
+        test_specializations(&v.iter().tuple_windows::<(_, _, _)>());
+    }
+
+    fn circular_tuple_windows(v: Vec<u8>) -> () {
+        test_specializations(&v.iter().circular_tuple_windows::<(_,)>());
+        test_specializations(&v.iter().circular_tuple_windows::<(_, _)>());
+        test_specializations(&v.iter().circular_tuple_windows::<(_, _, _)>());
+    }
+
+    fn tuples(v: Vec<u8>) -> () {
+        test_specializations(&v.iter().tuples::<(_,)>());
+        test_specializations(&v.iter().tuples::<(_, _)>());
+        test_specializations(&v.iter().tuples::<(_, _, _)>());
+    }
+
+    fn cartesian_product(a: Vec<u8>, b: Vec<u8>) -> TestResult {
+        if a.len() * b.len() > 100 {
+            return TestResult::discard();
+        }
+        test_specializations(&a.iter().cartesian_product(&b));
+        TestResult::passed()
+    }
+
+    fn multi_cartesian_product(a: Vec<u8>, b: Vec<u8>, c: Vec<u8>) -> TestResult {
+        if a.len() * b.len() * c.len() > 100 {
+            return TestResult::discard();
+        }
+        test_specializations(&vec![a, b, c].into_iter().multi_cartesian_product());
+        TestResult::passed()
+    }
+
+    fn coalesce(v: Vec<u8>) -> () {
+        test_specializations(&v.iter().coalesce(|x, y| if x == y { Ok(x) } else { Err((x, y)) }))
+    }
+
+    fn dedup(v: Vec<u8>) -> () {
+        test_specializations(&v.iter().dedup())
+    }
+
+    fn dedup_by(v: Vec<u8>) -> () {
+        test_specializations(&v.iter().dedup_by(PartialOrd::ge))
+    }
+
+    fn dedup_with_count(v: Vec<u8>) -> () {
+        test_specializations(&v.iter().dedup_with_count())
+    }
+
+    fn dedup_by_with_count(v: Vec<u8>) -> () {
+        test_specializations(&v.iter().dedup_by_with_count(PartialOrd::ge))
+    }
+
+    fn duplicates(v: Vec<u8>) -> () {
+        let it = v.iter().duplicates();
+        test_specializations(&it);
+        test_double_ended_specializations(&it);
+    }
+
+    fn duplicates_by(v: Vec<u8>) -> () {
+        let it = v.iter().duplicates_by(|x| *x % 10);
+        test_specializations(&it);
+        test_double_ended_specializations(&it);
+    }
+
+    fn unique(v: Vec<u8>) -> () {
+        let it = v.iter().unique();
+        test_specializations(&it);
+        test_double_ended_specializations(&it);
+    }
+
+    fn unique_by(v: Vec<u8>) -> () {
+        let it = v.iter().unique_by(|x| *x % 50);
+        test_specializations(&it);
+        test_double_ended_specializations(&it);
+    }
+
+    fn take_while_inclusive(v: Vec<u8>) -> () {
+        test_specializations(&v.iter().copied().take_while_inclusive(|&x| x < 100));
+    }
+
+    fn while_some(v: Vec<u8>) -> () {
+        test_specializations(&v.iter().map(|&x| if x < 100 { Some(2 * x) } else { None }).while_some());
+    }
+
+    fn pad_using(v: Vec<u8>) -> () {
+        use std::convert::TryFrom;
+        let it = v.iter().copied().pad_using(10, |i| u8::try_from(5 * i).unwrap_or(u8::MAX));
+        test_specializations(&it);
+        test_double_ended_specializations(&it);
+    }
+
+    fn with_position(v: Vec<u8>) -> () {
+        test_specializations(&v.iter().with_position());
+    }
+
+    fn positions(v: Vec<u8>) -> () {
+        let it = v.iter().positions(|x| x % 5 == 0);
+        test_specializations(&it);
+        test_double_ended_specializations(&it);
+    }
+
+    fn update(v: Vec<u8>) -> () {
+        let it = v.iter().copied().update(|x| *x = x.wrapping_mul(7));
+        test_specializations(&it);
+        test_double_ended_specializations(&it);
+    }
+
+    fn tuple_combinations(v: Vec<u8>) -> TestResult {
+        if v.len() > 10 {
+            return TestResult::discard();
+        }
+        test_specializations(&v.iter().tuple_combinations::<(_,)>());
+        test_specializations(&v.iter().tuple_combinations::<(_, _)>());
+        test_specializations(&v.iter().tuple_combinations::<(_, _, _)>());
+        TestResult::passed()
+    }
+
+    fn intersperse(v: Vec<u8>) -> () {
+        test_specializations(&v.into_iter().intersperse(0));
+    }
+
+    fn intersperse_with(v: Vec<u8>) -> () {
+        test_specializations(&v.into_iter().intersperse_with(|| 0));
+    }
+
+    fn array_combinations(v: Vec<u8>) -> TestResult {
+        if v.len() > 10 {
+            return TestResult::discard();
+        }
+        test_specializations(&v.iter().array_combinations::<1>());
+        test_specializations(&v.iter().array_combinations::<2>());
+        test_specializations(&v.iter().array_combinations::<3>());
+        TestResult::passed()
+    }
+
+    fn combinations(a: Vec<u8>, n: u8) -> TestResult {
+        if n > 3 || a.len() > 8 {
+            return TestResult::discard();
+        }
+        test_specializations(&a.iter().combinations(n as usize));
+        TestResult::passed()
+    }
+
+    fn combinations_with_replacement(a: Vec<u8>, n: u8) -> TestResult {
+        if n > 3 || a.len() > 7 {
+            return TestResult::discard();
+        }
+        test_specializations(&a.iter().combinations_with_replacement(n as usize));
+        TestResult::passed()
+    }
+
+    fn permutations(a: Vec<u8>, n: u8) -> TestResult {
+        if n > 3 || a.len() > 8 {
+            return TestResult::discard();
+        }
+        test_specializations(&a.iter().permutations(n as usize));
+        TestResult::passed()
+    }
+
+    fn powerset(a: Vec<u8>) -> TestResult {
+        if a.len() > 6 {
+            return TestResult::discard();
+        }
+        test_specializations(&a.iter().powerset());
+        TestResult::passed()
+    }
+
+    fn zip_longest(a: Vec<u8>, b: Vec<u8>) -> () {
+        let it = a.into_iter().zip_longest(b);
+        test_specializations(&it);
+        test_double_ended_specializations(&it);
+    }
+
+    fn zip_eq(a: Vec<u8>) -> () {
+        test_specializations(&a.iter().zip_eq(a.iter().rev()))
+    }
+
+    fn multizip(a: Vec<u8>) -> () {
+        let it = itertools::multizip((a.iter(), a.iter().rev(), a.iter().take(50)));
+        test_specializations(&it);
+        test_double_ended_specializations(&it);
+    }
+
+    fn izip(a: Vec<u8>, b: Vec<u8>) -> () {
+        test_specializations(&itertools::izip!(b.iter(), a, b.iter().rev()));
+    }
+
+    fn iproduct(a: Vec<u8>, b: Vec<u8>, c: Vec<u8>) -> TestResult {
+        if a.len() * b.len() * c.len() > 200 {
+            return TestResult::discard();
+        }
+        test_specializations(&itertools::iproduct!(a, b.iter(), c));
+        TestResult::passed()
+    }
+
+    fn repeat_n(element: i8, n: u8) -> () {
+        let it = itertools::repeat_n(element, n as usize);
+        test_specializations(&it);
+        test_double_ended_specializations(&it);
+    }
+
+    fn exactly_one_error(v: Vec<u8>) -> TestResult {
+        // Use `at_most_one` would be similar.
+        match v.iter().exactly_one() {
+            Ok(_) => TestResult::discard(),
+            Err(it) => {
+                test_specializations(&it);
+                TestResult::passed()
+            }
+        }
+    }
+}
+
+quickcheck! {
+    fn put_back_qc(test_vec: Vec<i32>) -> () {
+        test_specializations(&itertools::put_back(test_vec.iter()));
+        let mut pb = itertools::put_back(test_vec.into_iter());
+        pb.put_back(1);
+        test_specializations(&pb);
+    }
+
+    fn put_back_n(v: Vec<u8>, n: u8) -> () {
+        let mut it = itertools::put_back_n(v);
+        for k in 0..n {
+            it.put_back(k);
+        }
+        test_specializations(&it);
+    }
+
+    fn multipeek(v: Vec<u8>, n: u8) -> () {
+        let mut it = v.into_iter().multipeek();
+        for _ in 0..n {
+            it.peek();
+        }
+        test_specializations(&it);
+    }
+
+    fn peek_nth_with_peek(v: Vec<u8>, n: u8) -> () {
+        let mut it = itertools::peek_nth(v);
+        for _ in 0..n {
+            it.peek();
+        }
+        test_specializations(&it);
+    }
+
+    fn peek_nth_with_peek_nth(v: Vec<u8>, n: u8) -> () {
+        let mut it = itertools::peek_nth(v);
+        it.peek_nth(n as usize);
+        test_specializations(&it);
+    }
+
+    fn peek_nth_with_peek_mut(v: Vec<u8>, n: u8) -> () {
+        let mut it = itertools::peek_nth(v);
+        for _ in 0..n {
+            if let Some(x) = it.peek_mut() {
+                *x = x.wrapping_add(50);
+            }
+        }
+        test_specializations(&it);
+    }
+
+    fn peek_nth_with_peek_nth_mut(v: Vec<u8>, n: u8) -> () {
+        let mut it = itertools::peek_nth(v);
+        if let Some(x) = it.peek_nth_mut(n as usize) {
+            *x = x.wrapping_add(50);
+        }
+        test_specializations(&it);
+    }
+}
+
+quickcheck! {
+    fn merge(a: Vec<u8>, b: Vec<u8>) -> () {
+        test_specializations(&a.into_iter().merge(b))
+    }
+
+    fn merge_by(a: Vec<u8>, b: Vec<u8>) -> () {
+        test_specializations(&a.into_iter().merge_by(b, PartialOrd::ge))
+    }
+
+    fn merge_join_by_ordering(i1: Vec<u8>, i2: Vec<u8>) -> () {
+        test_specializations(&i1.into_iter().merge_join_by(i2, Ord::cmp));
+    }
+
+    fn merge_join_by_bool(i1: Vec<u8>, i2: Vec<u8>) -> () {
+        test_specializations(&i1.into_iter().merge_join_by(i2, PartialOrd::ge));
+    }
+
+    fn kmerge(a: Vec<i8>, b: Vec<i8>, c: Vec<i8>) -> () {
+        test_specializations(&vec![a, b, c]
+            .into_iter()
+            .map(|v| v.into_iter().sorted())
+            .kmerge());
+    }
+
+    fn kmerge_by(a: Vec<i8>, b: Vec<i8>, c: Vec<i8>) -> () {
+        test_specializations(&vec![a, b, c]
+            .into_iter()
+            .map(|v| v.into_iter().sorted_by_key(|a| a.abs()))
+            .kmerge_by(|a, b| a.abs() < b.abs()));
+    }
+}
+
+quickcheck! {
+    fn map_into(v: Vec<u8>) -> () {
+        let it = v.into_iter().map_into::<u32>();
+        test_specializations(&it);
+        test_double_ended_specializations(&it);
+    }
+
+    fn map_ok(v: Vec<Result<u8, char>>) -> () {
+        let it = v.into_iter().map_ok(|u| u.checked_add(1));
+        test_specializations(&it);
+        test_double_ended_specializations(&it);
+    }
+
+    fn filter_ok(v: Vec<Result<u8, char>>) -> () {
+        let it = v.into_iter().filter_ok(|&i| i < 20);
+        test_specializations(&it);
+        test_double_ended_specializations(&it);
+    }
+
+    fn filter_map_ok(v: Vec<Result<u8, char>>) -> () {
+        let it = v.into_iter().filter_map_ok(|i| if i < 20 { Some(i * 2) } else { None });
+        test_specializations(&it);
+        test_double_ended_specializations(&it);
+    }
+
+    // `SmallIter2<u8>` because `Vec<u8>` is too slow and we get bad coverage from a singleton like Option<u8>
+    fn flatten_ok(v: Vec<Result<SmallIter2<u8>, char>>) -> () {
+        let it = v.into_iter().flatten_ok();
+        test_specializations(&it);
+        test_double_ended_specializations(&it);
+    }
+}
+
+quickcheck! {
+    // TODO Replace this function by a normal call to test_specializations
+    fn process_results(v: Vec<Result<u8, u8>>) -> () {
+        helper(v.iter().copied());
+        helper(v.iter().copied().filter(Result::is_ok));
+
+        fn helper(it: impl DoubleEndedIterator<Item = Result<u8, u8>> + Clone) {
+            macro_rules! check_results_specialized {
+                ($src:expr, |$it:pat| $closure:expr) => {
+                    assert_eq!(
+                        itertools::process_results($src.clone(), |$it| $closure),
+                        itertools::process_results($src.clone(), |i| {
+                            let $it = Unspecialized(i);
+                            $closure
+                        }),
+                    )
+                }
+            }
+
+            check_results_specialized!(it, |i| i.count());
+            check_results_specialized!(it, |i| i.last());
+            check_results_specialized!(it, |i| i.collect::<Vec<_>>());
+            check_results_specialized!(it, |i| i.rev().collect::<Vec<_>>());
+            check_results_specialized!(it, |i| {
+                let mut parameters_from_fold = vec![];
+                let fold_result = i.fold(vec![], |mut acc, v| {
+                    parameters_from_fold.push((acc.clone(), v));
+                    acc.push(v);
+                    acc
+                });
+                (parameters_from_fold, fold_result)
+            });
+            check_results_specialized!(it, |i| {
+                let mut parameters_from_rfold = vec![];
+                let rfold_result = i.rfold(vec![], |mut acc, v| {
+                    parameters_from_rfold.push((acc.clone(), v));
+                    acc.push(v);
+                    acc
+                });
+                (parameters_from_rfold, rfold_result)
+            });
+            check_results_specialized!(it, |mut i| {
+                let mut parameters_from_all = vec![];
+                let first = i.next();
+                let all_result = i.all(|x| {
+                    parameters_from_all.push(x);
+                    Some(x)==first
+                });
+                (parameters_from_all, all_result)
+            });
+            let size = it.clone().count();
+            for n in 0..size + 2 {
+                check_results_specialized!(it, |mut i| i.nth(n));
+            }
+            for n in 0..size + 2 {
+                check_results_specialized!(it, |mut i| i.nth_back(n));
+            }
+        }
+    }
+}
+
+/// Like `VecIntoIter<T>` with maximum 2 elements.
+#[derive(Debug, Clone, Default)]
+enum SmallIter2<T> {
+    #[default]
+    Zero,
+    One(T),
+    Two(T, T),
+}
+
+impl<T: Arbitrary> Arbitrary for SmallIter2<T> {
+    fn arbitrary<G: quickcheck::Gen>(g: &mut G) -> Self {
+        match g.gen_range(0u8, 3) {
+            0 => Self::Zero,
+            1 => Self::One(T::arbitrary(g)),
+            2 => Self::Two(T::arbitrary(g), T::arbitrary(g)),
+            _ => unreachable!(),
+        }
+    }
+    // maybe implement shrink too, maybe not
+}
+
+impl<T> Iterator for SmallIter2<T> {
+    type Item = T;
+
+    fn next(&mut self) -> Option<Self::Item> {
+        match std::mem::take(self) {
+            Self::Zero => None,
+            Self::One(val) => Some(val),
+            Self::Two(val, second) => {
+                *self = Self::One(second);
+                Some(val)
+            }
+        }
+    }
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        let len = match self {
+            Self::Zero => 0,
+            Self::One(_) => 1,
+            Self::Two(_, _) => 2,
+        };
+        (len, Some(len))
+    }
+}
+
+impl<T> DoubleEndedIterator for SmallIter2<T> {
+    fn next_back(&mut self) -> Option<Self::Item> {
+        match std::mem::take(self) {
+            Self::Zero => None,
+            Self::One(val) => Some(val),
+            Self::Two(first, val) => {
+                *self = Self::One(first);
+                Some(val)
+            }
+        }
+    }
+}
diff --git a/vendor/itertools/tests/test_core.rs b/vendor/itertools/tests/test_core.rs
new file mode 100644
index 00000000..49361608
--- /dev/null
+++ b/vendor/itertools/tests/test_core.rs
@@ -0,0 +1,399 @@
+//! Licensed under the Apache License, Version 2.0
+//! https://www.apache.org/licenses/LICENSE-2.0 or the MIT license
+//! https://opensource.org/licenses/MIT, at your
+//! option. This file may not be copied, modified, or distributed
+//! except according to those terms.
+#![no_std]
+#![allow(deprecated)]
+
+use crate::it::chain;
+use crate::it::free::put_back;
+use crate::it::interleave;
+use crate::it::intersperse;
+use crate::it::intersperse_with;
+use crate::it::iproduct;
+use crate::it::izip;
+use crate::it::multizip;
+use crate::it::Itertools;
+use core::iter;
+use itertools as it;
+
+#[allow(dead_code)]
+fn get_esi_then_esi<I: ExactSizeIterator + Clone>(it: I) {
+    fn is_esi(_: impl ExactSizeIterator) {}
+    is_esi(it.clone().get(1..4));
+    is_esi(it.clone().get(1..=4));
+    is_esi(it.clone().get(1..));
+    is_esi(it.clone().get(..4));
+    is_esi(it.clone().get(..=4));
+    is_esi(it.get(..));
+}
+
+#[allow(dead_code)]
+fn get_dei_esi_then_dei_esi<I: DoubleEndedIterator + ExactSizeIterator + Clone>(it: I) {
+    fn is_dei_esi(_: impl DoubleEndedIterator + ExactSizeIterator) {}
+    is_dei_esi(it.clone().get(1..4));
+    is_dei_esi(it.clone().get(1..=4));
+    is_dei_esi(it.clone().get(1..));
+    is_dei_esi(it.clone().get(..4));
+    is_dei_esi(it.clone().get(..=4));
+    is_dei_esi(it.get(..));
+}
+
+#[test]
+fn get_1_max() {
+    let mut it = (0..5).get(1..=usize::MAX);
+    assert_eq!(it.next(), Some(1));
+    assert_eq!(it.next_back(), Some(4));
+}
+
+#[test]
+#[should_panic]
+fn get_full_range_inclusive() {
+    let _it = (0..5).get(0..=usize::MAX);
+}
+
+#[test]
+fn product0() {
+    let mut prod = iproduct!();
+    assert_eq!(prod.next(), Some(()));
+    assert!(prod.next().is_none());
+}
+
+#[test]
+fn iproduct1() {
+    let s = "αβ";
+
+    let mut prod = iproduct!(s.chars());
+    assert_eq!(prod.next(), Some(('α',)));
+    assert_eq!(prod.next(), Some(('β',)));
+    assert!(prod.next().is_none());
+}
+
+#[test]
+fn product2() {
+    let s = "αβ";
+
+    let mut prod = iproduct!(s.chars(), 0..2);
+    assert!(prod.next() == Some(('α', 0)));
+    assert!(prod.next() == Some(('α', 1)));
+    assert!(prod.next() == Some(('β', 0)));
+    assert!(prod.next() == Some(('β', 1)));
+    assert!(prod.next().is_none());
+}
+
+#[test]
+fn product_temporary() {
+    for (_x, _y, _z) in iproduct!(
+        [0, 1, 2].iter().cloned(),
+        [0, 1, 2].iter().cloned(),
+        [0, 1, 2].iter().cloned()
+    ) {
+        // ok
+    }
+}
+
+#[test]
+fn izip_macro() {
+    let mut zip = izip!(2..3);
+    assert!(zip.next() == Some(2));
+    assert!(zip.next().is_none());
+
+    let mut zip = izip!(0..3, 0..2, 0..2i8);
+    for i in 0..2 {
+        assert!((i as usize, i, i as i8) == zip.next().unwrap());
+    }
+    assert!(zip.next().is_none());
+
+    let xs: [isize; 0] = [];
+    let mut zip = izip!(0..3, 0..2, 0..2i8, &xs);
+    assert!(zip.next().is_none());
+}
+
+#[test]
+fn izip2() {
+    let _zip1: iter::Zip<_, _> = izip!(1.., 2..);
+    let _zip2: iter::Zip<_, _> = izip!(1.., 2..,);
+}
+
+#[test]
+fn izip3() {
+    let mut zip: iter::Map<iter::Zip<_, _>, _> = izip!(0..3, 0..2, 0..2i8);
+    for i in 0..2 {
+        assert!((i as usize, i, i as i8) == zip.next().unwrap());
+    }
+    assert!(zip.next().is_none());
+}
+
+#[test]
+fn multizip3() {
+    let mut zip = multizip((0..3, 0..2, 0..2i8));
+    for i in 0..2 {
+        assert!((i as usize, i, i as i8) == zip.next().unwrap());
+    }
+    assert!(zip.next().is_none());
+
+    let xs: [isize; 0] = [];
+    let mut zip = multizip((0..3, 0..2, 0..2i8, xs.iter()));
+    assert!(zip.next().is_none());
+
+    for (_, _, _, _, _) in multizip((0..3, 0..2, xs.iter(), &xs, xs.to_vec())) {
+        /* test compiles */
+    }
+}
+
+#[test]
+fn chain_macro() {
+    let mut chain = chain!(2..3);
+    assert!(chain.next() == Some(2));
+    assert!(chain.next().is_none());
+
+    let mut chain = chain!(0..2, 2..3, 3..5i8);
+    for i in 0..5i8 {
+        assert_eq!(Some(i), chain.next());
+    }
+    assert!(chain.next().is_none());
+
+    let mut chain = chain!();
+    assert_eq!(chain.next(), Option::<()>::None);
+}
+
+#[test]
+fn chain2() {
+    let _ = chain!(1.., 2..);
+    let _ = chain!(1.., 2..,);
+}
+
+#[test]
+fn write_to() {
+    let xs = [7, 9, 8];
+    let mut ys = [0; 5];
+    let cnt = ys.iter_mut().set_from(xs.iter().copied());
+    assert!(cnt == xs.len());
+    assert!(ys == [7, 9, 8, 0, 0]);
+
+    let cnt = ys.iter_mut().set_from(0..10);
+    assert!(cnt == ys.len());
+    assert!(ys == [0, 1, 2, 3, 4]);
+}
+
+#[test]
+fn test_interleave() {
+    let xs: [u8; 0] = [];
+    let ys = [7u8, 9, 8, 10];
+    let zs = [2u8, 77];
+    let it = interleave(xs.iter(), ys.iter());
+    it::assert_equal(it, ys.iter());
+
+    let rs = [7u8, 2, 9, 77, 8, 10];
+    let it = interleave(ys.iter(), zs.iter());
+    it::assert_equal(it, rs.iter());
+}
+
+#[test]
+fn test_intersperse() {
+    let xs = [1u8, 2, 3];
+    let ys = [1u8, 0, 2, 0, 3];
+    let it = intersperse(&xs, &0);
+    it::assert_equal(it, ys.iter());
+}
+
+#[test]
+fn test_intersperse_with() {
+    let xs = [1u8, 2, 3];
+    let ys = [1u8, 10, 2, 10, 3];
+    let i = 10;
+    let it = intersperse_with(&xs, || &i);
+    it::assert_equal(it, ys.iter());
+}
+
+#[test]
+fn dropping() {
+    let xs = [1, 2, 3];
+    let mut it = xs.iter().dropping(2);
+    assert_eq!(it.next(), Some(&3));
+    assert!(it.next().is_none());
+    let mut it = xs.iter().dropping(5);
+    assert!(it.next().is_none());
+}
+
+#[test]
+fn batching() {
+    let xs = [0, 1, 2, 1, 3];
+    let ys = [(0, 1), (2, 1)];
+
+    // An iterator that gathers elements up in pairs
+    let pit = xs
+        .iter()
+        .cloned()
+        .batching(|it| it.next().and_then(|x| it.next().map(|y| (x, y))));
+    it::assert_equal(pit, ys.iter().cloned());
+}
+
+#[test]
+fn test_put_back() {
+    let xs = [0, 1, 1, 1, 2, 1, 3, 3];
+    let mut pb = put_back(xs.iter().cloned());
+    pb.next();
+    pb.put_back(1);
+    pb.put_back(0);
+    it::assert_equal(pb, xs.iter().cloned());
+}
+
+#[test]
+fn merge() {
+    it::assert_equal((0..10).step_by(2).merge((1..10).step_by(2)), 0..10);
+}
+
+#[test]
+fn repeatn() {
+    let s = "α";
+    let mut it = it::repeat_n(s, 3);
+    assert_eq!(it.len(), 3);
+    assert_eq!(it.next(), Some(s));
+    assert_eq!(it.next(), Some(s));
+    assert_eq!(it.next(), Some(s));
+    assert_eq!(it.next(), None);
+    assert_eq!(it.next(), None);
+}
+
+#[test]
+fn count_clones() {
+    // Check that RepeatN only clones N - 1 times.
+
+    use core::cell::Cell;
+    #[derive(PartialEq, Debug)]
+    struct Foo {
+        n: Cell<usize>,
+    }
+
+    impl Clone for Foo {
+        fn clone(&self) -> Self {
+            let n = self.n.get();
+            self.n.set(n + 1);
+            Self {
+                n: Cell::new(n + 1),
+            }
+        }
+    }
+
+    for n in 0..10 {
+        let f = Foo { n: Cell::new(0) };
+        let it = it::repeat_n(f, n);
+        // drain it
+        let last = it.last();
+        if n == 0 {
+            assert_eq!(last, None);
+        } else {
+            assert_eq!(
+                last,
+                Some(Foo {
+                    n: Cell::new(n - 1)
+                })
+            );
+        }
+    }
+}
+
+#[test]
+fn part() {
+    let mut data = [7, 1, 1, 9, 1, 1, 3];
+    let i = it::partition(&mut data, |elt| *elt >= 3);
+    assert_eq!(i, 3);
+    assert_eq!(data, [7, 3, 9, 1, 1, 1, 1]);
+
+    let i = it::partition(&mut data, |elt| *elt == 1);
+    assert_eq!(i, 4);
+    assert_eq!(data, [1, 1, 1, 1, 9, 3, 7]);
+
+    let mut data = [1, 2, 3, 4, 5, 6, 7, 8, 9];
+    let i = it::partition(&mut data, |elt| *elt % 3 == 0);
+    assert_eq!(i, 3);
+    assert_eq!(data, [9, 6, 3, 4, 5, 2, 7, 8, 1]);
+}
+
+#[test]
+fn tree_reduce() {
+    for i in 0..100 {
+        assert_eq!((0..i).tree_reduce(|x, y| x + y), (0..i).fold1(|x, y| x + y));
+    }
+}
+
+#[test]
+fn exactly_one() {
+    assert_eq!((0..10).filter(|&x| x == 2).exactly_one().unwrap(), 2);
+    assert!((0..10)
+        .filter(|&x| x > 1 && x < 4)
+        .exactly_one()
+        .unwrap_err()
+        .eq(2..4));
+    assert!((0..10)
+        .filter(|&x| x > 1 && x < 5)
+        .exactly_one()
+        .unwrap_err()
+        .eq(2..5));
+    assert!((0..10)
+        .filter(|&_| false)
+        .exactly_one()
+        .unwrap_err()
+        .eq(0..0));
+}
+
+#[test]
+fn at_most_one() {
+    assert_eq!((0..10).filter(|&x| x == 2).at_most_one().unwrap(), Some(2));
+    assert!((0..10)
+        .filter(|&x| x > 1 && x < 4)
+        .at_most_one()
+        .unwrap_err()
+        .eq(2..4));
+    assert!((0..10)
+        .filter(|&x| x > 1 && x < 5)
+        .at_most_one()
+        .unwrap_err()
+        .eq(2..5));
+    assert_eq!((0..10).filter(|&_| false).at_most_one().unwrap(), None);
+}
+
+#[test]
+fn sum1() {
+    let v: &[i32] = &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
+    assert_eq!(v[..0].iter().cloned().sum1::<i32>(), None);
+    assert_eq!(v[1..2].iter().cloned().sum1::<i32>(), Some(1));
+    assert_eq!(v[1..3].iter().cloned().sum1::<i32>(), Some(3));
+    assert_eq!(v.iter().cloned().sum1::<i32>(), Some(55));
+}
+
+#[test]
+fn product1() {
+    let v: &[i32] = &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
+    assert_eq!(v[..0].iter().cloned().product1::<i32>(), None);
+    assert_eq!(v[..1].iter().cloned().product1::<i32>(), Some(0));
+    assert_eq!(v[1..3].iter().cloned().product1::<i32>(), Some(2));
+    assert_eq!(v[1..5].iter().cloned().product1::<i32>(), Some(24));
+}
+
+#[test]
+fn next_array() {
+    let v = [1, 2, 3, 4, 5];
+    let mut iter = v.iter();
+    assert_eq!(iter.next_array(), Some([]));
+    assert_eq!(iter.next_array().map(|[&x, &y]| [x, y]), Some([1, 2]));
+    assert_eq!(iter.next_array().map(|[&x, &y]| [x, y]), Some([3, 4]));
+    assert_eq!(iter.next_array::<2>(), None);
+}
+
+#[test]
+fn collect_array() {
+    let v = [1, 2];
+    let iter = v.iter().cloned();
+    assert_eq!(iter.collect_array(), Some([1, 2]));
+
+    let v = [1];
+    let iter = v.iter().cloned();
+    assert_eq!(iter.collect_array::<2>(), None);
+
+    let v = [1, 2, 3];
+    let iter = v.iter().cloned();
+    assert_eq!(iter.collect_array::<2>(), None);
+}
diff --git a/vendor/itertools/tests/test_std.rs b/vendor/itertools/tests/test_std.rs
new file mode 100644
index 00000000..ad391faa
--- /dev/null
+++ b/vendor/itertools/tests/test_std.rs
@@ -0,0 +1,1569 @@
+#![allow(unstable_name_collisions)]
+
+use crate::it::cloned;
+use crate::it::free::put_back_n;
+use crate::it::free::rciter;
+use crate::it::iproduct;
+use crate::it::izip;
+use crate::it::multipeek;
+use crate::it::multizip;
+use crate::it::peek_nth;
+use crate::it::repeat_n;
+use crate::it::ExactlyOneError;
+use crate::it::FoldWhile;
+use crate::it::Itertools;
+use itertools as it;
+use quickcheck as qc;
+use rand::{
+    distributions::{Distribution, Standard},
+    rngs::StdRng,
+    Rng, SeedableRng,
+};
+use rand::{seq::SliceRandom, thread_rng};
+use std::{cmp::min, fmt::Debug, marker::PhantomData};
+
+#[test]
+fn product3() {
+    let prod = iproduct!(0..3, 0..2, 0..2);
+    assert_eq!(prod.size_hint(), (12, Some(12)));
+    let v = prod.collect_vec();
+    for i in 0..3 {
+        for j in 0..2 {
+            for k in 0..2 {
+                assert!((i, j, k) == v[(i * 2 * 2 + j * 2 + k) as usize]);
+            }
+        }
+    }
+    for (_, _, _, _) in iproduct!(0..3, 0..2, 0..2, 0..3) { /* test compiles */ }
+}
+
+#[test]
+fn interleave_shortest() {
+    let v0: Vec<i32> = vec![0, 2, 4];
+    let v1: Vec<i32> = vec![1, 3, 5, 7];
+    let it = v0.into_iter().interleave_shortest(v1);
+    assert_eq!(it.size_hint(), (6, Some(6)));
+    assert_eq!(it.collect_vec(), vec![0, 1, 2, 3, 4, 5]);
+
+    let v0: Vec<i32> = vec![0, 2, 4, 6, 8];
+    let v1: Vec<i32> = vec![1, 3, 5];
+    let it = v0.into_iter().interleave_shortest(v1);
+    assert_eq!(it.size_hint(), (7, Some(7)));
+    assert_eq!(it.collect_vec(), vec![0, 1, 2, 3, 4, 5, 6]);
+
+    let i0 = ::std::iter::repeat(0);
+    let v1: Vec<_> = vec![1, 3, 5];
+    let it = i0.interleave_shortest(v1);
+    assert_eq!(it.size_hint(), (7, Some(7)));
+
+    let v0: Vec<_> = vec![0, 2, 4];
+    let i1 = ::std::iter::repeat(1);
+    let it = v0.into_iter().interleave_shortest(i1);
+    assert_eq!(it.size_hint(), (6, Some(6)));
+}
+
+#[test]
+fn duplicates_by() {
+    let xs = ["aaa", "bbbbb", "aa", "ccc", "bbbb", "aaaaa", "cccc"];
+    let ys = ["aa", "bbbb", "cccc"];
+    it::assert_equal(ys.iter(), xs.iter().duplicates_by(|x| x[..2].to_string()));
+    it::assert_equal(
+        ys.iter(),
+        xs.iter().rev().duplicates_by(|x| x[..2].to_string()).rev(),
+    );
+    let ys_rev = ["ccc", "aa", "bbbbb"];
+    it::assert_equal(
+        ys_rev.iter(),
+        xs.iter().duplicates_by(|x| x[..2].to_string()).rev(),
+    );
+}
+
+#[test]
+fn duplicates() {
+    let xs = [0, 1, 2, 3, 2, 1, 3];
+    let ys = [2, 1, 3];
+    it::assert_equal(ys.iter(), xs.iter().duplicates());
+    it::assert_equal(ys.iter(), xs.iter().rev().duplicates().rev());
+    let ys_rev = [3, 2, 1];
+    it::assert_equal(ys_rev.iter(), xs.iter().duplicates().rev());
+
+    let xs = [0, 1, 0, 1];
+    let ys = [0, 1];
+    it::assert_equal(ys.iter(), xs.iter().duplicates());
+    it::assert_equal(ys.iter(), xs.iter().rev().duplicates().rev());
+    let ys_rev = [1, 0];
+    it::assert_equal(ys_rev.iter(), xs.iter().duplicates().rev());
+
+    let xs = [0, 1, 2, 1, 2];
+    let ys = vec![1, 2];
+    assert_eq!(ys, xs.iter().duplicates().cloned().collect_vec());
+    assert_eq!(
+        ys,
+        xs.iter().rev().duplicates().rev().cloned().collect_vec()
+    );
+    let ys_rev = vec![2, 1];
+    assert_eq!(ys_rev, xs.iter().duplicates().rev().cloned().collect_vec());
+}
+
+#[test]
+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]
+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]
+fn intersperse() {
+    let xs = ["a", "", "b", "c"];
+    let v: Vec<&str> = xs.iter().cloned().intersperse(", ").collect();
+    let text: String = v.concat();
+    assert_eq!(text, "a, , b, c".to_string());
+
+    let ys = [0, 1, 2, 3];
+    let mut it = ys[..0].iter().copied().intersperse(1);
+    assert!(it.next().is_none());
+}
+
+#[test]
+fn dedup() {
+    let xs = [0, 1, 1, 1, 2, 1, 3, 3];
+    let ys = [0, 1, 2, 1, 3];
+    it::assert_equal(ys.iter(), xs.iter().dedup());
+    let xs = [0, 0, 0, 0, 0];
+    let ys = [0];
+    it::assert_equal(ys.iter(), xs.iter().dedup());
+
+    let xs = [0, 1, 1, 1, 2, 1, 3, 3];
+    let ys = [0, 1, 2, 1, 3];
+    let mut xs_d = Vec::new();
+    xs.iter().dedup().fold((), |(), &elt| xs_d.push(elt));
+    assert_eq!(&xs_d, &ys);
+}
+
+#[test]
+fn coalesce() {
+    let data = [-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)];
+    it::assert_equal(ys.iter(), xs.iter().dedup_by(|x, y| x.1 == y.1));
+    let xs = [(0, 1), (0, 2), (0, 3), (0, 4), (0, 5)];
+    let ys = [(0, 1)];
+    it::assert_equal(ys.iter(), xs.iter().dedup_by(|x, y| x.0 == y.0));
+
+    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)];
+    let mut xs_d = Vec::new();
+    xs.iter()
+        .dedup_by(|x, y| x.1 == y.1)
+        .fold((), |(), &elt| xs_d.push(elt));
+    assert_eq!(&xs_d, &ys);
+}
+
+#[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());
+    assert!(!"AABBCCC".chars().all_equal());
+    assert!("AAAAAAA".chars().all_equal());
+    for (_key, mut sub) in &"AABBCCC".chars().chunk_by(|&x| x) {
+        assert!(sub.all_equal());
+    }
+}
+
+#[test]
+fn all_equal_value() {
+    assert_eq!("".chars().all_equal_value(), Err(None));
+    assert_eq!("A".chars().all_equal_value(), Ok('A'));
+    assert_eq!("AABBCCC".chars().all_equal_value(), Err(Some(('A', 'B'))));
+    assert_eq!("AAAAAAA".chars().all_equal_value(), Ok('A'));
+    {
+        let mut it = [1, 2, 3].iter().copied();
+        let result = it.all_equal_value();
+        assert_eq!(result, Err(Some((1, 2))));
+        let remaining = it.next();
+        assert_eq!(remaining, Some(3));
+        assert!(it.next().is_none());
+    }
+}
+
+#[test]
+fn all_unique() {
+    assert!("ABCDEFGH".chars().all_unique());
+    assert!(!"ABCDEFGA".chars().all_unique());
+    assert!(::std::iter::empty::<usize>().all_unique());
+}
+
+#[test]
+fn test_put_back_n() {
+    let xs = [0, 1, 1, 1, 2, 1, 3, 3];
+    let mut pb = put_back_n(xs.iter().cloned());
+    pb.next();
+    pb.next();
+    pb.put_back(1);
+    pb.put_back(0);
+    it::assert_equal(pb, xs.iter().cloned());
+}
+
+#[test]
+fn tee() {
+    let xs = [0, 1, 2, 3];
+    let (mut t1, mut t2) = xs.iter().cloned().tee();
+    assert_eq!(t1.next(), Some(0));
+    assert_eq!(t2.next(), Some(0));
+    assert_eq!(t1.next(), Some(1));
+    assert_eq!(t1.next(), Some(2));
+    assert_eq!(t1.next(), Some(3));
+    assert_eq!(t1.next(), None);
+    assert_eq!(t2.next(), Some(1));
+    assert_eq!(t2.next(), Some(2));
+    assert_eq!(t1.next(), None);
+    assert_eq!(t2.next(), Some(3));
+    assert_eq!(t2.next(), None);
+    assert_eq!(t1.next(), None);
+    assert_eq!(t2.next(), None);
+
+    let (t1, t2) = xs.iter().cloned().tee();
+    it::assert_equal(t1, xs.iter().cloned());
+    it::assert_equal(t2, xs.iter().cloned());
+
+    let (t1, t2) = xs.iter().cloned().tee();
+    it::assert_equal(t1.zip(t2), xs.iter().cloned().zip(xs.iter().cloned()));
+}
+
+#[test]
+fn test_rciter() {
+    let xs = [0, 1, 1, 1, 2, 1, 3, 5, 6];
+
+    let mut r1 = rciter(xs.iter().cloned());
+    let mut r2 = r1.clone();
+    assert_eq!(r1.next(), Some(0));
+    assert_eq!(r2.next(), Some(1));
+    let mut z = r1.zip(r2);
+    assert_eq!(z.next(), Some((1, 1)));
+    assert_eq!(z.next(), Some((2, 1)));
+    assert_eq!(z.next(), Some((3, 5)));
+    assert_eq!(z.next(), None);
+
+    // test intoiterator
+    let r1 = rciter(0..5);
+    let mut z = izip!(&r1, r1);
+    assert_eq!(z.next(), Some((0, 1)));
+}
+
+#[test]
+fn trait_pointers() {
+    struct ByRef<'r, I: ?Sized>(&'r mut I);
+
+    impl<'r, X, I> Iterator for ByRef<'r, I>
+    where
+        I: ?Sized + 'r + Iterator<Item = X>,
+    {
+        type Item = X;
+        fn next(&mut self) -> Option<Self::Item> {
+            self.0.next()
+        }
+    }
+
+    let mut it = Box::new(0..10) as Box<dyn Iterator<Item = i32>>;
+    assert_eq!(it.next(), Some(0));
+
+    {
+        let jt: &mut dyn Iterator<Item = i32> = &mut *it;
+        assert_eq!(jt.next(), Some(1));
+
+        {
+            let mut r = ByRef(jt);
+            assert_eq!(r.next(), Some(2));
+        }
+
+        assert_eq!(jt.find_position(|x| *x == 4), Some((1, 4)));
+        jt.for_each(|_| ());
+    }
+}
+
+#[test]
+fn merge_by() {
+    let odd: Vec<(u32, &str)> = vec![(1, "hello"), (3, "world"), (5, "!")];
+    let even = [(2, "foo"), (4, "bar"), (6, "baz")];
+    let expected = [
+        (1, "hello"),
+        (2, "foo"),
+        (3, "world"),
+        (4, "bar"),
+        (5, "!"),
+        (6, "baz"),
+    ];
+    let results = odd.iter().merge_by(even.iter(), |a, b| a.0 <= b.0);
+    it::assert_equal(results, expected.iter());
+}
+
+#[test]
+fn merge_by_btree() {
+    use std::collections::BTreeMap;
+    let mut bt1 = BTreeMap::new();
+    bt1.insert("hello", 1);
+    bt1.insert("world", 3);
+    let mut bt2 = BTreeMap::new();
+    bt2.insert("foo", 2);
+    bt2.insert("bar", 4);
+    let results = bt1.into_iter().merge_by(bt2, |a, b| a.0 <= b.0);
+    let expected = vec![("bar", 4), ("foo", 2), ("hello", 1), ("world", 3)];
+    it::assert_equal(results, expected);
+}
+
+#[test]
+fn kmerge() {
+    let its = (0..4).map(|s| (s..10).step_by(4));
+
+    it::assert_equal(its.kmerge(), 0..10);
+}
+
+#[test]
+fn kmerge_2() {
+    let its = vec![3, 2, 1, 0].into_iter().map(|s| (s..10).step_by(4));
+
+    it::assert_equal(its.kmerge(), 0..10);
+}
+
+#[test]
+fn kmerge_empty() {
+    let its = (0..4).map(|_| 0..0);
+    assert_eq!(its.kmerge().next(), None);
+}
+
+#[test]
+fn kmerge_size_hint() {
+    let its = (0..5).map(|_| (0..10));
+    assert_eq!(its.kmerge().size_hint(), (50, Some(50)));
+}
+
+#[test]
+fn kmerge_empty_size_hint() {
+    let its = (0..5).map(|_| (0..0));
+    assert_eq!(its.kmerge().size_hint(), (0, Some(0)));
+}
+
+#[test]
+fn join() {
+    let many = [1, 2, 3];
+    let one = [1];
+    let none: Vec<i32> = vec![];
+
+    assert_eq!(many.iter().join(", "), "1, 2, 3");
+    assert_eq!(one.iter().join(", "), "1");
+    assert_eq!(none.iter().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));
+    it::assert_equal(sc, vec![1, 2, 3, 4]);
+
+    let v = (0..5).sorted_by(|&a, &b| a.cmp(&b).reverse());
+    it::assert_equal(v, vec![4, 3, 2, 1, 0]);
+}
+
+#[cfg(not(miri))]
+qc::quickcheck! {
+    fn k_smallest_range(n: i64, 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 usize, m as u64);
+
+        let mut v: Vec<_> = (n..n.saturating_add(m as _)).collect();
+        // Generate a random permutation of n..n+m
+        v.shuffle(&mut thread_rng());
+
+        // Construct the right answers for the top and bottom elements
+        let mut sorted = v.clone();
+        sorted.sort();
+        // how many elements are we checking
+        let num_elements = min(k, m as _);
+
+        // Compute the top and bottom k in various combinations
+        let sorted_smallest = sorted[..num_elements].iter().cloned();
+        let smallest = v.iter().cloned().k_smallest(k);
+        let smallest_by = v.iter().cloned().k_smallest_by(k, Ord::cmp);
+        let smallest_by_key = v.iter().cloned().k_smallest_by_key(k, |&x| x);
+
+        let sorted_largest = sorted[sorted.len() - num_elements..].iter().rev().cloned();
+        let largest = v.iter().cloned().k_largest(k);
+        let largest_by = v.iter().cloned().k_largest_by(k, Ord::cmp);
+        let largest_by_key = v.iter().cloned().k_largest_by_key(k, |&x| x);
+
+        // Check the variations produce the same answers and that they're right
+        it::assert_equal(smallest, sorted_smallest.clone());
+        it::assert_equal(smallest_by, sorted_smallest.clone());
+        it::assert_equal(smallest_by_key, sorted_smallest);
+
+        it::assert_equal(largest, sorted_largest.clone());
+        it::assert_equal(largest_by, sorted_largest.clone());
+        it::assert_equal(largest_by_key, sorted_largest);
+    }
+
+    fn k_smallest_relaxed_range(n: i64, 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 usize, m as u64);
+
+        let mut v: Vec<_> = (n..n.saturating_add(m as _)).collect();
+        // Generate a random permutation of n..n+m
+        v.shuffle(&mut thread_rng());
+
+        // Construct the right answers for the top and bottom elements
+        let mut sorted = v.clone();
+        sorted.sort();
+        // how many elements are we checking
+        let num_elements = min(k, m as _);
+
+        // Compute the top and bottom k in various combinations
+        let sorted_smallest = sorted[..num_elements].iter().cloned();
+        let smallest = v.iter().cloned().k_smallest_relaxed(k);
+        let smallest_by = v.iter().cloned().k_smallest_relaxed_by(k, Ord::cmp);
+        let smallest_by_key = v.iter().cloned().k_smallest_relaxed_by_key(k, |&x| x);
+
+        let sorted_largest = sorted[sorted.len() - num_elements..].iter().rev().cloned();
+        let largest = v.iter().cloned().k_largest_relaxed(k);
+        let largest_by = v.iter().cloned().k_largest_relaxed_by(k, Ord::cmp);
+        let largest_by_key = v.iter().cloned().k_largest_relaxed_by_key(k, |&x| x);
+
+        // Check the variations produce the same answers and that they're right
+        it::assert_equal(smallest, sorted_smallest.clone());
+        it::assert_equal(smallest_by, sorted_smallest.clone());
+        it::assert_equal(smallest_by_key, sorted_smallest);
+
+        it::assert_equal(largest, sorted_largest.clone());
+        it::assert_equal(largest_by, sorted_largest.clone());
+        it::assert_equal(largest_by_key, sorted_largest);
+    }
+}
+
+#[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 {
+        Self {
+            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 i1 = i.clone();
+    let j1 = i.clone();
+    let k = k as usize;
+    it::assert_equal(i.k_smallest(k), j.sorted().take(k));
+    it::assert_equal(i1.k_smallest_relaxed(k), j1.sorted().take(k));
+}
+
+// Similar to `k_smallest_sort` but for our custom heap implementation.
+fn k_smallest_by_sort<I>(i: I, k: u16)
+where
+    I: Iterator + Clone,
+    I::Item: Ord + Debug,
+{
+    let j = i.clone();
+    let i1 = i.clone();
+    let j1 = i.clone();
+    let k = k as usize;
+    it::assert_equal(i.k_smallest_by(k, Ord::cmp), j.sorted().take(k));
+    it::assert_equal(i1.k_smallest_relaxed_by(k, Ord::cmp), j1.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)
+                }
+            }
+        })+
+    };
+}
+
+#[cfg(not(miri))]
+generic_test!(k_smallest_sort, u8, u16, u32, u64, i8, i16, i32, i64);
+#[cfg(not(miri))]
+generic_test!(k_smallest_by_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);
+    it::assert_equal(sc, vec![1, 2, 3, 4]);
+
+    let v = (0..5).sorted_by_key(|&x| -x);
+    it::assert_equal(v, vec![4, 3, 2, 1, 0]);
+}
+
+#[test]
+fn sorted_by_cached_key() {
+    // Track calls to key function
+    let mut ncalls = 0;
+
+    let sorted = [3, 4, 1, 2].iter().cloned().sorted_by_cached_key(|&x| {
+        ncalls += 1;
+        x.to_string()
+    });
+    it::assert_equal(sorted, vec![1, 2, 3, 4]);
+    // Check key function called once per element
+    assert_eq!(ncalls, 4);
+
+    let mut ncalls = 0;
+
+    let sorted = (0..5).sorted_by_cached_key(|&x| {
+        ncalls += 1;
+        -x
+    });
+    it::assert_equal(sorted, vec![4, 3, 2, 1, 0]);
+    // Check key function called once per element
+    assert_eq!(ncalls, 5);
+}
+
+#[test]
+fn test_multipeek() {
+    let nums = vec![1u8, 2, 3, 4, 5];
+
+    let mp = multipeek(nums.iter().copied());
+    assert_eq!(nums, mp.collect::<Vec<_>>());
+
+    let mut mp = multipeek(nums.iter().copied());
+    assert_eq!(mp.peek(), Some(&1));
+    assert_eq!(mp.next(), Some(1));
+    assert_eq!(mp.peek(), Some(&2));
+    assert_eq!(mp.peek(), Some(&3));
+    assert_eq!(mp.next(), Some(2));
+    assert_eq!(mp.peek(), Some(&3));
+    assert_eq!(mp.peek(), Some(&4));
+    assert_eq!(mp.peek(), Some(&5));
+    assert_eq!(mp.peek(), None);
+    assert_eq!(mp.next(), Some(3));
+    assert_eq!(mp.next(), Some(4));
+    assert_eq!(mp.peek(), Some(&5));
+    assert_eq!(mp.peek(), None);
+    assert_eq!(mp.next(), Some(5));
+    assert_eq!(mp.next(), None);
+    assert_eq!(mp.peek(), None);
+}
+
+#[test]
+fn test_multipeek_reset() {
+    let data = [1, 2, 3, 4];
+
+    let mut mp = multipeek(cloned(&data));
+    assert_eq!(mp.peek(), Some(&1));
+    assert_eq!(mp.next(), Some(1));
+    assert_eq!(mp.peek(), Some(&2));
+    assert_eq!(mp.peek(), Some(&3));
+    mp.reset_peek();
+    assert_eq!(mp.peek(), Some(&2));
+    assert_eq!(mp.next(), Some(2));
+}
+
+#[test]
+fn test_multipeek_peeking_next() {
+    use crate::it::PeekingNext;
+    let nums = [1u8, 2, 3, 4, 5, 6, 7];
+
+    let mut mp = multipeek(nums.iter().copied());
+    assert_eq!(mp.peeking_next(|&x| x != 0), Some(1));
+    assert_eq!(mp.next(), Some(2));
+    assert_eq!(mp.peek(), Some(&3));
+    assert_eq!(mp.peek(), Some(&4));
+    assert_eq!(mp.peeking_next(|&x| x == 3), Some(3));
+    assert_eq!(mp.peek(), Some(&4));
+    assert_eq!(mp.peeking_next(|&x| x != 4), None);
+    assert_eq!(mp.peeking_next(|&x| x == 4), Some(4));
+    assert_eq!(mp.peek(), Some(&5));
+    assert_eq!(mp.peek(), Some(&6));
+    assert_eq!(mp.peeking_next(|&x| x != 5), None);
+    assert_eq!(mp.peek(), Some(&7));
+    assert_eq!(mp.peeking_next(|&x| x == 5), Some(5));
+    assert_eq!(mp.peeking_next(|&x| x == 6), Some(6));
+    assert_eq!(mp.peek(), Some(&7));
+    assert_eq!(mp.peek(), None);
+    assert_eq!(mp.next(), Some(7));
+    assert_eq!(mp.peek(), None);
+}
+
+#[test]
+fn test_repeat_n_peeking_next() {
+    use crate::it::PeekingNext;
+    let mut rn = repeat_n(0, 5);
+    assert_eq!(rn.peeking_next(|&x| x != 0), None);
+    assert_eq!(rn.peeking_next(|&x| x <= 0), Some(0));
+    assert_eq!(rn.next(), Some(0));
+    assert_eq!(rn.peeking_next(|&x| x <= 0), Some(0));
+    assert_eq!(rn.peeking_next(|&x| x != 0), None);
+    assert_eq!(rn.peeking_next(|&x| x >= 0), Some(0));
+    assert_eq!(rn.next(), Some(0));
+    assert_eq!(rn.peeking_next(|&x| x <= 0), None);
+    assert_eq!(rn.next(), None);
+}
+
+#[test]
+fn test_peek_nth() {
+    let nums = vec![1u8, 2, 3, 4, 5];
+
+    let iter = peek_nth(nums.iter().copied());
+    assert_eq!(nums, iter.collect::<Vec<_>>());
+
+    let mut iter = peek_nth(nums.iter().copied());
+
+    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 = [1u8, 2, 3, 4, 5, 6, 7];
+    let mut iter = peek_nth(nums.iter().copied());
+
+    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 test_peek_nth_next_if() {
+    let nums = [1u8, 2, 3, 4, 5, 6, 7];
+    let mut iter = peek_nth(nums.iter().copied());
+
+    assert_eq!(iter.next_if(|&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.next_if_eq(&3), Some(3));
+    assert_eq!(iter.peek(), Some(&4));
+
+    assert_eq!(iter.next_if(|&x| x != 4), None);
+    assert_eq!(iter.next_if_eq(&4), Some(4));
+    assert_eq!(iter.peek_nth(0), Some(&5));
+    assert_eq!(iter.peek_nth(1), Some(&6));
+
+    assert_eq!(iter.next_if(|&x| x != 5), None);
+    assert_eq!(iter.peek(), Some(&5));
+
+    assert_eq!(iter.next_if(|&x| x % 2 == 1), Some(5));
+    assert_eq!(iter.next_if_eq(&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);
+
+    let v: Vec<usize> = vec![0, 1, 2];
+    let r = v.into_iter().pad_using(5, |n| n);
+    it::assert_equal(r, vec![0, 1, 2, 3, 4]);
+
+    let v: Vec<usize> = vec![0, 1, 2];
+    let r = v.into_iter().pad_using(1, |_| panic!());
+    it::assert_equal(r, vec![0, 1, 2]);
+}
+
+#[test]
+fn chunk_by() {
+    for (ch1, sub) in &"AABBCCC".chars().chunk_by(|&x| x) {
+        for ch2 in sub {
+            assert_eq!(ch1, ch2);
+        }
+    }
+
+    for (ch1, sub) in &"AAABBBCCCCDDDD".chars().chunk_by(|&x| x) {
+        for ch2 in sub {
+            assert_eq!(ch1, ch2);
+            if ch1 == 'C' {
+                break;
+            }
+        }
+    }
+
+    let toupper = |ch: &char| ch.to_uppercase().next().unwrap();
+
+    // try all possible orderings
+    for indices in permutohedron::Heap::new(&mut [0, 1, 2, 3]) {
+        let chunks = "AaaBbbccCcDDDD".chars().chunk_by(&toupper);
+        let mut subs = chunks.into_iter().collect_vec();
+
+        for &idx in &indices[..] {
+            let (key, text) = match idx {
+                0 => ('A', "Aaa".chars()),
+                1 => ('B', "Bbb".chars()),
+                2 => ('C', "ccCc".chars()),
+                3 => ('D', "DDDD".chars()),
+                _ => unreachable!(),
+            };
+            assert_eq!(key, subs[idx].0);
+            it::assert_equal(&mut subs[idx].1, text);
+        }
+    }
+
+    let chunks = "AAABBBCCCCDDDD".chars().chunk_by(|&x| x);
+    let mut subs = chunks.into_iter().map(|(_, g)| g).collect_vec();
+
+    let sd = subs.pop().unwrap();
+    let sc = subs.pop().unwrap();
+    let sb = subs.pop().unwrap();
+    let sa = subs.pop().unwrap();
+    for (a, b, c, d) in multizip((sa, sb, sc, sd)) {
+        assert_eq!(a, 'A');
+        assert_eq!(b, 'B');
+        assert_eq!(c, 'C');
+        assert_eq!(d, 'D');
+    }
+
+    // check that the key closure is called exactly n times
+    {
+        let mut ntimes = 0;
+        let text = "AABCCC";
+        for (_, sub) in &text.chars().chunk_by(|&x| {
+            ntimes += 1;
+            x
+        }) {
+            for _ in sub {}
+        }
+        assert_eq!(ntimes, text.len());
+    }
+
+    {
+        let mut ntimes = 0;
+        let text = "AABCCC";
+        for _ in &text.chars().chunk_by(|&x| {
+            ntimes += 1;
+            x
+        }) {}
+        assert_eq!(ntimes, text.len());
+    }
+
+    {
+        let text = "ABCCCDEEFGHIJJKK";
+        let gr = text.chars().chunk_by(|&x| x);
+        it::assert_equal(gr.into_iter().flat_map(|(_, sub)| sub), text.chars());
+    }
+}
+
+#[test]
+fn chunk_by_lazy_2() {
+    let data = [0, 1];
+    let chunks = data.iter().chunk_by(|k| *k);
+    let gs = chunks.into_iter().collect_vec();
+    it::assert_equal(data.iter(), gs.into_iter().flat_map(|(_k, g)| g));
+
+    let data = [0, 1, 1, 0, 0];
+    let chunks = data.iter().chunk_by(|k| *k);
+    let mut gs = chunks.into_iter().collect_vec();
+    gs[1..].reverse();
+    it::assert_equal(&[0, 0, 0, 1, 1], gs.into_iter().flat_map(|(_, g)| g));
+
+    let grouper = data.iter().chunk_by(|k| *k);
+    let mut chunks = Vec::new();
+    for (k, chunk) in &grouper {
+        if *k == 1 {
+            chunks.push(chunk);
+        }
+    }
+    it::assert_equal(&mut chunks[0], &[1, 1]);
+
+    let data = [0, 0, 0, 1, 1, 0, 0, 2, 2, 3, 3];
+    let grouper = data.iter().chunk_by(|k| *k);
+    let mut chunks = Vec::new();
+    for (i, (_, chunk)) in grouper.into_iter().enumerate() {
+        if i < 2 {
+            chunks.push(chunk);
+        } else if i < 4 {
+            for _ in chunk {}
+        } else {
+            chunks.push(chunk);
+        }
+    }
+    it::assert_equal(&mut chunks[0], &[0, 0, 0]);
+    it::assert_equal(&mut chunks[1], &[1, 1]);
+    it::assert_equal(&mut chunks[2], &[3, 3]);
+
+    let data = [0, 0, 0, 1, 1, 0, 0, 2, 2, 3, 3];
+    let mut i = 0;
+    let grouper = data.iter().chunk_by(move |_| {
+        let k = i / 3;
+        i += 1;
+        k
+    });
+    for (i, chunk) in &grouper {
+        match i {
+            0 => it::assert_equal(chunk, &[0, 0, 0]),
+            1 => it::assert_equal(chunk, &[1, 1, 0]),
+            2 => it::assert_equal(chunk, &[0, 2, 2]),
+            3 => it::assert_equal(chunk, &[3, 3]),
+            _ => unreachable!(),
+        }
+    }
+}
+
+#[test]
+fn chunk_by_lazy_3() {
+    // test consuming each chunk on the lap after it was produced
+    let data = [0, 0, 0, 1, 1, 0, 0, 1, 1, 2, 2];
+    let grouper = data.iter().chunk_by(|elt| *elt);
+    let mut last = None;
+    for (key, chunk) in &grouper {
+        if let Some(gr) = last.take() {
+            for elt in gr {
+                assert!(elt != key && i32::abs(elt - key) == 1);
+            }
+        }
+        last = Some(chunk);
+    }
+}
+
+#[test]
+fn chunks() {
+    let data = [0, 0, 0, 1, 1, 0, 0, 2, 2, 3, 3];
+    let grouper = data.iter().chunks(3);
+    for (i, chunk) in grouper.into_iter().enumerate() {
+        match i {
+            0 => it::assert_equal(chunk, &[0, 0, 0]),
+            1 => it::assert_equal(chunk, &[1, 1, 0]),
+            2 => it::assert_equal(chunk, &[0, 2, 2]),
+            3 => it::assert_equal(chunk, &[3, 3]),
+            _ => unreachable!(),
+        }
+    }
+}
+
+#[test]
+fn concat_empty() {
+    let data: Vec<Vec<()>> = Vec::new();
+    assert_eq!(data.into_iter().concat(), Vec::new())
+}
+
+#[test]
+fn concat_non_empty() {
+    let data = vec![vec![1, 2, 3], vec![4, 5, 6], vec![7, 8, 9]];
+    assert_eq!(data.into_iter().concat(), vec![1, 2, 3, 4, 5, 6, 7, 8, 9])
+}
+
+#[test]
+fn combinations() {
+    assert!((1..3).combinations(5).next().is_none());
+
+    let it = (1..3).combinations(2);
+    it::assert_equal(it, vec![vec![1, 2]]);
+
+    let it = (1..5).combinations(2);
+    it::assert_equal(
+        it,
+        vec![
+            vec![1, 2],
+            vec![1, 3],
+            vec![1, 4],
+            vec![2, 3],
+            vec![2, 4],
+            vec![3, 4],
+        ],
+    );
+
+    it::assert_equal((0..0).tuple_combinations::<(_, _)>(), <Vec<_>>::new());
+    it::assert_equal((0..1).tuple_combinations::<(_, _)>(), <Vec<_>>::new());
+    it::assert_equal((0..2).tuple_combinations::<(_, _)>(), vec![(0, 1)]);
+
+    it::assert_equal((0..0).combinations(2), <Vec<Vec<_>>>::new());
+    it::assert_equal((0..1).combinations(1), vec![vec![0]]);
+    it::assert_equal((0..2).combinations(1), vec![vec![0], vec![1]]);
+    it::assert_equal((0..2).combinations(2), vec![vec![0, 1]]);
+}
+
+#[test]
+fn combinations_of_too_short() {
+    for i in 1..10 {
+        assert!((0..0).combinations(i).next().is_none());
+        assert!((0..i - 1).combinations(i).next().is_none());
+    }
+}
+
+#[test]
+fn combinations_zero() {
+    it::assert_equal((1..3).combinations(0), vec![vec![]]);
+    it::assert_equal((0..0).combinations(0), vec![vec![]]);
+}
+
+fn binomial(n: usize, k: usize) -> usize {
+    if k > n {
+        0
+    } else {
+        (n - k + 1..=n).product::<usize>() / (1..=k).product::<usize>()
+    }
+}
+
+#[test]
+fn combinations_range_count() {
+    for n in 0..=7 {
+        for k in 0..=7 {
+            let len = binomial(n, k);
+            let mut it = (0..n).combinations(k);
+            assert_eq!(len, it.clone().count());
+            assert_eq!(len, it.size_hint().0);
+            assert_eq!(Some(len), it.size_hint().1);
+            for count in (0..len).rev() {
+                let elem = it.next();
+                assert!(elem.is_some());
+                assert_eq!(count, it.clone().count());
+                assert_eq!(count, it.size_hint().0);
+                assert_eq!(Some(count), it.size_hint().1);
+            }
+            let should_be_none = it.next();
+            assert!(should_be_none.is_none());
+        }
+    }
+}
+
+#[test]
+fn combinations_inexact_size_hints() {
+    for k in 0..=7 {
+        let mut numbers = (0..18).filter(|i| i % 2 == 0); // 9 elements
+        let mut it = numbers.clone().combinations(k);
+        let real_n = numbers.clone().count();
+        let len = binomial(real_n, k);
+        assert_eq!(len, it.clone().count());
+
+        let mut nb_loaded = 0;
+        let sh = numbers.size_hint();
+        assert_eq!(binomial(sh.0 + nb_loaded, k), it.size_hint().0);
+        assert_eq!(sh.1.map(|n| binomial(n + nb_loaded, k)), it.size_hint().1);
+
+        for next_count in 1..=len {
+            let elem = it.next();
+            assert!(elem.is_some());
+            assert_eq!(len - next_count, it.clone().count());
+            if next_count == 1 {
+                // The very first time, the lazy buffer is prefilled.
+                nb_loaded = numbers.by_ref().take(k).count();
+            } else {
+                // Then it loads one item each time until exhausted.
+                let nb = numbers.next();
+                if nb.is_some() {
+                    nb_loaded += 1;
+                }
+            }
+            let sh = numbers.size_hint();
+            if next_count > real_n - k + 1 {
+                assert_eq!(0, sh.0);
+                assert_eq!(Some(0), sh.1);
+                assert_eq!(real_n, nb_loaded);
+                // Once it's fully loaded, size hints of `it` are exacts.
+            }
+            assert_eq!(binomial(sh.0 + nb_loaded, k) - next_count, it.size_hint().0);
+            assert_eq!(
+                sh.1.map(|n| binomial(n + nb_loaded, k) - next_count),
+                it.size_hint().1
+            );
+        }
+        let should_be_none = it.next();
+        assert!(should_be_none.is_none());
+    }
+}
+
+#[test]
+fn permutations_zero() {
+    it::assert_equal((1..3).permutations(0), vec![vec![]]);
+    it::assert_equal((0..0).permutations(0), vec![vec![]]);
+}
+
+#[test]
+fn permutations_range_count() {
+    for n in 0..=4 {
+        for k in 0..=4 {
+            let len = if k <= n { (n - k + 1..=n).product() } else { 0 };
+            let mut it = (0..n).permutations(k);
+            assert_eq!(len, it.clone().count());
+            assert_eq!(len, it.size_hint().0);
+            assert_eq!(Some(len), it.size_hint().1);
+            for count in (0..len).rev() {
+                let elem = it.next();
+                assert!(elem.is_some());
+                assert_eq!(count, it.clone().count());
+                assert_eq!(count, it.size_hint().0);
+                assert_eq!(Some(count), it.size_hint().1);
+            }
+            let should_be_none = it.next();
+            assert!(should_be_none.is_none());
+        }
+    }
+}
+
+#[test]
+fn permutations_overflowed_size_hints() {
+    let mut it = std::iter::repeat(()).permutations(2);
+    assert_eq!(it.size_hint().0, usize::MAX);
+    assert_eq!(it.size_hint().1, None);
+    for nb_generated in 1..=1000 {
+        it.next();
+        assert!(it.size_hint().0 >= usize::MAX - nb_generated);
+        assert_eq!(it.size_hint().1, None);
+    }
+}
+
+#[test]
+#[cfg(not(miri))]
+fn combinations_with_replacement() {
+    // Pool smaller than n
+    it::assert_equal((0..1).combinations_with_replacement(2), vec![vec![0, 0]]);
+    // Pool larger than n
+    it::assert_equal(
+        (0..3).combinations_with_replacement(2),
+        vec![
+            vec![0, 0],
+            vec![0, 1],
+            vec![0, 2],
+            vec![1, 1],
+            vec![1, 2],
+            vec![2, 2],
+        ],
+    );
+    // Zero size
+    it::assert_equal((0..3).combinations_with_replacement(0), vec![vec![]]);
+    // Zero size on empty pool
+    it::assert_equal((0..0).combinations_with_replacement(0), vec![vec![]]);
+    // Empty pool
+    it::assert_equal(
+        (0..0).combinations_with_replacement(2),
+        <Vec<Vec<_>>>::new(),
+    );
+}
+
+#[test]
+fn combinations_with_replacement_range_count() {
+    for n in 0..=4 {
+        for k in 0..=4 {
+            let len = binomial(usize::saturating_sub(n + k, 1), k);
+            let mut it = (0..n).combinations_with_replacement(k);
+            assert_eq!(len, it.clone().count());
+            assert_eq!(len, it.size_hint().0);
+            assert_eq!(Some(len), it.size_hint().1);
+            for count in (0..len).rev() {
+                let elem = it.next();
+                assert!(elem.is_some());
+                assert_eq!(count, it.clone().count());
+                assert_eq!(count, it.size_hint().0);
+                assert_eq!(Some(count), it.size_hint().1);
+            }
+            let should_be_none = it.next();
+            assert!(should_be_none.is_none());
+        }
+    }
+}
+
+#[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);
+
+    for n in 0..=4 {
+        let mut it = (0..n).powerset();
+        let len = 2_usize.pow(n);
+        assert_eq!(len, it.clone().count());
+        assert_eq!(len, it.size_hint().0);
+        assert_eq!(Some(len), it.size_hint().1);
+        for count in (0..len).rev() {
+            let elem = it.next();
+            assert!(elem.is_some());
+            assert_eq!(count, it.clone().count());
+            assert_eq!(count, it.size_hint().0);
+            assert_eq!(Some(count), it.size_hint().1);
+        }
+        let should_be_none = it.next();
+        assert!(should_be_none.is_none());
+    }
+}
+
+#[test]
+fn diff_mismatch() {
+    let a = [1, 2, 3, 4];
+    let b = vec![1.0, 5.0, 3.0, 4.0];
+    let b_map = b.into_iter().map(|f| f as i32);
+    let diff = it::diff_with(a.iter(), b_map, |a, b| *a == b);
+
+    assert!(match diff {
+        Some(it::Diff::FirstMismatch(1, _, from_diff)) =>
+            from_diff.collect::<Vec<_>>() == vec![5, 3, 4],
+        _ => false,
+    });
+}
+
+#[test]
+fn diff_longer() {
+    let a = [1, 2, 3, 4];
+    let b = vec![1.0, 2.0, 3.0, 4.0, 5.0, 6.0];
+    let b_map = b.into_iter().map(|f| f as i32);
+    let diff = it::diff_with(a.iter(), b_map, |a, b| *a == b);
+
+    assert!(match diff {
+        Some(it::Diff::Longer(_, remaining)) => remaining.collect::<Vec<_>>() == vec![5, 6],
+        _ => false,
+    });
+}
+
+#[test]
+fn diff_shorter() {
+    let a = [1, 2, 3, 4];
+    let b = vec![1.0, 2.0];
+    let b_map = b.into_iter().map(|f| f as i32);
+    let diff = it::diff_with(a.iter(), b_map, |a, b| *a == b);
+
+    assert!(match diff {
+        Some(it::Diff::Shorter(len, _)) => len == 2,
+        _ => false,
+    });
+}
+
+#[test]
+fn extrema_set() {
+    use std::cmp::Ordering;
+
+    // A peculiar type: Equality compares both tuple items, but ordering only the
+    // first item. Used to distinguish equal elements.
+    #[derive(Clone, Debug, PartialEq, Eq)]
+    struct Val(u32, u32);
+
+    impl PartialOrd<Self> for Val {
+        fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
+            Some(self.cmp(other))
+        }
+    }
+
+    impl Ord for Val {
+        fn cmp(&self, other: &Self) -> Ordering {
+            self.0.cmp(&other.0)
+        }
+    }
+
+    assert_eq!(None::<u32>.iter().min_set(), Vec::<&u32>::new());
+    assert_eq!(None::<u32>.iter().max_set(), Vec::<&u32>::new());
+
+    assert_eq!(Some(1u32).iter().min_set(), vec![&1]);
+    assert_eq!(Some(1u32).iter().max_set(), vec![&1]);
+
+    let data = [Val(0, 1), Val(2, 0), Val(0, 2), Val(1, 0), Val(2, 1)];
+
+    let min_set = data.iter().min_set();
+    assert_eq!(min_set, vec![&Val(0, 1), &Val(0, 2)]);
+
+    let min_set_by_key = data.iter().min_set_by_key(|v| v.1);
+    assert_eq!(min_set_by_key, vec![&Val(2, 0), &Val(1, 0)]);
+
+    let min_set_by = data.iter().min_set_by(|x, y| x.1.cmp(&y.1));
+    assert_eq!(min_set_by, vec![&Val(2, 0), &Val(1, 0)]);
+
+    let max_set = data.iter().max_set();
+    assert_eq!(max_set, vec![&Val(2, 0), &Val(2, 1)]);
+
+    let max_set_by_key = data.iter().max_set_by_key(|v| v.1);
+    assert_eq!(max_set_by_key, vec![&Val(0, 2)]);
+
+    let max_set_by = data.iter().max_set_by(|x, y| x.1.cmp(&y.1));
+    assert_eq!(max_set_by, vec![&Val(0, 2)]);
+}
+
+#[test]
+fn minmax() {
+    use crate::it::MinMaxResult;
+    use std::cmp::Ordering;
+
+    // A peculiar type: Equality compares both tuple items, but ordering only the
+    // first item.  This is so we can check the stability property easily.
+    #[derive(Clone, Debug, PartialEq, Eq)]
+    struct Val(u32, u32);
+
+    impl PartialOrd<Self> for Val {
+        fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
+            Some(self.cmp(other))
+        }
+    }
+
+    impl Ord for Val {
+        fn cmp(&self, other: &Self) -> Ordering {
+            self.0.cmp(&other.0)
+        }
+    }
+
+    assert_eq!(
+        None::<Option<u32>>.iter().minmax(),
+        MinMaxResult::NoElements
+    );
+
+    assert_eq!(Some(1u32).iter().minmax(), MinMaxResult::OneElement(&1));
+
+    let data = [Val(0, 1), Val(2, 0), Val(0, 2), Val(1, 0), Val(2, 1)];
+
+    let minmax = data.iter().minmax();
+    assert_eq!(minmax, MinMaxResult::MinMax(&Val(0, 1), &Val(2, 1)));
+
+    let (min, max) = data.iter().minmax_by_key(|v| v.1).into_option().unwrap();
+    assert_eq!(min, &Val(2, 0));
+    assert_eq!(max, &Val(0, 2));
+
+    let (min, max) = data
+        .iter()
+        .minmax_by(|x, y| x.1.cmp(&y.1))
+        .into_option()
+        .unwrap();
+    assert_eq!(min, &Val(2, 0));
+    assert_eq!(max, &Val(0, 2));
+}
+
+#[test]
+fn format() {
+    let data = [0, 1, 2, 3];
+    let ans1 = "0, 1, 2, 3";
+    let ans2 = "0--1--2--3";
+
+    let t1 = format!("{}", data.iter().format(", "));
+    assert_eq!(t1, ans1);
+    let t2 = format!("{:?}", data.iter().format("--"));
+    assert_eq!(t2, ans2);
+
+    let dataf = [1.1, 5.71828, -22.];
+    let t3 = format!("{:.2e}", dataf.iter().format(", "));
+    assert_eq!(t3, "1.10e0, 5.72e0, -2.20e1");
+}
+
+#[test]
+fn while_some() {
+    let ns = (1..10)
+        .map(|x| if x % 5 != 0 { Some(x) } else { None })
+        .while_some();
+    it::assert_equal(ns, vec![1, 2, 3, 4]);
+}
+
+#[test]
+fn fold_while() {
+    let mut iterations = 0;
+    let vec = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
+    let sum = vec
+        .into_iter()
+        .fold_while(0, |acc, item| {
+            iterations += 1;
+            let new_sum = acc + item;
+            if new_sum <= 20 {
+                FoldWhile::Continue(new_sum)
+            } else {
+                FoldWhile::Done(acc)
+            }
+        })
+        .into_inner();
+    assert_eq!(iterations, 6);
+    assert_eq!(sum, 15);
+}
+
+#[test]
+fn tree_reduce() {
+    let x = [
+        "",
+        "0",
+        "0 1 x",
+        "0 1 x 2 x",
+        "0 1 x 2 3 x x",
+        "0 1 x 2 3 x x 4 x",
+        "0 1 x 2 3 x x 4 5 x x",
+        "0 1 x 2 3 x x 4 5 x 6 x x",
+        "0 1 x 2 3 x x 4 5 x 6 7 x x x",
+        "0 1 x 2 3 x x 4 5 x 6 7 x x x 8 x",
+        "0 1 x 2 3 x x 4 5 x 6 7 x x x 8 9 x x",
+        "0 1 x 2 3 x x 4 5 x 6 7 x x x 8 9 x 10 x x",
+        "0 1 x 2 3 x x 4 5 x 6 7 x x x 8 9 x 10 11 x x x",
+        "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",
+        "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",
+        "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",
+        "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",
+    ];
+    for (i, &s) in x.iter().enumerate() {
+        let expected = if s.is_empty() {
+            None
+        } else {
+            Some(s.to_string())
+        };
+        let num_strings = (0..i).map(|x| x.to_string());
+        let actual = num_strings.tree_reduce(|a, b| format!("{} {} x", a, b));
+        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(())
+}
+
+#[test]
+fn multiunzip() {
+    let (a, b, c): (Vec<_>, Vec<_>, Vec<_>) = [(0, 1, 2), (3, 4, 5), (6, 7, 8)]
+        .iter()
+        .cloned()
+        .multiunzip();
+    assert_eq!((a, b, c), (vec![0, 3, 6], vec![1, 4, 7], vec![2, 5, 8]));
+    let (): () = [(), (), ()].iter().cloned().multiunzip();
+    #[allow(clippy::type_complexity)]
+    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();
+    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]
+        )
+    );
+}
diff --git a/vendor/itertools/tests/tuples.rs b/vendor/itertools/tests/tuples.rs
new file mode 100644
index 00000000..9fc8b3cc
--- /dev/null
+++ b/vendor/itertools/tests/tuples.rs
@@ -0,0 +1,86 @@
+use itertools::Itertools;
+
+#[test]
+fn tuples() {
+    let v = [1, 2, 3, 4, 5];
+    let mut iter = v.iter().cloned().tuples();
+    assert_eq!(Some((1,)), iter.next());
+    assert_eq!(Some((2,)), iter.next());
+    assert_eq!(Some((3,)), iter.next());
+    assert_eq!(Some((4,)), iter.next());
+    assert_eq!(Some((5,)), iter.next());
+    assert_eq!(None, iter.next());
+    assert_eq!(None, iter.into_buffer().next());
+
+    let mut iter = v.iter().cloned().tuples();
+    assert_eq!(Some((1, 2)), iter.next());
+    assert_eq!(Some((3, 4)), iter.next());
+    assert_eq!(None, iter.next());
+    itertools::assert_equal(vec![5], iter.into_buffer());
+
+    let mut iter = v.iter().cloned().tuples();
+    assert_eq!(Some((1, 2, 3)), iter.next());
+    assert_eq!(None, iter.next());
+    itertools::assert_equal(vec![4, 5], iter.into_buffer());
+
+    let mut iter = v.iter().cloned().tuples();
+    assert_eq!(Some((1, 2, 3, 4)), iter.next());
+    assert_eq!(None, iter.next());
+    itertools::assert_equal(vec![5], iter.into_buffer());
+}
+
+#[test]
+fn tuple_windows() {
+    let v = [1, 2, 3, 4, 5];
+
+    let mut iter = v.iter().cloned().tuple_windows();
+    assert_eq!(Some((1,)), iter.next());
+    assert_eq!(Some((2,)), iter.next());
+    assert_eq!(Some((3,)), iter.next());
+
+    let mut iter = v.iter().cloned().tuple_windows();
+    assert_eq!(Some((1, 2)), iter.next());
+    assert_eq!(Some((2, 3)), iter.next());
+    assert_eq!(Some((3, 4)), iter.next());
+    assert_eq!(Some((4, 5)), iter.next());
+    assert_eq!(None, iter.next());
+
+    let mut iter = v.iter().cloned().tuple_windows();
+    assert_eq!(Some((1, 2, 3)), iter.next());
+    assert_eq!(Some((2, 3, 4)), iter.next());
+    assert_eq!(Some((3, 4, 5)), iter.next());
+    assert_eq!(None, iter.next());
+
+    let mut iter = v.iter().cloned().tuple_windows();
+    assert_eq!(Some((1, 2, 3, 4)), iter.next());
+    assert_eq!(Some((2, 3, 4, 5)), iter.next());
+    assert_eq!(None, iter.next());
+
+    let v = [1, 2, 3];
+    let mut iter = v.iter().cloned().tuple_windows::<(_, _, _, _)>();
+    assert_eq!(None, iter.next());
+}
+
+#[test]
+fn next_tuple() {
+    let v = [1, 2, 3, 4, 5];
+    let mut iter = v.iter();
+    assert_eq!(iter.next_tuple().map(|(&x, &y)| (x, y)), Some((1, 2)));
+    assert_eq!(iter.next_tuple().map(|(&x, &y)| (x, y)), Some((3, 4)));
+    assert_eq!(iter.next_tuple::<(_, _)>(), None);
+}
+
+#[test]
+fn collect_tuple() {
+    let v = [1, 2];
+    let iter = v.iter().cloned();
+    assert_eq!(iter.collect_tuple(), Some((1, 2)));
+
+    let v = [1];
+    let iter = v.iter().cloned();
+    assert_eq!(iter.collect_tuple::<(_, _)>(), None);
+
+    let v = [1, 2, 3];
+    let iter = v.iter().cloned();
+    assert_eq!(iter.collect_tuple::<(_, _)>(), None);
+}
diff --git a/vendor/itertools/tests/zip.rs b/vendor/itertools/tests/zip.rs
new file mode 100644
index 00000000..daed31e3
--- /dev/null
+++ b/vendor/itertools/tests/zip.rs
@@ -0,0 +1,56 @@
+use itertools::multizip;
+use itertools::EitherOrBoth::{Both, Left, Right};
+use itertools::Itertools;
+
+#[test]
+fn zip_longest_fused() {
+    let a = [Some(1), None, Some(3), Some(4)];
+    let b = [1, 2, 3];
+
+    let unfused = a
+        .iter()
+        .batching(|it| *it.next().unwrap())
+        .zip_longest(b.iter().cloned());
+    itertools::assert_equal(unfused, vec![Both(1, 1), Right(2), Right(3)]);
+}
+
+#[test]
+fn test_zip_longest_size_hint() {
+    let c = (1..10).cycle();
+    let v: &[_] = &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
+    let v2 = &[10, 11, 12];
+
+    assert_eq!(c.zip_longest(v.iter()).size_hint(), (usize::MAX, None));
+
+    assert_eq!(v.iter().zip_longest(v2.iter()).size_hint(), (10, Some(10)));
+}
+
+#[test]
+fn test_double_ended_zip_longest() {
+    let xs = [1, 2, 3, 4, 5, 6];
+    let ys = [1, 2, 3, 7];
+    let a = xs.iter().copied();
+    let b = ys.iter().copied();
+    let mut it = a.zip_longest(b);
+    assert_eq!(it.next(), Some(Both(1, 1)));
+    assert_eq!(it.next(), Some(Both(2, 2)));
+    assert_eq!(it.next_back(), Some(Left(6)));
+    assert_eq!(it.next_back(), Some(Left(5)));
+    assert_eq!(it.next_back(), Some(Both(4, 7)));
+    assert_eq!(it.next(), Some(Both(3, 3)));
+    assert_eq!(it.next(), None);
+}
+
+#[test]
+fn test_double_ended_zip() {
+    let xs = [1, 2, 3, 4, 5, 6];
+    let ys = [1, 2, 3, 7];
+    let a = xs.iter().copied();
+    let b = ys.iter().copied();
+    let mut it = multizip((a, b));
+    assert_eq!(it.next_back(), Some((4, 7)));
+    assert_eq!(it.next_back(), Some((3, 3)));
+    assert_eq!(it.next_back(), Some((2, 2)));
+    assert_eq!(it.next_back(), Some((1, 1)));
+    assert_eq!(it.next_back(), None);
+}