1 #![warn(missing_docs)]
2 #![cfg_attr(feature = "unstable",
3 feature(
4 zero_one,
5 core_intrinsics,
6 ))]
7 #![crate_name="itertools"]
8
9 //! Itertools — extra iterator adaptors, functions and macros.
10 //!
11 //! To use the iterator methods in this crate, import the [`Itertools` trait](./trait.Itertools.html):
12 //!
13 //! ```ignore
14 //! use itertools::Itertools;
15 //! ```
16 //!
17 //! Some iterators or adaptors are used directly like regular structs, for example
18 //! [`PutBack`](./struct.PutBack.html), [`Unfold`](./struct.Unfold.html),
19 //! [`Zip`](./struct.Zip.html), [`Stride`](./struct.Stride.html)
20 //!
21 //! To enable the macros in this crate, use the `#[macro_use]` attribute:
22 //!
23 //! ```ignore
24 //! #[macro_use] extern crate itertools;
25 //! ```
26 //!
27 //! ## License
28 //! Dual-licensed to be compatible with the Rust project.
29 //!
30 //! Licensed under the Apache License, Version 2.0
31 //! http://www.apache.org/licenses/LICENSE-2.0 or the MIT license
32 //! http://opensource.org/licenses/MIT, at your
33 //! option. This file may not be copied, modified, or distributed
34 //! except according to those terms.
35 //!
36 //!
37
38 use std::iter::{self, IntoIterator};
39 use std::fmt::Write;
40 use std::cmp::Ordering;
41 use std::fmt;
42 use std::hash::Hash;
43
44 pub use adaptors::{
45 Dedup,
46 Interleave,
47 InterleaveShortest,
48 Product,
49 PutBack,
50 PutBackN,
51 Batching,
52 GroupBy,
53 Step,
54 Merge,
55 MergeBy,
56 MultiPeek,
57 TakeWhileRef,
58 WhileSome,
59 Coalesce,
60 MendSlices,
61 Combinations,
62 CombinationsN,
63 Unique,
64 UniqueBy,
65 Flatten,
66 };
67 #[cfg(feature = "unstable")]
68 #[cfg_attr(feature = "unstable", deprecated(note = "Uses deprecated libstd traits"))]
69 pub use adaptors::EnumerateFrom;
70 pub use diff::{diff_with, Diff};
71 pub use format::{Format, FormatDefault};
72 pub use free::{enumerate, rev};
73 pub use groupbylazy::{ChunksLazy, Chunk, Chunks, GroupByLazy, Group, Groups};
74 pub use intersperse::Intersperse;
75 pub use islice::ISlice;
76 pub use kmerge::KMerge;
77 #[cfg_attr(feature = "unstable", deprecated(note = "Will move to different crate"))]
78 pub use linspace::{linspace, Linspace};
79 pub use minmax::MinMaxResult;
80 pub use pad_tail::PadUsing;
81 pub use rciter::RcIter;
82 pub use repeatn::RepeatN;
83 pub use sources::{RepeatCall, Unfold};
84 #[cfg_attr(feature = "unstable", deprecated(note = "Will move to different crate"))]
85 pub use stride::Stride;
86 #[cfg_attr(feature = "unstable", deprecated(note = "Will move to different crate"))]
87 pub use stride::StrideMut;
88 pub use tee::Tee;
89 pub use zip_eq::ZipEq;
90 pub use zip_longest::{ZipLongest, EitherOrBoth};
91 pub use ziptuple::Zip;
92 #[cfg(feature = "unstable")]
93 #[cfg_attr(feature = "unstable", deprecated(note = "Will move to different crate"))]
94 pub use ziptrusted::{ZipTrusted, TrustedIterator};
95 #[cfg_attr(feature = "unstable", deprecated(note = "No longer has desired performance."))]
96 pub use zipslices::ZipSlices;
97 mod adaptors;
98 pub mod free;
99 mod format;
100 mod groupbylazy;
101 mod intersperse;
102 mod islice;
103 mod diff;
104 mod kmerge;
105 mod linspace;
106 mod minmax;
107 pub mod misc;
108 mod pad_tail;
109 mod rciter;
110 mod repeatn;
111 mod sources;
112 pub mod size_hint;
113 mod stride;
114 mod tee;
115 mod zip_eq;
116 mod zip_longest;
117 mod ziptuple;
118 #[cfg(feature = "unstable")]
119 mod ziptrusted;
120 mod zipslices;
121
122 /// The function pointer map iterator created with `.map_fn()`.
123 pub type MapFn<I, B> where I: Iterator = iter::Map<I, fn(I::Item) -> B>;
124
125 #[macro_export]
126 /// Create an iterator over the “cartesian product” of iterators.
127 ///
128 /// Iterator element type is like `(A, B, ..., E)` if formed
129 /// from iterators `(I, J, ..., M)` with element types `I::Item = A`, `J::Item = B`, etc.
130 ///
131 /// ```
132 /// #[macro_use] extern crate itertools;
133 /// # fn main() {
134 /// // Iterate over the coordinates of a 4 x 4 x 4 grid
135 /// // from (0, 0, 0), (0, 0, 1), .., (0, 1, 0), (0, 1, 1), .. etc until (3, 3, 3)
136 /// for (i, j, k) in iproduct!(0..4, 0..4, 0..4) {
137 /// // ..
138 /// }
139 /// # }
140 /// ```
141 macro_rules! iproduct {
142 (@flatten $I:expr,) => (
143 $I
144 );
145 (@flatten $I:expr, $J:expr, $($K:expr,)*) => (
146 iproduct!(@flatten $crate::misc::FlatTuples::new(iproduct!($I, $J)), $($K,)*)
147 );
148 ($I:expr) => (
149 (::std::iter::IntoIterator::into_iter($I))
150 );
151 ($I:expr, $J:expr) => (
152 $crate::Product::new(iproduct!($I), iproduct!($J))
153 );
154 ($I:expr, $J:expr, $($K:expr),+) => (
155 iproduct!(@flatten iproduct!($I, $J), $($K,)+)
156 );
157 }
158
159 #[macro_export]
160 /// Create an iterator running multiple iterators in lockstep.
161 ///
162 /// The izip! iterator yields elements until any subiterator
163 /// returns `None`.
164 ///
165 /// Iterator element type is like `(A, B, ..., E)` if formed
166 /// from iterators `(I, J, ..., M)` implementing `I: Iterator<A>`,
167 /// `J: Iterator<B>`, ..., `M: Iterator<E>`
168 ///
169 /// ```
170 /// #[macro_use] extern crate itertools;
171 /// # fn main() {
172 ///
173 /// // Iterate over three sequences side-by-side
174 /// let mut xs = [0, 0, 0];
175 /// let ys = [69, 107, 101];
176 ///
177 /// for (i, a, b) in izip!(0..100, &mut xs, &ys) {
178 /// *a = i ^ *b;
179 /// }
180 ///
181 /// assert_eq!(xs, [69, 106, 103]);
182 /// # }
183 /// ```
184 macro_rules! izip {
185 ($I:expr) => (
186 (::std::iter::IntoIterator::into_iter($I))
187 );
188 ($($I:expr),*) => (
189 {
190 $crate::Zip::new(($(izip!($I)),*))
191 }
192 );
193 }
194
195 /// The trait `Itertools`: extra iterator adaptors and methods for iterators.
196 ///
197 /// This trait defines a number of methods. They are divided into two groups:
198 ///
199 /// * *Adaptors* take an iterator and parameter as input, and return
200 /// a new iterator value. These are listed first in the trait. An example
201 /// of an adaptor is [`.interleave()`](#method.interleave)
202 ///
203 /// * *Regular methods* are those that don't return iterators and instead
204 /// return a regular value of some other kind. [`.find_position()`](#method.find_position)
205 /// is an example and the first regular method in the list.
206 pub trait Itertools : Iterator {
207 // adaptors
208
209 /// Alternate elements from two iterators until both
210 /// run out.
211 ///
212 /// Iterator element type is `Self::Item`.
213 ///
214 /// This iterator is *fused*.
215 ///
216 /// ```
217 /// use itertools::Itertools;
218 ///
219 /// let it = (0..3).interleave(vec![7, 8]);
220 /// itertools::assert_equal(it, vec![0, 7, 1, 8, 2]);
221 /// ```
interleave<J>(self, other: J) -> Interleave<Self, J::IntoIter> where J: IntoIterator<Item = Self::Item>, Self: Sized222 fn interleave<J>(self, other: J) -> Interleave<Self, J::IntoIter>
223 where J: IntoIterator<Item = Self::Item>,
224 Self: Sized
225 {
226 Interleave::new(self, other.into_iter())
227 }
228
229 /// Alternate elements from two iterators until one of them runs out.
230 ///
231 /// Iterator element type is `Self::Item`.
232 ///
233 /// ```
234 /// use itertools::Itertools;
235 ///
236 /// let it = (0..5).interleave_shortest(vec![7, 8]);
237 /// itertools::assert_equal(it, vec![0, 7, 1, 8, 2]);
238 /// ```
interleave_shortest<J>(self, other: J) -> InterleaveShortest<Self, J::IntoIter> where J: IntoIterator<Item = Self::Item>, Self: Sized239 fn interleave_shortest<J>(self, other: J) -> InterleaveShortest<Self, J::IntoIter>
240 where J: IntoIterator<Item = Self::Item>,
241 Self: Sized
242 {
243 InterleaveShortest::new(self, other.into_iter())
244 }
245
246 /// An iterator adaptor to insert a particular value
247 /// between each element of the adapted iterator.
248 ///
249 /// Iterator element type is `Self::Item`.
250 ///
251 /// This iterator is *fused*.
252 ///
253 /// ```
254 /// use itertools::Itertools;
255 ///
256 /// itertools::assert_equal((0..3).intersperse(8), vec![0, 8, 1, 8, 2]);
257 /// ```
intersperse(self, element: Self::Item) -> Intersperse<Self> where Self: Sized, Self::Item: Clone258 fn intersperse(self, element: Self::Item) -> Intersperse<Self>
259 where Self: Sized,
260 Self::Item: Clone
261 {
262 Intersperse::new(self, element)
263 }
264
265 /// Create an iterator which iterates over both this and the specified
266 /// iterator simultaneously, yielding pairs of two optional elements.
267 ///
268 /// This iterator is *fused*.
269 ///
270 /// When both iterators return `None`, all further invocations of `.next()`
271 /// will return `None`.
272 ///
273 /// Iterator element type is
274 /// [`EitherOrBoth<Self::Item, J::Item>`](enum.EitherOrBoth.html).
275 ///
276 /// ```rust
277 /// use itertools::EitherOrBoth::{Both, Right};
278 /// use itertools::Itertools;
279 /// let it = (0..1).zip_longest(1..3);
280 /// itertools::assert_equal(it, vec![Both(0, 1), Right(2)]);
281 /// ```
282 #[inline]
zip_longest<J>(self, other: J) -> ZipLongest<Self, J::IntoIter> where J: IntoIterator, Self: Sized283 fn zip_longest<J>(self, other: J) -> ZipLongest<Self, J::IntoIter>
284 where J: IntoIterator,
285 Self: Sized
286 {
287 ZipLongest::new(self, other.into_iter())
288 }
289
290 /// Create an iterator which iterates over both this and the specified
291 /// iterator simultaneously, yielding pairs of elements.
292 ///
293 /// **Panics** if the iterators reach an end and they are not of equal
294 /// lengths.
295 #[inline]
zip_eq<J>(self, other: J) -> ZipEq<Self, J::IntoIter> where J: IntoIterator, Self: Sized296 fn zip_eq<J>(self, other: J) -> ZipEq<Self, J::IntoIter>
297 where J: IntoIterator,
298 Self: Sized
299 {
300 zip_eq::new(self, other.into_iter())
301 }
302
303 /// A “meta iterator adaptor”. Its closure recives a reference to the iterator
304 /// and may pick off as many elements as it likes, to produce the next iterator element.
305 ///
306 /// Iterator element type is `B`.
307 ///
308 /// ```
309 /// use itertools::Itertools;
310 ///
311 /// // An adaptor that gathers elements up in pairs
312 /// let pit = (0..4).batching(|mut it| {
313 /// match it.next() {
314 /// None => None,
315 /// Some(x) => match it.next() {
316 /// None => None,
317 /// Some(y) => Some((x, y)),
318 /// }
319 /// }
320 /// });
321 ///
322 /// itertools::assert_equal(pit, vec![(0, 1), (2, 3)]);
323 /// ```
324 ///
batching<B, F>(self, f: F) -> Batching<Self, F> where F: FnMut(&mut Self) -> Option<B>, Self: Sized325 fn batching<B, F>(self, f: F) -> Batching<Self, F>
326 where F: FnMut(&mut Self) -> Option<B>,
327 Self: Sized
328 {
329 Batching::new(self, f)
330 }
331
332 /// Group iterator elements. Consecutive elements that map to the same key (“runs”),
333 /// are returned as the iterator elements of `GroupBy`.
334 ///
335 /// Iterator element type is `(K, Vec<Self::Item>)`
336 ///
337 /// ```
338 /// use itertools::Itertools;
339 ///
340 /// // group data into runs of larger than zero or not.
341 /// let data = vec![1, 3, -2, -2, 1, 0, 1, 2];
342 /// // groups: |---->|------>|--------->|
343 ///
344 /// for (key, group) in data.into_iter().group_by(|elt| *elt >= 0) {
345 /// // Check that the sum of each group is +/- 4.
346 /// assert_eq!(4, group.iter().fold(0_i32, |a, b| a + b).abs());
347 /// }
348 /// ```
group_by<K, F>(self, key: F) -> GroupBy<K, Self, F> where Self: Sized, F: FnMut(&Self::Item) -> K,349 fn group_by<K, F>(self, key: F) -> GroupBy<K, Self, F>
350 where Self: Sized,
351 F: FnMut(&Self::Item) -> K,
352 {
353 GroupBy::new(self, key)
354 }
355
356
357 /// Return an iterable that can group iterator elements.
358 /// Consecutive elements that map to the same key (“runs”), are assigned
359 /// to the same group.
360 ///
361 /// `GroupByLazy` is the storage for the lazy grouping operation.
362 ///
363 /// If the groups are consumed in order, or if each group's iterator is
364 /// dropped without keeping it around, then `GroupByLazy` uses no
365 /// allocations. It needs allocations only if several group iterators
366 /// are alive at the same time.
367 ///
368 /// This type implements `IntoIterator` (it is **not** an iterator
369 /// itself), because the group iterators need to borrow from this
370 /// value. It should be stored in a local variable or temporary and
371 /// iterated.
372 ///
373 /// Iterator element type is `(K, Group)`: the group's key and the
374 /// group iterator.
375 ///
376 /// ```
377 /// use itertools::Itertools;
378 ///
379 /// // group data into runs of larger than zero or not.
380 /// let data = vec![1, 3, -2, -2, 1, 0, 1, 2];
381 /// // groups: |---->|------>|--------->|
382 ///
383 /// // Note: The `&` is significant here, `GroupByLazy` is iterable
384 /// // only by reference. You can also call `.into_iter()` explicitly.
385 /// for (key, group) in &data.into_iter().group_by_lazy(|elt| *elt >= 0) {
386 /// // Check that the sum of each group is +/- 4.
387 /// assert_eq!(4, group.fold(0_i32, |a, b| a + b).abs());
388 /// }
389 /// ```
group_by_lazy<K, F>(self, key: F) -> GroupByLazy<K, Self, F> where Self: Sized, F: FnMut(&Self::Item) -> K,390 fn group_by_lazy<K, F>(self, key: F) -> GroupByLazy<K, Self, F>
391 where Self: Sized,
392 F: FnMut(&Self::Item) -> K,
393 {
394 groupbylazy::new(self, key)
395 }
396
397 /// Return an iterable that can chunk the iterator.
398 ///
399 /// Yield subiterators (chunks) that each yield a fixed number elements,
400 /// determined by `size`. The last chunk will be shorter if there aren't
401 /// enough elements.
402 ///
403 /// `ChunksLazy` is based on `GroupByLazy`: it is iterable (implements
404 /// `IntoIterator`, **not** `Iterator`), and it only buffers if several
405 /// chunk iterators are alive at the same time.
406 ///
407 /// Iterator element type is `Chunk`, each chunk's iterator.
408 ///
409 /// **Panics** if `size` is 0.
410 ///
411 /// ```
412 /// use itertools::Itertools;
413 ///
414 /// let data = vec![1, 1, 2, -2, 6, 0, 3, 1];
415 /// //chunk size=3 |------->|-------->|--->|
416 ///
417 /// // Note: The `&` is significant here, `ChunksLazy` is iterable
418 /// // only by reference. You can also call `.into_iter()` explicitly.
419 /// for chunk in &data.into_iter().chunks_lazy(3) {
420 /// // Check that the sum of each chunk is 4.
421 /// assert_eq!(4, chunk.fold(0_i32, |a, b| a + b));
422 /// }
423 /// ```
chunks_lazy(self, size: usize) -> ChunksLazy<Self> where Self: Sized,424 fn chunks_lazy(self, size: usize) -> ChunksLazy<Self>
425 where Self: Sized,
426 {
427 assert!(size != 0);
428 groupbylazy::new_chunks(self, size)
429 }
430
431
432 /// Split into an iterator pair that both yield all elements from
433 /// the original iterator.
434 ///
435 /// **Note:** If the iterator is clonable, prefer using that instead
436 /// of using this method. It is likely to be more efficient.
437 ///
438 /// Iterator element type is `Self::Item`.
439 ///
440 /// ```
441 /// use itertools::Itertools;
442 /// let xs = vec![0, 1, 2, 3];
443 ///
444 /// let (mut t1, mut t2) = xs.into_iter().tee();
445 /// assert_eq!(t1.next(), Some(0));
446 /// assert_eq!(t1.next(), Some(1));
447 /// assert_eq!(t2.next(), Some(0));
448 /// assert_eq!(t1.next(), Some(2));
449 /// assert_eq!(t1.next(), Some(3));
450 /// assert_eq!(t1.next(), None);
451 /// assert_eq!(t2.next(), Some(1));
452 /// ```
tee(self) -> (Tee<Self>, Tee<Self>) where Self: Sized, Self::Item: Clone453 fn tee(self) -> (Tee<Self>, Tee<Self>)
454 where Self: Sized,
455 Self::Item: Clone
456 {
457 tee::new(self)
458 }
459
460 /// Return a sliced iterator.
461 ///
462 /// **Note:** slicing an iterator is not constant time, and much less efficient than
463 /// slicing for example a vector.
464 ///
465 /// Iterator element type is `Self::Item`.
466 ///
467 /// ```
468 /// use std::iter::repeat;
469 /// use itertools::Itertools;
470 ///
471 /// let it = repeat('a').slice(..3);
472 /// assert_eq!(it.count(), 3);
473 /// ```
slice<R>(self, range: R) -> ISlice<Self> where R: misc::GenericRange, Self: Sized474 fn slice<R>(self, range: R) -> ISlice<Self>
475 where R: misc::GenericRange,
476 Self: Sized
477 {
478 ISlice::new(self, range)
479 }
480
481 /// **Deprecated:** use `itertools::free::rciter` instead.
482 /// (It's an iterator constructor, not an adaptor).
483 ///
484 /// Return an iterator inside a `Rc<RefCell<_>>` wrapper.
485 ///
486 /// The returned `RcIter` can be cloned, and each clone will refer back to the
487 /// same original iterator.
488 ///
489 /// `RcIter` allows doing interesting things like using `.zip()` on an iterator with
490 /// itself, at the cost of runtime borrow checking.
491 /// (If it is not obvious: this has a performance penalty.)
492 ///
493 /// Iterator element type is `Self::Item`.
494 ///
495 /// ```
496 /// use itertools::Itertools;
497 ///
498 /// let mut rit = (0..9).into_rc();
499 /// let mut z = rit.clone().zip(rit.clone());
500 /// assert_eq!(z.next(), Some((0, 1)));
501 /// assert_eq!(z.next(), Some((2, 3)));
502 /// assert_eq!(z.next(), Some((4, 5)));
503 /// assert_eq!(rit.next(), Some(6));
504 /// assert_eq!(z.next(), Some((7, 8)));
505 /// assert_eq!(z.next(), None);
506 /// ```
507 ///
508 /// **Panics** in iterator methods if a borrow error is encountered,
509 /// but it can only happen if the `RcIter` is reentered in for example `.next()`,
510 /// i.e. if it somehow participates in an “iterator knot” where it is an adaptor of itself.
511 #[cfg_attr(feature = "unstable", deprecated(note = "use itertools::free::rciter instead"))]
into_rc(self) -> RcIter<Self> where Self: Sized512 fn into_rc(self) -> RcIter<Self>
513 where Self: Sized
514 {
515 RcIter::new(self)
516 }
517
518 /// Return an iterator adaptor that steps `n` elements in the base iterator
519 /// for each iteration.
520 ///
521 /// The iterator steps by yielding the next element from the base iterator,
522 /// then skipping forward `n - 1` elements.
523 ///
524 /// Iterator element type is `Self::Item`.
525 ///
526 /// **Panics** if the step is 0.
527 ///
528 /// ```
529 /// use itertools::Itertools;
530 ///
531 /// let it = (0..8).step(3);
532 /// itertools::assert_equal(it, vec![0, 3, 6]);
533 /// ```
step(self, n: usize) -> Step<Self> where Self: Sized534 fn step(self, n: usize) -> Step<Self>
535 where Self: Sized
536 {
537 Step::new(self, n)
538 }
539
540 /// Return an iterator adaptor that merges the two base iterators in ascending order.
541 /// If both base iterators are sorted (ascending), the result is sorted.
542 ///
543 /// Iterator element type is `Self::Item`.
544 ///
545 /// ```
546 /// use itertools::Itertools;
547 ///
548 /// let a = (0..11).step(3);
549 /// let b = (0..11).step(5);
550 /// let it = a.merge(b);
551 /// itertools::assert_equal(it, vec![0, 0, 3, 5, 6, 9, 10]);
552 /// ```
merge<J>(self, other: J) -> Merge<Self, J::IntoIter> where Self: Sized, Self::Item: PartialOrd, J: IntoIterator<Item = Self::Item>553 fn merge<J>(self, other: J) -> Merge<Self, J::IntoIter>
554 where Self: Sized,
555 Self::Item: PartialOrd,
556 J: IntoIterator<Item = Self::Item>
557 {
558 adaptors::merge_new(self, other.into_iter())
559 }
560
561 /// Return an iterator adaptor that merges the two base iterators in order.
562 /// This is much like `.merge()` but allows for a custom ordering.
563 ///
564 /// This can be especially useful for sequences of tuples.
565 ///
566 /// Iterator element type is `Self::Item`.
567 ///
568 /// ```
569 /// use itertools::Itertools;
570 ///
571 /// let a = (0..).zip("bc".chars());
572 /// let b = (0..).zip("ad".chars());
573 /// let it = a.merge_by(b, |x, y| x.1 <= y.1);
574 /// itertools::assert_equal(it, vec![(0, 'a'), (0, 'b'), (1, 'c'), (1, 'd')]);
575 /// ```
576
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) -> bool577 fn merge_by<J, F>(self, other: J, is_first: F) -> MergeBy<Self, J::IntoIter, F>
578 where Self: Sized,
579 J: IntoIterator<Item = Self::Item>,
580 F: FnMut(&Self::Item, &Self::Item) -> bool
581 {
582 adaptors::merge_by_new(self, other.into_iter(), is_first)
583 }
584
585 /// Return an iterator adaptor that flattens an iterator of iterators by
586 /// merging them in ascending order.
587 ///
588 /// If all base iterators are sorted (ascending), the result is sorted.
589 ///
590 /// Iterator element type is `Self::Item`.
591 ///
592 /// ```
593 /// use itertools::Itertools;
594 ///
595 /// let a = (0..6).step(3);
596 /// let b = (1..6).step(3);
597 /// let c = (2..6).step(3);
598 /// let it = vec![a, b, c].into_iter().kmerge();
599 /// itertools::assert_equal(it, vec![0, 1, 2, 3, 4, 5]);
600 /// ```
kmerge(self) -> KMerge<<<Self as Iterator>::Item as IntoIterator>::IntoIter> where Self: Sized, Self::Item: IntoIterator, <<Self as Iterator>::Item as IntoIterator>::Item: Ord,601 fn kmerge(self) -> KMerge<<<Self as Iterator>::Item as IntoIterator>::IntoIter> where
602 Self: Sized,
603 Self::Item: IntoIterator,
604 <<Self as Iterator>::Item as IntoIterator>::Item: Ord,
605 {
606 kmerge::kmerge_new(self)
607 }
608
609 /// Return an iterator adaptor that iterates over the cartesian product of
610 /// the element sets of two iterators `self` and `J`.
611 ///
612 /// Iterator element type is `(Self::Item, J::Item)`.
613 ///
614 /// ```
615 /// use itertools::Itertools;
616 ///
617 /// let it = (0..2).cartesian_product("αβ".chars());
618 /// itertools::assert_equal(it, vec![(0, 'α'), (0, 'β'), (1, 'α'), (1, 'β')]);
619 /// ```
cartesian_product<J>(self, other: J) -> Product<Self, J::IntoIter> where Self: Sized, Self::Item: Clone, J: IntoIterator, J::IntoIter: Clone620 fn cartesian_product<J>(self, other: J) -> Product<Self, J::IntoIter>
621 where Self: Sized,
622 Self::Item: Clone,
623 J: IntoIterator,
624 J::IntoIter: Clone
625 {
626 Product::new(self, other.into_iter())
627 }
628
629 /// Return an iterator adaptor that enumerates the iterator elements,
630 /// starting from `start` and incrementing by one.
631 ///
632 /// Iterator element type is `(K, Self::Item)`.
633 ///
634 /// ```
635 /// use itertools::Itertools;
636 ///
637 /// assert_eq!(
638 /// "αβγ".chars().enumerate_from(-10i8).collect_vec(),
639 /// [(-10, 'α'), (-9, 'β'), (-8, 'γ')]
640 /// );
641 /// ```
642 #[cfg(feature = "unstable")]
643 #[cfg_attr(feature = "unstable", deprecated(note = "Uses deprecated libstd traits"))]
enumerate_from<K>(self, start: K) -> EnumerateFrom<Self, K> where Self: Sized644 fn enumerate_from<K>(self, start: K) -> EnumerateFrom<Self, K>
645 where Self: Sized
646 {
647 EnumerateFrom::new(self, start)
648 }
649
650 /// Return an iterator adapter that allows peeking multiple values.
651 ///
652 /// After a call to `.next()` the peeking cursor is reset.
653 ///
654 /// ```
655 /// use itertools::Itertools;
656 ///
657 /// let nums = vec![1u8,2,3,4,5];
658 /// let mut peekable = nums.into_iter().multipeek();
659 /// assert_eq!(peekable.peek(), Some(&1));
660 /// assert_eq!(peekable.peek(), Some(&2));
661 /// assert_eq!(peekable.peek(), Some(&3));
662 /// assert_eq!(peekable.next(), Some(1));
663 /// assert_eq!(peekable.peek(), Some(&2));
664 /// ```
multipeek(self) -> MultiPeek<Self> where Self: Sized665 fn multipeek(self) -> MultiPeek<Self>
666 where Self: Sized
667 {
668 MultiPeek::new(self)
669 }
670
671 /// Return an iterator adaptor that uses the passed-in closure to
672 /// optionally merge together consecutive elements.
673 ///
674 /// The closure `f` is passed two elements, `x`, `y` and may return either
675 /// (1) `Ok(z)` to merge the two values or (2) `Err((x', y'))` to indicate
676 /// they can't be merged. In (2), the value `x'` is emitted by the iterator.
677 /// Coalesce continues with either `z` (1) or `y'` (2), and the next iterator
678 /// element as the next pair of elements to merge.
679 ///
680 /// Iterator element type is `Self::Item`.
681 ///
682 /// This iterator is *fused*.
683 ///
684 /// ```
685 /// use itertools::Itertools;
686 ///
687 /// // sum same-sign runs together
688 /// let data = vec![-1., -2., -3., 3., 1., 0., -1.];
689 /// itertools::assert_equal(data.into_iter().coalesce(|x, y|
690 /// if (x >= 0.) == (y >= 0.) {
691 /// Ok(x + y)
692 /// } else {
693 /// Err((x, y))
694 /// }),
695 /// vec![-6., 4., -1.]);
696 /// ```
coalesce<F>(self, f: F) -> Coalesce<Self, F> where Self: Sized, F: FnMut(Self::Item, Self::Item) -> Result<Self::Item, (Self::Item, Self::Item)>697 fn coalesce<F>(self, f: F) -> Coalesce<Self, F>
698 where Self: Sized,
699 F: FnMut(Self::Item, Self::Item)
700 -> Result<Self::Item, (Self::Item, Self::Item)>
701 {
702 Coalesce::new(self, f)
703 }
704
705 /// Remove duplicates from sections of consecutive identical elements.
706 /// If the iterator is sorted, all elements will be unique.
707 ///
708 /// Iterator element type is `Self::Item`.
709 ///
710 /// This iterator is *fused*.
711 ///
712 /// ```
713 /// use itertools::Itertools;
714 ///
715 /// let data = vec![1., 1., 2., 3., 3., 2., 2.];
716 /// itertools::assert_equal(data.into_iter().dedup(),
717 /// vec![1., 2., 3., 2.]);
718 /// ```
dedup(self) -> Dedup<Self> where Self: Sized, Self::Item: PartialEq,719 fn dedup(self) -> Dedup<Self>
720 where Self: Sized,
721 Self::Item: PartialEq,
722 {
723 Dedup::new(self)
724 }
725
726 /// Return an iterator adaptor that filters out elements that have
727 /// already been produced once during the iteration. Duplicates
728 /// are detected using hash and equality.
729 ///
730 /// Clones of visited elements are stored in a hash set in the
731 /// iterator.
732 ///
733 /// ```
734 /// use itertools::Itertools;
735 ///
736 /// let data = vec![10, 20, 30, 20, 40, 10, 50];
737 /// itertools::assert_equal(data.into_iter().unique(),
738 /// vec![10, 20, 30, 40, 50]);
739 /// ```
unique(self) -> Unique<Self> where Self: Sized, Self::Item: Clone + Eq + Hash740 fn unique(self) -> Unique<Self>
741 where Self: Sized,
742 Self::Item: Clone + Eq + Hash
743 {
744 adaptors::unique(self)
745 }
746
747 /// Return an iterator adaptor that filters out elements that have
748 /// already been produced once during the iteration.
749 ///
750 /// Duplicates are detected by comparing the key they map to
751 /// with the keying function `f` by hash and equality.
752 /// The keys are stored in a hash set in the iterator.
753 ///
754 /// ```
755 /// use itertools::Itertools;
756 ///
757 /// let data = vec!["a", "bb", "aa", "c", "ccc"];
758 /// itertools::assert_equal(data.into_iter().unique_by(|s| s.len()),
759 /// vec!["a", "bb", "ccc"]);
760 /// ```
unique_by<V, F>(self, f: F) -> UniqueBy<Self, V, F> where Self: Sized, V: Eq + Hash, F: FnMut(&Self::Item) -> V761 fn unique_by<V, F>(self, f: F) -> UniqueBy<Self, V, F>
762 where Self: Sized,
763 V: Eq + Hash,
764 F: FnMut(&Self::Item) -> V
765 {
766 UniqueBy::new(self, f)
767 }
768
769 /// Return an iterator adaptor that joins together adjacent slices if possible.
770 ///
771 /// Only implemented for iterators with slice or string slice elements.
772 /// Only slices that are contiguous together can be joined.
773 ///
774 /// ```
775 /// use itertools::Itertools;
776 ///
777 /// // Split a string into a slice per letter, filter out whitespace,
778 /// // and join into words again by mending adjacent slices.
779 /// let text = String::from("Warning: γ-radiation (ionizing)");
780 /// let char_slices = text.char_indices()
781 /// .map(|(index, ch)| &text[index..index + ch.len_utf8()]);
782 /// let words = char_slices.filter(|s| !s.chars().any(char::is_whitespace))
783 /// .mend_slices();
784 ///
785 /// itertools::assert_equal(words, vec!["Warning:", "γ-radiation", "(ionizing)"]);
786 /// ```
mend_slices(self) -> MendSlices<Self> where Self: Sized, Self::Item: misc::MendSlice787 fn mend_slices(self) -> MendSlices<Self>
788 where Self: Sized,
789 Self::Item: misc::MendSlice
790 {
791 MendSlices::new(self)
792 }
793
794 /// Return an iterator adaptor that borrows from a `Clone`-able iterator
795 /// to only pick off elements while the predicate `f` returns `true`.
796 ///
797 /// It uses the `Clone` trait to restore the original iterator so that the last
798 /// and rejected element is still available when `TakeWhileRef` is done.
799 ///
800 /// ```
801 /// use itertools::Itertools;
802 ///
803 /// let mut hexadecimals = "0123456789abcdef".chars();
804 ///
805 /// let decimals = hexadecimals.take_while_ref(|c| c.is_numeric())
806 /// .collect::<String>();
807 /// assert_eq!(decimals, "0123456789");
808 /// assert_eq!(hexadecimals.next(), Some('a'));
809 ///
810 /// ```
take_while_ref<'a, F>(&'a mut self, f: F) -> TakeWhileRef<'a, Self, F> where Self: Clone, F: FnMut(&Self::Item) -> bool811 fn take_while_ref<'a, F>(&'a mut self, f: F) -> TakeWhileRef<'a, Self, F>
812 where Self: Clone,
813 F: FnMut(&Self::Item) -> bool
814 {
815 TakeWhileRef::new(self, f)
816 }
817
818 /// Return an iterator adaptor that filters `Option<A>` iterator elements
819 /// and produces `A`. Stops on the first `None` encountered.
820 ///
821 /// Iterator element type is `A`, the unwrapped element.
822 ///
823 /// ```
824 /// use itertools::Itertools;
825 ///
826 /// // List all hexadecimal digits
827 /// itertools::assert_equal(
828 /// (0..).map(|i| std::char::from_digit(i, 16)).while_some(),
829 /// "0123456789abcdef".chars());
830 ///
831 /// ```
while_some<A>(self) -> WhileSome<Self> where Self: Sized + Iterator<Item = Option<A>>832 fn while_some<A>(self) -> WhileSome<Self>
833 where Self: Sized + Iterator<Item = Option<A>>
834 {
835 WhileSome::new(self)
836 }
837
838 /// Return an iterator adaptor that iterates over the combinations of
839 /// the elements from an iterator.
840 ///
841 /// Iterator element type is `(Self::Item, Self::Item)`.
842 ///
843 /// ```
844 /// use itertools::Itertools;
845 ///
846 /// let it = (1..5).combinations();
847 /// itertools::assert_equal(it, vec![(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]);
848 /// ```
combinations(self) -> Combinations<Self> where Self: Sized + Clone, Self::Item: Clone849 fn combinations(self) -> Combinations<Self>
850 where Self: Sized + Clone,
851 Self::Item: Clone
852 {
853 Combinations::new(self)
854 }
855
856 /// Return an iterator adaptor that iterates over the `n`-length combinations of
857 /// the elements from an iterator.
858 ///
859 /// Iterator element type is `Vec<Self::Item>`. The iterator produces a new Vec per iteration,
860 /// and clones the iterator elements.
861 ///
862 /// ```
863 /// use itertools::Itertools;
864 ///
865 /// let it = (1..5).combinations_n(3);
866 /// itertools::assert_equal(it, vec![
867 /// vec![1, 2, 3],
868 /// vec![1, 2, 4],
869 /// vec![1, 3, 4],
870 /// vec![2, 3, 4],
871 /// ]);
872 /// ```
combinations_n(self, n: usize) -> CombinationsN<Self> where Self: Sized, Self::Item: Clone873 fn combinations_n(self, n: usize) -> CombinationsN<Self>
874 where Self: Sized,
875 Self::Item: Clone
876 {
877 CombinationsN::new(self, n)
878 }
879
880 /// Return an iterator adaptor that pads the sequence to a minimum length of
881 /// `min` by filling missing elements using a closure `f`.
882 ///
883 /// Iterator element type is `Self::Item`.
884 ///
885 /// ```
886 /// use itertools::Itertools;
887 ///
888 /// let it = (0..5).pad_using(10, |i| 2*i);
889 /// itertools::assert_equal(it, vec![0, 1, 2, 3, 4, 10, 12, 14, 16, 18]);
890 ///
891 /// let it = (0..10).pad_using(5, |i| 2*i);
892 /// itertools::assert_equal(it, vec![0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);
893 ///
894 /// let it = (0..5).pad_using(10, |i| 2*i).rev();
895 /// itertools::assert_equal(it, vec![18, 16, 14, 12, 10, 4, 3, 2, 1, 0]);
896 /// ```
pad_using<F>(self, min: usize, f: F) -> PadUsing<Self, F> where Self: Sized, F: FnMut(usize) -> Self::Item897 fn pad_using<F>(self, min: usize, f: F) -> PadUsing<Self, F>
898 where Self: Sized,
899 F: FnMut(usize) -> Self::Item
900 {
901 PadUsing::new(self, min, f)
902 }
903
904 /// Unravel a nested iterator.
905 ///
906 /// This is a shortcut for `it.flat_map(|x| x)`.
907 ///
908 /// ```
909 /// use itertools::Itertools;
910 ///
911 /// let data = vec![vec![1, 2, 3], vec![4, 5, 6]];
912 /// let flattened = data.into_iter().flatten();
913 ///
914 /// itertools::assert_equal(flattened, vec![1, 2, 3, 4, 5, 6]);
915 /// ```
flatten(self) -> Flatten<Self> where Self: Sized, Self::Item: IntoIterator916 fn flatten(self) -> Flatten<Self>
917 where Self: Sized,
918 Self::Item: IntoIterator
919 {
920 Flatten::new(self)
921 }
922
923 /// **Deprecated:** Will be removed in the next version
924 ///
925 /// Like regular `.map()`, specialized to using a simple function pointer instead,
926 /// so that the resulting `Map` iterator value can be cloned.
927 ///
928 /// Iterator element type is `B`.
929 ///
930 /// ```
931 /// use itertools::Itertools;
932 ///
933 /// let data = vec![Ok(1), Ok(0), Err("No result")];
934 ///
935 /// let iter = data.iter().cloned().map_fn(Result::ok);
936 /// let iter_copy = iter.clone();
937 ///
938 /// itertools::assert_equal(iter, vec![Some(1), Some(0), None]);
939 /// itertools::assert_equal(iter_copy, vec![Some(1), Some(0), None]);
940 /// ```
941 #[cfg_attr(feature = "unstable", deprecated(note = "will be removed in the next version"))]
map_fn<B>(self, f: fn(Self::Item) -> B) -> MapFn<Self, B> where Self: Sized942 fn map_fn<B>(self, f: fn(Self::Item) -> B) -> MapFn<Self, B>
943 where Self: Sized
944 {
945 self.map(f)
946 }
947
948 // non-adaptor methods
949
950 /// Find the position and value of the first element satisfying a predicate.
951 ///
952 /// The iterator is not advanced past the first element found.
953 ///
954 /// ```
955 /// use itertools::Itertools;
956 ///
957 /// let text = "Hα";
958 /// assert_eq!(text.chars().find_position(|ch| ch.is_lowercase()), Some((1, 'α')));
959 /// ```
find_position<P>(&mut self, mut pred: P) -> Option<(usize, Self::Item)> where P: FnMut(&Self::Item) -> bool960 fn find_position<P>(&mut self, mut pred: P) -> Option<(usize, Self::Item)>
961 where P: FnMut(&Self::Item) -> bool
962 {
963 let mut index = 0usize;
964 for elt in self {
965 if pred(&elt) {
966 return Some((index, elt));
967 }
968 index += 1;
969 }
970 None
971 }
972
973 /// Consume the first `n` elements of the iterator eagerly.
974 ///
975 /// Return actual number of elements consumed, until done or reaching the end.
976 ///
977 /// ```
978 /// use itertools::Itertools;
979 ///
980 /// let mut iter = "αβγ".chars();
981 /// iter.dropn(2);
982 /// itertools::assert_equal(iter, "γ".chars());
983 /// ```
dropn(&mut self, mut n: usize) -> usize984 fn dropn(&mut self, mut n: usize) -> usize {
985 // FIXME: Can we use .nth() somehow?
986 let start = n;
987 while n > 0 {
988 match self.next() {
989 Some(..) => n -= 1,
990 None => break,
991 }
992 }
993 start - n
994 }
995
996 /// Consume the first `n` elements from the iterator eagerly,
997 /// and return the same iterator again.
998 ///
999 /// It works similarly to *.skip(* `n` *)* except it is eager and
1000 /// preserves the iterator type.
1001 ///
1002 /// ```
1003 /// use itertools::Itertools;
1004 ///
1005 /// let mut iter = "αβγ".chars().dropping(2);
1006 /// itertools::assert_equal(iter, "γ".chars());
1007 /// ```
1008 ///
1009 /// *Fusing notes: if the iterator is exhausted by dropping,
1010 /// the result of calling `.next()` again depends on the iterator implementation.*
dropping(mut self, n: usize) -> Self where Self: Sized1011 fn dropping(mut self, n: usize) -> Self
1012 where Self: Sized
1013 {
1014 if n > 0 {
1015 self.nth(n - 1);
1016 }
1017 self
1018 }
1019
1020 /// Consume the last `n` elements from the iterator eagerly,
1021 /// and return the same iterator again.
1022 ///
1023 /// This is only possible on double ended iterators. `n` may be
1024 /// larger than the number of elements.
1025 ///
1026 /// Note: This method is eager, dropping the back elements immediately and
1027 /// preserves the iterator type.
1028 ///
1029 /// ```
1030 /// use itertools::Itertools;
1031 ///
1032 /// let init = vec![0, 3, 6, 9].into_iter().dropping_back(1);
1033 /// itertools::assert_equal(init, vec![0, 3, 6]);
1034 /// ```
dropping_back(mut self, n: usize) -> Self where Self: Sized, Self: DoubleEndedIterator1035 fn dropping_back(mut self, n: usize) -> Self
1036 where Self: Sized,
1037 Self: DoubleEndedIterator
1038 {
1039 self.by_ref().rev().dropn(n);
1040 self
1041 }
1042
1043 /// Run the closure `f` eagerly on each element of the iterator.
1044 ///
1045 /// Consumes the iterator until its end.
1046 ///
1047 /// ```
1048 /// use std::sync::mpsc::channel;
1049 /// use itertools::Itertools;
1050 ///
1051 /// let (tx, rx) = channel();
1052 ///
1053 /// // use .foreach() to apply a function to each value -- sending it
1054 /// (0..5).map(|x| x * 2 + 1).foreach(|x| { tx.send(x).unwrap(); } );
1055 ///
1056 /// drop(tx);
1057 ///
1058 /// itertools::assert_equal(rx.iter(), vec![1, 3, 5, 7, 9]);
1059 /// ```
foreach<F>(&mut self, mut f: F) where F: FnMut(Self::Item)1060 fn foreach<F>(&mut self, mut f: F)
1061 where F: FnMut(Self::Item)
1062 {
1063 for elt in self {
1064 f(elt)
1065 }
1066 }
1067
1068 /// `.collect_vec()` is simply a type specialization of `.collect()`,
1069 /// for convenience.
collect_vec(self) -> Vec<Self::Item> where Self: Sized1070 fn collect_vec(self) -> Vec<Self::Item>
1071 where Self: Sized
1072 {
1073 self.collect()
1074 }
1075
1076 /// Assign to each reference in `self` from the `from` iterator,
1077 /// stopping at the shortest of the two iterators.
1078 ///
1079 /// The `from` iterator is queried for its next element before the `self`
1080 /// iterator, and if either is exhausted the method is done.
1081 ///
1082 /// Return the number of elements written.
1083 ///
1084 /// ```
1085 /// use itertools::Itertools;
1086 ///
1087 /// let mut xs = [0; 4];
1088 /// xs.iter_mut().set_from(1..);
1089 /// assert_eq!(xs, [1, 2, 3, 4]);
1090 /// ```
1091 #[inline]
set_from<'a, A: 'a, J>(&mut self, from: J) -> usize where Self: Iterator<Item = &'a mut A>, J: IntoIterator<Item = A>1092 fn set_from<'a, A: 'a, J>(&mut self, from: J) -> usize
1093 where Self: Iterator<Item = &'a mut A>,
1094 J: IntoIterator<Item = A>
1095 {
1096 let mut count = 0;
1097 for elt in from {
1098 match self.next() {
1099 None => break,
1100 Some(ptr) => *ptr = elt,
1101 }
1102 count += 1;
1103 }
1104 count
1105 }
1106
1107 /// Combine all iterator elements into one String, seperated by `sep`.
1108 ///
1109 /// Use the `Display` implementation of each element.
1110 ///
1111 /// ```
1112 /// use itertools::Itertools;
1113 ///
1114 /// assert_eq!(["a", "b", "c"].iter().join(", "), "a, b, c");
1115 /// assert_eq!([1, 2, 3].iter().join(", "), "1, 2, 3");
1116 /// ```
join(&mut self, sep: &str) -> String where Self::Item: std::fmt::Display1117 fn join(&mut self, sep: &str) -> String
1118 where Self::Item: std::fmt::Display
1119 {
1120 match self.next() {
1121 None => String::new(),
1122 Some(first_elt) => {
1123 // estimate lower bound of capacity needed
1124 let (lower, _) = self.size_hint();
1125 let mut result = String::with_capacity(sep.len() * lower);
1126 write!(&mut result, "{}", first_elt).unwrap();
1127 for elt in self {
1128 result.push_str(sep);
1129 write!(&mut result, "{}", elt).unwrap();
1130 }
1131 result
1132 }
1133 }
1134 }
1135
1136 /// Format all iterator elements, separated by `sep`.
1137 ///
1138 /// All elements are formatted (any formatting trait)
1139 /// with `sep` inserted between each element.
1140 ///
1141 /// ```
1142 /// use itertools::Itertools;
1143 ///
1144 /// let data = [1.1, 2.71828, -3.];
1145 /// assert_eq!(
1146 /// format!("{:.2}", data.iter().format_default(", ")),
1147 /// "1.10, 2.72, -3.00");
1148 /// ```
format_default(self, sep: &str) -> FormatDefault<Self> where Self: Sized,1149 fn format_default(self, sep: &str) -> FormatDefault<Self>
1150 where Self: Sized,
1151 {
1152 format::new_format_default(self, sep)
1153 }
1154
1155 /// Format all iterator elements, separated by `sep`.
1156 ///
1157 /// This is a customizable version of `.format_default()`.
1158 ///
1159 /// The supplied closure `format` is called once per iterator element,
1160 /// with two arguments: the element and a callback that takes a
1161 /// `&Display` value, i.e. any reference to type that implements `Display`.
1162 ///
1163 /// Using `&format_args!(...)` is the most versatile way to apply custom
1164 /// element formatting. The callback can be called multiple times if needed.
1165 ///
1166 /// ```
1167 /// use itertools::Itertools;
1168 ///
1169 /// let data = [1.1, 2.71828, -3.];
1170 /// let data_formatter = data.iter().format(", ", |elt, f| f(&format_args!("{:.2}", elt)));
1171 /// assert_eq!(format!("{}", data_formatter),
1172 /// "1.10, 2.72, -3.00");
1173 ///
1174 /// // .format() is recursively composable
1175 /// let matrix = [[1., 2., 3.],
1176 /// [4., 5., 6.]];
1177 /// let matrix_formatter = matrix.iter().format("\n", |row, f| {
1178 /// f(&row.iter().format(", ", |elt, g| g(&elt)))
1179 /// });
1180 /// assert_eq!(format!("{}", matrix_formatter),
1181 /// "1, 2, 3\n4, 5, 6");
1182 ///
1183 ///
1184 /// ```
format<F>(self, sep: &str, format: F) -> Format<Self, F> where Self: Sized, F: FnMut(Self::Item, &mut FnMut(&fmt::Display) -> fmt::Result) -> fmt::Result,1185 fn format<F>(self, sep: &str, format: F) -> Format<Self, F>
1186 where Self: Sized,
1187 F: FnMut(Self::Item, &mut FnMut(&fmt::Display) -> fmt::Result) -> fmt::Result,
1188 {
1189 format::new_format(self, sep, format)
1190 }
1191
1192 /// Fold `Result` values from an iterator.
1193 ///
1194 /// Only `Ok` values are folded. If no error is encountered, the folded
1195 /// value is returned inside `Ok`. Otherwise, the operation terminates
1196 /// and returns the first `Err` value it encounters. No iterator elements are
1197 /// consumed after the first error.
1198 ///
1199 /// The first accumulator value is the `start` parameter.
1200 /// Each iteration passes the accumulator value and the next value inside `Ok`
1201 /// to the fold function `f` and its return value becomes the new accumulator value.
1202 ///
1203 /// For example the sequence *Ok(1), Ok(2), Ok(3)* will result in a
1204 /// computation like this:
1205 ///
1206 /// ```ignore
1207 /// let mut accum = start;
1208 /// accum = f(accum, 1);
1209 /// accum = f(accum, 2);
1210 /// accum = f(accum, 3);
1211 /// ```
1212 ///
1213 /// With a `start` value of 0 and an addition as folding function,
1214 /// this effetively results in *((0 + 1) + 2) + 3*
1215 ///
1216 /// ```
1217 /// use std::ops::Add;
1218 /// use itertools::Itertools;
1219 ///
1220 /// let values = [1, 2, -2, -1, 2, 1];
1221 /// assert_eq!(
1222 /// values.iter()
1223 /// .map(Ok::<_, ()>)
1224 /// .fold_results(0, Add::add),
1225 /// Ok(3)
1226 /// );
1227 /// assert!(
1228 /// values.iter()
1229 /// .map(|&x| if x >= 0 { Ok(x) } else { Err("Negative number") })
1230 /// .fold_results(0, Add::add)
1231 /// .is_err()
1232 /// );
1233 /// ```
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) -> B1234 fn fold_results<A, E, B, F>(&mut self, mut start: B, mut f: F) -> Result<B, E>
1235 where Self: Iterator<Item = Result<A, E>>,
1236 F: FnMut(B, A) -> B
1237 {
1238 for elt in self {
1239 match elt {
1240 Ok(v) => start = f(start, v),
1241 Err(u) => return Err(u),
1242 }
1243 }
1244 Ok(start)
1245 }
1246
1247 /// Fold `Option` values from an iterator.
1248 ///
1249 /// Only `Some` values are folded. If no `None` is encountered, the folded
1250 /// value is returned inside `Some`. Otherwise, the operation terminates
1251 /// and returns `None`. No iterator elements are consumed after the `None`.
1252 ///
1253 /// This is the `Option` equivalent to `fold_results`.
1254 ///
1255 /// ```
1256 /// use std::ops::Add;
1257 /// use itertools::Itertools;
1258 ///
1259 /// let mut values = vec![Some(1), Some(2), Some(-2)].into_iter();
1260 /// assert_eq!(values.fold_options(5, Add::add), Some(5 + 1 + 2 - 2));
1261 ///
1262 /// let mut more_values = vec![Some(2), None, Some(0)].into_iter();
1263 /// assert!(more_values.fold_options(0, Add::add).is_none());
1264 /// assert_eq!(more_values.next().unwrap(), Some(0));
1265 /// ```
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) -> B1266 fn fold_options<A, B, F>(&mut self, mut start: B, mut f: F) -> Option<B>
1267 where Self: Iterator<Item = Option<A>>,
1268 F: FnMut(B, A) -> B
1269 {
1270 for elt in self {
1271 match elt {
1272 Some(v) => start = f(start, v),
1273 None => return None,
1274 }
1275 }
1276 Some(start)
1277 }
1278
1279 /// Accumulator of the elements in the iterator.
1280 ///
1281 /// Like `.fold()`, without a base case. If the iterator is
1282 /// empty, return `None`. With just one element, return it.
1283 /// Otherwise elements are accumulated in sequence using the closure `f`.
1284 ///
1285 /// ```
1286 /// use itertools::Itertools;
1287 ///
1288 /// assert_eq!((0..10).fold1(|x, y| x + y).unwrap_or(0), 45);
1289 /// assert_eq!((0..0).fold1(|x, y| x * y), None);
1290 /// ```
fold1<F>(&mut self, mut f: F) -> Option<Self::Item> where F: FnMut(Self::Item, Self::Item) -> Self::Item1291 fn fold1<F>(&mut self, mut f: F) -> Option<Self::Item>
1292 where F: FnMut(Self::Item, Self::Item) -> Self::Item
1293 {
1294 match self.next() {
1295 None => None,
1296 Some(mut x) => {
1297 for y in self {
1298 x = f(x, y);
1299 }
1300 Some(x)
1301 }
1302 }
1303 }
1304
1305 /// An iterator adaptor that applies a function, producing a single, final value.
1306 ///
1307 /// `fold_while()` is basically equivalent to `fold()` but with additional support for
1308 /// early exit via short-circuiting.
1309 ///
1310 /// ```
1311 /// use itertools::Itertools;
1312 /// use itertools::FoldWhile::{Continue, Done};
1313 ///
1314 /// let numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
1315 ///
1316 /// let mut result = 0;
1317 ///
1318 /// // for loop:
1319 /// for i in &numbers {
1320 /// if *i > 5 {
1321 /// break;
1322 /// }
1323 /// result = result + i;
1324 /// }
1325 ///
1326 /// // fold:
1327 /// let result2 = numbers.iter().fold(0, |acc, x| {
1328 /// if *x > 5 { acc } else { acc + x }
1329 /// });
1330 ///
1331 /// // fold_while:
1332 /// let result3 = numbers.iter().fold_while(0, |acc, x| {
1333 /// if *x > 5 { Done(acc) } else { Continue(acc + x) }
1334 /// });
1335 ///
1336 /// // they're the same
1337 /// assert_eq!(result, result2);
1338 /// assert_eq!(result2, result3);
1339 /// ```
1340 ///
1341 /// The big difference between the computations of `result2` and `result3` is that while
1342 /// `fold()` called the provided closure for every item of the callee iterator,
1343 /// `fold_while()` actually stopped iterating as soon as it encountered `Fold::Done(_)`.
fold_while<B, F>(self, init: B, mut f: F) -> B where Self: Sized, F: FnMut(B, Self::Item) -> FoldWhile<B>1344 fn fold_while<B, F>(self, init: B, mut f: F) -> B
1345 where Self: Sized,
1346 F: FnMut(B, Self::Item) -> FoldWhile<B>
1347 {
1348 let mut accum = init;
1349 for item in self {
1350 match f(accum, item) {
1351 FoldWhile::Continue(res) => {
1352 accum = res;
1353 }
1354 FoldWhile::Done(res) => {
1355 accum = res;
1356 break;
1357 }
1358 }
1359 }
1360 accum
1361 }
1362
1363 /// Tell if the iterator is empty or not according to its size hint.
1364 /// Return `None` if the size hint does not tell, or return a `Some`
1365 /// value with the emptiness if it's possible to tell.
1366 ///
1367 /// ```
1368 /// use itertools::Itertools;
1369 ///
1370 /// assert_eq!((1..1).is_empty_hint(), Some(true));
1371 /// assert_eq!([1, 2, 3].iter().is_empty_hint(), Some(false));
1372 /// assert_eq!((0..10).filter(|&x| x > 0).is_empty_hint(), None);
1373 /// ```
is_empty_hint(&self) -> Option<bool>1374 fn is_empty_hint(&self) -> Option<bool> {
1375 let (low, opt_hi) = self.size_hint();
1376 // check for erronous hint
1377 if let Some(hi) = opt_hi {
1378 if hi < low { return None }
1379 }
1380
1381 if opt_hi == Some(0) {
1382 Some(true)
1383 } else if low > 0 {
1384 Some(false)
1385 } else {
1386 None
1387 }
1388 }
1389
1390 /// Collect all iterator elements into a sorted vector in ascending order.
1391 ///
1392 /// **Note:** This consumes the entire iterator, uses the
1393 /// `slice::sort_by()` method and returns the sorted vector.
1394 ///
1395 /// ```
1396 /// use itertools::Itertools;
1397 ///
1398 /// // sort the letters of the text in ascending order
1399 /// let text = "bdacfe";
1400 /// itertools::assert_equal(text.chars().sorted(),
1401 /// "abcdef".chars());
1402 /// ```
sorted(self) -> Vec<Self::Item> where Self: Sized, Self::Item: Ord1403 fn sorted(self) -> Vec<Self::Item>
1404 where Self: Sized,
1405 Self::Item: Ord
1406 {
1407 self.sorted_by(Ord::cmp)
1408 }
1409
1410 /// Collect all iterator elements into a sorted vector.
1411 ///
1412 /// **Note:** This consumes the entire iterator, uses the
1413 /// `slice::sort_by()` method and returns the sorted vector.
1414 ///
1415 /// ```
1416 /// use itertools::Itertools;
1417 ///
1418 /// // sort people in descending order by age
1419 /// let people = vec![("Jane", 20), ("John", 18), ("Jill", 30), ("Jack", 27)];
1420 ///
1421 /// let oldest_people_first = people
1422 /// .into_iter()
1423 /// .sorted_by(|a, b| Ord::cmp(&b.1, &a.1))
1424 /// .into_iter()
1425 /// .map(|(person, _age)| person);
1426 ///
1427 /// itertools::assert_equal(oldest_people_first,
1428 /// vec!["Jill", "Jack", "Jane", "John"]);
1429 /// ```
sorted_by<F>(self, cmp: F) -> Vec<Self::Item> where Self: Sized, F: FnMut(&Self::Item, &Self::Item) -> Ordering,1430 fn sorted_by<F>(self, cmp: F) -> Vec<Self::Item>
1431 where Self: Sized,
1432 F: FnMut(&Self::Item, &Self::Item) -> Ordering,
1433 {
1434 let mut v: Vec<Self::Item> = self.collect();
1435
1436 v.sort_by(cmp);
1437 v
1438 }
1439
1440 #[cfg_attr(feature = "unstable", deprecated(note = "Replaced by .sorted_by()"))]
1441 /// **Deprecated:** renamed to `.sorted_by()`
sort_by<F>(self, cmp: F) -> Vec<Self::Item> where Self: Sized, F: FnMut(&Self::Item, &Self::Item) -> Ordering,1442 fn sort_by<F>(self, cmp: F) -> Vec<Self::Item>
1443 where Self: Sized,
1444 F: FnMut(&Self::Item, &Self::Item) -> Ordering,
1445 {
1446 self.sorted_by(cmp)
1447 }
1448
1449 /// Collect all iterator elements into one of two
1450 /// partitions. Unlike `Iterator::partition`, each partition may
1451 /// have a distinct type.
1452 ///
1453 /// ```
1454 /// use itertools::{Itertools, Partition};
1455 ///
1456 /// let successes_and_failures = vec![Ok(1), Err(false), Err(true), Ok(2)];
1457 ///
1458 /// let (successes, failures): (Vec<_>, Vec<_>) = successes_and_failures
1459 /// .into_iter()
1460 /// .partition_map(|r| {
1461 /// match r {
1462 /// Ok(v) => Partition::Left(v),
1463 /// Err(v) => Partition::Right(v),
1464 /// }
1465 /// });
1466 ///
1467 /// assert_eq!(successes, [1, 2]);
1468 /// assert_eq!(failures, [false, true]);
1469 /// ```
partition_map<A, B, F, L, R>(self, predicate: F) -> (A, B) where Self: Sized, F: Fn(Self::Item) -> Partition<L, R>, A: Default + Extend<L>, B: Default + Extend<R>,1470 fn partition_map<A, B, F, L, R>(self, predicate: F) -> (A, B)
1471 where Self: Sized,
1472 F: Fn(Self::Item) -> Partition<L, R>,
1473 A: Default + Extend<L>,
1474 B: Default + Extend<R>,
1475 {
1476 let mut left = A::default();
1477 let mut right = B::default();
1478
1479 for val in self {
1480 match predicate(val) {
1481 Partition::Left(v) => left.extend(Some(v)),
1482 Partition::Right(v) => right.extend(Some(v)),
1483 }
1484 }
1485
1486 (left, right)
1487 }
1488
1489 /// Return the minimum and maximum elements in the iterator.
1490 ///
1491 /// The return type `MinMaxResult` is an enum of three variants:
1492 ///
1493 /// - `NoElements` if the iterator is empty.
1494 /// - `OneElement(x)` if the iterator has exactly one element.
1495 /// - `MinMax(x, y)` is returned otherwise, where `x <= y`. Two
1496 /// values are equal if and only if there is more than one
1497 /// element in the iterator and all elements are equal.
1498 ///
1499 /// On an iterator of length `n`, `min_max` does `1.5 * n` comparisons,
1500 /// and so is faster than calling `min` and `max` separately which does
1501 /// `2 * n` comparisons.
1502 ///
1503 /// # Examples
1504 ///
1505 /// ```
1506 /// use itertools::Itertools;
1507 /// use itertools::MinMaxResult::{NoElements, OneElement, MinMax};
1508 ///
1509 /// let a: [i32; 0] = [];
1510 /// assert_eq!(a.iter().minmax(), NoElements);
1511 ///
1512 /// let a = [1];
1513 /// assert_eq!(a.iter().minmax(), OneElement(&1));
1514 ///
1515 /// let a = [1, 2, 3, 4, 5];
1516 /// assert_eq!(a.iter().minmax(), MinMax(&1, &5));
1517 ///
1518 /// let a = [1, 1, 1, 1];
1519 /// assert_eq!(a.iter().minmax(), MinMax(&1, &1));
1520 /// ```
minmax(self) -> MinMaxResult<Self::Item> where Self: Sized, Self::Item: Ord1521 fn minmax(self) -> MinMaxResult<Self::Item>
1522 where Self: Sized, Self::Item: Ord
1523 {
1524 minmax::minmax_impl(self, |_| (), |x, y, _, _| x < y)
1525 }
1526
1527 /// Return the minimum and maximum element of an iterator, as determined by
1528 /// the specified function.
1529 ///
1530 /// The return value is a variant of `MinMaxResult` like for `minmax()`.
1531 ///
1532 /// For the minimum, the first minimal element is returned. For the maximum,
1533 /// the last maximal element wins. This matches the behavior of the standard
1534 /// `Iterator::min()` and `Iterator::max()` methods.
minmax_by_key<K, F>(self, key: F) -> MinMaxResult<Self::Item> where Self: Sized, K: Ord, F: FnMut(&Self::Item) -> K1535 fn minmax_by_key<K, F>(self, key: F) -> MinMaxResult<Self::Item>
1536 where Self: Sized, K: Ord, F: FnMut(&Self::Item) -> K
1537 {
1538 minmax::minmax_impl(self, key, |_, _, xk, yk| xk < yk)
1539 }
1540
1541 /// Return the minimum and maximum element of an iterator, as determined by
1542 /// the specified comparison function.
1543 ///
1544 /// The return value is a variant of `MinMaxResult` like for `minmax()`.
1545 ///
1546 /// For the minimum, the first minimal element is returned. For the maximum,
1547 /// the last maximal element wins. This matches the behavior of the standard
1548 /// `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) -> Ordering1549 fn minmax_by<F>(self, mut compare: F) -> MinMaxResult<Self::Item>
1550 where Self: Sized, F: FnMut(&Self::Item, &Self::Item) -> Ordering
1551 {
1552 minmax::minmax_impl(
1553 self,
1554 |_| (),
1555 |x, y, _, _| Ordering::Less == compare(x, y)
1556 )
1557 }
1558 }
1559
1560 impl<T: ?Sized> Itertools for T where T: Iterator { }
1561
1562 /// Return `true` if both iterators produce equal sequences
1563 /// (elements pairwise equal and sequences of the same length),
1564 /// `false` otherwise.
1565 ///
1566 /// **Note:** the standard library method `Iterator::eq` now provides
1567 /// the same functionality.
1568 ///
1569 /// ```
1570 /// assert!(itertools::equal(vec![1, 2, 3], 1..4));
1571 /// assert!(!itertools::equal(&[0, 0], &[0, 0, 0]));
1572 /// ```
equal<I, J>(a: I, b: J) -> bool where I: IntoIterator, J: IntoIterator, I::Item: PartialEq<J::Item>1573 pub fn equal<I, J>(a: I, b: J) -> bool
1574 where I: IntoIterator,
1575 J: IntoIterator,
1576 I::Item: PartialEq<J::Item>
1577 {
1578 let mut ia = a.into_iter();
1579 let mut ib = b.into_iter();
1580 loop {
1581 match ia.next() {
1582 Some(ref x) => match ib.next() {
1583 Some(ref y) => if x != y { return false; },
1584 None => return false,
1585 },
1586 None => return ib.next().is_none()
1587 }
1588 }
1589 }
1590
1591 /// Assert that two iterators produce equal sequences, with the same
1592 /// semantics as *equal(a, b)*.
1593 ///
1594 /// **Panics** on assertion failure with a message that shows the
1595 /// two iteration elements.
1596 ///
1597 /// ```ignore
1598 /// assert_equal("exceed".split('c'), "excess".split('c'));
1599 /// // ^PANIC: panicked at 'Failed assertion Some("eed") == Some("ess") for iteration 1',
1600 /// ```
assert_equal<I, J>(a: I, b: J) where I: IntoIterator, J: IntoIterator, I::Item: fmt::Debug + PartialEq<J::Item>, J::Item: fmt::Debug,1601 pub fn assert_equal<I, J>(a: I, b: J)
1602 where I: IntoIterator,
1603 J: IntoIterator,
1604 I::Item: fmt::Debug + PartialEq<J::Item>,
1605 J::Item: fmt::Debug,
1606 {
1607 let mut ia = a.into_iter();
1608 let mut ib = b.into_iter();
1609 let mut i = 0;
1610 loop {
1611 match (ia.next(), ib.next()) {
1612 (None, None) => return,
1613 (a, b) => {
1614 let equal = match (&a, &b) {
1615 (&Some(ref a), &Some(ref b)) => a == b,
1616 _ => false,
1617 };
1618 assert!(equal, "Failed assertion {a:?} == {b:?} for iteration {i}",
1619 i=i, a=a, b=b);
1620 i += 1;
1621 }
1622 }
1623 }
1624 }
1625
1626 /// Partition a sequence using predicate `pred` so that elements
1627 /// that map to `true` are placed before elements which map to `false`.
1628 ///
1629 /// The order within the partitions is arbitrary.
1630 ///
1631 /// Return the index of the split point.
1632 ///
1633 /// ```
1634 /// use itertools::partition;
1635 ///
1636 /// # // use repeated numbers to not promise any ordering
1637 /// let mut data = [7, 1, 1, 7, 1, 1, 7];
1638 /// let split_index = partition(&mut data, |elt| *elt >= 3);
1639 ///
1640 /// assert_eq!(data, [7, 7, 7, 1, 1, 1, 1]);
1641 /// assert_eq!(split_index, 3);
1642 /// ```
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) -> bool1643 pub fn partition<'a, A: 'a, I, F>(iter: I, mut pred: F) -> usize
1644 where I: IntoIterator<Item = &'a mut A>,
1645 I::IntoIter: DoubleEndedIterator,
1646 F: FnMut(&A) -> bool
1647 {
1648 let mut split_index = 0;
1649 let mut iter = iter.into_iter();
1650 'main: while let Some(front) = iter.next() {
1651 if !pred(front) {
1652 loop {
1653 match iter.next_back() {
1654 Some(back) => if pred(back) {
1655 std::mem::swap(front, back);
1656 break;
1657 },
1658 None => break 'main,
1659 }
1660 }
1661 }
1662 split_index += 1;
1663 }
1664 split_index
1665 }
1666
1667 /// Classifies the result of the `.partition_map()` closure into a
1668 /// partition.
1669 pub enum Partition<L, R> {
1670 /// Classify into the left partition.
1671 Left(L),
1672 /// Classify into the right partition.
1673 Right(R),
1674 }
1675
1676
1677 /// An enum used for controlling the execution of `.fold_while()`.
1678 ///
1679 /// See [`.fold_while()`](trait.Itertools.html#method.fold_while) for more information.
1680 pub enum FoldWhile<T> {
1681 /// Continue folding with this value
1682 Continue(T),
1683 /// Fold is complete and will return this value
1684 Done(T),
1685 }
1686
1687