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