vendor/itertools-0.7.8/src/adaptors/mod.rs

   1 //! Licensed under the Apache License, Version 2.0
   2 //! http://www.apache.org/licenses/LICENSE-2.0 or the MIT license
   3 //! http://opensource.org/licenses/MIT, at your
   4 //! option. This file may not be copied, modified, or distributed
   5 //! except according to those terms.
   6
   7 mod multi_product;
   8 #[cfg(feature = "use_std")]
   9 pub use self::multi_product::*;
  10
  11 use std::fmt;
  12 use std::mem::replace;
  13 use std::iter::{Fuse, Peekable, FromIterator};
  14 use std::marker::PhantomData;
  15 use size_hint;
  16 use fold;
  17
  18 macro_rules! clone_fields {
  19     ($name:ident, $base:expr, $($field:ident),+) => (
  20         $name {
  21             $(
  22                 $field : $base . $field .clone()
  23             ),*
  24         }
  25     );
  26 }
  27
  28 /// An iterator adaptor that alternates elements from two iterators until both
  29 /// run out.
  30 ///
  31 /// This iterator is *fused*.
  32 ///
  33 /// See [`.interleave()`](../trait.Itertools.html#method.interleave) for more information.
  34 #[derive(Clone, Debug)]
  35 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
  36 pub struct Interleave<I, J> {
  37     a: Fuse<I>,
  38     b: Fuse<J>,
  39     flag: bool,
  40 }
  41
  42 /// Create an iterator that interleaves elements in `i` and `j`.
  43 ///
  44 /// `IntoIterator` enabled version of `i.interleave(j)`.
  45 ///
  46 /// ```
  47 /// use itertools::interleave;
  48 ///
  49 /// for elt in interleave(&[1, 2, 3], &[2, 3, 4]) {
  50 ///     /* loop body */
  51 /// }
  52 /// ```
  53 pub fn interleave<I, J>(i: I, j: J) -> Interleave<<I as IntoIterator>::IntoIter, <J as IntoIterator>::IntoIter>
  54     where I: IntoIterator,
  55           J: IntoIterator<Item = I::Item>
  56 {
  57     Interleave {
  58         a: i.into_iter().fuse(),
  59         b: j.into_iter().fuse(),
  60         flag: false,
  61     }
  62 }
  63
  64 impl<I, J> Iterator for Interleave<I, J>
  65     where I: Iterator,
  66           J: Iterator<Item = I::Item>
  67 {
  68     type Item = I::Item;
  69     #[inline]
  70     fn next(&mut self) -> Option<I::Item> {
  71         self.flag = !self.flag;
  72         if self.flag {
  73             match self.a.next() {
  74                 None => self.b.next(),
  75                 r => r,
  76             }
  77         } else {
  78             match self.b.next() {
  79                 None => self.a.next(),
  80                 r => r,
  81             }
  82         }
  83     }
  84
  85     fn size_hint(&self) -> (usize, Option<usize>) {
  86         size_hint::add(self.a.size_hint(), self.b.size_hint())
  87     }
  88 }
  89
  90 /// An iterator adaptor that alternates elements from the two iterators until
  91 /// one of them runs out.
  92 ///
  93 /// This iterator is *fused*.
  94 ///
  95 /// See [`.interleave_shortest()`](../trait.Itertools.html#method.interleave_shortest)
  96 /// for more information.
  97 #[derive(Clone, Debug)]
  98 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
  99 pub struct InterleaveShortest<I, J>
 100     where I: Iterator,
 101           J: Iterator<Item = I::Item>
 102 {
 103     it0: I,
 104     it1: J,
 105     phase: bool, // false ==> it0, true ==> it1
 106 }
 107
 108 /// Create a new `InterleaveShortest` iterator.
 109 pub fn interleave_shortest<I, J>(a: I, b: J) -> InterleaveShortest<I, J>
 110     where I: Iterator,
 111           J: Iterator<Item = I::Item>
 112 {
 113     InterleaveShortest {
 114         it0: a,
 115         it1: b,
 116         phase: false,
 117     }
 118 }
 119
 120 impl<I, J> Iterator for InterleaveShortest<I, J>
 121     where I: Iterator,
 122           J: Iterator<Item = I::Item>
 123 {
 124     type Item = I::Item;
 125
 126     #[inline]
 127     fn next(&mut self) -> Option<I::Item> {
 128         match self.phase {
 129             false => match self.it0.next() {
 130                 None => None,
 131                 e => {
 132                     self.phase = true;
 133                     e
 134                 }
 135             },
 136             true => match self.it1.next() {
 137                 None => None,
 138                 e => {
 139                     self.phase = false;
 140                     e
 141                 }
 142             },
 143         }
 144     }
 145
 146     #[inline]
 147     fn size_hint(&self) -> (usize, Option<usize>) {
 148         let (curr_hint, next_hint) = {
 149             let it0_hint = self.it0.size_hint();
 150             let it1_hint = self.it1.size_hint();
 151             if self.phase {
 152                 (it1_hint, it0_hint)
 153             } else {
 154                 (it0_hint, it1_hint)
 155             }
 156         };
 157         let (curr_lower, curr_upper) = curr_hint;
 158         let (next_lower, next_upper) = next_hint;
 159         let (combined_lower, combined_upper) =
 160             size_hint::mul_scalar(size_hint::min(curr_hint, next_hint), 2);
 161         let lower =
 162             if curr_lower > next_lower {
 163                 combined_lower + 1
 164             } else {
 165                 combined_lower
 166             };
 167         let upper = {
 168             let extra_elem = match (curr_upper, next_upper) {
 169                 (_, None) => false,
 170                 (None, Some(_)) => true,
 171                 (Some(curr_max), Some(next_max)) => curr_max > next_max,
 172             };
 173             if extra_elem {
 174                 combined_upper.and_then(|x| x.checked_add(1))
 175             } else {
 176                 combined_upper
 177             }
 178         };
 179         (lower, upper)
 180     }
 181 }
 182
 183 #[derive(Clone, Debug)]
 184 /// An iterator adaptor that allows putting back a single
 185 /// item to the front of the iterator.
 186 ///
 187 /// Iterator element type is `I::Item`.
 188 pub struct PutBack<I>
 189     where I: Iterator
 190 {
 191     top: Option<I::Item>,
 192     iter: I,
 193 }
 194
 195 /// Create an iterator where you can put back a single item
 196 pub fn put_back<I>(iterable: I) -> PutBack<I::IntoIter>
 197     where I: IntoIterator
 198 {
 199     PutBack {
 200         top: None,
 201         iter: iterable.into_iter(),
 202     }
 203 }
 204
 205 impl<I> PutBack<I>
 206     where I: Iterator
 207 {
 208     /// put back value `value` (builder method)
 209     pub fn with_value(mut self, value: I::Item) -> Self {
 210         self.put_back(value);
 211         self
 212     }
 213
 214     /// Split the `PutBack` into its parts.
 215     #[inline]
 216     pub fn into_parts(self) -> (Option<I::Item>, I) {
 217         let PutBack{top, iter} = self;
 218         (top, iter)
 219     }
 220
 221     /// Put back a single value to the front of the iterator.
 222     ///
 223     /// If a value is already in the put back slot, it is overwritten.
 224     #[inline]
 225     pub fn put_back(&mut self, x: I::Item) {
 226         self.top = Some(x)
 227     }
 228 }
 229
 230 impl<I> Iterator for PutBack<I>
 231     where I: Iterator
 232 {
 233     type Item = I::Item;
 234     #[inline]
 235     fn next(&mut self) -> Option<I::Item> {
 236         match self.top {
 237             None => self.iter.next(),
 238             ref mut some => some.take(),
 239         }
 240     }
 241     #[inline]
 242     fn size_hint(&self) -> (usize, Option<usize>) {
 243         // Not ExactSizeIterator because size may be larger than usize
 244         size_hint::add_scalar(self.iter.size_hint(), self.top.is_some() as usize)
 245     }
 246
 247     fn all<G>(&mut self, mut f: G) -> bool
 248         where G: FnMut(Self::Item) -> bool
 249     {
 250         if let Some(elt) = self.top.take() {
 251             if !f(elt) {
 252                 return false;
 253             }
 254         }
 255         self.iter.all(f)
 256     }
 257
 258     fn fold<Acc, G>(mut self, init: Acc, mut f: G) -> Acc
 259         where G: FnMut(Acc, Self::Item) -> Acc,
 260     {
 261         let mut accum = init;
 262         if let Some(elt) = self.top.take() {
 263             accum = f(accum, elt);
 264         }
 265         self.iter.fold(accum, f)
 266     }
 267 }
 268
 269 #[derive(Debug, Clone)]
 270 /// An iterator adaptor that iterates over the cartesian product of
 271 /// the element sets of two iterators `I` and `J`.
 272 ///
 273 /// Iterator element type is `(I::Item, J::Item)`.
 274 ///
 275 /// See [`.cartesian_product()`](../trait.Itertools.html#method.cartesian_product) for more information.
 276 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
 277 pub struct Product<I, J>
 278     where I: Iterator
 279 {
 280     a: I,
 281     a_cur: Option<I::Item>,
 282     b: J,
 283     b_orig: J,
 284 }
 285
 286 /// Create a new cartesian product iterator
 287 ///
 288 /// Iterator element type is `(I::Item, J::Item)`.
 289 pub fn cartesian_product<I, J>(mut i: I, j: J) -> Product<I, J>
 290     where I: Iterator,
 291           J: Clone + Iterator,
 292           I::Item: Clone
 293 {
 294     Product {
 295         a_cur: i.next(),
 296         a: i,
 297         b: j.clone(),
 298         b_orig: j,
 299     }
 300 }
 301
 302
 303 impl<I, J> Iterator for Product<I, J>
 304     where I: Iterator,
 305           J: Clone + Iterator,
 306           I::Item: Clone
 307 {
 308     type Item = (I::Item, J::Item);
 309     fn next(&mut self) -> Option<(I::Item, J::Item)> {
 310         let elt_b = match self.b.next() {
 311             None => {
 312                 self.b = self.b_orig.clone();
 313                 match self.b.next() {
 314                     None => return None,
 315                     Some(x) => {
 316                         self.a_cur = self.a.next();
 317                         x
 318                     }
 319                 }
 320             }
 321             Some(x) => x
 322         };
 323         match self.a_cur {
 324             None => None,
 325             Some(ref a) => {
 326                 Some((a.clone(), elt_b))
 327             }
 328         }
 329     }
 330
 331     fn size_hint(&self) -> (usize, Option<usize>) {
 332         let has_cur = self.a_cur.is_some() as usize;
 333         // Not ExactSizeIterator because size may be larger than usize
 334         let (b_min, b_max) = self.b.size_hint();
 335
 336         // Compute a * b_orig + b for both lower and upper bound
 337         size_hint::add(
 338             size_hint::mul(self.a.size_hint(), self.b_orig.size_hint()),
 339             (b_min * has_cur, b_max.map(move |x| x * has_cur)))
 340     }
 341
 342     fn fold<Acc, G>(mut self, mut accum: Acc, mut f: G) -> Acc
 343         where G: FnMut(Acc, Self::Item) -> Acc,
 344     {
 345         // use a split loop to handle the loose a_cur as well as avoiding to
 346         // clone b_orig at the end.
 347         if let Some(mut a) = self.a_cur.take() {
 348             let mut b = self.b;
 349             loop {
 350                 accum = b.fold(accum, |acc, elt| f(acc, (a.clone(), elt)));
 351
 352                 // we can only continue iterating a if we had a first element;
 353                 if let Some(next_a) = self.a.next() {
 354                     b = self.b_orig.clone();
 355                     a = next_a;
 356                 } else {
 357                     break;
 358                 }
 359             }
 360         }
 361         accum
 362     }
 363 }
 364
 365 /// A “meta iterator adaptor”. Its closure recives a reference to the iterator
 366 /// and may pick off as many elements as it likes, to produce the next iterator element.
 367 ///
 368 /// Iterator element type is *X*, if the return type of `F` is *Option\<X\>*.
 369 ///
 370 /// See [`.batching()`](../trait.Itertools.html#method.batching) for more information.
 371 #[derive(Clone)]
 372 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
 373 pub struct Batching<I, F> {
 374     f: F,
 375     iter: I,
 376 }
 377
 378 impl<I, F> fmt::Debug for Batching<I, F> where I: fmt::Debug {
 379     debug_fmt_fields!(Batching, iter);
 380 }
 381
 382 /// Create a new Batching iterator.
 383 pub fn batching<I, F>(iter: I, f: F) -> Batching<I, F> {
 384     Batching { f: f, iter: iter }
 385 }
 386
 387 impl<B, F, I> Iterator for Batching<I, F>
 388     where I: Iterator,
 389           F: FnMut(&mut I) -> Option<B>
 390 {
 391     type Item = B;
 392     #[inline]
 393     fn next(&mut self) -> Option<B> {
 394         (self.f)(&mut self.iter)
 395     }
 396
 397     #[inline]
 398     fn size_hint(&self) -> (usize, Option<usize>) {
 399         // No information about closue behavior
 400         (0, None)
 401     }
 402 }
 403
 404 /// An iterator adaptor that steps a number elements in the base iterator
 405 /// for each iteration.
 406 ///
 407 /// The iterator steps by yielding the next element from the base iterator,
 408 /// then skipping forward *n-1* elements.
 409 ///
 410 /// See [`.step()`](../trait.Itertools.html#method.step) for more information.
 411 #[derive(Clone, Debug)]
 412 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
 413 pub struct Step<I> {
 414     iter: Fuse<I>,
 415     skip: usize,
 416 }
 417
 418 /// Create a `Step` iterator.
 419 ///
 420 /// **Panics** if the step is 0.
 421 pub fn step<I>(iter: I, step: usize) -> Step<I>
 422     where I: Iterator
 423 {
 424     assert!(step != 0);
 425     Step {
 426         iter: iter.fuse(),
 427         skip: step - 1,
 428     }
 429 }
 430
 431 impl<I> Iterator for Step<I>
 432     where I: Iterator
 433 {
 434     type Item = I::Item;
 435     #[inline]
 436     fn next(&mut self) -> Option<I::Item> {
 437         let elt = self.iter.next();
 438         if self.skip > 0 {
 439             self.iter.nth(self.skip - 1);
 440         }
 441         elt
 442     }
 443
 444     fn size_hint(&self) -> (usize, Option<usize>) {
 445         let (low, high) = self.iter.size_hint();
 446         let div = |x: usize| {
 447             if x == 0 {
 448                 0
 449             } else {
 450                 1 + (x - 1) / (self.skip + 1)
 451             }
 452         };
 453         (div(low), high.map(div))
 454     }
 455 }
 456
 457 // known size
 458 impl<I> ExactSizeIterator for Step<I>
 459     where I: ExactSizeIterator
 460 {}
 461
 462
 463 struct MergeCore<I, J>
 464     where I: Iterator,
 465           J: Iterator<Item = I::Item>
 466 {
 467     a: Peekable<I>,
 468     b: Peekable<J>,
 469     fused: Option<bool>,
 470 }
 471
 472
 473 impl<I, J> Clone for MergeCore<I, J>
 474     where I: Iterator,
 475           J: Iterator<Item = I::Item>,
 476           Peekable<I>: Clone,
 477           Peekable<J>: Clone
 478 {
 479     fn clone(&self) -> Self {
 480         clone_fields!(MergeCore, self, a, b, fused)
 481     }
 482 }
 483
 484 impl<I, J> MergeCore<I, J>
 485     where I: Iterator,
 486           J: Iterator<Item = I::Item>
 487 {
 488     fn next_with<F>(&mut self, mut less_than: F) -> Option<I::Item>
 489         where F: FnMut(&I::Item, &I::Item) -> bool
 490     {
 491         let less_than = match self.fused {
 492             Some(lt) => lt,
 493             None => match (self.a.peek(), self.b.peek()) {
 494                 (Some(a), Some(b)) => less_than(a, b),
 495                 (Some(_), None) => {
 496                     self.fused = Some(true);
 497                     true
 498                 }
 499                 (None, Some(_)) => {
 500                     self.fused = Some(false);
 501                     false
 502                 }
 503                 (None, None) => return None,
 504             }
 505         };
 506
 507         if less_than {
 508             self.a.next()
 509         } else {
 510             self.b.next()
 511         }
 512     }
 513
 514     fn size_hint(&self) -> (usize, Option<usize>) {
 515         // Not ExactSizeIterator because size may be larger than usize
 516         size_hint::add(self.a.size_hint(), self.b.size_hint())
 517     }
 518 }
 519
 520 /// An iterator adaptor that merges the two base iterators in ascending order.
 521 /// If both base iterators are sorted (ascending), the result is sorted.
 522 ///
 523 /// Iterator element type is `I::Item`.
 524 ///
 525 /// See [`.merge()`](../trait.Itertools.html#method.merge_by) for more information.
 526 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
 527 pub struct Merge<I, J>
 528     where I: Iterator,
 529           J: Iterator<Item = I::Item>
 530 {
 531     merge: MergeCore<I, J>,
 532 }
 533
 534 impl<I, J> Clone for Merge<I, J>
 535     where I: Iterator,
 536           J: Iterator<Item = I::Item>,
 537           Peekable<I>: Clone,
 538           Peekable<J>: Clone
 539 {
 540     fn clone(&self) -> Self {
 541         clone_fields!(Merge, self, merge)
 542     }
 543 }
 544
 545 impl<I, J> fmt::Debug for Merge<I, J>
 546     where I: Iterator + fmt::Debug, J: Iterator<Item = I::Item> + fmt::Debug,
 547           I::Item: fmt::Debug,
 548 {
 549     debug_fmt_fields!(Merge, merge.a, merge.b);
 550 }
 551
 552 /// Create an iterator that merges elements in `i` and `j`.
 553 ///
 554 /// `IntoIterator` enabled version of `i.merge(j)`.
 555 ///
 556 /// ```
 557 /// use itertools::merge;
 558 ///
 559 /// for elt in merge(&[1, 2, 3], &[2, 3, 4]) {
 560 ///     /* loop body */
 561 /// }
 562 /// ```
 563 pub fn merge<I, J>(i: I, j: J) -> Merge<<I as IntoIterator>::IntoIter, <J as IntoIterator>::IntoIter>
 564     where I: IntoIterator,
 565           J: IntoIterator<Item = I::Item>,
 566           I::Item: PartialOrd
 567 {
 568     Merge {
 569         merge: MergeCore {
 570             a: i.into_iter().peekable(),
 571             b: j.into_iter().peekable(),
 572             fused: None,
 573         },
 574     }
 575 }
 576
 577 impl<I, J> Iterator for Merge<I, J>
 578     where I: Iterator,
 579           J: Iterator<Item = I::Item>,
 580           I::Item: PartialOrd
 581 {
 582     type Item = I::Item;
 583
 584     fn next(&mut self) -> Option<I::Item> {
 585         self.merge.next_with(|a, b| a <= b)
 586     }
 587
 588     fn size_hint(&self) -> (usize, Option<usize>) {
 589         self.merge.size_hint()
 590     }
 591 }
 592
 593 /// An iterator adaptor that merges the two base iterators in ascending order.
 594 /// If both base iterators are sorted (ascending), the result is sorted.
 595 ///
 596 /// Iterator element type is `I::Item`.
 597 ///
 598 /// See [`.merge_by()`](../trait.Itertools.html#method.merge_by) for more information.
 599 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
 600 pub struct MergeBy<I, J, F>
 601     where I: Iterator,
 602           J: Iterator<Item = I::Item>
 603 {
 604     merge: MergeCore<I, J>,
 605     cmp: F,
 606 }
 607
 608 impl<I, J, F> fmt::Debug for MergeBy<I, J, F>
 609     where I: Iterator + fmt::Debug, J: Iterator<Item = I::Item> + fmt::Debug,
 610           I::Item: fmt::Debug,
 611 {
 612     debug_fmt_fields!(MergeBy, merge.a, merge.b);
 613 }
 614
 615 /// Create a `MergeBy` iterator.
 616 pub fn merge_by_new<I, J, F>(a: I, b: J, cmp: F) -> MergeBy<I, J, F>
 617     where I: Iterator,
 618           J: Iterator<Item = I::Item>
 619 {
 620     MergeBy {
 621         merge: MergeCore {
 622             a: a.peekable(),
 623             b: b.peekable(),
 624             fused: None,
 625         },
 626         cmp: cmp,
 627     }
 628 }
 629
 630 impl<I, J, F> Clone for MergeBy<I, J, F>
 631     where I: Iterator,
 632           J: Iterator<Item = I::Item>,
 633           Peekable<I>: Clone,
 634           Peekable<J>: Clone,
 635           F: Clone
 636 {
 637     fn clone(&self) -> Self {
 638         clone_fields!(MergeBy, self, merge, cmp)
 639     }
 640 }
 641
 642 impl<I, J, F> Iterator for MergeBy<I, J, F>
 643     where I: Iterator,
 644           J: Iterator<Item = I::Item>,
 645           F: FnMut(&I::Item, &I::Item) -> bool
 646 {
 647     type Item = I::Item;
 648
 649     fn next(&mut self) -> Option<I::Item> {
 650         self.merge.next_with(&mut self.cmp)
 651     }
 652
 653     fn size_hint(&self) -> (usize, Option<usize>) {
 654         self.merge.size_hint()
 655     }
 656 }
 657
 658 #[derive(Clone, Debug)]
 659 pub struct CoalesceCore<I>
 660     where I: Iterator
 661 {
 662     iter: I,
 663     last: Option<I::Item>,
 664 }
 665
 666 impl<I> CoalesceCore<I>
 667     where I: Iterator
 668 {
 669     fn next_with<F>(&mut self, mut f: F) -> Option<I::Item>
 670         where F: FnMut(I::Item, I::Item) -> Result<I::Item, (I::Item, I::Item)>
 671     {
 672         // this fuses the iterator
 673         let mut last = match self.last.take() {
 674             None => return None,
 675             Some(x) => x,
 676         };
 677         for next in &mut self.iter {
 678             match f(last, next) {
 679                 Ok(joined) => last = joined,
 680                 Err((last_, next_)) => {
 681                     self.last = Some(next_);
 682                     return Some(last_);
 683                 }
 684             }
 685         }
 686
 687         Some(last)
 688     }
 689
 690     fn size_hint(&self) -> (usize, Option<usize>) {
 691         let (low, hi) = size_hint::add_scalar(self.iter.size_hint(),
 692                                               self.last.is_some() as usize);
 693         ((low > 0) as usize, hi)
 694     }
 695 }
 696
 697 /// An iterator adaptor that may join together adjacent elements.
 698 ///
 699 /// See [`.coalesce()`](../trait.Itertools.html#method.coalesce) for more information.
 700 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
 701 pub struct Coalesce<I, F>
 702     where I: Iterator
 703 {
 704     iter: CoalesceCore<I>,
 705     f: F,
 706 }
 707
 708 impl<I: Clone, F: Clone> Clone for Coalesce<I, F>
 709     where I: Iterator,
 710           I::Item: Clone
 711 {
 712     fn clone(&self) -> Self {
 713         clone_fields!(Coalesce, self, iter, f)
 714     }
 715 }
 716
 717 impl<I, F> fmt::Debug for Coalesce<I, F>
 718     where I: Iterator + fmt::Debug,
 719           I::Item: fmt::Debug,
 720 {
 721     debug_fmt_fields!(Coalesce, iter);
 722 }
 723
 724 /// Create a new `Coalesce`.
 725 pub fn coalesce<I, F>(mut iter: I, f: F) -> Coalesce<I, F>
 726     where I: Iterator
 727 {
 728     Coalesce {
 729         iter: CoalesceCore {
 730             last: iter.next(),
 731             iter: iter,
 732         },
 733         f: f,
 734     }
 735 }
 736
 737 impl<I, F> Iterator for Coalesce<I, F>
 738     where I: Iterator,
 739           F: FnMut(I::Item, I::Item) -> Result<I::Item, (I::Item, I::Item)>
 740 {
 741     type Item = I::Item;
 742
 743     fn next(&mut self) -> Option<I::Item> {
 744         self.iter.next_with(&mut self.f)
 745     }
 746
 747     fn size_hint(&self) -> (usize, Option<usize>) {
 748         self.iter.size_hint()
 749     }
 750 }
 751
 752 /// An iterator adaptor that removes repeated duplicates.
 753 ///
 754 /// See [`.dedup()`](../trait.Itertools.html#method.dedup) for more information.
 755 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
 756 pub struct Dedup<I>
 757     where I: Iterator
 758 {
 759     iter: CoalesceCore<I>,
 760 }
 761
 762 impl<I: Clone> Clone for Dedup<I>
 763     where I: Iterator,
 764           I::Item: Clone
 765 {
 766     fn clone(&self) -> Self {
 767         clone_fields!(Dedup, self, iter)
 768     }
 769 }
 770
 771 /// Create a new `Dedup`.
 772 pub fn dedup<I>(mut iter: I) -> Dedup<I>
 773     where I: Iterator
 774 {
 775     Dedup {
 776         iter: CoalesceCore {
 777             last: iter.next(),
 778             iter: iter,
 779         },
 780     }
 781 }
 782
 783 impl<I> fmt::Debug for Dedup<I>
 784     where I: Iterator + fmt::Debug,
 785           I::Item: fmt::Debug,
 786 {
 787     debug_fmt_fields!(Dedup, iter);
 788 }
 789
 790 impl<I> Iterator for Dedup<I>
 791     where I: Iterator,
 792           I::Item: PartialEq
 793 {
 794     type Item = I::Item;
 795
 796     fn next(&mut self) -> Option<I::Item> {
 797         self.iter.next_with(|x, y| {
 798             if x == y { Ok(x) } else { Err((x, y)) }
 799         })
 800     }
 801
 802     fn size_hint(&self) -> (usize, Option<usize>) {
 803         self.iter.size_hint()
 804     }
 805
 806     fn fold<Acc, G>(self, mut accum: Acc, mut f: G) -> Acc
 807         where G: FnMut(Acc, Self::Item) -> Acc,
 808     {
 809         if let Some(mut last) = self.iter.last {
 810             accum = self.iter.iter.fold(accum, |acc, elt| {
 811                 if elt == last {
 812                     acc
 813                 } else {
 814                     f(acc, replace(&mut last, elt))
 815                 }
 816             });
 817             f(accum, last)
 818         } else {
 819             accum
 820         }
 821     }
 822 }
 823
 824 /// An iterator adaptor that borrows from a `Clone`-able iterator
 825 /// to only pick off elements while the predicate returns `true`.
 826 ///
 827 /// See [`.take_while_ref()`](../trait.Itertools.html#method.take_while_ref) for more information.
 828 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
 829 pub struct TakeWhileRef<'a, I: 'a, F> {
 830     iter: &'a mut I,
 831     f: F,
 832 }
 833
 834 impl<'a, I, F> fmt::Debug for TakeWhileRef<'a, I, F>
 835     where I: Iterator + fmt::Debug,
 836 {
 837     debug_fmt_fields!(TakeWhileRef, iter);
 838 }
 839
 840 /// Create a new `TakeWhileRef` from a reference to clonable iterator.
 841 pub fn take_while_ref<I, F>(iter: &mut I, f: F) -> TakeWhileRef<I, F>
 842     where I: Iterator + Clone
 843 {
 844     TakeWhileRef { iter: iter, f: f }
 845 }
 846
 847 impl<'a, I, F> Iterator for TakeWhileRef<'a, I, F>
 848     where I: Iterator + Clone,
 849           F: FnMut(&I::Item) -> bool
 850 {
 851     type Item = I::Item;
 852
 853     fn next(&mut self) -> Option<I::Item> {
 854         let old = self.iter.clone();
 855         match self.iter.next() {
 856             None => None,
 857             Some(elt) => {
 858                 if (self.f)(&elt) {
 859                     Some(elt)
 860                 } else {
 861                     *self.iter = old;
 862                     None
 863                 }
 864             }
 865         }
 866     }
 867
 868     fn size_hint(&self) -> (usize, Option<usize>) {
 869         let (_, hi) = self.iter.size_hint();
 870         (0, hi)
 871     }
 872 }
 873
 874 /// An iterator adaptor that filters `Option<A>` iterator elements
 875 /// and produces `A`. Stops on the first `None` encountered.
 876 ///
 877 /// See [`.while_some()`](../trait.Itertools.html#method.while_some) for more information.
 878 #[derive(Clone, Debug)]
 879 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
 880 pub struct WhileSome<I> {
 881     iter: I,
 882 }
 883
 884 /// Create a new `WhileSome<I>`.
 885 pub fn while_some<I>(iter: I) -> WhileSome<I> {
 886     WhileSome { iter: iter }
 887 }
 888
 889 impl<I, A> Iterator for WhileSome<I>
 890     where I: Iterator<Item = Option<A>>
 891 {
 892     type Item = A;
 893
 894     fn next(&mut self) -> Option<A> {
 895         match self.iter.next() {
 896             None | Some(None) => None,
 897             Some(elt) => elt,
 898         }
 899     }
 900
 901     fn size_hint(&self) -> (usize, Option<usize>) {
 902         let sh = self.iter.size_hint();
 903         (0, sh.1)
 904     }
 905 }
 906
 907 /// An iterator to iterate through all combinations in a `Clone`-able iterator that produces tuples
 908 /// of a specific size.
 909 ///
 910 /// See [`.tuple_combinations()`](../trait.Itertools.html#method.tuple_combinations) for more
 911 /// information.
 912 #[derive(Debug)]
 913 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
 914 pub struct TupleCombinations<I, T>
 915     where I: Iterator,
 916           T: HasCombination<I>
 917 {
 918     iter: T::Combination,
 919     _mi: PhantomData<I>,
 920     _mt: PhantomData<T>
 921 }
 922
 923 pub trait HasCombination<I>: Sized {
 924     type Combination: From<I> + Iterator<Item = Self>;
 925 }
 926
 927 /// Create a new `TupleCombinations` from a clonable iterator.
 928 pub fn tuple_combinations<T, I>(iter: I) -> TupleCombinations<I, T>
 929     where I: Iterator + Clone,
 930           I::Item: Clone,
 931           T: HasCombination<I>,
 932 {
 933     TupleCombinations {
 934         iter: T::Combination::from(iter),
 935         _mi: PhantomData,
 936         _mt: PhantomData,
 937     }
 938 }
 939
 940 impl<I, T> Iterator for TupleCombinations<I, T>
 941     where I: Iterator,
 942           T: HasCombination<I>,
 943 {
 944     type Item = T;
 945
 946     fn next(&mut self) -> Option<Self::Item> {
 947         self.iter.next()
 948     }
 949 }
 950
 951 #[derive(Debug)]
 952 pub struct Tuple1Combination<I> {
 953     iter: I,
 954 }
 955
 956 impl<I> From<I> for Tuple1Combination<I> {
 957     fn from(iter: I) -> Self {
 958         Tuple1Combination { iter: iter }
 959     }
 960 }
 961
 962 impl<I: Iterator> Iterator for Tuple1Combination<I> {
 963     type Item = (I::Item,);
 964
 965     fn next(&mut self) -> Option<Self::Item> {
 966         self.iter.next().map(|x| (x,))
 967     }
 968 }
 969
 970 impl<I: Iterator> HasCombination<I> for (I::Item,) {
 971     type Combination = Tuple1Combination<I>;
 972 }
 973
 974 macro_rules! impl_tuple_combination {
 975     ($C:ident $P:ident ; $A:ident, $($I:ident),* ; $($X:ident)*) => (
 976         #[derive(Debug)]
 977         pub struct $C<I: Iterator> {
 978             item: Option<I::Item>,
 979             iter: I,
 980             c: $P<I>,
 981         }
 982
 983         impl<I: Iterator + Clone> From<I> for $C<I> {
 984             fn from(mut iter: I) -> Self {
 985                 $C {
 986                     item: iter.next(),
 987                     iter: iter.clone(),
 988                     c: $P::from(iter),
 989                 }
 990             }
 991         }
 992
 993         impl<I: Iterator + Clone> From<I> for $C<Fuse<I>> {
 994             fn from(iter: I) -> Self {
 995                 let mut iter = iter.fuse();
 996                 $C {
 997                     item: iter.next(),
 998                     iter: iter.clone(),
 999                     c: $P::from(iter),
1000                 }
1001             }
1002         }
1003
1004         impl<I, $A> Iterator for $C<I>
1005             where I: Iterator<Item = $A> + Clone,
1006                   I::Item: Clone
1007         {
1008             type Item = ($($I),*);
1009
1010             fn next(&mut self) -> Option<Self::Item> {
1011                 if let Some(($($X),*,)) = self.c.next() {
1012                     let z = self.item.clone().unwrap();
1013                     Some((z, $($X),*))
1014                 } else {
1015                     self.item = self.iter.next();
1016                     self.item.clone().and_then(|z| {
1017                         self.c = $P::from(self.iter.clone());
1018                         self.c.next().map(|($($X),*,)| (z, $($X),*))
1019                     })
1020                 }
1021             }
1022         }
1023
1024         impl<I, $A> HasCombination<I> for ($($I),*)
1025             where I: Iterator<Item = $A> + Clone,
1026                   I::Item: Clone
1027         {
1028             type Combination = $C<Fuse<I>>;
1029         }
1030     )
1031 }
1032
1033 impl_tuple_combination!(Tuple2Combination Tuple1Combination ; A, A, A ; a);
1034 impl_tuple_combination!(Tuple3Combination Tuple2Combination ; A, A, A, A ; a b);
1035 impl_tuple_combination!(Tuple4Combination Tuple3Combination ; A, A, A, A, A; a b c);
1036
1037
1038 /// An iterator adapter to simply flatten a structure.
1039 ///
1040 /// See [`.flatten()`](../trait.Itertools.html#method.flatten) for more information.
1041 #[derive(Clone, Debug)]
1042 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
1043 pub struct Flatten<I, J> {
1044     iter: I,
1045     front: Option<J>,
1046 }
1047
1048 /// Flatten an iterable of iterables into a single combined sequence of all
1049 /// the elements in the iterables.
1050 ///
1051 /// This is more or less equivalent to `.flat_map` with an identity
1052 /// function.
1053 ///
1054 /// This is an `IntoIterator`-enabled version of the [`.flatten()`][1] adaptor.
1055 ///
1056 /// [1]: trait.Itertools.html#method.flatten
1057 ///
1058 /// ```
1059 /// use itertools::flatten;
1060 ///
1061 /// let data = vec![vec![1, 2, 3], vec![4, 5, 6]];
1062 ///
1063 /// itertools::assert_equal(flatten(&data),
1064 ///                         &[1, 2, 3, 4, 5, 6]);
1065 /// ```
1066 pub fn flatten<I, J>(iterable: I) -> Flatten<I::IntoIter, J>
1067     where I: IntoIterator,
1068           I::Item: IntoIterator<IntoIter=J, Item=J::Item>,
1069           J: Iterator,
1070 {
1071     Flatten {
1072         iter: iterable.into_iter(),
1073         front: None,
1074     }
1075 }
1076
1077 impl<I, J> Iterator for Flatten<I, J>
1078     where I: Iterator,
1079           I::Item: IntoIterator<IntoIter=J, Item=J::Item>,
1080           J: Iterator,
1081 {
1082     type Item = J::Item;
1083     fn next(&mut self) -> Option<Self::Item> {
1084         loop {
1085             if let Some(ref mut f) = self.front {
1086                 match f.next() {
1087                     elt @ Some(_) => return elt,
1088                     None => { }
1089                 }
1090             }
1091             if let Some(next_front) = self.iter.next() {
1092                 self.front = Some(next_front.into_iter());
1093             } else {
1094                 break;
1095             }
1096         }
1097         None
1098     }
1099
1100     // special case to convert segmented iterator into consecutive loops
1101     fn fold<Acc, G>(self, init: Acc, mut f: G) -> Acc
1102         where G: FnMut(Acc, Self::Item) -> Acc,
1103     {
1104         let mut accum = init;
1105         if let Some(iter) = self.front {
1106             accum = fold(iter, accum, &mut f);
1107         }
1108         self.iter.fold(accum, move |accum, iter| fold(iter, accum, &mut f))
1109     }
1110
1111 }
1112
1113 /// An iterator adapter to apply a transformation within a nested `Result`.
1114 ///
1115 /// See [`.map_results()`](../trait.Itertools.html#method.map_results) for more information.
1116 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
1117 pub struct MapResults<I, F> {
1118     iter: I,
1119     f: F
1120 }
1121
1122 /// Create a new `MapResults` iterator.
1123 pub fn map_results<I, F, T, U, E>(iter: I, f: F) -> MapResults<I, F>
1124     where I: Iterator<Item = Result<T, E>>,
1125           F: FnMut(T) -> U,
1126 {
1127     MapResults {
1128         iter: iter,
1129         f: f,
1130     }
1131 }
1132
1133 impl<I, F, T, U, E> Iterator for MapResults<I, F>
1134     where I: Iterator<Item = Result<T, E>>,
1135           F: FnMut(T) -> U,
1136 {
1137     type Item = Result<U, E>;
1138
1139     fn next(&mut self) -> Option<Self::Item> {
1140         self.iter.next().map(|v| v.map(&mut self.f))
1141     }
1142
1143     fn size_hint(&self) -> (usize, Option<usize>) {
1144         self.iter.size_hint()
1145     }
1146
1147     fn fold<Acc, Fold>(self, init: Acc, mut fold_f: Fold) -> Acc
1148         where Fold: FnMut(Acc, Self::Item) -> Acc,
1149     {
1150         let mut f = self.f;
1151         self.iter.fold(init, move |acc, v| fold_f(acc, v.map(&mut f)))
1152     }
1153
1154     fn collect<C>(self) -> C
1155         where C: FromIterator<Self::Item>
1156     {
1157         let mut f = self.f;
1158         self.iter.map(move |v| v.map(&mut f)).collect()
1159     }
1160 }
1161
1162 /// An iterator adapter to get the positions of each element that matches a predicate.
1163 ///
1164 /// See [`.positions()`](../trait.Itertools.html#method.positions) for more information.
1165 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
1166 pub struct Positions<I, F> {
1167     iter: I,
1168     f: F,
1169     count: usize,
1170 }
1171
1172 /// Create a new `Positions` iterator.
1173 pub fn positions<I, F>(iter: I, f: F) -> Positions<I, F>
1174     where I: Iterator,
1175           F: FnMut(I::Item) -> bool,
1176 {
1177     Positions {
1178         iter: iter,
1179         f: f,
1180         count: 0
1181     }
1182 }
1183
1184 impl<I, F> Iterator for Positions<I, F>
1185     where I: Iterator,
1186           F: FnMut(I::Item) -> bool,
1187 {
1188     type Item = usize;
1189
1190     fn next(&mut self) -> Option<Self::Item> {
1191         while let Some(v) = self.iter.next() {
1192             let i = self.count;
1193             self.count = i + 1;
1194             if (self.f)(v) {
1195                 return Some(i);
1196             }
1197         }
1198         None
1199     }
1200
1201     fn size_hint(&self) -> (usize, Option<usize>) {
1202         (0, self.iter.size_hint().1)
1203     }
1204 }
1205
1206 impl<I, F> DoubleEndedIterator for Positions<I, F>
1207     where I: DoubleEndedIterator + ExactSizeIterator,
1208           F: FnMut(I::Item) -> bool,
1209 {
1210     fn next_back(&mut self) -> Option<Self::Item> {
1211         while let Some(v) = self.iter.next_back() {
1212             if (self.f)(v) {
1213                 return Some(self.count + self.iter.len())
1214             }
1215         }
1216         None
1217     }
1218 }
1219
1220 /// An iterator adapter to apply a mutating function to each element before yielding it.
1221 ///
1222 /// See [`.update()`](../trait.Itertools.html#method.update) for more information.
1223 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
1224 pub struct Update<I, F> {
1225     iter: I,
1226     f: F,
1227 }
1228
1229 /// Create a new `Update` iterator.
1230 pub fn update<I, F>(iter: I, f: F) -> Update<I, F>
1231 where
1232     I: Iterator,
1233     F: FnMut(&mut I::Item),
1234 {
1235     Update { iter: iter, f: f }
1236 }
1237
1238 impl<I, F> Iterator for Update<I, F>
1239 where
1240     I: Iterator,
1241     F: FnMut(&mut I::Item),
1242 {
1243     type Item = I::Item;
1244
1245     fn next(&mut self) -> Option<Self::Item> {
1246         if let Some(mut v) = self.iter.next() {
1247             (self.f)(&mut v);
1248             Some(v)
1249         } else {
1250             None
1251         }
1252     }
1253
1254     fn size_hint(&self) -> (usize, Option<usize>) {
1255         self.iter.size_hint()
1256     }
1257
1258     fn fold<Acc, G>(self, init: Acc, mut g: G) -> Acc
1259         where G: FnMut(Acc, Self::Item) -> Acc,
1260     {
1261         let mut f = self.f;
1262         self.iter.fold(init, move |acc, mut v| { f(&mut v); g(acc, v) })
1263     }
1264
1265     // if possible, re-use inner iterator specializations in collect
1266     fn collect<C>(self) -> C
1267         where C: FromIterator<Self::Item>
1268     {
1269         let mut f = self.f;
1270         self.iter.map(move |mut v| { f(&mut v); v }).collect()
1271     }
1272 }
1273
1274 impl<I, F> ExactSizeIterator for Update<I, F>
1275 where
1276     I: ExactSizeIterator,
1277     F: FnMut(&mut I::Item),
1278 {}
1279
1280 impl<I, F> DoubleEndedIterator for Update<I, F>
1281 where
1282     I: DoubleEndedIterator,
1283     F: FnMut(&mut I::Item),
1284 {
1285     fn next_back(&mut self) -> Option<Self::Item> {
1286         if let Some(mut v) = self.iter.next_back() {
1287             (self.f)(&mut v);
1288             Some(v)
1289         } else {
1290             None
1291         }
1292     }
1293 }