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](./trait.Itertools.html):
9 //!
10 //! ```
11 //! use itertools::Itertools;
12 //! ```
13 //!
14 //! Now, new methods like [`interleave`](./trait.Itertools.html#method.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 //!
47 //! [`Iterator`]: https://doc.rust-lang.org/std/iter/trait.Iterator.html
48 #![doc(html_root_url="https://docs.rs/itertools/0.8/")]
49
50 #[cfg(not(feature = "use_std"))]
51 extern crate core as std;
52
53 pub use either::Either;
54
55 #[cfg(feature = "use_std")]
56 use std::collections::HashMap;
57 use std::iter::{IntoIterator, once};
58 use std::cmp::Ordering;
59 use std::fmt;
60 #[cfg(feature = "use_std")]
61 use std::hash::Hash;
62 #[cfg(feature = "use_std")]
63 use std::fmt::Write;
64 #[cfg(feature = "use_std")]
65 type VecIntoIter<T> = ::std::vec::IntoIter<T>;
66 #[cfg(feature = "use_std")]
67 use std::iter::FromIterator;
68
69 #[macro_use]
70 mod impl_macros;
71
72 // for compatibility with no std and macros
73 #[doc(hidden)]
74 pub use std::iter as __std_iter;
75
76 /// The concrete iterator types.
77 pub mod structs {
78 pub use crate::adaptors::{
79 Dedup,
80 DedupBy,
81 Interleave,
82 InterleaveShortest,
83 Product,
84 PutBack,
85 Batching,
86 MapInto,
87 MapResults,
88 Merge,
89 MergeBy,
90 TakeWhileRef,
91 WhileSome,
92 Coalesce,
93 TupleCombinations,
94 Positions,
95 Update,
96 };
97 #[allow(deprecated)]
98 pub use crate::adaptors::Step;
99 #[cfg(feature = "use_std")]
100 pub use crate::adaptors::MultiProduct;
101 #[cfg(feature = "use_std")]
102 pub use crate::combinations::Combinations;
103 #[cfg(feature = "use_std")]
104 pub use crate::combinations_with_replacement::CombinationsWithReplacement;
105 pub use crate::cons_tuples_impl::ConsTuples;
106 pub use crate::exactly_one_err::ExactlyOneError;
107 pub use crate::format::{Format, FormatWith};
108 #[cfg(feature = "use_std")]
109 pub use crate::groupbylazy::{IntoChunks, Chunk, Chunks, GroupBy, Group, Groups};
110 pub use crate::intersperse::Intersperse;
111 #[cfg(feature = "use_std")]
112 pub use crate::kmerge_impl::{KMerge, KMergeBy};
113 pub use crate::merge_join::MergeJoinBy;
114 #[cfg(feature = "use_std")]
115 pub use crate::multipeek_impl::MultiPeek;
116 pub use crate::pad_tail::PadUsing;
117 pub use crate::peeking_take_while::PeekingTakeWhile;
118 #[cfg(feature = "use_std")]
119 pub use crate::permutations::Permutations;
120 pub use crate::process_results_impl::ProcessResults;
121 #[cfg(feature = "use_std")]
122 pub use crate::put_back_n_impl::PutBackN;
123 #[cfg(feature = "use_std")]
124 pub use crate::rciter_impl::RcIter;
125 pub use crate::repeatn::RepeatN;
126 #[allow(deprecated)]
127 pub use crate::sources::{RepeatCall, Unfold, Iterate};
128 #[cfg(feature = "use_std")]
129 pub use crate::tee::Tee;
130 pub use crate::tuple_impl::{TupleBuffer, TupleWindows, Tuples};
131 #[cfg(feature = "use_std")]
132 pub use crate::unique_impl::{Unique, UniqueBy};
133 pub use crate::with_position::WithPosition;
134 pub use crate::zip_eq_impl::ZipEq;
135 pub use crate::zip_longest::ZipLongest;
136 pub use crate::ziptuple::Zip;
137 }
138
139 /// Traits helpful for using certain `Itertools` methods in generic contexts.
140 pub mod traits {
141 pub use crate::tuple_impl::HomogeneousTuple;
142 }
143
144 #[allow(deprecated)]
145 pub use crate::structs::*;
146 pub use crate::concat_impl::concat;
147 pub use crate::cons_tuples_impl::cons_tuples;
148 pub use crate::diff::diff_with;
149 pub use crate::diff::Diff;
150 #[cfg(feature = "use_std")]
151 pub use crate::kmerge_impl::{kmerge_by};
152 pub use crate::minmax::MinMaxResult;
153 pub use crate::peeking_take_while::PeekingNext;
154 pub use crate::process_results_impl::process_results;
155 pub use crate::repeatn::repeat_n;
156 #[allow(deprecated)]
157 pub use crate::sources::{repeat_call, unfold, iterate};
158 pub use crate::with_position::Position;
159 pub use crate::ziptuple::multizip;
160 mod adaptors;
161 mod either_or_both;
162 pub use crate::either_or_both::EitherOrBoth;
163 #[doc(hidden)]
164 pub mod free;
165 #[doc(inline)]
166 pub use crate::free::*;
167 mod concat_impl;
168 mod cons_tuples_impl;
169 #[cfg(feature = "use_std")]
170 mod combinations;
171 #[cfg(feature = "use_std")]
172 mod combinations_with_replacement;
173 mod exactly_one_err;
174 mod diff;
175 mod format;
176 #[cfg(feature = "use_std")]
177 mod group_map;
178 #[cfg(feature = "use_std")]
179 mod groupbylazy;
180 mod intersperse;
181 #[cfg(feature = "use_std")]
182 mod kmerge_impl;
183 #[cfg(feature = "use_std")]
184 mod lazy_buffer;
185 mod merge_join;
186 mod minmax;
187 #[cfg(feature = "use_std")]
188 mod multipeek_impl;
189 mod pad_tail;
190 mod peeking_take_while;
191 #[cfg(feature = "use_std")]
192 mod permutations;
193 mod process_results_impl;
194 #[cfg(feature = "use_std")]
195 mod put_back_n_impl;
196 #[cfg(feature = "use_std")]
197 mod rciter_impl;
198 mod repeatn;
199 mod size_hint;
200 mod sources;
201 #[cfg(feature = "use_std")]
202 mod tee;
203 mod tuple_impl;
204 #[cfg(feature = "use_std")]
205 mod unique_impl;
206 mod with_position;
207 mod zip_eq_impl;
208 mod zip_longest;
209 mod ziptuple;
210
211 #[macro_export]
212 /// Create an iterator over the “cartesian product” of iterators.
213 ///
214 /// Iterator element type is like `(A, B, ..., E)` if formed
215 /// from iterators `(I, J, ..., M)` with element types `I::Item = A`, `J::Item = B`, etc.
216 ///
217 /// ```
218 /// # use itertools::iproduct;
219 /// #
220 /// # fn main() {
221 /// // Iterate over the coordinates of a 4 x 4 x 4 grid
222 /// // from (0, 0, 0), (0, 0, 1), .., (0, 1, 0), (0, 1, 1), .. etc until (3, 3, 3)
223 /// for (i, j, k) in iproduct!(0..4, 0..4, 0..4) {
224 /// // ..
225 /// }
226 /// # }
227 /// ```
228 macro_rules! iproduct {
229 (@flatten $I:expr,) => (
230 $I
231 );
232 (@flatten $I:expr, $J:expr, $($K:expr,)*) => (
233 iproduct!(@flatten $crate::cons_tuples(iproduct!($I, $J)), $($K,)*)
234 );
235 ($I:expr) => (
236 $crate::__std_iter::IntoIterator::into_iter($I)
237 );
238 ($I:expr, $J:expr) => (
239 $crate::Itertools::cartesian_product(iproduct!($I), iproduct!($J))
240 );
241 ($I:expr, $J:expr, $($K:expr),+) => (
242 iproduct!(@flatten iproduct!($I, $J), $($K,)+)
243 );
244 }
245
246 #[macro_export]
247 /// Create an iterator running multiple iterators in lockstep.
248 ///
249 /// The `izip!` iterator yields elements until any subiterator
250 /// returns `None`.
251 ///
252 /// This is a version of the standard ``.zip()`` that's supporting more than
253 /// two iterators. The iterator element type is a tuple with one element
254 /// from each of the input iterators. Just like ``.zip()``, the iteration stops
255 /// when the shortest of the inputs reaches its end.
256 ///
257 /// **Note:** The result of this macro is in the general case an iterator
258 /// composed of repeated `.zip()` and a `.map()`; it has an anonymous type.
259 /// The special cases of one and two arguments produce the equivalent of
260 /// `$a.into_iter()` and `$a.into_iter().zip($b)` respectively.
261 ///
262 /// Prefer this macro `izip!()` over [`multizip`] for the performance benefits
263 /// of using the standard library `.zip()`.
264 ///
265 /// [`multizip`]: fn.multizip.html
266 ///
267 /// ```
268 /// # use itertools::izip;
269 /// #
270 /// # fn main() {
271 ///
272 /// // iterate over three sequences side-by-side
273 /// let mut results = [0, 0, 0, 0];
274 /// let inputs = [3, 7, 9, 6];
275 ///
276 /// for (r, index, input) in izip!(&mut results, 0..10, &inputs) {
277 /// *r = index * 10 + input;
278 /// }
279 ///
280 /// assert_eq!(results, [0 + 3, 10 + 7, 29, 36]);
281 /// # }
282 /// ```
283 macro_rules! izip {
284 // @closure creates a tuple-flattening closure for .map() call. usage:
285 // @closure partial_pattern => partial_tuple , rest , of , iterators
286 // eg. izip!( @closure ((a, b), c) => (a, b, c) , dd , ee )
287 ( @closure $p:pat => $tup:expr ) => {
288 |$p| $tup
289 };
290
291 // The "b" identifier is a different identifier on each recursion level thanks to hygiene.
292 ( @closure $p:pat => ( $($tup:tt)* ) , $_iter:expr $( , $tail:expr )* ) => {
293 izip!(@closure ($p, b) => ( $($tup)*, b ) $( , $tail )*)
294 };
295
296 // unary
297 ($first:expr $(,)*) => {
298 $crate::__std_iter::IntoIterator::into_iter($first)
299 };
300
301 // binary
302 ($first:expr, $second:expr $(,)*) => {
303 izip!($first)
304 .zip($second)
305 };
306
307 // n-ary where n > 2
308 ( $first:expr $( , $rest:expr )* $(,)* ) => {
309 izip!($first)
310 $(
311 .zip($rest)
312 )*
313 .map(
314 izip!(@closure a => (a) $( , $rest )*)
315 )
316 };
317 }
318
319 /// An [`Iterator`] blanket implementation that provides extra adaptors and
320 /// methods.
321 ///
322 /// This trait defines a number of methods. They are divided into two groups:
323 ///
324 /// * *Adaptors* take an iterator and parameter as input, and return
325 /// a new iterator value. These are listed first in the trait. An example
326 /// of an adaptor is [`.interleave()`](#method.interleave)
327 ///
328 /// * *Regular methods* are those that don't return iterators and instead
329 /// return a regular value of some other kind.
330 /// [`.next_tuple()`](#method.next_tuple) is an example and the first regular
331 /// method in the list.
332 ///
333 /// [`Iterator`]: https://doc.rust-lang.org/std/iter/trait.Iterator.html
334 pub trait Itertools : Iterator {
335 // adaptors
336
337 /// Alternate elements from two iterators until both have run out.
338 ///
339 /// Iterator element type is `Self::Item`.
340 ///
341 /// This iterator is *fused*.
342 ///
343 /// ```
344 /// use itertools::Itertools;
345 ///
346 /// let it = (1..7).interleave(vec![-1, -2]);
347 /// itertools::assert_equal(it, vec![1, -1, 2, -2, 3, 4, 5, 6]);
348 /// ```
interleave<J>(self, other: J) -> Interleave<Self, J::IntoIter> where J: IntoIterator<Item = Self::Item>, Self: Sized349 fn interleave<J>(self, other: J) -> Interleave<Self, J::IntoIter>
350 where J: IntoIterator<Item = Self::Item>,
351 Self: Sized
352 {
353 interleave(self, other)
354 }
355
356 /// Alternate elements from two iterators until at least one of them has run
357 /// out.
358 ///
359 /// Iterator element type is `Self::Item`.
360 ///
361 /// ```
362 /// use itertools::Itertools;
363 ///
364 /// let it = (1..7).interleave_shortest(vec![-1, -2]);
365 /// itertools::assert_equal(it, vec![1, -1, 2, -2, 3]);
366 /// ```
interleave_shortest<J>(self, other: J) -> InterleaveShortest<Self, J::IntoIter> where J: IntoIterator<Item = Self::Item>, Self: Sized367 fn interleave_shortest<J>(self, other: J) -> InterleaveShortest<Self, J::IntoIter>
368 where J: IntoIterator<Item = Self::Item>,
369 Self: Sized
370 {
371 adaptors::interleave_shortest(self, other.into_iter())
372 }
373
374 /// An iterator adaptor to insert a particular value
375 /// between each element of the adapted iterator.
376 ///
377 /// Iterator element type is `Self::Item`.
378 ///
379 /// This iterator is *fused*.
380 ///
381 /// ```
382 /// use itertools::Itertools;
383 ///
384 /// itertools::assert_equal((0..3).intersperse(8), vec![0, 8, 1, 8, 2]);
385 /// ```
intersperse(self, element: Self::Item) -> Intersperse<Self> where Self: Sized, Self::Item: Clone386 fn intersperse(self, element: Self::Item) -> Intersperse<Self>
387 where Self: Sized,
388 Self::Item: Clone
389 {
390 intersperse::intersperse(self, element)
391 }
392
393 /// Create an iterator which iterates over both this and the specified
394 /// iterator simultaneously, yielding pairs of two optional elements.
395 ///
396 /// This iterator is *fused*.
397 ///
398 /// As long as neither input iterator is exhausted yet, it yields two values
399 /// via `EitherOrBoth::Both`.
400 ///
401 /// When the parameter iterator is exhausted, it only yields a value from the
402 /// `self` iterator via `EitherOrBoth::Left`.
403 ///
404 /// When the `self` iterator is exhausted, it only yields a value from the
405 /// parameter iterator via `EitherOrBoth::Right`.
406 ///
407 /// When both iterators return `None`, all further invocations of `.next()`
408 /// will return `None`.
409 ///
410 /// Iterator element type is
411 /// [`EitherOrBoth<Self::Item, J::Item>`](enum.EitherOrBoth.html).
412 ///
413 /// ```rust
414 /// use itertools::EitherOrBoth::{Both, Right};
415 /// use itertools::Itertools;
416 /// let it = (0..1).zip_longest(1..3);
417 /// itertools::assert_equal(it, vec![Both(0, 1), Right(2)]);
418 /// ```
419 #[inline]
zip_longest<J>(self, other: J) -> ZipLongest<Self, J::IntoIter> where J: IntoIterator, Self: Sized420 fn zip_longest<J>(self, other: J) -> ZipLongest<Self, J::IntoIter>
421 where J: IntoIterator,
422 Self: Sized
423 {
424 zip_longest::zip_longest(self, other.into_iter())
425 }
426
427 /// Create an iterator which iterates over both this and the specified
428 /// iterator simultaneously, yielding pairs of elements.
429 ///
430 /// **Panics** if the iterators reach an end and they are not of equal
431 /// lengths.
432 #[inline]
zip_eq<J>(self, other: J) -> ZipEq<Self, J::IntoIter> where J: IntoIterator, Self: Sized433 fn zip_eq<J>(self, other: J) -> ZipEq<Self, J::IntoIter>
434 where J: IntoIterator,
435 Self: Sized
436 {
437 zip_eq(self, other)
438 }
439
440 /// A “meta iterator adaptor”. Its closure receives a reference to the
441 /// iterator and may pick off as many elements as it likes, to produce the
442 /// next iterator element.
443 ///
444 /// Iterator element type is `B`.
445 ///
446 /// ```
447 /// use itertools::Itertools;
448 ///
449 /// // An adaptor that gathers elements in pairs
450 /// let pit = (0..4).batching(|it| {
451 /// match it.next() {
452 /// None => None,
453 /// Some(x) => match it.next() {
454 /// None => None,
455 /// Some(y) => Some((x, y)),
456 /// }
457 /// }
458 /// });
459 ///
460 /// itertools::assert_equal(pit, vec![(0, 1), (2, 3)]);
461 /// ```
462 ///
batching<B, F>(self, f: F) -> Batching<Self, F> where F: FnMut(&mut Self) -> Option<B>, Self: Sized463 fn batching<B, F>(self, f: F) -> Batching<Self, F>
464 where F: FnMut(&mut Self) -> Option<B>,
465 Self: Sized
466 {
467 adaptors::batching(self, f)
468 }
469
470 /// Return an *iterable* that can group iterator elements.
471 /// Consecutive elements that map to the same key (“runs”), are assigned
472 /// to the same group.
473 ///
474 /// `GroupBy` is the storage for the lazy grouping operation.
475 ///
476 /// If the groups are consumed in order, or if each group's iterator is
477 /// dropped without keeping it around, then `GroupBy` uses no
478 /// allocations. It needs allocations only if several group iterators
479 /// are alive at the same time.
480 ///
481 /// This type implements `IntoIterator` (it is **not** an iterator
482 /// itself), because the group iterators need to borrow from this
483 /// value. It should be stored in a local variable or temporary and
484 /// iterated.
485 ///
486 /// Iterator element type is `(K, Group)`: the group's key and the
487 /// group iterator.
488 ///
489 /// ```
490 /// use itertools::Itertools;
491 ///
492 /// // group data into runs of larger than zero or not.
493 /// let data = vec![1, 3, -2, -2, 1, 0, 1, 2];
494 /// // groups: |---->|------>|--------->|
495 ///
496 /// // Note: The `&` is significant here, `GroupBy` is iterable
497 /// // only by reference. You can also call `.into_iter()` explicitly.
498 /// let mut data_grouped = Vec::new();
499 /// for (key, group) in &data.into_iter().group_by(|elt| *elt >= 0) {
500 /// data_grouped.push((key, group.collect()));
501 /// }
502 /// assert_eq!(data_grouped, vec![(true, vec![1, 3]), (false, vec![-2, -2]), (true, vec![1, 0, 1, 2])]);
503 /// ```
504 #[cfg(feature = "use_std")]
group_by<K, F>(self, key: F) -> GroupBy<K, Self, F> where Self: Sized, F: FnMut(&Self::Item) -> K, K: PartialEq,505 fn group_by<K, F>(self, key: F) -> GroupBy<K, Self, F>
506 where Self: Sized,
507 F: FnMut(&Self::Item) -> K,
508 K: PartialEq,
509 {
510 groupbylazy::new(self, key)
511 }
512
513 /// Return an *iterable* that can chunk the iterator.
514 ///
515 /// Yield subiterators (chunks) that each yield a fixed number elements,
516 /// determined by `size`. The last chunk will be shorter if there aren't
517 /// enough elements.
518 ///
519 /// `IntoChunks` is based on `GroupBy`: it is iterable (implements
520 /// `IntoIterator`, **not** `Iterator`), and it only buffers if several
521 /// chunk iterators are alive at the same time.
522 ///
523 /// Iterator element type is `Chunk`, each chunk's iterator.
524 ///
525 /// **Panics** if `size` is 0.
526 ///
527 /// ```
528 /// use itertools::Itertools;
529 ///
530 /// let data = vec![1, 1, 2, -2, 6, 0, 3, 1];
531 /// //chunk size=3 |------->|-------->|--->|
532 ///
533 /// // Note: The `&` is significant here, `IntoChunks` is iterable
534 /// // only by reference. You can also call `.into_iter()` explicitly.
535 /// for chunk in &data.into_iter().chunks(3) {
536 /// // Check that the sum of each chunk is 4.
537 /// assert_eq!(4, chunk.sum());
538 /// }
539 /// ```
540 #[cfg(feature = "use_std")]
chunks(self, size: usize) -> IntoChunks<Self> where Self: Sized,541 fn chunks(self, size: usize) -> IntoChunks<Self>
542 where Self: Sized,
543 {
544 assert!(size != 0);
545 groupbylazy::new_chunks(self, size)
546 }
547
548 /// Return an iterator over all contiguous windows producing tuples of
549 /// a specific size (up to 4).
550 ///
551 /// `tuple_windows` clones the iterator elements so that they can be
552 /// part of successive windows, this makes it most suited for iterators
553 /// of references and other values that are cheap to copy.
554 ///
555 /// ```
556 /// use itertools::Itertools;
557 /// let mut v = Vec::new();
558 /// for (a, b) in (1..5).tuple_windows() {
559 /// v.push((a, b));
560 /// }
561 /// assert_eq!(v, vec![(1, 2), (2, 3), (3, 4)]);
562 ///
563 /// let mut it = (1..5).tuple_windows();
564 /// assert_eq!(Some((1, 2, 3)), it.next());
565 /// assert_eq!(Some((2, 3, 4)), it.next());
566 /// assert_eq!(None, it.next());
567 ///
568 /// // this requires a type hint
569 /// let it = (1..5).tuple_windows::<(_, _, _)>();
570 /// itertools::assert_equal(it, vec![(1, 2, 3), (2, 3, 4)]);
571 ///
572 /// // you can also specify the complete type
573 /// use itertools::TupleWindows;
574 /// use std::ops::Range;
575 ///
576 /// let it: TupleWindows<Range<u32>, (u32, u32, u32)> = (1..5).tuple_windows();
577 /// itertools::assert_equal(it, vec![(1, 2, 3), (2, 3, 4)]);
578 /// ```
tuple_windows<T>(self) -> TupleWindows<Self, T> where Self: Sized + Iterator<Item = T::Item>, T: traits::HomogeneousTuple, T::Item: Clone579 fn tuple_windows<T>(self) -> TupleWindows<Self, T>
580 where Self: Sized + Iterator<Item = T::Item>,
581 T: traits::HomogeneousTuple,
582 T::Item: Clone
583 {
584 tuple_impl::tuple_windows(self)
585 }
586
587 /// Return an iterator that groups the items in tuples of a specific size
588 /// (up to 4).
589 ///
590 /// See also the method [`.next_tuple()`](#method.next_tuple).
591 ///
592 /// ```
593 /// use itertools::Itertools;
594 /// let mut v = Vec::new();
595 /// for (a, b) in (1..5).tuples() {
596 /// v.push((a, b));
597 /// }
598 /// assert_eq!(v, vec![(1, 2), (3, 4)]);
599 ///
600 /// let mut it = (1..7).tuples();
601 /// assert_eq!(Some((1, 2, 3)), it.next());
602 /// assert_eq!(Some((4, 5, 6)), it.next());
603 /// assert_eq!(None, it.next());
604 ///
605 /// // this requires a type hint
606 /// let it = (1..7).tuples::<(_, _, _)>();
607 /// itertools::assert_equal(it, vec![(1, 2, 3), (4, 5, 6)]);
608 ///
609 /// // you can also specify the complete type
610 /// use itertools::Tuples;
611 /// use std::ops::Range;
612 ///
613 /// let it: Tuples<Range<u32>, (u32, u32, u32)> = (1..7).tuples();
614 /// itertools::assert_equal(it, vec![(1, 2, 3), (4, 5, 6)]);
615 /// ```
616 ///
617 /// See also [`Tuples::into_buffer`](structs/struct.Tuples.html#method.into_buffer).
tuples<T>(self) -> Tuples<Self, T> where Self: Sized + Iterator<Item = T::Item>, T: traits::HomogeneousTuple618 fn tuples<T>(self) -> Tuples<Self, T>
619 where Self: Sized + Iterator<Item = T::Item>,
620 T: traits::HomogeneousTuple
621 {
622 tuple_impl::tuples(self)
623 }
624
625 /// Split into an iterator pair that both yield all elements from
626 /// the original iterator.
627 ///
628 /// **Note:** If the iterator is clonable, prefer using that instead
629 /// of using this method. It is likely to be more efficient.
630 ///
631 /// Iterator element type is `Self::Item`.
632 ///
633 /// ```
634 /// use itertools::Itertools;
635 /// let xs = vec![0, 1, 2, 3];
636 ///
637 /// let (mut t1, t2) = xs.into_iter().tee();
638 /// itertools::assert_equal(t1.next(), Some(0));
639 /// itertools::assert_equal(t2, 0..4);
640 /// itertools::assert_equal(t1, 1..4);
641 /// ```
642 #[cfg(feature = "use_std")]
tee(self) -> (Tee<Self>, Tee<Self>) where Self: Sized, Self::Item: Clone643 fn tee(self) -> (Tee<Self>, Tee<Self>)
644 where Self: Sized,
645 Self::Item: Clone
646 {
647 tee::new(self)
648 }
649
650 /// Return an iterator adaptor that steps `n` elements in the base iterator
651 /// for each iteration.
652 ///
653 /// The iterator steps by yielding the next element from the base iterator,
654 /// then skipping forward `n - 1` elements.
655 ///
656 /// Iterator element type is `Self::Item`.
657 ///
658 /// **Panics** if the step is 0.
659 ///
660 /// ```
661 /// use itertools::Itertools;
662 ///
663 /// let it = (0..8).step(3);
664 /// itertools::assert_equal(it, vec![0, 3, 6]);
665 /// ```
666 #[deprecated(note="Use std .step_by() instead", since="0.8")]
667 #[allow(deprecated)]
step(self, n: usize) -> Step<Self> where Self: Sized668 fn step(self, n: usize) -> Step<Self>
669 where Self: Sized
670 {
671 adaptors::step(self, n)
672 }
673
674 /// Convert each item of the iterator using the `Into` trait.
675 ///
676 /// ```rust
677 /// use itertools::Itertools;
678 ///
679 /// (1i32..42i32).map_into::<f64>().collect_vec();
680 /// ```
map_into<R>(self) -> MapInto<Self, R> where Self: Sized, Self::Item: Into<R>,681 fn map_into<R>(self) -> MapInto<Self, R>
682 where Self: Sized,
683 Self::Item: Into<R>,
684 {
685 adaptors::map_into(self)
686 }
687
688 /// Return an iterator adaptor that applies the provided closure
689 /// to every `Result::Ok` value. `Result::Err` values are
690 /// unchanged.
691 ///
692 /// ```
693 /// use itertools::Itertools;
694 ///
695 /// let input = vec![Ok(41), Err(false), Ok(11)];
696 /// let it = input.into_iter().map_results(|i| i + 1);
697 /// itertools::assert_equal(it, vec![Ok(42), Err(false), Ok(12)]);
698 /// ```
map_results<F, T, U, E>(self, f: F) -> MapResults<Self, F> where Self: Iterator<Item = Result<T, E>> + Sized, F: FnMut(T) -> U,699 fn map_results<F, T, U, E>(self, f: F) -> MapResults<Self, F>
700 where Self: Iterator<Item = Result<T, E>> + Sized,
701 F: FnMut(T) -> U,
702 {
703 adaptors::map_results(self, f)
704 }
705
706 /// Return an iterator adaptor that merges the two base iterators in
707 /// ascending order. If both base iterators are sorted (ascending), the
708 /// result is sorted.
709 ///
710 /// Iterator element type is `Self::Item`.
711 ///
712 /// ```
713 /// use itertools::Itertools;
714 ///
715 /// let a = (0..11).step(3);
716 /// let b = (0..11).step(5);
717 /// let it = a.merge(b);
718 /// itertools::assert_equal(it, vec![0, 0, 3, 5, 6, 9, 10]);
719 /// ```
merge<J>(self, other: J) -> Merge<Self, J::IntoIter> where Self: Sized, Self::Item: PartialOrd, J: IntoIterator<Item = Self::Item>720 fn merge<J>(self, other: J) -> Merge<Self, J::IntoIter>
721 where Self: Sized,
722 Self::Item: PartialOrd,
723 J: IntoIterator<Item = Self::Item>
724 {
725 merge(self, other)
726 }
727
728 /// Return an iterator adaptor that merges the two base iterators in order.
729 /// This is much like `.merge()` but allows for a custom ordering.
730 ///
731 /// This can be especially useful for sequences of tuples.
732 ///
733 /// Iterator element type is `Self::Item`.
734 ///
735 /// ```
736 /// use itertools::Itertools;
737 ///
738 /// let a = (0..).zip("bc".chars());
739 /// let b = (0..).zip("ad".chars());
740 /// let it = a.merge_by(b, |x, y| x.1 <= y.1);
741 /// itertools::assert_equal(it, vec![(0, 'a'), (0, 'b'), (1, 'c'), (1, 'd')]);
742 /// ```
743
merge_by<J, F>(self, other: J, is_first: F) -> MergeBy<Self, J::IntoIter, F> where Self: Sized, J: IntoIterator<Item = Self::Item>, F: FnMut(&Self::Item, &Self::Item) -> bool744 fn merge_by<J, F>(self, other: J, is_first: F) -> MergeBy<Self, J::IntoIter, F>
745 where Self: Sized,
746 J: IntoIterator<Item = Self::Item>,
747 F: FnMut(&Self::Item, &Self::Item) -> bool
748 {
749 adaptors::merge_by_new(self, other.into_iter(), is_first)
750 }
751
752 /// Create an iterator that merges items from both this and the specified
753 /// iterator in ascending order.
754 ///
755 /// It chooses whether to pair elements based on the `Ordering` returned by the
756 /// specified compare function. At any point, inspecting the tip of the
757 /// iterators `I` and `J` as items `i` of type `I::Item` and `j` of type
758 /// `J::Item` respectively, the resulting iterator will:
759 ///
760 /// - Emit `EitherOrBoth::Left(i)` when `i < j`,
761 /// and remove `i` from its source iterator
762 /// - Emit `EitherOrBoth::Right(j)` when `i > j`,
763 /// and remove `j` from its source iterator
764 /// - Emit `EitherOrBoth::Both(i, j)` when `i == j`,
765 /// and remove both `i` and `j` from their respective source iterators
766 ///
767 /// ```
768 /// use itertools::Itertools;
769 /// use itertools::EitherOrBoth::{Left, Right, Both};
770 ///
771 /// let ki = (0..10).step(3);
772 /// let ku = (0..10).step(5);
773 /// let ki_ku = ki.merge_join_by(ku, |i, j| i.cmp(j)).map(|either| {
774 /// match either {
775 /// Left(_) => "Ki",
776 /// Right(_) => "Ku",
777 /// Both(_, _) => "KiKu"
778 /// }
779 /// });
780 ///
781 /// itertools::assert_equal(ki_ku, vec!["KiKu", "Ki", "Ku", "Ki", "Ki"]);
782 /// ```
783 #[inline]
merge_join_by<J, F>(self, other: J, cmp_fn: F) -> MergeJoinBy<Self, J::IntoIter, F> where J: IntoIterator, F: FnMut(&Self::Item, &J::Item) -> std::cmp::Ordering, Self: Sized784 fn merge_join_by<J, F>(self, other: J, cmp_fn: F) -> MergeJoinBy<Self, J::IntoIter, F>
785 where J: IntoIterator,
786 F: FnMut(&Self::Item, &J::Item) -> std::cmp::Ordering,
787 Self: Sized
788 {
789 merge_join_by(self, other, cmp_fn)
790 }
791
792
793 /// Return an iterator adaptor that flattens an iterator of iterators by
794 /// merging them in ascending order.
795 ///
796 /// If all base iterators are sorted (ascending), the result is sorted.
797 ///
798 /// Iterator element type is `Self::Item`.
799 ///
800 /// ```
801 /// use itertools::Itertools;
802 ///
803 /// let a = (0..6).step(3);
804 /// let b = (1..6).step(3);
805 /// let c = (2..6).step(3);
806 /// let it = vec![a, b, c].into_iter().kmerge();
807 /// itertools::assert_equal(it, vec![0, 1, 2, 3, 4, 5]);
808 /// ```
809 #[cfg(feature = "use_std")]
kmerge(self) -> KMerge<<Self::Item as IntoIterator>::IntoIter> where Self: Sized, Self::Item: IntoIterator, <Self::Item as IntoIterator>::Item: PartialOrd,810 fn kmerge(self) -> KMerge<<Self::Item as IntoIterator>::IntoIter>
811 where Self: Sized,
812 Self::Item: IntoIterator,
813 <Self::Item as IntoIterator>::Item: PartialOrd,
814 {
815 kmerge(self)
816 }
817
818 /// Return an iterator adaptor that flattens an iterator of iterators by
819 /// merging them according to the given closure.
820 ///
821 /// The closure `first` is called with two elements *a*, *b* and should
822 /// return `true` if *a* is ordered before *b*.
823 ///
824 /// If all base iterators are sorted according to `first`, the result is
825 /// sorted.
826 ///
827 /// Iterator element type is `Self::Item`.
828 ///
829 /// ```
830 /// use itertools::Itertools;
831 ///
832 /// let a = vec![-1f64, 2., 3., -5., 6., -7.];
833 /// let b = vec![0., 2., -4.];
834 /// let mut it = vec![a, b].into_iter().kmerge_by(|a, b| a.abs() < b.abs());
835 /// assert_eq!(it.next(), Some(0.));
836 /// assert_eq!(it.last(), Some(-7.));
837 /// ```
838 #[cfg(feature = "use_std")]
kmerge_by<F>(self, first: F) -> KMergeBy<<Self::Item as IntoIterator>::IntoIter, F> where Self: Sized, Self::Item: IntoIterator, F: FnMut(&<Self::Item as IntoIterator>::Item, &<Self::Item as IntoIterator>::Item) -> bool839 fn kmerge_by<F>(self, first: F)
840 -> KMergeBy<<Self::Item as IntoIterator>::IntoIter, F>
841 where Self: Sized,
842 Self::Item: IntoIterator,
843 F: FnMut(&<Self::Item as IntoIterator>::Item,
844 &<Self::Item as IntoIterator>::Item) -> bool
845 {
846 kmerge_by(self, first)
847 }
848
849 /// Return an iterator adaptor that iterates over the cartesian product of
850 /// the element sets of two iterators `self` and `J`.
851 ///
852 /// Iterator element type is `(Self::Item, J::Item)`.
853 ///
854 /// ```
855 /// use itertools::Itertools;
856 ///
857 /// let it = (0..2).cartesian_product("αβ".chars());
858 /// itertools::assert_equal(it, vec![(0, 'α'), (0, 'β'), (1, 'α'), (1, 'β')]);
859 /// ```
cartesian_product<J>(self, other: J) -> Product<Self, J::IntoIter> where Self: Sized, Self::Item: Clone, J: IntoIterator, J::IntoIter: Clone860 fn cartesian_product<J>(self, other: J) -> Product<Self, J::IntoIter>
861 where Self: Sized,
862 Self::Item: Clone,
863 J: IntoIterator,
864 J::IntoIter: Clone
865 {
866 adaptors::cartesian_product(self, other.into_iter())
867 }
868
869 /// Return an iterator adaptor that iterates over the cartesian product of
870 /// all subiterators returned by meta-iterator `self`.
871 ///
872 /// All provided iterators must yield the same `Item` type. To generate
873 /// the product of iterators yielding multiple types, use the
874 /// [`iproduct`](macro.iproduct.html) macro instead.
875 ///
876 ///
877 /// The iterator element type is `Vec<T>`, where `T` is the iterator element
878 /// of the subiterators.
879 ///
880 /// ```
881 /// use itertools::Itertools;
882 /// let mut multi_prod = (0..3).map(|i| (i * 2)..(i * 2 + 2))
883 /// .multi_cartesian_product();
884 /// assert_eq!(multi_prod.next(), Some(vec![0, 2, 4]));
885 /// assert_eq!(multi_prod.next(), Some(vec![0, 2, 5]));
886 /// assert_eq!(multi_prod.next(), Some(vec![0, 3, 4]));
887 /// assert_eq!(multi_prod.next(), Some(vec![0, 3, 5]));
888 /// assert_eq!(multi_prod.next(), Some(vec![1, 2, 4]));
889 /// assert_eq!(multi_prod.next(), Some(vec![1, 2, 5]));
890 /// assert_eq!(multi_prod.next(), Some(vec![1, 3, 4]));
891 /// assert_eq!(multi_prod.next(), Some(vec![1, 3, 5]));
892 /// assert_eq!(multi_prod.next(), None);
893 /// ```
894 #[cfg(feature = "use_std")]
multi_cartesian_product(self) -> MultiProduct<<Self::Item as IntoIterator>::IntoIter> where Self: Iterator + Sized, Self::Item: IntoIterator, <Self::Item as IntoIterator>::IntoIter: Clone, <Self::Item as IntoIterator>::Item: Clone895 fn multi_cartesian_product(self) -> MultiProduct<<Self::Item as IntoIterator>::IntoIter>
896 where Self: Iterator + Sized,
897 Self::Item: IntoIterator,
898 <Self::Item as IntoIterator>::IntoIter: Clone,
899 <Self::Item as IntoIterator>::Item: Clone
900 {
901 adaptors::multi_cartesian_product(self)
902 }
903
904 /// Return an iterator adaptor that uses the passed-in closure to
905 /// optionally merge together consecutive elements.
906 ///
907 /// The closure `f` is passed two elements, `previous` and `current` and may
908 /// return either (1) `Ok(combined)` to merge the two values or
909 /// (2) `Err((previous', current'))` to indicate they can't be merged.
910 /// In (2), the value `previous'` is emitted by the iterator.
911 /// Either (1) `combined` or (2) `current'` becomes the previous value
912 /// when coalesce continues with the next pair of elements to merge. The
913 /// value that remains at the end is also emitted by the iterator.
914 ///
915 /// Iterator element type is `Self::Item`.
916 ///
917 /// This iterator is *fused*.
918 ///
919 /// ```
920 /// use itertools::Itertools;
921 ///
922 /// // sum same-sign runs together
923 /// let data = vec![-1., -2., -3., 3., 1., 0., -1.];
924 /// itertools::assert_equal(data.into_iter().coalesce(|x, y|
925 /// if (x >= 0.) == (y >= 0.) {
926 /// Ok(x + y)
927 /// } else {
928 /// Err((x, y))
929 /// }),
930 /// vec![-6., 4., -1.]);
931 /// ```
coalesce<F>(self, f: F) -> Coalesce<Self, F> where Self: Sized, F: FnMut(Self::Item, Self::Item) -> Result<Self::Item, (Self::Item, Self::Item)>932 fn coalesce<F>(self, f: F) -> Coalesce<Self, F>
933 where Self: Sized,
934 F: FnMut(Self::Item, Self::Item)
935 -> Result<Self::Item, (Self::Item, Self::Item)>
936 {
937 adaptors::coalesce(self, f)
938 }
939
940 /// Remove duplicates from sections of consecutive identical elements.
941 /// If the iterator is sorted, all elements will be unique.
942 ///
943 /// Iterator element type is `Self::Item`.
944 ///
945 /// This iterator is *fused*.
946 ///
947 /// ```
948 /// use itertools::Itertools;
949 ///
950 /// let data = vec![1., 1., 2., 3., 3., 2., 2.];
951 /// itertools::assert_equal(data.into_iter().dedup(),
952 /// vec![1., 2., 3., 2.]);
953 /// ```
dedup(self) -> Dedup<Self> where Self: Sized, Self::Item: PartialEq,954 fn dedup(self) -> Dedup<Self>
955 where Self: Sized,
956 Self::Item: PartialEq,
957 {
958 adaptors::dedup(self)
959 }
960
961 /// Remove duplicates from sections of consecutive identical elements,
962 /// determining equality using a comparison function.
963 /// If the iterator is sorted, all elements will be unique.
964 ///
965 /// Iterator element type is `Self::Item`.
966 ///
967 /// This iterator is *fused*.
968 ///
969 /// ```
970 /// use itertools::Itertools;
971 ///
972 /// let data = vec![(0, 1.), (1, 1.), (0, 2.), (0, 3.), (1, 3.), (1, 2.), (2, 2.)];
973 /// itertools::assert_equal(data.into_iter().dedup_by(|x, y| x.1==y.1),
974 /// vec![(0, 1.), (0, 2.), (0, 3.), (1, 2.)]);
975 /// ```
dedup_by<Cmp>(self, cmp: Cmp) -> DedupBy<Self, Cmp> where Self: Sized, Cmp: FnMut(&Self::Item, &Self::Item)->bool,976 fn dedup_by<Cmp>(self, cmp: Cmp) -> DedupBy<Self, Cmp>
977 where Self: Sized,
978 Cmp: FnMut(&Self::Item, &Self::Item)->bool,
979 {
980 adaptors::dedup_by(self, cmp)
981 }
982
983 /// Return an iterator adaptor that filters out elements that have
984 /// already been produced once during the iteration. Duplicates
985 /// are detected using hash and equality.
986 ///
987 /// Clones of visited elements are stored in a hash set in the
988 /// iterator.
989 ///
990 /// ```
991 /// use itertools::Itertools;
992 ///
993 /// let data = vec![10, 20, 30, 20, 40, 10, 50];
994 /// itertools::assert_equal(data.into_iter().unique(),
995 /// vec![10, 20, 30, 40, 50]);
996 /// ```
997 #[cfg(feature = "use_std")]
unique(self) -> Unique<Self> where Self: Sized, Self::Item: Clone + Eq + Hash998 fn unique(self) -> Unique<Self>
999 where Self: Sized,
1000 Self::Item: Clone + Eq + Hash
1001 {
1002 unique_impl::unique(self)
1003 }
1004
1005 /// Return an iterator adaptor that filters out elements that have
1006 /// already been produced once during the iteration.
1007 ///
1008 /// Duplicates are detected by comparing the key they map to
1009 /// with the keying function `f` by hash and equality.
1010 /// The keys are stored in a hash set in the iterator.
1011 ///
1012 /// ```
1013 /// use itertools::Itertools;
1014 ///
1015 /// let data = vec!["a", "bb", "aa", "c", "ccc"];
1016 /// itertools::assert_equal(data.into_iter().unique_by(|s| s.len()),
1017 /// vec!["a", "bb", "ccc"]);
1018 /// ```
1019 #[cfg(feature = "use_std")]
unique_by<V, F>(self, f: F) -> UniqueBy<Self, V, F> where Self: Sized, V: Eq + Hash, F: FnMut(&Self::Item) -> V1020 fn unique_by<V, F>(self, f: F) -> UniqueBy<Self, V, F>
1021 where Self: Sized,
1022 V: Eq + Hash,
1023 F: FnMut(&Self::Item) -> V
1024 {
1025 unique_impl::unique_by(self, f)
1026 }
1027
1028 /// Return an iterator adaptor that borrows from this iterator and
1029 /// takes items while the closure `accept` returns `true`.
1030 ///
1031 /// This adaptor can only be used on iterators that implement `PeekingNext`
1032 /// like `.peekable()`, `put_back` and a few other collection iterators.
1033 ///
1034 /// The last and rejected element (first `false`) is still available when
1035 /// `peeking_take_while` is done.
1036 ///
1037 ///
1038 /// See also [`.take_while_ref()`](#method.take_while_ref)
1039 /// which is a similar adaptor.
peeking_take_while<F>(&mut self, accept: F) -> PeekingTakeWhile<Self, F> where Self: Sized + PeekingNext, F: FnMut(&Self::Item) -> bool,1040 fn peeking_take_while<F>(&mut self, accept: F) -> PeekingTakeWhile<Self, F>
1041 where Self: Sized + PeekingNext,
1042 F: FnMut(&Self::Item) -> bool,
1043 {
1044 peeking_take_while::peeking_take_while(self, accept)
1045 }
1046
1047 /// Return an iterator adaptor that borrows from a `Clone`-able iterator
1048 /// to only pick off elements while the predicate `accept` returns `true`.
1049 ///
1050 /// It uses the `Clone` trait to restore the original iterator so that the
1051 /// last and rejected element (first `false`) is still available when
1052 /// `take_while_ref` is done.
1053 ///
1054 /// ```
1055 /// use itertools::Itertools;
1056 ///
1057 /// let mut hexadecimals = "0123456789abcdef".chars();
1058 ///
1059 /// let decimals = hexadecimals.take_while_ref(|c| c.is_numeric())
1060 /// .collect::<String>();
1061 /// assert_eq!(decimals, "0123456789");
1062 /// assert_eq!(hexadecimals.next(), Some('a'));
1063 ///
1064 /// ```
take_while_ref<F>(&mut self, accept: F) -> TakeWhileRef<Self, F> where Self: Clone, F: FnMut(&Self::Item) -> bool1065 fn take_while_ref<F>(&mut self, accept: F) -> TakeWhileRef<Self, F>
1066 where Self: Clone,
1067 F: FnMut(&Self::Item) -> bool
1068 {
1069 adaptors::take_while_ref(self, accept)
1070 }
1071
1072 /// Return an iterator adaptor that filters `Option<A>` iterator elements
1073 /// and produces `A`. Stops on the first `None` encountered.
1074 ///
1075 /// Iterator element type is `A`, the unwrapped element.
1076 ///
1077 /// ```
1078 /// use itertools::Itertools;
1079 ///
1080 /// // List all hexadecimal digits
1081 /// itertools::assert_equal(
1082 /// (0..).map(|i| std::char::from_digit(i, 16)).while_some(),
1083 /// "0123456789abcdef".chars());
1084 ///
1085 /// ```
while_some<A>(self) -> WhileSome<Self> where Self: Sized + Iterator<Item = Option<A>>1086 fn while_some<A>(self) -> WhileSome<Self>
1087 where Self: Sized + Iterator<Item = Option<A>>
1088 {
1089 adaptors::while_some(self)
1090 }
1091
1092 /// Return an iterator adaptor that iterates over the combinations of the
1093 /// elements from an iterator.
1094 ///
1095 /// Iterator element can be any homogeneous tuple of type `Self::Item` with
1096 /// size up to 4.
1097 ///
1098 /// ```
1099 /// use itertools::Itertools;
1100 ///
1101 /// let mut v = Vec::new();
1102 /// for (a, b) in (1..5).tuple_combinations() {
1103 /// v.push((a, b));
1104 /// }
1105 /// assert_eq!(v, vec![(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]);
1106 ///
1107 /// let mut it = (1..5).tuple_combinations();
1108 /// assert_eq!(Some((1, 2, 3)), it.next());
1109 /// assert_eq!(Some((1, 2, 4)), it.next());
1110 /// assert_eq!(Some((1, 3, 4)), it.next());
1111 /// assert_eq!(Some((2, 3, 4)), it.next());
1112 /// assert_eq!(None, it.next());
1113 ///
1114 /// // this requires a type hint
1115 /// let it = (1..5).tuple_combinations::<(_, _, _)>();
1116 /// itertools::assert_equal(it, vec![(1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4)]);
1117 ///
1118 /// // you can also specify the complete type
1119 /// use itertools::TupleCombinations;
1120 /// use std::ops::Range;
1121 ///
1122 /// let it: TupleCombinations<Range<u32>, (u32, u32, u32)> = (1..5).tuple_combinations();
1123 /// itertools::assert_equal(it, vec![(1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4)]);
1124 /// ```
tuple_combinations<T>(self) -> TupleCombinations<Self, T> where Self: Sized + Clone, Self::Item: Clone, T: adaptors::HasCombination<Self>,1125 fn tuple_combinations<T>(self) -> TupleCombinations<Self, T>
1126 where Self: Sized + Clone,
1127 Self::Item: Clone,
1128 T: adaptors::HasCombination<Self>,
1129 {
1130 adaptors::tuple_combinations(self)
1131 }
1132
1133 /// Return an iterator adaptor that iterates over the `k`-length combinations of
1134 /// the elements from an iterator.
1135 ///
1136 /// Iterator element type is `Vec<Self::Item>`. The iterator produces a new Vec per iteration,
1137 /// and clones the iterator elements.
1138 ///
1139 /// ```
1140 /// use itertools::Itertools;
1141 ///
1142 /// let it = (1..5).combinations(3);
1143 /// itertools::assert_equal(it, vec![
1144 /// vec![1, 2, 3],
1145 /// vec![1, 2, 4],
1146 /// vec![1, 3, 4],
1147 /// vec![2, 3, 4],
1148 /// ]);
1149 /// ```
1150 ///
1151 /// Note: Combinations does not take into account the equality of the iterated values.
1152 /// ```
1153 /// use itertools::Itertools;
1154 ///
1155 /// let it = vec![1, 2, 2].into_iter().combinations(2);
1156 /// itertools::assert_equal(it, vec![
1157 /// vec![1, 2], // Note: these are the same
1158 /// vec![1, 2], // Note: these are the same
1159 /// vec![2, 2],
1160 /// ]);
1161 /// ```
1162 #[cfg(feature = "use_std")]
combinations(self, k: usize) -> Combinations<Self> where Self: Sized, Self::Item: Clone1163 fn combinations(self, k: usize) -> Combinations<Self>
1164 where Self: Sized,
1165 Self::Item: Clone
1166 {
1167 combinations::combinations(self, k)
1168 }
1169
1170 /// Return an iterator that iterates over the `k`-length combinations of
1171 /// the elements from an iterator, with replacement.
1172 ///
1173 /// Iterator element type is `Vec<Self::Item>`. The iterator produces a new Vec per iteration,
1174 /// and clones the iterator elements.
1175 ///
1176 /// ```
1177 /// use itertools::Itertools;
1178 ///
1179 /// let it = (1..4).combinations_with_replacement(2);
1180 /// itertools::assert_equal(it, vec![
1181 /// vec![1, 1],
1182 /// vec![1, 2],
1183 /// vec![1, 3],
1184 /// vec![2, 2],
1185 /// vec![2, 3],
1186 /// vec![3, 3],
1187 /// ]);
1188 /// ```
1189 #[cfg(feature = "use_std")]
combinations_with_replacement(self, k: usize) -> CombinationsWithReplacement<Self> where Self: Sized, Self::Item: Clone,1190 fn combinations_with_replacement(self, k: usize) -> CombinationsWithReplacement<Self>
1191 where
1192 Self: Sized,
1193 Self::Item: Clone,
1194 {
1195 combinations_with_replacement::combinations_with_replacement(self, k)
1196 }
1197
1198 /// Return an iterator adaptor that iterates over all k-permutations of the
1199 /// elements from an iterator.
1200 ///
1201 /// Iterator element type is `Vec<Self::Item>` with length `k`. The iterator
1202 /// produces a new Vec per iteration, and clones the iterator elements.
1203 ///
1204 /// If `k` is greater than the length of the input iterator, the resultant
1205 /// iterator adaptor will be empty.
1206 ///
1207 /// ```
1208 /// use itertools::Itertools;
1209 ///
1210 /// let perms = (5..8).permutations(2);
1211 /// itertools::assert_equal(perms, vec![
1212 /// vec![5, 6],
1213 /// vec![5, 7],
1214 /// vec![6, 5],
1215 /// vec![6, 7],
1216 /// vec![7, 5],
1217 /// vec![7, 6],
1218 /// ]);
1219 /// ```
1220 ///
1221 /// Note: Permutations does not take into account the equality of the iterated values.
1222 ///
1223 /// ```
1224 /// use itertools::Itertools;
1225 ///
1226 /// let it = vec![2, 2].into_iter().permutations(2);
1227 /// itertools::assert_equal(it, vec![
1228 /// vec![2, 2], // Note: these are the same
1229 /// vec![2, 2], // Note: these are the same
1230 /// ]);
1231 /// ```
1232 ///
1233 /// Note: The source iterator is collected lazily, and will not be
1234 /// re-iterated if the permutations adaptor is completed and re-iterated.
1235 #[cfg(feature = "use_std")]
permutations(self, k: usize) -> Permutations<Self> where Self: Sized, Self::Item: Clone1236 fn permutations(self, k: usize) -> Permutations<Self>
1237 where Self: Sized,
1238 Self::Item: Clone
1239 {
1240 permutations::permutations(self, k)
1241 }
1242
1243 /// Return an iterator adaptor that pads the sequence to a minimum length of
1244 /// `min` by filling missing elements using a closure `f`.
1245 ///
1246 /// Iterator element type is `Self::Item`.
1247 ///
1248 /// ```
1249 /// use itertools::Itertools;
1250 ///
1251 /// let it = (0..5).pad_using(10, |i| 2*i);
1252 /// itertools::assert_equal(it, vec![0, 1, 2, 3, 4, 10, 12, 14, 16, 18]);
1253 ///
1254 /// let it = (0..10).pad_using(5, |i| 2*i);
1255 /// itertools::assert_equal(it, vec![0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);
1256 ///
1257 /// let it = (0..5).pad_using(10, |i| 2*i).rev();
1258 /// itertools::assert_equal(it, vec![18, 16, 14, 12, 10, 4, 3, 2, 1, 0]);
1259 /// ```
pad_using<F>(self, min: usize, f: F) -> PadUsing<Self, F> where Self: Sized, F: FnMut(usize) -> Self::Item1260 fn pad_using<F>(self, min: usize, f: F) -> PadUsing<Self, F>
1261 where Self: Sized,
1262 F: FnMut(usize) -> Self::Item
1263 {
1264 pad_tail::pad_using(self, min, f)
1265 }
1266
1267 /// Return an iterator adaptor that wraps each element in a `Position` to
1268 /// ease special-case handling of the first or last elements.
1269 ///
1270 /// Iterator element type is
1271 /// [`Position<Self::Item>`](enum.Position.html)
1272 ///
1273 /// ```
1274 /// use itertools::{Itertools, Position};
1275 ///
1276 /// let it = (0..4).with_position();
1277 /// itertools::assert_equal(it,
1278 /// vec![Position::First(0),
1279 /// Position::Middle(1),
1280 /// Position::Middle(2),
1281 /// Position::Last(3)]);
1282 ///
1283 /// let it = (0..1).with_position();
1284 /// itertools::assert_equal(it, vec![Position::Only(0)]);
1285 /// ```
with_position(self) -> WithPosition<Self> where Self: Sized,1286 fn with_position(self) -> WithPosition<Self>
1287 where Self: Sized,
1288 {
1289 with_position::with_position(self)
1290 }
1291
1292 /// Return an iterator adaptor that yields the indices of all elements
1293 /// satisfying a predicate, counted from the start of the iterator.
1294 ///
1295 /// Equivalent to `iter.enumerate().filter(|(_, v)| predicate(v)).map(|(i, _)| i)`.
1296 ///
1297 /// ```
1298 /// use itertools::Itertools;
1299 ///
1300 /// let data = vec![1, 2, 3, 3, 4, 6, 7, 9];
1301 /// itertools::assert_equal(data.iter().positions(|v| v % 2 == 0), vec![1, 4, 5]);
1302 ///
1303 /// itertools::assert_equal(data.iter().positions(|v| v % 2 == 1).rev(), vec![7, 6, 3, 2, 0]);
1304 /// ```
positions<P>(self, predicate: P) -> Positions<Self, P> where Self: Sized, P: FnMut(Self::Item) -> bool,1305 fn positions<P>(self, predicate: P) -> Positions<Self, P>
1306 where Self: Sized,
1307 P: FnMut(Self::Item) -> bool,
1308 {
1309 adaptors::positions(self, predicate)
1310 }
1311
1312 /// Return an iterator adaptor that applies a mutating function
1313 /// to each element before yielding it.
1314 ///
1315 /// ```
1316 /// use itertools::Itertools;
1317 ///
1318 /// let input = vec![vec![1], vec![3, 2, 1]];
1319 /// let it = input.into_iter().update(|mut v| v.push(0));
1320 /// itertools::assert_equal(it, vec![vec![1, 0], vec![3, 2, 1, 0]]);
1321 /// ```
update<F>(self, updater: F) -> Update<Self, F> where Self: Sized, F: FnMut(&mut Self::Item),1322 fn update<F>(self, updater: F) -> Update<Self, F>
1323 where Self: Sized,
1324 F: FnMut(&mut Self::Item),
1325 {
1326 adaptors::update(self, updater)
1327 }
1328
1329 // non-adaptor methods
1330 /// Advances the iterator and returns the next items grouped in a tuple of
1331 /// a specific size (up to 4).
1332 ///
1333 /// If there are enough elements to be grouped in a tuple, then the tuple is
1334 /// returned inside `Some`, otherwise `None` is returned.
1335 ///
1336 /// ```
1337 /// use itertools::Itertools;
1338 ///
1339 /// let mut iter = 1..5;
1340 ///
1341 /// assert_eq!(Some((1, 2)), iter.next_tuple());
1342 /// ```
next_tuple<T>(&mut self) -> Option<T> where Self: Sized + Iterator<Item = T::Item>, T: traits::HomogeneousTuple1343 fn next_tuple<T>(&mut self) -> Option<T>
1344 where Self: Sized + Iterator<Item = T::Item>,
1345 T: traits::HomogeneousTuple
1346 {
1347 T::collect_from_iter_no_buf(self)
1348 }
1349
1350 /// Collects all items from the iterator into a tuple of a specific size
1351 /// (up to 4).
1352 ///
1353 /// If the number of elements inside the iterator is **exactly** equal to
1354 /// the tuple size, then the tuple is returned inside `Some`, otherwise
1355 /// `None` is returned.
1356 ///
1357 /// ```
1358 /// use itertools::Itertools;
1359 ///
1360 /// let iter = 1..3;
1361 ///
1362 /// if let Some((x, y)) = iter.collect_tuple() {
1363 /// assert_eq!((x, y), (1, 2))
1364 /// } else {
1365 /// panic!("Expected two elements")
1366 /// }
1367 /// ```
collect_tuple<T>(mut self) -> Option<T> where Self: Sized + Iterator<Item = T::Item>, T: traits::HomogeneousTuple1368 fn collect_tuple<T>(mut self) -> Option<T>
1369 where Self: Sized + Iterator<Item = T::Item>,
1370 T: traits::HomogeneousTuple
1371 {
1372 match self.next_tuple() {
1373 elt @ Some(_) => match self.next() {
1374 Some(_) => None,
1375 None => elt,
1376 },
1377 _ => None
1378 }
1379 }
1380
1381
1382 /// Find the position and value of the first element satisfying a predicate.
1383 ///
1384 /// The iterator is not advanced past the first element found.
1385 ///
1386 /// ```
1387 /// use itertools::Itertools;
1388 ///
1389 /// let text = "Hα";
1390 /// assert_eq!(text.chars().find_position(|ch| ch.is_lowercase()), Some((1, 'α')));
1391 /// ```
find_position<P>(&mut self, mut pred: P) -> Option<(usize, Self::Item)> where P: FnMut(&Self::Item) -> bool1392 fn find_position<P>(&mut self, mut pred: P) -> Option<(usize, Self::Item)>
1393 where P: FnMut(&Self::Item) -> bool
1394 {
1395 let mut index = 0usize;
1396 for elt in self {
1397 if pred(&elt) {
1398 return Some((index, elt));
1399 }
1400 index += 1;
1401 }
1402 None
1403 }
1404
1405 /// Check whether all elements compare equal.
1406 ///
1407 /// Empty iterators are considered to have equal elements:
1408 ///
1409 /// ```
1410 /// use itertools::Itertools;
1411 ///
1412 /// let data = vec![1, 1, 1, 2, 2, 3, 3, 3, 4, 5, 5];
1413 /// assert!(!data.iter().all_equal());
1414 /// assert!(data[0..3].iter().all_equal());
1415 /// assert!(data[3..5].iter().all_equal());
1416 /// assert!(data[5..8].iter().all_equal());
1417 ///
1418 /// let data : Option<usize> = None;
1419 /// assert!(data.into_iter().all_equal());
1420 /// ```
all_equal(&mut self) -> bool where Self: Sized, Self::Item: PartialEq,1421 fn all_equal(&mut self) -> bool
1422 where Self: Sized,
1423 Self::Item: PartialEq,
1424 {
1425 match self.next() {
1426 None => true,
1427 Some(a) => self.all(|x| a == x),
1428 }
1429 }
1430
1431 /// Consume the first `n` elements from the iterator eagerly,
1432 /// and return the same iterator again.
1433 ///
1434 /// It works similarly to *.skip(* `n` *)* except it is eager and
1435 /// preserves the iterator type.
1436 ///
1437 /// ```
1438 /// use itertools::Itertools;
1439 ///
1440 /// let mut iter = "αβγ".chars().dropping(2);
1441 /// itertools::assert_equal(iter, "γ".chars());
1442 /// ```
1443 ///
1444 /// *Fusing notes: if the iterator is exhausted by dropping,
1445 /// the result of calling `.next()` again depends on the iterator implementation.*
dropping(mut self, n: usize) -> Self where Self: Sized1446 fn dropping(mut self, n: usize) -> Self
1447 where Self: Sized
1448 {
1449 if n > 0 {
1450 self.nth(n - 1);
1451 }
1452 self
1453 }
1454
1455 /// Consume the last `n` elements from the iterator eagerly,
1456 /// and return the same iterator again.
1457 ///
1458 /// This is only possible on double ended iterators. `n` may be
1459 /// larger than the number of elements.
1460 ///
1461 /// Note: This method is eager, dropping the back elements immediately and
1462 /// preserves the iterator type.
1463 ///
1464 /// ```
1465 /// use itertools::Itertools;
1466 ///
1467 /// let init = vec![0, 3, 6, 9].into_iter().dropping_back(1);
1468 /// itertools::assert_equal(init, vec![0, 3, 6]);
1469 /// ```
dropping_back(mut self, n: usize) -> Self where Self: Sized, Self: DoubleEndedIterator1470 fn dropping_back(mut self, n: usize) -> Self
1471 where Self: Sized,
1472 Self: DoubleEndedIterator
1473 {
1474 if n > 0 {
1475 (&mut self).rev().nth(n - 1);
1476 }
1477 self
1478 }
1479
1480 /// Run the closure `f` eagerly on each element of the iterator.
1481 ///
1482 /// Consumes the iterator until its end.
1483 ///
1484 /// ```
1485 /// use std::sync::mpsc::channel;
1486 /// use itertools::Itertools;
1487 ///
1488 /// let (tx, rx) = channel();
1489 ///
1490 /// // use .foreach() to apply a function to each value -- sending it
1491 /// (0..5).map(|x| x * 2 + 1).foreach(|x| { tx.send(x).unwrap(); } );
1492 ///
1493 /// drop(tx);
1494 ///
1495 /// itertools::assert_equal(rx.iter(), vec![1, 3, 5, 7, 9]);
1496 /// ```
1497 #[deprecated(note="Use .for_each() instead", since="0.8")]
foreach<F>(self, f: F) where F: FnMut(Self::Item), Self: Sized,1498 fn foreach<F>(self, f: F)
1499 where F: FnMut(Self::Item),
1500 Self: Sized,
1501 {
1502 self.for_each(f)
1503 }
1504
1505 /// Combine all an iterator's elements into one element by using `Extend`.
1506 ///
1507 /// This combinator will extend the first item with each of the rest of the
1508 /// items of the iterator. If the iterator is empty, the default value of
1509 /// `I::Item` is returned.
1510 ///
1511 /// ```rust
1512 /// use itertools::Itertools;
1513 ///
1514 /// let input = vec![vec![1], vec![2, 3], vec![4, 5, 6]];
1515 /// assert_eq!(input.into_iter().concat(),
1516 /// vec![1, 2, 3, 4, 5, 6]);
1517 /// ```
concat(self) -> Self::Item where Self: Sized, Self::Item: Extend<<<Self as Iterator>::Item as IntoIterator>::Item> + IntoIterator + Default1518 fn concat(self) -> Self::Item
1519 where Self: Sized,
1520 Self::Item: Extend<<<Self as Iterator>::Item as IntoIterator>::Item> + IntoIterator + Default
1521 {
1522 concat(self)
1523 }
1524
1525 /// `.collect_vec()` is simply a type specialization of `.collect()`,
1526 /// for convenience.
1527 #[cfg(feature = "use_std")]
collect_vec(self) -> Vec<Self::Item> where Self: Sized1528 fn collect_vec(self) -> Vec<Self::Item>
1529 where Self: Sized
1530 {
1531 self.collect()
1532 }
1533
1534 /// `.try_collect()` is more convenient way of writing
1535 /// `.collect::<Result<_, _>>()`
1536 ///
1537 /// # Example
1538 ///
1539 /// ```
1540 /// use std::{fs, io};
1541 /// use itertools::Itertools;
1542 ///
1543 /// fn process_dir_entries(entries: &[fs::DirEntry]) {
1544 /// // ...
1545 /// }
1546 ///
1547 /// fn do_stuff() -> std::io::Result<()> {
1548 /// let entries: Vec<_> = fs::read_dir(".")?.try_collect()?;
1549 /// process_dir_entries(&entries);
1550 ///
1551 /// Ok(())
1552 /// }
1553 /// ```
1554 #[cfg(feature = "use_std")]
try_collect<T, U, E>(self) -> Result<U, E> where Self: Sized + Iterator<Item = Result<T, E>>, Result<U, E>: FromIterator<Result<T, E>>,1555 fn try_collect<T, U, E>(self) -> Result<U, E>
1556 where
1557 Self: Sized + Iterator<Item = Result<T, E>>,
1558 Result<U, E>: FromIterator<Result<T, E>>,
1559 {
1560 self.collect()
1561 }
1562
1563 /// Assign to each reference in `self` from the `from` iterator,
1564 /// stopping at the shortest of the two iterators.
1565 ///
1566 /// The `from` iterator is queried for its next element before the `self`
1567 /// iterator, and if either is exhausted the method is done.
1568 ///
1569 /// Return the number of elements written.
1570 ///
1571 /// ```
1572 /// use itertools::Itertools;
1573 ///
1574 /// let mut xs = [0; 4];
1575 /// xs.iter_mut().set_from(1..);
1576 /// assert_eq!(xs, [1, 2, 3, 4]);
1577 /// ```
1578 #[inline]
set_from<'a, A: 'a, J>(&mut self, from: J) -> usize where Self: Iterator<Item = &'a mut A>, J: IntoIterator<Item = A>1579 fn set_from<'a, A: 'a, J>(&mut self, from: J) -> usize
1580 where Self: Iterator<Item = &'a mut A>,
1581 J: IntoIterator<Item = A>
1582 {
1583 let mut count = 0;
1584 for elt in from {
1585 match self.next() {
1586 None => break,
1587 Some(ptr) => *ptr = elt,
1588 }
1589 count += 1;
1590 }
1591 count
1592 }
1593
1594 /// Combine all iterator elements into one String, separated by `sep`.
1595 ///
1596 /// Use the `Display` implementation of each element.
1597 ///
1598 /// ```
1599 /// use itertools::Itertools;
1600 ///
1601 /// assert_eq!(["a", "b", "c"].iter().join(", "), "a, b, c");
1602 /// assert_eq!([1, 2, 3].iter().join(", "), "1, 2, 3");
1603 /// ```
1604 #[cfg(feature = "use_std")]
join(&mut self, sep: &str) -> String where Self::Item: std::fmt::Display1605 fn join(&mut self, sep: &str) -> String
1606 where Self::Item: std::fmt::Display
1607 {
1608 match self.next() {
1609 None => String::new(),
1610 Some(first_elt) => {
1611 // estimate lower bound of capacity needed
1612 let (lower, _) = self.size_hint();
1613 let mut result = String::with_capacity(sep.len() * lower);
1614 write!(&mut result, "{}", first_elt).unwrap();
1615 for elt in self {
1616 result.push_str(sep);
1617 write!(&mut result, "{}", elt).unwrap();
1618 }
1619 result
1620 }
1621 }
1622 }
1623
1624 /// Format all iterator elements, separated by `sep`.
1625 ///
1626 /// All elements are formatted (any formatting trait)
1627 /// with `sep` inserted between each element.
1628 ///
1629 /// **Panics** if the formatter helper is formatted more than once.
1630 ///
1631 /// ```
1632 /// use itertools::Itertools;
1633 ///
1634 /// let data = [1.1, 2.71828, -3.];
1635 /// assert_eq!(
1636 /// format!("{:.2}", data.iter().format(", ")),
1637 /// "1.10, 2.72, -3.00");
1638 /// ```
format(self, sep: &str) -> Format<Self> where Self: Sized,1639 fn format(self, sep: &str) -> Format<Self>
1640 where Self: Sized,
1641 {
1642 format::new_format_default(self, sep)
1643 }
1644
1645 /// Format all iterator elements, separated by `sep`.
1646 ///
1647 /// This is a customizable version of `.format()`.
1648 ///
1649 /// The supplied closure `format` is called once per iterator element,
1650 /// with two arguments: the element and a callback that takes a
1651 /// `&Display` value, i.e. any reference to type that implements `Display`.
1652 ///
1653 /// Using `&format_args!(...)` is the most versatile way to apply custom
1654 /// element formatting. The callback can be called multiple times if needed.
1655 ///
1656 /// **Panics** if the formatter helper is formatted more than once.
1657 ///
1658 /// ```
1659 /// use itertools::Itertools;
1660 ///
1661 /// let data = [1.1, 2.71828, -3.];
1662 /// let data_formatter = data.iter().format_with(", ", |elt, f| f(&format_args!("{:.2}", elt)));
1663 /// assert_eq!(format!("{}", data_formatter),
1664 /// "1.10, 2.72, -3.00");
1665 ///
1666 /// // .format_with() is recursively composable
1667 /// let matrix = [[1., 2., 3.],
1668 /// [4., 5., 6.]];
1669 /// let matrix_formatter = matrix.iter().format_with("\n", |row, f| {
1670 /// f(&row.iter().format_with(", ", |elt, g| g(&elt)))
1671 /// });
1672 /// assert_eq!(format!("{}", matrix_formatter),
1673 /// "1, 2, 3\n4, 5, 6");
1674 ///
1675 ///
1676 /// ```
format_with<F>(self, sep: &str, format: F) -> FormatWith<Self, F> where Self: Sized, F: FnMut(Self::Item, &mut dyn FnMut(&dyn fmt::Display) -> fmt::Result) -> fmt::Result,1677 fn format_with<F>(self, sep: &str, format: F) -> FormatWith<Self, F>
1678 where Self: Sized,
1679 F: FnMut(Self::Item, &mut dyn FnMut(&dyn fmt::Display) -> fmt::Result) -> fmt::Result,
1680 {
1681 format::new_format(self, sep, format)
1682 }
1683
1684 /// Fold `Result` values from an iterator.
1685 ///
1686 /// Only `Ok` values are folded. If no error is encountered, the folded
1687 /// value is returned inside `Ok`. Otherwise, the operation terminates
1688 /// and returns the first `Err` value it encounters. No iterator elements are
1689 /// consumed after the first error.
1690 ///
1691 /// The first accumulator value is the `start` parameter.
1692 /// Each iteration passes the accumulator value and the next value inside `Ok`
1693 /// to the fold function `f` and its return value becomes the new accumulator value.
1694 ///
1695 /// For example the sequence *Ok(1), Ok(2), Ok(3)* will result in a
1696 /// computation like this:
1697 ///
1698 /// ```ignore
1699 /// let mut accum = start;
1700 /// accum = f(accum, 1);
1701 /// accum = f(accum, 2);
1702 /// accum = f(accum, 3);
1703 /// ```
1704 ///
1705 /// With a `start` value of 0 and an addition as folding function,
1706 /// this effectively results in *((0 + 1) + 2) + 3*
1707 ///
1708 /// ```
1709 /// use std::ops::Add;
1710 /// use itertools::Itertools;
1711 ///
1712 /// let values = [1, 2, -2, -1, 2, 1];
1713 /// assert_eq!(
1714 /// values.iter()
1715 /// .map(Ok::<_, ()>)
1716 /// .fold_results(0, Add::add),
1717 /// Ok(3)
1718 /// );
1719 /// assert!(
1720 /// values.iter()
1721 /// .map(|&x| if x >= 0 { Ok(x) } else { Err("Negative number") })
1722 /// .fold_results(0, Add::add)
1723 /// .is_err()
1724 /// );
1725 /// ```
fold_results<A, E, B, F>(&mut self, mut start: B, mut f: F) -> Result<B, E> where Self: Iterator<Item = Result<A, E>>, F: FnMut(B, A) -> B1726 fn fold_results<A, E, B, F>(&mut self, mut start: B, mut f: F) -> Result<B, E>
1727 where Self: Iterator<Item = Result<A, E>>,
1728 F: FnMut(B, A) -> B
1729 {
1730 for elt in self {
1731 match elt {
1732 Ok(v) => start = f(start, v),
1733 Err(u) => return Err(u),
1734 }
1735 }
1736 Ok(start)
1737 }
1738
1739 /// Fold `Option` values from an iterator.
1740 ///
1741 /// Only `Some` values are folded. If no `None` is encountered, the folded
1742 /// value is returned inside `Some`. Otherwise, the operation terminates
1743 /// and returns `None`. No iterator elements are consumed after the `None`.
1744 ///
1745 /// This is the `Option` equivalent to `fold_results`.
1746 ///
1747 /// ```
1748 /// use std::ops::Add;
1749 /// use itertools::Itertools;
1750 ///
1751 /// let mut values = vec![Some(1), Some(2), Some(-2)].into_iter();
1752 /// assert_eq!(values.fold_options(5, Add::add), Some(5 + 1 + 2 - 2));
1753 ///
1754 /// let mut more_values = vec![Some(2), None, Some(0)].into_iter();
1755 /// assert!(more_values.fold_options(0, Add::add).is_none());
1756 /// assert_eq!(more_values.next().unwrap(), Some(0));
1757 /// ```
fold_options<A, B, F>(&mut self, mut start: B, mut f: F) -> Option<B> where Self: Iterator<Item = Option<A>>, F: FnMut(B, A) -> B1758 fn fold_options<A, B, F>(&mut self, mut start: B, mut f: F) -> Option<B>
1759 where Self: Iterator<Item = Option<A>>,
1760 F: FnMut(B, A) -> B
1761 {
1762 for elt in self {
1763 match elt {
1764 Some(v) => start = f(start, v),
1765 None => return None,
1766 }
1767 }
1768 Some(start)
1769 }
1770
1771 /// Accumulator of the elements in the iterator.
1772 ///
1773 /// Like `.fold()`, without a base case. If the iterator is
1774 /// empty, return `None`. With just one element, return it.
1775 /// Otherwise elements are accumulated in sequence using the closure `f`.
1776 ///
1777 /// ```
1778 /// use itertools::Itertools;
1779 ///
1780 /// assert_eq!((0..10).fold1(|x, y| x + y).unwrap_or(0), 45);
1781 /// assert_eq!((0..0).fold1(|x, y| x * y), None);
1782 /// ```
fold1<F>(mut self, f: F) -> Option<Self::Item> where F: FnMut(Self::Item, Self::Item) -> Self::Item, Self: Sized,1783 fn fold1<F>(mut self, f: F) -> Option<Self::Item>
1784 where F: FnMut(Self::Item, Self::Item) -> Self::Item,
1785 Self: Sized,
1786 {
1787 self.next().map(move |x| self.fold(x, f))
1788 }
1789
1790 /// Accumulate the elements in the iterator in a tree-like manner.
1791 ///
1792 /// You can think of it as, while there's more than one item, repeatedly
1793 /// combining adjacent items. It does so in bottom-up-merge-sort order,
1794 /// however, so that it needs only logarithmic stack space.
1795 ///
1796 /// This produces a call tree like the following (where the calls under
1797 /// an item are done after reading that item):
1798 ///
1799 /// ```text
1800 /// 1 2 3 4 5 6 7
1801 /// │ │ │ │ │ │ │
1802 /// └─f └─f └─f │
1803 /// │ │ │ │
1804 /// └───f └─f
1805 /// │ │
1806 /// └─────f
1807 /// ```
1808 ///
1809 /// Which, for non-associative functions, will typically produce a different
1810 /// result than the linear call tree used by `fold1`:
1811 ///
1812 /// ```text
1813 /// 1 2 3 4 5 6 7
1814 /// │ │ │ │ │ │ │
1815 /// └─f─f─f─f─f─f
1816 /// ```
1817 ///
1818 /// If `f` is associative, prefer the normal `fold1` instead.
1819 ///
1820 /// ```
1821 /// use itertools::Itertools;
1822 ///
1823 /// // The same tree as above
1824 /// let num_strings = (1..8).map(|x| x.to_string());
1825 /// assert_eq!(num_strings.tree_fold1(|x, y| format!("f({}, {})", x, y)),
1826 /// Some(String::from("f(f(f(1, 2), f(3, 4)), f(f(5, 6), 7))")));
1827 ///
1828 /// // Like fold1, an empty iterator produces None
1829 /// assert_eq!((0..0).tree_fold1(|x, y| x * y), None);
1830 ///
1831 /// // tree_fold1 matches fold1 for associative operations...
1832 /// assert_eq!((0..10).tree_fold1(|x, y| x + y),
1833 /// (0..10).fold1(|x, y| x + y));
1834 /// // ...but not for non-associative ones
1835 /// assert_ne!((0..10).tree_fold1(|x, y| x - y),
1836 /// (0..10).fold1(|x, y| x - y));
1837 /// ```
tree_fold1<F>(mut self, mut f: F) -> Option<Self::Item> where F: FnMut(Self::Item, Self::Item) -> Self::Item, Self: Sized,1838 fn tree_fold1<F>(mut self, mut f: F) -> Option<Self::Item>
1839 where F: FnMut(Self::Item, Self::Item) -> Self::Item,
1840 Self: Sized,
1841 {
1842 type State<T> = Result<T, Option<T>>;
1843
1844 fn inner0<T, II, FF>(it: &mut II, f: &mut FF) -> State<T>
1845 where
1846 II: Iterator<Item = T>,
1847 FF: FnMut(T, T) -> T
1848 {
1849 // This function could be replaced with `it.next().ok_or(None)`,
1850 // but half the useful tree_fold1 work is combining adjacent items,
1851 // so put that in a form that LLVM is more likely to optimize well.
1852
1853 let a =
1854 if let Some(v) = it.next() { v }
1855 else { return Err(None) };
1856 let b =
1857 if let Some(v) = it.next() { v }
1858 else { return Err(Some(a)) };
1859 Ok(f(a, b))
1860 }
1861
1862 fn inner<T, II, FF>(stop: usize, it: &mut II, f: &mut FF) -> State<T>
1863 where
1864 II: Iterator<Item = T>,
1865 FF: FnMut(T, T) -> T
1866 {
1867 let mut x = inner0(it, f)?;
1868 for height in 0..stop {
1869 // Try to get another tree the same size with which to combine it,
1870 // creating a new tree that's twice as big for next time around.
1871 let next =
1872 if height == 0 {
1873 inner0(it, f)
1874 } else {
1875 inner(height, it, f)
1876 };
1877 match next {
1878 Ok(y) => x = f(x, y),
1879
1880 // If we ran out of items, combine whatever we did manage
1881 // to get. It's better combined with the current value
1882 // than something in a parent frame, because the tree in
1883 // the parent is always as least as big as this one.
1884 Err(None) => return Err(Some(x)),
1885 Err(Some(y)) => return Err(Some(f(x, y))),
1886 }
1887 }
1888 Ok(x)
1889 }
1890
1891 match inner(usize::max_value(), &mut self, &mut f) {
1892 Err(x) => x,
1893 _ => unreachable!(),
1894 }
1895 }
1896
1897 /// An iterator method that applies a function, producing a single, final value.
1898 ///
1899 /// `fold_while()` is basically equivalent to `fold()` but with additional support for
1900 /// early exit via short-circuiting.
1901 ///
1902 /// ```
1903 /// use itertools::Itertools;
1904 /// use itertools::FoldWhile::{Continue, Done};
1905 ///
1906 /// let numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
1907 ///
1908 /// let mut result = 0;
1909 ///
1910 /// // for loop:
1911 /// for i in &numbers {
1912 /// if *i > 5 {
1913 /// break;
1914 /// }
1915 /// result = result + i;
1916 /// }
1917 ///
1918 /// // fold:
1919 /// let result2 = numbers.iter().fold(0, |acc, x| {
1920 /// if *x > 5 { acc } else { acc + x }
1921 /// });
1922 ///
1923 /// // fold_while:
1924 /// let result3 = numbers.iter().fold_while(0, |acc, x| {
1925 /// if *x > 5 { Done(acc) } else { Continue(acc + x) }
1926 /// }).into_inner();
1927 ///
1928 /// // they're the same
1929 /// assert_eq!(result, result2);
1930 /// assert_eq!(result2, result3);
1931 /// ```
1932 ///
1933 /// The big difference between the computations of `result2` and `result3` is that while
1934 /// `fold()` called the provided closure for every item of the callee iterator,
1935 /// `fold_while()` actually stopped iterating as soon as it encountered `Fold::Done(_)`.
1936 #[deprecated(note="Use .try_fold() instead", since="0.8")]
fold_while<B, F>(&mut self, init: B, mut f: F) -> FoldWhile<B> where Self: Sized, F: FnMut(B, Self::Item) -> FoldWhile<B>1937 fn fold_while<B, F>(&mut self, init: B, mut f: F) -> FoldWhile<B>
1938 where Self: Sized,
1939 F: FnMut(B, Self::Item) -> FoldWhile<B>
1940 {
1941 let mut acc = init;
1942 while let Some(item) = self.next() {
1943 match f(acc, item) {
1944 FoldWhile::Continue(res) => acc = res,
1945 res @ FoldWhile::Done(_) => return res,
1946 }
1947 }
1948 FoldWhile::Continue(acc)
1949 }
1950
1951 /// Iterate over the entire iterator and add all the elements.
1952 ///
1953 /// An empty iterator returns `None`, otherwise `Some(sum)`.
1954 ///
1955 /// # Panics
1956 ///
1957 /// When calling `sum1()` and a primitive integer type is being returned, this
1958 /// method will panic if the computation overflows and debug assertions are
1959 /// enabled.
1960 ///
1961 /// # Examples
1962 ///
1963 /// ```
1964 /// use itertools::Itertools;
1965 ///
1966 /// let empty_sum = (1..1).sum1::<i32>();
1967 /// assert_eq!(empty_sum, None);
1968 ///
1969 /// let nonempty_sum = (1..11).sum1::<i32>();
1970 /// assert_eq!(nonempty_sum, Some(55));
1971 /// ```
sum1<S>(mut self) -> Option<S> where Self: Sized, S: std::iter::Sum<Self::Item>,1972 fn sum1<S>(mut self) -> Option<S>
1973 where Self: Sized,
1974 S: std::iter::Sum<Self::Item>,
1975 {
1976 self.next()
1977 .map(|first| once(first).chain(self).sum())
1978 }
1979
1980 /// Iterate over the entire iterator and multiply all the elements.
1981 ///
1982 /// An empty iterator returns `None`, otherwise `Some(product)`.
1983 ///
1984 /// # Panics
1985 ///
1986 /// When calling `product1()` and a primitive integer type is being returned,
1987 /// method will panic if the computation overflows and debug assertions are
1988 /// enabled.
1989 ///
1990 /// # Examples
1991 /// ```
1992 /// use itertools::Itertools;
1993 ///
1994 /// let empty_product = (1..1).product1::<i32>();
1995 /// assert_eq!(empty_product, None);
1996 ///
1997 /// let nonempty_product = (1..11).product1::<i32>();
1998 /// assert_eq!(nonempty_product, Some(3628800));
1999 /// ```
product1<P>(mut self) -> Option<P> where Self: Sized, P: std::iter::Product<Self::Item>,2000 fn product1<P>(mut self) -> Option<P>
2001 where Self: Sized,
2002 P: std::iter::Product<Self::Item>,
2003 {
2004 self.next()
2005 .map(|first| once(first).chain(self).product())
2006 }
2007
2008
2009 /// Sort all iterator elements into a new iterator in ascending order.
2010 ///
2011 /// **Note:** This consumes the entire iterator, uses the
2012 /// `slice::sort()` method and returns the result as a new
2013 /// iterator that owns its elements.
2014 ///
2015 /// The sorted iterator, if directly collected to a `Vec`, is converted
2016 /// without any extra copying or allocation cost.
2017 ///
2018 /// ```
2019 /// use itertools::Itertools;
2020 ///
2021 /// // sort the letters of the text in ascending order
2022 /// let text = "bdacfe";
2023 /// itertools::assert_equal(text.chars().sorted(),
2024 /// "abcdef".chars());
2025 /// ```
2026 #[cfg(feature = "use_std")]
sorted(self) -> VecIntoIter<Self::Item> where Self: Sized, Self::Item: Ord2027 fn sorted(self) -> VecIntoIter<Self::Item>
2028 where Self: Sized,
2029 Self::Item: Ord
2030 {
2031 // Use .sort() directly since it is not quite identical with
2032 // .sort_by(Ord::cmp)
2033 let mut v = Vec::from_iter(self);
2034 v.sort();
2035 v.into_iter()
2036 }
2037
2038 /// Sort all iterator elements into a new iterator in ascending order.
2039 ///
2040 /// **Note:** This consumes the entire iterator, uses the
2041 /// `slice::sort_by()` method and returns the result as a new
2042 /// iterator that owns its elements.
2043 ///
2044 /// The sorted iterator, if directly collected to a `Vec`, is converted
2045 /// without any extra copying or allocation cost.
2046 ///
2047 /// ```
2048 /// use itertools::Itertools;
2049 ///
2050 /// // sort people in descending order by age
2051 /// let people = vec![("Jane", 20), ("John", 18), ("Jill", 30), ("Jack", 27)];
2052 ///
2053 /// let oldest_people_first = people
2054 /// .into_iter()
2055 /// .sorted_by(|a, b| Ord::cmp(&b.1, &a.1))
2056 /// .map(|(person, _age)| person);
2057 ///
2058 /// itertools::assert_equal(oldest_people_first,
2059 /// vec!["Jill", "Jack", "Jane", "John"]);
2060 /// ```
2061 #[cfg(feature = "use_std")]
sorted_by<F>(self, cmp: F) -> VecIntoIter<Self::Item> where Self: Sized, F: FnMut(&Self::Item, &Self::Item) -> Ordering,2062 fn sorted_by<F>(self, cmp: F) -> VecIntoIter<Self::Item>
2063 where Self: Sized,
2064 F: FnMut(&Self::Item, &Self::Item) -> Ordering,
2065 {
2066 let mut v = Vec::from_iter(self);
2067 v.sort_by(cmp);
2068 v.into_iter()
2069 }
2070
2071 /// Sort all iterator elements into a new iterator in ascending order.
2072 ///
2073 /// **Note:** This consumes the entire iterator, uses the
2074 /// `slice::sort_by_key()` method and returns the result as a new
2075 /// iterator that owns its elements.
2076 ///
2077 /// The sorted iterator, if directly collected to a `Vec`, is converted
2078 /// without any extra copying or allocation cost.
2079 ///
2080 /// ```
2081 /// use itertools::Itertools;
2082 ///
2083 /// // sort people in descending order by age
2084 /// let people = vec![("Jane", 20), ("John", 18), ("Jill", 30), ("Jack", 27)];
2085 ///
2086 /// let oldest_people_first = people
2087 /// .into_iter()
2088 /// .sorted_by_key(|x| -x.1)
2089 /// .map(|(person, _age)| person);
2090 ///
2091 /// itertools::assert_equal(oldest_people_first,
2092 /// vec!["Jill", "Jack", "Jane", "John"]);
2093 /// ```
2094 #[cfg(feature = "use_std")]
sorted_by_key<K, F>(self, f: F) -> VecIntoIter<Self::Item> where Self: Sized, K: Ord, F: FnMut(&Self::Item) -> K,2095 fn sorted_by_key<K, F>(self, f: F) -> VecIntoIter<Self::Item>
2096 where Self: Sized,
2097 K: Ord,
2098 F: FnMut(&Self::Item) -> K,
2099 {
2100 let mut v = Vec::from_iter(self);
2101 v.sort_by_key(f);
2102 v.into_iter()
2103 }
2104
2105 /// Collect all iterator elements into one of two
2106 /// partitions. Unlike `Iterator::partition`, each partition may
2107 /// have a distinct type.
2108 ///
2109 /// ```
2110 /// use itertools::{Itertools, Either};
2111 ///
2112 /// let successes_and_failures = vec![Ok(1), Err(false), Err(true), Ok(2)];
2113 ///
2114 /// let (successes, failures): (Vec<_>, Vec<_>) = successes_and_failures
2115 /// .into_iter()
2116 /// .partition_map(|r| {
2117 /// match r {
2118 /// Ok(v) => Either::Left(v),
2119 /// Err(v) => Either::Right(v),
2120 /// }
2121 /// });
2122 ///
2123 /// assert_eq!(successes, [1, 2]);
2124 /// assert_eq!(failures, [false, true]);
2125 /// ```
partition_map<A, B, F, L, R>(self, mut predicate: F) -> (A, B) where Self: Sized, F: FnMut(Self::Item) -> Either<L, R>, A: Default + Extend<L>, B: Default + Extend<R>,2126 fn partition_map<A, B, F, L, R>(self, mut predicate: F) -> (A, B)
2127 where Self: Sized,
2128 F: FnMut(Self::Item) -> Either<L, R>,
2129 A: Default + Extend<L>,
2130 B: Default + Extend<R>,
2131 {
2132 let mut left = A::default();
2133 let mut right = B::default();
2134
2135 self.for_each(|val| match predicate(val) {
2136 Either::Left(v) => left.extend(Some(v)),
2137 Either::Right(v) => right.extend(Some(v)),
2138 });
2139
2140 (left, right)
2141 }
2142
2143 /// Return a `HashMap` of keys mapped to `Vec`s of values. Keys and values
2144 /// are taken from `(Key, Value)` tuple pairs yielded by the input iterator.
2145 ///
2146 /// ```
2147 /// use itertools::Itertools;
2148 ///
2149 /// let data = vec![(0, 10), (2, 12), (3, 13), (0, 20), (3, 33), (2, 42)];
2150 /// let lookup = data.into_iter().into_group_map();
2151 ///
2152 /// assert_eq!(lookup[&0], vec![10, 20]);
2153 /// assert_eq!(lookup.get(&1), None);
2154 /// assert_eq!(lookup[&2], vec![12, 42]);
2155 /// assert_eq!(lookup[&3], vec![13, 33]);
2156 /// ```
2157 #[cfg(feature = "use_std")]
into_group_map<K, V>(self) -> HashMap<K, Vec<V>> where Self: Iterator<Item=(K, V)> + Sized, K: Hash + Eq,2158 fn into_group_map<K, V>(self) -> HashMap<K, Vec<V>>
2159 where Self: Iterator<Item=(K, V)> + Sized,
2160 K: Hash + Eq,
2161 {
2162 group_map::into_group_map(self)
2163 }
2164
2165 /// Return the minimum and maximum elements in the iterator.
2166 ///
2167 /// The return type `MinMaxResult` is an enum of three variants:
2168 ///
2169 /// - `NoElements` if the iterator is empty.
2170 /// - `OneElement(x)` if the iterator has exactly one element.
2171 /// - `MinMax(x, y)` is returned otherwise, where `x <= y`. Two
2172 /// values are equal if and only if there is more than one
2173 /// element in the iterator and all elements are equal.
2174 ///
2175 /// On an iterator of length `n`, `minmax` does `1.5 * n` comparisons,
2176 /// and so is faster than calling `min` and `max` separately which does
2177 /// `2 * n` comparisons.
2178 ///
2179 /// # Examples
2180 ///
2181 /// ```
2182 /// use itertools::Itertools;
2183 /// use itertools::MinMaxResult::{NoElements, OneElement, MinMax};
2184 ///
2185 /// let a: [i32; 0] = [];
2186 /// assert_eq!(a.iter().minmax(), NoElements);
2187 ///
2188 /// let a = [1];
2189 /// assert_eq!(a.iter().minmax(), OneElement(&1));
2190 ///
2191 /// let a = [1, 2, 3, 4, 5];
2192 /// assert_eq!(a.iter().minmax(), MinMax(&1, &5));
2193 ///
2194 /// let a = [1, 1, 1, 1];
2195 /// assert_eq!(a.iter().minmax(), MinMax(&1, &1));
2196 /// ```
2197 ///
2198 /// The elements can be floats but no particular result is guaranteed
2199 /// if an element is NaN.
minmax(self) -> MinMaxResult<Self::Item> where Self: Sized, Self::Item: PartialOrd2200 fn minmax(self) -> MinMaxResult<Self::Item>
2201 where Self: Sized, Self::Item: PartialOrd
2202 {
2203 minmax::minmax_impl(self, |_| (), |x, y, _, _| x < y)
2204 }
2205
2206 /// Return the minimum and maximum element of an iterator, as determined by
2207 /// the specified function.
2208 ///
2209 /// The return value is a variant of `MinMaxResult` like for `minmax()`.
2210 ///
2211 /// For the minimum, the first minimal element is returned. For the maximum,
2212 /// the last maximal element wins. This matches the behavior of the standard
2213 /// `Iterator::min()` and `Iterator::max()` methods.
2214 ///
2215 /// The keys can be floats but no particular result is guaranteed
2216 /// if a key is NaN.
minmax_by_key<K, F>(self, key: F) -> MinMaxResult<Self::Item> where Self: Sized, K: PartialOrd, F: FnMut(&Self::Item) -> K2217 fn minmax_by_key<K, F>(self, key: F) -> MinMaxResult<Self::Item>
2218 where Self: Sized, K: PartialOrd, F: FnMut(&Self::Item) -> K
2219 {
2220 minmax::minmax_impl(self, key, |_, _, xk, yk| xk < yk)
2221 }
2222
2223 /// Return the minimum and maximum element of an iterator, as determined by
2224 /// the specified comparison function.
2225 ///
2226 /// The return value is a variant of `MinMaxResult` like for `minmax()`.
2227 ///
2228 /// For the minimum, the first minimal element is returned. For the maximum,
2229 /// the last maximal element wins. This matches the behavior of the standard
2230 /// `Iterator::min()` and `Iterator::max()` methods.
minmax_by<F>(self, mut compare: F) -> MinMaxResult<Self::Item> where Self: Sized, F: FnMut(&Self::Item, &Self::Item) -> Ordering2231 fn minmax_by<F>(self, mut compare: F) -> MinMaxResult<Self::Item>
2232 where Self: Sized, F: FnMut(&Self::Item, &Self::Item) -> Ordering
2233 {
2234 minmax::minmax_impl(
2235 self,
2236 |_| (),
2237 |x, y, _, _| Ordering::Less == compare(x, y)
2238 )
2239 }
2240
2241 /// Return the position of the maximum element in the iterator.
2242 ///
2243 /// If several elements are equally maximum, the position of the
2244 /// last of them is returned.
2245 ///
2246 /// # Examples
2247 ///
2248 /// ```
2249 /// use itertools::Itertools;
2250 ///
2251 /// let a: [i32; 0] = [];
2252 /// assert_eq!(a.iter().position_max(), None);
2253 ///
2254 /// let a = [-3, 0, 1, 5, -10];
2255 /// assert_eq!(a.iter().position_max(), Some(3));
2256 ///
2257 /// let a = [1, 1, -1, -1];
2258 /// assert_eq!(a.iter().position_max(), Some(1));
2259 /// ```
position_max(self) -> Option<usize> where Self: Sized, Self::Item: Ord2260 fn position_max(self) -> Option<usize>
2261 where Self: Sized, Self::Item: Ord
2262 {
2263 self.enumerate()
2264 .max_by(|x, y| Ord::cmp(&x.1, &y.1))
2265 .map(|x| x.0)
2266 }
2267
2268 /// Return the position of the maximum element in the iterator, as
2269 /// determined by the specified function.
2270 ///
2271 /// If several elements are equally maximum, the position of the
2272 /// last of them is returned.
2273 ///
2274 /// # Examples
2275 ///
2276 /// ```
2277 /// use itertools::Itertools;
2278 ///
2279 /// let a: [i32; 0] = [];
2280 /// assert_eq!(a.iter().position_max_by_key(|x| x.abs()), None);
2281 ///
2282 /// let a = [-3_i32, 0, 1, 5, -10];
2283 /// assert_eq!(a.iter().position_max_by_key(|x| x.abs()), Some(4));
2284 ///
2285 /// let a = [1_i32, 1, -1, -1];
2286 /// assert_eq!(a.iter().position_max_by_key(|x| x.abs()), Some(3));
2287 /// ```
position_max_by_key<K, F>(self, mut key: F) -> Option<usize> where Self: Sized, K: Ord, F: FnMut(&Self::Item) -> K2288 fn position_max_by_key<K, F>(self, mut key: F) -> Option<usize>
2289 where Self: Sized, K: Ord, F: FnMut(&Self::Item) -> K
2290 {
2291 self.enumerate()
2292 .max_by(|x, y| Ord::cmp(&key(&x.1), &key(&y.1)))
2293 .map(|x| x.0)
2294 }
2295
2296 /// Return the position of the maximum element in the iterator, as
2297 /// determined by the specified comparison function.
2298 ///
2299 /// If several elements are equally maximum, the position of the
2300 /// last of them is returned.
2301 ///
2302 /// # Examples
2303 ///
2304 /// ```
2305 /// use itertools::Itertools;
2306 ///
2307 /// let a: [i32; 0] = [];
2308 /// assert_eq!(a.iter().position_max_by(|x, y| x.cmp(y)), None);
2309 ///
2310 /// let a = [-3_i32, 0, 1, 5, -10];
2311 /// assert_eq!(a.iter().position_max_by(|x, y| x.cmp(y)), Some(3));
2312 ///
2313 /// let a = [1_i32, 1, -1, -1];
2314 /// assert_eq!(a.iter().position_max_by(|x, y| x.cmp(y)), Some(1));
2315 /// ```
position_max_by<F>(self, mut compare: F) -> Option<usize> where Self: Sized, F: FnMut(&Self::Item, &Self::Item) -> Ordering2316 fn position_max_by<F>(self, mut compare: F) -> Option<usize>
2317 where Self: Sized, F: FnMut(&Self::Item, &Self::Item) -> Ordering
2318 {
2319 self.enumerate()
2320 .max_by(|x, y| compare(&x.1, &y.1))
2321 .map(|x| x.0)
2322 }
2323
2324 /// Return the position of the minimum element in the iterator.
2325 ///
2326 /// If several elements are equally minimum, the position of the
2327 /// first of them is returned.
2328 ///
2329 /// # Examples
2330 ///
2331 /// ```
2332 /// use itertools::Itertools;
2333 ///
2334 /// let a: [i32; 0] = [];
2335 /// assert_eq!(a.iter().position_min(), None);
2336 ///
2337 /// let a = [-3, 0, 1, 5, -10];
2338 /// assert_eq!(a.iter().position_min(), Some(4));
2339 ///
2340 /// let a = [1, 1, -1, -1];
2341 /// assert_eq!(a.iter().position_min(), Some(2));
2342 /// ```
position_min(self) -> Option<usize> where Self: Sized, Self::Item: Ord2343 fn position_min(self) -> Option<usize>
2344 where Self: Sized, Self::Item: Ord
2345 {
2346 self.enumerate()
2347 .min_by(|x, y| Ord::cmp(&x.1, &y.1))
2348 .map(|x| x.0)
2349 }
2350
2351 /// Return the position of the minimum element in the iterator, as
2352 /// determined by the specified function.
2353 ///
2354 /// If several elements are equally minimum, the position of the
2355 /// first of them is returned.
2356 ///
2357 /// # Examples
2358 ///
2359 /// ```
2360 /// use itertools::Itertools;
2361 ///
2362 /// let a: [i32; 0] = [];
2363 /// assert_eq!(a.iter().position_min_by_key(|x| x.abs()), None);
2364 ///
2365 /// let a = [-3_i32, 0, 1, 5, -10];
2366 /// assert_eq!(a.iter().position_min_by_key(|x| x.abs()), Some(1));
2367 ///
2368 /// let a = [1_i32, 1, -1, -1];
2369 /// assert_eq!(a.iter().position_min_by_key(|x| x.abs()), Some(0));
2370 /// ```
position_min_by_key<K, F>(self, mut key: F) -> Option<usize> where Self: Sized, K: Ord, F: FnMut(&Self::Item) -> K2371 fn position_min_by_key<K, F>(self, mut key: F) -> Option<usize>
2372 where Self: Sized, K: Ord, F: FnMut(&Self::Item) -> K
2373 {
2374 self.enumerate()
2375 .min_by(|x, y| Ord::cmp(&key(&x.1), &key(&y.1)))
2376 .map(|x| x.0)
2377 }
2378
2379 /// Return the position of the minimum element in the iterator, as
2380 /// determined by the specified comparison function.
2381 ///
2382 /// If several elements are equally minimum, the position of the
2383 /// first of them is returned.
2384 ///
2385 /// # Examples
2386 ///
2387 /// ```
2388 /// use itertools::Itertools;
2389 ///
2390 /// let a: [i32; 0] = [];
2391 /// assert_eq!(a.iter().position_min_by(|x, y| x.cmp(y)), None);
2392 ///
2393 /// let a = [-3_i32, 0, 1, 5, -10];
2394 /// assert_eq!(a.iter().position_min_by(|x, y| x.cmp(y)), Some(4));
2395 ///
2396 /// let a = [1_i32, 1, -1, -1];
2397 /// assert_eq!(a.iter().position_min_by(|x, y| x.cmp(y)), Some(2));
2398 /// ```
position_min_by<F>(self, mut compare: F) -> Option<usize> where Self: Sized, F: FnMut(&Self::Item, &Self::Item) -> Ordering2399 fn position_min_by<F>(self, mut compare: F) -> Option<usize>
2400 where Self: Sized, F: FnMut(&Self::Item, &Self::Item) -> Ordering
2401 {
2402 self.enumerate()
2403 .min_by(|x, y| compare(&x.1, &y.1))
2404 .map(|x| x.0)
2405 }
2406
2407 /// Return the positions of the minimum and maximum elements in
2408 /// the iterator.
2409 ///
2410 /// The return type [`MinMaxResult`] is an enum of three variants:
2411 ///
2412 /// - `NoElements` if the iterator is empty.
2413 /// - `OneElement(xpos)` if the iterator has exactly one element.
2414 /// - `MinMax(xpos, ypos)` is returned otherwise, where the
2415 /// element at `xpos` ≤ the element at `ypos`. While the
2416 /// referenced elements themselves may be equal, `xpos` cannot
2417 /// be equal to `ypos`.
2418 ///
2419 /// On an iterator of length `n`, `position_minmax` does `1.5 * n`
2420 /// comparisons, and so is faster than calling `positon_min` and
2421 /// `position_max` separately which does `2 * n` comparisons.
2422 ///
2423 /// For the minimum, if several elements are equally minimum, the
2424 /// position of the first of them is returned. For the maximum, if
2425 /// several elements are equally maximum, the position of the last
2426 /// of them is returned.
2427 ///
2428 /// The elements can be floats but no particular result is
2429 /// guaranteed if an element is NaN.
2430 ///
2431 /// # Examples
2432 ///
2433 /// ```
2434 /// use itertools::Itertools;
2435 /// use itertools::MinMaxResult::{NoElements, OneElement, MinMax};
2436 ///
2437 /// let a: [i32; 0] = [];
2438 /// assert_eq!(a.iter().position_minmax(), NoElements);
2439 ///
2440 /// let a = [10];
2441 /// assert_eq!(a.iter().position_minmax(), OneElement(0));
2442 ///
2443 /// let a = [-3, 0, 1, 5, -10];
2444 /// assert_eq!(a.iter().position_minmax(), MinMax(4, 3));
2445 ///
2446 /// let a = [1, 1, -1, -1];
2447 /// assert_eq!(a.iter().position_minmax(), MinMax(2, 1));
2448 /// ```
2449 ///
2450 /// [`MinMaxResult`]: enum.MinMaxResult.html
position_minmax(self) -> MinMaxResult<usize> where Self: Sized, Self::Item: PartialOrd2451 fn position_minmax(self) -> MinMaxResult<usize>
2452 where Self: Sized, Self::Item: PartialOrd
2453 {
2454 use crate::MinMaxResult::{NoElements, OneElement, MinMax};
2455 match minmax::minmax_impl(self.enumerate(), |_| (), |x, y, _, _| x.1 < y.1) {
2456 NoElements => NoElements,
2457 OneElement(x) => OneElement(x.0),
2458 MinMax(x, y) => MinMax(x.0, y.0),
2459 }
2460 }
2461
2462 /// Return the postions of the minimum and maximum elements of an
2463 /// iterator, as determined by the specified function.
2464 ///
2465 /// The return value is a variant of [`MinMaxResult`] like for
2466 /// [`position_minmax`].
2467 ///
2468 /// For the minimum, if several elements are equally minimum, the
2469 /// position of the first of them is returned. For the maximum, if
2470 /// several elements are equally maximum, the position of the last
2471 /// of them is returned.
2472 ///
2473 /// The keys can be floats but no particular result is guaranteed
2474 /// if a key is NaN.
2475 ///
2476 /// # Examples
2477 ///
2478 /// ```
2479 /// use itertools::Itertools;
2480 /// use itertools::MinMaxResult::{NoElements, OneElement, MinMax};
2481 ///
2482 /// let a: [i32; 0] = [];
2483 /// assert_eq!(a.iter().position_minmax_by_key(|x| x.abs()), NoElements);
2484 ///
2485 /// let a = [10_i32];
2486 /// assert_eq!(a.iter().position_minmax_by_key(|x| x.abs()), OneElement(0));
2487 ///
2488 /// let a = [-3_i32, 0, 1, 5, -10];
2489 /// assert_eq!(a.iter().position_minmax_by_key(|x| x.abs()), MinMax(1, 4));
2490 ///
2491 /// let a = [1_i32, 1, -1, -1];
2492 /// assert_eq!(a.iter().position_minmax_by_key(|x| x.abs()), MinMax(0, 3));
2493 /// ```
2494 ///
2495 /// [`MinMaxResult`]: enum.MinMaxResult.html
2496 /// [`position_minmax`]: #method.position_minmax
position_minmax_by_key<K, F>(self, mut key: F) -> MinMaxResult<usize> where Self: Sized, K: PartialOrd, F: FnMut(&Self::Item) -> K2497 fn position_minmax_by_key<K, F>(self, mut key: F) -> MinMaxResult<usize>
2498 where Self: Sized, K: PartialOrd, F: FnMut(&Self::Item) -> K
2499 {
2500 use crate::MinMaxResult::{NoElements, OneElement, MinMax};
2501 match self.enumerate().minmax_by_key(|e| key(&e.1)) {
2502 NoElements => NoElements,
2503 OneElement(x) => OneElement(x.0),
2504 MinMax(x, y) => MinMax(x.0, y.0),
2505 }
2506 }
2507
2508 /// Return the postions of the minimum and maximum elements of an
2509 /// iterator, as determined by the specified comparison function.
2510 ///
2511 /// The return value is a variant of [`MinMaxResult`] like for
2512 /// [`position_minmax`].
2513 ///
2514 /// For the minimum, if several elements are equally minimum, the
2515 /// position of the first of them is returned. For the maximum, if
2516 /// several elements are equally maximum, the position of the last
2517 /// of them is returned.
2518 ///
2519 /// # Examples
2520 ///
2521 /// ```
2522 /// use itertools::Itertools;
2523 /// use itertools::MinMaxResult::{NoElements, OneElement, MinMax};
2524 ///
2525 /// let a: [i32; 0] = [];
2526 /// assert_eq!(a.iter().position_minmax_by(|x, y| x.cmp(y)), NoElements);
2527 ///
2528 /// let a = [10_i32];
2529 /// assert_eq!(a.iter().position_minmax_by(|x, y| x.cmp(y)), OneElement(0));
2530 ///
2531 /// let a = [-3_i32, 0, 1, 5, -10];
2532 /// assert_eq!(a.iter().position_minmax_by(|x, y| x.cmp(y)), MinMax(4, 3));
2533 ///
2534 /// let a = [1_i32, 1, -1, -1];
2535 /// assert_eq!(a.iter().position_minmax_by(|x, y| x.cmp(y)), MinMax(2, 1));
2536 /// ```
2537 ///
2538 /// [`MinMaxResult`]: enum.MinMaxResult.html
2539 /// [`position_minmax`]: #method.position_minmax
position_minmax_by<F>(self, mut compare: F) -> MinMaxResult<usize> where Self: Sized, F: FnMut(&Self::Item, &Self::Item) -> Ordering2540 fn position_minmax_by<F>(self, mut compare: F) -> MinMaxResult<usize>
2541 where Self: Sized, F: FnMut(&Self::Item, &Self::Item) -> Ordering
2542 {
2543 use crate::MinMaxResult::{NoElements, OneElement, MinMax};
2544 match self.enumerate().minmax_by(|x, y| compare(&x.1, &y.1)) {
2545 NoElements => NoElements,
2546 OneElement(x) => OneElement(x.0),
2547 MinMax(x, y) => MinMax(x.0, y.0),
2548 }
2549 }
2550
2551 /// If the iterator yields exactly one element, that element will be returned, otherwise
2552 /// an error will be returned containing an iterator that has the same output as the input
2553 /// iterator.
2554 ///
2555 /// This provides an additional layer of validation over just calling `Iterator::next()`.
2556 /// If your assumption that there should only be one element yielded is false this provides
2557 /// the opportunity to detect and handle that, preventing errors at a distance.
2558 ///
2559 /// # Examples
2560 /// ```
2561 /// use itertools::Itertools;
2562 ///
2563 /// assert_eq!((0..10).filter(|&x| x == 2).exactly_one().unwrap(), 2);
2564 /// assert!((0..10).filter(|&x| x > 1 && x < 4).exactly_one().unwrap_err().eq(2..4));
2565 /// assert!((0..10).filter(|&x| x > 1 && x < 5).exactly_one().unwrap_err().eq(2..5));
2566 /// assert!((0..10).filter(|&_| false).exactly_one().unwrap_err().eq(0..0));
2567 /// ```
exactly_one(mut self) -> Result<Self::Item, ExactlyOneError<Self>> where Self: Sized,2568 fn exactly_one(mut self) -> Result<Self::Item, ExactlyOneError<Self>>
2569 where
2570 Self: Sized,
2571 {
2572 match self.next() {
2573 Some(first) => {
2574 match self.next() {
2575 Some(second) => {
2576 Err(ExactlyOneError::new((Some(first), Some(second)), self))
2577 }
2578 None => {
2579 Ok(first)
2580 }
2581 }
2582 }
2583 None => Err(ExactlyOneError::new((None, None), self)),
2584 }
2585 }
2586 }
2587
2588 impl<T: ?Sized> Itertools for T where T: Iterator { }
2589
2590 /// Return `true` if both iterables produce equal sequences
2591 /// (elements pairwise equal and sequences of the same length),
2592 /// `false` otherwise.
2593 ///
2594 /// This is an `IntoIterator` enabled function that is similar to the standard
2595 /// library method `Iterator::eq`.
2596 ///
2597 /// ```
2598 /// assert!(itertools::equal(vec![1, 2, 3], 1..4));
2599 /// assert!(!itertools::equal(&[0, 0], &[0, 0, 0]));
2600 /// ```
equal<I, J>(a: I, b: J) -> bool where I: IntoIterator, J: IntoIterator, I::Item: PartialEq<J::Item>2601 pub fn equal<I, J>(a: I, b: J) -> bool
2602 where I: IntoIterator,
2603 J: IntoIterator,
2604 I::Item: PartialEq<J::Item>
2605 {
2606 let mut ia = a.into_iter();
2607 let mut ib = b.into_iter();
2608 loop {
2609 match ia.next() {
2610 Some(x) => match ib.next() {
2611 Some(y) => if x != y { return false; },
2612 None => return false,
2613 },
2614 None => return ib.next().is_none()
2615 }
2616 }
2617 }
2618
2619 /// Assert that two iterables produce equal sequences, with the same
2620 /// semantics as *equal(a, b)*.
2621 ///
2622 /// **Panics** on assertion failure with a message that shows the
2623 /// two iteration elements.
2624 ///
2625 /// ```ignore
2626 /// assert_equal("exceed".split('c'), "excess".split('c'));
2627 /// // ^PANIC: panicked at 'Failed assertion Some("eed") == Some("ess") for iteration 1',
2628 /// ```
assert_equal<I, J>(a: I, b: J) where I: IntoIterator, J: IntoIterator, I::Item: fmt::Debug + PartialEq<J::Item>, J::Item: fmt::Debug,2629 pub fn assert_equal<I, J>(a: I, b: J)
2630 where I: IntoIterator,
2631 J: IntoIterator,
2632 I::Item: fmt::Debug + PartialEq<J::Item>,
2633 J::Item: fmt::Debug,
2634 {
2635 let mut ia = a.into_iter();
2636 let mut ib = b.into_iter();
2637 let mut i = 0;
2638 loop {
2639 match (ia.next(), ib.next()) {
2640 (None, None) => return,
2641 (a, b) => {
2642 let equal = match (&a, &b) {
2643 (&Some(ref a), &Some(ref b)) => a == b,
2644 _ => false,
2645 };
2646 assert!(equal, "Failed assertion {a:?} == {b:?} for iteration {i}",
2647 i=i, a=a, b=b);
2648 i += 1;
2649 }
2650 }
2651 }
2652 }
2653
2654 /// Partition a sequence using predicate `pred` so that elements
2655 /// that map to `true` are placed before elements which map to `false`.
2656 ///
2657 /// The order within the partitions is arbitrary.
2658 ///
2659 /// Return the index of the split point.
2660 ///
2661 /// ```
2662 /// use itertools::partition;
2663 ///
2664 /// # // use repeated numbers to not promise any ordering
2665 /// let mut data = [7, 1, 1, 7, 1, 1, 7];
2666 /// let split_index = partition(&mut data, |elt| *elt >= 3);
2667 ///
2668 /// assert_eq!(data, [7, 7, 7, 1, 1, 1, 1]);
2669 /// assert_eq!(split_index, 3);
2670 /// ```
partition<'a, A: 'a, I, F>(iter: I, mut pred: F) -> usize where I: IntoIterator<Item = &'a mut A>, I::IntoIter: DoubleEndedIterator, F: FnMut(&A) -> bool2671 pub fn partition<'a, A: 'a, I, F>(iter: I, mut pred: F) -> usize
2672 where I: IntoIterator<Item = &'a mut A>,
2673 I::IntoIter: DoubleEndedIterator,
2674 F: FnMut(&A) -> bool
2675 {
2676 let mut split_index = 0;
2677 let mut iter = iter.into_iter();
2678 'main: while let Some(front) = iter.next() {
2679 if !pred(front) {
2680 loop {
2681 match iter.next_back() {
2682 Some(back) => if pred(back) {
2683 std::mem::swap(front, back);
2684 break;
2685 },
2686 None => break 'main,
2687 }
2688 }
2689 }
2690 split_index += 1;
2691 }
2692 split_index
2693 }
2694
2695 /// An enum used for controlling the execution of `.fold_while()`.
2696 ///
2697 /// See [`.fold_while()`](trait.Itertools.html#method.fold_while) for more information.
2698 #[derive(Copy, Clone, Debug, Eq, PartialEq)]
2699 pub enum FoldWhile<T> {
2700 /// Continue folding with this value
2701 Continue(T),
2702 /// Fold is complete and will return this value
2703 Done(T),
2704 }
2705
2706 impl<T> FoldWhile<T> {
2707 /// Return the value in the continue or done.
into_inner(self) -> T2708 pub fn into_inner(self) -> T {
2709 match self {
2710 FoldWhile::Continue(x) | FoldWhile::Done(x) => x,
2711 }
2712 }
2713
2714 /// Return true if `self` is `Done`, false if it is `Continue`.
is_done(&self) -> bool2715 pub fn is_done(&self) -> bool {
2716 match *self {
2717 FoldWhile::Continue(_) => false,
2718 FoldWhile::Done(_) => true,
2719 }
2720 }
2721 }
2722