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