2 #![crate_name="itertools"]
3 #![cfg_attr(not(feature = "use_std"), no_std)]
5 //! Extra iterator adaptors, functions and macros.
7 //! To extend [`Iterator`] with methods in this crate, import
8 //! the [`Itertools` trait](./trait.Itertools.html):
11 //! use itertools::Itertools;
14 //! Now, new methods like [`interleave`](./trait.Itertools.html#method.interleave)
15 //! are available on all iterators:
18 //! use itertools::Itertools;
20 //! let it = (1..3).interleave(vec![-1, -2]);
21 //! itertools::assert_equal(it, vec![1, -1, 2, -2]);
24 //! Most iterator methods are also provided as functions (with the benefit
25 //! that they convert parameters using [`IntoIterator`]):
28 //! use itertools::interleave;
30 //! for elt in interleave(&[1, 2, 3], &[2, 3, 4]) {
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).
45 //! This version of itertools requires Rust 1.24 or later.
47 //! [`Iterator`]: https://doc.rust-lang.org/std/iter/trait.Iterator.html
48 #![doc(html_root_url="https://docs.rs/itertools/0.8/")]
52 #[cfg(not(feature = "use_std"))]
53 extern crate core
as std
;
55 pub use either
::Either
;
57 #[cfg(feature = "use_std")]
58 use std
::collections
::HashMap
;
59 use std
::iter
::{IntoIterator}
;
60 use std
::cmp
::Ordering
;
62 #[cfg(feature = "use_std")]
64 #[cfg(feature = "use_std")]
66 #[cfg(feature = "use_std")]
67 type VecIntoIter
<T
> = ::std
::vec
::IntoIter
<T
>;
68 #[cfg(feature = "use_std")]
69 use std
::iter
::FromIterator
;
74 // for compatibility with no std and macros
76 pub use std
::iter
as __std_iter
;
78 /// The concrete iterator types.
99 pub use adaptors
::Step
;
100 #[cfg(feature = "use_std")]
101 pub use adaptors
::MultiProduct
;
102 #[cfg(feature = "use_std")]
103 pub use combinations
::Combinations
;
104 pub use cons_tuples_impl
::ConsTuples
;
105 pub use format
::{Format, FormatWith}
;
106 #[cfg(feature = "use_std")]
107 pub use groupbylazy
::{IntoChunks, Chunk, Chunks, GroupBy, Group, Groups}
;
108 pub use intersperse
::Intersperse
;
109 #[cfg(feature = "use_std")]
110 pub use kmerge_impl
::{KMerge, KMergeBy}
;
111 pub use merge_join
::MergeJoinBy
;
112 #[cfg(feature = "use_std")]
113 pub use multipeek_impl
::MultiPeek
;
114 pub use pad_tail
::PadUsing
;
115 pub use peeking_take_while
::PeekingTakeWhile
;
116 pub use process_results_impl
::ProcessResults
;
117 #[cfg(feature = "use_std")]
118 pub use put_back_n_impl
::PutBackN
;
119 #[cfg(feature = "use_std")]
120 pub use rciter_impl
::RcIter
;
121 pub use repeatn
::RepeatN
;
123 pub use sources
::{RepeatCall, Unfold, Iterate}
;
124 #[cfg(feature = "use_std")]
126 pub use tuple_impl
::{TupleBuffer, TupleWindows, Tuples}
;
127 #[cfg(feature = "use_std")]
128 pub use unique_impl
::{Unique, UniqueBy}
;
129 pub use with_position
::WithPosition
;
130 pub use zip_eq_impl
::ZipEq
;
131 pub use zip_longest
::ZipLongest
;
132 pub use ziptuple
::Zip
;
136 pub use concat_impl
::concat
;
137 pub use cons_tuples_impl
::cons_tuples
;
138 pub use diff
::diff_with
;
140 #[cfg(feature = "use_std")]
141 pub use kmerge_impl
::{kmerge_by}
;
142 pub use minmax
::MinMaxResult
;
143 pub use peeking_take_while
::PeekingNext
;
144 pub use process_results_impl
::process_results
;
145 pub use repeatn
::repeat_n
;
147 pub use sources
::{repeat_call, unfold, iterate}
;
148 pub use with_position
::Position
;
149 pub use ziptuple
::multizip
;
152 pub use either_or_both
::EitherOrBoth
;
158 mod cons_tuples_impl
;
159 #[cfg(feature = "use_std")]
163 #[cfg(feature = "use_std")]
165 #[cfg(feature = "use_std")]
168 #[cfg(feature = "use_std")]
172 #[cfg(feature = "use_std")]
175 mod peeking_take_while
;
176 mod process_results_impl
;
177 #[cfg(feature = "use_std")]
179 #[cfg(feature = "use_std")]
184 #[cfg(feature = "use_std")]
187 #[cfg(feature = "use_std")]
195 /// Create an iterator over the “cartesian product” of iterators.
197 /// Iterator element type is like `(A, B, ..., E)` if formed
198 /// from iterators `(I, J, ..., M)` with element types `I::Item = A`, `J::Item = B`, etc.
201 /// #[macro_use] extern crate itertools;
203 /// // Iterate over the coordinates of a 4 x 4 x 4 grid
204 /// // from (0, 0, 0), (0, 0, 1), .., (0, 1, 0), (0, 1, 1), .. etc until (3, 3, 3)
205 /// for (i, j, k) in iproduct!(0..4, 0..4, 0..4) {
211 /// **Note:** To enable the macros in this crate, use the `#[macro_use]`
212 /// attribute when importing the crate:
215 /// #[macro_use] extern crate itertools;
218 macro_rules
! iproduct
{
219 (@flatten $I
:expr
,) => (
222 (@flatten $I
:expr
, $J
:expr
, $
($K
:expr
,)*) => (
223 iproduct
!(@flatten $
crate::cons_tuples(iproduct
!($I
, $J
)), $
($K
,)*)
226 $
crate::__std_iter
::IntoIterator
::into_iter($I
)
228 ($I
:expr
, $J
:expr
) => (
229 $
crate::Itertools
::cartesian_product(iproduct
!($I
), iproduct
!($J
))
231 ($I
:expr
, $J
:expr
, $
($K
:expr
),+) => (
232 iproduct
!(@flatten iproduct
!($I
, $J
), $
($K
,)+)
237 /// Create an iterator running multiple iterators in lockstep.
239 /// The `izip!` iterator yields elements until any subiterator
242 /// This is a version of the standard ``.zip()`` that's supporting more than
243 /// two iterators. The iterator element type is a tuple with one element
244 /// from each of the input iterators. Just like ``.zip()``, the iteration stops
245 /// when the shortest of the inputs reaches its end.
247 /// **Note:** The result of this macro is in the general case an iterator
248 /// composed of repeated `.zip()` and a `.map()`; it has an anonymous type.
249 /// The special cases of one and two arguments produce the equivalent of
250 /// `$a.into_iter()` and `$a.into_iter().zip($b)` respectively.
252 /// Prefer this macro `izip!()` over [`multizip`] for the performance benefits
253 /// of using the standard library `.zip()`.
255 /// [`multizip`]: fn.multizip.html
258 /// #[macro_use] extern crate itertools;
261 /// // iterate over three sequences side-by-side
262 /// let mut results = [0, 0, 0, 0];
263 /// let inputs = [3, 7, 9, 6];
265 /// for (r, index, input) in izip!(&mut results, 0..10, &inputs) {
266 /// *r = index * 10 + input;
269 /// assert_eq!(results, [0 + 3, 10 + 7, 29, 36]);
273 /// **Note:** To enable the macros in this crate, use the `#[macro_use]`
274 /// attribute when importing the crate:
277 /// #[macro_use] extern crate itertools;
281 // @closure creates a tuple-flattening closure for .map() call. usage:
282 // @closure partial_pattern => partial_tuple , rest , of , iterators
283 // eg. izip!( @closure ((a, b), c) => (a, b, c) , dd , ee )
284 ( @closure $p
:pat
=> $tup
:expr
) => {
288 // The "b" identifier is a different identifier on each recursion level thanks to hygiene.
289 ( @closure $p
:pat
=> ( $
($tup
:tt
)* ) , $_iter
:expr $
( , $tail
:expr
)* ) => {
290 izip
!(@
closure ($p
, b
) => ( $
($tup
)*, b
) $
( , $tail
)*)
294 ($first
:expr $
(,)*) => {
295 $
crate::__std_iter
::IntoIterator
::into_iter($first
)
299 ($first
:expr
, $second
:expr $
(,)*) => {
305 ( $first
:expr $
( , $rest
:expr
)* $
(,)* ) => {
311 izip
!(@closure a
=> (a
) $
( , $rest
)*)
316 /// An [`Iterator`] blanket implementation that provides extra adaptors and
319 /// This trait defines a number of methods. They are divided into two groups:
321 /// * *Adaptors* take an iterator and parameter as input, and return
322 /// a new iterator value. These are listed first in the trait. An example
323 /// of an adaptor is [`.interleave()`](#method.interleave)
325 /// * *Regular methods* are those that don't return iterators and instead
326 /// return a regular value of some other kind.
327 /// [`.next_tuple()`](#method.next_tuple) is an example and the first regular
328 /// method in the list.
330 /// [`Iterator`]: https://doc.rust-lang.org/std/iter/trait.Iterator.html
331 pub trait Itertools
: Iterator
{
334 /// Alternate elements from two iterators until both have run out.
336 /// Iterator element type is `Self::Item`.
338 /// This iterator is *fused*.
341 /// use itertools::Itertools;
343 /// let it = (1..7).interleave(vec![-1, -2]);
344 /// itertools::assert_equal(it, vec![1, -1, 2, -2, 3, 4, 5, 6]);
346 fn interleave
<J
>(self, other
: J
) -> Interleave
<Self, J
::IntoIter
>
347 where J
: IntoIterator
<Item
= Self::Item
>,
350 interleave(self, other
)
353 /// Alternate elements from two iterators until at least one of them has run
356 /// Iterator element type is `Self::Item`.
359 /// use itertools::Itertools;
361 /// let it = (1..7).interleave_shortest(vec![-1, -2]);
362 /// itertools::assert_equal(it, vec![1, -1, 2, -2, 3]);
364 fn interleave_shortest
<J
>(self, other
: J
) -> InterleaveShortest
<Self, J
::IntoIter
>
365 where J
: IntoIterator
<Item
= Self::Item
>,
368 adaptors
::interleave_shortest(self, other
.into_iter())
371 /// An iterator adaptor to insert a particular value
372 /// between each element of the adapted iterator.
374 /// Iterator element type is `Self::Item`.
376 /// This iterator is *fused*.
379 /// use itertools::Itertools;
381 /// itertools::assert_equal((0..3).intersperse(8), vec![0, 8, 1, 8, 2]);
383 fn intersperse(self, element
: Self::Item
) -> Intersperse
<Self>
387 intersperse
::intersperse(self, element
)
390 /// Create an iterator which iterates over both this and the specified
391 /// iterator simultaneously, yielding pairs of two optional elements.
393 /// This iterator is *fused*.
395 /// As long as neither input iterator is exhausted yet, it yields two values
396 /// via `EitherOrBoth::Both`.
398 /// When the parameter iterator is exhausted, it only yields a value from the
399 /// `self` iterator via `EitherOrBoth::Left`.
401 /// When the `self` iterator is exhausted, it only yields a value from the
402 /// parameter iterator via `EitherOrBoth::Right`.
404 /// When both iterators return `None`, all further invocations of `.next()`
405 /// will return `None`.
407 /// Iterator element type is
408 /// [`EitherOrBoth<Self::Item, J::Item>`](enum.EitherOrBoth.html).
411 /// use itertools::EitherOrBoth::{Both, Right};
412 /// use itertools::Itertools;
413 /// let it = (0..1).zip_longest(1..3);
414 /// itertools::assert_equal(it, vec![Both(0, 1), Right(2)]);
417 fn zip_longest
<J
>(self, other
: J
) -> ZipLongest
<Self, J
::IntoIter
>
418 where J
: IntoIterator
,
421 zip_longest
::zip_longest(self, other
.into_iter())
424 /// Create an iterator which iterates over both this and the specified
425 /// iterator simultaneously, yielding pairs of elements.
427 /// **Panics** if the iterators reach an end and they are not of equal
430 fn zip_eq
<J
>(self, other
: J
) -> ZipEq
<Self, J
::IntoIter
>
431 where J
: IntoIterator
,
437 /// A “meta iterator adaptor”. Its closure receives a reference to the
438 /// iterator and may pick off as many elements as it likes, to produce the
439 /// next iterator element.
441 /// Iterator element type is `B`.
444 /// use itertools::Itertools;
446 /// // An adaptor that gathers elements in pairs
447 /// let pit = (0..4).batching(|it| {
448 /// match it.next() {
450 /// Some(x) => match it.next() {
452 /// Some(y) => Some((x, y)),
457 /// itertools::assert_equal(pit, vec![(0, 1), (2, 3)]);
460 fn batching
<B
, F
>(self, f
: F
) -> Batching
<Self, F
>
461 where F
: FnMut(&mut Self) -> Option
<B
>,
464 adaptors
::batching(self, f
)
467 /// Return an *iterable* that can group iterator elements.
468 /// Consecutive elements that map to the same key (“runs”), are assigned
469 /// to the same group.
471 /// `GroupBy` is the storage for the lazy grouping operation.
473 /// If the groups are consumed in order, or if each group's iterator is
474 /// dropped without keeping it around, then `GroupBy` uses no
475 /// allocations. It needs allocations only if several group iterators
476 /// are alive at the same time.
478 /// This type implements `IntoIterator` (it is **not** an iterator
479 /// itself), because the group iterators need to borrow from this
480 /// value. It should be stored in a local variable or temporary and
483 /// Iterator element type is `(K, Group)`: the group's key and the
487 /// use itertools::Itertools;
489 /// // group data into runs of larger than zero or not.
490 /// let data = vec![1, 3, -2, -2, 1, 0, 1, 2];
491 /// // groups: |---->|------>|--------->|
493 /// // Note: The `&` is significant here, `GroupBy` is iterable
494 /// // only by reference. You can also call `.into_iter()` explicitly.
495 /// for (key, group) in &data.into_iter().group_by(|elt| *elt >= 0) {
496 /// // Check that the sum of each group is +/- 4.
497 /// assert_eq!(4, group.sum::<i32>().abs());
500 #[cfg(feature = "use_std")]
501 fn group_by
<K
, F
>(self, key
: F
) -> GroupBy
<K
, Self, F
>
503 F
: FnMut(&Self::Item
) -> K
,
506 groupbylazy
::new(self, key
)
509 /// Return an *iterable* that can chunk the iterator.
511 /// Yield subiterators (chunks) that each yield a fixed number elements,
512 /// determined by `size`. The last chunk will be shorter if there aren't
515 /// `IntoChunks` is based on `GroupBy`: it is iterable (implements
516 /// `IntoIterator`, **not** `Iterator`), and it only buffers if several
517 /// chunk iterators are alive at the same time.
519 /// Iterator element type is `Chunk`, each chunk's iterator.
521 /// **Panics** if `size` is 0.
524 /// use itertools::Itertools;
526 /// let data = vec![1, 1, 2, -2, 6, 0, 3, 1];
527 /// //chunk size=3 |------->|-------->|--->|
529 /// // Note: The `&` is significant here, `IntoChunks` is iterable
530 /// // only by reference. You can also call `.into_iter()` explicitly.
531 /// for chunk in &data.into_iter().chunks(3) {
532 /// // Check that the sum of each chunk is 4.
533 /// assert_eq!(4, chunk.sum());
536 #[cfg(feature = "use_std")]
537 fn chunks(self, size
: usize) -> IntoChunks
<Self>
541 groupbylazy
::new_chunks(self, size
)
544 /// Return an iterator over all contiguous windows producing tuples of
545 /// a specific size (up to 4).
547 /// `tuple_windows` clones the iterator elements so that they can be
548 /// part of successive windows, this makes it most suited for iterators
549 /// of references and other values that are cheap to copy.
552 /// use itertools::Itertools;
553 /// let mut v = Vec::new();
554 /// for (a, b) in (1..5).tuple_windows() {
557 /// assert_eq!(v, vec![(1, 2), (2, 3), (3, 4)]);
559 /// let mut it = (1..5).tuple_windows();
560 /// assert_eq!(Some((1, 2, 3)), it.next());
561 /// assert_eq!(Some((2, 3, 4)), it.next());
562 /// assert_eq!(None, it.next());
564 /// // this requires a type hint
565 /// let it = (1..5).tuple_windows::<(_, _, _)>();
566 /// itertools::assert_equal(it, vec![(1, 2, 3), (2, 3, 4)]);
568 /// // you can also specify the complete type
569 /// use itertools::TupleWindows;
570 /// use std::ops::Range;
572 /// let it: TupleWindows<Range<u32>, (u32, u32, u32)> = (1..5).tuple_windows();
573 /// itertools::assert_equal(it, vec![(1, 2, 3), (2, 3, 4)]);
575 fn tuple_windows
<T
>(self) -> TupleWindows
<Self, T
>
576 where Self: Sized
+ Iterator
<Item
= T
::Item
>,
577 T
: tuple_impl
::TupleCollect
,
580 tuple_impl
::tuple_windows(self)
583 /// Return an iterator that groups the items in tuples of a specific size
586 /// See also the method [`.next_tuple()`](#method.next_tuple).
589 /// use itertools::Itertools;
590 /// let mut v = Vec::new();
591 /// for (a, b) in (1..5).tuples() {
594 /// assert_eq!(v, vec![(1, 2), (3, 4)]);
596 /// let mut it = (1..7).tuples();
597 /// assert_eq!(Some((1, 2, 3)), it.next());
598 /// assert_eq!(Some((4, 5, 6)), it.next());
599 /// assert_eq!(None, it.next());
601 /// // this requires a type hint
602 /// let it = (1..7).tuples::<(_, _, _)>();
603 /// itertools::assert_equal(it, vec![(1, 2, 3), (4, 5, 6)]);
605 /// // you can also specify the complete type
606 /// use itertools::Tuples;
607 /// use std::ops::Range;
609 /// let it: Tuples<Range<u32>, (u32, u32, u32)> = (1..7).tuples();
610 /// itertools::assert_equal(it, vec![(1, 2, 3), (4, 5, 6)]);
613 /// See also [`Tuples::into_buffer`](structs/struct.Tuples.html#method.into_buffer).
614 fn tuples
<T
>(self) -> Tuples
<Self, T
>
615 where Self: Sized
+ Iterator
<Item
= T
::Item
>,
616 T
: tuple_impl
::TupleCollect
618 tuple_impl
::tuples(self)
621 /// Split into an iterator pair that both yield all elements from
622 /// the original iterator.
624 /// **Note:** If the iterator is clonable, prefer using that instead
625 /// of using this method. It is likely to be more efficient.
627 /// Iterator element type is `Self::Item`.
630 /// use itertools::Itertools;
631 /// let xs = vec![0, 1, 2, 3];
633 /// let (mut t1, t2) = xs.into_iter().tee();
634 /// itertools::assert_equal(t1.next(), Some(0));
635 /// itertools::assert_equal(t2, 0..4);
636 /// itertools::assert_equal(t1, 1..4);
638 #[cfg(feature = "use_std")]
639 fn tee(self) -> (Tee
<Self>, Tee
<Self>)
646 /// Return an iterator adaptor that steps `n` elements in the base iterator
647 /// for each iteration.
649 /// The iterator steps by yielding the next element from the base iterator,
650 /// then skipping forward `n - 1` elements.
652 /// Iterator element type is `Self::Item`.
654 /// **Panics** if the step is 0.
657 /// use itertools::Itertools;
659 /// let it = (0..8).step(3);
660 /// itertools::assert_equal(it, vec![0, 3, 6]);
662 #[deprecated(note="Use std .step_by() instead", since="0.8")]
664 fn step(self, n
: usize) -> Step
<Self>
667 adaptors
::step(self, n
)
670 /// Convert each item of the iterator using the `Into` trait.
673 /// use itertools::Itertools;
675 /// (1i32..42i32).map_into::<f64>().collect_vec();
677 fn map_into
<R
>(self) -> MapInto
<Self, R
>
681 adaptors
::map_into(self)
684 /// Return an iterator adaptor that applies the provided closure
685 /// to every `Result::Ok` value. `Result::Err` values are
689 /// use itertools::Itertools;
691 /// let input = vec![Ok(41), Err(false), Ok(11)];
692 /// let it = input.into_iter().map_results(|i| i + 1);
693 /// itertools::assert_equal(it, vec![Ok(42), Err(false), Ok(12)]);
695 fn map_results
<F
, T
, U
, E
>(self, f
: F
) -> MapResults
<Self, F
>
696 where Self: Iterator
<Item
= Result
<T
, E
>> + Sized
,
699 adaptors
::map_results(self, f
)
702 /// Return an iterator adaptor that merges the two base iterators in
703 /// ascending order. If both base iterators are sorted (ascending), the
704 /// result is sorted.
706 /// Iterator element type is `Self::Item`.
709 /// use itertools::Itertools;
711 /// let a = (0..11).step(3);
712 /// let b = (0..11).step(5);
713 /// let it = a.merge(b);
714 /// itertools::assert_equal(it, vec![0, 0, 3, 5, 6, 9, 10]);
716 fn merge
<J
>(self, other
: J
) -> Merge
<Self, J
::IntoIter
>
718 Self::Item
: PartialOrd
,
719 J
: IntoIterator
<Item
= Self::Item
>
724 /// Return an iterator adaptor that merges the two base iterators in order.
725 /// This is much like `.merge()` but allows for a custom ordering.
727 /// This can be especially useful for sequences of tuples.
729 /// Iterator element type is `Self::Item`.
732 /// use itertools::Itertools;
734 /// let a = (0..).zip("bc".chars());
735 /// let b = (0..).zip("ad".chars());
736 /// let it = a.merge_by(b, |x, y| x.1 <= y.1);
737 /// itertools::assert_equal(it, vec![(0, 'a'), (0, 'b'), (1, 'c'), (1, 'd')]);
740 fn merge_by
<J
, F
>(self, other
: J
, is_first
: F
) -> MergeBy
<Self, J
::IntoIter
, F
>
742 J
: IntoIterator
<Item
= Self::Item
>,
743 F
: FnMut(&Self::Item
, &Self::Item
) -> bool
745 adaptors
::merge_by_new(self, other
.into_iter(), is_first
)
748 /// Create an iterator that merges items from both this and the specified
749 /// iterator in ascending order.
751 /// It chooses whether to pair elements based on the `Ordering` returned by the
752 /// specified compare function. At any point, inspecting the tip of the
753 /// iterators `I` and `J` as items `i` of type `I::Item` and `j` of type
754 /// `J::Item` respectively, the resulting iterator will:
756 /// - Emit `EitherOrBoth::Left(i)` when `i < j`,
757 /// and remove `i` from its source iterator
758 /// - Emit `EitherOrBoth::Right(j)` when `i > j`,
759 /// and remove `j` from its source iterator
760 /// - Emit `EitherOrBoth::Both(i, j)` when `i == j`,
761 /// and remove both `i` and `j` from their respective source iterators
764 /// use itertools::Itertools;
765 /// use itertools::EitherOrBoth::{Left, Right, Both};
767 /// let ki = (0..10).step(3);
768 /// let ku = (0..10).step(5);
769 /// let ki_ku = ki.merge_join_by(ku, |i, j| i.cmp(j)).map(|either| {
772 /// Right(_) => "Ku",
773 /// Both(_, _) => "KiKu"
777 /// itertools::assert_equal(ki_ku, vec!["KiKu", "Ki", "Ku", "Ki", "Ki"]);
780 fn merge_join_by
<J
, F
>(self, other
: J
, cmp_fn
: F
) -> MergeJoinBy
<Self, J
::IntoIter
, F
>
781 where J
: IntoIterator
,
782 F
: FnMut(&Self::Item
, &J
::Item
) -> std
::cmp
::Ordering
,
785 merge_join_by(self, other
, cmp_fn
)
789 /// Return an iterator adaptor that flattens an iterator of iterators by
790 /// merging them in ascending order.
792 /// If all base iterators are sorted (ascending), the result is sorted.
794 /// Iterator element type is `Self::Item`.
797 /// use itertools::Itertools;
799 /// let a = (0..6).step(3);
800 /// let b = (1..6).step(3);
801 /// let c = (2..6).step(3);
802 /// let it = vec![a, b, c].into_iter().kmerge();
803 /// itertools::assert_equal(it, vec![0, 1, 2, 3, 4, 5]);
805 #[cfg(feature = "use_std")]
806 fn kmerge(self) -> KMerge
<<Self::Item
as IntoIterator
>::IntoIter
>
808 Self::Item
: IntoIterator
,
809 <Self::Item
as IntoIterator
>::Item
: PartialOrd
,
814 /// Return an iterator adaptor that flattens an iterator of iterators by
815 /// merging them according to the given closure.
817 /// The closure `first` is called with two elements *a*, *b* and should
818 /// return `true` if *a* is ordered before *b*.
820 /// If all base iterators are sorted according to `first`, the result is
823 /// Iterator element type is `Self::Item`.
826 /// use itertools::Itertools;
828 /// let a = vec![-1f64, 2., 3., -5., 6., -7.];
829 /// let b = vec![0., 2., -4.];
830 /// let mut it = vec![a, b].into_iter().kmerge_by(|a, b| a.abs() < b.abs());
831 /// assert_eq!(it.next(), Some(0.));
832 /// assert_eq!(it.last(), Some(-7.));
834 #[cfg(feature = "use_std")]
835 fn kmerge_by
<F
>(self, first
: F
)
836 -> KMergeBy
<<Self::Item
as IntoIterator
>::IntoIter
, F
>
838 Self::Item
: IntoIterator
,
839 F
: FnMut(&<Self::Item
as IntoIterator
>::Item
,
840 &<Self::Item
as IntoIterator
>::Item
) -> bool
842 kmerge_by(self, first
)
845 /// Return an iterator adaptor that iterates over the cartesian product of
846 /// the element sets of two iterators `self` and `J`.
848 /// Iterator element type is `(Self::Item, J::Item)`.
851 /// use itertools::Itertools;
853 /// let it = (0..2).cartesian_product("αβ".chars());
854 /// itertools::assert_equal(it, vec![(0, 'α'), (0, 'β'), (1, 'α'), (1, 'β')]);
856 fn cartesian_product
<J
>(self, other
: J
) -> Product
<Self, J
::IntoIter
>
862 adaptors
::cartesian_product(self, other
.into_iter())
865 /// Return an iterator adaptor that iterates over the cartesian product of
866 /// all subiterators returned by meta-iterator `self`.
868 /// All provided iterators must yield the same `Item` type. To generate
869 /// the product of iterators yielding multiple types, use the
870 /// [`iproduct`](macro.iproduct.html) macro instead.
873 /// The iterator element type is `Vec<T>`, where `T` is the iterator element
874 /// of the subiterators.
877 /// use itertools::Itertools;
878 /// let mut multi_prod = (0..3).map(|i| (i * 2)..(i * 2 + 2))
879 /// .multi_cartesian_product();
880 /// assert_eq!(multi_prod.next(), Some(vec![0, 2, 4]));
881 /// assert_eq!(multi_prod.next(), Some(vec![0, 2, 5]));
882 /// assert_eq!(multi_prod.next(), Some(vec![0, 3, 4]));
883 /// assert_eq!(multi_prod.next(), Some(vec![0, 3, 5]));
884 /// assert_eq!(multi_prod.next(), Some(vec![1, 2, 4]));
885 /// assert_eq!(multi_prod.next(), Some(vec![1, 2, 5]));
886 /// assert_eq!(multi_prod.next(), Some(vec![1, 3, 4]));
887 /// assert_eq!(multi_prod.next(), Some(vec![1, 3, 5]));
888 /// assert_eq!(multi_prod.next(), None);
890 #[cfg(feature = "use_std")]
891 fn multi_cartesian_product(self) -> MultiProduct
<<Self::Item
as IntoIterator
>::IntoIter
>
892 where Self: Iterator
+ Sized
,
893 Self::Item
: IntoIterator
,
894 <Self::Item
as IntoIterator
>::IntoIter
: Clone
,
895 <Self::Item
as IntoIterator
>::Item
: Clone
897 adaptors
::multi_cartesian_product(self)
900 /// Return an iterator adaptor that uses the passed-in closure to
901 /// optionally merge together consecutive elements.
903 /// The closure `f` is passed two elements, `previous` and `current` and may
904 /// return either (1) `Ok(combined)` to merge the two values or
905 /// (2) `Err((previous', current'))` to indicate they can't be merged.
906 /// In (2), the value `previous'` is emitted by the iterator.
907 /// Either (1) `combined` or (2) `current'` becomes the previous value
908 /// when coalesce continues with the next pair of elements to merge. The
909 /// value that remains at the end is also emitted by the iterator.
911 /// Iterator element type is `Self::Item`.
913 /// This iterator is *fused*.
916 /// use itertools::Itertools;
918 /// // sum same-sign runs together
919 /// let data = vec![-1., -2., -3., 3., 1., 0., -1.];
920 /// itertools::assert_equal(data.into_iter().coalesce(|x, y|
921 /// if (x >= 0.) == (y >= 0.) {
926 /// vec![-6., 4., -1.]);
928 fn coalesce
<F
>(self, f
: F
) -> Coalesce
<Self, F
>
930 F
: FnMut(Self::Item
, Self::Item
)
931 -> Result
<Self::Item
, (Self::Item
, Self::Item
)>
933 adaptors
::coalesce(self, f
)
936 /// Remove duplicates from sections of consecutive identical elements.
937 /// If the iterator is sorted, all elements will be unique.
939 /// Iterator element type is `Self::Item`.
941 /// This iterator is *fused*.
944 /// use itertools::Itertools;
946 /// let data = vec![1., 1., 2., 3., 3., 2., 2.];
947 /// itertools::assert_equal(data.into_iter().dedup(),
948 /// vec![1., 2., 3., 2.]);
950 fn dedup(self) -> Dedup
<Self>
952 Self::Item
: PartialEq
,
954 adaptors
::dedup(self)
957 /// Return an iterator adaptor that filters out elements that have
958 /// already been produced once during the iteration. Duplicates
959 /// are detected using hash and equality.
961 /// Clones of visited elements are stored in a hash set in the
965 /// use itertools::Itertools;
967 /// let data = vec![10, 20, 30, 20, 40, 10, 50];
968 /// itertools::assert_equal(data.into_iter().unique(),
969 /// vec![10, 20, 30, 40, 50]);
971 #[cfg(feature = "use_std")]
972 fn unique(self) -> Unique
<Self>
974 Self::Item
: Clone
+ Eq
+ Hash
976 unique_impl
::unique(self)
979 /// Return an iterator adaptor that filters out elements that have
980 /// already been produced once during the iteration.
982 /// Duplicates are detected by comparing the key they map to
983 /// with the keying function `f` by hash and equality.
984 /// The keys are stored in a hash set in the iterator.
987 /// use itertools::Itertools;
989 /// let data = vec!["a", "bb", "aa", "c", "ccc"];
990 /// itertools::assert_equal(data.into_iter().unique_by(|s| s.len()),
991 /// vec!["a", "bb", "ccc"]);
993 #[cfg(feature = "use_std")]
994 fn unique_by
<V
, F
>(self, f
: F
) -> UniqueBy
<Self, V
, F
>
997 F
: FnMut(&Self::Item
) -> V
999 unique_impl
::unique_by(self, f
)
1002 /// Return an iterator adaptor that borrows from this iterator and
1003 /// takes items while the closure `accept` returns `true`.
1005 /// This adaptor can only be used on iterators that implement `PeekingNext`
1006 /// like `.peekable()`, `put_back` and a few other collection iterators.
1008 /// The last and rejected element (first `false`) is still available when
1009 /// `peeking_take_while` is done.
1012 /// See also [`.take_while_ref()`](#method.take_while_ref)
1013 /// which is a similar adaptor.
1014 fn peeking_take_while
<F
>(&mut self, accept
: F
) -> PeekingTakeWhile
<Self, F
>
1015 where Self: Sized
+ PeekingNext
,
1016 F
: FnMut(&Self::Item
) -> bool
,
1018 peeking_take_while
::peeking_take_while(self, accept
)
1021 /// Return an iterator adaptor that borrows from a `Clone`-able iterator
1022 /// to only pick off elements while the predicate `accept` returns `true`.
1024 /// It uses the `Clone` trait to restore the original iterator so that the
1025 /// last and rejected element (first `false`) is still available when
1026 /// `take_while_ref` is done.
1029 /// use itertools::Itertools;
1031 /// let mut hexadecimals = "0123456789abcdef".chars();
1033 /// let decimals = hexadecimals.take_while_ref(|c| c.is_numeric())
1034 /// .collect::<String>();
1035 /// assert_eq!(decimals, "0123456789");
1036 /// assert_eq!(hexadecimals.next(), Some('a'));
1039 fn take_while_ref
<F
>(&mut self, accept
: F
) -> TakeWhileRef
<Self, F
>
1041 F
: FnMut(&Self::Item
) -> bool
1043 adaptors
::take_while_ref(self, accept
)
1046 /// Return an iterator adaptor that filters `Option<A>` iterator elements
1047 /// and produces `A`. Stops on the first `None` encountered.
1049 /// Iterator element type is `A`, the unwrapped element.
1052 /// use itertools::Itertools;
1054 /// // List all hexadecimal digits
1055 /// itertools::assert_equal(
1056 /// (0..).map(|i| std::char::from_digit(i, 16)).while_some(),
1057 /// "0123456789abcdef".chars());
1060 fn while_some
<A
>(self) -> WhileSome
<Self>
1061 where Self: Sized
+ Iterator
<Item
= Option
<A
>>
1063 adaptors
::while_some(self)
1066 /// Return an iterator adaptor that iterates over the combinations of the
1067 /// elements from an iterator.
1069 /// Iterator element can be any homogeneous tuple of type `Self::Item` with
1073 /// use itertools::Itertools;
1075 /// let mut v = Vec::new();
1076 /// for (a, b) in (1..5).tuple_combinations() {
1079 /// assert_eq!(v, vec![(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]);
1081 /// let mut it = (1..5).tuple_combinations();
1082 /// assert_eq!(Some((1, 2, 3)), it.next());
1083 /// assert_eq!(Some((1, 2, 4)), it.next());
1084 /// assert_eq!(Some((1, 3, 4)), it.next());
1085 /// assert_eq!(Some((2, 3, 4)), it.next());
1086 /// assert_eq!(None, it.next());
1088 /// // this requires a type hint
1089 /// let it = (1..5).tuple_combinations::<(_, _, _)>();
1090 /// itertools::assert_equal(it, vec![(1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4)]);
1092 /// // you can also specify the complete type
1093 /// use itertools::TupleCombinations;
1094 /// use std::ops::Range;
1096 /// let it: TupleCombinations<Range<u32>, (u32, u32, u32)> = (1..5).tuple_combinations();
1097 /// itertools::assert_equal(it, vec![(1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4)]);
1099 fn tuple_combinations
<T
>(self) -> TupleCombinations
<Self, T
>
1100 where Self: Sized
+ Clone
,
1102 T
: adaptors
::HasCombination
<Self>,
1104 adaptors
::tuple_combinations(self)
1107 /// Return an iterator adaptor that iterates over the `n`-length combinations of
1108 /// the elements from an iterator.
1110 /// Iterator element type is `Vec<Self::Item>`. The iterator produces a new Vec per iteration,
1111 /// and clones the iterator elements.
1114 /// use itertools::Itertools;
1116 /// let it = (1..5).combinations(3);
1117 /// itertools::assert_equal(it, vec![
1124 #[cfg(feature = "use_std")]
1125 fn combinations(self, n
: usize) -> Combinations
<Self>
1129 combinations
::combinations(self, n
)
1132 /// Return an iterator adaptor that pads the sequence to a minimum length of
1133 /// `min` by filling missing elements using a closure `f`.
1135 /// Iterator element type is `Self::Item`.
1138 /// use itertools::Itertools;
1140 /// let it = (0..5).pad_using(10, |i| 2*i);
1141 /// itertools::assert_equal(it, vec![0, 1, 2, 3, 4, 10, 12, 14, 16, 18]);
1143 /// let it = (0..10).pad_using(5, |i| 2*i);
1144 /// itertools::assert_equal(it, vec![0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);
1146 /// let it = (0..5).pad_using(10, |i| 2*i).rev();
1147 /// itertools::assert_equal(it, vec![18, 16, 14, 12, 10, 4, 3, 2, 1, 0]);
1149 fn pad_using
<F
>(self, min
: usize, f
: F
) -> PadUsing
<Self, F
>
1151 F
: FnMut(usize) -> Self::Item
1153 pad_tail
::pad_using(self, min
, f
)
1156 /// Return an iterator adaptor that wraps each element in a `Position` to
1157 /// ease special-case handling of the first or last elements.
1159 /// Iterator element type is
1160 /// [`Position<Self::Item>`](enum.Position.html)
1163 /// use itertools::{Itertools, Position};
1165 /// let it = (0..4).with_position();
1166 /// itertools::assert_equal(it,
1167 /// vec![Position::First(0),
1168 /// Position::Middle(1),
1169 /// Position::Middle(2),
1170 /// Position::Last(3)]);
1172 /// let it = (0..1).with_position();
1173 /// itertools::assert_equal(it, vec![Position::Only(0)]);
1175 fn with_position(self) -> WithPosition
<Self>
1178 with_position
::with_position(self)
1181 /// Return an iterator adaptor that yields the indices of all elements
1182 /// satisfying a predicate, counted from the start of the iterator.
1184 /// Equivalent to `iter.enumerate().filter(|(_, v)| predicate(v)).map(|(i, _)| i)`.
1187 /// use itertools::Itertools;
1189 /// let data = vec![1, 2, 3, 3, 4, 6, 7, 9];
1190 /// itertools::assert_equal(data.iter().positions(|v| v % 2 == 0), vec![1, 4, 5]);
1192 /// itertools::assert_equal(data.iter().positions(|v| v % 2 == 1).rev(), vec![7, 6, 3, 2, 0]);
1194 fn positions
<P
>(self, predicate
: P
) -> Positions
<Self, P
>
1196 P
: FnMut(Self::Item
) -> bool
,
1198 adaptors
::positions(self, predicate
)
1201 /// Return an iterator adaptor that applies a mutating function
1202 /// to each element before yielding it.
1205 /// use itertools::Itertools;
1207 /// let input = vec![vec![1], vec![3, 2, 1]];
1208 /// let it = input.into_iter().update(|mut v| v.push(0));
1209 /// itertools::assert_equal(it, vec![vec![1, 0], vec![3, 2, 1, 0]]);
1211 fn update
<F
>(self, updater
: F
) -> Update
<Self, F
>
1213 F
: FnMut(&mut Self::Item
),
1215 adaptors
::update(self, updater
)
1218 // non-adaptor methods
1219 /// Advances the iterator and returns the next items grouped in a tuple of
1220 /// a specific size (up to 4).
1222 /// If there are enough elements to be grouped in a tuple, then the tuple is
1223 /// returned inside `Some`, otherwise `None` is returned.
1226 /// use itertools::Itertools;
1228 /// let mut iter = 1..5;
1230 /// assert_eq!(Some((1, 2)), iter.next_tuple());
1232 fn next_tuple
<T
>(&mut self) -> Option
<T
>
1233 where Self: Sized
+ Iterator
<Item
= T
::Item
>,
1234 T
: tuple_impl
::TupleCollect
1236 T
::collect_from_iter_no_buf(self)
1239 /// Collects all items from the iterator into a tuple of a specific size
1242 /// If the number of elements inside the iterator is **exactly** equal to
1243 /// the tuple size, then the tuple is returned inside `Some`, otherwise
1244 /// `None` is returned.
1247 /// use itertools::Itertools;
1249 /// let iter = 1..3;
1251 /// if let Some((x, y)) = iter.collect_tuple() {
1252 /// assert_eq!((x, y), (1, 2))
1254 /// panic!("Expected two elements")
1257 fn collect_tuple
<T
>(mut self) -> Option
<T
>
1258 where Self: Sized
+ Iterator
<Item
= T
::Item
>,
1259 T
: tuple_impl
::TupleCollect
1261 match self.next_tuple() {
1262 elt @
Some(_
) => match self.next() {
1271 /// Find the position and value of the first element satisfying a predicate.
1273 /// The iterator is not advanced past the first element found.
1276 /// use itertools::Itertools;
1278 /// let text = "Hα";
1279 /// assert_eq!(text.chars().find_position(|ch| ch.is_lowercase()), Some((1, 'α')));
1281 fn find_position
<P
>(&mut self, mut pred
: P
) -> Option
<(usize, Self::Item
)>
1282 where P
: FnMut(&Self::Item
) -> bool
1284 let mut index
= 0usize
;
1287 return Some((index
, elt
));
1294 /// Check whether all elements compare equal.
1296 /// Empty iterators are considered to have equal elements:
1299 /// use itertools::Itertools;
1301 /// let data = vec![1, 1, 1, 2, 2, 3, 3, 3, 4, 5, 5];
1302 /// assert!(!data.iter().all_equal());
1303 /// assert!(data[0..3].iter().all_equal());
1304 /// assert!(data[3..5].iter().all_equal());
1305 /// assert!(data[5..8].iter().all_equal());
1307 /// let data : Option<usize> = None;
1308 /// assert!(data.into_iter().all_equal());
1310 fn all_equal(&mut self) -> bool
1311 where Self::Item
: PartialEq
,
1313 self.dedup().nth(1).is_none()
1316 /// Consume the first `n` elements from the iterator eagerly,
1317 /// and return the same iterator again.
1319 /// It works similarly to *.skip(* `n` *)* except it is eager and
1320 /// preserves the iterator type.
1323 /// use itertools::Itertools;
1325 /// let mut iter = "αβγ".chars().dropping(2);
1326 /// itertools::assert_equal(iter, "γ".chars());
1329 /// *Fusing notes: if the iterator is exhausted by dropping,
1330 /// the result of calling `.next()` again depends on the iterator implementation.*
1331 fn dropping(mut self, n
: usize) -> Self
1340 /// Consume the last `n` elements from the iterator eagerly,
1341 /// and return the same iterator again.
1343 /// This is only possible on double ended iterators. `n` may be
1344 /// larger than the number of elements.
1346 /// Note: This method is eager, dropping the back elements immediately and
1347 /// preserves the iterator type.
1350 /// use itertools::Itertools;
1352 /// let init = vec![0, 3, 6, 9].into_iter().dropping_back(1);
1353 /// itertools::assert_equal(init, vec![0, 3, 6]);
1355 fn dropping_back(mut self, n
: usize) -> Self
1357 Self: DoubleEndedIterator
1360 (&mut self).rev().nth(n
- 1);
1365 /// Run the closure `f` eagerly on each element of the iterator.
1367 /// Consumes the iterator until its end.
1370 /// use std::sync::mpsc::channel;
1371 /// use itertools::Itertools;
1373 /// let (tx, rx) = channel();
1375 /// // use .foreach() to apply a function to each value -- sending it
1376 /// (0..5).map(|x| x * 2 + 1).foreach(|x| { tx.send(x).unwrap(); } );
1380 /// itertools::assert_equal(rx.iter(), vec![1, 3, 5, 7, 9]);
1382 #[deprecated(note="Use .for_each() instead", since="0.8")]
1383 fn foreach
<F
>(self, f
: F
)
1384 where F
: FnMut(Self::Item
),
1390 /// Combine all an iterator's elements into one element by using `Extend`.
1392 /// This combinator will extend the first item with each of the rest of the
1393 /// items of the iterator. If the iterator is empty, the default value of
1394 /// `I::Item` is returned.
1397 /// use itertools::Itertools;
1399 /// let input = vec![vec![1], vec![2, 3], vec![4, 5, 6]];
1400 /// assert_eq!(input.into_iter().concat(),
1401 /// vec![1, 2, 3, 4, 5, 6]);
1403 fn concat(self) -> Self::Item
1405 Self::Item
: Extend
<<<Self as Iterator
>::Item
as IntoIterator
>::Item
> + IntoIterator
+ Default
1410 /// `.collect_vec()` is simply a type specialization of `.collect()`,
1411 /// for convenience.
1412 #[cfg(feature = "use_std")]
1413 fn collect_vec(self) -> Vec
<Self::Item
>
1419 /// Assign to each reference in `self` from the `from` iterator,
1420 /// stopping at the shortest of the two iterators.
1422 /// The `from` iterator is queried for its next element before the `self`
1423 /// iterator, and if either is exhausted the method is done.
1425 /// Return the number of elements written.
1428 /// use itertools::Itertools;
1430 /// let mut xs = [0; 4];
1431 /// xs.iter_mut().set_from(1..);
1432 /// assert_eq!(xs, [1, 2, 3, 4]);
1435 fn set_from
<'a
, A
: 'a
, J
>(&mut self, from
: J
) -> usize
1436 where Self: Iterator
<Item
= &'a
mut A
>,
1437 J
: IntoIterator
<Item
= A
>
1443 Some(ptr
) => *ptr
= elt
,
1450 /// Combine all iterator elements into one String, seperated by `sep`.
1452 /// Use the `Display` implementation of each element.
1455 /// use itertools::Itertools;
1457 /// assert_eq!(["a", "b", "c"].iter().join(", "), "a, b, c");
1458 /// assert_eq!([1, 2, 3].iter().join(", "), "1, 2, 3");
1460 #[cfg(feature = "use_std")]
1461 fn join(&mut self, sep
: &str) -> String
1462 where Self::Item
: std
::fmt
::Display
1465 None
=> String
::new(),
1466 Some(first_elt
) => {
1467 // estimate lower bound of capacity needed
1468 let (lower
, _
) = self.size_hint();
1469 let mut result
= String
::with_capacity(sep
.len() * lower
);
1470 write
!(&mut result
, "{}", first_elt
).unwrap();
1472 result
.push_str(sep
);
1473 write
!(&mut result
, "{}", elt
).unwrap();
1480 /// Format all iterator elements, separated by `sep`.
1482 /// All elements are formatted (any formatting trait)
1483 /// with `sep` inserted between each element.
1485 /// **Panics** if the formatter helper is formatted more than once.
1488 /// use itertools::Itertools;
1490 /// let data = [1.1, 2.71828, -3.];
1492 /// format!("{:.2}", data.iter().format(", ")),
1493 /// "1.10, 2.72, -3.00");
1495 fn format(self, sep
: &str) -> Format
<Self>
1498 format
::new_format_default(self, sep
)
1501 /// Format all iterator elements, separated by `sep`.
1503 /// This is a customizable version of `.format()`.
1505 /// The supplied closure `format` is called once per iterator element,
1506 /// with two arguments: the element and a callback that takes a
1507 /// `&Display` value, i.e. any reference to type that implements `Display`.
1509 /// Using `&format_args!(...)` is the most versatile way to apply custom
1510 /// element formatting. The callback can be called multiple times if needed.
1512 /// **Panics** if the formatter helper is formatted more than once.
1515 /// use itertools::Itertools;
1517 /// let data = [1.1, 2.71828, -3.];
1518 /// let data_formatter = data.iter().format_with(", ", |elt, f| f(&format_args!("{:.2}", elt)));
1519 /// assert_eq!(format!("{}", data_formatter),
1520 /// "1.10, 2.72, -3.00");
1522 /// // .format_with() is recursively composable
1523 /// let matrix = [[1., 2., 3.],
1525 /// let matrix_formatter = matrix.iter().format_with("\n", |row, f| {
1526 /// f(&row.iter().format_with(", ", |elt, g| g(&elt)))
1528 /// assert_eq!(format!("{}", matrix_formatter),
1529 /// "1, 2, 3\n4, 5, 6");
1533 fn format_with
<F
>(self, sep
: &str, format
: F
) -> FormatWith
<Self, F
>
1535 F
: FnMut(Self::Item
, &mut FnMut(&fmt
::Display
) -> fmt
::Result
) -> fmt
::Result
,
1537 format
::new_format(self, sep
, format
)
1540 /// Fold `Result` values from an iterator.
1542 /// Only `Ok` values are folded. If no error is encountered, the folded
1543 /// value is returned inside `Ok`. Otherwise, the operation terminates
1544 /// and returns the first `Err` value it encounters. No iterator elements are
1545 /// consumed after the first error.
1547 /// The first accumulator value is the `start` parameter.
1548 /// Each iteration passes the accumulator value and the next value inside `Ok`
1549 /// to the fold function `f` and its return value becomes the new accumulator value.
1551 /// For example the sequence *Ok(1), Ok(2), Ok(3)* will result in a
1552 /// computation like this:
1555 /// let mut accum = start;
1556 /// accum = f(accum, 1);
1557 /// accum = f(accum, 2);
1558 /// accum = f(accum, 3);
1561 /// With a `start` value of 0 and an addition as folding function,
1562 /// this effetively results in *((0 + 1) + 2) + 3*
1565 /// use std::ops::Add;
1566 /// use itertools::Itertools;
1568 /// let values = [1, 2, -2, -1, 2, 1];
1571 /// .map(Ok::<_, ()>)
1572 /// .fold_results(0, Add::add),
1577 /// .map(|&x| if x >= 0 { Ok(x) } else { Err("Negative number") })
1578 /// .fold_results(0, Add::add)
1582 fn fold_results
<A
, E
, B
, F
>(&mut self, mut start
: B
, mut f
: F
) -> Result
<B
, E
>
1583 where Self: Iterator
<Item
= Result
<A
, E
>>,
1588 Ok(v
) => start
= f(start
, v
),
1589 Err(u
) => return Err(u
),
1595 /// Fold `Option` values from an iterator.
1597 /// Only `Some` values are folded. If no `None` is encountered, the folded
1598 /// value is returned inside `Some`. Otherwise, the operation terminates
1599 /// and returns `None`. No iterator elements are consumed after the `None`.
1601 /// This is the `Option` equivalent to `fold_results`.
1604 /// use std::ops::Add;
1605 /// use itertools::Itertools;
1607 /// let mut values = vec![Some(1), Some(2), Some(-2)].into_iter();
1608 /// assert_eq!(values.fold_options(5, Add::add), Some(5 + 1 + 2 - 2));
1610 /// let mut more_values = vec![Some(2), None, Some(0)].into_iter();
1611 /// assert!(more_values.fold_options(0, Add::add).is_none());
1612 /// assert_eq!(more_values.next().unwrap(), Some(0));
1614 fn fold_options
<A
, B
, F
>(&mut self, mut start
: B
, mut f
: F
) -> Option
<B
>
1615 where Self: Iterator
<Item
= Option
<A
>>,
1620 Some(v
) => start
= f(start
, v
),
1621 None
=> return None
,
1627 /// Accumulator of the elements in the iterator.
1629 /// Like `.fold()`, without a base case. If the iterator is
1630 /// empty, return `None`. With just one element, return it.
1631 /// Otherwise elements are accumulated in sequence using the closure `f`.
1634 /// use itertools::Itertools;
1636 /// assert_eq!((0..10).fold1(|x, y| x + y).unwrap_or(0), 45);
1637 /// assert_eq!((0..0).fold1(|x, y| x * y), None);
1639 fn fold1
<F
>(mut self, f
: F
) -> Option
<Self::Item
>
1640 where F
: FnMut(Self::Item
, Self::Item
) -> Self::Item
,
1643 self.next().map(move |x
| self.fold(x
, f
))
1646 /// Accumulate the elements in the iterator in a tree-like manner.
1648 /// You can think of it as, while there's more than one item, repeatedly
1649 /// combining adjacent items. It does so in bottom-up-merge-sort order,
1650 /// however, so that it needs only logarithmic stack space.
1652 /// This produces a call tree like the following (where the calls under
1653 /// an item are done after reading that item):
1665 /// Which, for non-associative functions, will typically produce a different
1666 /// result than the linear call tree used by `fold1`:
1674 /// If `f` is associative, prefer the normal `fold1` instead.
1677 /// use itertools::Itertools;
1679 /// // The same tree as above
1680 /// let num_strings = (1..8).map(|x| x.to_string());
1681 /// assert_eq!(num_strings.tree_fold1(|x, y| format!("f({}, {})", x, y)),
1682 /// Some(String::from("f(f(f(1, 2), f(3, 4)), f(f(5, 6), 7))")));
1684 /// // Like fold1, an empty iterator produces None
1685 /// assert_eq!((0..0).tree_fold1(|x, y| x * y), None);
1687 /// // tree_fold1 matches fold1 for associative operations...
1688 /// assert_eq!((0..10).tree_fold1(|x, y| x + y),
1689 /// (0..10).fold1(|x, y| x + y));
1690 /// // ...but not for non-associative ones
1691 /// assert!((0..10).tree_fold1(|x, y| x - y)
1692 /// != (0..10).fold1(|x, y| x - y));
1694 // FIXME: If minver changes to >= 1.13, use `assert_ne!` in the doctest.
1695 fn tree_fold1
<F
>(mut self, mut f
: F
) -> Option
<Self::Item
>
1696 where F
: FnMut(Self::Item
, Self::Item
) -> Self::Item
,
1699 type State
<T
> = Result
<T
, Option
<T
>>;
1701 fn inner0
<T
, II
, FF
>(it
: &mut II
, f
: &mut FF
) -> State
<T
>
1703 II
: Iterator
<Item
= T
>,
1704 FF
: FnMut(T
, T
) -> T
1706 // This function could be replaced with `it.next().ok_or(None)`,
1707 // but half the useful tree_fold1 work is combining adjacent items,
1708 // so put that in a form that LLVM is more likely to optimize well.
1711 if let Some(v
) = it
.next() { v }
1712 else { return Err(None) }
;
1714 if let Some(v
) = it
.next() { v }
1715 else { return Err(Some(a)) }
;
1719 fn inner
<T
, II
, FF
>(stop
: usize, it
: &mut II
, f
: &mut FF
) -> State
<T
>
1721 II
: Iterator
<Item
= T
>,
1722 FF
: FnMut(T
, T
) -> T
1724 let mut x
= try
!(inner0(it
, f
));
1725 for height
in 0..stop
{
1726 // Try to get another tree the same size with which to combine it,
1727 // creating a new tree that's twice as big for next time around.
1732 inner(height
, it
, f
)
1735 Ok(y
) => x
= f(x
, y
),
1737 // If we ran out of items, combine whatever we did manage
1738 // to get. It's better combined with the current value
1739 // than something in a parent frame, because the tree in
1740 // the parent is always as least as big as this one.
1741 Err(None
) => return Err(Some(x
)),
1742 Err(Some(y
)) => return Err(Some(f(x
, y
))),
1748 match inner(usize::max_value(), &mut self, &mut f
) {
1750 _
=> unreachable
!(),
1754 /// An iterator method that applies a function, producing a single, final value.
1756 /// `fold_while()` is basically equivalent to `fold()` but with additional support for
1757 /// early exit via short-circuiting.
1760 /// use itertools::Itertools;
1761 /// use itertools::FoldWhile::{Continue, Done};
1763 /// let numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
1765 /// let mut result = 0;
1768 /// for i in &numbers {
1772 /// result = result + i;
1776 /// let result2 = numbers.iter().fold(0, |acc, x| {
1777 /// if *x > 5 { acc } else { acc + x }
1781 /// let result3 = numbers.iter().fold_while(0, |acc, x| {
1782 /// if *x > 5 { Done(acc) } else { Continue(acc + x) }
1783 /// }).into_inner();
1785 /// // they're the same
1786 /// assert_eq!(result, result2);
1787 /// assert_eq!(result2, result3);
1790 /// The big difference between the computations of `result2` and `result3` is that while
1791 /// `fold()` called the provided closure for every item of the callee iterator,
1792 /// `fold_while()` actually stopped iterating as soon as it encountered `Fold::Done(_)`.
1793 #[deprecated(note="Use .try_fold() instead", since="0.8")]
1794 fn fold_while
<B
, F
>(&mut self, init
: B
, mut f
: F
) -> FoldWhile
<B
>
1796 F
: FnMut(B
, Self::Item
) -> FoldWhile
<B
>
1799 while let Some(item
) = self.next() {
1800 match f(acc
, item
) {
1801 FoldWhile
::Continue(res
) => acc
= res
,
1802 res @ FoldWhile
::Done(_
) => return res
,
1805 FoldWhile
::Continue(acc
)
1808 /// Sort all iterator elements into a new iterator in ascending order.
1810 /// **Note:** This consumes the entire iterator, uses the
1811 /// `slice::sort()` method and returns the result as a new
1812 /// iterator that owns its elements.
1814 /// The sorted iterator, if directly collected to a `Vec`, is converted
1815 /// without any extra copying or allocation cost.
1818 /// use itertools::Itertools;
1820 /// // sort the letters of the text in ascending order
1821 /// let text = "bdacfe";
1822 /// itertools::assert_equal(text.chars().sorted(),
1823 /// "abcdef".chars());
1825 #[cfg(feature = "use_std")]
1826 fn sorted(self) -> VecIntoIter
<Self::Item
>
1830 // Use .sort() directly since it is not quite identical with
1831 // .sort_by(Ord::cmp)
1832 let mut v
= Vec
::from_iter(self);
1837 /// Sort all iterator elements into a new iterator in ascending order.
1839 /// **Note:** This consumes the entire iterator, uses the
1840 /// `slice::sort_by()` method and returns the result as a new
1841 /// iterator that owns its elements.
1843 /// The sorted iterator, if directly collected to a `Vec`, is converted
1844 /// without any extra copying or allocation cost.
1847 /// use itertools::Itertools;
1849 /// // sort people in descending order by age
1850 /// let people = vec![("Jane", 20), ("John", 18), ("Jill", 30), ("Jack", 27)];
1852 /// let oldest_people_first = people
1854 /// .sorted_by(|a, b| Ord::cmp(&b.1, &a.1))
1855 /// .map(|(person, _age)| person);
1857 /// itertools::assert_equal(oldest_people_first,
1858 /// vec!["Jill", "Jack", "Jane", "John"]);
1860 #[cfg(feature = "use_std")]
1861 fn sorted_by
<F
>(self, cmp
: F
) -> VecIntoIter
<Self::Item
>
1863 F
: FnMut(&Self::Item
, &Self::Item
) -> Ordering
,
1865 let mut v
= Vec
::from_iter(self);
1870 /// Sort all iterator elements into a new iterator in ascending order.
1872 /// **Note:** This consumes the entire iterator, uses the
1873 /// `slice::sort_by_key()` method and returns the result as a new
1874 /// iterator that owns its elements.
1876 /// The sorted iterator, if directly collected to a `Vec`, is converted
1877 /// without any extra copying or allocation cost.
1880 /// use itertools::Itertools;
1882 /// // sort people in descending order by age
1883 /// let people = vec![("Jane", 20), ("John", 18), ("Jill", 30), ("Jack", 27)];
1885 /// let oldest_people_first = people
1887 /// .sorted_by_key(|x| -x.1)
1888 /// .map(|(person, _age)| person);
1890 /// itertools::assert_equal(oldest_people_first,
1891 /// vec!["Jill", "Jack", "Jane", "John"]);
1893 #[cfg(feature = "use_std")]
1894 fn sorted_by_key
<K
, F
>(self, f
: F
) -> VecIntoIter
<Self::Item
>
1897 F
: FnMut(&Self::Item
) -> K
,
1899 let mut v
= Vec
::from_iter(self);
1904 /// Collect all iterator elements into one of two
1905 /// partitions. Unlike `Iterator::partition`, each partition may
1906 /// have a distinct type.
1909 /// use itertools::{Itertools, Either};
1911 /// let successes_and_failures = vec![Ok(1), Err(false), Err(true), Ok(2)];
1913 /// let (successes, failures): (Vec<_>, Vec<_>) = successes_and_failures
1915 /// .partition_map(|r| {
1917 /// Ok(v) => Either::Left(v),
1918 /// Err(v) => Either::Right(v),
1922 /// assert_eq!(successes, [1, 2]);
1923 /// assert_eq!(failures, [false, true]);
1925 fn partition_map
<A
, B
, F
, L
, R
>(self, predicate
: F
) -> (A
, B
)
1927 F
: Fn(Self::Item
) -> Either
<L
, R
>,
1928 A
: Default
+ Extend
<L
>,
1929 B
: Default
+ Extend
<R
>,
1931 let mut left
= A
::default();
1932 let mut right
= B
::default();
1935 match predicate(val
) {
1936 Either
::Left(v
) => left
.extend(Some(v
)),
1937 Either
::Right(v
) => right
.extend(Some(v
)),
1944 /// Return a `HashMap` of keys mapped to `Vec`s of values. Keys and values
1945 /// are taken from `(Key, Value)` tuple pairs yielded by the input iterator.
1948 /// use itertools::Itertools;
1950 /// let data = vec![(0, 10), (2, 12), (3, 13), (0, 20), (3, 33), (2, 42)];
1951 /// let lookup = data.into_iter().into_group_map();
1953 /// assert_eq!(lookup[&0], vec![10, 20]);
1954 /// assert_eq!(lookup.get(&1), None);
1955 /// assert_eq!(lookup[&2], vec![12, 42]);
1956 /// assert_eq!(lookup[&3], vec![13, 33]);
1958 #[cfg(feature = "use_std")]
1959 fn into_group_map
<K
, V
>(self) -> HashMap
<K
, Vec
<V
>>
1960 where Self: Iterator
<Item
=(K
, V
)> + Sized
,
1963 group_map
::into_group_map(self)
1966 /// Return the minimum and maximum elements in the iterator.
1968 /// The return type `MinMaxResult` is an enum of three variants:
1970 /// - `NoElements` if the iterator is empty.
1971 /// - `OneElement(x)` if the iterator has exactly one element.
1972 /// - `MinMax(x, y)` is returned otherwise, where `x <= y`. Two
1973 /// values are equal if and only if there is more than one
1974 /// element in the iterator and all elements are equal.
1976 /// On an iterator of length `n`, `minmax` does `1.5 * n` comparisons,
1977 /// and so is faster than calling `min` and `max` separately which does
1978 /// `2 * n` comparisons.
1983 /// use itertools::Itertools;
1984 /// use itertools::MinMaxResult::{NoElements, OneElement, MinMax};
1986 /// let a: [i32; 0] = [];
1987 /// assert_eq!(a.iter().minmax(), NoElements);
1990 /// assert_eq!(a.iter().minmax(), OneElement(&1));
1992 /// let a = [1, 2, 3, 4, 5];
1993 /// assert_eq!(a.iter().minmax(), MinMax(&1, &5));
1995 /// let a = [1, 1, 1, 1];
1996 /// assert_eq!(a.iter().minmax(), MinMax(&1, &1));
1999 /// The elements can be floats but no particular result is guaranteed
2000 /// if an element is NaN.
2001 fn minmax(self) -> MinMaxResult
<Self::Item
>
2002 where Self: Sized
, Self::Item
: PartialOrd
2004 minmax
::minmax_impl(self, |_
| (), |x
, y
, _
, _
| x
< y
)
2007 /// Return the minimum and maximum element of an iterator, as determined by
2008 /// the specified function.
2010 /// The return value is a variant of `MinMaxResult` like for `minmax()`.
2012 /// For the minimum, the first minimal element is returned. For the maximum,
2013 /// the last maximal element wins. This matches the behavior of the standard
2014 /// `Iterator::min()` and `Iterator::max()` methods.
2016 /// The keys can be floats but no particular result is guaranteed
2017 /// if a key is NaN.
2018 fn minmax_by_key
<K
, F
>(self, key
: F
) -> MinMaxResult
<Self::Item
>
2019 where Self: Sized
, K
: PartialOrd
, F
: FnMut(&Self::Item
) -> K
2021 minmax
::minmax_impl(self, key
, |_
, _
, xk
, yk
| xk
< yk
)
2024 /// Return the minimum and maximum element of an iterator, as determined by
2025 /// the specified comparison function.
2027 /// The return value is a variant of `MinMaxResult` like for `minmax()`.
2029 /// For the minimum, the first minimal element is returned. For the maximum,
2030 /// the last maximal element wins. This matches the behavior of the standard
2031 /// `Iterator::min()` and `Iterator::max()` methods.
2032 fn minmax_by
<F
>(self, mut compare
: F
) -> MinMaxResult
<Self::Item
>
2033 where Self: Sized
, F
: FnMut(&Self::Item
, &Self::Item
) -> Ordering
2035 minmax
::minmax_impl(
2038 |x
, y
, _
, _
| Ordering
::Less
== compare(x
, y
)
2043 impl<T
: ?Sized
> Itertools
for T
where T
: Iterator { }
2045 /// Return `true` if both iterables produce equal sequences
2046 /// (elements pairwise equal and sequences of the same length),
2047 /// `false` otherwise.
2049 /// This is an `IntoIterator` enabled function that is similar to the standard
2050 /// library method `Iterator::eq`.
2053 /// assert!(itertools::equal(vec![1, 2, 3], 1..4));
2054 /// assert!(!itertools::equal(&[0, 0], &[0, 0, 0]));
2056 pub fn equal
<I
, J
>(a
: I
, b
: J
) -> bool
2057 where I
: IntoIterator
,
2059 I
::Item
: PartialEq
<J
::Item
>
2061 let mut ia
= a
.into_iter();
2062 let mut ib
= b
.into_iter();
2065 Some(x
) => match ib
.next() {
2066 Some(y
) => if x
!= y { return false; }
,
2067 None
=> return false,
2069 None
=> return ib
.next().is_none()
2074 /// Assert that two iterables produce equal sequences, with the same
2075 /// semantics as *equal(a, b)*.
2077 /// **Panics** on assertion failure with a message that shows the
2078 /// two iteration elements.
2081 /// assert_equal("exceed".split('c'), "excess".split('c'));
2082 /// // ^PANIC: panicked at 'Failed assertion Some("eed") == Some("ess") for iteration 1',
2084 pub fn assert_equal
<I
, J
>(a
: I
, b
: J
)
2085 where I
: IntoIterator
,
2087 I
::Item
: fmt
::Debug
+ PartialEq
<J
::Item
>,
2088 J
::Item
: fmt
::Debug
,
2090 let mut ia
= a
.into_iter();
2091 let mut ib
= b
.into_iter();
2094 match (ia
.next(), ib
.next()) {
2095 (None
, None
) => return,
2097 let equal
= match (&a
, &b
) {
2098 (&Some(ref a
), &Some(ref b
)) => a
== b
,
2101 assert
!(equal
, "Failed assertion {a:?} == {b:?} for iteration {i}",
2109 /// Partition a sequence using predicate `pred` so that elements
2110 /// that map to `true` are placed before elements which map to `false`.
2112 /// The order within the partitions is arbitrary.
2114 /// Return the index of the split point.
2117 /// use itertools::partition;
2119 /// # // use repeated numbers to not promise any ordering
2120 /// let mut data = [7, 1, 1, 7, 1, 1, 7];
2121 /// let split_index = partition(&mut data, |elt| *elt >= 3);
2123 /// assert_eq!(data, [7, 7, 7, 1, 1, 1, 1]);
2124 /// assert_eq!(split_index, 3);
2126 pub fn partition
<'a
, A
: 'a
, I
, F
>(iter
: I
, mut pred
: F
) -> usize
2127 where I
: IntoIterator
<Item
= &'a
mut A
>,
2128 I
::IntoIter
: DoubleEndedIterator
,
2129 F
: FnMut(&A
) -> bool
2131 let mut split_index
= 0;
2132 let mut iter
= iter
.into_iter();
2133 'main
: while let Some(front
) = iter
.next() {
2136 match iter
.next_back() {
2137 Some(back
) => if pred(back
) {
2138 std
::mem
::swap(front
, back
);
2141 None
=> break 'main
,
2150 /// An enum used for controlling the execution of `.fold_while()`.
2152 /// See [`.fold_while()`](trait.Itertools.html#method.fold_while) for more information.
2153 #[derive(Copy, Clone, Debug, Eq, PartialEq)]
2154 pub enum FoldWhile
<T
> {
2155 /// Continue folding with this value
2157 /// Fold is complete and will return this value
2161 impl<T
> FoldWhile
<T
> {
2162 /// Return the value in the continue or done.
2163 pub fn into_inner(self) -> T
{
2165 FoldWhile
::Continue(x
) | FoldWhile
::Done(x
) => x
,
2169 /// Return true if `self` is `Done`, false if it is `Continue`.
2170 pub fn is_done(&self) -> bool
{
2172 FoldWhile
::Continue(_
) => false,
2173 FoldWhile
::Done(_
) => true,