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