src/libcore/iter/adapters/mod.rs

   1 use crate::cmp;
   2 use crate::fmt;
   3 use crate::intrinsics;
   4 use crate::ops::{Add, AddAssign, Try};
   5 use crate::usize;
   6
   7 use super::{from_fn, LoopState};
   8 use super::{DoubleEndedIterator, ExactSizeIterator, FusedIterator, Iterator, TrustedLen};
   9
  10 mod chain;
  11 mod flatten;
  12 mod zip;
  13
  14 pub use self::chain::Chain;
  15 #[stable(feature = "rust1", since = "1.0.0")]
  16 pub use self::flatten::{FlatMap, Flatten};
  17 pub(crate) use self::zip::TrustedRandomAccess;
  18 pub use self::zip::Zip;
  19
  20 /// A double-ended iterator with the direction inverted.
  21 ///
  22 /// This `struct` is created by the [`rev`] method on [`Iterator`]. See its
  23 /// documentation for more.
  24 ///
  25 /// [`rev`]: trait.Iterator.html#method.rev
  26 /// [`Iterator`]: trait.Iterator.html
  27 #[derive(Clone, Debug)]
  28 #[must_use = "iterators are lazy and do nothing unless consumed"]
  29 #[stable(feature = "rust1", since = "1.0.0")]
  30 pub struct Rev<T> {
  31     iter: T,
  32 }
  33 impl<T> Rev<T> {
  34     pub(super) fn new(iter: T) -> Rev<T> {
  35         Rev { iter }
  36     }
  37 }
  38
  39 #[stable(feature = "rust1", since = "1.0.0")]
  40 impl<I> Iterator for Rev<I>
  41 where
  42     I: DoubleEndedIterator,
  43 {
  44     type Item = <I as Iterator>::Item;
  45
  46     #[inline]
  47     fn next(&mut self) -> Option<<I as Iterator>::Item> {
  48         self.iter.next_back()
  49     }
  50     #[inline]
  51     fn size_hint(&self) -> (usize, Option<usize>) {
  52         self.iter.size_hint()
  53     }
  54
  55     #[inline]
  56     fn nth(&mut self, n: usize) -> Option<<I as Iterator>::Item> {
  57         self.iter.nth_back(n)
  58     }
  59
  60     fn try_fold<B, F, R>(&mut self, init: B, f: F) -> R
  61     where
  62         Self: Sized,
  63         F: FnMut(B, Self::Item) -> R,
  64         R: Try<Ok = B>,
  65     {
  66         self.iter.try_rfold(init, f)
  67     }
  68
  69     fn fold<Acc, F>(self, init: Acc, f: F) -> Acc
  70     where
  71         F: FnMut(Acc, Self::Item) -> Acc,
  72     {
  73         self.iter.rfold(init, f)
  74     }
  75
  76     #[inline]
  77     fn find<P>(&mut self, predicate: P) -> Option<Self::Item>
  78     where
  79         P: FnMut(&Self::Item) -> bool,
  80     {
  81         self.iter.rfind(predicate)
  82     }
  83 }
  84
  85 #[stable(feature = "rust1", since = "1.0.0")]
  86 impl<I> DoubleEndedIterator for Rev<I>
  87 where
  88     I: DoubleEndedIterator,
  89 {
  90     #[inline]
  91     fn next_back(&mut self) -> Option<<I as Iterator>::Item> {
  92         self.iter.next()
  93     }
  94
  95     #[inline]
  96     fn nth_back(&mut self, n: usize) -> Option<<I as Iterator>::Item> {
  97         self.iter.nth(n)
  98     }
  99
 100     fn try_rfold<B, F, R>(&mut self, init: B, f: F) -> R
 101     where
 102         Self: Sized,
 103         F: FnMut(B, Self::Item) -> R,
 104         R: Try<Ok = B>,
 105     {
 106         self.iter.try_fold(init, f)
 107     }
 108
 109     fn rfold<Acc, F>(self, init: Acc, f: F) -> Acc
 110     where
 111         F: FnMut(Acc, Self::Item) -> Acc,
 112     {
 113         self.iter.fold(init, f)
 114     }
 115
 116     fn rfind<P>(&mut self, predicate: P) -> Option<Self::Item>
 117     where
 118         P: FnMut(&Self::Item) -> bool,
 119     {
 120         self.iter.find(predicate)
 121     }
 122 }
 123
 124 #[stable(feature = "rust1", since = "1.0.0")]
 125 impl<I> ExactSizeIterator for Rev<I>
 126 where
 127     I: ExactSizeIterator + DoubleEndedIterator,
 128 {
 129     fn len(&self) -> usize {
 130         self.iter.len()
 131     }
 132
 133     fn is_empty(&self) -> bool {
 134         self.iter.is_empty()
 135     }
 136 }
 137
 138 #[stable(feature = "fused", since = "1.26.0")]
 139 impl<I> FusedIterator for Rev<I> where I: FusedIterator + DoubleEndedIterator {}
 140
 141 #[unstable(feature = "trusted_len", issue = "37572")]
 142 unsafe impl<I> TrustedLen for Rev<I> where I: TrustedLen + DoubleEndedIterator {}
 143
 144 /// An iterator that copies the elements of an underlying iterator.
 145 ///
 146 /// This `struct` is created by the [`copied`] method on [`Iterator`]. See its
 147 /// documentation for more.
 148 ///
 149 /// [`copied`]: trait.Iterator.html#method.copied
 150 /// [`Iterator`]: trait.Iterator.html
 151 #[stable(feature = "iter_copied", since = "1.36.0")]
 152 #[must_use = "iterators are lazy and do nothing unless consumed"]
 153 #[derive(Clone, Debug)]
 154 pub struct Copied<I> {
 155     it: I,
 156 }
 157
 158 impl<I> Copied<I> {
 159     pub(super) fn new(it: I) -> Copied<I> {
 160         Copied { it }
 161     }
 162 }
 163
 164 fn copy_fold<T: Copy, Acc>(mut f: impl FnMut(Acc, T) -> Acc) -> impl FnMut(Acc, &T) -> Acc {
 165     move |acc, &elt| f(acc, elt)
 166 }
 167
 168 fn copy_try_fold<T: Copy, Acc, R>(mut f: impl FnMut(Acc, T) -> R) -> impl FnMut(Acc, &T) -> R {
 169     move |acc, &elt| f(acc, elt)
 170 }
 171
 172 #[stable(feature = "iter_copied", since = "1.36.0")]
 173 impl<'a, I, T: 'a> Iterator for Copied<I>
 174 where
 175     I: Iterator<Item = &'a T>,
 176     T: Copy,
 177 {
 178     type Item = T;
 179
 180     fn next(&mut self) -> Option<T> {
 181         self.it.next().copied()
 182     }
 183
 184     fn size_hint(&self) -> (usize, Option<usize>) {
 185         self.it.size_hint()
 186     }
 187
 188     fn try_fold<B, F, R>(&mut self, init: B, f: F) -> R
 189     where
 190         Self: Sized,
 191         F: FnMut(B, Self::Item) -> R,
 192         R: Try<Ok = B>,
 193     {
 194         self.it.try_fold(init, copy_try_fold(f))
 195     }
 196
 197     fn fold<Acc, F>(self, init: Acc, f: F) -> Acc
 198     where
 199         F: FnMut(Acc, Self::Item) -> Acc,
 200     {
 201         self.it.fold(init, copy_fold(f))
 202     }
 203
 204     fn nth(&mut self, n: usize) -> Option<T> {
 205         self.it.nth(n).copied()
 206     }
 207
 208     fn last(self) -> Option<T> {
 209         self.it.last().copied()
 210     }
 211
 212     fn count(self) -> usize {
 213         self.it.count()
 214     }
 215 }
 216
 217 #[stable(feature = "iter_copied", since = "1.36.0")]
 218 impl<'a, I, T: 'a> DoubleEndedIterator for Copied<I>
 219 where
 220     I: DoubleEndedIterator<Item = &'a T>,
 221     T: Copy,
 222 {
 223     fn next_back(&mut self) -> Option<T> {
 224         self.it.next_back().copied()
 225     }
 226
 227     fn try_rfold<B, F, R>(&mut self, init: B, f: F) -> R
 228     where
 229         Self: Sized,
 230         F: FnMut(B, Self::Item) -> R,
 231         R: Try<Ok = B>,
 232     {
 233         self.it.try_rfold(init, copy_try_fold(f))
 234     }
 235
 236     fn rfold<Acc, F>(self, init: Acc, f: F) -> Acc
 237     where
 238         F: FnMut(Acc, Self::Item) -> Acc,
 239     {
 240         self.it.rfold(init, copy_fold(f))
 241     }
 242 }
 243
 244 #[stable(feature = "iter_copied", since = "1.36.0")]
 245 impl<'a, I, T: 'a> ExactSizeIterator for Copied<I>
 246 where
 247     I: ExactSizeIterator<Item = &'a T>,
 248     T: Copy,
 249 {
 250     fn len(&self) -> usize {
 251         self.it.len()
 252     }
 253
 254     fn is_empty(&self) -> bool {
 255         self.it.is_empty()
 256     }
 257 }
 258
 259 #[stable(feature = "iter_copied", since = "1.36.0")]
 260 impl<'a, I, T: 'a> FusedIterator for Copied<I>
 261 where
 262     I: FusedIterator<Item = &'a T>,
 263     T: Copy,
 264 {
 265 }
 266
 267 #[doc(hidden)]
 268 unsafe impl<'a, I, T: 'a> TrustedRandomAccess for Copied<I>
 269 where
 270     I: TrustedRandomAccess<Item = &'a T>,
 271     T: Copy,
 272 {
 273     unsafe fn get_unchecked(&mut self, i: usize) -> Self::Item {
 274         *self.it.get_unchecked(i)
 275     }
 276
 277     #[inline]
 278     fn may_have_side_effect() -> bool {
 279         I::may_have_side_effect()
 280     }
 281 }
 282
 283 #[stable(feature = "iter_copied", since = "1.36.0")]
 284 unsafe impl<'a, I, T: 'a> TrustedLen for Copied<I>
 285 where
 286     I: TrustedLen<Item = &'a T>,
 287     T: Copy,
 288 {
 289 }
 290
 291 /// An iterator that clones the elements of an underlying iterator.
 292 ///
 293 /// This `struct` is created by the [`cloned`] method on [`Iterator`]. See its
 294 /// documentation for more.
 295 ///
 296 /// [`cloned`]: trait.Iterator.html#method.cloned
 297 /// [`Iterator`]: trait.Iterator.html
 298 #[stable(feature = "iter_cloned", since = "1.1.0")]
 299 #[must_use = "iterators are lazy and do nothing unless consumed"]
 300 #[derive(Clone, Debug)]
 301 pub struct Cloned<I> {
 302     it: I,
 303 }
 304 impl<I> Cloned<I> {
 305     pub(super) fn new(it: I) -> Cloned<I> {
 306         Cloned { it }
 307     }
 308 }
 309
 310 fn clone_try_fold<T: Clone, Acc, R>(mut f: impl FnMut(Acc, T) -> R) -> impl FnMut(Acc, &T) -> R {
 311     move |acc, elt| f(acc, elt.clone())
 312 }
 313
 314 #[stable(feature = "iter_cloned", since = "1.1.0")]
 315 impl<'a, I, T: 'a> Iterator for Cloned<I>
 316 where
 317     I: Iterator<Item = &'a T>,
 318     T: Clone,
 319 {
 320     type Item = T;
 321
 322     fn next(&mut self) -> Option<T> {
 323         self.it.next().cloned()
 324     }
 325
 326     fn size_hint(&self) -> (usize, Option<usize>) {
 327         self.it.size_hint()
 328     }
 329
 330     fn try_fold<B, F, R>(&mut self, init: B, f: F) -> R
 331     where
 332         Self: Sized,
 333         F: FnMut(B, Self::Item) -> R,
 334         R: Try<Ok = B>,
 335     {
 336         self.it.try_fold(init, clone_try_fold(f))
 337     }
 338
 339     fn fold<Acc, F>(self, init: Acc, f: F) -> Acc
 340     where
 341         F: FnMut(Acc, Self::Item) -> Acc,
 342     {
 343         self.it.map(T::clone).fold(init, f)
 344     }
 345 }
 346
 347 #[stable(feature = "iter_cloned", since = "1.1.0")]
 348 impl<'a, I, T: 'a> DoubleEndedIterator for Cloned<I>
 349 where
 350     I: DoubleEndedIterator<Item = &'a T>,
 351     T: Clone,
 352 {
 353     fn next_back(&mut self) -> Option<T> {
 354         self.it.next_back().cloned()
 355     }
 356
 357     fn try_rfold<B, F, R>(&mut self, init: B, f: F) -> R
 358     where
 359         Self: Sized,
 360         F: FnMut(B, Self::Item) -> R,
 361         R: Try<Ok = B>,
 362     {
 363         self.it.try_rfold(init, clone_try_fold(f))
 364     }
 365
 366     fn rfold<Acc, F>(self, init: Acc, f: F) -> Acc
 367     where
 368         F: FnMut(Acc, Self::Item) -> Acc,
 369     {
 370         self.it.map(T::clone).rfold(init, f)
 371     }
 372 }
 373
 374 #[stable(feature = "iter_cloned", since = "1.1.0")]
 375 impl<'a, I, T: 'a> ExactSizeIterator for Cloned<I>
 376 where
 377     I: ExactSizeIterator<Item = &'a T>,
 378     T: Clone,
 379 {
 380     fn len(&self) -> usize {
 381         self.it.len()
 382     }
 383
 384     fn is_empty(&self) -> bool {
 385         self.it.is_empty()
 386     }
 387 }
 388
 389 #[stable(feature = "fused", since = "1.26.0")]
 390 impl<'a, I, T: 'a> FusedIterator for Cloned<I>
 391 where
 392     I: FusedIterator<Item = &'a T>,
 393     T: Clone,
 394 {
 395 }
 396
 397 #[doc(hidden)]
 398 unsafe impl<'a, I, T: 'a> TrustedRandomAccess for Cloned<I>
 399 where
 400     I: TrustedRandomAccess<Item = &'a T>,
 401     T: Clone,
 402 {
 403     default unsafe fn get_unchecked(&mut self, i: usize) -> Self::Item {
 404         self.it.get_unchecked(i).clone()
 405     }
 406
 407     #[inline]
 408     default fn may_have_side_effect() -> bool {
 409         true
 410     }
 411 }
 412
 413 #[doc(hidden)]
 414 unsafe impl<'a, I, T: 'a> TrustedRandomAccess for Cloned<I>
 415 where
 416     I: TrustedRandomAccess<Item = &'a T>,
 417     T: Copy,
 418 {
 419     unsafe fn get_unchecked(&mut self, i: usize) -> Self::Item {
 420         *self.it.get_unchecked(i)
 421     }
 422
 423     #[inline]
 424     fn may_have_side_effect() -> bool {
 425         I::may_have_side_effect()
 426     }
 427 }
 428
 429 #[unstable(feature = "trusted_len", issue = "37572")]
 430 unsafe impl<'a, I, T: 'a> TrustedLen for Cloned<I>
 431 where
 432     I: TrustedLen<Item = &'a T>,
 433     T: Clone,
 434 {
 435 }
 436
 437 /// An iterator that repeats endlessly.
 438 ///
 439 /// This `struct` is created by the [`cycle`] method on [`Iterator`]. See its
 440 /// documentation for more.
 441 ///
 442 /// [`cycle`]: trait.Iterator.html#method.cycle
 443 /// [`Iterator`]: trait.Iterator.html
 444 #[derive(Clone, Debug)]
 445 #[must_use = "iterators are lazy and do nothing unless consumed"]
 446 #[stable(feature = "rust1", since = "1.0.0")]
 447 pub struct Cycle<I> {
 448     orig: I,
 449     iter: I,
 450 }
 451 impl<I: Clone> Cycle<I> {
 452     pub(super) fn new(iter: I) -> Cycle<I> {
 453         Cycle { orig: iter.clone(), iter }
 454     }
 455 }
 456
 457 #[stable(feature = "rust1", since = "1.0.0")]
 458 impl<I> Iterator for Cycle<I>
 459 where
 460     I: Clone + Iterator,
 461 {
 462     type Item = <I as Iterator>::Item;
 463
 464     #[inline]
 465     fn next(&mut self) -> Option<<I as Iterator>::Item> {
 466         match self.iter.next() {
 467             None => {
 468                 self.iter = self.orig.clone();
 469                 self.iter.next()
 470             }
 471             y => y,
 472         }
 473     }
 474
 475     #[inline]
 476     fn size_hint(&self) -> (usize, Option<usize>) {
 477         // the cycle iterator is either empty or infinite
 478         match self.orig.size_hint() {
 479             sz @ (0, Some(0)) => sz,
 480             (0, _) => (0, None),
 481             _ => (usize::MAX, None),
 482         }
 483     }
 484
 485     #[inline]
 486     fn try_fold<Acc, F, R>(&mut self, mut acc: Acc, mut f: F) -> R
 487     where
 488         F: FnMut(Acc, Self::Item) -> R,
 489         R: Try<Ok = Acc>,
 490     {
 491         // fully iterate the current iterator. this is necessary because
 492         // `self.iter` may be empty even when `self.orig` isn't
 493         acc = self.iter.try_fold(acc, &mut f)?;
 494         self.iter = self.orig.clone();
 495
 496         // complete a full cycle, keeping track of whether the cycled
 497         // iterator is empty or not. we need to return early in case
 498         // of an empty iterator to prevent an infinite loop
 499         let mut is_empty = true;
 500         acc = self.iter.try_fold(acc, |acc, x| {
 501             is_empty = false;
 502             f(acc, x)
 503         })?;
 504
 505         if is_empty {
 506             return Try::from_ok(acc);
 507         }
 508
 509         loop {
 510             self.iter = self.orig.clone();
 511             acc = self.iter.try_fold(acc, &mut f)?;
 512         }
 513     }
 514 }
 515
 516 #[stable(feature = "fused", since = "1.26.0")]
 517 impl<I> FusedIterator for Cycle<I> where I: Clone + Iterator {}
 518
 519 /// An iterator for stepping iterators by a custom amount.
 520 ///
 521 /// This `struct` is created by the [`step_by`] method on [`Iterator`]. See
 522 /// its documentation for more.
 523 ///
 524 /// [`step_by`]: trait.Iterator.html#method.step_by
 525 /// [`Iterator`]: trait.Iterator.html
 526 #[must_use = "iterators are lazy and do nothing unless consumed"]
 527 #[stable(feature = "iterator_step_by", since = "1.28.0")]
 528 #[derive(Clone, Debug)]
 529 pub struct StepBy<I> {
 530     iter: I,
 531     step: usize,
 532     first_take: bool,
 533 }
 534 impl<I> StepBy<I> {
 535     pub(super) fn new(iter: I, step: usize) -> StepBy<I> {
 536         assert!(step != 0);
 537         StepBy { iter, step: step - 1, first_take: true }
 538     }
 539 }
 540
 541 #[stable(feature = "iterator_step_by", since = "1.28.0")]
 542 impl<I> Iterator for StepBy<I>
 543 where
 544     I: Iterator,
 545 {
 546     type Item = I::Item;
 547
 548     #[inline]
 549     fn next(&mut self) -> Option<Self::Item> {
 550         if self.first_take {
 551             self.first_take = false;
 552             self.iter.next()
 553         } else {
 554             self.iter.nth(self.step)
 555         }
 556     }
 557
 558     #[inline]
 559     fn size_hint(&self) -> (usize, Option<usize>) {
 560         #[inline]
 561         fn first_size(step: usize) -> impl Fn(usize) -> usize {
 562             move |n| if n == 0 { 0 } else { 1 + (n - 1) / (step + 1) }
 563         }
 564
 565         #[inline]
 566         fn other_size(step: usize) -> impl Fn(usize) -> usize {
 567             move |n| n / (step + 1)
 568         }
 569
 570         let (low, high) = self.iter.size_hint();
 571
 572         if self.first_take {
 573             let f = first_size(self.step);
 574             (f(low), high.map(f))
 575         } else {
 576             let f = other_size(self.step);
 577             (f(low), high.map(f))
 578         }
 579     }
 580
 581     #[inline]
 582     fn nth(&mut self, mut n: usize) -> Option<Self::Item> {
 583         if self.first_take {
 584             self.first_take = false;
 585             let first = self.iter.next();
 586             if n == 0 {
 587                 return first;
 588             }
 589             n -= 1;
 590         }
 591         // n and self.step are indices, we need to add 1 to get the amount of elements
 592         // When calling `.nth`, we need to subtract 1 again to convert back to an index
 593         // step + 1 can't overflow because `.step_by` sets `self.step` to `step - 1`
 594         let mut step = self.step + 1;
 595         // n + 1 could overflow
 596         // thus, if n is usize::MAX, instead of adding one, we call .nth(step)
 597         if n == usize::MAX {
 598             self.iter.nth(step - 1);
 599         } else {
 600             n += 1;
 601         }
 602
 603         // overflow handling
 604         loop {
 605             let mul = n.checked_mul(step);
 606             {
 607                 if intrinsics::likely(mul.is_some()) {
 608                     return self.iter.nth(mul.unwrap() - 1);
 609                 }
 610             }
 611             let div_n = usize::MAX / n;
 612             let div_step = usize::MAX / step;
 613             let nth_n = div_n * n;
 614             let nth_step = div_step * step;
 615             let nth = if nth_n > nth_step {
 616                 step -= div_n;
 617                 nth_n
 618             } else {
 619                 n -= div_step;
 620                 nth_step
 621             };
 622             self.iter.nth(nth - 1);
 623         }
 624     }
 625
 626     fn try_fold<Acc, F, R>(&mut self, mut acc: Acc, mut f: F) -> R
 627     where
 628         F: FnMut(Acc, Self::Item) -> R,
 629         R: Try<Ok = Acc>,
 630     {
 631         #[inline]
 632         fn nth<I: Iterator>(iter: &mut I, step: usize) -> impl FnMut() -> Option<I::Item> + '_ {
 633             move || iter.nth(step)
 634         }
 635
 636         if self.first_take {
 637             self.first_take = false;
 638             match self.iter.next() {
 639                 None => return Try::from_ok(acc),
 640                 Some(x) => acc = f(acc, x)?,
 641             }
 642         }
 643         from_fn(nth(&mut self.iter, self.step)).try_fold(acc, f)
 644     }
 645 }
 646
 647 impl<I> StepBy<I>
 648 where
 649     I: ExactSizeIterator,
 650 {
 651     // The zero-based index starting from the end of the iterator of the
 652     // last element. Used in the `DoubleEndedIterator` implementation.
 653     fn next_back_index(&self) -> usize {
 654         let rem = self.iter.len() % (self.step + 1);
 655         if self.first_take {
 656             if rem == 0 { self.step } else { rem - 1 }
 657         } else {
 658             rem
 659         }
 660     }
 661 }
 662
 663 #[stable(feature = "double_ended_step_by_iterator", since = "1.38.0")]
 664 impl<I> DoubleEndedIterator for StepBy<I>
 665 where
 666     I: DoubleEndedIterator + ExactSizeIterator,
 667 {
 668     #[inline]
 669     fn next_back(&mut self) -> Option<Self::Item> {
 670         self.iter.nth_back(self.next_back_index())
 671     }
 672
 673     #[inline]
 674     fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
 675         // `self.iter.nth_back(usize::MAX)` does the right thing here when `n`
 676         // is out of bounds because the length of `self.iter` does not exceed
 677         // `usize::MAX` (because `I: ExactSizeIterator`) and `nth_back` is
 678         // zero-indexed
 679         let n = n.saturating_mul(self.step + 1).saturating_add(self.next_back_index());
 680         self.iter.nth_back(n)
 681     }
 682
 683     fn try_rfold<Acc, F, R>(&mut self, init: Acc, mut f: F) -> R
 684     where
 685         F: FnMut(Acc, Self::Item) -> R,
 686         R: Try<Ok = Acc>,
 687     {
 688         #[inline]
 689         fn nth_back<I: DoubleEndedIterator>(
 690             iter: &mut I,
 691             step: usize,
 692         ) -> impl FnMut() -> Option<I::Item> + '_ {
 693             move || iter.nth_back(step)
 694         }
 695
 696         match self.next_back() {
 697             None => Try::from_ok(init),
 698             Some(x) => {
 699                 let acc = f(init, x)?;
 700                 from_fn(nth_back(&mut self.iter, self.step)).try_fold(acc, f)
 701             }
 702         }
 703     }
 704 }
 705
 706 // StepBy can only make the iterator shorter, so the len will still fit.
 707 #[stable(feature = "iterator_step_by", since = "1.28.0")]
 708 impl<I> ExactSizeIterator for StepBy<I> where I: ExactSizeIterator {}
 709
 710 /// An iterator that maps the values of `iter` with `f`.
 711 ///
 712 /// This `struct` is created by the [`map`] method on [`Iterator`]. See its
 713 /// documentation for more.
 714 ///
 715 /// [`map`]: trait.Iterator.html#method.map
 716 /// [`Iterator`]: trait.Iterator.html
 717 ///
 718 /// # Notes about side effects
 719 ///
 720 /// The [`map`] iterator implements [`DoubleEndedIterator`], meaning that
 721 /// you can also [`map`] backwards:
 722 ///
 723 /// ```rust
 724 /// let v: Vec<i32> = vec![1, 2, 3].into_iter().map(|x| x + 1).rev().collect();
 725 ///
 726 /// assert_eq!(v, [4, 3, 2]);
 727 /// ```
 728 ///
 729 /// [`DoubleEndedIterator`]: trait.DoubleEndedIterator.html
 730 ///
 731 /// But if your closure has state, iterating backwards may act in a way you do
 732 /// not expect. Let's go through an example. First, in the forward direction:
 733 ///
 734 /// ```rust
 735 /// let mut c = 0;
 736 ///
 737 /// for pair in vec!['a', 'b', 'c'].into_iter()
 738 ///                                .map(|letter| { c += 1; (letter, c) }) {
 739 ///     println!("{:?}", pair);
 740 /// }
 741 /// ```
 742 ///
 743 /// This will print "('a', 1), ('b', 2), ('c', 3)".
 744 ///
 745 /// Now consider this twist where we add a call to `rev`. This version will
 746 /// print `('c', 1), ('b', 2), ('a', 3)`. Note that the letters are reversed,
 747 /// but the values of the counter still go in order. This is because `map()` is
 748 /// still being called lazily on each item, but we are popping items off the
 749 /// back of the vector now, instead of shifting them from the front.
 750 ///
 751 /// ```rust
 752 /// let mut c = 0;
 753 ///
 754 /// for pair in vec!['a', 'b', 'c'].into_iter()
 755 ///                                .map(|letter| { c += 1; (letter, c) })
 756 ///                                .rev() {
 757 ///     println!("{:?}", pair);
 758 /// }
 759 /// ```
 760 #[must_use = "iterators are lazy and do nothing unless consumed"]
 761 #[stable(feature = "rust1", since = "1.0.0")]
 762 #[derive(Clone)]
 763 pub struct Map<I, F> {
 764     iter: I,
 765     f: F,
 766 }
 767 impl<I, F> Map<I, F> {
 768     pub(super) fn new(iter: I, f: F) -> Map<I, F> {
 769         Map { iter, f }
 770     }
 771 }
 772
 773 #[stable(feature = "core_impl_debug", since = "1.9.0")]
 774 impl<I: fmt::Debug, F> fmt::Debug for Map<I, F> {
 775     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 776         f.debug_struct("Map").field("iter", &self.iter).finish()
 777     }
 778 }
 779
 780 fn map_fold<T, B, Acc>(
 781     mut f: impl FnMut(T) -> B,
 782     mut g: impl FnMut(Acc, B) -> Acc,
 783 ) -> impl FnMut(Acc, T) -> Acc {
 784     move |acc, elt| g(acc, f(elt))
 785 }
 786
 787 fn map_try_fold<'a, T, B, Acc, R>(
 788     f: &'a mut impl FnMut(T) -> B,
 789     mut g: impl FnMut(Acc, B) -> R + 'a,
 790 ) -> impl FnMut(Acc, T) -> R + 'a {
 791     move |acc, elt| g(acc, f(elt))
 792 }
 793
 794 #[stable(feature = "rust1", since = "1.0.0")]
 795 impl<B, I: Iterator, F> Iterator for Map<I, F>
 796 where
 797     F: FnMut(I::Item) -> B,
 798 {
 799     type Item = B;
 800
 801     #[inline]
 802     fn next(&mut self) -> Option<B> {
 803         self.iter.next().map(&mut self.f)
 804     }
 805
 806     #[inline]
 807     fn size_hint(&self) -> (usize, Option<usize>) {
 808         self.iter.size_hint()
 809     }
 810
 811     fn try_fold<Acc, G, R>(&mut self, init: Acc, g: G) -> R
 812     where
 813         Self: Sized,
 814         G: FnMut(Acc, Self::Item) -> R,
 815         R: Try<Ok = Acc>,
 816     {
 817         self.iter.try_fold(init, map_try_fold(&mut self.f, g))
 818     }
 819
 820     fn fold<Acc, G>(self, init: Acc, g: G) -> Acc
 821     where
 822         G: FnMut(Acc, Self::Item) -> Acc,
 823     {
 824         self.iter.fold(init, map_fold(self.f, g))
 825     }
 826 }
 827
 828 #[stable(feature = "rust1", since = "1.0.0")]
 829 impl<B, I: DoubleEndedIterator, F> DoubleEndedIterator for Map<I, F>
 830 where
 831     F: FnMut(I::Item) -> B,
 832 {
 833     #[inline]
 834     fn next_back(&mut self) -> Option<B> {
 835         self.iter.next_back().map(&mut self.f)
 836     }
 837
 838     fn try_rfold<Acc, G, R>(&mut self, init: Acc, g: G) -> R
 839     where
 840         Self: Sized,
 841         G: FnMut(Acc, Self::Item) -> R,
 842         R: Try<Ok = Acc>,
 843     {
 844         self.iter.try_rfold(init, map_try_fold(&mut self.f, g))
 845     }
 846
 847     fn rfold<Acc, G>(self, init: Acc, g: G) -> Acc
 848     where
 849         G: FnMut(Acc, Self::Item) -> Acc,
 850     {
 851         self.iter.rfold(init, map_fold(self.f, g))
 852     }
 853 }
 854
 855 #[stable(feature = "rust1", since = "1.0.0")]
 856 impl<B, I: ExactSizeIterator, F> ExactSizeIterator for Map<I, F>
 857 where
 858     F: FnMut(I::Item) -> B,
 859 {
 860     fn len(&self) -> usize {
 861         self.iter.len()
 862     }
 863
 864     fn is_empty(&self) -> bool {
 865         self.iter.is_empty()
 866     }
 867 }
 868
 869 #[stable(feature = "fused", since = "1.26.0")]
 870 impl<B, I: FusedIterator, F> FusedIterator for Map<I, F> where F: FnMut(I::Item) -> B {}
 871
 872 #[unstable(feature = "trusted_len", issue = "37572")]
 873 unsafe impl<B, I, F> TrustedLen for Map<I, F>
 874 where
 875     I: TrustedLen,
 876     F: FnMut(I::Item) -> B,
 877 {
 878 }
 879
 880 #[doc(hidden)]
 881 unsafe impl<B, I, F> TrustedRandomAccess for Map<I, F>
 882 where
 883     I: TrustedRandomAccess,
 884     F: FnMut(I::Item) -> B,
 885 {
 886     unsafe fn get_unchecked(&mut self, i: usize) -> Self::Item {
 887         (self.f)(self.iter.get_unchecked(i))
 888     }
 889     #[inline]
 890     fn may_have_side_effect() -> bool {
 891         true
 892     }
 893 }
 894
 895 /// An iterator that filters the elements of `iter` with `predicate`.
 896 ///
 897 /// This `struct` is created by the [`filter`] method on [`Iterator`]. See its
 898 /// documentation for more.
 899 ///
 900 /// [`filter`]: trait.Iterator.html#method.filter
 901 /// [`Iterator`]: trait.Iterator.html
 902 #[must_use = "iterators are lazy and do nothing unless consumed"]
 903 #[stable(feature = "rust1", since = "1.0.0")]
 904 #[derive(Clone)]
 905 pub struct Filter<I, P> {
 906     iter: I,
 907     predicate: P,
 908 }
 909 impl<I, P> Filter<I, P> {
 910     pub(super) fn new(iter: I, predicate: P) -> Filter<I, P> {
 911         Filter { iter, predicate }
 912     }
 913 }
 914
 915 #[stable(feature = "core_impl_debug", since = "1.9.0")]
 916 impl<I: fmt::Debug, P> fmt::Debug for Filter<I, P> {
 917     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 918         f.debug_struct("Filter").field("iter", &self.iter).finish()
 919     }
 920 }
 921
 922 fn filter_fold<T, Acc>(
 923     mut predicate: impl FnMut(&T) -> bool,
 924     mut fold: impl FnMut(Acc, T) -> Acc,
 925 ) -> impl FnMut(Acc, T) -> Acc {
 926     move |acc, item| if predicate(&item) { fold(acc, item) } else { acc }
 927 }
 928
 929 fn filter_try_fold<'a, T, Acc, R: Try<Ok = Acc>>(
 930     predicate: &'a mut impl FnMut(&T) -> bool,
 931     mut fold: impl FnMut(Acc, T) -> R + 'a,
 932 ) -> impl FnMut(Acc, T) -> R + 'a {
 933     move |acc, item| if predicate(&item) { fold(acc, item) } else { R::from_ok(acc) }
 934 }
 935
 936 #[stable(feature = "rust1", since = "1.0.0")]
 937 impl<I: Iterator, P> Iterator for Filter<I, P>
 938 where
 939     P: FnMut(&I::Item) -> bool,
 940 {
 941     type Item = I::Item;
 942
 943     #[inline]
 944     fn next(&mut self) -> Option<I::Item> {
 945         self.iter.find(&mut self.predicate)
 946     }
 947
 948     #[inline]
 949     fn size_hint(&self) -> (usize, Option<usize>) {
 950         let (_, upper) = self.iter.size_hint();
 951         (0, upper) // can't know a lower bound, due to the predicate
 952     }
 953
 954     // this special case allows the compiler to make `.filter(_).count()`
 955     // branchless. Barring perfect branch prediction (which is unattainable in
 956     // the general case), this will be much faster in >90% of cases (containing
 957     // virtually all real workloads) and only a tiny bit slower in the rest.
 958     //
 959     // Having this specialization thus allows us to write `.filter(p).count()`
 960     // where we would otherwise write `.map(|x| p(x) as usize).sum()`, which is
 961     // less readable and also less backwards-compatible to Rust before 1.10.
 962     //
 963     // Using the branchless version will also simplify the LLVM byte code, thus
 964     // leaving more budget for LLVM optimizations.
 965     #[inline]
 966     fn count(self) -> usize {
 967         #[inline]
 968         fn to_usize<T>(mut predicate: impl FnMut(&T) -> bool) -> impl FnMut(T) -> usize {
 969             move |x| predicate(&x) as usize
 970         }
 971
 972         self.iter.map(to_usize(self.predicate)).sum()
 973     }
 974
 975     #[inline]
 976     fn try_fold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R
 977     where
 978         Self: Sized,
 979         Fold: FnMut(Acc, Self::Item) -> R,
 980         R: Try<Ok = Acc>,
 981     {
 982         self.iter.try_fold(init, filter_try_fold(&mut self.predicate, fold))
 983     }
 984
 985     #[inline]
 986     fn fold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
 987     where
 988         Fold: FnMut(Acc, Self::Item) -> Acc,
 989     {
 990         self.iter.fold(init, filter_fold(self.predicate, fold))
 991     }
 992 }
 993
 994 #[stable(feature = "rust1", since = "1.0.0")]
 995 impl<I: DoubleEndedIterator, P> DoubleEndedIterator for Filter<I, P>
 996 where
 997     P: FnMut(&I::Item) -> bool,
 998 {
 999     #[inline]
1000     fn next_back(&mut self) -> Option<I::Item> {
1001         self.iter.rfind(&mut self.predicate)
1002     }
1003
1004     #[inline]
1005     fn try_rfold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R
1006     where
1007         Self: Sized,
1008         Fold: FnMut(Acc, Self::Item) -> R,
1009         R: Try<Ok = Acc>,
1010     {
1011         self.iter.try_rfold(init, filter_try_fold(&mut self.predicate, fold))
1012     }
1013
1014     #[inline]
1015     fn rfold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
1016     where
1017         Fold: FnMut(Acc, Self::Item) -> Acc,
1018     {
1019         self.iter.rfold(init, filter_fold(self.predicate, fold))
1020     }
1021 }
1022
1023 #[stable(feature = "fused", since = "1.26.0")]
1024 impl<I: FusedIterator, P> FusedIterator for Filter<I, P> where P: FnMut(&I::Item) -> bool {}
1025
1026 /// An iterator that uses `f` to both filter and map elements from `iter`.
1027 ///
1028 /// This `struct` is created by the [`filter_map`] method on [`Iterator`]. See its
1029 /// documentation for more.
1030 ///
1031 /// [`filter_map`]: trait.Iterator.html#method.filter_map
1032 /// [`Iterator`]: trait.Iterator.html
1033 #[must_use = "iterators are lazy and do nothing unless consumed"]
1034 #[stable(feature = "rust1", since = "1.0.0")]
1035 #[derive(Clone)]
1036 pub struct FilterMap<I, F> {
1037     iter: I,
1038     f: F,
1039 }
1040 impl<I, F> FilterMap<I, F> {
1041     pub(super) fn new(iter: I, f: F) -> FilterMap<I, F> {
1042         FilterMap { iter, f }
1043     }
1044 }
1045
1046 #[stable(feature = "core_impl_debug", since = "1.9.0")]
1047 impl<I: fmt::Debug, F> fmt::Debug for FilterMap<I, F> {
1048     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1049         f.debug_struct("FilterMap").field("iter", &self.iter).finish()
1050     }
1051 }
1052
1053 fn filter_map_fold<T, B, Acc>(
1054     mut f: impl FnMut(T) -> Option<B>,
1055     mut fold: impl FnMut(Acc, B) -> Acc,
1056 ) -> impl FnMut(Acc, T) -> Acc {
1057     move |acc, item| match f(item) {
1058         Some(x) => fold(acc, x),
1059         None => acc,
1060     }
1061 }
1062
1063 fn filter_map_try_fold<'a, T, B, Acc, R: Try<Ok = Acc>>(
1064     f: &'a mut impl FnMut(T) -> Option<B>,
1065     mut fold: impl FnMut(Acc, B) -> R + 'a,
1066 ) -> impl FnMut(Acc, T) -> R + 'a {
1067     move |acc, item| match f(item) {
1068         Some(x) => fold(acc, x),
1069         None => R::from_ok(acc),
1070     }
1071 }
1072
1073 #[stable(feature = "rust1", since = "1.0.0")]
1074 impl<B, I: Iterator, F> Iterator for FilterMap<I, F>
1075 where
1076     F: FnMut(I::Item) -> Option<B>,
1077 {
1078     type Item = B;
1079
1080     #[inline]
1081     fn next(&mut self) -> Option<B> {
1082         self.iter.find_map(&mut self.f)
1083     }
1084
1085     #[inline]
1086     fn size_hint(&self) -> (usize, Option<usize>) {
1087         let (_, upper) = self.iter.size_hint();
1088         (0, upper) // can't know a lower bound, due to the predicate
1089     }
1090
1091     #[inline]
1092     fn try_fold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R
1093     where
1094         Self: Sized,
1095         Fold: FnMut(Acc, Self::Item) -> R,
1096         R: Try<Ok = Acc>,
1097     {
1098         self.iter.try_fold(init, filter_map_try_fold(&mut self.f, fold))
1099     }
1100
1101     #[inline]
1102     fn fold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
1103     where
1104         Fold: FnMut(Acc, Self::Item) -> Acc,
1105     {
1106         self.iter.fold(init, filter_map_fold(self.f, fold))
1107     }
1108 }
1109
1110 #[stable(feature = "rust1", since = "1.0.0")]
1111 impl<B, I: DoubleEndedIterator, F> DoubleEndedIterator for FilterMap<I, F>
1112 where
1113     F: FnMut(I::Item) -> Option<B>,
1114 {
1115     #[inline]
1116     fn next_back(&mut self) -> Option<B> {
1117         #[inline]
1118         fn find<T, B>(
1119             f: &mut impl FnMut(T) -> Option<B>,
1120         ) -> impl FnMut((), T) -> LoopState<(), B> + '_ {
1121             move |(), x| match f(x) {
1122                 Some(x) => LoopState::Break(x),
1123                 None => LoopState::Continue(()),
1124             }
1125         }
1126
1127         self.iter.try_rfold((), find(&mut self.f)).break_value()
1128     }
1129
1130     #[inline]
1131     fn try_rfold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R
1132     where
1133         Self: Sized,
1134         Fold: FnMut(Acc, Self::Item) -> R,
1135         R: Try<Ok = Acc>,
1136     {
1137         self.iter.try_rfold(init, filter_map_try_fold(&mut self.f, fold))
1138     }
1139
1140     #[inline]
1141     fn rfold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
1142     where
1143         Fold: FnMut(Acc, Self::Item) -> Acc,
1144     {
1145         self.iter.rfold(init, filter_map_fold(self.f, fold))
1146     }
1147 }
1148
1149 #[stable(feature = "fused", since = "1.26.0")]
1150 impl<B, I: FusedIterator, F> FusedIterator for FilterMap<I, F> where F: FnMut(I::Item) -> Option<B> {}
1151
1152 /// An iterator that yields the current count and the element during iteration.
1153 ///
1154 /// This `struct` is created by the [`enumerate`] method on [`Iterator`]. See its
1155 /// documentation for more.
1156 ///
1157 /// [`enumerate`]: trait.Iterator.html#method.enumerate
1158 /// [`Iterator`]: trait.Iterator.html
1159 #[derive(Clone, Debug)]
1160 #[must_use = "iterators are lazy and do nothing unless consumed"]
1161 #[stable(feature = "rust1", since = "1.0.0")]
1162 pub struct Enumerate<I> {
1163     iter: I,
1164     count: usize,
1165 }
1166 impl<I> Enumerate<I> {
1167     pub(super) fn new(iter: I) -> Enumerate<I> {
1168         Enumerate { iter, count: 0 }
1169     }
1170 }
1171
1172 #[stable(feature = "rust1", since = "1.0.0")]
1173 impl<I> Iterator for Enumerate<I>
1174 where
1175     I: Iterator,
1176 {
1177     type Item = (usize, <I as Iterator>::Item);
1178
1179     /// # Overflow Behavior
1180     ///
1181     /// The method does no guarding against overflows, so enumerating more than
1182     /// `usize::MAX` elements either produces the wrong result or panics. If
1183     /// debug assertions are enabled, a panic is guaranteed.
1184     ///
1185     /// # Panics
1186     ///
1187     /// Might panic if the index of the element overflows a `usize`.
1188     #[inline]
1189     fn next(&mut self) -> Option<(usize, <I as Iterator>::Item)> {
1190         let a = self.iter.next()?;
1191         let i = self.count;
1192         // Possible undefined overflow.
1193         AddAssign::add_assign(&mut self.count, 1);
1194         Some((i, a))
1195     }
1196
1197     #[inline]
1198     fn size_hint(&self) -> (usize, Option<usize>) {
1199         self.iter.size_hint()
1200     }
1201
1202     #[inline]
1203     fn nth(&mut self, n: usize) -> Option<(usize, I::Item)> {
1204         let a = self.iter.nth(n)?;
1205         // Possible undefined overflow.
1206         let i = Add::add(self.count, n);
1207         self.count = Add::add(i, 1);
1208         Some((i, a))
1209     }
1210
1211     #[inline]
1212     fn count(self) -> usize {
1213         self.iter.count()
1214     }
1215
1216     #[inline]
1217     fn try_fold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R
1218     where
1219         Self: Sized,
1220         Fold: FnMut(Acc, Self::Item) -> R,
1221         R: Try<Ok = Acc>,
1222     {
1223         #[inline]
1224         fn enumerate<'a, T, Acc, R>(
1225             count: &'a mut usize,
1226             mut fold: impl FnMut(Acc, (usize, T)) -> R + 'a,
1227         ) -> impl FnMut(Acc, T) -> R + 'a {
1228             move |acc, item| {
1229                 let acc = fold(acc, (*count, item));
1230                 // Possible undefined overflow.
1231                 AddAssign::add_assign(count, 1);
1232                 acc
1233             }
1234         }
1235
1236         self.iter.try_fold(init, enumerate(&mut self.count, fold))
1237     }
1238
1239     #[inline]
1240     fn fold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
1241     where
1242         Fold: FnMut(Acc, Self::Item) -> Acc,
1243     {
1244         #[inline]
1245         fn enumerate<T, Acc>(
1246             mut count: usize,
1247             mut fold: impl FnMut(Acc, (usize, T)) -> Acc,
1248         ) -> impl FnMut(Acc, T) -> Acc {
1249             move |acc, item| {
1250                 let acc = fold(acc, (count, item));
1251                 // Possible undefined overflow.
1252                 AddAssign::add_assign(&mut count, 1);
1253                 acc
1254             }
1255         }
1256
1257         self.iter.fold(init, enumerate(self.count, fold))
1258     }
1259 }
1260
1261 #[stable(feature = "rust1", since = "1.0.0")]
1262 impl<I> DoubleEndedIterator for Enumerate<I>
1263 where
1264     I: ExactSizeIterator + DoubleEndedIterator,
1265 {
1266     #[inline]
1267     fn next_back(&mut self) -> Option<(usize, <I as Iterator>::Item)> {
1268         let a = self.iter.next_back()?;
1269         let len = self.iter.len();
1270         // Can safely add, `ExactSizeIterator` promises that the number of
1271         // elements fits into a `usize`.
1272         Some((self.count + len, a))
1273     }
1274
1275     #[inline]
1276     fn nth_back(&mut self, n: usize) -> Option<(usize, <I as Iterator>::Item)> {
1277         let a = self.iter.nth_back(n)?;
1278         let len = self.iter.len();
1279         // Can safely add, `ExactSizeIterator` promises that the number of
1280         // elements fits into a `usize`.
1281         Some((self.count + len, a))
1282     }
1283
1284     #[inline]
1285     fn try_rfold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R
1286     where
1287         Self: Sized,
1288         Fold: FnMut(Acc, Self::Item) -> R,
1289         R: Try<Ok = Acc>,
1290     {
1291         // Can safely add and subtract the count, as `ExactSizeIterator` promises
1292         // that the number of elements fits into a `usize`.
1293         fn enumerate<T, Acc, R>(
1294             mut count: usize,
1295             mut fold: impl FnMut(Acc, (usize, T)) -> R,
1296         ) -> impl FnMut(Acc, T) -> R {
1297             move |acc, item| {
1298                 count -= 1;
1299                 fold(acc, (count, item))
1300             }
1301         }
1302
1303         let count = self.count + self.iter.len();
1304         self.iter.try_rfold(init, enumerate(count, fold))
1305     }
1306
1307     #[inline]
1308     fn rfold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
1309     where
1310         Fold: FnMut(Acc, Self::Item) -> Acc,
1311     {
1312         // Can safely add and subtract the count, as `ExactSizeIterator` promises
1313         // that the number of elements fits into a `usize`.
1314         fn enumerate<T, Acc>(
1315             mut count: usize,
1316             mut fold: impl FnMut(Acc, (usize, T)) -> Acc,
1317         ) -> impl FnMut(Acc, T) -> Acc {
1318             move |acc, item| {
1319                 count -= 1;
1320                 fold(acc, (count, item))
1321             }
1322         }
1323
1324         let count = self.count + self.iter.len();
1325         self.iter.rfold(init, enumerate(count, fold))
1326     }
1327 }
1328
1329 #[stable(feature = "rust1", since = "1.0.0")]
1330 impl<I> ExactSizeIterator for Enumerate<I>
1331 where
1332     I: ExactSizeIterator,
1333 {
1334     fn len(&self) -> usize {
1335         self.iter.len()
1336     }
1337
1338     fn is_empty(&self) -> bool {
1339         self.iter.is_empty()
1340     }
1341 }
1342
1343 #[doc(hidden)]
1344 unsafe impl<I> TrustedRandomAccess for Enumerate<I>
1345 where
1346     I: TrustedRandomAccess,
1347 {
1348     unsafe fn get_unchecked(&mut self, i: usize) -> (usize, I::Item) {
1349         (self.count + i, self.iter.get_unchecked(i))
1350     }
1351
1352     fn may_have_side_effect() -> bool {
1353         I::may_have_side_effect()
1354     }
1355 }
1356
1357 #[stable(feature = "fused", since = "1.26.0")]
1358 impl<I> FusedIterator for Enumerate<I> where I: FusedIterator {}
1359
1360 #[unstable(feature = "trusted_len", issue = "37572")]
1361 unsafe impl<I> TrustedLen for Enumerate<I> where I: TrustedLen {}
1362
1363 /// An iterator with a `peek()` that returns an optional reference to the next
1364 /// element.
1365 ///
1366 /// This `struct` is created by the [`peekable`] method on [`Iterator`]. See its
1367 /// documentation for more.
1368 ///
1369 /// [`peekable`]: trait.Iterator.html#method.peekable
1370 /// [`Iterator`]: trait.Iterator.html
1371 #[derive(Clone, Debug)]
1372 #[must_use = "iterators are lazy and do nothing unless consumed"]
1373 #[stable(feature = "rust1", since = "1.0.0")]
1374 pub struct Peekable<I: Iterator> {
1375     iter: I,
1376     /// Remember a peeked value, even if it was None.
1377     peeked: Option<Option<I::Item>>,
1378 }
1379 impl<I: Iterator> Peekable<I> {
1380     pub(super) fn new(iter: I) -> Peekable<I> {
1381         Peekable { iter, peeked: None }
1382     }
1383 }
1384
1385 // Peekable must remember if a None has been seen in the `.peek()` method.
1386 // It ensures that `.peek(); .peek();` or `.peek(); .next();` only advances the
1387 // underlying iterator at most once. This does not by itself make the iterator
1388 // fused.
1389 #[stable(feature = "rust1", since = "1.0.0")]
1390 impl<I: Iterator> Iterator for Peekable<I> {
1391     type Item = I::Item;
1392
1393     #[inline]
1394     fn next(&mut self) -> Option<I::Item> {
1395         match self.peeked.take() {
1396             Some(v) => v,
1397             None => self.iter.next(),
1398         }
1399     }
1400
1401     #[inline]
1402     #[rustc_inherit_overflow_checks]
1403     fn count(mut self) -> usize {
1404         match self.peeked.take() {
1405             Some(None) => 0,
1406             Some(Some(_)) => 1 + self.iter.count(),
1407             None => self.iter.count(),
1408         }
1409     }
1410
1411     #[inline]
1412     fn nth(&mut self, n: usize) -> Option<I::Item> {
1413         match self.peeked.take() {
1414             Some(None) => None,
1415             Some(v @ Some(_)) if n == 0 => v,
1416             Some(Some(_)) => self.iter.nth(n - 1),
1417             None => self.iter.nth(n),
1418         }
1419     }
1420
1421     #[inline]
1422     fn last(mut self) -> Option<I::Item> {
1423         let peek_opt = match self.peeked.take() {
1424             Some(None) => return None,
1425             Some(v) => v,
1426             None => None,
1427         };
1428         self.iter.last().or(peek_opt)
1429     }
1430
1431     #[inline]
1432     fn size_hint(&self) -> (usize, Option<usize>) {
1433         let peek_len = match self.peeked {
1434             Some(None) => return (0, Some(0)),
1435             Some(Some(_)) => 1,
1436             None => 0,
1437         };
1438         let (lo, hi) = self.iter.size_hint();
1439         let lo = lo.saturating_add(peek_len);
1440         let hi = match hi {
1441             Some(x) => x.checked_add(peek_len),
1442             None => None,
1443         };
1444         (lo, hi)
1445     }
1446
1447     #[inline]
1448     fn try_fold<B, F, R>(&mut self, init: B, mut f: F) -> R
1449     where
1450         Self: Sized,
1451         F: FnMut(B, Self::Item) -> R,
1452         R: Try<Ok = B>,
1453     {
1454         let acc = match self.peeked.take() {
1455             Some(None) => return Try::from_ok(init),
1456             Some(Some(v)) => f(init, v)?,
1457             None => init,
1458         };
1459         self.iter.try_fold(acc, f)
1460     }
1461
1462     #[inline]
1463     fn fold<Acc, Fold>(self, init: Acc, mut fold: Fold) -> Acc
1464     where
1465         Fold: FnMut(Acc, Self::Item) -> Acc,
1466     {
1467         let acc = match self.peeked {
1468             Some(None) => return init,
1469             Some(Some(v)) => fold(init, v),
1470             None => init,
1471         };
1472         self.iter.fold(acc, fold)
1473     }
1474 }
1475
1476 #[stable(feature = "double_ended_peek_iterator", since = "1.38.0")]
1477 impl<I> DoubleEndedIterator for Peekable<I>
1478 where
1479     I: DoubleEndedIterator,
1480 {
1481     #[inline]
1482     fn next_back(&mut self) -> Option<Self::Item> {
1483         match self.peeked.as_mut() {
1484             Some(v @ Some(_)) => self.iter.next_back().or_else(|| v.take()),
1485             Some(None) => None,
1486             None => self.iter.next_back(),
1487         }
1488     }
1489
1490     #[inline]
1491     fn try_rfold<B, F, R>(&mut self, init: B, mut f: F) -> R
1492     where
1493         Self: Sized,
1494         F: FnMut(B, Self::Item) -> R,
1495         R: Try<Ok = B>,
1496     {
1497         match self.peeked.take() {
1498             Some(None) => Try::from_ok(init),
1499             Some(Some(v)) => match self.iter.try_rfold(init, &mut f).into_result() {
1500                 Ok(acc) => f(acc, v),
1501                 Err(e) => {
1502                     self.peeked = Some(Some(v));
1503                     Try::from_error(e)
1504                 }
1505             },
1506             None => self.iter.try_rfold(init, f),
1507         }
1508     }
1509
1510     #[inline]
1511     fn rfold<Acc, Fold>(self, init: Acc, mut fold: Fold) -> Acc
1512     where
1513         Fold: FnMut(Acc, Self::Item) -> Acc,
1514     {
1515         match self.peeked {
1516             Some(None) => init,
1517             Some(Some(v)) => {
1518                 let acc = self.iter.rfold(init, &mut fold);
1519                 fold(acc, v)
1520             }
1521             None => self.iter.rfold(init, fold),
1522         }
1523     }
1524 }
1525
1526 #[stable(feature = "rust1", since = "1.0.0")]
1527 impl<I: ExactSizeIterator> ExactSizeIterator for Peekable<I> {}
1528
1529 #[stable(feature = "fused", since = "1.26.0")]
1530 impl<I: FusedIterator> FusedIterator for Peekable<I> {}
1531
1532 impl<I: Iterator> Peekable<I> {
1533     /// Returns a reference to the next() value without advancing the iterator.
1534     ///
1535     /// Like [`next`], if there is a value, it is wrapped in a `Some(T)`.
1536     /// But if the iteration is over, `None` is returned.
1537     ///
1538     /// [`next`]: trait.Iterator.html#tymethod.next
1539     ///
1540     /// Because `peek()` returns a reference, and many iterators iterate over
1541     /// references, there can be a possibly confusing situation where the
1542     /// return value is a double reference. You can see this effect in the
1543     /// examples below.
1544     ///
1545     /// # Examples
1546     ///
1547     /// Basic usage:
1548     ///
1549     /// ```
1550     /// let xs = [1, 2, 3];
1551     ///
1552     /// let mut iter = xs.iter().peekable();
1553     ///
1554     /// // peek() lets us see into the future
1555     /// assert_eq!(iter.peek(), Some(&&1));
1556     /// assert_eq!(iter.next(), Some(&1));
1557     ///
1558     /// assert_eq!(iter.next(), Some(&2));
1559     ///
1560     /// // The iterator does not advance even if we `peek` multiple times
1561     /// assert_eq!(iter.peek(), Some(&&3));
1562     /// assert_eq!(iter.peek(), Some(&&3));
1563     ///
1564     /// assert_eq!(iter.next(), Some(&3));
1565     ///
1566     /// // After the iterator is finished, so is `peek()`
1567     /// assert_eq!(iter.peek(), None);
1568     /// assert_eq!(iter.next(), None);
1569     /// ```
1570     #[inline]
1571     #[stable(feature = "rust1", since = "1.0.0")]
1572     pub fn peek(&mut self) -> Option<&I::Item> {
1573         let iter = &mut self.iter;
1574         self.peeked.get_or_insert_with(|| iter.next()).as_ref()
1575     }
1576 }
1577
1578 /// An iterator that rejects elements while `predicate` returns `true`.
1579 ///
1580 /// This `struct` is created by the [`skip_while`] method on [`Iterator`]. See its
1581 /// documentation for more.
1582 ///
1583 /// [`skip_while`]: trait.Iterator.html#method.skip_while
1584 /// [`Iterator`]: trait.Iterator.html
1585 #[must_use = "iterators are lazy and do nothing unless consumed"]
1586 #[stable(feature = "rust1", since = "1.0.0")]
1587 #[derive(Clone)]
1588 pub struct SkipWhile<I, P> {
1589     iter: I,
1590     flag: bool,
1591     predicate: P,
1592 }
1593 impl<I, P> SkipWhile<I, P> {
1594     pub(super) fn new(iter: I, predicate: P) -> SkipWhile<I, P> {
1595         SkipWhile { iter, flag: false, predicate }
1596     }
1597 }
1598
1599 #[stable(feature = "core_impl_debug", since = "1.9.0")]
1600 impl<I: fmt::Debug, P> fmt::Debug for SkipWhile<I, P> {
1601     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1602         f.debug_struct("SkipWhile").field("iter", &self.iter).field("flag", &self.flag).finish()
1603     }
1604 }
1605
1606 #[stable(feature = "rust1", since = "1.0.0")]
1607 impl<I: Iterator, P> Iterator for SkipWhile<I, P>
1608 where
1609     P: FnMut(&I::Item) -> bool,
1610 {
1611     type Item = I::Item;
1612
1613     #[inline]
1614     fn next(&mut self) -> Option<I::Item> {
1615         fn check<'a, T>(
1616             flag: &'a mut bool,
1617             pred: &'a mut impl FnMut(&T) -> bool,
1618         ) -> impl FnMut(&T) -> bool + 'a {
1619             move |x| {
1620                 if *flag || !pred(x) {
1621                     *flag = true;
1622                     true
1623                 } else {
1624                     false
1625                 }
1626             }
1627         }
1628
1629         let flag = &mut self.flag;
1630         let pred = &mut self.predicate;
1631         self.iter.find(check(flag, pred))
1632     }
1633
1634     #[inline]
1635     fn size_hint(&self) -> (usize, Option<usize>) {
1636         let (_, upper) = self.iter.size_hint();
1637         (0, upper) // can't know a lower bound, due to the predicate
1638     }
1639
1640     #[inline]
1641     fn try_fold<Acc, Fold, R>(&mut self, mut init: Acc, mut fold: Fold) -> R
1642     where
1643         Self: Sized,
1644         Fold: FnMut(Acc, Self::Item) -> R,
1645         R: Try<Ok = Acc>,
1646     {
1647         if !self.flag {
1648             match self.next() {
1649                 Some(v) => init = fold(init, v)?,
1650                 None => return Try::from_ok(init),
1651             }
1652         }
1653         self.iter.try_fold(init, fold)
1654     }
1655
1656     #[inline]
1657     fn fold<Acc, Fold>(mut self, mut init: Acc, mut fold: Fold) -> Acc
1658     where
1659         Fold: FnMut(Acc, Self::Item) -> Acc,
1660     {
1661         if !self.flag {
1662             match self.next() {
1663                 Some(v) => init = fold(init, v),
1664                 None => return init,
1665             }
1666         }
1667         self.iter.fold(init, fold)
1668     }
1669 }
1670
1671 #[stable(feature = "fused", since = "1.26.0")]
1672 impl<I, P> FusedIterator for SkipWhile<I, P>
1673 where
1674     I: FusedIterator,
1675     P: FnMut(&I::Item) -> bool,
1676 {
1677 }
1678
1679 /// An iterator that only accepts elements while `predicate` returns `true`.
1680 ///
1681 /// This `struct` is created by the [`take_while`] method on [`Iterator`]. See its
1682 /// documentation for more.
1683 ///
1684 /// [`take_while`]: trait.Iterator.html#method.take_while
1685 /// [`Iterator`]: trait.Iterator.html
1686 #[must_use = "iterators are lazy and do nothing unless consumed"]
1687 #[stable(feature = "rust1", since = "1.0.0")]
1688 #[derive(Clone)]
1689 pub struct TakeWhile<I, P> {
1690     iter: I,
1691     flag: bool,
1692     predicate: P,
1693 }
1694 impl<I, P> TakeWhile<I, P> {
1695     pub(super) fn new(iter: I, predicate: P) -> TakeWhile<I, P> {
1696         TakeWhile { iter, flag: false, predicate }
1697     }
1698 }
1699
1700 #[stable(feature = "core_impl_debug", since = "1.9.0")]
1701 impl<I: fmt::Debug, P> fmt::Debug for TakeWhile<I, P> {
1702     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1703         f.debug_struct("TakeWhile").field("iter", &self.iter).field("flag", &self.flag).finish()
1704     }
1705 }
1706
1707 #[stable(feature = "rust1", since = "1.0.0")]
1708 impl<I: Iterator, P> Iterator for TakeWhile<I, P>
1709 where
1710     P: FnMut(&I::Item) -> bool,
1711 {
1712     type Item = I::Item;
1713
1714     #[inline]
1715     fn next(&mut self) -> Option<I::Item> {
1716         if self.flag {
1717             None
1718         } else {
1719             let x = self.iter.next()?;
1720             if (self.predicate)(&x) {
1721                 Some(x)
1722             } else {
1723                 self.flag = true;
1724                 None
1725             }
1726         }
1727     }
1728
1729     #[inline]
1730     fn size_hint(&self) -> (usize, Option<usize>) {
1731         if self.flag {
1732             (0, Some(0))
1733         } else {
1734             let (_, upper) = self.iter.size_hint();
1735             (0, upper) // can't know a lower bound, due to the predicate
1736         }
1737     }
1738
1739     #[inline]
1740     fn try_fold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R
1741     where
1742         Self: Sized,
1743         Fold: FnMut(Acc, Self::Item) -> R,
1744         R: Try<Ok = Acc>,
1745     {
1746         fn check<'a, T, Acc, R: Try<Ok = Acc>>(
1747             flag: &'a mut bool,
1748             p: &'a mut impl FnMut(&T) -> bool,
1749             mut fold: impl FnMut(Acc, T) -> R + 'a,
1750         ) -> impl FnMut(Acc, T) -> LoopState<Acc, R> + 'a {
1751             move |acc, x| {
1752                 if p(&x) {
1753                     LoopState::from_try(fold(acc, x))
1754                 } else {
1755                     *flag = true;
1756                     LoopState::Break(Try::from_ok(acc))
1757                 }
1758             }
1759         }
1760
1761         if self.flag {
1762             Try::from_ok(init)
1763         } else {
1764             let flag = &mut self.flag;
1765             let p = &mut self.predicate;
1766             self.iter.try_fold(init, check(flag, p, fold)).into_try()
1767         }
1768     }
1769 }
1770
1771 /// An iterator that only accepts elements while `predicate` returns `Some(_)`.
1772 ///
1773 /// This `struct` is created by the [`map_while`] method on [`Iterator`]. See its
1774 /// documentation for more.
1775 ///
1776 /// [`map_while`]: trait.Iterator.html#method.map_while
1777 /// [`Iterator`]: trait.Iterator.html
1778 #[must_use = "iterators are lazy and do nothing unless consumed"]
1779 #[unstable(feature = "iter_map_while", reason = "recently added", issue = "68537")]
1780 #[derive(Clone)]
1781 pub struct MapWhile<I, P> {
1782     iter: I,
1783     finished: bool,
1784     predicate: P,
1785 }
1786
1787 impl<I, P> MapWhile<I, P> {
1788     pub(super) fn new(iter: I, predicate: P) -> MapWhile<I, P> {
1789         MapWhile { iter, finished: false, predicate }
1790     }
1791 }
1792
1793 #[unstable(feature = "iter_map_while", reason = "recently added", issue = "68537")]
1794 impl<I: fmt::Debug, P> fmt::Debug for MapWhile<I, P> {
1795     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1796         f.debug_struct("MapWhile").field("iter", &self.iter).field("flag", &self.finished).finish()
1797     }
1798 }
1799
1800 #[unstable(feature = "iter_map_while", reason = "recently added", issue = "68537")]
1801 impl<B, I: Iterator, P> Iterator for MapWhile<I, P>
1802 where
1803     P: FnMut(I::Item) -> Option<B>,
1804 {
1805     type Item = B;
1806
1807     #[inline]
1808     fn next(&mut self) -> Option<B> {
1809         if self.finished {
1810             None
1811         } else {
1812             let x = self.iter.next()?;
1813             let ret = (self.predicate)(x);
1814             self.finished = ret.is_none();
1815             ret
1816         }
1817     }
1818
1819     #[inline]
1820     fn size_hint(&self) -> (usize, Option<usize>) {
1821         if self.finished {
1822             (0, Some(0))
1823         } else {
1824             let (_, upper) = self.iter.size_hint();
1825             (0, upper) // can't know a lower bound, due to the predicate
1826         }
1827     }
1828
1829     #[inline]
1830     fn try_fold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R
1831     where
1832         Self: Sized,
1833         Fold: FnMut(Acc, Self::Item) -> R,
1834         R: Try<Ok = Acc>,
1835     {
1836         fn check<'a, B, T, Acc, R: Try<Ok = Acc>>(
1837             flag: &'a mut bool,
1838             p: &'a mut impl FnMut(T) -> Option<B>,
1839             mut fold: impl FnMut(Acc, B) -> R + 'a,
1840         ) -> impl FnMut(Acc, T) -> LoopState<Acc, R> + 'a {
1841             move |acc, x| match p(x) {
1842                 Some(item) => LoopState::from_try(fold(acc, item)),
1843                 None => {
1844                     *flag = true;
1845                     LoopState::Break(Try::from_ok(acc))
1846                 }
1847             }
1848         }
1849
1850         if self.finished {
1851             Try::from_ok(init)
1852         } else {
1853             let flag = &mut self.finished;
1854             let p = &mut self.predicate;
1855             self.iter.try_fold(init, check(flag, p, fold)).into_try()
1856         }
1857     }
1858 }
1859
1860 #[stable(feature = "fused", since = "1.26.0")]
1861 impl<I, P> FusedIterator for TakeWhile<I, P>
1862 where
1863     I: FusedIterator,
1864     P: FnMut(&I::Item) -> bool,
1865 {
1866 }
1867
1868 /// An iterator that skips over `n` elements of `iter`.
1869 ///
1870 /// This `struct` is created by the [`skip`] method on [`Iterator`]. See its
1871 /// documentation for more.
1872 ///
1873 /// [`skip`]: trait.Iterator.html#method.skip
1874 /// [`Iterator`]: trait.Iterator.html
1875 #[derive(Clone, Debug)]
1876 #[must_use = "iterators are lazy and do nothing unless consumed"]
1877 #[stable(feature = "rust1", since = "1.0.0")]
1878 pub struct Skip<I> {
1879     iter: I,
1880     n: usize,
1881 }
1882 impl<I> Skip<I> {
1883     pub(super) fn new(iter: I, n: usize) -> Skip<I> {
1884         Skip { iter, n }
1885     }
1886 }
1887
1888 #[stable(feature = "rust1", since = "1.0.0")]
1889 impl<I> Iterator for Skip<I>
1890 where
1891     I: Iterator,
1892 {
1893     type Item = <I as Iterator>::Item;
1894
1895     #[inline]
1896     fn next(&mut self) -> Option<I::Item> {
1897         if self.n == 0 {
1898             self.iter.next()
1899         } else {
1900             let old_n = self.n;
1901             self.n = 0;
1902             self.iter.nth(old_n)
1903         }
1904     }
1905
1906     #[inline]
1907     fn nth(&mut self, n: usize) -> Option<I::Item> {
1908         // Can't just add n + self.n due to overflow.
1909         if self.n > 0 {
1910             let to_skip = self.n;
1911             self.n = 0;
1912             // nth(n) skips n+1
1913             self.iter.nth(to_skip - 1)?;
1914         }
1915         self.iter.nth(n)
1916     }
1917
1918     #[inline]
1919     fn count(mut self) -> usize {
1920         if self.n > 0 {
1921             // nth(n) skips n+1
1922             if self.iter.nth(self.n - 1).is_none() {
1923                 return 0;
1924             }
1925         }
1926         self.iter.count()
1927     }
1928
1929     #[inline]
1930     fn last(mut self) -> Option<I::Item> {
1931         if self.n > 0 {
1932             // nth(n) skips n+1
1933             self.iter.nth(self.n - 1)?;
1934         }
1935         self.iter.last()
1936     }
1937
1938     #[inline]
1939     fn size_hint(&self) -> (usize, Option<usize>) {
1940         let (lower, upper) = self.iter.size_hint();
1941
1942         let lower = lower.saturating_sub(self.n);
1943         let upper = match upper {
1944             Some(x) => Some(x.saturating_sub(self.n)),
1945             None => None,
1946         };
1947
1948         (lower, upper)
1949     }
1950
1951     #[inline]
1952     fn try_fold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R
1953     where
1954         Self: Sized,
1955         Fold: FnMut(Acc, Self::Item) -> R,
1956         R: Try<Ok = Acc>,
1957     {
1958         let n = self.n;
1959         self.n = 0;
1960         if n > 0 {
1961             // nth(n) skips n+1
1962             if self.iter.nth(n - 1).is_none() {
1963                 return Try::from_ok(init);
1964             }
1965         }
1966         self.iter.try_fold(init, fold)
1967     }
1968
1969     #[inline]
1970     fn fold<Acc, Fold>(mut self, init: Acc, fold: Fold) -> Acc
1971     where
1972         Fold: FnMut(Acc, Self::Item) -> Acc,
1973     {
1974         if self.n > 0 {
1975             // nth(n) skips n+1
1976             if self.iter.nth(self.n - 1).is_none() {
1977                 return init;
1978             }
1979         }
1980         self.iter.fold(init, fold)
1981     }
1982 }
1983
1984 #[stable(feature = "rust1", since = "1.0.0")]
1985 impl<I> ExactSizeIterator for Skip<I> where I: ExactSizeIterator {}
1986
1987 #[stable(feature = "double_ended_skip_iterator", since = "1.9.0")]
1988 impl<I> DoubleEndedIterator for Skip<I>
1989 where
1990     I: DoubleEndedIterator + ExactSizeIterator,
1991 {
1992     fn next_back(&mut self) -> Option<Self::Item> {
1993         if self.len() > 0 { self.iter.next_back() } else { None }
1994     }
1995
1996     #[inline]
1997     fn nth_back(&mut self, n: usize) -> Option<I::Item> {
1998         let len = self.len();
1999         if n < len {
2000             self.iter.nth_back(n)
2001         } else {
2002             if len > 0 {
2003                 // consume the original iterator
2004                 self.iter.nth_back(len - 1);
2005             }
2006             None
2007         }
2008     }
2009
2010     fn try_rfold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R
2011     where
2012         Self: Sized,
2013         Fold: FnMut(Acc, Self::Item) -> R,
2014         R: Try<Ok = Acc>,
2015     {
2016         fn check<T, Acc, R: Try<Ok = Acc>>(
2017             mut n: usize,
2018             mut fold: impl FnMut(Acc, T) -> R,
2019         ) -> impl FnMut(Acc, T) -> LoopState<Acc, R> {
2020             move |acc, x| {
2021                 n -= 1;
2022                 let r = fold(acc, x);
2023                 if n == 0 { LoopState::Break(r) } else { LoopState::from_try(r) }
2024             }
2025         }
2026
2027         let n = self.len();
2028         if n == 0 {
2029             Try::from_ok(init)
2030         } else {
2031             self.iter.try_rfold(init, check(n, fold)).into_try()
2032         }
2033     }
2034 }
2035
2036 #[stable(feature = "fused", since = "1.26.0")]
2037 impl<I> FusedIterator for Skip<I> where I: FusedIterator {}
2038
2039 /// An iterator that only iterates over the first `n` iterations of `iter`.
2040 ///
2041 /// This `struct` is created by the [`take`] method on [`Iterator`]. See its
2042 /// documentation for more.
2043 ///
2044 /// [`take`]: trait.Iterator.html#method.take
2045 /// [`Iterator`]: trait.Iterator.html
2046 #[derive(Clone, Debug)]
2047 #[must_use = "iterators are lazy and do nothing unless consumed"]
2048 #[stable(feature = "rust1", since = "1.0.0")]
2049 pub struct Take<I> {
2050     pub(super) iter: I,
2051     pub(super) n: usize,
2052 }
2053 impl<I> Take<I> {
2054     pub(super) fn new(iter: I, n: usize) -> Take<I> {
2055         Take { iter, n }
2056     }
2057 }
2058
2059 #[stable(feature = "rust1", since = "1.0.0")]
2060 impl<I> Iterator for Take<I>
2061 where
2062     I: Iterator,
2063 {
2064     type Item = <I as Iterator>::Item;
2065
2066     #[inline]
2067     fn next(&mut self) -> Option<<I as Iterator>::Item> {
2068         if self.n != 0 {
2069             self.n -= 1;
2070             self.iter.next()
2071         } else {
2072             None
2073         }
2074     }
2075
2076     #[inline]
2077     fn nth(&mut self, n: usize) -> Option<I::Item> {
2078         if self.n > n {
2079             self.n -= n + 1;
2080             self.iter.nth(n)
2081         } else {
2082             if self.n > 0 {
2083                 self.iter.nth(self.n - 1);
2084                 self.n = 0;
2085             }
2086             None
2087         }
2088     }
2089
2090     #[inline]
2091     fn size_hint(&self) -> (usize, Option<usize>) {
2092         if self.n == 0 {
2093             return (0, Some(0));
2094         }
2095
2096         let (lower, upper) = self.iter.size_hint();
2097
2098         let lower = cmp::min(lower, self.n);
2099
2100         let upper = match upper {
2101             Some(x) if x < self.n => Some(x),
2102             _ => Some(self.n),
2103         };
2104
2105         (lower, upper)
2106     }
2107
2108     #[inline]
2109     fn try_fold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R
2110     where
2111         Self: Sized,
2112         Fold: FnMut(Acc, Self::Item) -> R,
2113         R: Try<Ok = Acc>,
2114     {
2115         fn check<'a, T, Acc, R: Try<Ok = Acc>>(
2116             n: &'a mut usize,
2117             mut fold: impl FnMut(Acc, T) -> R + 'a,
2118         ) -> impl FnMut(Acc, T) -> LoopState<Acc, R> + 'a {
2119             move |acc, x| {
2120                 *n -= 1;
2121                 let r = fold(acc, x);
2122                 if *n == 0 { LoopState::Break(r) } else { LoopState::from_try(r) }
2123             }
2124         }
2125
2126         if self.n == 0 {
2127             Try::from_ok(init)
2128         } else {
2129             let n = &mut self.n;
2130             self.iter.try_fold(init, check(n, fold)).into_try()
2131         }
2132     }
2133 }
2134
2135 #[stable(feature = "double_ended_take_iterator", since = "1.38.0")]
2136 impl<I> DoubleEndedIterator for Take<I>
2137 where
2138     I: DoubleEndedIterator + ExactSizeIterator,
2139 {
2140     #[inline]
2141     fn next_back(&mut self) -> Option<Self::Item> {
2142         if self.n == 0 {
2143             None
2144         } else {
2145             let n = self.n;
2146             self.n -= 1;
2147             self.iter.nth_back(self.iter.len().saturating_sub(n))
2148         }
2149     }
2150
2151     #[inline]
2152     fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
2153         let len = self.iter.len();
2154         if self.n > n {
2155             let m = len.saturating_sub(self.n) + n;
2156             self.n -= n + 1;
2157             self.iter.nth_back(m)
2158         } else {
2159             if len > 0 {
2160                 self.iter.nth_back(len - 1);
2161             }
2162             None
2163         }
2164     }
2165
2166     #[inline]
2167     fn try_rfold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R
2168     where
2169         Self: Sized,
2170         Fold: FnMut(Acc, Self::Item) -> R,
2171         R: Try<Ok = Acc>,
2172     {
2173         if self.n == 0 {
2174             Try::from_ok(init)
2175         } else {
2176             let len = self.iter.len();
2177             if len > self.n && self.iter.nth_back(len - self.n - 1).is_none() {
2178                 Try::from_ok(init)
2179             } else {
2180                 self.iter.try_rfold(init, fold)
2181             }
2182         }
2183     }
2184 }
2185
2186 #[stable(feature = "rust1", since = "1.0.0")]
2187 impl<I> ExactSizeIterator for Take<I> where I: ExactSizeIterator {}
2188
2189 #[stable(feature = "fused", since = "1.26.0")]
2190 impl<I> FusedIterator for Take<I> where I: FusedIterator {}
2191
2192 #[unstable(feature = "trusted_len", issue = "37572")]
2193 unsafe impl<I: TrustedLen> TrustedLen for Take<I> {}
2194
2195 /// An iterator to maintain state while iterating another iterator.
2196 ///
2197 /// This `struct` is created by the [`scan`] method on [`Iterator`]. See its
2198 /// documentation for more.
2199 ///
2200 /// [`scan`]: trait.Iterator.html#method.scan
2201 /// [`Iterator`]: trait.Iterator.html
2202 #[must_use = "iterators are lazy and do nothing unless consumed"]
2203 #[stable(feature = "rust1", since = "1.0.0")]
2204 #[derive(Clone)]
2205 pub struct Scan<I, St, F> {
2206     iter: I,
2207     f: F,
2208     state: St,
2209 }
2210 impl<I, St, F> Scan<I, St, F> {
2211     pub(super) fn new(iter: I, state: St, f: F) -> Scan<I, St, F> {
2212         Scan { iter, state, f }
2213     }
2214 }
2215
2216 #[stable(feature = "core_impl_debug", since = "1.9.0")]
2217 impl<I: fmt::Debug, St: fmt::Debug, F> fmt::Debug for Scan<I, St, F> {
2218     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2219         f.debug_struct("Scan").field("iter", &self.iter).field("state", &self.state).finish()
2220     }
2221 }
2222
2223 #[stable(feature = "rust1", since = "1.0.0")]
2224 impl<B, I, St, F> Iterator for Scan<I, St, F>
2225 where
2226     I: Iterator,
2227     F: FnMut(&mut St, I::Item) -> Option<B>,
2228 {
2229     type Item = B;
2230
2231     #[inline]
2232     fn next(&mut self) -> Option<B> {
2233         let a = self.iter.next()?;
2234         (self.f)(&mut self.state, a)
2235     }
2236
2237     #[inline]
2238     fn size_hint(&self) -> (usize, Option<usize>) {
2239         let (_, upper) = self.iter.size_hint();
2240         (0, upper) // can't know a lower bound, due to the scan function
2241     }
2242
2243     #[inline]
2244     fn try_fold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R
2245     where
2246         Self: Sized,
2247         Fold: FnMut(Acc, Self::Item) -> R,
2248         R: Try<Ok = Acc>,
2249     {
2250         fn scan<'a, T, St, B, Acc, R: Try<Ok = Acc>>(
2251             state: &'a mut St,
2252             f: &'a mut impl FnMut(&mut St, T) -> Option<B>,
2253             mut fold: impl FnMut(Acc, B) -> R + 'a,
2254         ) -> impl FnMut(Acc, T) -> LoopState<Acc, R> + 'a {
2255             move |acc, x| match f(state, x) {
2256                 None => LoopState::Break(Try::from_ok(acc)),
2257                 Some(x) => LoopState::from_try(fold(acc, x)),
2258             }
2259         }
2260
2261         let state = &mut self.state;
2262         let f = &mut self.f;
2263         self.iter.try_fold(init, scan(state, f, fold)).into_try()
2264     }
2265 }
2266
2267 /// An iterator that yields `None` forever after the underlying iterator
2268 /// yields `None` once.
2269 ///
2270 /// This `struct` is created by the [`fuse`] method on [`Iterator`]. See its
2271 /// documentation for more.
2272 ///
2273 /// [`fuse`]: trait.Iterator.html#method.fuse
2274 /// [`Iterator`]: trait.Iterator.html
2275 #[derive(Clone, Debug)]
2276 #[must_use = "iterators are lazy and do nothing unless consumed"]
2277 #[stable(feature = "rust1", since = "1.0.0")]
2278 pub struct Fuse<I> {
2279     iter: I,
2280     done: bool,
2281 }
2282 impl<I> Fuse<I> {
2283     pub(super) fn new(iter: I) -> Fuse<I> {
2284         Fuse { iter, done: false }
2285     }
2286 }
2287
2288 #[stable(feature = "fused", since = "1.26.0")]
2289 impl<I> FusedIterator for Fuse<I> where I: Iterator {}
2290
2291 #[stable(feature = "rust1", since = "1.0.0")]
2292 impl<I> Iterator for Fuse<I>
2293 where
2294     I: Iterator,
2295 {
2296     type Item = <I as Iterator>::Item;
2297
2298     #[inline]
2299     default fn next(&mut self) -> Option<<I as Iterator>::Item> {
2300         if self.done {
2301             None
2302         } else {
2303             let next = self.iter.next();
2304             self.done = next.is_none();
2305             next
2306         }
2307     }
2308
2309     #[inline]
2310     default fn nth(&mut self, n: usize) -> Option<I::Item> {
2311         if self.done {
2312             None
2313         } else {
2314             let nth = self.iter.nth(n);
2315             self.done = nth.is_none();
2316             nth
2317         }
2318     }
2319
2320     #[inline]
2321     default fn last(self) -> Option<I::Item> {
2322         if self.done { None } else { self.iter.last() }
2323     }
2324
2325     #[inline]
2326     default fn count(self) -> usize {
2327         if self.done { 0 } else { self.iter.count() }
2328     }
2329
2330     #[inline]
2331     default fn size_hint(&self) -> (usize, Option<usize>) {
2332         if self.done { (0, Some(0)) } else { self.iter.size_hint() }
2333     }
2334
2335     #[inline]
2336     default fn try_fold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R
2337     where
2338         Self: Sized,
2339         Fold: FnMut(Acc, Self::Item) -> R,
2340         R: Try<Ok = Acc>,
2341     {
2342         if self.done {
2343             Try::from_ok(init)
2344         } else {
2345             let acc = self.iter.try_fold(init, fold)?;
2346             self.done = true;
2347             Try::from_ok(acc)
2348         }
2349     }
2350
2351     #[inline]
2352     default fn fold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
2353     where
2354         Fold: FnMut(Acc, Self::Item) -> Acc,
2355     {
2356         if self.done { init } else { self.iter.fold(init, fold) }
2357     }
2358 }
2359
2360 #[stable(feature = "rust1", since = "1.0.0")]
2361 impl<I> DoubleEndedIterator for Fuse<I>
2362 where
2363     I: DoubleEndedIterator,
2364 {
2365     #[inline]
2366     default fn next_back(&mut self) -> Option<<I as Iterator>::Item> {
2367         if self.done {
2368             None
2369         } else {
2370             let next = self.iter.next_back();
2371             self.done = next.is_none();
2372             next
2373         }
2374     }
2375
2376     #[inline]
2377     default fn nth_back(&mut self, n: usize) -> Option<<I as Iterator>::Item> {
2378         if self.done {
2379             None
2380         } else {
2381             let nth = self.iter.nth_back(n);
2382             self.done = nth.is_none();
2383             nth
2384         }
2385     }
2386
2387     #[inline]
2388     default fn try_rfold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R
2389     where
2390         Self: Sized,
2391         Fold: FnMut(Acc, Self::Item) -> R,
2392         R: Try<Ok = Acc>,
2393     {
2394         if self.done {
2395             Try::from_ok(init)
2396         } else {
2397             let acc = self.iter.try_rfold(init, fold)?;
2398             self.done = true;
2399             Try::from_ok(acc)
2400         }
2401     }
2402
2403     #[inline]
2404     default fn rfold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
2405     where
2406         Fold: FnMut(Acc, Self::Item) -> Acc,
2407     {
2408         if self.done { init } else { self.iter.rfold(init, fold) }
2409     }
2410 }
2411
2412 unsafe impl<I> TrustedRandomAccess for Fuse<I>
2413 where
2414     I: TrustedRandomAccess,
2415 {
2416     unsafe fn get_unchecked(&mut self, i: usize) -> I::Item {
2417         self.iter.get_unchecked(i)
2418     }
2419
2420     fn may_have_side_effect() -> bool {
2421         I::may_have_side_effect()
2422     }
2423 }
2424
2425 #[stable(feature = "fused", since = "1.26.0")]
2426 impl<I> Iterator for Fuse<I>
2427 where
2428     I: FusedIterator,
2429 {
2430     #[inline]
2431     fn next(&mut self) -> Option<<I as Iterator>::Item> {
2432         self.iter.next()
2433     }
2434
2435     #[inline]
2436     fn nth(&mut self, n: usize) -> Option<I::Item> {
2437         self.iter.nth(n)
2438     }
2439
2440     #[inline]
2441     fn last(self) -> Option<I::Item> {
2442         self.iter.last()
2443     }
2444
2445     #[inline]
2446     fn count(self) -> usize {
2447         self.iter.count()
2448     }
2449
2450     #[inline]
2451     fn size_hint(&self) -> (usize, Option<usize>) {
2452         self.iter.size_hint()
2453     }
2454
2455     #[inline]
2456     fn try_fold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R
2457     where
2458         Self: Sized,
2459         Fold: FnMut(Acc, Self::Item) -> R,
2460         R: Try<Ok = Acc>,
2461     {
2462         self.iter.try_fold(init, fold)
2463     }
2464
2465     #[inline]
2466     fn fold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
2467     where
2468         Fold: FnMut(Acc, Self::Item) -> Acc,
2469     {
2470         self.iter.fold(init, fold)
2471     }
2472 }
2473
2474 #[stable(feature = "fused", since = "1.26.0")]
2475 impl<I> DoubleEndedIterator for Fuse<I>
2476 where
2477     I: DoubleEndedIterator + FusedIterator,
2478 {
2479     #[inline]
2480     fn next_back(&mut self) -> Option<<I as Iterator>::Item> {
2481         self.iter.next_back()
2482     }
2483
2484     #[inline]
2485     fn nth_back(&mut self, n: usize) -> Option<<I as Iterator>::Item> {
2486         self.iter.nth_back(n)
2487     }
2488
2489     #[inline]
2490     fn try_rfold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R
2491     where
2492         Self: Sized,
2493         Fold: FnMut(Acc, Self::Item) -> R,
2494         R: Try<Ok = Acc>,
2495     {
2496         self.iter.try_rfold(init, fold)
2497     }
2498
2499     #[inline]
2500     fn rfold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
2501     where
2502         Fold: FnMut(Acc, Self::Item) -> Acc,
2503     {
2504         self.iter.rfold(init, fold)
2505     }
2506 }
2507
2508 #[stable(feature = "rust1", since = "1.0.0")]
2509 impl<I> ExactSizeIterator for Fuse<I>
2510 where
2511     I: ExactSizeIterator,
2512 {
2513     fn len(&self) -> usize {
2514         self.iter.len()
2515     }
2516
2517     fn is_empty(&self) -> bool {
2518         self.iter.is_empty()
2519     }
2520 }
2521
2522 /// An iterator that calls a function with a reference to each element before
2523 /// yielding it.
2524 ///
2525 /// This `struct` is created by the [`inspect`] method on [`Iterator`]. See its
2526 /// documentation for more.
2527 ///
2528 /// [`inspect`]: trait.Iterator.html#method.inspect
2529 /// [`Iterator`]: trait.Iterator.html
2530 #[must_use = "iterators are lazy and do nothing unless consumed"]
2531 #[stable(feature = "rust1", since = "1.0.0")]
2532 #[derive(Clone)]
2533 pub struct Inspect<I, F> {
2534     iter: I,
2535     f: F,
2536 }
2537 impl<I, F> Inspect<I, F> {
2538     pub(super) fn new(iter: I, f: F) -> Inspect<I, F> {
2539         Inspect { iter, f }
2540     }
2541 }
2542
2543 #[stable(feature = "core_impl_debug", since = "1.9.0")]
2544 impl<I: fmt::Debug, F> fmt::Debug for Inspect<I, F> {
2545     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2546         f.debug_struct("Inspect").field("iter", &self.iter).finish()
2547     }
2548 }
2549
2550 impl<I: Iterator, F> Inspect<I, F>
2551 where
2552     F: FnMut(&I::Item),
2553 {
2554     #[inline]
2555     fn do_inspect(&mut self, elt: Option<I::Item>) -> Option<I::Item> {
2556         if let Some(ref a) = elt {
2557             (self.f)(a);
2558         }
2559
2560         elt
2561     }
2562 }
2563
2564 fn inspect_fold<T, Acc>(
2565     mut f: impl FnMut(&T),
2566     mut fold: impl FnMut(Acc, T) -> Acc,
2567 ) -> impl FnMut(Acc, T) -> Acc {
2568     move |acc, item| {
2569         f(&item);
2570         fold(acc, item)
2571     }
2572 }
2573
2574 fn inspect_try_fold<'a, T, Acc, R>(
2575     f: &'a mut impl FnMut(&T),
2576     mut fold: impl FnMut(Acc, T) -> R + 'a,
2577 ) -> impl FnMut(Acc, T) -> R + 'a {
2578     move |acc, item| {
2579         f(&item);
2580         fold(acc, item)
2581     }
2582 }
2583
2584 #[stable(feature = "rust1", since = "1.0.0")]
2585 impl<I: Iterator, F> Iterator for Inspect<I, F>
2586 where
2587     F: FnMut(&I::Item),
2588 {
2589     type Item = I::Item;
2590
2591     #[inline]
2592     fn next(&mut self) -> Option<I::Item> {
2593         let next = self.iter.next();
2594         self.do_inspect(next)
2595     }
2596
2597     #[inline]
2598     fn size_hint(&self) -> (usize, Option<usize>) {
2599         self.iter.size_hint()
2600     }
2601
2602     #[inline]
2603     fn try_fold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R
2604     where
2605         Self: Sized,
2606         Fold: FnMut(Acc, Self::Item) -> R,
2607         R: Try<Ok = Acc>,
2608     {
2609         self.iter.try_fold(init, inspect_try_fold(&mut self.f, fold))
2610     }
2611
2612     #[inline]
2613     fn fold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
2614     where
2615         Fold: FnMut(Acc, Self::Item) -> Acc,
2616     {
2617         self.iter.fold(init, inspect_fold(self.f, fold))
2618     }
2619 }
2620
2621 #[stable(feature = "rust1", since = "1.0.0")]
2622 impl<I: DoubleEndedIterator, F> DoubleEndedIterator for Inspect<I, F>
2623 where
2624     F: FnMut(&I::Item),
2625 {
2626     #[inline]
2627     fn next_back(&mut self) -> Option<I::Item> {
2628         let next = self.iter.next_back();
2629         self.do_inspect(next)
2630     }
2631
2632     #[inline]
2633     fn try_rfold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R
2634     where
2635         Self: Sized,
2636         Fold: FnMut(Acc, Self::Item) -> R,
2637         R: Try<Ok = Acc>,
2638     {
2639         self.iter.try_rfold(init, inspect_try_fold(&mut self.f, fold))
2640     }
2641
2642     #[inline]
2643     fn rfold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
2644     where
2645         Fold: FnMut(Acc, Self::Item) -> Acc,
2646     {
2647         self.iter.rfold(init, inspect_fold(self.f, fold))
2648     }
2649 }
2650
2651 #[stable(feature = "rust1", since = "1.0.0")]
2652 impl<I: ExactSizeIterator, F> ExactSizeIterator for Inspect<I, F>
2653 where
2654     F: FnMut(&I::Item),
2655 {
2656     fn len(&self) -> usize {
2657         self.iter.len()
2658     }
2659
2660     fn is_empty(&self) -> bool {
2661         self.iter.is_empty()
2662     }
2663 }
2664
2665 #[stable(feature = "fused", since = "1.26.0")]
2666 impl<I: FusedIterator, F> FusedIterator for Inspect<I, F> where F: FnMut(&I::Item) {}
2667
2668 /// An iterator adapter that produces output as long as the underlying
2669 /// iterator produces `Result::Ok` values.
2670 ///
2671 /// If an error is encountered, the iterator stops and the error is
2672 /// stored.
2673 pub(crate) struct ResultShunt<'a, I, E> {
2674     iter: I,
2675     error: &'a mut Result<(), E>,
2676 }
2677
2678 /// Process the given iterator as if it yielded a `T` instead of a
2679 /// `Result<T, _>`. Any errors will stop the inner iterator and
2680 /// the overall result will be an error.
2681 pub(crate) fn process_results<I, T, E, F, U>(iter: I, mut f: F) -> Result<U, E>
2682 where
2683     I: Iterator<Item = Result<T, E>>,
2684     for<'a> F: FnMut(ResultShunt<'a, I, E>) -> U,
2685 {
2686     let mut error = Ok(());
2687     let shunt = ResultShunt { iter, error: &mut error };
2688     let value = f(shunt);
2689     error.map(|()| value)
2690 }
2691
2692 impl<I, T, E> Iterator for ResultShunt<'_, I, E>
2693 where
2694     I: Iterator<Item = Result<T, E>>,
2695 {
2696     type Item = T;
2697
2698     fn next(&mut self) -> Option<Self::Item> {
2699         self.find(|_| true)
2700     }
2701
2702     fn size_hint(&self) -> (usize, Option<usize>) {
2703         if self.error.is_err() {
2704             (0, Some(0))
2705         } else {
2706             let (_, upper) = self.iter.size_hint();
2707             (0, upper)
2708         }
2709     }
2710
2711     fn try_fold<B, F, R>(&mut self, init: B, mut f: F) -> R
2712     where
2713         F: FnMut(B, Self::Item) -> R,
2714         R: Try<Ok = B>,
2715     {
2716         let error = &mut *self.error;
2717         self.iter
2718             .try_fold(init, |acc, x| match x {
2719                 Ok(x) => LoopState::from_try(f(acc, x)),
2720                 Err(e) => {
2721                     *error = Err(e);
2722                     LoopState::Break(Try::from_ok(acc))
2723                 }
2724             })
2725             .into_try()
2726     }
2727 }