#![warn(missing_docs)]

#![crate_name="itertools"]

#![cfg_attr(not(feature = "use_std"), no_std)]

//! Extra iterator adaptors, functions and macros.

//!

//! To extend [`Iterator`] with methods in this crate, import

//! the [`Itertools`] trait:

//!

//! ```

//! use itertools::Itertools;

//! ```

//!

//! Now, new methods like [`interleave`](Itertools::interleave)

//! are available on all iterators:

//!

//! ```

//! use itertools::Itertools;

//!

//! let it = (1..3).interleave(vec![-1, -2]);

//! itertools::assert_equal(it, vec![1, -1, 2, -2]);

//! ```

//!

//! Most iterator methods are also provided as functions (with the benefit

//! that they convert parameters using [`IntoIterator`]):

//!

//! ```

//! use itertools::interleave;

//!

//! for elt in interleave(&[1, 2, 3], &[2, 3, 4]) {

//!     /* loop body */

//! }

//! ```

//!

//! ## Crate Features

//!

//! - `use_std`

//!   - Enabled by default.

//!   - Disable to compile itertools using `#![no_std]`. This disables

//!     any items that depend on collections (like `group_by`, `unique`,

//!     `kmerge`, `join` and many more).

//!

//! ## Rust Version

//!

//! This version of itertools requires Rust 1.32 or later.

#![doc(html_root_url="https://docs.rs/itertools/0.8/")]

#[cfg(not(feature = "use_std"))]

extern crate core as std;

#[cfg(feature = "use_alloc")]

extern crate alloc;

#[cfg(feature = "use_alloc")]

use alloc::{

    string::String,

    vec::Vec,

};

pub use either::Either;

use core::borrow::Borrow;

#[cfg(feature = "use_std")]

use std::collections::HashMap;

use std::iter::{IntoIterator, once};

use std::cmp::Ordering;

use std::fmt;

#[cfg(feature = "use_std")]

use std::collections::HashSet;

#[cfg(feature = "use_std")]

use std::hash::Hash;

#[cfg(feature = "use_alloc")]

use std::fmt::Write;

#[cfg(feature = "use_alloc")]

type VecIntoIter<T> = alloc::vec::IntoIter<T>;

#[cfg(feature = "use_alloc")]

use std::iter::FromIterator;

#[macro_use]

mod impl_macros;

// for compatibility with no std and macros

#[doc(hidden)]

pub use std::iter as __std_iter;

/// The concrete iterator types.

pub mod structs {

    pub use crate::adaptors::{

        Dedup,

        DedupBy,

        DedupWithCount,

        DedupByWithCount,

        Interleave,

        InterleaveShortest,

        FilterMapOk,

        FilterOk,

        Product,

        PutBack,

        Batching,

        MapInto,

        MapOk,

        Merge,

        MergeBy,

        TakeWhileRef,

        WhileSome,

        Coalesce,

        TupleCombinations,

        Positions,

        Update,

    };

    #[allow(deprecated)]

    pub use crate::adaptors::{MapResults, Step};

    #[cfg(feature = "use_alloc")]

    pub use crate::adaptors::MultiProduct;

    #[cfg(feature = "use_alloc")]

    pub use crate::combinations::Combinations;

    #[cfg(feature = "use_alloc")]

    pub use crate::combinations_with_replacement::CombinationsWithReplacement;

    pub use crate::cons_tuples_impl::ConsTuples;

    pub use crate::exactly_one_err::ExactlyOneError;

    pub use crate::format::{Format, FormatWith};

    pub use crate::flatten_ok::FlattenOk;

    #[cfg(feature = "use_std")]

    pub use crate::grouping_map::{GroupingMap, GroupingMapBy};

    #[cfg(feature = "use_alloc")]

    pub use crate::groupbylazy::{IntoChunks, Chunk, Chunks, GroupBy, Group, Groups};

    pub use crate::intersperse::{Intersperse, IntersperseWith};

    #[cfg(feature = "use_alloc")]

    pub use crate::kmerge_impl::{KMerge, KMergeBy};

    pub use crate::merge_join::MergeJoinBy;

    #[cfg(feature = "use_alloc")]

    pub use crate::multipeek_impl::MultiPeek;

    #[cfg(feature = "use_alloc")]

    pub use crate::peek_nth::PeekNth;

    pub use crate::pad_tail::PadUsing;

    pub use crate::peeking_take_while::PeekingTakeWhile;

    #[cfg(feature = "use_alloc")]

    pub use crate::permutations::Permutations;

    pub use crate::process_results_impl::ProcessResults;

    #[cfg(feature = "use_alloc")]

    pub use crate::powerset::Powerset;

    #[cfg(feature = "use_alloc")]

    pub use crate::put_back_n_impl::PutBackN;

    #[cfg(feature = "use_alloc")]

    pub use crate::rciter_impl::RcIter;

    pub use crate::repeatn::RepeatN;

    #[allow(deprecated)]

    pub use crate::sources::{RepeatCall, Unfold, Iterate};

    pub use crate::take_while_inclusive::TakeWhileInclusive;

    #[cfg(feature = "use_alloc")]

    pub use crate::tee::Tee;

    pub use crate::tuple_impl::{TupleBuffer, TupleWindows, CircularTupleWindows, Tuples};

    #[cfg(feature = "use_std")]

    pub use crate::duplicates_impl::{Duplicates, DuplicatesBy};

    #[cfg(feature = "use_std")]

    pub use crate::unique_impl::{Unique, UniqueBy};

    pub use crate::with_position::WithPosition;

    pub use crate::zip_eq_impl::ZipEq;

    pub use crate::zip_longest::ZipLongest;

    pub use crate::ziptuple::Zip;

}

/// Traits helpful for using certain `Itertools` methods in generic contexts.

pub mod traits {

    pub use crate::tuple_impl::HomogeneousTuple;

}

#[allow(deprecated)]

pub use crate::structs::*;

pub use crate::concat_impl::concat;

pub use crate::cons_tuples_impl::cons_tuples;

pub use crate::diff::diff_with;

pub use crate::diff::Diff;

#[cfg(feature = "use_alloc")]

pub use crate::kmerge_impl::{kmerge_by};

pub use crate::minmax::MinMaxResult;

pub use crate::peeking_take_while::PeekingNext;

pub use crate::process_results_impl::process_results;

pub use crate::repeatn::repeat_n;

#[allow(deprecated)]

pub use crate::sources::{repeat_call, unfold, iterate};

pub use crate::with_position::Position;

pub use crate::unziptuple::{multiunzip, MultiUnzip};

pub use crate::ziptuple::multizip;

mod adaptors;

mod either_or_both;

pub use crate::either_or_both::EitherOrBoth;

#[doc(hidden)]

pub mod free;

#[doc(inline)]

pub use crate::free::*;

mod concat_impl;

mod cons_tuples_impl;

#[cfg(feature = "use_alloc")]

mod combinations;

#[cfg(feature = "use_alloc")]

mod combinations_with_replacement;

mod exactly_one_err;

mod diff;

mod flatten_ok;

#[cfg(feature = "use_std")]

mod extrema_set;

mod format;

#[cfg(feature = "use_std")]

mod grouping_map;

#[cfg(feature = "use_alloc")]

mod group_map;

#[cfg(feature = "use_alloc")]

mod groupbylazy;

mod intersperse;

#[cfg(feature = "use_alloc")]

mod k_smallest;

#[cfg(feature = "use_alloc")]

mod kmerge_impl;

#[cfg(feature = "use_alloc")]

mod lazy_buffer;

mod merge_join;

mod minmax;

#[cfg(feature = "use_alloc")]

mod multipeek_impl;

mod pad_tail;

#[cfg(feature = "use_alloc")]

mod peek_nth;

mod peeking_take_while;

#[cfg(feature = "use_alloc")]

mod permutations;

#[cfg(feature = "use_alloc")]

mod powerset;

mod process_results_impl;

#[cfg(feature = "use_alloc")]

mod put_back_n_impl;

#[cfg(feature = "use_alloc")]

mod rciter_impl;

mod repeatn;

mod size_hint;

mod sources;

mod take_while_inclusive;

#[cfg(feature = "use_alloc")]

mod tee;

mod tuple_impl;

#[cfg(feature = "use_std")]

mod duplicates_impl;

#[cfg(feature = "use_std")]

mod unique_impl;

mod unziptuple;

mod with_position;

mod zip_eq_impl;

mod zip_longest;

mod ziptuple;

#[macro_export]

/// Create an iterator over the “cartesian product” of iterators.

///

/// Iterator element type is like `(A, B, ..., E)` if formed

/// from iterators `(I, J, ..., M)` with element types `I::Item = A`, `J::Item = B`, etc.

///

/// ```

/// # use itertools::iproduct;

/// #

/// # fn main() {

/// // Iterate over the coordinates of a 4 x 4 x 4 grid

/// // from (0, 0, 0), (0, 0, 1), .., (0, 1, 0), (0, 1, 1), .. etc until (3, 3, 3)

/// for (i, j, k) in iproduct!(0..4, 0..4, 0..4) {

///    // ..

/// }

/// # }

/// ```

macro_rules! iproduct {

    (@flatten $I:expr,) => (

        $I

    );

    (@flatten $I:expr, $J:expr, $($K:expr,)*) => (

        $crate::iproduct!(@flatten $crate::cons_tuples($crate::iproduct!($I, $J)), $($K,)*)

    );

    ($I:expr) => (

        $crate::__std_iter::IntoIterator::into_iter($I)

    );

    ($I:expr, $J:expr) => (

        $crate::Itertools::cartesian_product($crate::iproduct!($I), $crate::iproduct!($J))

    );

    ($I:expr, $J:expr, $($K:expr),+) => (

        $crate::iproduct!(@flatten $crate::iproduct!($I, $J), $($K,)+)

    );

}

#[macro_export]

/// Create an iterator running multiple iterators in lockstep.

///

/// The `izip!` iterator yields elements until any subiterator

/// returns `None`.

///

/// This is a version of the standard ``.zip()`` that's supporting more than

/// two iterators. The iterator element type is a tuple with one element

/// from each of the input iterators. Just like ``.zip()``, the iteration stops

/// when the shortest of the inputs reaches its end.

///

/// **Note:** The result of this macro is in the general case an iterator

/// composed of repeated `.zip()` and a `.map()`; it has an anonymous type.

/// The special cases of one and two arguments produce the equivalent of

/// `$a.into_iter()` and `$a.into_iter().zip($b)` respectively.

///

/// Prefer this macro `izip!()` over [`multizip`] for the performance benefits

/// of using the standard library `.zip()`.

///

/// ```

/// # use itertools::izip;

/// #

/// # fn main() {

///

/// // iterate over three sequences side-by-side

/// let mut results = [0, 0, 0, 0];

/// let inputs = [3, 7, 9, 6];

///

/// for (r, index, input) in izip!(&mut results, 0..10, &inputs) {

///     *r = index * 10 + input;

/// }

///

/// assert_eq!(results, [0 + 3, 10 + 7, 29, 36]);

/// # }

/// ```

macro_rules! izip {

    // @closure creates a tuple-flattening closure for .map() call. usage:

    // @closure partial_pattern => partial_tuple , rest , of , iterators

    // eg. izip!( @closure ((a, b), c) => (a, b, c) , dd , ee )

    ( @closure $p:pat => $tup:expr ) => {

        |$p| $tup

    };

    // The "b" identifier is a different identifier on each recursion level thanks to hygiene.

    ( @closure $p:pat => ( $($tup:tt)* ) , $_iter:expr $( , $tail:expr )* ) => {

        $crate::izip!(@closure ($p, b) => ( $($tup)*, b ) $( , $tail )*)

    };

    // unary

    ($first:expr $(,)*) => {

        $crate::__std_iter::IntoIterator::into_iter($first)

    };

    // binary

    ($first:expr, $second:expr $(,)*) => {

        $crate::izip!($first)

            .zip($second)

    };

    // n-ary where n > 2

    ( $first:expr $( , $rest:expr )* $(,)* ) => {

        $crate::izip!($first)

            $(

                .zip($rest)

            )*

            .map(

                $crate::izip!(@closure a => (a) $( , $rest )*)

            )

    };

}

#[macro_export]

/// [Chain][`chain`] zero or more iterators together into one sequence.

///

/// The comma-separated arguments must implement [`IntoIterator`].

/// The final argument may be followed by a trailing comma.

///

/// [`chain`]: Iterator::chain

///

/// # Examples

///

/// Empty invocations of `chain!` expand to an invocation of [`std::iter::empty`]:

/// ```

/// use std::iter;

/// use itertools::chain;

///

/// let _: iter::Empty<()> = chain!();

/// let _: iter::Empty<i8> = chain!();

/// ```

///

/// Invocations of `chain!` with one argument expand to [`arg.into_iter()`](IntoIterator):

/// ```

/// use std::{ops::Range, slice};

/// use itertools::chain;

/// let _: <Range<_> as IntoIterator>::IntoIter = chain!((2..6),); // trailing comma optional!

/// let _:     <&[_] as IntoIterator>::IntoIter = chain!(&[2, 3, 4]);

/// ```

///

/// Invocations of `chain!` with multiple arguments [`.into_iter()`](IntoIterator) each

/// argument, and then [`chain`] them together:

/// ```

/// use std::{iter::*, ops::Range, slice};

/// use itertools::{assert_equal, chain};

///

/// // e.g., this:

/// let with_macro:  Chain<Chain<Once<_>, Take<Repeat<_>>>, slice::Iter<_>> =

///     chain![once(&0), repeat(&1).take(2), &[2, 3, 5],];

///

/// // ...is equivalent to this:

/// let with_method: Chain<Chain<Once<_>, Take<Repeat<_>>>, slice::Iter<_>> =

///     once(&0)

///         .chain(repeat(&1).take(2))

///         .chain(&[2, 3, 5]);

///

/// assert_equal(with_macro, with_method);

/// ```

macro_rules! chain {

    () => {

        core::iter::empty()

    };

    ($first:expr $(, $rest:expr )* $(,)?) => {

        {

            let iter = core::iter::IntoIterator::into_iter($first);

            $(

                let iter =

                    core::iter::Iterator::chain(

                        iter,

                        core::iter::IntoIterator::into_iter($rest));

            )*

            iter

        }

    };

}

/// An [`Iterator`] blanket implementation that provides extra adaptors and

/// methods.

///

/// This trait defines a number of methods. They are divided into two groups:

///

/// * *Adaptors* take an iterator and parameter as input, and return

/// a new iterator value. These are listed first in the trait. An example

/// of an adaptor is [`.interleave()`](Itertools::interleave)

///

/// * *Regular methods* are those that don't return iterators and instead

/// return a regular value of some other kind.

/// [`.next_tuple()`](Itertools::next_tuple) is an example and the first regular

/// method in the list.

pub trait Itertools : Iterator {

    // adaptors

    /// Alternate elements from two iterators until both have run out.

    ///

    /// Iterator element type is `Self::Item`.

    ///

    /// This iterator is *fused*.

    ///

    /// ```

    /// use itertools::Itertools;

    ///

    /// let it = (1..7).interleave(vec![-1, -2]);

    /// itertools::assert_equal(it, vec![1, -1, 2, -2, 3, 4, 5, 6]);

    /// ```

    fn interleave<J>(self, other: J) -> Interleave<Self, J::IntoIter>

        where J: IntoIterator<Item = Self::Item>,

              Self: Sized

    {

        interleave(self, other)

    }

    /// Alternate elements from two iterators until at least one of them has run

    /// out.

    ///

    /// Iterator element type is `Self::Item`.

    ///

    /// ```

    /// use itertools::Itertools;

    ///

    /// let it = (1..7).interleave_shortest(vec![-1, -2]);

    /// itertools::assert_equal(it, vec![1, -1, 2, -2, 3]);

    /// ```

    fn interleave_shortest<J>(self, other: J) -> InterleaveShortest<Self, J::IntoIter>

        where J: IntoIterator<Item = Self::Item>,

              Self: Sized

    {

        adaptors::interleave_shortest(self, other.into_iter())

    }

    /// An iterator adaptor to insert a particular value

    /// between each element of the adapted iterator.

    ///

    /// Iterator element type is `Self::Item`.

    ///

    /// This iterator is *fused*.

    ///

    /// ```

    /// use itertools::Itertools;

    ///

    /// itertools::assert_equal((0..3).intersperse(8), vec![0, 8, 1, 8, 2]);

    /// ```

    fn intersperse(self, element: Self::Item) -> Intersperse<Self>

        where Self: Sized,

              Self::Item: Clone

    {

        intersperse::intersperse(self, element)

    }

    /// An iterator adaptor to insert a particular value created by a function

    /// between each element of the adapted iterator.

    ///

    /// Iterator element type is `Self::Item`.

    ///

    /// This iterator is *fused*.

    ///

    /// ```

    /// use itertools::Itertools;

    ///

    /// let mut i = 10;

    /// itertools::assert_equal((0..3).intersperse_with(|| { i -= 1; i }), vec![0, 9, 1, 8, 2]);

    /// assert_eq!(i, 8);

    /// ```

    fn intersperse_with<F>(self, element: F) -> IntersperseWith<Self, F>

        where Self: Sized,

        F: FnMut() -> Self::Item

    {

        intersperse::intersperse_with(self, element)

    }

    /// Create an iterator which iterates over both this and the specified

    /// iterator simultaneously, yielding pairs of two optional elements.

    ///

    /// This iterator is *fused*.

    ///

    /// As long as neither input iterator is exhausted yet, it yields two values

    /// via `EitherOrBoth::Both`.

    ///

    /// When the parameter iterator is exhausted, it only yields a value from the

    /// `self` iterator via `EitherOrBoth::Left`.

    ///

    /// When the `self` iterator is exhausted, it only yields a value from the

    /// parameter iterator via `EitherOrBoth::Right`.

    ///

    /// When both iterators return `None`, all further invocations of `.next()`

    /// will return `None`.

    ///

    /// Iterator element type is

    /// [`EitherOrBoth<Self::Item, J::Item>`](EitherOrBoth).

    ///

    /// ```rust

    /// use itertools::EitherOrBoth::{Both, Right};

    /// use itertools::Itertools;

    /// let it = (0..1).zip_longest(1..3);

    /// itertools::assert_equal(it, vec![Both(0, 1), Right(2)]);

    /// ```

    #[inline]

    fn zip_longest<J>(self, other: J) -> ZipLongest<Self, J::IntoIter>

        where J: IntoIterator,

              Self: Sized

    {

        zip_longest::zip_longest(self, other.into_iter())

    }

    /// Create an iterator which iterates over both this and the specified

    /// iterator simultaneously, yielding pairs of elements.

    ///

    /// **Panics** if the iterators reach an end and they are not of equal

    /// lengths.

    #[inline]

    fn zip_eq<J>(self, other: J) -> ZipEq<Self, J::IntoIter>

        where J: IntoIterator,

              Self: Sized

    {

        zip_eq(self, other)

    }

    /// A “meta iterator adaptor”. Its closure receives a reference to the

    /// iterator and may pick off as many elements as it likes, to produce the

    /// next iterator element.

    ///

    /// Iterator element type is `B`.

    ///

    /// ```

    /// use itertools::Itertools;

    ///

    /// // An adaptor that gathers elements in pairs

    /// let pit = (0..4).batching(|it| {

    ///            match it.next() {

    ///                None => None,

    ///                Some(x) => match it.next() {

    ///                    None => None,

    ///                    Some(y) => Some((x, y)),

    ///                }

    ///            }

    ///        });

    ///

    /// itertools::assert_equal(pit, vec![(0, 1), (2, 3)]);

    /// ```

    ///

    fn batching<B, F>(self, f: F) -> Batching<Self, F>

        where F: FnMut(&mut Self) -> Option<B>,

              Self: Sized

    {

        adaptors::batching(self, f)

    }

    /// Return an *iterable* that can group iterator elements.

    /// Consecutive elements that map to the same key (“runs”), are assigned

    /// to the same group.

    ///

    /// `GroupBy` is the storage for the lazy grouping operation.

    ///

    /// If the groups are consumed in order, or if each group's iterator is

    /// dropped without keeping it around, then `GroupBy` uses no

    /// allocations.  It needs allocations only if several group iterators

    /// are alive at the same time.

    ///

    /// This type implements [`IntoIterator`] (it is **not** an iterator

    /// itself), because the group iterators need to borrow from this

    /// value. It should be stored in a local variable or temporary and

    /// iterated.

    ///

    /// Iterator element type is `(K, Group)`: the group's key and the

    /// group iterator.

    ///

    /// ```

    /// use itertools::Itertools;

    ///

    /// // group data into runs of larger than zero or not.

    /// let data = vec![1, 3, -2, -2, 1, 0, 1, 2];

    /// // groups:     |---->|------>|--------->|

    ///

    /// // Note: The `&` is significant here, `GroupBy` is iterable

    /// // only by reference. You can also call `.into_iter()` explicitly.

    /// let mut data_grouped = Vec::new();

    /// for (key, group) in &data.into_iter().group_by(|elt| *elt >= 0) {

    ///     data_grouped.push((key, group.collect()));

    /// }

    /// assert_eq!(data_grouped, vec![(true, vec![1, 3]), (false, vec![-2, -2]), (true, vec![1, 0, 1, 2])]);

    /// ```

    #[cfg(feature = "use_alloc")]

    fn group_by<K, F>(self, key: F) -> GroupBy<K, Self, F>

        where Self: Sized,

              F: FnMut(&Self::Item) -> K,

              K: PartialEq,

    {

        groupbylazy::new(self, key)

    }

    /// Return an *iterable* that can chunk the iterator.

    ///

    /// Yield subiterators (chunks) that each yield a fixed number elements,

    /// determined by `size`. The last chunk will be shorter if there aren't

    /// enough elements.

    ///

    /// `IntoChunks` is based on `GroupBy`: it is iterable (implements

    /// `IntoIterator`, **not** `Iterator`), and it only buffers if several

    /// chunk iterators are alive at the same time.

    ///

    /// Iterator element type is `Chunk`, each chunk's iterator.

    ///

    /// **Panics** if `size` is 0.

    ///

    /// ```

    /// use itertools::Itertools;

    ///

    /// let data = vec![1, 1, 2, -2, 6, 0, 3, 1];

    /// //chunk size=3 |------->|-------->|--->|

    ///

    /// // Note: The `&` is significant here, `IntoChunks` is iterable

    /// // only by reference. You can also call `.into_iter()` explicitly.

    /// for chunk in &data.into_iter().chunks(3) {

    ///     // Check that the sum of each chunk is 4.

    ///     assert_eq!(4, chunk.sum());

    /// }

    /// ```

    #[cfg(feature = "use_alloc")]

    fn chunks(self, size: usize) -> IntoChunks<Self>

        where Self: Sized,

    {

        assert!(size != 0);

        groupbylazy::new_chunks(self, size)

    }

    /// Return an iterator over all contiguous windows producing tuples of

    /// a specific size (up to 12).

    ///

    /// `tuple_windows` clones the iterator elements so that they can be

    /// part of successive windows, this makes it most suited for iterators

    /// of references and other values that are cheap to copy.

    ///

    /// ```

    /// use itertools::Itertools;

    /// let mut v = Vec::new();

    ///

    /// // pairwise iteration

    /// for (a, b) in (1..5).tuple_windows() {

    ///     v.push((a, b));

    /// }

    /// assert_eq!(v, vec![(1, 2), (2, 3), (3, 4)]);

    ///

    /// let mut it = (1..5).tuple_windows();

    /// assert_eq!(Some((1, 2, 3)), it.next());

    /// assert_eq!(Some((2, 3, 4)), it.next());

    /// assert_eq!(None, it.next());

    ///

    /// // this requires a type hint

    /// let it = (1..5).tuple_windows::<(_, _, _)>();

    /// itertools::assert_equal(it, vec![(1, 2, 3), (2, 3, 4)]);

    ///

    /// // you can also specify the complete type

    /// use itertools::TupleWindows;

    /// use std::ops::Range;

    ///

    /// let it: TupleWindows<Range<u32>, (u32, u32, u32)> = (1..5).tuple_windows();

    /// itertools::assert_equal(it, vec![(1, 2, 3), (2, 3, 4)]);

    /// ```

    fn tuple_windows<T>(self) -> TupleWindows<Self, T>

        where Self: Sized + Iterator<Item = T::Item>,

              T: traits::HomogeneousTuple,

              T::Item: Clone

    {

        tuple_impl::tuple_windows(self)

    }

    /// Return an iterator over all windows, wrapping back to the first

    /// elements when the window would otherwise exceed the length of the

    /// iterator, producing tuples of a specific size (up to 12).

    ///

    /// `circular_tuple_windows` clones the iterator elements so that they can be

    /// part of successive windows, this makes it most suited for iterators

    /// of references and other values that are cheap to copy.

    ///

    /// ```

    /// use itertools::Itertools;

    /// let mut v = Vec::new();

    /// for (a, b) in (1..5).circular_tuple_windows() {

    ///     v.push((a, b));

    /// }

    /// assert_eq!(v, vec![(1, 2), (2, 3), (3, 4), (4, 1)]);

    ///

    /// let mut it = (1..5).circular_tuple_windows();

    /// assert_eq!(Some((1, 2, 3)), it.next());

    /// assert_eq!(Some((2, 3, 4)), it.next());

    /// assert_eq!(Some((3, 4, 1)), it.next());

    /// assert_eq!(Some((4, 1, 2)), it.next());

    /// assert_eq!(None, it.next());

    ///

    /// // this requires a type hint

    /// let it = (1..5).circular_tuple_windows::<(_, _, _)>();

    /// itertools::assert_equal(it, vec![(1, 2, 3), (2, 3, 4), (3, 4, 1), (4, 1, 2)]);

    /// ```

    fn circular_tuple_windows<T>(self) -> CircularTupleWindows<Self, T>

        where Self: Sized + Clone + Iterator<Item = T::Item> + ExactSizeIterator,

              T: tuple_impl::TupleCollect + Clone,

              T::Item: Clone

    {

        tuple_impl::circular_tuple_windows(self)

    }

    /// Return an iterator that groups the items in tuples of a specific size

    /// (up to 12).

    ///

    /// See also the method [`.next_tuple()`](Itertools::next_tuple).

    ///

    /// ```

    /// use itertools::Itertools;

    /// let mut v = Vec::new();

    /// for (a, b) in (1..5).tuples() {

    ///     v.push((a, b));

    /// }

    /// assert_eq!(v, vec![(1, 2), (3, 4)]);

    ///

    /// let mut it = (1..7).tuples();

    /// assert_eq!(Some((1, 2, 3)), it.next());

    /// assert_eq!(Some((4, 5, 6)), it.next());

    /// assert_eq!(None, it.next());

    ///

    /// // this requires a type hint

    /// let it = (1..7).tuples::<(_, _, _)>();

    /// itertools::assert_equal(it, vec![(1, 2, 3), (4, 5, 6)]);

    ///

    /// // you can also specify the complete type

    /// use itertools::Tuples;

    /// use std::ops::Range;

    ///

    /// let it: Tuples<Range<u32>, (u32, u32, u32)> = (1..7).tuples();

    /// itertools::assert_equal(it, vec![(1, 2, 3), (4, 5, 6)]);

    /// ```

    ///

    /// See also [`Tuples::into_buffer`].

    fn tuples<T>(self) -> Tuples<Self, T>

        where Self: Sized + Iterator<Item = T::Item>,

              T: traits::HomogeneousTuple

    {

        tuple_impl::tuples(self)

    }

    /// Split into an iterator pair that both yield all elements from

    /// the original iterator.

    ///

    /// **Note:** If the iterator is clonable, prefer using that instead

    /// of using this method. Cloning is likely to be more efficient.

    ///

    /// Iterator element type is `Self::Item`.

    ///

    /// ```

    /// use itertools::Itertools;

    /// let xs = vec![0, 1, 2, 3];

    ///

    /// let (mut t1, t2) = xs.into_iter().tee();

    /// itertools::assert_equal(t1.next(), Some(0));

    /// itertools::assert_equal(t2, 0..4);

    /// itertools::assert_equal(t1, 1..4);

    /// ```

    #[cfg(feature = "use_alloc")]

    fn tee(self) -> (Tee<Self>, Tee<Self>)

        where Self: Sized,

              Self::Item: Clone

    {

        tee::new(self)

    }

    /// Return an iterator adaptor that steps `n` elements in the base iterator

    /// for each iteration.

    ///

    /// The iterator steps by yielding the next element from the base iterator,

    /// then skipping forward `n - 1` elements.

    ///

    /// Iterator element type is `Self::Item`.

    ///

    /// **Panics** if the step is 0.

    ///

    /// ```

    /// use itertools::Itertools;

    ///

    /// let it = (0..8).step(3);

    /// itertools::assert_equal(it, vec![0, 3, 6]);

    /// ```

    #[deprecated(note="Use std .step_by() instead", since="0.8.0")]

    #[allow(deprecated)]

    fn step(self, n: usize) -> Step<Self>

        where Self: Sized

    {

        adaptors::step(self, n)

    }

    /// Convert each item of the iterator using the [`Into`] trait.

    ///

    /// ```rust

    /// use itertools::Itertools;

    ///

    /// (1i32..42i32).map_into::<f64>().collect_vec();

    /// ```

    fn map_into<R>(self) -> MapInto<Self, R>

        where Self: Sized,

              Self::Item: Into<R>,

    {

        adaptors::map_into(self)

    }

    /// See [`.map_ok()`](Itertools::map_ok).

    #[deprecated(note="Use .map_ok() instead", since="0.10.0")]

    fn map_results<F, T, U, E>(self, f: F) -> MapOk<Self, F>

        where Self: Iterator<Item = Result<T, E>> + Sized,

              F: FnMut(T) -> U,

    {

        self.map_ok(f)

    }

    /// Return an iterator adaptor that applies the provided closure

    /// to every `Result::Ok` value. `Result::Err` values are

    /// unchanged.

    ///

    /// ```

    /// use itertools::Itertools;

    ///

    /// let input = vec![Ok(41), Err(false), Ok(11)];

    /// let it = input.into_iter().map_ok(|i| i + 1);

    /// itertools::assert_equal(it, vec![Ok(42), Err(false), Ok(12)]);

    /// ```

    fn map_ok<F, T, U, E>(self, f: F) -> MapOk<Self, F>

        where Self: Iterator<Item = Result<T, E>> + Sized,

              F: FnMut(T) -> U,

    {

        adaptors::map_ok(self, f)

    }

    /// Return an iterator adaptor that filters every `Result::Ok`

    /// value with the provided closure. `Result::Err` values are

    /// unchanged.

    ///

    /// ```

    /// use itertools::Itertools;

    ///

    /// let input = vec![Ok(22), Err(false), Ok(11)];

    /// let it = input.into_iter().filter_ok(|&i| i > 20);

    /// itertools::assert_equal(it, vec![Ok(22), Err(false)]);

    /// ```

    fn filter_ok<F, T, E>(self, f: F) -> FilterOk<Self, F>

        where Self: Iterator<Item = Result<T, E>> + Sized,

              F: FnMut(&T) -> bool,

    {

        adaptors::filter_ok(self, f)

    }

    /// Return an iterator adaptor that filters and transforms every

    /// `Result::Ok` value with the provided closure. `Result::Err`

    /// values are unchanged.

    ///

    /// ```

    /// use itertools::Itertools;

    ///

    /// let input = vec![Ok(22), Err(false), Ok(11)];

    /// let it = input.into_iter().filter_map_ok(|i| if i > 20 { Some(i * 2) } else { None });

    /// itertools::assert_equal(it, vec![Ok(44), Err(false)]);

    /// ```

    fn filter_map_ok<F, T, U, E>(self, f: F) -> FilterMapOk<Self, F>

        where Self: Iterator<Item = Result<T, E>> + Sized,

              F: FnMut(T) -> Option<U>,

    {

        adaptors::filter_map_ok(self, f)

    }

    /// Return an iterator adaptor that flattens every `Result::Ok` value into

    /// a series of `Result::Ok` values. `Result::Err` values are unchanged.

    ///

    /// This is useful when you have some common error type for your crate and

    /// need to propagate it upwards, but the `Result::Ok` case needs to be flattened.

    ///

    /// ```

    /// use itertools::Itertools;

    ///

    /// let input = vec![Ok(0..2), Err(false), Ok(2..4)];

    /// let it = input.iter().cloned().flatten_ok();

    /// itertools::assert_equal(it.clone(), vec![Ok(0), Ok(1), Err(false), Ok(2), Ok(3)]);

    ///

    /// // This can also be used to propagate errors when collecting.

    /// let output_result: Result<Vec<i32>, bool> = it.collect();

    /// assert_eq!(output_result, Err(false));

    /// ```

    fn flatten_ok<T, E>(self) -> FlattenOk<Self, T, E>

        where Self: Iterator<Item = Result<T, E>> + Sized,

              T: IntoIterator

    {

        flatten_ok::flatten_ok(self)

    }

    /// “Lift” a function of the values of the current iterator so as to process

    /// an iterator of `Result` values instead.

    ///

    /// `processor` is a closure that receives an adapted version of the iterator

    /// as the only argument — the adapted iterator produces elements of type `T`,

    /// as long as the original iterator produces `Ok` values.

    ///

    /// If the original iterable produces an error at any point, the adapted

    /// iterator ends and it will return the error iself.

    ///

    /// Otherwise, the return value from the closure is returned wrapped

    /// inside `Ok`.

    ///

    /// # Example

    ///

    /// ```

    /// use itertools::Itertools;

    ///

    /// type Item = Result<i32, &'static str>;

    ///

    /// let first_values: Vec<Item> = vec![Ok(1), Ok(0), Ok(3)];

    /// let second_values: Vec<Item> = vec![Ok(2), Ok(1), Err("overflow")];

    ///

    /// // “Lift” the iterator .max() method to work on the Ok-values.

    /// let first_max = first_values.into_iter().process_results(|iter| iter.max().unwrap_or(0));

    /// let second_max = second_values.into_iter().process_results(|iter| iter.max().unwrap_or(0));

    ///

    /// assert_eq!(first_max, Ok(3));

    /// assert!(second_max.is_err());

    /// ```

    fn process_results<F, T, E, R>(self, processor: F) -> Result<R, E>

        where Self: Iterator<Item = Result<T, E>> + Sized,

              F: FnOnce(ProcessResults<Self, E>) -> R

    {

        process_results(self, processor)

    }

    /// Return an iterator adaptor that merges the two base iterators in

    /// ascending order.  If both base iterators are sorted (ascending), the

    /// result is sorted.

    ///

    /// Iterator element type is `Self::Item`.

    ///

    /// ```

    /// use itertools::Itertools;

    ///

    /// let a = (0..11).step_by(3);

    /// let b = (0..11).step_by(5);

    /// let it = a.merge(b);

    /// itertools::assert_equal(it, vec![0, 0, 3, 5, 6, 9, 10]);

    /// ```

    fn merge<J>(self, other: J) -> Merge<Self, J::IntoIter>

        where Self: Sized,

              Self::Item: PartialOrd,

              J: IntoIterator<Item = Self::Item>

    {

        merge(self, other)

    }

    /// Return an iterator adaptor that merges the two base iterators in order.

    /// This is much like [`.merge()`](Itertools::merge) but allows for a custom ordering.

    ///

    /// This can be especially useful for sequences of tuples.

    ///

    /// Iterator element type is `Self::Item`.

    ///

    /// ```

    /// use itertools::Itertools;

    ///

    /// let a = (0..).zip("bc".chars());

    /// let b = (0..).zip("ad".chars());

    /// let it = a.merge_by(b, |x, y| x.1 <= y.1);

    /// itertools::assert_equal(it, vec![(0, 'a'), (0, 'b'), (1, 'c'), (1, 'd')]);

    /// ```

    fn merge_by<J, F>(self, other: J, is_first: F) -> MergeBy<Self, J::IntoIter, F>

        where Self: Sized,

              J: IntoIterator<Item = Self::Item>,

              F: FnMut(&Self::Item, &Self::Item) -> bool

    {

        adaptors::merge_by_new(self, other.into_iter(), is_first)

    }

    /// Create an iterator that merges items from both this and the specified

    /// iterator in ascending order.

    ///

    /// The function can either return an `Ordering` variant or a boolean.

    ///

    /// If `cmp_fn` returns `Ordering`,

    /// it chooses whether to pair elements based on the `Ordering` returned by the

    /// specified compare function. At any point, inspecting the tip of the

    /// iterators `I` and `J` as items `i` of type `I::Item` and `j` of type

    /// `J::Item` respectively, the resulting iterator will:

    ///

    /// - Emit `EitherOrBoth::Left(i)` when `i < j`,

    ///   and remove `i` from its source iterator

    /// - Emit `EitherOrBoth::Right(j)` when `i > j`,

    ///   and remove `j` from its source iterator

    /// - Emit `EitherOrBoth::Both(i, j)` when  `i == j`,

    ///   and remove both `i` and `j` from their respective source iterators

    ///

    /// ```

    /// use itertools::Itertools;

    /// use itertools::EitherOrBoth::{Left, Right, Both};

    ///

    /// let a = vec![0, 2, 4, 6, 1].into_iter();

    /// let b = (0..10).step_by(3);

    ///

    /// itertools::assert_equal(

    ///     a.merge_join_by(b, |i, j| i.cmp(j)),

    ///     vec![Both(0, 0), Left(2), Right(3), Left(4), Both(6, 6), Left(1), Right(9)]

    /// );

    /// ```

    ///

    /// If `cmp_fn` returns `bool`,

    /// it chooses whether to pair elements based on the boolean returned by the

    /// specified function. At any point, inspecting the tip of the

    /// iterators `I` and `J` as items `i` of type `I::Item` and `j` of type

    /// `J::Item` respectively, the resulting iterator will:

    ///

    /// - Emit `Either::Left(i)` when `true`,

    ///   and remove `i` from its source iterator

    /// - Emit `Either::Right(j)` when `false`,

    ///   and remove `j` from its source iterator

    ///

    /// It is similar to the `Ordering` case if the first argument is considered

    /// "less" than the second argument.

    ///

    /// ```

    /// use itertools::Itertools;

    /// use itertools::Either::{Left, Right};

    ///

    /// let a = vec![0, 2, 4, 6, 1].into_iter();

    /// let b = (0..10).step_by(3);

    ///

    /// itertools::assert_equal(

    ///     a.merge_join_by(b, |i, j| i <= j),

    ///     vec![Left(0), Right(0), Left(2), Right(3), Left(4), Left(6), Left(1), Right(6), Right(9)]

    /// );

    /// ```

    #[inline]

    fn merge_join_by<J, F, T>(self, other: J, cmp_fn: F) -> MergeJoinBy<Self, J::IntoIter, F>

        where J: IntoIterator,

              F: FnMut(&Self::Item, &J::Item) -> T,

              T: merge_join::OrderingOrBool<Self::Item, J::Item>,

              Self: Sized

    {

        merge_join_by(self, other, cmp_fn)

    }

    /// Return an iterator adaptor that flattens an iterator of iterators by

    /// merging them in ascending order.

    ///

    /// If all base iterators are sorted (ascending), the result is sorted.

    ///

    /// Iterator element type is `Self::Item`.

    ///

    /// ```

    /// use itertools::Itertools;

    ///

    /// let a = (0..6).step_by(3);

    /// let b = (1..6).step_by(3);

    /// let c = (2..6).step_by(3);

    /// let it = vec![a, b, c].into_iter().kmerge();

    /// itertools::assert_equal(it, vec![0, 1, 2, 3, 4, 5]);

    /// ```

    #[cfg(feature = "use_alloc")]