itertools/
lib.rs

1#![warn(missing_docs)]
2#![crate_name="itertools"]
3#![cfg_attr(not(feature = "use_std"), no_std)]
4
5//! Extra iterator adaptors, functions and macros.
6//!
7//! To extend [`Iterator`] with methods in this crate, import
8//! the [`Itertools`] trait:
9//!
10//! ```
11//! use itertools::Itertools;
12//! ```
13//!
14//! Now, new methods like [`interleave`](Itertools::interleave)
15//! are available on all iterators:
16//!
17//! ```
18//! use itertools::Itertools;
19//!
20//! let it = (1..3).interleave(vec![-1, -2]);
21//! itertools::assert_equal(it, vec![1, -1, 2, -2]);
22//! ```
23//!
24//! Most iterator methods are also provided as functions (with the benefit
25//! that they convert parameters using [`IntoIterator`]):
26//!
27//! ```
28//! use itertools::interleave;
29//!
30//! for elt in interleave(&[1, 2, 3], &[2, 3, 4]) {
31//!     /* loop body */
32//! }
33//! ```
34//!
35//! ## Crate Features
36//!
37//! - `use_std`
38//!   - Enabled by default.
39//!   - Disable to compile itertools using `#![no_std]`. This disables
40//!     any items that depend on collections (like `group_by`, `unique`,
41//!     `kmerge`, `join` and many more).
42//!
43//! ## Rust Version
44//!
45//! This version of itertools requires Rust 1.32 or later.
46#![doc(html_root_url="https://docs.rs/itertools/0.8/")]
47
48#[cfg(not(feature = "use_std"))]
49extern crate core as std;
50
51#[cfg(feature = "use_alloc")]
52extern crate alloc;
53
54#[cfg(feature = "use_alloc")]
55use alloc::{
56    string::String,
57    vec::Vec,
58};
59
60pub use either::Either;
61
62use core::borrow::Borrow;
63#[cfg(feature = "use_std")]
64use std::collections::HashMap;
65use std::iter::{IntoIterator, once};
66use std::cmp::Ordering;
67use std::fmt;
68#[cfg(feature = "use_std")]
69use std::collections::HashSet;
70#[cfg(feature = "use_std")]
71use std::hash::Hash;
72#[cfg(feature = "use_alloc")]
73use std::fmt::Write;
74#[cfg(feature = "use_alloc")]
75type VecIntoIter<T> = alloc::vec::IntoIter<T>;
76#[cfg(feature = "use_alloc")]
77use std::iter::FromIterator;
78
79#[macro_use]
80mod impl_macros;
81
82// for compatibility with no std and macros
83#[doc(hidden)]
84pub use std::iter as __std_iter;
85
86/// The concrete iterator types.
87pub mod structs {
88    pub use crate::adaptors::{
89        Dedup,
90        DedupBy,
91        DedupWithCount,
92        DedupByWithCount,
93        Interleave,
94        InterleaveShortest,
95        FilterMapOk,
96        FilterOk,
97        Product,
98        PutBack,
99        Batching,
100        MapInto,
101        MapOk,
102        Merge,
103        MergeBy,
104        TakeWhileRef,
105        WhileSome,
106        Coalesce,
107        TupleCombinations,
108        Positions,
109        Update,
110    };
111    #[allow(deprecated)]
112    pub use crate::adaptors::{MapResults, Step};
113    #[cfg(feature = "use_alloc")]
114    pub use crate::adaptors::MultiProduct;
115    #[cfg(feature = "use_alloc")]
116    pub use crate::combinations::Combinations;
117    #[cfg(feature = "use_alloc")]
118    pub use crate::combinations_with_replacement::CombinationsWithReplacement;
119    pub use crate::cons_tuples_impl::ConsTuples;
120    pub use crate::exactly_one_err::ExactlyOneError;
121    pub use crate::format::{Format, FormatWith};
122    pub use crate::flatten_ok::FlattenOk;
123    #[cfg(feature = "use_std")]
124    pub use crate::grouping_map::{GroupingMap, GroupingMapBy};
125    #[cfg(feature = "use_alloc")]
126    pub use crate::groupbylazy::{IntoChunks, Chunk, Chunks, GroupBy, Group, Groups};
127    pub use crate::intersperse::{Intersperse, IntersperseWith};
128    #[cfg(feature = "use_alloc")]
129    pub use crate::kmerge_impl::{KMerge, KMergeBy};
130    pub use crate::merge_join::MergeJoinBy;
131    #[cfg(feature = "use_alloc")]
132    pub use crate::multipeek_impl::MultiPeek;
133    #[cfg(feature = "use_alloc")]
134    pub use crate::peek_nth::PeekNth;
135    pub use crate::pad_tail::PadUsing;
136    pub use crate::peeking_take_while::PeekingTakeWhile;
137    #[cfg(feature = "use_alloc")]
138    pub use crate::permutations::Permutations;
139    pub use crate::process_results_impl::ProcessResults;
140    #[cfg(feature = "use_alloc")]
141    pub use crate::powerset::Powerset;
142    #[cfg(feature = "use_alloc")]
143    pub use crate::put_back_n_impl::PutBackN;
144    #[cfg(feature = "use_alloc")]
145    pub use crate::rciter_impl::RcIter;
146    pub use crate::repeatn::RepeatN;
147    #[allow(deprecated)]
148    pub use crate::sources::{RepeatCall, Unfold, Iterate};
149    pub use crate::take_while_inclusive::TakeWhileInclusive;
150    #[cfg(feature = "use_alloc")]
151    pub use crate::tee::Tee;
152    pub use crate::tuple_impl::{TupleBuffer, TupleWindows, CircularTupleWindows, Tuples};
153    #[cfg(feature = "use_std")]
154    pub use crate::duplicates_impl::{Duplicates, DuplicatesBy};
155    #[cfg(feature = "use_std")]
156    pub use crate::unique_impl::{Unique, UniqueBy};
157    pub use crate::with_position::WithPosition;
158    pub use crate::zip_eq_impl::ZipEq;
159    pub use crate::zip_longest::ZipLongest;
160    pub use crate::ziptuple::Zip;
161}
162
163/// Traits helpful for using certain `Itertools` methods in generic contexts.
164pub mod traits {
165    pub use crate::tuple_impl::HomogeneousTuple;
166}
167
168#[allow(deprecated)]
169pub use crate::structs::*;
170pub use crate::concat_impl::concat;
171pub use crate::cons_tuples_impl::cons_tuples;
172pub use crate::diff::diff_with;
173pub use crate::diff::Diff;
174#[cfg(feature = "use_alloc")]
175pub use crate::kmerge_impl::{kmerge_by};
176pub use crate::minmax::MinMaxResult;
177pub use crate::peeking_take_while::PeekingNext;
178pub use crate::process_results_impl::process_results;
179pub use crate::repeatn::repeat_n;
180#[allow(deprecated)]
181pub use crate::sources::{repeat_call, unfold, iterate};
182pub use crate::with_position::Position;
183pub use crate::unziptuple::{multiunzip, MultiUnzip};
184pub use crate::ziptuple::multizip;
185mod adaptors;
186mod either_or_both;
187pub use crate::either_or_both::EitherOrBoth;
188#[doc(hidden)]
189pub mod free;
190#[doc(inline)]
191pub use crate::free::*;
192mod concat_impl;
193mod cons_tuples_impl;
194#[cfg(feature = "use_alloc")]
195mod combinations;
196#[cfg(feature = "use_alloc")]
197mod combinations_with_replacement;
198mod exactly_one_err;
199mod diff;
200mod flatten_ok;
201#[cfg(feature = "use_std")]
202mod extrema_set;
203mod format;
204#[cfg(feature = "use_std")]
205mod grouping_map;
206#[cfg(feature = "use_alloc")]
207mod group_map;
208#[cfg(feature = "use_alloc")]
209mod groupbylazy;
210mod intersperse;
211#[cfg(feature = "use_alloc")]
212mod k_smallest;
213#[cfg(feature = "use_alloc")]
214mod kmerge_impl;
215#[cfg(feature = "use_alloc")]
216mod lazy_buffer;
217mod merge_join;
218mod minmax;
219#[cfg(feature = "use_alloc")]
220mod multipeek_impl;
221mod pad_tail;
222#[cfg(feature = "use_alloc")]
223mod peek_nth;
224mod peeking_take_while;
225#[cfg(feature = "use_alloc")]
226mod permutations;
227#[cfg(feature = "use_alloc")]
228mod powerset;
229mod process_results_impl;
230#[cfg(feature = "use_alloc")]
231mod put_back_n_impl;
232#[cfg(feature = "use_alloc")]
233mod rciter_impl;
234mod repeatn;
235mod size_hint;
236mod sources;
237mod take_while_inclusive;
238#[cfg(feature = "use_alloc")]
239mod tee;
240mod tuple_impl;
241#[cfg(feature = "use_std")]
242mod duplicates_impl;
243#[cfg(feature = "use_std")]
244mod unique_impl;
245mod unziptuple;
246mod with_position;
247mod zip_eq_impl;
248mod zip_longest;
249mod ziptuple;
250
251#[macro_export]
252/// Create an iterator over the “cartesian product” of iterators.
253///
254/// Iterator element type is like `(A, B, ..., E)` if formed
255/// from iterators `(I, J, ..., M)` with element types `I::Item = A`, `J::Item = B`, etc.
256///
257/// ```
258/// # use itertools::iproduct;
259/// #
260/// # fn main() {
261/// // Iterate over the coordinates of a 4 x 4 x 4 grid
262/// // from (0, 0, 0), (0, 0, 1), .., (0, 1, 0), (0, 1, 1), .. etc until (3, 3, 3)
263/// for (i, j, k) in iproduct!(0..4, 0..4, 0..4) {
264///    // ..
265/// }
266/// # }
267/// ```
268macro_rules! iproduct {
269    (@flatten $I:expr,) => (
270        $I
271    );
272    (@flatten $I:expr, $J:expr, $($K:expr,)*) => (
273        $crate::iproduct!(@flatten $crate::cons_tuples($crate::iproduct!($I, $J)), $($K,)*)
274    );
275    ($I:expr) => (
276        $crate::__std_iter::IntoIterator::into_iter($I)
277    );
278    ($I:expr, $J:expr) => (
279        $crate::Itertools::cartesian_product($crate::iproduct!($I), $crate::iproduct!($J))
280    );
281    ($I:expr, $J:expr, $($K:expr),+) => (
282        $crate::iproduct!(@flatten $crate::iproduct!($I, $J), $($K,)+)
283    );
284}
285
286#[macro_export]
287/// Create an iterator running multiple iterators in lockstep.
288///
289/// The `izip!` iterator yields elements until any subiterator
290/// returns `None`.
291///
292/// This is a version of the standard ``.zip()`` that's supporting more than
293/// two iterators. The iterator element type is a tuple with one element
294/// from each of the input iterators. Just like ``.zip()``, the iteration stops
295/// when the shortest of the inputs reaches its end.
296///
297/// **Note:** The result of this macro is in the general case an iterator
298/// composed of repeated `.zip()` and a `.map()`; it has an anonymous type.
299/// The special cases of one and two arguments produce the equivalent of
300/// `$a.into_iter()` and `$a.into_iter().zip($b)` respectively.
301///
302/// Prefer this macro `izip!()` over [`multizip`] for the performance benefits
303/// of using the standard library `.zip()`.
304///
305/// ```
306/// # use itertools::izip;
307/// #
308/// # fn main() {
309///
310/// // iterate over three sequences side-by-side
311/// let mut results = [0, 0, 0, 0];
312/// let inputs = [3, 7, 9, 6];
313///
314/// for (r, index, input) in izip!(&mut results, 0..10, &inputs) {
315///     *r = index * 10 + input;
316/// }
317///
318/// assert_eq!(results, [0 + 3, 10 + 7, 29, 36]);
319/// # }
320/// ```
321macro_rules! izip {
322    // @closure creates a tuple-flattening closure for .map() call. usage:
323    // @closure partial_pattern => partial_tuple , rest , of , iterators
324    // eg. izip!( @closure ((a, b), c) => (a, b, c) , dd , ee )
325    ( @closure $p:pat => $tup:expr ) => {
326        |$p| $tup
327    };
328
329    // The "b" identifier is a different identifier on each recursion level thanks to hygiene.
330    ( @closure $p:pat => ( $($tup:tt)* ) , $_iter:expr $( , $tail:expr )* ) => {
331        $crate::izip!(@closure ($p, b) => ( $($tup)*, b ) $( , $tail )*)
332    };
333
334    // unary
335    ($first:expr $(,)*) => {
336        $crate::__std_iter::IntoIterator::into_iter($first)
337    };
338
339    // binary
340    ($first:expr, $second:expr $(,)*) => {
341        $crate::izip!($first)
342            .zip($second)
343    };
344
345    // n-ary where n > 2
346    ( $first:expr $( , $rest:expr )* $(,)* ) => {
347        $crate::izip!($first)
348            $(
349                .zip($rest)
350            )*
351            .map(
352                $crate::izip!(@closure a => (a) $( , $rest )*)
353            )
354    };
355}
356
357#[macro_export]
358/// [Chain][`chain`] zero or more iterators together into one sequence.
359///
360/// The comma-separated arguments must implement [`IntoIterator`].
361/// The final argument may be followed by a trailing comma.
362///
363/// [`chain`]: Iterator::chain
364///
365/// # Examples
366///
367/// Empty invocations of `chain!` expand to an invocation of [`std::iter::empty`]:
368/// ```
369/// use std::iter;
370/// use itertools::chain;
371///
372/// let _: iter::Empty<()> = chain!();
373/// let _: iter::Empty<i8> = chain!();
374/// ```
375///
376/// Invocations of `chain!` with one argument expand to [`arg.into_iter()`](IntoIterator):
377/// ```
378/// use std::{ops::Range, slice};
379/// use itertools::chain;
380/// let _: <Range<_> as IntoIterator>::IntoIter = chain!((2..6),); // trailing comma optional!
381/// let _:     <&[_] as IntoIterator>::IntoIter = chain!(&[2, 3, 4]);
382/// ```
383///
384/// Invocations of `chain!` with multiple arguments [`.into_iter()`](IntoIterator) each
385/// argument, and then [`chain`] them together:
386/// ```
387/// use std::{iter::*, ops::Range, slice};
388/// use itertools::{assert_equal, chain};
389///
390/// // e.g., this:
391/// let with_macro:  Chain<Chain<Once<_>, Take<Repeat<_>>>, slice::Iter<_>> =
392///     chain![once(&0), repeat(&1).take(2), &[2, 3, 5],];
393///
394/// // ...is equivalent to this:
395/// let with_method: Chain<Chain<Once<_>, Take<Repeat<_>>>, slice::Iter<_>> =
396///     once(&0)
397///         .chain(repeat(&1).take(2))
398///         .chain(&[2, 3, 5]);
399///
400/// assert_equal(with_macro, with_method);
401/// ```
402macro_rules! chain {
403    () => {
404        core::iter::empty()
405    };
406    ($first:expr $(, $rest:expr )* $(,)?) => {
407        {
408            let iter = core::iter::IntoIterator::into_iter($first);
409            $(
410                let iter =
411                    core::iter::Iterator::chain(
412                        iter,
413                        core::iter::IntoIterator::into_iter($rest));
414            )*
415            iter
416        }
417    };
418}
419
420/// An [`Iterator`] blanket implementation that provides extra adaptors and
421/// methods.
422///
423/// This trait defines a number of methods. They are divided into two groups:
424///
425/// * *Adaptors* take an iterator and parameter as input, and return
426/// a new iterator value. These are listed first in the trait. An example
427/// of an adaptor is [`.interleave()`](Itertools::interleave)
428///
429/// * *Regular methods* are those that don't return iterators and instead
430/// return a regular value of some other kind.
431/// [`.next_tuple()`](Itertools::next_tuple) is an example and the first regular
432/// method in the list.
433pub trait Itertools : Iterator {
434    // adaptors
435
436    /// Alternate elements from two iterators until both have run out.
437    ///
438    /// Iterator element type is `Self::Item`.
439    ///
440    /// This iterator is *fused*.
441    ///
442    /// ```
443    /// use itertools::Itertools;
444    ///
445    /// let it = (1..7).interleave(vec![-1, -2]);
446    /// itertools::assert_equal(it, vec![1, -1, 2, -2, 3, 4, 5, 6]);
447    /// ```
448    fn interleave<J>(self, other: J) -> Interleave<Self, J::IntoIter>
449        where J: IntoIterator<Item = Self::Item>,
450              Self: Sized
451    {
452        interleave(self, other)
453    }
454
455    /// Alternate elements from two iterators until at least one of them has run
456    /// out.
457    ///
458    /// Iterator element type is `Self::Item`.
459    ///
460    /// ```
461    /// use itertools::Itertools;
462    ///
463    /// let it = (1..7).interleave_shortest(vec![-1, -2]);
464    /// itertools::assert_equal(it, vec![1, -1, 2, -2, 3]);
465    /// ```
466    fn interleave_shortest<J>(self, other: J) -> InterleaveShortest<Self, J::IntoIter>
467        where J: IntoIterator<Item = Self::Item>,
468              Self: Sized
469    {
470        adaptors::interleave_shortest(self, other.into_iter())
471    }
472
473    /// An iterator adaptor to insert a particular value
474    /// between each element of the adapted iterator.
475    ///
476    /// Iterator element type is `Self::Item`.
477    ///
478    /// This iterator is *fused*.
479    ///
480    /// ```
481    /// use itertools::Itertools;
482    ///
483    /// itertools::assert_equal((0..3).intersperse(8), vec![0, 8, 1, 8, 2]);
484    /// ```
485    fn intersperse(self, element: Self::Item) -> Intersperse<Self>
486        where Self: Sized,
487              Self::Item: Clone
488    {
489        intersperse::intersperse(self, element)
490    }
491
492    /// An iterator adaptor to insert a particular value created by a function
493    /// between each element of the adapted iterator.
494    ///
495    /// Iterator element type is `Self::Item`.
496    ///
497    /// This iterator is *fused*.
498    ///
499    /// ```
500    /// use itertools::Itertools;
501    ///
502    /// let mut i = 10;
503    /// itertools::assert_equal((0..3).intersperse_with(|| { i -= 1; i }), vec![0, 9, 1, 8, 2]);
504    /// assert_eq!(i, 8);
505    /// ```
506    fn intersperse_with<F>(self, element: F) -> IntersperseWith<Self, F>
507        where Self: Sized,
508        F: FnMut() -> Self::Item
509    {
510        intersperse::intersperse_with(self, element)
511    }
512
513    /// Create an iterator which iterates over both this and the specified
514    /// iterator simultaneously, yielding pairs of two optional elements.
515    ///
516    /// This iterator is *fused*.
517    ///
518    /// As long as neither input iterator is exhausted yet, it yields two values
519    /// via `EitherOrBoth::Both`.
520    ///
521    /// When the parameter iterator is exhausted, it only yields a value from the
522    /// `self` iterator via `EitherOrBoth::Left`.
523    ///
524    /// When the `self` iterator is exhausted, it only yields a value from the
525    /// parameter iterator via `EitherOrBoth::Right`.
526    ///
527    /// When both iterators return `None`, all further invocations of `.next()`
528    /// will return `None`.
529    ///
530    /// Iterator element type is
531    /// [`EitherOrBoth<Self::Item, J::Item>`](EitherOrBoth).
532    ///
533    /// ```rust
534    /// use itertools::EitherOrBoth::{Both, Right};
535    /// use itertools::Itertools;
536    /// let it = (0..1).zip_longest(1..3);
537    /// itertools::assert_equal(it, vec![Both(0, 1), Right(2)]);
538    /// ```
539    #[inline]
540    fn zip_longest<J>(self, other: J) -> ZipLongest<Self, J::IntoIter>
541        where J: IntoIterator,
542              Self: Sized
543    {
544        zip_longest::zip_longest(self, other.into_iter())
545    }
546
547    /// Create an iterator which iterates over both this and the specified
548    /// iterator simultaneously, yielding pairs of elements.
549    ///
550    /// **Panics** if the iterators reach an end and they are not of equal
551    /// lengths.
552    #[inline]
553    fn zip_eq<J>(self, other: J) -> ZipEq<Self, J::IntoIter>
554        where J: IntoIterator,
555              Self: Sized
556    {
557        zip_eq(self, other)
558    }
559
560    /// A “meta iterator adaptor”. Its closure receives a reference to the
561    /// iterator and may pick off as many elements as it likes, to produce the
562    /// next iterator element.
563    ///
564    /// Iterator element type is `B`.
565    ///
566    /// ```
567    /// use itertools::Itertools;
568    ///
569    /// // An adaptor that gathers elements in pairs
570    /// let pit = (0..4).batching(|it| {
571    ///            match it.next() {
572    ///                None => None,
573    ///                Some(x) => match it.next() {
574    ///                    None => None,
575    ///                    Some(y) => Some((x, y)),
576    ///                }
577    ///            }
578    ///        });
579    ///
580    /// itertools::assert_equal(pit, vec![(0, 1), (2, 3)]);
581    /// ```
582    ///
583    fn batching<B, F>(self, f: F) -> Batching<Self, F>
584        where F: FnMut(&mut Self) -> Option<B>,
585              Self: Sized
586    {
587        adaptors::batching(self, f)
588    }
589
590    /// Return an *iterable* that can group iterator elements.
591    /// Consecutive elements that map to the same key (“runs”), are assigned
592    /// to the same group.
593    ///
594    /// `GroupBy` is the storage for the lazy grouping operation.
595    ///
596    /// If the groups are consumed in order, or if each group's iterator is
597    /// dropped without keeping it around, then `GroupBy` uses no
598    /// allocations.  It needs allocations only if several group iterators
599    /// are alive at the same time.
600    ///
601    /// This type implements [`IntoIterator`] (it is **not** an iterator
602    /// itself), because the group iterators need to borrow from this
603    /// value. It should be stored in a local variable or temporary and
604    /// iterated.
605    ///
606    /// Iterator element type is `(K, Group)`: the group's key and the
607    /// group iterator.
608    ///
609    /// ```
610    /// use itertools::Itertools;
611    ///
612    /// // group data into runs of larger than zero or not.
613    /// let data = vec![1, 3, -2, -2, 1, 0, 1, 2];
614    /// // groups:     |---->|------>|--------->|
615    ///
616    /// // Note: The `&` is significant here, `GroupBy` is iterable
617    /// // only by reference. You can also call `.into_iter()` explicitly.
618    /// let mut data_grouped = Vec::new();
619    /// for (key, group) in &data.into_iter().group_by(|elt| *elt >= 0) {
620    ///     data_grouped.push((key, group.collect()));
621    /// }
622    /// assert_eq!(data_grouped, vec![(true, vec![1, 3]), (false, vec![-2, -2]), (true, vec![1, 0, 1, 2])]);
623    /// ```
624    #[cfg(feature = "use_alloc")]
625    fn group_by<K, F>(self, key: F) -> GroupBy<K, Self, F>
626        where Self: Sized,
627              F: FnMut(&Self::Item) -> K,
628              K: PartialEq,
629    {
630        groupbylazy::new(self, key)
631    }
632
633    /// Return an *iterable* that can chunk the iterator.
634    ///
635    /// Yield subiterators (chunks) that each yield a fixed number elements,
636    /// determined by `size`. The last chunk will be shorter if there aren't
637    /// enough elements.
638    ///
639    /// `IntoChunks` is based on `GroupBy`: it is iterable (implements
640    /// `IntoIterator`, **not** `Iterator`), and it only buffers if several
641    /// chunk iterators are alive at the same time.
642    ///
643    /// Iterator element type is `Chunk`, each chunk's iterator.
644    ///
645    /// **Panics** if `size` is 0.
646    ///
647    /// ```
648    /// use itertools::Itertools;
649    ///
650    /// let data = vec![1, 1, 2, -2, 6, 0, 3, 1];
651    /// //chunk size=3 |------->|-------->|--->|
652    ///
653    /// // Note: The `&` is significant here, `IntoChunks` is iterable
654    /// // only by reference. You can also call `.into_iter()` explicitly.
655    /// for chunk in &data.into_iter().chunks(3) {
656    ///     // Check that the sum of each chunk is 4.
657    ///     assert_eq!(4, chunk.sum());
658    /// }
659    /// ```
660    #[cfg(feature = "use_alloc")]
661    fn chunks(self, size: usize) -> IntoChunks<Self>
662        where Self: Sized,
663    {
664        assert!(size != 0);
665        groupbylazy::new_chunks(self, size)
666    }
667
668    /// Return an iterator over all contiguous windows producing tuples of
669    /// a specific size (up to 12).
670    ///
671    /// `tuple_windows` clones the iterator elements so that they can be
672    /// part of successive windows, this makes it most suited for iterators
673    /// of references and other values that are cheap to copy.
674    ///
675    /// ```
676    /// use itertools::Itertools;
677    /// let mut v = Vec::new();
678    ///
679    /// // pairwise iteration
680    /// for (a, b) in (1..5).tuple_windows() {
681    ///     v.push((a, b));
682    /// }
683    /// assert_eq!(v, vec![(1, 2), (2, 3), (3, 4)]);
684    ///
685    /// let mut it = (1..5).tuple_windows();
686    /// assert_eq!(Some((1, 2, 3)), it.next());
687    /// assert_eq!(Some((2, 3, 4)), it.next());
688    /// assert_eq!(None, it.next());
689    ///
690    /// // this requires a type hint
691    /// let it = (1..5).tuple_windows::<(_, _, _)>();
692    /// itertools::assert_equal(it, vec![(1, 2, 3), (2, 3, 4)]);
693    ///
694    /// // you can also specify the complete type
695    /// use itertools::TupleWindows;
696    /// use std::ops::Range;
697    ///
698    /// let it: TupleWindows<Range<u32>, (u32, u32, u32)> = (1..5).tuple_windows();
699    /// itertools::assert_equal(it, vec![(1, 2, 3), (2, 3, 4)]);
700    /// ```
701    fn tuple_windows<T>(self) -> TupleWindows<Self, T>
702        where Self: Sized + Iterator<Item = T::Item>,
703              T: traits::HomogeneousTuple,
704              T::Item: Clone
705    {
706        tuple_impl::tuple_windows(self)
707    }
708
709    /// Return an iterator over all windows, wrapping back to the first
710    /// elements when the window would otherwise exceed the length of the
711    /// iterator, producing tuples of a specific size (up to 12).
712    ///
713    /// `circular_tuple_windows` clones the iterator elements so that they can be
714    /// part of successive windows, this makes it most suited for iterators
715    /// of references and other values that are cheap to copy.
716    ///
717    /// ```
718    /// use itertools::Itertools;
719    /// let mut v = Vec::new();
720    /// for (a, b) in (1..5).circular_tuple_windows() {
721    ///     v.push((a, b));
722    /// }
723    /// assert_eq!(v, vec![(1, 2), (2, 3), (3, 4), (4, 1)]);
724    ///
725    /// let mut it = (1..5).circular_tuple_windows();
726    /// assert_eq!(Some((1, 2, 3)), it.next());
727    /// assert_eq!(Some((2, 3, 4)), it.next());
728    /// assert_eq!(Some((3, 4, 1)), it.next());
729    /// assert_eq!(Some((4, 1, 2)), it.next());
730    /// assert_eq!(None, it.next());
731    ///
732    /// // this requires a type hint
733    /// let it = (1..5).circular_tuple_windows::<(_, _, _)>();
734    /// itertools::assert_equal(it, vec![(1, 2, 3), (2, 3, 4), (3, 4, 1), (4, 1, 2)]);
735    /// ```
736    fn circular_tuple_windows<T>(self) -> CircularTupleWindows<Self, T>
737        where Self: Sized + Clone + Iterator<Item = T::Item> + ExactSizeIterator,
738              T: tuple_impl::TupleCollect + Clone,
739              T::Item: Clone
740    {
741        tuple_impl::circular_tuple_windows(self)
742    }
743    /// Return an iterator that groups the items in tuples of a specific size
744    /// (up to 12).
745    ///
746    /// See also the method [`.next_tuple()`](Itertools::next_tuple).
747    ///
748    /// ```
749    /// use itertools::Itertools;
750    /// let mut v = Vec::new();
751    /// for (a, b) in (1..5).tuples() {
752    ///     v.push((a, b));
753    /// }
754    /// assert_eq!(v, vec![(1, 2), (3, 4)]);
755    ///
756    /// let mut it = (1..7).tuples();
757    /// assert_eq!(Some((1, 2, 3)), it.next());
758    /// assert_eq!(Some((4, 5, 6)), it.next());
759    /// assert_eq!(None, it.next());
760    ///
761    /// // this requires a type hint
762    /// let it = (1..7).tuples::<(_, _, _)>();
763    /// itertools::assert_equal(it, vec![(1, 2, 3), (4, 5, 6)]);
764    ///
765    /// // you can also specify the complete type
766    /// use itertools::Tuples;
767    /// use std::ops::Range;
768    ///
769    /// let it: Tuples<Range<u32>, (u32, u32, u32)> = (1..7).tuples();
770    /// itertools::assert_equal(it, vec![(1, 2, 3), (4, 5, 6)]);
771    /// ```
772    ///
773    /// See also [`Tuples::into_buffer`].
774    fn tuples<T>(self) -> Tuples<Self, T>
775        where Self: Sized + Iterator<Item = T::Item>,
776              T: traits::HomogeneousTuple
777    {
778        tuple_impl::tuples(self)
779    }
780
781    /// Split into an iterator pair that both yield all elements from
782    /// the original iterator.
783    ///
784    /// **Note:** If the iterator is clonable, prefer using that instead
785    /// of using this method. Cloning is likely to be more efficient.
786    ///
787    /// Iterator element type is `Self::Item`.
788    ///
789    /// ```
790    /// use itertools::Itertools;
791    /// let xs = vec![0, 1, 2, 3];
792    ///
793    /// let (mut t1, t2) = xs.into_iter().tee();
794    /// itertools::assert_equal(t1.next(), Some(0));
795    /// itertools::assert_equal(t2, 0..4);
796    /// itertools::assert_equal(t1, 1..4);
797    /// ```
798    #[cfg(feature = "use_alloc")]
799    fn tee(self) -> (Tee<Self>, Tee<Self>)
800        where Self: Sized,
801              Self::Item: Clone
802    {
803        tee::new(self)
804    }
805
806    /// Return an iterator adaptor that steps `n` elements in the base iterator
807    /// for each iteration.
808    ///
809    /// The iterator steps by yielding the next element from the base iterator,
810    /// then skipping forward `n - 1` elements.
811    ///
812    /// Iterator element type is `Self::Item`.
813    ///
814    /// **Panics** if the step is 0.
815    ///
816    /// ```
817    /// use itertools::Itertools;
818    ///
819    /// let it = (0..8).step(3);
820    /// itertools::assert_equal(it, vec![0, 3, 6]);
821    /// ```
822    #[deprecated(note="Use std .step_by() instead", since="0.8.0")]
823    #[allow(deprecated)]
824    fn step(self, n: usize) -> Step<Self>
825        where Self: Sized
826    {
827        adaptors::step(self, n)
828    }
829
830    /// Convert each item of the iterator using the [`Into`] trait.
831    ///
832    /// ```rust
833    /// use itertools::Itertools;
834    ///
835    /// (1i32..42i32).map_into::<f64>().collect_vec();
836    /// ```
837    fn map_into<R>(self) -> MapInto<Self, R>
838        where Self: Sized,
839              Self::Item: Into<R>,
840    {
841        adaptors::map_into(self)
842    }
843
844    /// See [`.map_ok()`](Itertools::map_ok).
845    #[deprecated(note="Use .map_ok() instead", since="0.10.0")]
846    fn map_results<F, T, U, E>(self, f: F) -> MapOk<Self, F>
847        where Self: Iterator<Item = Result<T, E>> + Sized,
848              F: FnMut(T) -> U,
849    {
850        self.map_ok(f)
851    }
852
853    /// Return an iterator adaptor that applies the provided closure
854    /// to every `Result::Ok` value. `Result::Err` values are
855    /// unchanged.
856    ///
857    /// ```
858    /// use itertools::Itertools;
859    ///
860    /// let input = vec![Ok(41), Err(false), Ok(11)];
861    /// let it = input.into_iter().map_ok(|i| i + 1);
862    /// itertools::assert_equal(it, vec![Ok(42), Err(false), Ok(12)]);
863    /// ```
864    fn map_ok<F, T, U, E>(self, f: F) -> MapOk<Self, F>
865        where Self: Iterator<Item = Result<T, E>> + Sized,
866              F: FnMut(T) -> U,
867    {
868        adaptors::map_ok(self, f)
869    }
870
871    /// Return an iterator adaptor that filters every `Result::Ok`
872    /// value with the provided closure. `Result::Err` values are
873    /// unchanged.
874    ///
875    /// ```
876    /// use itertools::Itertools;
877    ///
878    /// let input = vec![Ok(22), Err(false), Ok(11)];
879    /// let it = input.into_iter().filter_ok(|&i| i > 20);
880    /// itertools::assert_equal(it, vec![Ok(22), Err(false)]);
881    /// ```
882    fn filter_ok<F, T, E>(self, f: F) -> FilterOk<Self, F>
883        where Self: Iterator<Item = Result<T, E>> + Sized,
884              F: FnMut(&T) -> bool,
885    {
886        adaptors::filter_ok(self, f)
887    }
888
889    /// Return an iterator adaptor that filters and transforms every
890    /// `Result::Ok` value with the provided closure. `Result::Err`
891    /// values are unchanged.
892    ///
893    /// ```
894    /// use itertools::Itertools;
895    ///
896    /// let input = vec![Ok(22), Err(false), Ok(11)];
897    /// let it = input.into_iter().filter_map_ok(|i| if i > 20 { Some(i * 2) } else { None });
898    /// itertools::assert_equal(it, vec![Ok(44), Err(false)]);
899    /// ```
900    fn filter_map_ok<F, T, U, E>(self, f: F) -> FilterMapOk<Self, F>
901        where Self: Iterator<Item = Result<T, E>> + Sized,
902              F: FnMut(T) -> Option<U>,
903    {
904        adaptors::filter_map_ok(self, f)
905    }
906
907    /// Return an iterator adaptor that flattens every `Result::Ok` value into
908    /// a series of `Result::Ok` values. `Result::Err` values are unchanged.
909    ///
910    /// This is useful when you have some common error type for your crate and
911    /// need to propagate it upwards, but the `Result::Ok` case needs to be flattened.
912    ///
913    /// ```
914    /// use itertools::Itertools;
915    ///
916    /// let input = vec![Ok(0..2), Err(false), Ok(2..4)];
917    /// let it = input.iter().cloned().flatten_ok();
918    /// itertools::assert_equal(it.clone(), vec![Ok(0), Ok(1), Err(false), Ok(2), Ok(3)]);
919    ///
920    /// // This can also be used to propagate errors when collecting.
921    /// let output_result: Result<Vec<i32>, bool> = it.collect();
922    /// assert_eq!(output_result, Err(false));
923    /// ```
924    fn flatten_ok<T, E>(self) -> FlattenOk<Self, T, E>
925        where Self: Iterator<Item = Result<T, E>> + Sized,
926              T: IntoIterator
927    {
928        flatten_ok::flatten_ok(self)
929    }
930
931    /// “Lift” a function of the values of the current iterator so as to process
932    /// an iterator of `Result` values instead.
933    ///
934    /// `processor` is a closure that receives an adapted version of the iterator
935    /// as the only argument — the adapted iterator produces elements of type `T`,
936    /// as long as the original iterator produces `Ok` values.
937    ///
938    /// If the original iterable produces an error at any point, the adapted
939    /// iterator ends and it will return the error iself.
940    ///
941    /// Otherwise, the return value from the closure is returned wrapped
942    /// inside `Ok`.
943    ///
944    /// # Example
945    ///
946    /// ```
947    /// use itertools::Itertools;
948    ///
949    /// type Item = Result<i32, &'static str>;
950    ///
951    /// let first_values: Vec<Item> = vec![Ok(1), Ok(0), Ok(3)];
952    /// let second_values: Vec<Item> = vec![Ok(2), Ok(1), Err("overflow")];
953    ///
954    /// // “Lift” the iterator .max() method to work on the Ok-values.
955    /// let first_max = first_values.into_iter().process_results(|iter| iter.max().unwrap_or(0));
956    /// let second_max = second_values.into_iter().process_results(|iter| iter.max().unwrap_or(0));
957    ///
958    /// assert_eq!(first_max, Ok(3));
959    /// assert!(second_max.is_err());
960    /// ```
961    fn process_results<F, T, E, R>(self, processor: F) -> Result<R, E>
962        where Self: Iterator<Item = Result<T, E>> + Sized,
963              F: FnOnce(ProcessResults<Self, E>) -> R
964    {
965        process_results(self, processor)
966    }
967
968    /// Return an iterator adaptor that merges the two base iterators in
969    /// ascending order.  If both base iterators are sorted (ascending), the
970    /// result is sorted.
971    ///
972    /// Iterator element type is `Self::Item`.
973    ///
974    /// ```
975    /// use itertools::Itertools;
976    ///
977    /// let a = (0..11).step_by(3);
978    /// let b = (0..11).step_by(5);
979    /// let it = a.merge(b);
980    /// itertools::assert_equal(it, vec![0, 0, 3, 5, 6, 9, 10]);
981    /// ```
982    fn merge<J>(self, other: J) -> Merge<Self, J::IntoIter>
983        where Self: Sized,
984              Self::Item: PartialOrd,
985              J: IntoIterator<Item = Self::Item>
986    {
987        merge(self, other)
988    }
989
990    /// Return an iterator adaptor that merges the two base iterators in order.
991    /// This is much like [`.merge()`](Itertools::merge) but allows for a custom ordering.
992    ///
993    /// This can be especially useful for sequences of tuples.
994    ///
995    /// Iterator element type is `Self::Item`.
996    ///
997    /// ```
998    /// use itertools::Itertools;
999    ///
1000    /// let a = (0..).zip("bc".chars());
1001    /// let b = (0..).zip("ad".chars());
1002    /// let it = a.merge_by(b, |x, y| x.1 <= y.1);
1003    /// itertools::assert_equal(it, vec![(0, 'a'), (0, 'b'), (1, 'c'), (1, 'd')]);
1004    /// ```
1005
1006    fn merge_by<J, F>(self, other: J, is_first: F) -> MergeBy<Self, J::IntoIter, F>
1007        where Self: Sized,
1008              J: IntoIterator<Item = Self::Item>,
1009              F: FnMut(&Self::Item, &Self::Item) -> bool
1010    {
1011        adaptors::merge_by_new(self, other.into_iter(), is_first)
1012    }
1013
1014    /// Create an iterator that merges items from both this and the specified
1015    /// iterator in ascending order.
1016    ///
1017    /// The function can either return an `Ordering` variant or a boolean.
1018    ///
1019    /// If `cmp_fn` returns `Ordering`,
1020    /// it chooses whether to pair elements based on the `Ordering` returned by the
1021    /// specified compare function. At any point, inspecting the tip of the
1022    /// iterators `I` and `J` as items `i` of type `I::Item` and `j` of type
1023    /// `J::Item` respectively, the resulting iterator will:
1024    ///
1025    /// - Emit `EitherOrBoth::Left(i)` when `i < j`,
1026    ///   and remove `i` from its source iterator
1027    /// - Emit `EitherOrBoth::Right(j)` when `i > j`,
1028    ///   and remove `j` from its source iterator
1029    /// - Emit `EitherOrBoth::Both(i, j)` when  `i == j`,
1030    ///   and remove both `i` and `j` from their respective source iterators
1031    ///
1032    /// ```
1033    /// use itertools::Itertools;
1034    /// use itertools::EitherOrBoth::{Left, Right, Both};
1035    ///
1036    /// let a = vec![0, 2, 4, 6, 1].into_iter();
1037    /// let b = (0..10).step_by(3);
1038    ///
1039    /// itertools::assert_equal(
1040    ///     a.merge_join_by(b, |i, j| i.cmp(j)),
1041    ///     vec![Both(0, 0), Left(2), Right(3), Left(4), Both(6, 6), Left(1), Right(9)]
1042    /// );
1043    /// ```
1044    ///
1045    /// If `cmp_fn` returns `bool`,
1046    /// it chooses whether to pair elements based on the boolean returned by the
1047    /// specified function. At any point, inspecting the tip of the
1048    /// iterators `I` and `J` as items `i` of type `I::Item` and `j` of type
1049    /// `J::Item` respectively, the resulting iterator will:
1050    ///
1051    /// - Emit `Either::Left(i)` when `true`,
1052    ///   and remove `i` from its source iterator
1053    /// - Emit `Either::Right(j)` when `false`,
1054    ///   and remove `j` from its source iterator
1055    ///
1056    /// It is similar to the `Ordering` case if the first argument is considered
1057    /// "less" than the second argument.
1058    ///
1059    /// ```
1060    /// use itertools::Itertools;
1061    /// use itertools::Either::{Left, Right};
1062    ///
1063    /// let a = vec![0, 2, 4, 6, 1].into_iter();
1064    /// let b = (0..10).step_by(3);
1065    ///
1066    /// itertools::assert_equal(
1067    ///     a.merge_join_by(b, |i, j| i <= j),
1068    ///     vec![Left(0), Right(0), Left(2), Right(3), Left(4), Left(6), Left(1), Right(6), Right(9)]
1069    /// );
1070    /// ```
1071    #[inline]
1072    fn merge_join_by<J, F, T>(self, other: J, cmp_fn: F) -> MergeJoinBy<Self, J::IntoIter, F>
1073        where J: IntoIterator,
1074              F: FnMut(&Self::Item, &J::Item) -> T,
1075              T: merge_join::OrderingOrBool<Self::Item, J::Item>,
1076              Self: Sized
1077    {
1078        merge_join_by(self, other, cmp_fn)
1079    }
1080
1081    /// Return an iterator adaptor that flattens an iterator of iterators by
1082    /// merging them in ascending order.
1083    ///
1084    /// If all base iterators are sorted (ascending), the result is sorted.
1085    ///
1086    /// Iterator element type is `Self::Item`.
1087    ///
1088    /// ```
1089    /// use itertools::Itertools;
1090    ///
1091    /// let a = (0..6).step_by(3);
1092    /// let b = (1..6).step_by(3);
1093    /// let c = (2..6).step_by(3);
1094    /// let it = vec![a, b, c].into_iter().kmerge();
1095    /// itertools::assert_equal(it, vec![0, 1, 2, 3, 4, 5]);
1096    /// ```
1097    #[cfg(feature = "use_alloc")]
1098    fn kmerge(self) -> KMerge<<Self::Item as IntoIterator>::IntoIter>
1099        where Self: Sized,
1100              Self::Item: IntoIterator,
1101              <Self::Item as IntoIterator>::Item: PartialOrd,
1102    {
1103        kmerge(self)
1104    }
1105
1106    /// Return an iterator adaptor that flattens an iterator of iterators by
1107    /// merging them according to the given closure.
1108    ///
1109    /// The closure `first` is called with two elements *a*, *b* and should
1110    /// return `true` if *a* is ordered before *b*.
1111    ///
1112    /// If all base iterators are sorted according to `first`, the result is
1113    /// sorted.
1114    ///
1115    /// Iterator element type is `Self::Item`.
1116    ///
1117    /// ```
1118    /// use itertools::Itertools;
1119    ///
1120    /// let a = vec![-1f64, 2., 3., -5., 6., -7.];
1121    /// let b = vec![0., 2., -4.];
1122    /// let mut it = vec![a, b].into_iter().kmerge_by(|a, b| a.abs() < b.abs());
1123    /// assert_eq!(it.next(), Some(0.));
1124    /// assert_eq!(it.last(), Some(-7.));
1125    /// ```
1126    #[cfg(feature = "use_alloc")]
1127    fn kmerge_by<F>(self, first: F)
1128        -> KMergeBy<<Self::Item as IntoIterator>::IntoIter, F>
1129        where Self: Sized,
1130              Self::Item: IntoIterator,
1131              F: FnMut(&<Self::Item as IntoIterator>::Item,
1132                       &<Self::Item as IntoIterator>::Item) -> bool
1133    {
1134        kmerge_by(self, first)
1135    }
1136
1137    /// Return an iterator adaptor that iterates over the cartesian product of
1138    /// the element sets of two iterators `self` and `J`.
1139    ///
1140    /// Iterator element type is `(Self::Item, J::Item)`.
1141    ///
1142    /// ```
1143    /// use itertools::Itertools;
1144    ///
1145    /// let it = (0..2).cartesian_product("αβ".chars());
1146    /// itertools::assert_equal(it, vec![(0, 'α'), (0, 'β'), (1, 'α'), (1, 'β')]);
1147    /// ```
1148    fn cartesian_product<J>(self, other: J) -> Product<Self, J::IntoIter>
1149        where Self: Sized,
1150              Self::Item: Clone,
1151              J: IntoIterator,
1152              J::IntoIter: Clone
1153    {
1154        adaptors::cartesian_product(self, other.into_iter())
1155    }
1156
1157    /// Return an iterator adaptor that iterates over the cartesian product of
1158    /// all subiterators returned by meta-iterator `self`.
1159    ///
1160    /// All provided iterators must yield the same `Item` type. To generate
1161    /// the product of iterators yielding multiple types, use the
1162    /// [`iproduct`] macro instead.
1163    ///
1164    ///
1165    /// The iterator element type is `Vec<T>`, where `T` is the iterator element
1166    /// of the subiterators.
1167    ///
1168    /// ```
1169    /// use itertools::Itertools;
1170    /// let mut multi_prod = (0..3).map(|i| (i * 2)..(i * 2 + 2))
1171    ///     .multi_cartesian_product();
1172    /// assert_eq!(multi_prod.next(), Some(vec![0, 2, 4]));
1173    /// assert_eq!(multi_prod.next(), Some(vec![0, 2, 5]));
1174    /// assert_eq!(multi_prod.next(), Some(vec![0, 3, 4]));
1175    /// assert_eq!(multi_prod.next(), Some(vec![0, 3, 5]));
1176    /// assert_eq!(multi_prod.next(), Some(vec![1, 2, 4]));
1177    /// assert_eq!(multi_prod.next(), Some(vec![1, 2, 5]));
1178    /// assert_eq!(multi_prod.next(), Some(vec![1, 3, 4]));
1179    /// assert_eq!(multi_prod.next(), Some(vec![1, 3, 5]));
1180    /// assert_eq!(multi_prod.next(), None);
1181    /// ```
1182    #[cfg(feature = "use_alloc")]
1183    fn multi_cartesian_product(self) -> MultiProduct<<Self::Item as IntoIterator>::IntoIter>
1184        where Self: Sized,
1185              Self::Item: IntoIterator,
1186              <Self::Item as IntoIterator>::IntoIter: Clone,
1187              <Self::Item as IntoIterator>::Item: Clone
1188    {
1189        adaptors::multi_cartesian_product(self)
1190    }
1191
1192    /// Return an iterator adaptor that uses the passed-in closure to
1193    /// optionally merge together consecutive elements.
1194    ///
1195    /// The closure `f` is passed two elements, `previous` and `current` and may
1196    /// return either (1) `Ok(combined)` to merge the two values or
1197    /// (2) `Err((previous', current'))` to indicate they can't be merged.
1198    /// In (2), the value `previous'` is emitted by the iterator.
1199    /// Either (1) `combined` or (2) `current'` becomes the previous value
1200    /// when coalesce continues with the next pair of elements to merge. The
1201    /// value that remains at the end is also emitted by the iterator.
1202    ///
1203    /// Iterator element type is `Self::Item`.
1204    ///
1205    /// This iterator is *fused*.
1206    ///
1207    /// ```
1208    /// use itertools::Itertools;
1209    ///
1210    /// // sum same-sign runs together
1211    /// let data = vec![-1., -2., -3., 3., 1., 0., -1.];
1212    /// itertools::assert_equal(data.into_iter().coalesce(|x, y|
1213    ///         if (x >= 0.) == (y >= 0.) {
1214    ///             Ok(x + y)
1215    ///         } else {
1216    ///             Err((x, y))
1217    ///         }),
1218    ///         vec![-6., 4., -1.]);
1219    /// ```
1220    fn coalesce<F>(self, f: F) -> Coalesce<Self, F>
1221        where Self: Sized,
1222              F: FnMut(Self::Item, Self::Item)
1223                       -> Result<Self::Item, (Self::Item, Self::Item)>
1224    {
1225        adaptors::coalesce(self, f)
1226    }
1227
1228    /// Remove duplicates from sections of consecutive identical elements.
1229    /// If the iterator is sorted, all elements will be unique.
1230    ///
1231    /// Iterator element type is `Self::Item`.
1232    ///
1233    /// This iterator is *fused*.
1234    ///
1235    /// ```
1236    /// use itertools::Itertools;
1237    ///
1238    /// let data = vec![1., 1., 2., 3., 3., 2., 2.];
1239    /// itertools::assert_equal(data.into_iter().dedup(),
1240    ///                         vec![1., 2., 3., 2.]);
1241    /// ```
1242    fn dedup(self) -> Dedup<Self>
1243        where Self: Sized,
1244              Self::Item: PartialEq,
1245    {
1246        adaptors::dedup(self)
1247    }
1248
1249    /// Remove duplicates from sections of consecutive identical elements,
1250    /// determining equality using a comparison function.
1251    /// If the iterator is sorted, all elements will be unique.
1252    ///
1253    /// Iterator element type is `Self::Item`.
1254    ///
1255    /// This iterator is *fused*.
1256    ///
1257    /// ```
1258    /// use itertools::Itertools;
1259    ///
1260    /// let data = vec![(0, 1.), (1, 1.), (0, 2.), (0, 3.), (1, 3.), (1, 2.), (2, 2.)];
1261    /// itertools::assert_equal(data.into_iter().dedup_by(|x, y| x.1 == y.1),
1262    ///                         vec![(0, 1.), (0, 2.), (0, 3.), (1, 2.)]);
1263    /// ```
1264    fn dedup_by<Cmp>(self, cmp: Cmp) -> DedupBy<Self, Cmp>
1265        where Self: Sized,
1266              Cmp: FnMut(&Self::Item, &Self::Item)->bool,
1267    {
1268        adaptors::dedup_by(self, cmp)
1269    }
1270
1271    /// Remove duplicates from sections of consecutive identical elements, while keeping a count of
1272    /// how many repeated elements were present.
1273    /// If the iterator is sorted, all elements will be unique.
1274    ///
1275    /// Iterator element type is `(usize, Self::Item)`.
1276    ///
1277    /// This iterator is *fused*.
1278    ///
1279    /// ```
1280    /// use itertools::Itertools;
1281    ///
1282    /// let data = vec!['a', 'a', 'b', 'c', 'c', 'b', 'b'];
1283    /// itertools::assert_equal(data.into_iter().dedup_with_count(),
1284    ///                         vec![(2, 'a'), (1, 'b'), (2, 'c'), (2, 'b')]);
1285    /// ```
1286    fn dedup_with_count(self) -> DedupWithCount<Self>
1287    where
1288        Self: Sized,
1289    {
1290        adaptors::dedup_with_count(self)
1291    }
1292
1293    /// Remove duplicates from sections of consecutive identical elements, while keeping a count of
1294    /// how many repeated elements were present.
1295    /// This will determine equality using a comparison function.
1296    /// If the iterator is sorted, all elements will be unique.
1297    ///
1298    /// Iterator element type is `(usize, Self::Item)`.
1299    ///
1300    /// This iterator is *fused*.
1301    ///
1302    /// ```
1303    /// use itertools::Itertools;
1304    ///
1305    /// let data = vec![(0, 'a'), (1, 'a'), (0, 'b'), (0, 'c'), (1, 'c'), (1, 'b'), (2, 'b')];
1306    /// itertools::assert_equal(data.into_iter().dedup_by_with_count(|x, y| x.1 == y.1),
1307    ///                         vec![(2, (0, 'a')), (1, (0, 'b')), (2, (0, 'c')), (2, (1, 'b'))]);
1308    /// ```
1309    fn dedup_by_with_count<Cmp>(self, cmp: Cmp) -> DedupByWithCount<Self, Cmp>
1310    where
1311        Self: Sized,
1312        Cmp: FnMut(&Self::Item, &Self::Item) -> bool,
1313    {
1314        adaptors::dedup_by_with_count(self, cmp)
1315    }
1316
1317    /// Return an iterator adaptor that produces elements that appear more than once during the
1318    /// iteration. Duplicates are detected using hash and equality.
1319    ///
1320    /// The iterator is stable, returning the duplicate items in the order in which they occur in
1321    /// the adapted iterator. Each duplicate item is returned exactly once. If an item appears more
1322    /// than twice, the second item is the item retained and the rest are discarded.
1323    ///
1324    /// ```
1325    /// use itertools::Itertools;
1326    ///
1327    /// let data = vec![10, 20, 30, 20, 40, 10, 50];
1328    /// itertools::assert_equal(data.into_iter().duplicates(),
1329    ///                         vec![20, 10]);
1330    /// ```
1331    #[cfg(feature = "use_std")]
1332    fn duplicates(self) -> Duplicates<Self>
1333        where Self: Sized,
1334              Self::Item: Eq + Hash
1335    {
1336        duplicates_impl::duplicates(self)
1337    }
1338
1339    /// Return an iterator adaptor that produces elements that appear more than once during the
1340    /// iteration. Duplicates are detected using hash and equality.
1341    ///
1342    /// Duplicates are detected by comparing the key they map to with the keying function `f` by
1343    /// hash and equality. The keys are stored in a hash map in the iterator.
1344    ///
1345    /// The iterator is stable, returning the duplicate items in the order in which they occur in
1346    /// the adapted iterator. Each duplicate item is returned exactly once. If an item appears more
1347    /// than twice, the second item is the item retained and the rest are discarded.
1348    ///
1349    /// ```
1350    /// use itertools::Itertools;
1351    ///
1352    /// let data = vec!["a", "bb", "aa", "c", "ccc"];
1353    /// itertools::assert_equal(data.into_iter().duplicates_by(|s| s.len()),
1354    ///                         vec!["aa", "c"]);
1355    /// ```
1356    #[cfg(feature = "use_std")]
1357    fn duplicates_by<V, F>(self, f: F) -> DuplicatesBy<Self, V, F>
1358        where Self: Sized,
1359              V: Eq + Hash,
1360              F: FnMut(&Self::Item) -> V
1361    {
1362        duplicates_impl::duplicates_by(self, f)
1363    }
1364
1365    /// Return an iterator adaptor that filters out elements that have
1366    /// already been produced once during the iteration. Duplicates
1367    /// are detected using hash and equality.
1368    ///
1369    /// Clones of visited elements are stored in a hash set in the
1370    /// iterator.
1371    ///
1372    /// The iterator is stable, returning the non-duplicate items in the order
1373    /// in which they occur in the adapted iterator. In a set of duplicate
1374    /// items, the first item encountered is the item retained.
1375    ///
1376    /// ```
1377    /// use itertools::Itertools;
1378    ///
1379    /// let data = vec![10, 20, 30, 20, 40, 10, 50];
1380    /// itertools::assert_equal(data.into_iter().unique(),
1381    ///                         vec![10, 20, 30, 40, 50]);
1382    /// ```
1383    #[cfg(feature = "use_std")]
1384    fn unique(self) -> Unique<Self>
1385        where Self: Sized,
1386              Self::Item: Clone + Eq + Hash
1387    {
1388        unique_impl::unique(self)
1389    }
1390
1391    /// Return an iterator adaptor that filters out elements that have
1392    /// already been produced once during the iteration.
1393    ///
1394    /// Duplicates are detected by comparing the key they map to
1395    /// with the keying function `f` by hash and equality.
1396    /// The keys are stored in a hash set in the iterator.
1397    ///
1398    /// The iterator is stable, returning the non-duplicate items in the order
1399    /// in which they occur in the adapted iterator. In a set of duplicate
1400    /// items, the first item encountered is the item retained.
1401    ///
1402    /// ```
1403    /// use itertools::Itertools;
1404    ///
1405    /// let data = vec!["a", "bb", "aa", "c", "ccc"];
1406    /// itertools::assert_equal(data.into_iter().unique_by(|s| s.len()),
1407    ///                         vec!["a", "bb", "ccc"]);
1408    /// ```
1409    #[cfg(feature = "use_std")]
1410    fn unique_by<V, F>(self, f: F) -> UniqueBy<Self, V, F>
1411        where Self: Sized,
1412              V: Eq + Hash,
1413              F: FnMut(&Self::Item) -> V
1414    {
1415        unique_impl::unique_by(self, f)
1416    }
1417
1418    /// Return an iterator adaptor that borrows from this iterator and
1419    /// takes items while the closure `accept` returns `true`.
1420    ///
1421    /// This adaptor can only be used on iterators that implement `PeekingNext`
1422    /// like `.peekable()`, `put_back` and a few other collection iterators.
1423    ///
1424    /// The last and rejected element (first `false`) is still available when
1425    /// `peeking_take_while` is done.
1426    ///
1427    ///
1428    /// See also [`.take_while_ref()`](Itertools::take_while_ref)
1429    /// which is a similar adaptor.
1430    fn peeking_take_while<F>(&mut self, accept: F) -> PeekingTakeWhile<Self, F>
1431        where Self: Sized + PeekingNext,
1432              F: FnMut(&Self::Item) -> bool,
1433    {
1434        peeking_take_while::peeking_take_while(self, accept)
1435    }
1436
1437    /// Return an iterator adaptor that borrows from a `Clone`-able iterator
1438    /// to only pick off elements while the predicate `accept` returns `true`.
1439    ///
1440    /// It uses the `Clone` trait to restore the original iterator so that the
1441    /// last and rejected element (first `false`) is still available when
1442    /// `take_while_ref` is done.
1443    ///
1444    /// ```
1445    /// use itertools::Itertools;
1446    ///
1447    /// let mut hexadecimals = "0123456789abcdef".chars();
1448    ///
1449    /// let decimals = hexadecimals.take_while_ref(|c| c.is_numeric())
1450    ///                            .collect::<String>();
1451    /// assert_eq!(decimals, "0123456789");
1452    /// assert_eq!(hexadecimals.next(), Some('a'));
1453    ///
1454    /// ```
1455    fn take_while_ref<F>(&mut self, accept: F) -> TakeWhileRef<Self, F>
1456        where Self: Clone,
1457              F: FnMut(&Self::Item) -> bool
1458    {
1459        adaptors::take_while_ref(self, accept)
1460    }
1461
1462    /// Returns an iterator adaptor that consumes elements while the given
1463    /// predicate is `true`, *including* the element for which the predicate
1464    /// first returned `false`.
1465    ///
1466    /// The [`.take_while()`][std::iter::Iterator::take_while] adaptor is useful
1467    /// when you want items satisfying a predicate, but to know when to stop
1468    /// taking elements, we have to consume that first element that doesn't
1469    /// satisfy the predicate. This adaptor includes that element where
1470    /// [`.take_while()`][std::iter::Iterator::take_while] would drop it.
1471    ///
1472    /// The [`.take_while_ref()`][crate::Itertools::take_while_ref] adaptor
1473    /// serves a similar purpose, but this adaptor doesn't require [`Clone`]ing
1474    /// the underlying elements.
1475    ///
1476    /// ```rust
1477    /// # use itertools::Itertools;
1478    /// let items = vec![1, 2, 3, 4, 5];
1479    /// let filtered: Vec<_> = items
1480    ///     .into_iter()
1481    ///     .take_while_inclusive(|&n| n % 3 != 0)
1482    ///     .collect();
1483    ///
1484    /// assert_eq!(filtered, vec![1, 2, 3]);
1485    /// ```
1486    ///
1487    /// ```rust
1488    /// # use itertools::Itertools;
1489    /// let items = vec![1, 2, 3, 4, 5];
1490    ///
1491    /// let take_while_inclusive_result: Vec<_> = items
1492    ///     .iter()
1493    ///     .copied()
1494    ///     .take_while_inclusive(|&n| n % 3 != 0)
1495    ///     .collect();
1496    /// let take_while_result: Vec<_> = items
1497    ///     .into_iter()
1498    ///     .take_while(|&n| n % 3 != 0)
1499    ///     .collect();
1500    ///
1501    /// assert_eq!(take_while_inclusive_result, vec![1, 2, 3]);
1502    /// assert_eq!(take_while_result, vec![1, 2]);
1503    /// // both iterators have the same items remaining at this point---the 3
1504    /// // is lost from the `take_while` vec
1505    /// ```
1506    ///
1507    /// ```rust
1508    /// # use itertools::Itertools;
1509    /// #[derive(Debug, PartialEq)]
1510    /// struct NoCloneImpl(i32);
1511    ///
1512    /// let non_clonable_items: Vec<_> = vec![1, 2, 3, 4, 5]
1513    ///     .into_iter()
1514    ///     .map(NoCloneImpl)
1515    ///     .collect();
1516    /// let filtered: Vec<_> = non_clonable_items
1517    ///     .into_iter()
1518    ///     .take_while_inclusive(|n| n.0 % 3 != 0)
1519    ///     .collect();
1520    /// let expected: Vec<_> = vec![1, 2, 3].into_iter().map(NoCloneImpl).collect();
1521    /// assert_eq!(filtered, expected);
1522    fn take_while_inclusive<F>(&mut self, accept: F) -> TakeWhileInclusive<Self, F>
1523    where
1524        Self: Sized,
1525        F: FnMut(&Self::Item) -> bool,
1526    {
1527        take_while_inclusive::TakeWhileInclusive::new(self, accept)
1528    }
1529
1530    /// Return an iterator adaptor that filters `Option<A>` iterator elements
1531    /// and produces `A`. Stops on the first `None` encountered.
1532    ///
1533    /// Iterator element type is `A`, the unwrapped element.
1534    ///
1535    /// ```
1536    /// use itertools::Itertools;
1537    ///
1538    /// // List all hexadecimal digits
1539    /// itertools::assert_equal(
1540    ///     (0..).map(|i| std::char::from_digit(i, 16)).while_some(),
1541    ///     "0123456789abcdef".chars());
1542    ///
1543    /// ```
1544    fn while_some<A>(self) -> WhileSome<Self>
1545        where Self: Sized + Iterator<Item = Option<A>>
1546    {
1547        adaptors::while_some(self)
1548    }
1549
1550    /// Return an iterator adaptor that iterates over the combinations of the
1551    /// elements from an iterator.
1552    ///
1553    /// Iterator element can be any homogeneous tuple of type `Self::Item` with
1554    /// size up to 12.
1555    ///
1556    /// ```
1557    /// use itertools::Itertools;
1558    ///
1559    /// let mut v = Vec::new();
1560    /// for (a, b) in (1..5).tuple_combinations() {
1561    ///     v.push((a, b));
1562    /// }
1563    /// assert_eq!(v, vec![(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]);
1564    ///
1565    /// let mut it = (1..5).tuple_combinations();
1566    /// assert_eq!(Some((1, 2, 3)), it.next());
1567    /// assert_eq!(Some((1, 2, 4)), it.next());
1568    /// assert_eq!(Some((1, 3, 4)), it.next());
1569    /// assert_eq!(Some((2, 3, 4)), it.next());
1570    /// assert_eq!(None, it.next());
1571    ///
1572    /// // this requires a type hint
1573    /// let it = (1..5).tuple_combinations::<(_, _, _)>();
1574    /// itertools::assert_equal(it, vec![(1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4)]);
1575    ///
1576    /// // you can also specify the complete type
1577    /// use itertools::TupleCombinations;
1578    /// use std::ops::Range;
1579    ///
1580    /// let it: TupleCombinations<Range<u32>, (u32, u32, u32)> = (1..5).tuple_combinations();
1581    /// itertools::assert_equal(it, vec![(1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4)]);
1582    /// ```
1583    fn tuple_combinations<T>(self) -> TupleCombinations<Self, T>
1584        where Self: Sized + Clone,
1585              Self::Item: Clone,
1586              T: adaptors::HasCombination<Self>,
1587    {
1588        adaptors::tuple_combinations(self)
1589    }
1590
1591    /// Return an iterator adaptor that iterates over the `k`-length combinations of
1592    /// the elements from an iterator.
1593    ///
1594    /// Iterator element type is `Vec<Self::Item>`. The iterator produces a new Vec per iteration,
1595    /// and clones the iterator elements.
1596    ///
1597    /// ```
1598    /// use itertools::Itertools;
1599    ///
1600    /// let it = (1..5).combinations(3);
1601    /// itertools::assert_equal(it, vec![
1602    ///     vec![1, 2, 3],
1603    ///     vec![1, 2, 4],
1604    ///     vec![1, 3, 4],
1605    ///     vec![2, 3, 4],
1606    /// ]);
1607    /// ```
1608    ///
1609    /// Note: Combinations does not take into account the equality of the iterated values.
1610    /// ```
1611    /// use itertools::Itertools;
1612    ///
1613    /// let it = vec![1, 2, 2].into_iter().combinations(2);
1614    /// itertools::assert_equal(it, vec![
1615    ///     vec![1, 2], // Note: these are the same
1616    ///     vec![1, 2], // Note: these are the same
1617    ///     vec![2, 2],
1618    /// ]);
1619    /// ```
1620    #[cfg(feature = "use_alloc")]
1621    fn combinations(self, k: usize) -> Combinations<Self>
1622        where Self: Sized,
1623              Self::Item: Clone
1624    {
1625        combinations::combinations(self, k)
1626    }
1627
1628    /// Return an iterator that iterates over the `k`-length combinations of
1629    /// the elements from an iterator, with replacement.
1630    ///
1631    /// Iterator element type is `Vec<Self::Item>`. The iterator produces a new Vec per iteration,
1632    /// and clones the iterator elements.
1633    ///
1634    /// ```
1635    /// use itertools::Itertools;
1636    ///
1637    /// let it = (1..4).combinations_with_replacement(2);
1638    /// itertools::assert_equal(it, vec![
1639    ///     vec![1, 1],
1640    ///     vec![1, 2],
1641    ///     vec![1, 3],
1642    ///     vec![2, 2],
1643    ///     vec![2, 3],
1644    ///     vec![3, 3],
1645    /// ]);
1646    /// ```
1647    #[cfg(feature = "use_alloc")]
1648    fn combinations_with_replacement(self, k: usize) -> CombinationsWithReplacement<Self>
1649    where
1650        Self: Sized,
1651        Self::Item: Clone,
1652    {
1653        combinations_with_replacement::combinations_with_replacement(self, k)
1654    }
1655
1656    /// Return an iterator adaptor that iterates over all k-permutations of the
1657    /// elements from an iterator.
1658    ///
1659    /// Iterator element type is `Vec<Self::Item>` with length `k`. The iterator
1660    /// produces a new Vec per iteration, and clones the iterator elements.
1661    ///
1662    /// If `k` is greater than the length of the input iterator, the resultant
1663    /// iterator adaptor will be empty.
1664    ///
1665    /// ```
1666    /// use itertools::Itertools;
1667    ///
1668    /// let perms = (5..8).permutations(2);
1669    /// itertools::assert_equal(perms, vec![
1670    ///     vec![5, 6],
1671    ///     vec![5, 7],
1672    ///     vec![6, 5],
1673    ///     vec![6, 7],
1674    ///     vec![7, 5],
1675    ///     vec![7, 6],
1676    /// ]);
1677    /// ```
1678    ///
1679    /// Note: Permutations does not take into account the equality of the iterated values.
1680    ///
1681    /// ```
1682    /// use itertools::Itertools;
1683    ///
1684    /// let it = vec![2, 2].into_iter().permutations(2);
1685    /// itertools::assert_equal(it, vec![
1686    ///     vec![2, 2], // Note: these are the same
1687    ///     vec![2, 2], // Note: these are the same
1688    /// ]);
1689    /// ```
1690    ///
1691    /// Note: The source iterator is collected lazily, and will not be
1692    /// re-iterated if the permutations adaptor is completed and re-iterated.
1693    #[cfg(feature = "use_alloc")]
1694    fn permutations(self, k: usize) -> Permutations<Self>
1695        where Self: Sized,
1696              Self::Item: Clone
1697    {
1698        permutations::permutations(self, k)
1699    }
1700
1701    /// Return an iterator that iterates through the powerset of the elements from an
1702    /// iterator.
1703    ///
1704    /// Iterator element type is `Vec<Self::Item>`. The iterator produces a new `Vec`
1705    /// per iteration, and clones the iterator elements.
1706    ///
1707    /// The powerset of a set contains all subsets including the empty set and the full
1708    /// input set. A powerset has length _2^n_ where _n_ is the length of the input
1709    /// set.
1710    ///
1711    /// Each `Vec` produced by this iterator represents a subset of the elements
1712    /// produced by the source iterator.
1713    ///
1714    /// ```
1715    /// use itertools::Itertools;
1716    ///
1717    /// let sets = (1..4).powerset().collect::<Vec<_>>();
1718    /// itertools::assert_equal(sets, vec![
1719    ///     vec![],
1720    ///     vec![1],
1721    ///     vec![2],
1722    ///     vec![3],
1723    ///     vec![1, 2],
1724    ///     vec![1, 3],
1725    ///     vec![2, 3],
1726    ///     vec![1, 2, 3],
1727    /// ]);
1728    /// ```
1729    #[cfg(feature = "use_alloc")]
1730    fn powerset(self) -> Powerset<Self>
1731        where Self: Sized,
1732              Self::Item: Clone,
1733    {
1734        powerset::powerset(self)
1735    }
1736
1737    /// Return an iterator adaptor that pads the sequence to a minimum length of
1738    /// `min` by filling missing elements using a closure `f`.
1739    ///
1740    /// Iterator element type is `Self::Item`.
1741    ///
1742    /// ```
1743    /// use itertools::Itertools;
1744    ///
1745    /// let it = (0..5).pad_using(10, |i| 2*i);
1746    /// itertools::assert_equal(it, vec![0, 1, 2, 3, 4, 10, 12, 14, 16, 18]);
1747    ///
1748    /// let it = (0..10).pad_using(5, |i| 2*i);
1749    /// itertools::assert_equal(it, vec![0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);
1750    ///
1751    /// let it = (0..5).pad_using(10, |i| 2*i).rev();
1752    /// itertools::assert_equal(it, vec![18, 16, 14, 12, 10, 4, 3, 2, 1, 0]);
1753    /// ```
1754    fn pad_using<F>(self, min: usize, f: F) -> PadUsing<Self, F>
1755        where Self: Sized,
1756              F: FnMut(usize) -> Self::Item
1757    {
1758        pad_tail::pad_using(self, min, f)
1759    }
1760
1761    /// Return an iterator adaptor that combines each element with a `Position` to
1762    /// ease special-case handling of the first or last elements.
1763    ///
1764    /// Iterator element type is
1765    /// [`(Position, Self::Item)`](Position)
1766    ///
1767    /// ```
1768    /// use itertools::{Itertools, Position};
1769    ///
1770    /// let it = (0..4).with_position();
1771    /// itertools::assert_equal(it,
1772    ///                         vec![(Position::First, 0),
1773    ///                              (Position::Middle, 1),
1774    ///                              (Position::Middle, 2),
1775    ///                              (Position::Last, 3)]);
1776    ///
1777    /// let it = (0..1).with_position();
1778    /// itertools::assert_equal(it, vec![(Position::Only, 0)]);
1779    /// ```
1780    fn with_position(self) -> WithPosition<Self>
1781        where Self: Sized,
1782    {
1783        with_position::with_position(self)
1784    }
1785
1786    /// Return an iterator adaptor that yields the indices of all elements
1787    /// satisfying a predicate, counted from the start of the iterator.
1788    ///
1789    /// Equivalent to `iter.enumerate().filter(|(_, v)| predicate(v)).map(|(i, _)| i)`.
1790    ///
1791    /// ```
1792    /// use itertools::Itertools;
1793    ///
1794    /// let data = vec![1, 2, 3, 3, 4, 6, 7, 9];
1795    /// itertools::assert_equal(data.iter().positions(|v| v % 2 == 0), vec![1, 4, 5]);
1796    ///
1797    /// itertools::assert_equal(data.iter().positions(|v| v % 2 == 1).rev(), vec![7, 6, 3, 2, 0]);
1798    /// ```
1799    fn positions<P>(self, predicate: P) -> Positions<Self, P>
1800        where Self: Sized,
1801              P: FnMut(Self::Item) -> bool,
1802    {
1803        adaptors::positions(self, predicate)
1804    }
1805
1806    /// Return an iterator adaptor that applies a mutating function
1807    /// to each element before yielding it.
1808    ///
1809    /// ```
1810    /// use itertools::Itertools;
1811    ///
1812    /// let input = vec![vec![1], vec![3, 2, 1]];
1813    /// let it = input.into_iter().update(|mut v| v.push(0));
1814    /// itertools::assert_equal(it, vec![vec![1, 0], vec![3, 2, 1, 0]]);
1815    /// ```
1816    fn update<F>(self, updater: F) -> Update<Self, F>
1817        where Self: Sized,
1818              F: FnMut(&mut Self::Item),
1819    {
1820        adaptors::update(self, updater)
1821    }
1822
1823    // non-adaptor methods
1824    /// Advances the iterator and returns the next items grouped in a tuple of
1825    /// a specific size (up to 12).
1826    ///
1827    /// If there are enough elements to be grouped in a tuple, then the tuple is
1828    /// returned inside `Some`, otherwise `None` is returned.
1829    ///
1830    /// ```
1831    /// use itertools::Itertools;
1832    ///
1833    /// let mut iter = 1..5;
1834    ///
1835    /// assert_eq!(Some((1, 2)), iter.next_tuple());
1836    /// ```
1837    fn next_tuple<T>(&mut self) -> Option<T>
1838        where Self: Sized + Iterator<Item = T::Item>,
1839              T: traits::HomogeneousTuple
1840    {
1841        T::collect_from_iter_no_buf(self)
1842    }
1843
1844    /// Collects all items from the iterator into a tuple of a specific size
1845    /// (up to 12).
1846    ///
1847    /// If the number of elements inside the iterator is **exactly** equal to
1848    /// the tuple size, then the tuple is returned inside `Some`, otherwise
1849    /// `None` is returned.
1850    ///
1851    /// ```
1852    /// use itertools::Itertools;
1853    ///
1854    /// let iter = 1..3;
1855    ///
1856    /// if let Some((x, y)) = iter.collect_tuple() {
1857    ///     assert_eq!((x, y), (1, 2))
1858    /// } else {
1859    ///     panic!("Expected two elements")
1860    /// }
1861    /// ```
1862    fn collect_tuple<T>(mut self) -> Option<T>
1863        where Self: Sized + Iterator<Item = T::Item>,
1864              T: traits::HomogeneousTuple
1865    {
1866        match self.next_tuple() {
1867            elt @ Some(_) => match self.next() {
1868                Some(_) => None,
1869                None => elt,
1870            },
1871            _ => None
1872        }
1873    }
1874
1875
1876    /// Find the position and value of the first element satisfying a predicate.
1877    ///
1878    /// The iterator is not advanced past the first element found.
1879    ///
1880    /// ```
1881    /// use itertools::Itertools;
1882    ///
1883    /// let text = "Hα";
1884    /// assert_eq!(text.chars().find_position(|ch| ch.is_lowercase()), Some((1, 'α')));
1885    /// ```
1886    fn find_position<P>(&mut self, mut pred: P) -> Option<(usize, Self::Item)>
1887        where P: FnMut(&Self::Item) -> bool
1888    {
1889        for (index, elt) in self.enumerate() {
1890            if pred(&elt) {
1891                return Some((index, elt));
1892            }
1893        }
1894        None
1895    }
1896    /// Find the value of the first element satisfying a predicate or return the last element, if any.
1897    ///
1898    /// The iterator is not advanced past the first element found.
1899    ///
1900    /// ```
1901    /// use itertools::Itertools;
1902    ///
1903    /// let numbers = [1, 2, 3, 4];
1904    /// assert_eq!(numbers.iter().find_or_last(|&&x| x > 5), Some(&4));
1905    /// assert_eq!(numbers.iter().find_or_last(|&&x| x > 2), Some(&3));
1906    /// assert_eq!(std::iter::empty::<i32>().find_or_last(|&x| x > 5), None);
1907    /// ```
1908    fn find_or_last<P>(mut self, mut predicate: P) -> Option<Self::Item>
1909        where Self: Sized,
1910              P: FnMut(&Self::Item) -> bool,
1911    {
1912        let mut prev = None;
1913        self.find_map(|x| if predicate(&x) { Some(x) } else { prev = Some(x); None })
1914            .or(prev)
1915    }
1916    /// Find the value of the first element satisfying a predicate or return the first element, if any.
1917    ///
1918    /// The iterator is not advanced past the first element found.
1919    ///
1920    /// ```
1921    /// use itertools::Itertools;
1922    ///
1923    /// let numbers = [1, 2, 3, 4];
1924    /// assert_eq!(numbers.iter().find_or_first(|&&x| x > 5), Some(&1));
1925    /// assert_eq!(numbers.iter().find_or_first(|&&x| x > 2), Some(&3));
1926    /// assert_eq!(std::iter::empty::<i32>().find_or_first(|&x| x > 5), None);
1927    /// ```
1928    fn find_or_first<P>(mut self, mut predicate: P) -> Option<Self::Item>
1929        where Self: Sized,
1930              P: FnMut(&Self::Item) -> bool,
1931    {
1932        let first = self.next()?;
1933        Some(if predicate(&first) {
1934            first
1935        } else {
1936            self.find(|x| predicate(x)).unwrap_or(first)
1937        })
1938    }
1939    /// Returns `true` if the given item is present in this iterator.
1940    ///
1941    /// This method is short-circuiting. If the given item is present in this
1942    /// iterator, this method will consume the iterator up-to-and-including
1943    /// the item. If the given item is not present in this iterator, the
1944    /// iterator will be exhausted.
1945    ///
1946    /// ```
1947    /// use itertools::Itertools;
1948    ///
1949    /// #[derive(PartialEq, Debug)]
1950    /// enum Enum { A, B, C, D, E, }
1951    ///
1952    /// let mut iter = vec![Enum::A, Enum::B, Enum::C, Enum::D].into_iter();
1953    ///
1954    /// // search `iter` for `B`
1955    /// assert_eq!(iter.contains(&Enum::B), true);
1956    /// // `B` was found, so the iterator now rests at the item after `B` (i.e, `C`).
1957    /// assert_eq!(iter.next(), Some(Enum::C));
1958    ///
1959    /// // search `iter` for `E`
1960    /// assert_eq!(iter.contains(&Enum::E), false);
1961    /// // `E` wasn't found, so `iter` is now exhausted
1962    /// assert_eq!(iter.next(), None);
1963    /// ```
1964    fn contains<Q>(&mut self, query: &Q) -> bool
1965    where
1966        Self: Sized,
1967        Self::Item: Borrow<Q>,
1968        Q: PartialEq,
1969    {
1970        self.any(|x| x.borrow() == query)
1971    }
1972
1973    /// Check whether all elements compare equal.
1974    ///
1975    /// Empty iterators are considered to have equal elements:
1976    ///
1977    /// ```
1978    /// use itertools::Itertools;
1979    ///
1980    /// let data = vec![1, 1, 1, 2, 2, 3, 3, 3, 4, 5, 5];
1981    /// assert!(!data.iter().all_equal());
1982    /// assert!(data[0..3].iter().all_equal());
1983    /// assert!(data[3..5].iter().all_equal());
1984    /// assert!(data[5..8].iter().all_equal());
1985    ///
1986    /// let data : Option<usize> = None;
1987    /// assert!(data.into_iter().all_equal());
1988    /// ```
1989    fn all_equal(&mut self) -> bool
1990        where Self: Sized,
1991              Self::Item: PartialEq,
1992    {
1993        match self.next() {
1994            None => true,
1995            Some(a) => self.all(|x| a == x),
1996        }
1997    }
1998
1999    /// If there are elements and they are all equal, return a single copy of that element.
2000    /// If there are no elements, return an Error containing None.
2001    /// If there are elements and they are not all equal, return a tuple containing the first
2002    /// two non-equal elements found.
2003    ///
2004    /// ```
2005    /// use itertools::Itertools;
2006    ///
2007    /// let data = vec![1, 1, 1, 2, 2, 3, 3, 3, 4, 5, 5];
2008    /// assert_eq!(data.iter().all_equal_value(), Err(Some((&1, &2))));
2009    /// assert_eq!(data[0..3].iter().all_equal_value(), Ok(&1));
2010    /// assert_eq!(data[3..5].iter().all_equal_value(), Ok(&2));
2011    /// assert_eq!(data[5..8].iter().all_equal_value(), Ok(&3));
2012    ///
2013    /// let data : Option<usize> = None;
2014    /// assert_eq!(data.into_iter().all_equal_value(), Err(None));
2015    /// ```
2016    fn all_equal_value(&mut self) -> Result<Self::Item, Option<(Self::Item, Self::Item)>>
2017        where
2018            Self: Sized,
2019            Self::Item: PartialEq
2020    {
2021        let first = self.next().ok_or(None)?;
2022        let other = self.find(|x| x != &first);
2023        if let Some(other) = other {
2024            Err(Some((first, other)))
2025        } else {
2026            Ok(first)
2027        }
2028    }
2029
2030    /// Check whether all elements are unique (non equal).
2031    ///
2032    /// Empty iterators are considered to have unique elements:
2033    ///
2034    /// ```
2035    /// use itertools::Itertools;
2036    ///
2037    /// let data = vec![1, 2, 3, 4, 1, 5];
2038    /// assert!(!data.iter().all_unique());
2039    /// assert!(data[0..4].iter().all_unique());
2040    /// assert!(data[1..6].iter().all_unique());
2041    ///
2042    /// let data : Option<usize> = None;
2043    /// assert!(data.into_iter().all_unique());
2044    /// ```
2045    #[cfg(feature = "use_std")]
2046    fn all_unique(&mut self) -> bool
2047        where Self: Sized,
2048              Self::Item: Eq + Hash
2049    {
2050        let mut used = HashSet::new();
2051        self.all(move |elt| used.insert(elt))
2052    }
2053
2054    /// Consume the first `n` elements from the iterator eagerly,
2055    /// and return the same iterator again.
2056    ///
2057    /// It works similarly to *.skip(* `n` *)* except it is eager and
2058    /// preserves the iterator type.
2059    ///
2060    /// ```
2061    /// use itertools::Itertools;
2062    ///
2063    /// let mut iter = "αβγ".chars().dropping(2);
2064    /// itertools::assert_equal(iter, "γ".chars());
2065    /// ```
2066    ///
2067    /// *Fusing notes: if the iterator is exhausted by dropping,
2068    /// the result of calling `.next()` again depends on the iterator implementation.*
2069    fn dropping(mut self, n: usize) -> Self
2070        where Self: Sized
2071    {
2072        if n > 0 {
2073            self.nth(n - 1);
2074        }
2075        self
2076    }
2077
2078    /// Consume the last `n` elements from the iterator eagerly,
2079    /// and return the same iterator again.
2080    ///
2081    /// This is only possible on double ended iterators. `n` may be
2082    /// larger than the number of elements.
2083    ///
2084    /// Note: This method is eager, dropping the back elements immediately and
2085    /// preserves the iterator type.
2086    ///
2087    /// ```
2088    /// use itertools::Itertools;
2089    ///
2090    /// let init = vec![0, 3, 6, 9].into_iter().dropping_back(1);
2091    /// itertools::assert_equal(init, vec![0, 3, 6]);
2092    /// ```
2093    fn dropping_back(mut self, n: usize) -> Self
2094        where Self: Sized,
2095              Self: DoubleEndedIterator
2096    {
2097        if n > 0 {
2098            (&mut self).rev().nth(n - 1);
2099        }
2100        self
2101    }
2102
2103    /// Run the closure `f` eagerly on each element of the iterator.
2104    ///
2105    /// Consumes the iterator until its end.
2106    ///
2107    /// ```
2108    /// use std::sync::mpsc::channel;
2109    /// use itertools::Itertools;
2110    ///
2111    /// let (tx, rx) = channel();
2112    ///
2113    /// // use .foreach() to apply a function to each value -- sending it
2114    /// (0..5).map(|x| x * 2 + 1).foreach(|x| { tx.send(x).unwrap(); } );
2115    ///
2116    /// drop(tx);
2117    ///
2118    /// itertools::assert_equal(rx.iter(), vec![1, 3, 5, 7, 9]);
2119    /// ```
2120    #[deprecated(note="Use .for_each() instead", since="0.8.0")]
2121    fn foreach<F>(self, f: F)
2122        where F: FnMut(Self::Item),
2123              Self: Sized,
2124    {
2125        self.for_each(f);
2126    }
2127
2128    /// Combine all an iterator's elements into one element by using [`Extend`].
2129    ///
2130    /// This combinator will extend the first item with each of the rest of the
2131    /// items of the iterator. If the iterator is empty, the default value of
2132    /// `I::Item` is returned.
2133    ///
2134    /// ```rust
2135    /// use itertools::Itertools;
2136    ///
2137    /// let input = vec![vec![1], vec![2, 3], vec![4, 5, 6]];
2138    /// assert_eq!(input.into_iter().concat(),
2139    ///            vec![1, 2, 3, 4, 5, 6]);
2140    /// ```
2141    fn concat(self) -> Self::Item
2142        where Self: Sized,
2143              Self::Item: Extend<<<Self as Iterator>::Item as IntoIterator>::Item> + IntoIterator + Default
2144    {
2145        concat(self)
2146    }
2147
2148    /// `.collect_vec()` is simply a type specialization of [`Iterator::collect`],
2149    /// for convenience.
2150    #[cfg(feature = "use_alloc")]
2151    fn collect_vec(self) -> Vec<Self::Item>
2152        where Self: Sized
2153    {
2154        self.collect()
2155    }
2156
2157    /// `.try_collect()` is more convenient way of writing
2158    /// `.collect::<Result<_, _>>()`
2159    ///
2160    /// # Example
2161    ///
2162    /// ```
2163    /// use std::{fs, io};
2164    /// use itertools::Itertools;
2165    ///
2166    /// fn process_dir_entries(entries: &[fs::DirEntry]) {
2167    ///     // ...
2168    /// }
2169    ///
2170    /// fn do_stuff() -> std::io::Result<()> {
2171    ///     let entries: Vec<_> = fs::read_dir(".")?.try_collect()?;
2172    ///     process_dir_entries(&entries);
2173    ///
2174    ///     Ok(())
2175    /// }
2176    /// ```
2177    #[cfg(feature = "use_alloc")]
2178    fn try_collect<T, U, E>(self) -> Result<U, E>
2179    where
2180        Self: Sized + Iterator<Item = Result<T, E>>,
2181        Result<U, E>: FromIterator<Result<T, E>>,
2182    {
2183        self.collect()
2184    }
2185
2186    /// Assign to each reference in `self` from the `from` iterator,
2187    /// stopping at the shortest of the two iterators.
2188    ///
2189    /// The `from` iterator is queried for its next element before the `self`
2190    /// iterator, and if either is exhausted the method is done.
2191    ///
2192    /// Return the number of elements written.
2193    ///
2194    /// ```
2195    /// use itertools::Itertools;
2196    ///
2197    /// let mut xs = [0; 4];
2198    /// xs.iter_mut().set_from(1..);
2199    /// assert_eq!(xs, [1, 2, 3, 4]);
2200    /// ```
2201    #[inline]
2202    fn set_from<'a, A: 'a, J>(&mut self, from: J) -> usize
2203        where Self: Iterator<Item = &'a mut A>,
2204              J: IntoIterator<Item = A>
2205    {
2206        let mut count = 0;
2207        for elt in from {
2208            match self.next() {
2209                None => break,
2210                Some(ptr) => *ptr = elt,
2211            }
2212            count += 1;
2213        }
2214        count
2215    }
2216
2217    /// Combine all iterator elements into one String, separated by `sep`.
2218    ///
2219    /// Use the `Display` implementation of each element.
2220    ///
2221    /// ```
2222    /// use itertools::Itertools;
2223    ///
2224    /// assert_eq!(["a", "b", "c"].iter().join(", "), "a, b, c");
2225    /// assert_eq!([1, 2, 3].iter().join(", "), "1, 2, 3");
2226    /// ```
2227    #[cfg(feature = "use_alloc")]
2228    fn join(&mut self, sep: &str) -> String
2229        where Self::Item: std::fmt::Display
2230    {
2231        match self.next() {
2232            None => String::new(),
2233            Some(first_elt) => {
2234                // estimate lower bound of capacity needed
2235                let (lower, _) = self.size_hint();
2236                let mut result = String::with_capacity(sep.len() * lower);
2237                write!(&mut result, "{}", first_elt).unwrap();
2238                self.for_each(|elt| {
2239                    result.push_str(sep);
2240                    write!(&mut result, "{}", elt).unwrap();
2241                });
2242                result
2243            }
2244        }
2245    }
2246
2247    /// Format all iterator elements, separated by `sep`.
2248    ///
2249    /// All elements are formatted (any formatting trait)
2250    /// with `sep` inserted between each element.
2251    ///
2252    /// **Panics** if the formatter helper is formatted more than once.
2253    ///
2254    /// ```
2255    /// use itertools::Itertools;
2256    ///
2257    /// let data = [1.1, 2.71828, -3.];
2258    /// assert_eq!(
2259    ///     format!("{:.2}", data.iter().format(", ")),
2260    ///            "1.10, 2.72, -3.00");
2261    /// ```
2262    fn format(self, sep: &str) -> Format<Self>
2263        where Self: Sized,
2264    {
2265        format::new_format_default(self, sep)
2266    }
2267
2268    /// Format all iterator elements, separated by `sep`.
2269    ///
2270    /// This is a customizable version of [`.format()`](Itertools::format).
2271    ///
2272    /// The supplied closure `format` is called once per iterator element,
2273    /// with two arguments: the element and a callback that takes a
2274    /// `&Display` value, i.e. any reference to type that implements `Display`.
2275    ///
2276    /// Using `&format_args!(...)` is the most versatile way to apply custom
2277    /// element formatting. The callback can be called multiple times if needed.
2278    ///
2279    /// **Panics** if the formatter helper is formatted more than once.
2280    ///
2281    /// ```
2282    /// use itertools::Itertools;
2283    ///
2284    /// let data = [1.1, 2.71828, -3.];
2285    /// let data_formatter = data.iter().format_with(", ", |elt, f| f(&format_args!("{:.2}", elt)));
2286    /// assert_eq!(format!("{}", data_formatter),
2287    ///            "1.10, 2.72, -3.00");
2288    ///
2289    /// // .format_with() is recursively composable
2290    /// let matrix = [[1., 2., 3.],
2291    ///               [4., 5., 6.]];
2292    /// let matrix_formatter = matrix.iter().format_with("\n", |row, f| {
2293    ///                                 f(&row.iter().format_with(", ", |elt, g| g(&elt)))
2294    ///                              });
2295    /// assert_eq!(format!("{}", matrix_formatter),
2296    ///            "1, 2, 3\n4, 5, 6");
2297    ///
2298    ///
2299    /// ```
2300    fn format_with<F>(self, sep: &str, format: F) -> FormatWith<Self, F>
2301        where Self: Sized,
2302              F: FnMut(Self::Item, &mut dyn FnMut(&dyn fmt::Display) -> fmt::Result) -> fmt::Result,
2303    {
2304        format::new_format(self, sep, format)
2305    }
2306
2307    /// See [`.fold_ok()`](Itertools::fold_ok).
2308    #[deprecated(note="Use .fold_ok() instead", since="0.10.0")]
2309    fn fold_results<A, E, B, F>(&mut self, start: B, f: F) -> Result<B, E>
2310        where Self: Iterator<Item = Result<A, E>>,
2311              F: FnMut(B, A) -> B
2312    {
2313        self.fold_ok(start, f)
2314    }
2315
2316    /// Fold `Result` values from an iterator.
2317    ///
2318    /// Only `Ok` values are folded. If no error is encountered, the folded
2319    /// value is returned inside `Ok`. Otherwise, the operation terminates
2320    /// and returns the first `Err` value it encounters. No iterator elements are
2321    /// consumed after the first error.
2322    ///
2323    /// The first accumulator value is the `start` parameter.
2324    /// Each iteration passes the accumulator value and the next value inside `Ok`
2325    /// to the fold function `f` and its return value becomes the new accumulator value.
2326    ///
2327    /// For example the sequence *Ok(1), Ok(2), Ok(3)* will result in a
2328    /// computation like this:
2329    ///
2330    /// ```ignore
2331    /// let mut accum = start;
2332    /// accum = f(accum, 1);
2333    /// accum = f(accum, 2);
2334    /// accum = f(accum, 3);
2335    /// ```
2336    ///
2337    /// With a `start` value of 0 and an addition as folding function,
2338    /// this effectively results in *((0 + 1) + 2) + 3*
2339    ///
2340    /// ```
2341    /// use std::ops::Add;
2342    /// use itertools::Itertools;
2343    ///
2344    /// let values = [1, 2, -2, -1, 2, 1];
2345    /// assert_eq!(
2346    ///     values.iter()
2347    ///           .map(Ok::<_, ()>)
2348    ///           .fold_ok(0, Add::add),
2349    ///     Ok(3)
2350    /// );
2351    /// assert!(
2352    ///     values.iter()
2353    ///           .map(|&x| if x >= 0 { Ok(x) } else { Err("Negative number") })
2354    ///           .fold_ok(0, Add::add)
2355    ///           .is_err()
2356    /// );
2357    /// ```
2358    fn fold_ok<A, E, B, F>(&mut self, mut start: B, mut f: F) -> Result<B, E>
2359        where Self: Iterator<Item = Result<A, E>>,
2360              F: FnMut(B, A) -> B
2361    {
2362        for elt in self {
2363            match elt {
2364                Ok(v) => start = f(start, v),
2365                Err(u) => return Err(u),
2366            }
2367        }
2368        Ok(start)
2369    }
2370
2371    /// Fold `Option` values from an iterator.
2372    ///
2373    /// Only `Some` values are folded. If no `None` is encountered, the folded
2374    /// value is returned inside `Some`. Otherwise, the operation terminates
2375    /// and returns `None`. No iterator elements are consumed after the `None`.
2376    ///
2377    /// This is the `Option` equivalent to [`fold_ok`](Itertools::fold_ok).
2378    ///
2379    /// ```
2380    /// use std::ops::Add;
2381    /// use itertools::Itertools;
2382    ///
2383    /// let mut values = vec![Some(1), Some(2), Some(-2)].into_iter();
2384    /// assert_eq!(values.fold_options(5, Add::add), Some(5 + 1 + 2 - 2));
2385    ///
2386    /// let mut more_values = vec![Some(2), None, Some(0)].into_iter();
2387    /// assert!(more_values.fold_options(0, Add::add).is_none());
2388    /// assert_eq!(more_values.next().unwrap(), Some(0));
2389    /// ```
2390    fn fold_options<A, B, F>(&mut self, mut start: B, mut f: F) -> Option<B>
2391        where Self: Iterator<Item = Option<A>>,
2392              F: FnMut(B, A) -> B
2393    {
2394        for elt in self {
2395            match elt {
2396                Some(v) => start = f(start, v),
2397                None => return None,
2398            }
2399        }
2400        Some(start)
2401    }
2402
2403    /// Accumulator of the elements in the iterator.
2404    ///
2405    /// Like `.fold()`, without a base case. If the iterator is
2406    /// empty, return `None`. With just one element, return it.
2407    /// Otherwise elements are accumulated in sequence using the closure `f`.
2408    ///
2409    /// ```
2410    /// use itertools::Itertools;
2411    ///
2412    /// assert_eq!((0..10).fold1(|x, y| x + y).unwrap_or(0), 45);
2413    /// assert_eq!((0..0).fold1(|x, y| x * y), None);
2414    /// ```
2415    #[deprecated(since = "0.10.2", note = "Use `Iterator::reduce` instead")]
2416    fn fold1<F>(mut self, f: F) -> Option<Self::Item>
2417        where F: FnMut(Self::Item, Self::Item) -> Self::Item,
2418              Self: Sized,
2419    {
2420        self.next().map(move |x| self.fold(x, f))
2421    }
2422
2423    /// Accumulate the elements in the iterator in a tree-like manner.
2424    ///
2425    /// You can think of it as, while there's more than one item, repeatedly
2426    /// combining adjacent items.  It does so in bottom-up-merge-sort order,
2427    /// however, so that it needs only logarithmic stack space.
2428    ///
2429    /// This produces a call tree like the following (where the calls under
2430    /// an item are done after reading that item):
2431    ///
2432    /// ```text
2433    /// 1 2 3 4 5 6 7
2434    /// │ │ │ │ │ │ │
2435    /// └─f └─f └─f │
2436    ///   │   │   │ │
2437    ///   └───f   └─f
2438    ///       │     │
2439    ///       └─────f
2440    /// ```
2441    ///
2442    /// Which, for non-associative functions, will typically produce a different
2443    /// result than the linear call tree used by [`Iterator::reduce`]:
2444    ///
2445    /// ```text
2446    /// 1 2 3 4 5 6 7
2447    /// │ │ │ │ │ │ │
2448    /// └─f─f─f─f─f─f
2449    /// ```
2450    ///
2451    /// If `f` is associative, prefer the normal [`Iterator::reduce`] instead.
2452    ///
2453    /// ```
2454    /// use itertools::Itertools;
2455    ///
2456    /// // The same tree as above
2457    /// let num_strings = (1..8).map(|x| x.to_string());
2458    /// assert_eq!(num_strings.tree_fold1(|x, y| format!("f({}, {})", x, y)),
2459    ///     Some(String::from("f(f(f(1, 2), f(3, 4)), f(f(5, 6), 7))")));
2460    ///
2461    /// // Like fold1, an empty iterator produces None
2462    /// assert_eq!((0..0).tree_fold1(|x, y| x * y), None);
2463    ///
2464    /// // tree_fold1 matches fold1 for associative operations...
2465    /// assert_eq!((0..10).tree_fold1(|x, y| x + y),
2466    ///     (0..10).fold1(|x, y| x + y));
2467    /// // ...but not for non-associative ones
2468    /// assert_ne!((0..10).tree_fold1(|x, y| x - y),
2469    ///     (0..10).fold1(|x, y| x - y));
2470    /// ```
2471    fn tree_fold1<F>(mut self, mut f: F) -> Option<Self::Item>
2472        where F: FnMut(Self::Item, Self::Item) -> Self::Item,
2473              Self: Sized,
2474    {
2475        type State<T> = Result<T, Option<T>>;
2476
2477        fn inner0<T, II, FF>(it: &mut II, f: &mut FF) -> State<T>
2478            where
2479                II: Iterator<Item = T>,
2480                FF: FnMut(T, T) -> T
2481        {
2482            // This function could be replaced with `it.next().ok_or(None)`,
2483            // but half the useful tree_fold1 work is combining adjacent items,
2484            // so put that in a form that LLVM is more likely to optimize well.
2485
2486            let a =
2487                if let Some(v) = it.next() { v }
2488                else { return Err(None) };
2489            let b =
2490                if let Some(v) = it.next() { v }
2491                else { return Err(Some(a)) };
2492            Ok(f(a, b))
2493        }
2494
2495        fn inner<T, II, FF>(stop: usize, it: &mut II, f: &mut FF) -> State<T>
2496            where
2497                II: Iterator<Item = T>,
2498                FF: FnMut(T, T) -> T
2499        {
2500            let mut x = inner0(it, f)?;
2501            for height in 0..stop {
2502                // Try to get another tree the same size with which to combine it,
2503                // creating a new tree that's twice as big for next time around.
2504                let next =
2505                    if height == 0 {
2506                        inner0(it, f)
2507                    } else {
2508                        inner(height, it, f)
2509                    };
2510                match next {
2511                    Ok(y) => x = f(x, y),
2512
2513                    // If we ran out of items, combine whatever we did manage
2514                    // to get.  It's better combined with the current value
2515                    // than something in a parent frame, because the tree in
2516                    // the parent is always as least as big as this one.
2517                    Err(None) => return Err(Some(x)),
2518                    Err(Some(y)) => return Err(Some(f(x, y))),
2519                }
2520            }
2521            Ok(x)
2522        }
2523
2524        match inner(usize::max_value(), &mut self, &mut f) {
2525            Err(x) => x,
2526            _ => unreachable!(),
2527        }
2528    }
2529
2530    /// An iterator method that applies a function, producing a single, final value.
2531    ///
2532    /// `fold_while()` is basically equivalent to [`Iterator::fold`] but with additional support for
2533    /// early exit via short-circuiting.
2534    ///
2535    /// ```
2536    /// use itertools::Itertools;
2537    /// use itertools::FoldWhile::{Continue, Done};
2538    ///
2539    /// let numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
2540    ///
2541    /// let mut result = 0;
2542    ///
2543    /// // for loop:
2544    /// for i in &numbers {
2545    ///     if *i > 5 {
2546    ///         break;
2547    ///     }
2548    ///     result = result + i;
2549    /// }
2550    ///
2551    /// // fold:
2552    /// let result2 = numbers.iter().fold(0, |acc, x| {
2553    ///     if *x > 5 { acc } else { acc + x }
2554    /// });
2555    ///
2556    /// // fold_while:
2557    /// let result3 = numbers.iter().fold_while(0, |acc, x| {
2558    ///     if *x > 5 { Done(acc) } else { Continue(acc + x) }
2559    /// }).into_inner();
2560    ///
2561    /// // they're the same
2562    /// assert_eq!(result, result2);
2563    /// assert_eq!(result2, result3);
2564    /// ```
2565    ///
2566    /// The big difference between the computations of `result2` and `result3` is that while
2567    /// `fold()` called the provided closure for every item of the callee iterator,
2568    /// `fold_while()` actually stopped iterating as soon as it encountered `Fold::Done(_)`.
2569    fn fold_while<B, F>(&mut self, init: B, mut f: F) -> FoldWhile<B>
2570        where Self: Sized,
2571              F: FnMut(B, Self::Item) -> FoldWhile<B>
2572    {
2573        use Result::{
2574            Ok as Continue,
2575            Err as Break,
2576        };
2577
2578        let result = self.try_fold(init, #[inline(always)] |acc, v|
2579            match f(acc, v) {
2580              FoldWhile::Continue(acc) => Continue(acc),
2581              FoldWhile::Done(acc) => Break(acc),
2582            }
2583        );
2584
2585        match result {
2586            Continue(acc) => FoldWhile::Continue(acc),
2587            Break(acc) => FoldWhile::Done(acc),
2588        }
2589    }
2590
2591    /// Iterate over the entire iterator and add all the elements.
2592    ///
2593    /// An empty iterator returns `None`, otherwise `Some(sum)`.
2594    ///
2595    /// # Panics
2596    ///
2597    /// When calling `sum1()` and a primitive integer type is being returned, this
2598    /// method will panic if the computation overflows and debug assertions are
2599    /// enabled.
2600    ///
2601    /// # Examples
2602    ///
2603    /// ```
2604    /// use itertools::Itertools;
2605    ///
2606    /// let empty_sum = (1..1).sum1::<i32>();
2607    /// assert_eq!(empty_sum, None);
2608    ///
2609    /// let nonempty_sum = (1..11).sum1::<i32>();
2610    /// assert_eq!(nonempty_sum, Some(55));
2611    /// ```
2612    fn sum1<S>(mut self) -> Option<S>
2613        where Self: Sized,
2614              S: std::iter::Sum<Self::Item>,
2615    {
2616        self.next()
2617            .map(|first| once(first).chain(self).sum())
2618    }
2619
2620    /// Iterate over the entire iterator and multiply all the elements.
2621    ///
2622    /// An empty iterator returns `None`, otherwise `Some(product)`.
2623    ///
2624    /// # Panics
2625    ///
2626    /// When calling `product1()` and a primitive integer type is being returned,
2627    /// method will panic if the computation overflows and debug assertions are
2628    /// enabled.
2629    ///
2630    /// # Examples
2631    /// ```
2632    /// use itertools::Itertools;
2633    ///
2634    /// let empty_product = (1..1).product1::<i32>();
2635    /// assert_eq!(empty_product, None);
2636    ///
2637    /// let nonempty_product = (1..11).product1::<i32>();
2638    /// assert_eq!(nonempty_product, Some(3628800));
2639    /// ```
2640    fn product1<P>(mut self) -> Option<P>
2641        where Self: Sized,
2642              P: std::iter::Product<Self::Item>,
2643    {
2644        self.next()
2645            .map(|first| once(first).chain(self).product())
2646    }
2647
2648    /// Sort all iterator elements into a new iterator in ascending order.
2649    ///
2650    /// **Note:** This consumes the entire iterator, uses the
2651    /// [`slice::sort_unstable`] method and returns the result as a new
2652    /// iterator that owns its elements.
2653    /// 
2654    /// This sort is unstable (i.e., may reorder equal elements).
2655    ///
2656    /// The sorted iterator, if directly collected to a `Vec`, is converted
2657    /// without any extra copying or allocation cost.
2658    ///
2659    /// ```
2660    /// use itertools::Itertools;
2661    ///
2662    /// // sort the letters of the text in ascending order
2663    /// let text = "bdacfe";
2664    /// itertools::assert_equal(text.chars().sorted_unstable(),
2665    ///                         "abcdef".chars());
2666    /// ```
2667    #[cfg(feature = "use_alloc")]
2668    fn sorted_unstable(self) -> VecIntoIter<Self::Item>
2669        where Self: Sized,
2670              Self::Item: Ord
2671    {
2672        // Use .sort_unstable() directly since it is not quite identical with
2673        // .sort_by(Ord::cmp)
2674        let mut v = Vec::from_iter(self);
2675        v.sort_unstable();
2676        v.into_iter()
2677    }
2678
2679    /// Sort all iterator elements into a new iterator in ascending order.
2680    ///
2681    /// **Note:** This consumes the entire iterator, uses the
2682    /// [`slice::sort_unstable_by`] method and returns the result as a new
2683    /// iterator that owns its elements.
2684    /// 
2685    /// This sort is unstable (i.e., may reorder equal elements).
2686    ///
2687    /// The sorted iterator, if directly collected to a `Vec`, is converted
2688    /// without any extra copying or allocation cost.
2689    ///
2690    /// ```
2691    /// use itertools::Itertools;
2692    ///
2693    /// // sort people in descending order by age
2694    /// let people = vec![("Jane", 20), ("John", 18), ("Jill", 30), ("Jack", 27)];
2695    ///
2696    /// let oldest_people_first = people
2697    ///     .into_iter()
2698    ///     .sorted_unstable_by(|a, b| Ord::cmp(&b.1, &a.1))
2699    ///     .map(|(person, _age)| person);
2700    ///
2701    /// itertools::assert_equal(oldest_people_first,
2702    ///                         vec!["Jill", "Jack", "Jane", "John"]);
2703    /// ```
2704    #[cfg(feature = "use_alloc")]
2705    fn sorted_unstable_by<F>(self, cmp: F) -> VecIntoIter<Self::Item>
2706        where Self: Sized,
2707              F: FnMut(&Self::Item, &Self::Item) -> Ordering,
2708    {
2709        let mut v = Vec::from_iter(self);
2710        v.sort_unstable_by(cmp);
2711        v.into_iter()
2712    }
2713
2714    /// Sort all iterator elements into a new iterator in ascending order.
2715    ///
2716    /// **Note:** This consumes the entire iterator, uses the
2717    /// [`slice::sort_unstable_by_key`] method and returns the result as a new
2718    /// iterator that owns its elements.
2719    /// 
2720    /// This sort is unstable (i.e., may reorder equal elements).
2721    ///
2722    /// The sorted iterator, if directly collected to a `Vec`, is converted
2723    /// without any extra copying or allocation cost.
2724    ///
2725    /// ```
2726    /// use itertools::Itertools;
2727    ///
2728    /// // sort people in descending order by age
2729    /// let people = vec![("Jane", 20), ("John", 18), ("Jill", 30), ("Jack", 27)];
2730    ///
2731    /// let oldest_people_first = people
2732    ///     .into_iter()
2733    ///     .sorted_unstable_by_key(|x| -x.1)
2734    ///     .map(|(person, _age)| person);
2735    ///
2736    /// itertools::assert_equal(oldest_people_first,
2737    ///                         vec!["Jill", "Jack", "Jane", "John"]);
2738    /// ```
2739    #[cfg(feature = "use_alloc")]
2740    fn sorted_unstable_by_key<K, F>(self, f: F) -> VecIntoIter<Self::Item>
2741        where Self: Sized,
2742              K: Ord,
2743              F: FnMut(&Self::Item) -> K,
2744    {
2745        let mut v = Vec::from_iter(self);
2746        v.sort_unstable_by_key(f);
2747        v.into_iter()
2748    }
2749
2750    /// Sort all iterator elements into a new iterator in ascending order.
2751    ///
2752    /// **Note:** This consumes the entire iterator, uses the
2753    /// [`slice::sort`] method and returns the result as a new
2754    /// iterator that owns its elements.
2755    /// 
2756    /// This sort is stable (i.e., does not reorder equal elements).
2757    ///
2758    /// The sorted iterator, if directly collected to a `Vec`, is converted
2759    /// without any extra copying or allocation cost.
2760    ///
2761    /// ```
2762    /// use itertools::Itertools;
2763    ///
2764    /// // sort the letters of the text in ascending order
2765    /// let text = "bdacfe";
2766    /// itertools::assert_equal(text.chars().sorted(),
2767    ///                         "abcdef".chars());
2768    /// ```
2769    #[cfg(feature = "use_alloc")]
2770    fn sorted(self) -> VecIntoIter<Self::Item>
2771        where Self: Sized,
2772              Self::Item: Ord
2773    {
2774        // Use .sort() directly since it is not quite identical with
2775        // .sort_by(Ord::cmp)
2776        let mut v = Vec::from_iter(self);
2777        v.sort();
2778        v.into_iter()
2779    }
2780
2781    /// Sort all iterator elements into a new iterator in ascending order.
2782    ///
2783    /// **Note:** This consumes the entire iterator, uses the
2784    /// [`slice::sort_by`] method and returns the result as a new
2785    /// iterator that owns its elements.
2786    /// 
2787    /// This sort is stable (i.e., does not reorder equal elements).
2788    ///
2789    /// The sorted iterator, if directly collected to a `Vec`, is converted
2790    /// without any extra copying or allocation cost.
2791    ///
2792    /// ```
2793    /// use itertools::Itertools;
2794    ///
2795    /// // sort people in descending order by age
2796    /// let people = vec![("Jane", 20), ("John", 18), ("Jill", 30), ("Jack", 30)];
2797    ///
2798    /// let oldest_people_first = people
2799    ///     .into_iter()
2800    ///     .sorted_by(|a, b| Ord::cmp(&b.1, &a.1))
2801    ///     .map(|(person, _age)| person);
2802    ///
2803    /// itertools::assert_equal(oldest_people_first,
2804    ///                         vec!["Jill", "Jack", "Jane", "John"]);
2805    /// ```
2806    #[cfg(feature = "use_alloc")]
2807    fn sorted_by<F>(self, cmp: F) -> VecIntoIter<Self::Item>
2808        where Self: Sized,
2809              F: FnMut(&Self::Item, &Self::Item) -> Ordering,
2810    {
2811        let mut v = Vec::from_iter(self);
2812        v.sort_by(cmp);
2813        v.into_iter()
2814    }
2815
2816    /// Sort all iterator elements into a new iterator in ascending order.
2817    ///
2818    /// **Note:** This consumes the entire iterator, uses the
2819    /// [`slice::sort_by_key`] method and returns the result as a new
2820    /// iterator that owns its elements.
2821    /// 
2822    /// This sort is stable (i.e., does not reorder equal elements).
2823    ///
2824    /// The sorted iterator, if directly collected to a `Vec`, is converted
2825    /// without any extra copying or allocation cost.
2826    ///
2827    /// ```
2828    /// use itertools::Itertools;
2829    ///
2830    /// // sort people in descending order by age
2831    /// let people = vec![("Jane", 20), ("John", 18), ("Jill", 30), ("Jack", 30)];
2832    ///
2833    /// let oldest_people_first = people
2834    ///     .into_iter()
2835    ///     .sorted_by_key(|x| -x.1)
2836    ///     .map(|(person, _age)| person);
2837    ///
2838    /// itertools::assert_equal(oldest_people_first,
2839    ///                         vec!["Jill", "Jack", "Jane", "John"]);
2840    /// ```
2841    #[cfg(feature = "use_alloc")]
2842    fn sorted_by_key<K, F>(self, f: F) -> VecIntoIter<Self::Item>
2843        where Self: Sized,
2844              K: Ord,
2845              F: FnMut(&Self::Item) -> K,
2846    {
2847        let mut v = Vec::from_iter(self);
2848        v.sort_by_key(f);
2849        v.into_iter()
2850    }
2851
2852    /// Sort all iterator elements into a new iterator in ascending order. The key function is
2853    /// called exactly once per key.
2854    ///
2855    /// **Note:** This consumes the entire iterator, uses the
2856    /// [`slice::sort_by_cached_key`] method and returns the result as a new
2857    /// iterator that owns its elements.
2858    /// 
2859    /// This sort is stable (i.e., does not reorder equal elements).
2860    ///
2861    /// The sorted iterator, if directly collected to a `Vec`, is converted
2862    /// without any extra copying or allocation cost.
2863    ///
2864    /// ```
2865    /// use itertools::Itertools;
2866    ///
2867    /// // sort people in descending order by age
2868    /// let people = vec![("Jane", 20), ("John", 18), ("Jill", 30), ("Jack", 30)];
2869    ///
2870    /// let oldest_people_first = people
2871    ///     .into_iter()
2872    ///     .sorted_by_cached_key(|x| -x.1)
2873    ///     .map(|(person, _age)| person);
2874    ///
2875    /// itertools::assert_equal(oldest_people_first,
2876    ///                         vec!["Jill", "Jack", "Jane", "John"]);
2877    /// ```
2878    #[cfg(feature = "use_alloc")]
2879    fn sorted_by_cached_key<K, F>(self, f: F) -> VecIntoIter<Self::Item>
2880    where
2881        Self: Sized,
2882        K: Ord,
2883        F: FnMut(&Self::Item) -> K,
2884    {
2885        let mut v = Vec::from_iter(self);
2886        v.sort_by_cached_key(f);
2887        v.into_iter()
2888    }
2889
2890    /// Sort the k smallest elements into a new iterator, in ascending order.
2891    ///
2892    /// **Note:** This consumes the entire iterator, and returns the result
2893    /// as a new iterator that owns its elements.  If the input contains
2894    /// less than k elements, the result is equivalent to `self.sorted()`.
2895    ///
2896    /// This is guaranteed to use `k * sizeof(Self::Item) + O(1)` memory
2897    /// and `O(n log k)` time, with `n` the number of elements in the input.
2898    ///
2899    /// The sorted iterator, if directly collected to a `Vec`, is converted
2900    /// without any extra copying or allocation cost.
2901    ///
2902    /// **Note:** This is functionally-equivalent to `self.sorted().take(k)`
2903    /// but much more efficient.
2904    ///
2905    /// ```
2906    /// use itertools::Itertools;
2907    ///
2908    /// // A random permutation of 0..15
2909    /// let numbers = vec![6, 9, 1, 14, 0, 4, 8, 7, 11, 2, 10, 3, 13, 12, 5];
2910    ///
2911    /// let five_smallest = numbers
2912    ///     .into_iter()
2913    ///     .k_smallest(5);
2914    ///
2915    /// itertools::assert_equal(five_smallest, 0..5);
2916    /// ```
2917    #[cfg(feature = "use_alloc")]
2918    fn k_smallest(self, k: usize) -> VecIntoIter<Self::Item>
2919        where Self: Sized,
2920              Self::Item: Ord
2921    {
2922        crate::k_smallest::k_smallest(self, k)
2923            .into_sorted_vec()
2924            .into_iter()
2925    }
2926
2927    /// Collect all iterator elements into one of two
2928    /// partitions. Unlike [`Iterator::partition`], each partition may
2929    /// have a distinct type.
2930    ///
2931    /// ```
2932    /// use itertools::{Itertools, Either};
2933    ///
2934    /// let successes_and_failures = vec![Ok(1), Err(false), Err(true), Ok(2)];
2935    ///
2936    /// let (successes, failures): (Vec<_>, Vec<_>) = successes_and_failures
2937    ///     .into_iter()
2938    ///     .partition_map(|r| {
2939    ///         match r {
2940    ///             Ok(v) => Either::Left(v),
2941    ///             Err(v) => Either::Right(v),
2942    ///         }
2943    ///     });
2944    ///
2945    /// assert_eq!(successes, [1, 2]);
2946    /// assert_eq!(failures, [false, true]);
2947    /// ```
2948    fn partition_map<A, B, F, L, R>(self, mut predicate: F) -> (A, B)
2949        where Self: Sized,
2950              F: FnMut(Self::Item) -> Either<L, R>,
2951              A: Default + Extend<L>,
2952              B: Default + Extend<R>,
2953    {
2954        let mut left = A::default();
2955        let mut right = B::default();
2956
2957        self.for_each(|val| match predicate(val) {
2958            Either::Left(v) => left.extend(Some(v)),
2959            Either::Right(v) => right.extend(Some(v)),
2960        });
2961
2962        (left, right)
2963    }
2964
2965    /// Partition a sequence of `Result`s into one list of all the `Ok` elements
2966    /// and another list of all the `Err` elements.
2967    ///
2968    /// ```
2969    /// use itertools::Itertools;
2970    ///
2971    /// let successes_and_failures = vec![Ok(1), Err(false), Err(true), Ok(2)];
2972    ///
2973    /// let (successes, failures): (Vec<_>, Vec<_>) = successes_and_failures
2974    ///     .into_iter()
2975    ///     .partition_result();
2976    ///
2977    /// assert_eq!(successes, [1, 2]);
2978    /// assert_eq!(failures, [false, true]);
2979    /// ```
2980    fn partition_result<A, B, T, E>(self) -> (A, B)
2981        where
2982            Self: Iterator<Item = Result<T, E>> + Sized,
2983            A: Default + Extend<T>,
2984            B: Default + Extend<E>,
2985    {
2986        self.partition_map(|r| match r {
2987            Ok(v) => Either::Left(v),
2988            Err(v) => Either::Right(v),
2989        })
2990    }
2991
2992    /// Return a `HashMap` of keys mapped to `Vec`s of values. Keys and values
2993    /// are taken from `(Key, Value)` tuple pairs yielded by the input iterator.
2994    ///
2995    /// Essentially a shorthand for `.into_grouping_map().collect::<Vec<_>>()`.
2996    ///
2997    /// ```
2998    /// use itertools::Itertools;
2999    ///
3000    /// let data = vec![(0, 10), (2, 12), (3, 13), (0, 20), (3, 33), (2, 42)];
3001    /// let lookup = data.into_iter().into_group_map();
3002    ///
3003    /// assert_eq!(lookup[&0], vec![10, 20]);
3004    /// assert_eq!(lookup.get(&1), None);
3005    /// assert_eq!(lookup[&2], vec![12, 42]);
3006    /// assert_eq!(lookup[&3], vec![13, 33]);
3007    /// ```
3008    #[cfg(feature = "use_std")]
3009    fn into_group_map<K, V>(self) -> HashMap<K, Vec<V>>
3010        where Self: Iterator<Item=(K, V)> + Sized,
3011              K: Hash + Eq,
3012    {
3013        group_map::into_group_map(self)
3014    }
3015
3016    /// Return an `Iterator` on a `HashMap`. Keys mapped to `Vec`s of values. The key is specified
3017    /// in the closure.
3018    ///
3019    /// Essentially a shorthand for `.into_grouping_map_by(f).collect::<Vec<_>>()`.
3020    ///
3021    /// ```
3022    /// use itertools::Itertools;
3023    /// use std::collections::HashMap;
3024    ///
3025    /// let data = vec![(0, 10), (2, 12), (3, 13), (0, 20), (3, 33), (2, 42)];
3026    /// let lookup: HashMap<u32,Vec<(u32, u32)>> =
3027    ///     data.clone().into_iter().into_group_map_by(|a| a.0);
3028    ///
3029    /// assert_eq!(lookup[&0], vec![(0,10),(0,20)]);
3030    /// assert_eq!(lookup.get(&1), None);
3031    /// assert_eq!(lookup[&2], vec![(2,12), (2,42)]);
3032    /// assert_eq!(lookup[&3], vec![(3,13), (3,33)]);
3033    ///
3034    /// assert_eq!(
3035    ///     data.into_iter()
3036    ///         .into_group_map_by(|x| x.0)
3037    ///         .into_iter()
3038    ///         .map(|(key, values)| (key, values.into_iter().fold(0,|acc, (_,v)| acc + v )))
3039    ///         .collect::<HashMap<u32,u32>>()[&0],
3040    ///     30,
3041    /// );
3042    /// ```
3043    #[cfg(feature = "use_std")]
3044    fn into_group_map_by<K, V, F>(self, f: F) -> HashMap<K, Vec<V>>
3045        where
3046            Self: Iterator<Item=V> + Sized,
3047            K: Hash + Eq,
3048            F: Fn(&V) -> K,
3049    {
3050        group_map::into_group_map_by(self, f)
3051    }
3052
3053    /// Constructs a `GroupingMap` to be used later with one of the efficient
3054    /// group-and-fold operations it allows to perform.
3055    ///
3056    /// The input iterator must yield item in the form of `(K, V)` where the
3057    /// value of type `K` will be used as key to identify the groups and the
3058    /// value of type `V` as value for the folding operation.
3059    ///
3060    /// See [`GroupingMap`] for more informations
3061    /// on what operations are available.
3062    #[cfg(feature = "use_std")]
3063    fn into_grouping_map<K, V>(self) -> GroupingMap<Self>
3064        where Self: Iterator<Item=(K, V)> + Sized,
3065              K: Hash + Eq,
3066    {
3067        grouping_map::new(self)
3068    }
3069
3070    /// Constructs a `GroupingMap` to be used later with one of the efficient
3071    /// group-and-fold operations it allows to perform.
3072    ///
3073    /// The values from this iterator will be used as values for the folding operation
3074    /// while the keys will be obtained from the values by calling `key_mapper`.
3075    ///
3076    /// See [`GroupingMap`] for more informations
3077    /// on what operations are available.
3078    #[cfg(feature = "use_std")]
3079    fn into_grouping_map_by<K, V, F>(self, key_mapper: F) -> GroupingMapBy<Self, F>
3080        where Self: Iterator<Item=V> + Sized,
3081              K: Hash + Eq,
3082              F: FnMut(&V) -> K
3083    {
3084        grouping_map::new(grouping_map::MapForGrouping::new(self, key_mapper))
3085    }
3086
3087    /// Return all minimum elements of an iterator.
3088    ///
3089    /// # Examples
3090    ///
3091    /// ```
3092    /// use itertools::Itertools;
3093    ///
3094    /// let a: [i32; 0] = [];
3095    /// assert_eq!(a.iter().min_set(), Vec::<&i32>::new());
3096    ///
3097    /// let a = [1];
3098    /// assert_eq!(a.iter().min_set(), vec![&1]);
3099    ///
3100    /// let a = [1, 2, 3, 4, 5];
3101    /// assert_eq!(a.iter().min_set(), vec![&1]);
3102    ///
3103    /// let a = [1, 1, 1, 1];
3104    /// assert_eq!(a.iter().min_set(), vec![&1, &1, &1, &1]);
3105    /// ```
3106    ///
3107    /// The elements can be floats but no particular result is guaranteed
3108    /// if an element is NaN.
3109    #[cfg(feature = "use_std")]
3110    fn min_set(self) -> Vec<Self::Item>
3111        where Self: Sized, Self::Item: Ord
3112    {
3113        extrema_set::min_set_impl(self, |_| (), |x, y, _, _| x.cmp(y))
3114    }
3115
3116    /// Return all minimum elements of an iterator, as determined by
3117    /// the specified function.
3118    ///
3119    /// # Examples
3120    ///
3121    /// ```
3122    /// # use std::cmp::Ordering;
3123    /// use itertools::Itertools;
3124    ///
3125    /// let a: [(i32, i32); 0] = [];
3126    /// assert_eq!(a.iter().min_set_by(|_, _| Ordering::Equal), Vec::<&(i32, i32)>::new());
3127    ///
3128    /// let a = [(1, 2)];
3129    /// assert_eq!(a.iter().min_set_by(|&&(k1,_), &&(k2, _)| k1.cmp(&k2)), vec![&(1, 2)]);
3130    ///
3131    /// let a = [(1, 2), (2, 2), (3, 9), (4, 8), (5, 9)];
3132    /// assert_eq!(a.iter().min_set_by(|&&(_,k1), &&(_,k2)| k1.cmp(&k2)), vec![&(1, 2), &(2, 2)]);
3133    ///
3134    /// let a = [(1, 2), (1, 3), (1, 4), (1, 5)];
3135    /// assert_eq!(a.iter().min_set_by(|&&(k1,_), &&(k2, _)| k1.cmp(&k2)), vec![&(1, 2), &(1, 3), &(1, 4), &(1, 5)]);
3136    /// ```
3137    ///
3138    /// The elements can be floats but no particular result is guaranteed
3139    /// if an element is NaN.
3140    #[cfg(feature = "use_std")]
3141    fn min_set_by<F>(self, mut compare: F) -> Vec<Self::Item>
3142        where Self: Sized, F: FnMut(&Self::Item, &Self::Item) -> Ordering
3143    {
3144        extrema_set::min_set_impl(
3145            self,
3146            |_| (),
3147            |x, y, _, _| compare(x, y)
3148        )
3149    }
3150
3151    /// Return all minimum elements of an iterator, as determined by
3152    /// the specified function.
3153    ///
3154    /// # Examples
3155    ///
3156    /// ```
3157    /// use itertools::Itertools;
3158    ///
3159    /// let a: [(i32, i32); 0] = [];
3160    /// assert_eq!(a.iter().min_set_by_key(|_| ()), Vec::<&(i32, i32)>::new());
3161    ///
3162    /// let a = [(1, 2)];
3163    /// assert_eq!(a.iter().min_set_by_key(|&&(k,_)| k), vec![&(1, 2)]);
3164    ///
3165    /// let a = [(1, 2), (2, 2), (3, 9), (4, 8), (5, 9)];
3166    /// assert_eq!(a.iter().min_set_by_key(|&&(_, k)| k), vec![&(1, 2), &(2, 2)]);
3167    ///
3168    /// let a = [(1, 2), (1, 3), (1, 4), (1, 5)];
3169    /// assert_eq!(a.iter().min_set_by_key(|&&(k, _)| k), vec![&(1, 2), &(1, 3), &(1, 4), &(1, 5)]);
3170    /// ```
3171    ///
3172    /// The elements can be floats but no particular result is guaranteed
3173    /// if an element is NaN.
3174    #[cfg(feature = "use_std")]
3175    fn min_set_by_key<K, F>(self, key: F) -> Vec<Self::Item>
3176        where Self: Sized, K: Ord, F: FnMut(&Self::Item) -> K
3177    {
3178        extrema_set::min_set_impl(self, key, |_, _, kx, ky| kx.cmp(ky))
3179    }
3180
3181    /// Return all maximum elements of an iterator.
3182    ///
3183    /// # Examples
3184    ///
3185    /// ```
3186    /// use itertools::Itertools;
3187    ///
3188    /// let a: [i32; 0] = [];
3189    /// assert_eq!(a.iter().max_set(), Vec::<&i32>::new());
3190    ///
3191    /// let a = [1];
3192    /// assert_eq!(a.iter().max_set(), vec![&1]);
3193    ///
3194    /// let a = [1, 2, 3, 4, 5];
3195    /// assert_eq!(a.iter().max_set(), vec![&5]);
3196    ///
3197    /// let a = [1, 1, 1, 1];
3198    /// assert_eq!(a.iter().max_set(), vec![&1, &1, &1, &1]);
3199    /// ```
3200    ///
3201    /// The elements can be floats but no particular result is guaranteed
3202    /// if an element is NaN.
3203    #[cfg(feature = "use_std")]
3204    fn max_set(self) -> Vec<Self::Item>
3205        where Self: Sized, Self::Item: Ord
3206    {
3207        extrema_set::max_set_impl(self, |_| (), |x, y, _, _| x.cmp(y))
3208    }
3209
3210    /// Return all maximum elements of an iterator, as determined by
3211    /// the specified function.
3212    ///
3213    /// # Examples
3214    ///
3215    /// ```
3216    /// # use std::cmp::Ordering;
3217    /// use itertools::Itertools;
3218    ///
3219    /// let a: [(i32, i32); 0] = [];
3220    /// assert_eq!(a.iter().max_set_by(|_, _| Ordering::Equal), Vec::<&(i32, i32)>::new());
3221    ///
3222    /// let a = [(1, 2)];
3223    /// assert_eq!(a.iter().max_set_by(|&&(k1,_), &&(k2, _)| k1.cmp(&k2)), vec![&(1, 2)]);
3224    ///
3225    /// let a = [(1, 2), (2, 2), (3, 9), (4, 8), (5, 9)];
3226    /// assert_eq!(a.iter().max_set_by(|&&(_,k1), &&(_,k2)| k1.cmp(&k2)), vec![&(3, 9), &(5, 9)]);
3227    ///
3228    /// let a = [(1, 2), (1, 3), (1, 4), (1, 5)];
3229    /// assert_eq!(a.iter().max_set_by(|&&(k1,_), &&(k2, _)| k1.cmp(&k2)), vec![&(1, 2), &(1, 3), &(1, 4), &(1, 5)]);
3230    /// ```
3231    ///
3232    /// The elements can be floats but no particular result is guaranteed
3233    /// if an element is NaN.
3234    #[cfg(feature = "use_std")]
3235    fn max_set_by<F>(self, mut compare: F) -> Vec<Self::Item>
3236        where Self: Sized, F: FnMut(&Self::Item, &Self::Item) -> Ordering
3237    {
3238        extrema_set::max_set_impl(
3239            self,
3240            |_| (),
3241            |x, y, _, _| compare(x, y)
3242        )
3243    }
3244
3245    /// Return all maximum elements of an iterator, as determined by
3246    /// the specified function.
3247    ///
3248    /// # Examples
3249    ///
3250    /// ```
3251    /// use itertools::Itertools;
3252    ///
3253    /// let a: [(i32, i32); 0] = [];
3254    /// assert_eq!(a.iter().max_set_by_key(|_| ()), Vec::<&(i32, i32)>::new());
3255    ///
3256    /// let a = [(1, 2)];
3257    /// assert_eq!(a.iter().max_set_by_key(|&&(k,_)| k), vec![&(1, 2)]);
3258    ///
3259    /// let a = [(1, 2), (2, 2), (3, 9), (4, 8), (5, 9)];
3260    /// assert_eq!(a.iter().max_set_by_key(|&&(_, k)| k), vec![&(3, 9), &(5, 9)]);
3261    ///
3262    /// let a = [(1, 2), (1, 3), (1, 4), (1, 5)];
3263    /// assert_eq!(a.iter().max_set_by_key(|&&(k, _)| k), vec![&(1, 2), &(1, 3), &(1, 4), &(1, 5)]);
3264    /// ```
3265    ///
3266    /// The elements can be floats but no particular result is guaranteed
3267    /// if an element is NaN.
3268    #[cfg(feature = "use_std")]
3269    fn max_set_by_key<K, F>(self, key: F) -> Vec<Self::Item>
3270        where Self: Sized, K: Ord, F: FnMut(&Self::Item) -> K
3271    {
3272        extrema_set::max_set_impl(self, key, |_, _, kx, ky| kx.cmp(ky))
3273    }
3274
3275    /// Return the minimum and maximum elements in the iterator.
3276    ///
3277    /// The return type `MinMaxResult` is an enum of three variants:
3278    ///
3279    /// - `NoElements` if the iterator is empty.
3280    /// - `OneElement(x)` if the iterator has exactly one element.
3281    /// - `MinMax(x, y)` is returned otherwise, where `x <= y`. Two
3282    ///    values are equal if and only if there is more than one
3283    ///    element in the iterator and all elements are equal.
3284    ///
3285    /// On an iterator of length `n`, `minmax` does `1.5 * n` comparisons,
3286    /// and so is faster than calling `min` and `max` separately which does
3287    /// `2 * n` comparisons.
3288    ///
3289    /// # Examples
3290    ///
3291    /// ```
3292    /// use itertools::Itertools;
3293    /// use itertools::MinMaxResult::{NoElements, OneElement, MinMax};
3294    ///
3295    /// let a: [i32; 0] = [];
3296    /// assert_eq!(a.iter().minmax(), NoElements);
3297    ///
3298    /// let a = [1];
3299    /// assert_eq!(a.iter().minmax(), OneElement(&1));
3300    ///
3301    /// let a = [1, 2, 3, 4, 5];
3302    /// assert_eq!(a.iter().minmax(), MinMax(&1, &5));
3303    ///
3304    /// let a = [1, 1, 1, 1];
3305    /// assert_eq!(a.iter().minmax(), MinMax(&1, &1));
3306    /// ```
3307    ///
3308    /// The elements can be floats but no particular result is guaranteed
3309    /// if an element is NaN.
3310    fn minmax(self) -> MinMaxResult<Self::Item>
3311        where Self: Sized, Self::Item: PartialOrd
3312    {
3313        minmax::minmax_impl(self, |_| (), |x, y, _, _| x < y)
3314    }
3315
3316    /// Return the minimum and maximum element of an iterator, as determined by
3317    /// the specified function.
3318    ///
3319    /// The return value is a variant of [`MinMaxResult`] like for [`.minmax()`](Itertools::minmax).
3320    ///
3321    /// For the minimum, the first minimal element is returned.  For the maximum,
3322    /// the last maximal element wins.  This matches the behavior of the standard
3323    /// [`Iterator::min`] and [`Iterator::max`] methods.
3324    ///
3325    /// The keys can be floats but no particular result is guaranteed
3326    /// if a key is NaN.
3327    fn minmax_by_key<K, F>(self, key: F) -> MinMaxResult<Self::Item>
3328        where Self: Sized, K: PartialOrd, F: FnMut(&Self::Item) -> K
3329    {
3330        minmax::minmax_impl(self, key, |_, _, xk, yk| xk < yk)
3331    }
3332
3333    /// Return the minimum and maximum element of an iterator, as determined by
3334    /// the specified comparison function.
3335    ///
3336    /// The return value is a variant of [`MinMaxResult`] like for [`.minmax()`](Itertools::minmax).
3337    ///
3338    /// For the minimum, the first minimal element is returned.  For the maximum,
3339    /// the last maximal element wins.  This matches the behavior of the standard
3340    /// [`Iterator::min`] and [`Iterator::max`] methods.
3341    fn minmax_by<F>(self, mut compare: F) -> MinMaxResult<Self::Item>
3342        where Self: Sized, F: FnMut(&Self::Item, &Self::Item) -> Ordering
3343    {
3344        minmax::minmax_impl(
3345            self,
3346            |_| (),
3347            |x, y, _, _| Ordering::Less == compare(x, y)
3348        )
3349    }
3350
3351    /// Return the position of the maximum element in the iterator.
3352    ///
3353    /// If several elements are equally maximum, the position of the
3354    /// last of them is returned.
3355    ///
3356    /// # Examples
3357    ///
3358    /// ```
3359    /// use itertools::Itertools;
3360    ///
3361    /// let a: [i32; 0] = [];
3362    /// assert_eq!(a.iter().position_max(), None);
3363    ///
3364    /// let a = [-3, 0, 1, 5, -10];
3365    /// assert_eq!(a.iter().position_max(), Some(3));
3366    ///
3367    /// let a = [1, 1, -1, -1];
3368    /// assert_eq!(a.iter().position_max(), Some(1));
3369    /// ```
3370    fn position_max(self) -> Option<usize>
3371        where Self: Sized, Self::Item: Ord
3372    {
3373        self.enumerate()
3374            .max_by(|x, y| Ord::cmp(&x.1, &y.1))
3375            .map(|x| x.0)
3376    }
3377
3378    /// Return the position of the maximum element in the iterator, as
3379    /// determined by the specified function.
3380    ///
3381    /// If several elements are equally maximum, the position of the
3382    /// last of them is returned.
3383    ///
3384    /// # Examples
3385    ///
3386    /// ```
3387    /// use itertools::Itertools;
3388    ///
3389    /// let a: [i32; 0] = [];
3390    /// assert_eq!(a.iter().position_max_by_key(|x| x.abs()), None);
3391    ///
3392    /// let a = [-3_i32, 0, 1, 5, -10];
3393    /// assert_eq!(a.iter().position_max_by_key(|x| x.abs()), Some(4));
3394    ///
3395    /// let a = [1_i32, 1, -1, -1];
3396    /// assert_eq!(a.iter().position_max_by_key(|x| x.abs()), Some(3));
3397    /// ```
3398    fn position_max_by_key<K, F>(self, mut key: F) -> Option<usize>
3399        where Self: Sized, K: Ord, F: FnMut(&Self::Item) -> K
3400    {
3401        self.enumerate()
3402            .max_by(|x, y| Ord::cmp(&key(&x.1), &key(&y.1)))
3403            .map(|x| x.0)
3404    }
3405
3406    /// Return the position of the maximum element in the iterator, as
3407    /// determined by the specified comparison function.
3408    ///
3409    /// If several elements are equally maximum, the position of the
3410    /// last of them is returned.
3411    ///
3412    /// # Examples
3413    ///
3414    /// ```
3415    /// use itertools::Itertools;
3416    ///
3417    /// let a: [i32; 0] = [];
3418    /// assert_eq!(a.iter().position_max_by(|x, y| x.cmp(y)), None);
3419    ///
3420    /// let a = [-3_i32, 0, 1, 5, -10];
3421    /// assert_eq!(a.iter().position_max_by(|x, y| x.cmp(y)), Some(3));
3422    ///
3423    /// let a = [1_i32, 1, -1, -1];
3424    /// assert_eq!(a.iter().position_max_by(|x, y| x.cmp(y)), Some(1));
3425    /// ```
3426    fn position_max_by<F>(self, mut compare: F) -> Option<usize>
3427        where Self: Sized, F: FnMut(&Self::Item, &Self::Item) -> Ordering
3428    {
3429        self.enumerate()
3430            .max_by(|x, y| compare(&x.1, &y.1))
3431            .map(|x| x.0)
3432    }
3433
3434    /// Return the position of the minimum element in the iterator.
3435    ///
3436    /// If several elements are equally minimum, the position of the
3437    /// first of them is returned.
3438    ///
3439    /// # Examples
3440    ///
3441    /// ```
3442    /// use itertools::Itertools;
3443    ///
3444    /// let a: [i32; 0] = [];
3445    /// assert_eq!(a.iter().position_min(), None);
3446    ///
3447    /// let a = [-3, 0, 1, 5, -10];
3448    /// assert_eq!(a.iter().position_min(), Some(4));
3449    ///
3450    /// let a = [1, 1, -1, -1];
3451    /// assert_eq!(a.iter().position_min(), Some(2));
3452    /// ```
3453    fn position_min(self) -> Option<usize>
3454        where Self: Sized, Self::Item: Ord
3455    {
3456        self.enumerate()
3457            .min_by(|x, y| Ord::cmp(&x.1, &y.1))
3458            .map(|x| x.0)
3459    }
3460
3461    /// Return the position of the minimum element in the iterator, as
3462    /// determined by the specified function.
3463    ///
3464    /// If several elements are equally minimum, the position of the
3465    /// first of them is returned.
3466    ///
3467    /// # Examples
3468    ///
3469    /// ```
3470    /// use itertools::Itertools;
3471    ///
3472    /// let a: [i32; 0] = [];
3473    /// assert_eq!(a.iter().position_min_by_key(|x| x.abs()), None);
3474    ///
3475    /// let a = [-3_i32, 0, 1, 5, -10];
3476    /// assert_eq!(a.iter().position_min_by_key(|x| x.abs()), Some(1));
3477    ///
3478    /// let a = [1_i32, 1, -1, -1];
3479    /// assert_eq!(a.iter().position_min_by_key(|x| x.abs()), Some(0));
3480    /// ```
3481    fn position_min_by_key<K, F>(self, mut key: F) -> Option<usize>
3482        where Self: Sized, K: Ord, F: FnMut(&Self::Item) -> K
3483    {
3484        self.enumerate()
3485            .min_by(|x, y| Ord::cmp(&key(&x.1), &key(&y.1)))
3486            .map(|x| x.0)
3487    }
3488
3489    /// Return the position of the minimum element in the iterator, as
3490    /// determined by the specified comparison function.
3491    ///
3492    /// If several elements are equally minimum, the position of the
3493    /// first of them is returned.
3494    ///
3495    /// # Examples
3496    ///
3497    /// ```
3498    /// use itertools::Itertools;
3499    ///
3500    /// let a: [i32; 0] = [];
3501    /// assert_eq!(a.iter().position_min_by(|x, y| x.cmp(y)), None);
3502    ///
3503    /// let a = [-3_i32, 0, 1, 5, -10];
3504    /// assert_eq!(a.iter().position_min_by(|x, y| x.cmp(y)), Some(4));
3505    ///
3506    /// let a = [1_i32, 1, -1, -1];
3507    /// assert_eq!(a.iter().position_min_by(|x, y| x.cmp(y)), Some(2));
3508    /// ```
3509    fn position_min_by<F>(self, mut compare: F) -> Option<usize>
3510        where Self: Sized, F: FnMut(&Self::Item, &Self::Item) -> Ordering
3511    {
3512        self.enumerate()
3513            .min_by(|x, y| compare(&x.1, &y.1))
3514            .map(|x| x.0)
3515    }
3516
3517    /// Return the positions of the minimum and maximum elements in
3518    /// the iterator.
3519    ///
3520    /// The return type [`MinMaxResult`] is an enum of three variants:
3521    ///
3522    /// - `NoElements` if the iterator is empty.
3523    /// - `OneElement(xpos)` if the iterator has exactly one element.
3524    /// - `MinMax(xpos, ypos)` is returned otherwise, where the
3525    ///    element at `xpos` ≤ the element at `ypos`. While the
3526    ///    referenced elements themselves may be equal, `xpos` cannot
3527    ///    be equal to `ypos`.
3528    ///
3529    /// On an iterator of length `n`, `position_minmax` does `1.5 * n`
3530    /// comparisons, and so is faster than calling `position_min` and
3531    /// `position_max` separately which does `2 * n` comparisons.
3532    ///
3533    /// For the minimum, if several elements are equally minimum, the
3534    /// position of the first of them is returned. For the maximum, if
3535    /// several elements are equally maximum, the position of the last
3536    /// of them is returned.
3537    ///
3538    /// The elements can be floats but no particular result is
3539    /// guaranteed if an element is NaN.
3540    ///
3541    /// # Examples
3542    ///
3543    /// ```
3544    /// use itertools::Itertools;
3545    /// use itertools::MinMaxResult::{NoElements, OneElement, MinMax};
3546    ///
3547    /// let a: [i32; 0] = [];
3548    /// assert_eq!(a.iter().position_minmax(), NoElements);
3549    ///
3550    /// let a = [10];
3551    /// assert_eq!(a.iter().position_minmax(), OneElement(0));
3552    ///
3553    /// let a = [-3, 0, 1, 5, -10];
3554    /// assert_eq!(a.iter().position_minmax(), MinMax(4, 3));
3555    ///
3556    /// let a = [1, 1, -1, -1];
3557    /// assert_eq!(a.iter().position_minmax(), MinMax(2, 1));
3558    /// ```
3559    fn position_minmax(self) -> MinMaxResult<usize>
3560        where Self: Sized, Self::Item: PartialOrd
3561    {
3562        use crate::MinMaxResult::{NoElements, OneElement, MinMax};
3563        match minmax::minmax_impl(self.enumerate(), |_| (), |x, y, _, _| x.1 < y.1) {
3564            NoElements => NoElements,
3565            OneElement(x) => OneElement(x.0),
3566            MinMax(x, y) => MinMax(x.0, y.0),
3567        }
3568    }
3569
3570    /// Return the postions of the minimum and maximum elements of an
3571    /// iterator, as determined by the specified function.
3572    ///
3573    /// The return value is a variant of [`MinMaxResult`] like for
3574    /// [`position_minmax`].
3575    ///
3576    /// For the minimum, if several elements are equally minimum, the
3577    /// position of the first of them is returned. For the maximum, if
3578    /// several elements are equally maximum, the position of the last
3579    /// of them is returned.
3580    ///
3581    /// The keys can be floats but no particular result is guaranteed
3582    /// if a key is NaN.
3583    ///
3584    /// # Examples
3585    ///
3586    /// ```
3587    /// use itertools::Itertools;
3588    /// use itertools::MinMaxResult::{NoElements, OneElement, MinMax};
3589    ///
3590    /// let a: [i32; 0] = [];
3591    /// assert_eq!(a.iter().position_minmax_by_key(|x| x.abs()), NoElements);
3592    ///
3593    /// let a = [10_i32];
3594    /// assert_eq!(a.iter().position_minmax_by_key(|x| x.abs()), OneElement(0));
3595    ///
3596    /// let a = [-3_i32, 0, 1, 5, -10];
3597    /// assert_eq!(a.iter().position_minmax_by_key(|x| x.abs()), MinMax(1, 4));
3598    ///
3599    /// let a = [1_i32, 1, -1, -1];
3600    /// assert_eq!(a.iter().position_minmax_by_key(|x| x.abs()), MinMax(0, 3));
3601    /// ```
3602    ///
3603    /// [`position_minmax`]: Self::position_minmax
3604    fn position_minmax_by_key<K, F>(self, mut key: F) -> MinMaxResult<usize>
3605        where Self: Sized, K: PartialOrd, F: FnMut(&Self::Item) -> K
3606    {
3607        use crate::MinMaxResult::{NoElements, OneElement, MinMax};
3608        match self.enumerate().minmax_by_key(|e| key(&e.1)) {
3609            NoElements => NoElements,
3610            OneElement(x) => OneElement(x.0),
3611            MinMax(x, y) => MinMax(x.0, y.0),
3612        }
3613    }
3614
3615    /// Return the postions of the minimum and maximum elements of an
3616    /// iterator, as determined by the specified comparison function.
3617    ///
3618    /// The return value is a variant of [`MinMaxResult`] like for
3619    /// [`position_minmax`].
3620    ///
3621    /// For the minimum, if several elements are equally minimum, the
3622    /// position of the first of them is returned. For the maximum, if
3623    /// several elements are equally maximum, the position of the last
3624    /// of them is returned.
3625    ///
3626    /// # Examples
3627    ///
3628    /// ```
3629    /// use itertools::Itertools;
3630    /// use itertools::MinMaxResult::{NoElements, OneElement, MinMax};
3631    ///
3632    /// let a: [i32; 0] = [];
3633    /// assert_eq!(a.iter().position_minmax_by(|x, y| x.cmp(y)), NoElements);
3634    ///
3635    /// let a = [10_i32];
3636    /// assert_eq!(a.iter().position_minmax_by(|x, y| x.cmp(y)), OneElement(0));
3637    ///
3638    /// let a = [-3_i32, 0, 1, 5, -10];
3639    /// assert_eq!(a.iter().position_minmax_by(|x, y| x.cmp(y)), MinMax(4, 3));
3640    ///
3641    /// let a = [1_i32, 1, -1, -1];
3642    /// assert_eq!(a.iter().position_minmax_by(|x, y| x.cmp(y)), MinMax(2, 1));
3643    /// ```
3644    ///
3645    /// [`position_minmax`]: Self::position_minmax
3646    fn position_minmax_by<F>(self, mut compare: F) -> MinMaxResult<usize>
3647        where Self: Sized, F: FnMut(&Self::Item, &Self::Item) -> Ordering
3648    {
3649        use crate::MinMaxResult::{NoElements, OneElement, MinMax};
3650        match self.enumerate().minmax_by(|x, y| compare(&x.1, &y.1)) {
3651            NoElements => NoElements,
3652            OneElement(x) => OneElement(x.0),
3653            MinMax(x, y) => MinMax(x.0, y.0),
3654        }
3655    }
3656
3657    /// If the iterator yields exactly one element, that element will be returned, otherwise
3658    /// an error will be returned containing an iterator that has the same output as the input
3659    /// iterator.
3660    ///
3661    /// This provides an additional layer of validation over just calling `Iterator::next()`.
3662    /// If your assumption that there should only be one element yielded is false this provides
3663    /// the opportunity to detect and handle that, preventing errors at a distance.
3664    ///
3665    /// # Examples
3666    /// ```
3667    /// use itertools::Itertools;
3668    ///
3669    /// assert_eq!((0..10).filter(|&x| x == 2).exactly_one().unwrap(), 2);
3670    /// assert!((0..10).filter(|&x| x > 1 && x < 4).exactly_one().unwrap_err().eq(2..4));
3671    /// assert!((0..10).filter(|&x| x > 1 && x < 5).exactly_one().unwrap_err().eq(2..5));
3672    /// assert!((0..10).filter(|&_| false).exactly_one().unwrap_err().eq(0..0));
3673    /// ```
3674    fn exactly_one(mut self) -> Result<Self::Item, ExactlyOneError<Self>>
3675    where
3676        Self: Sized,
3677    {
3678        match self.next() {
3679            Some(first) => {
3680                match self.next() {
3681                    Some(second) => {
3682                        Err(ExactlyOneError::new(Some(Either::Left([first, second])), self))
3683                    }
3684                    None => {
3685                        Ok(first)
3686                    }
3687                }
3688            }
3689            None => Err(ExactlyOneError::new(None, self)),
3690        }
3691    }
3692
3693    /// If the iterator yields no elements, Ok(None) will be returned. If the iterator yields
3694    /// exactly one element, that element will be returned, otherwise an error will be returned
3695    /// containing an iterator that has the same output as the input iterator.
3696    ///
3697    /// This provides an additional layer of validation over just calling `Iterator::next()`.
3698    /// If your assumption that there should be at most one element yielded is false this provides
3699    /// the opportunity to detect and handle that, preventing errors at a distance.
3700    ///
3701    /// # Examples
3702    /// ```
3703    /// use itertools::Itertools;
3704    ///
3705    /// assert_eq!((0..10).filter(|&x| x == 2).at_most_one().unwrap(), Some(2));
3706    /// assert!((0..10).filter(|&x| x > 1 && x < 4).at_most_one().unwrap_err().eq(2..4));
3707    /// assert!((0..10).filter(|&x| x > 1 && x < 5).at_most_one().unwrap_err().eq(2..5));
3708    /// assert_eq!((0..10).filter(|&_| false).at_most_one().unwrap(), None);
3709    /// ```
3710    fn at_most_one(mut self) -> Result<Option<Self::Item>, ExactlyOneError<Self>>
3711    where
3712        Self: Sized,
3713    {
3714        match self.next() {
3715            Some(first) => {
3716                match self.next() {
3717                    Some(second) => {
3718                        Err(ExactlyOneError::new(Some(Either::Left([first, second])), self))
3719                    }
3720                    None => {
3721                        Ok(Some(first))
3722                    }
3723                }
3724            }
3725            None => Ok(None),
3726        }
3727    }
3728
3729    /// An iterator adaptor that allows the user to peek at multiple `.next()`
3730    /// values without advancing the base iterator.
3731    ///
3732    /// # Examples
3733    /// ```
3734    /// use itertools::Itertools;
3735    ///
3736    /// let mut iter = (0..10).multipeek();
3737    /// assert_eq!(iter.peek(), Some(&0));
3738    /// assert_eq!(iter.peek(), Some(&1));
3739    /// assert_eq!(iter.peek(), Some(&2));
3740    /// assert_eq!(iter.next(), Some(0));
3741    /// assert_eq!(iter.peek(), Some(&1));
3742    /// ```
3743    #[cfg(feature = "use_alloc")]
3744    fn multipeek(self) -> MultiPeek<Self>
3745    where
3746        Self: Sized,
3747    {
3748        multipeek_impl::multipeek(self)
3749    }
3750
3751    /// Collect the items in this iterator and return a `HashMap` which
3752    /// contains each item that appears in the iterator and the number
3753    /// of times it appears.
3754    ///
3755    /// # Examples
3756    /// ```
3757    /// # use itertools::Itertools;
3758    /// let counts = [1, 1, 1, 3, 3, 5].into_iter().counts();
3759    /// assert_eq!(counts[&1], 3);
3760    /// assert_eq!(counts[&3], 2);
3761    /// assert_eq!(counts[&5], 1);
3762    /// assert_eq!(counts.get(&0), None);
3763    /// ```
3764    #[cfg(feature = "use_std")]
3765    fn counts(self) -> HashMap<Self::Item, usize>
3766    where
3767        Self: Sized,
3768        Self::Item: Eq + Hash,
3769    {
3770        let mut counts = HashMap::new();
3771        self.for_each(|item| *counts.entry(item).or_default() += 1);
3772        counts
3773    }
3774
3775    /// Collect the items in this iterator and return a `HashMap` which
3776    /// contains each item that appears in the iterator and the number
3777    /// of times it appears,
3778    /// determining identity using a keying function.
3779    ///
3780    /// ```
3781    /// # use itertools::Itertools;
3782    /// struct Character {
3783    ///   first_name: &'static str,
3784    ///   last_name:  &'static str,
3785    /// }
3786    ///
3787    /// let characters =
3788    ///     vec![
3789    ///         Character { first_name: "Amy",   last_name: "Pond"      },
3790    ///         Character { first_name: "Amy",   last_name: "Wong"      },
3791    ///         Character { first_name: "Amy",   last_name: "Santiago"  },
3792    ///         Character { first_name: "James", last_name: "Bond"      },
3793    ///         Character { first_name: "James", last_name: "Sullivan"  },
3794    ///         Character { first_name: "James", last_name: "Norington" },
3795    ///         Character { first_name: "James", last_name: "Kirk"      },
3796    ///     ];
3797    ///
3798    /// let first_name_frequency =
3799    ///     characters
3800    ///         .into_iter()
3801    ///         .counts_by(|c| c.first_name);
3802    ///
3803    /// assert_eq!(first_name_frequency["Amy"], 3);
3804    /// assert_eq!(first_name_frequency["James"], 4);
3805    /// assert_eq!(first_name_frequency.contains_key("Asha"), false);
3806    /// ```
3807    #[cfg(feature = "use_std")]
3808    fn counts_by<K, F>(self, f: F) -> HashMap<K, usize>
3809    where
3810        Self: Sized,
3811        K: Eq + Hash,
3812        F: FnMut(Self::Item) -> K,
3813    {
3814        self.map(f).counts()
3815    }
3816
3817    /// Converts an iterator of tuples into a tuple of containers.
3818    ///
3819    /// `unzip()` consumes an entire iterator of n-ary tuples, producing `n` collections, one for each
3820    /// column.
3821    ///
3822    /// This function is, in some sense, the opposite of [`multizip`].
3823    ///
3824    /// ```
3825    /// use itertools::Itertools;
3826    ///
3827    /// let inputs = vec![(1, 2, 3), (4, 5, 6), (7, 8, 9)];
3828    ///
3829    /// let (a, b, c): (Vec<_>, Vec<_>, Vec<_>) = inputs
3830    ///     .into_iter()
3831    ///     .multiunzip();
3832    ///
3833    /// assert_eq!(a, vec![1, 4, 7]);
3834    /// assert_eq!(b, vec![2, 5, 8]);
3835    /// assert_eq!(c, vec![3, 6, 9]);
3836    /// ```
3837    fn multiunzip<FromI>(self) -> FromI
3838    where
3839        Self: Sized + MultiUnzip<FromI>,
3840    {
3841        MultiUnzip::multiunzip(self)
3842    }
3843}
3844
3845impl<T: ?Sized> Itertools for T where T: Iterator { }
3846
3847/// Return `true` if both iterables produce equal sequences
3848/// (elements pairwise equal and sequences of the same length),
3849/// `false` otherwise.
3850///
3851/// [`IntoIterator`] enabled version of [`Iterator::eq`].
3852///
3853/// ```
3854/// assert!(itertools::equal(vec![1, 2, 3], 1..4));
3855/// assert!(!itertools::equal(&[0, 0], &[0, 0, 0]));
3856/// ```
3857pub fn equal<I, J>(a: I, b: J) -> bool
3858    where I: IntoIterator,
3859          J: IntoIterator,
3860          I::Item: PartialEq<J::Item>
3861{
3862    a.into_iter().eq(b)
3863}
3864
3865/// Assert that two iterables produce equal sequences, with the same
3866/// semantics as [`equal(a, b)`](equal).
3867///
3868/// **Panics** on assertion failure with a message that shows the
3869/// two iteration elements.
3870///
3871/// ```ignore
3872/// assert_equal("exceed".split('c'), "excess".split('c'));
3873/// // ^PANIC: panicked at 'Failed assertion Some("eed") == Some("ess") for iteration 1',
3874/// ```
3875pub fn assert_equal<I, J>(a: I, b: J)
3876    where I: IntoIterator,
3877          J: IntoIterator,
3878          I::Item: fmt::Debug + PartialEq<J::Item>,
3879          J::Item: fmt::Debug,
3880{
3881    let mut ia = a.into_iter();
3882    let mut ib = b.into_iter();
3883    let mut i = 0;
3884    loop {
3885        match (ia.next(), ib.next()) {
3886            (None, None) => return,
3887            (a, b) => {
3888                let equal = match (&a, &b) {
3889                    (&Some(ref a), &Some(ref b)) => a == b,
3890                    _ => false,
3891                };
3892                assert!(equal, "Failed assertion {a:?} == {b:?} for iteration {i}",
3893                        i=i, a=a, b=b);
3894                i += 1;
3895            }
3896        }
3897    }
3898}
3899
3900/// Partition a sequence using predicate `pred` so that elements
3901/// that map to `true` are placed before elements which map to `false`.
3902///
3903/// The order within the partitions is arbitrary.
3904///
3905/// Return the index of the split point.
3906///
3907/// ```
3908/// use itertools::partition;
3909///
3910/// # // use repeated numbers to not promise any ordering
3911/// let mut data = [7, 1, 1, 7, 1, 1, 7];
3912/// let split_index = partition(&mut data, |elt| *elt >= 3);
3913///
3914/// assert_eq!(data, [7, 7, 7, 1, 1, 1, 1]);
3915/// assert_eq!(split_index, 3);
3916/// ```
3917pub fn partition<'a, A: 'a, I, F>(iter: I, mut pred: F) -> usize
3918    where I: IntoIterator<Item = &'a mut A>,
3919          I::IntoIter: DoubleEndedIterator,
3920          F: FnMut(&A) -> bool
3921{
3922    let mut split_index = 0;
3923    let mut iter = iter.into_iter();
3924    'main: while let Some(front) = iter.next() {
3925        if !pred(front) {
3926            loop {
3927                match iter.next_back() {
3928                    Some(back) => if pred(back) {
3929                        std::mem::swap(front, back);
3930                        break;
3931                    },
3932                    None => break 'main,
3933                }
3934            }
3935        }
3936        split_index += 1;
3937    }
3938    split_index
3939}
3940
3941/// An enum used for controlling the execution of `fold_while`.
3942///
3943/// See [`.fold_while()`](Itertools::fold_while) for more information.
3944#[derive(Copy, Clone, Debug, Eq, PartialEq)]
3945pub enum FoldWhile<T> {
3946    /// Continue folding with this value
3947    Continue(T),
3948    /// Fold is complete and will return this value
3949    Done(T),
3950}
3951
3952impl<T> FoldWhile<T> {
3953    /// Return the value in the continue or done.
3954    pub fn into_inner(self) -> T {
3955        match self {
3956            FoldWhile::Continue(x) | FoldWhile::Done(x) => x,
3957        }
3958    }
3959
3960    /// Return true if `self` is `Done`, false if it is `Continue`.
3961    pub fn is_done(&self) -> bool {
3962        match *self {
3963            FoldWhile::Continue(_) => false,
3964            FoldWhile::Done(_) => true,
3965        }
3966    }
3967}