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