#![stable(feature = "rust1", since = "1.0.0")]
-use cmp;
-use fmt;
-use iter_private::TrustedRandomAccess;
use ops::Try;
-use usize;
-use intrinsics;
#[stable(feature = "rust1", since = "1.0.0")]
-pub use self::iterator::Iterator;
+pub use self::traits::Iterator;
#[unstable(feature = "step_trait",
reason = "likely to be replaced by finer-grained traits",
pub use self::sources::{Once, once};
#[unstable(feature = "iter_once_with", issue = "57581")]
pub use self::sources::{OnceWith, once_with};
-#[unstable(feature = "iter_unfold", issue = "55977")]
-pub use self::sources::{Unfold, unfold, Successors, successors};
+#[stable(feature = "iter_from_fn", since = "1.34.0")]
+pub use self::sources::{FromFn, from_fn};
+#[stable(feature = "iter_successors", since = "1.34.0")]
+pub use self::sources::{Successors, successors};
#[stable(feature = "rust1", since = "1.0.0")]
pub use self::traits::{FromIterator, IntoIterator, DoubleEndedIterator, Extend};
#[unstable(feature = "trusted_len", issue = "37572")]
pub use self::traits::TrustedLen;
-mod iterator;
+#[stable(feature = "rust1", since = "1.0.0")]
+pub use self::adapters::{Rev, Cycle, Chain, Zip, Map, Filter, FilterMap, Enumerate};
+#[stable(feature = "rust1", since = "1.0.0")]
+pub use self::adapters::{Peekable, SkipWhile, TakeWhile, Skip, Take, Scan, FlatMap};
+#[stable(feature = "rust1", since = "1.0.0")]
+pub use self::adapters::{Fuse, Inspect};
+#[stable(feature = "iter_cloned", since = "1.1.0")]
+pub use self::adapters::Cloned;
+#[stable(feature = "iterator_step_by", since = "1.28.0")]
+pub use self::adapters::StepBy;
+#[stable(feature = "iterator_flatten", since = "1.29.0")]
+pub use self::adapters::Flatten;
+#[unstable(feature = "iter_copied", issue = "57127")]
+pub use self::adapters::Copied;
+
+pub(crate) use self::adapters::TrustedRandomAccess;
+
mod range;
mod sources;
mod traits;
+mod adapters;
/// Used to make try_fold closures more like normal loops
#[derive(PartialEq)]
}
}
}
-
-/// A double-ended iterator with the direction inverted.
-///
-/// This `struct` is created by the [`rev`] method on [`Iterator`]. See its
-/// documentation for more.
-///
-/// [`rev`]: trait.Iterator.html#method.rev
-/// [`Iterator`]: trait.Iterator.html
-#[derive(Clone, Debug)]
-#[must_use = "iterators are lazy and do nothing unless consumed"]
-#[stable(feature = "rust1", since = "1.0.0")]
-pub struct Rev<T> {
- iter: T
-}
-
-#[stable(feature = "rust1", since = "1.0.0")]
-impl<I> Iterator for Rev<I> where I: DoubleEndedIterator {
- type Item = <I as Iterator>::Item;
-
- #[inline]
- fn next(&mut self) -> Option<<I as Iterator>::Item> { self.iter.next_back() }
- #[inline]
- fn size_hint(&self) -> (usize, Option<usize>) { self.iter.size_hint() }
-
- #[inline]
- fn nth(&mut self, n: usize) -> Option<<I as Iterator>::Item> { self.iter.nth_back(n) }
-
- fn try_fold<B, F, R>(&mut self, init: B, f: F) -> R where
- Self: Sized, F: FnMut(B, Self::Item) -> R, R: Try<Ok=B>
- {
- self.iter.try_rfold(init, f)
- }
-
- fn fold<Acc, F>(self, init: Acc, f: F) -> Acc
- where F: FnMut(Acc, Self::Item) -> Acc,
- {
- self.iter.rfold(init, f)
- }
-
- #[inline]
- fn find<P>(&mut self, predicate: P) -> Option<Self::Item>
- where P: FnMut(&Self::Item) -> bool
- {
- self.iter.rfind(predicate)
- }
-
- #[inline]
- fn rposition<P>(&mut self, predicate: P) -> Option<usize> where
- P: FnMut(Self::Item) -> bool
- {
- self.iter.position(predicate)
- }
-}
-
-#[stable(feature = "rust1", since = "1.0.0")]
-impl<I> DoubleEndedIterator for Rev<I> where I: DoubleEndedIterator {
- #[inline]
- fn next_back(&mut self) -> Option<<I as Iterator>::Item> { self.iter.next() }
-
- #[inline]
- fn nth_back(&mut self, n: usize) -> Option<<I as Iterator>::Item> { self.iter.nth(n) }
-
- fn try_rfold<B, F, R>(&mut self, init: B, f: F) -> R where
- Self: Sized, F: FnMut(B, Self::Item) -> R, R: Try<Ok=B>
- {
- self.iter.try_fold(init, f)
- }
-
- fn rfold<Acc, F>(self, init: Acc, f: F) -> Acc
- where F: FnMut(Acc, Self::Item) -> Acc,
- {
- self.iter.fold(init, f)
- }
-
- fn rfind<P>(&mut self, predicate: P) -> Option<Self::Item>
- where P: FnMut(&Self::Item) -> bool
- {
- self.iter.find(predicate)
- }
-}
-
-#[stable(feature = "rust1", since = "1.0.0")]
-impl<I> ExactSizeIterator for Rev<I>
- where I: ExactSizeIterator + DoubleEndedIterator
-{
- fn len(&self) -> usize {
- self.iter.len()
- }
-
- fn is_empty(&self) -> bool {
- self.iter.is_empty()
- }
-}
-
-#[stable(feature = "fused", since = "1.26.0")]
-impl<I> FusedIterator for Rev<I>
- where I: FusedIterator + DoubleEndedIterator {}
-
-#[unstable(feature = "trusted_len", issue = "37572")]
-unsafe impl<I> TrustedLen for Rev<I>
- where I: TrustedLen + DoubleEndedIterator {}
-
-/// An iterator that copies the elements of an underlying iterator.
-///
-/// This `struct` is created by the [`copied`] method on [`Iterator`]. See its
-/// documentation for more.
-///
-/// [`copied`]: trait.Iterator.html#method.copied
-/// [`Iterator`]: trait.Iterator.html
-#[unstable(feature = "iter_copied", issue = "57127")]
-#[must_use = "iterators are lazy and do nothing unless consumed"]
-#[derive(Clone, Debug)]
-pub struct Copied<I> {
- it: I,
-}
-
-#[unstable(feature = "iter_copied", issue = "57127")]
-impl<'a, I, T: 'a> Iterator for Copied<I>
- where I: Iterator<Item=&'a T>, T: Copy
-{
- type Item = T;
-
- fn next(&mut self) -> Option<T> {
- self.it.next().copied()
- }
-
- fn size_hint(&self) -> (usize, Option<usize>) {
- self.it.size_hint()
- }
-
- fn try_fold<B, F, R>(&mut self, init: B, mut f: F) -> R where
- Self: Sized, F: FnMut(B, Self::Item) -> R, R: Try<Ok=B>
- {
- self.it.try_fold(init, move |acc, &elt| f(acc, elt))
- }
-
- fn fold<Acc, F>(self, init: Acc, mut f: F) -> Acc
- where F: FnMut(Acc, Self::Item) -> Acc,
- {
- self.it.fold(init, move |acc, &elt| f(acc, elt))
- }
-}
-
-#[unstable(feature = "iter_copied", issue = "57127")]
-impl<'a, I, T: 'a> DoubleEndedIterator for Copied<I>
- where I: DoubleEndedIterator<Item=&'a T>, T: Copy
-{
- fn next_back(&mut self) -> Option<T> {
- self.it.next_back().copied()
- }
-
- fn try_rfold<B, F, R>(&mut self, init: B, mut f: F) -> R where
- Self: Sized, F: FnMut(B, Self::Item) -> R, R: Try<Ok=B>
- {
- self.it.try_rfold(init, move |acc, &elt| f(acc, elt))
- }
-
- fn rfold<Acc, F>(self, init: Acc, mut f: F) -> Acc
- where F: FnMut(Acc, Self::Item) -> Acc,
- {
- self.it.rfold(init, move |acc, &elt| f(acc, elt))
- }
-}
-
-#[unstable(feature = "iter_copied", issue = "57127")]
-impl<'a, I, T: 'a> ExactSizeIterator for Copied<I>
- where I: ExactSizeIterator<Item=&'a T>, T: Copy
-{
- fn len(&self) -> usize {
- self.it.len()
- }
-
- fn is_empty(&self) -> bool {
- self.it.is_empty()
- }
-}
-
-#[unstable(feature = "iter_copied", issue = "57127")]
-impl<'a, I, T: 'a> FusedIterator for Copied<I>
- where I: FusedIterator<Item=&'a T>, T: Copy
-{}
-
-#[doc(hidden)]
-unsafe impl<'a, I, T: 'a> TrustedRandomAccess for Copied<I>
- where I: TrustedRandomAccess<Item=&'a T>, T: Copy
-{
- unsafe fn get_unchecked(&mut self, i: usize) -> Self::Item {
- *self.it.get_unchecked(i)
- }
-
- #[inline]
- fn may_have_side_effect() -> bool {
- I::may_have_side_effect()
- }
-}
-
-#[unstable(feature = "iter_copied", issue = "57127")]
-unsafe impl<'a, I, T: 'a> TrustedLen for Copied<I>
- where I: TrustedLen<Item=&'a T>,
- T: Copy
-{}
-
-/// An iterator that clones the elements of an underlying iterator.
-///
-/// This `struct` is created by the [`cloned`] method on [`Iterator`]. See its
-/// documentation for more.
-///
-/// [`cloned`]: trait.Iterator.html#method.cloned
-/// [`Iterator`]: trait.Iterator.html
-#[stable(feature = "iter_cloned", since = "1.1.0")]
-#[must_use = "iterators are lazy and do nothing unless consumed"]
-#[derive(Clone, Debug)]
-pub struct Cloned<I> {
- it: I,
-}
-
-#[stable(feature = "iter_cloned", since = "1.1.0")]
-impl<'a, I, T: 'a> Iterator for Cloned<I>
- where I: Iterator<Item=&'a T>, T: Clone
-{
- type Item = T;
-
- fn next(&mut self) -> Option<T> {
- self.it.next().cloned()
- }
-
- fn size_hint(&self) -> (usize, Option<usize>) {
- self.it.size_hint()
- }
-
- fn try_fold<B, F, R>(&mut self, init: B, mut f: F) -> R where
- Self: Sized, F: FnMut(B, Self::Item) -> R, R: Try<Ok=B>
- {
- self.it.try_fold(init, move |acc, elt| f(acc, elt.clone()))
- }
-
- fn fold<Acc, F>(self, init: Acc, mut f: F) -> Acc
- where F: FnMut(Acc, Self::Item) -> Acc,
- {
- self.it.fold(init, move |acc, elt| f(acc, elt.clone()))
- }
-}
-
-#[stable(feature = "iter_cloned", since = "1.1.0")]
-impl<'a, I, T: 'a> DoubleEndedIterator for Cloned<I>
- where I: DoubleEndedIterator<Item=&'a T>, T: Clone
-{
- fn next_back(&mut self) -> Option<T> {
- self.it.next_back().cloned()
- }
-
- fn try_rfold<B, F, R>(&mut self, init: B, mut f: F) -> R where
- Self: Sized, F: FnMut(B, Self::Item) -> R, R: Try<Ok=B>
- {
- self.it.try_rfold(init, move |acc, elt| f(acc, elt.clone()))
- }
-
- fn rfold<Acc, F>(self, init: Acc, mut f: F) -> Acc
- where F: FnMut(Acc, Self::Item) -> Acc,
- {
- self.it.rfold(init, move |acc, elt| f(acc, elt.clone()))
- }
-}
-
-#[stable(feature = "iter_cloned", since = "1.1.0")]
-impl<'a, I, T: 'a> ExactSizeIterator for Cloned<I>
- where I: ExactSizeIterator<Item=&'a T>, T: Clone
-{
- fn len(&self) -> usize {
- self.it.len()
- }
-
- fn is_empty(&self) -> bool {
- self.it.is_empty()
- }
-}
-
-#[stable(feature = "fused", since = "1.26.0")]
-impl<'a, I, T: 'a> FusedIterator for Cloned<I>
- where I: FusedIterator<Item=&'a T>, T: Clone
-{}
-
-#[doc(hidden)]
-unsafe impl<'a, I, T: 'a> TrustedRandomAccess for Cloned<I>
- where I: TrustedRandomAccess<Item=&'a T>, T: Clone
-{
- default unsafe fn get_unchecked(&mut self, i: usize) -> Self::Item {
- self.it.get_unchecked(i).clone()
- }
-
- #[inline]
- default fn may_have_side_effect() -> bool { true }
-}
-
-#[doc(hidden)]
-unsafe impl<'a, I, T: 'a> TrustedRandomAccess for Cloned<I>
- where I: TrustedRandomAccess<Item=&'a T>, T: Copy
-{
- unsafe fn get_unchecked(&mut self, i: usize) -> Self::Item {
- *self.it.get_unchecked(i)
- }
-
- #[inline]
- fn may_have_side_effect() -> bool {
- I::may_have_side_effect()
- }
-}
-
-#[unstable(feature = "trusted_len", issue = "37572")]
-unsafe impl<'a, I, T: 'a> TrustedLen for Cloned<I>
- where I: TrustedLen<Item=&'a T>,
- T: Clone
-{}
-
-/// An iterator that repeats endlessly.
-///
-/// This `struct` is created by the [`cycle`] method on [`Iterator`]. See its
-/// documentation for more.
-///
-/// [`cycle`]: trait.Iterator.html#method.cycle
-/// [`Iterator`]: trait.Iterator.html
-#[derive(Clone, Debug)]
-#[must_use = "iterators are lazy and do nothing unless consumed"]
-#[stable(feature = "rust1", since = "1.0.0")]
-pub struct Cycle<I> {
- orig: I,
- iter: I,
-}
-
-#[stable(feature = "rust1", since = "1.0.0")]
-impl<I> Iterator for Cycle<I> where I: Clone + Iterator {
- type Item = <I as Iterator>::Item;
-
- #[inline]
- fn next(&mut self) -> Option<<I as Iterator>::Item> {
- match self.iter.next() {
- None => { self.iter = self.orig.clone(); self.iter.next() }
- y => y
- }
- }
-
- #[inline]
- fn size_hint(&self) -> (usize, Option<usize>) {
- // the cycle iterator is either empty or infinite
- match self.orig.size_hint() {
- sz @ (0, Some(0)) => sz,
- (0, _) => (0, None),
- _ => (usize::MAX, None)
- }
- }
-}
-
-#[stable(feature = "fused", since = "1.26.0")]
-impl<I> FusedIterator for Cycle<I> where I: Clone + Iterator {}
-
-/// An iterator for stepping iterators by a custom amount.
-///
-/// This `struct` is created by the [`step_by`] method on [`Iterator`]. See
-/// its documentation for more.
-///
-/// [`step_by`]: trait.Iterator.html#method.step_by
-/// [`Iterator`]: trait.Iterator.html
-#[must_use = "iterators are lazy and do nothing unless consumed"]
-#[stable(feature = "iterator_step_by", since = "1.28.0")]
-#[derive(Clone, Debug)]
-pub struct StepBy<I> {
- iter: I,
- step: usize,
- first_take: bool,
-}
-
-#[stable(feature = "iterator_step_by", since = "1.28.0")]
-impl<I> Iterator for StepBy<I> where I: Iterator {
- type Item = I::Item;
-
- #[inline]
- fn next(&mut self) -> Option<Self::Item> {
- if self.first_take {
- self.first_take = false;
- self.iter.next()
- } else {
- self.iter.nth(self.step)
- }
- }
-
- #[inline]
- fn size_hint(&self) -> (usize, Option<usize>) {
- let inner_hint = self.iter.size_hint();
-
- if self.first_take {
- let f = |n| if n == 0 { 0 } else { 1 + (n-1)/(self.step+1) };
- (f(inner_hint.0), inner_hint.1.map(f))
- } else {
- let f = |n| n / (self.step+1);
- (f(inner_hint.0), inner_hint.1.map(f))
- }
- }
-
- #[inline]
- fn nth(&mut self, mut n: usize) -> Option<Self::Item> {
- if self.first_take {
- self.first_take = false;
- let first = self.iter.next();
- if n == 0 {
- return first;
- }
- n -= 1;
- }
- // n and self.step are indices, we need to add 1 to get the amount of elements
- // When calling `.nth`, we need to subtract 1 again to convert back to an index
- // step + 1 can't overflow because `.step_by` sets `self.step` to `step - 1`
- let mut step = self.step + 1;
- // n + 1 could overflow
- // thus, if n is usize::MAX, instead of adding one, we call .nth(step)
- if n == usize::MAX {
- self.iter.nth(step - 1);
- } else {
- n += 1;
- }
-
- // overflow handling
- loop {
- let mul = n.checked_mul(step);
- if unsafe { intrinsics::likely(mul.is_some()) } {
- return self.iter.nth(mul.unwrap() - 1);
- }
- let div_n = usize::MAX / n;
- let div_step = usize::MAX / step;
- let nth_n = div_n * n;
- let nth_step = div_step * step;
- let nth = if nth_n > nth_step {
- step -= div_n;
- nth_n
- } else {
- n -= div_step;
- nth_step
- };
- self.iter.nth(nth - 1);
- }
- }
-}
-
-// StepBy can only make the iterator shorter, so the len will still fit.
-#[stable(feature = "iterator_step_by", since = "1.28.0")]
-impl<I> ExactSizeIterator for StepBy<I> where I: ExactSizeIterator {}
-
-/// An iterator that strings two iterators together.
-///
-/// This `struct` is created by the [`chain`] method on [`Iterator`]. See its
-/// documentation for more.
-///
-/// [`chain`]: trait.Iterator.html#method.chain
-/// [`Iterator`]: trait.Iterator.html
-#[derive(Clone, Debug)]
-#[must_use = "iterators are lazy and do nothing unless consumed"]
-#[stable(feature = "rust1", since = "1.0.0")]
-pub struct Chain<A, B> {
- a: A,
- b: B,
- state: ChainState,
-}
-
-// The iterator protocol specifies that iteration ends with the return value
-// `None` from `.next()` (or `.next_back()`) and it is unspecified what
-// further calls return. The chain adaptor must account for this since it uses
-// two subiterators.
-//
-// It uses three states:
-//
-// - Both: `a` and `b` are remaining
-// - Front: `a` remaining
-// - Back: `b` remaining
-//
-// The fourth state (neither iterator is remaining) only occurs after Chain has
-// returned None once, so we don't need to store this state.
-#[derive(Clone, Debug)]
-enum ChainState {
- // both front and back iterator are remaining
- Both,
- // only front is remaining
- Front,
- // only back is remaining
- Back,
-}
-
-#[stable(feature = "rust1", since = "1.0.0")]
-impl<A, B> Iterator for Chain<A, B> where
- A: Iterator,
- B: Iterator<Item = A::Item>
-{
- type Item = A::Item;
-
- #[inline]
- fn next(&mut self) -> Option<A::Item> {
- match self.state {
- ChainState::Both => match self.a.next() {
- elt @ Some(..) => elt,
- None => {
- self.state = ChainState::Back;
- self.b.next()
- }
- },
- ChainState::Front => self.a.next(),
- ChainState::Back => self.b.next(),
- }
- }
-
- #[inline]
- #[rustc_inherit_overflow_checks]
- fn count(self) -> usize {
- match self.state {
- ChainState::Both => self.a.count() + self.b.count(),
- ChainState::Front => self.a.count(),
- ChainState::Back => self.b.count(),
- }
- }
-
- fn try_fold<Acc, F, R>(&mut self, init: Acc, mut f: F) -> R where
- Self: Sized, F: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
- {
- let mut accum = init;
- match self.state {
- ChainState::Both | ChainState::Front => {
- accum = self.a.try_fold(accum, &mut f)?;
- if let ChainState::Both = self.state {
- self.state = ChainState::Back;
- }
- }
- _ => { }
- }
- if let ChainState::Back = self.state {
- accum = self.b.try_fold(accum, &mut f)?;
- }
- Try::from_ok(accum)
- }
-
- fn fold<Acc, F>(self, init: Acc, mut f: F) -> Acc
- where F: FnMut(Acc, Self::Item) -> Acc,
- {
- let mut accum = init;
- match self.state {
- ChainState::Both | ChainState::Front => {
- accum = self.a.fold(accum, &mut f);
- }
- _ => { }
- }
- match self.state {
- ChainState::Both | ChainState::Back => {
- accum = self.b.fold(accum, &mut f);
- }
- _ => { }
- }
- accum
- }
-
- #[inline]
- fn nth(&mut self, mut n: usize) -> Option<A::Item> {
- match self.state {
- ChainState::Both | ChainState::Front => {
- for x in self.a.by_ref() {
- if n == 0 {
- return Some(x)
- }
- n -= 1;
- }
- if let ChainState::Both = self.state {
- self.state = ChainState::Back;
- }
- }
- ChainState::Back => {}
- }
- if let ChainState::Back = self.state {
- self.b.nth(n)
- } else {
- None
- }
- }
-
- #[inline]
- fn find<P>(&mut self, mut predicate: P) -> Option<Self::Item> where
- P: FnMut(&Self::Item) -> bool,
- {
- match self.state {
- ChainState::Both => match self.a.find(&mut predicate) {
- None => {
- self.state = ChainState::Back;
- self.b.find(predicate)
- }
- v => v
- },
- ChainState::Front => self.a.find(predicate),
- ChainState::Back => self.b.find(predicate),
- }
- }
-
- #[inline]
- fn last(self) -> Option<A::Item> {
- match self.state {
- ChainState::Both => {
- // Must exhaust a before b.
- let a_last = self.a.last();
- let b_last = self.b.last();
- b_last.or(a_last)
- },
- ChainState::Front => self.a.last(),
- ChainState::Back => self.b.last()
- }
- }
-
- #[inline]
- fn size_hint(&self) -> (usize, Option<usize>) {
- let (a_lower, a_upper) = self.a.size_hint();
- let (b_lower, b_upper) = self.b.size_hint();
-
- let lower = a_lower.saturating_add(b_lower);
-
- let upper = match (a_upper, b_upper) {
- (Some(x), Some(y)) => x.checked_add(y),
- _ => None
- };
-
- (lower, upper)
- }
-}
-
-#[stable(feature = "rust1", since = "1.0.0")]
-impl<A, B> DoubleEndedIterator for Chain<A, B> where
- A: DoubleEndedIterator,
- B: DoubleEndedIterator<Item=A::Item>,
-{
- #[inline]
- fn next_back(&mut self) -> Option<A::Item> {
- match self.state {
- ChainState::Both => match self.b.next_back() {
- elt @ Some(..) => elt,
- None => {
- self.state = ChainState::Front;
- self.a.next_back()
- }
- },
- ChainState::Front => self.a.next_back(),
- ChainState::Back => self.b.next_back(),
- }
- }
-
- fn try_rfold<Acc, F, R>(&mut self, init: Acc, mut f: F) -> R where
- Self: Sized, F: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
- {
- let mut accum = init;
- match self.state {
- ChainState::Both | ChainState::Back => {
- accum = self.b.try_rfold(accum, &mut f)?;
- if let ChainState::Both = self.state {
- self.state = ChainState::Front;
- }
- }
- _ => { }
- }
- if let ChainState::Front = self.state {
- accum = self.a.try_rfold(accum, &mut f)?;
- }
- Try::from_ok(accum)
- }
-
- fn rfold<Acc, F>(self, init: Acc, mut f: F) -> Acc
- where F: FnMut(Acc, Self::Item) -> Acc,
- {
- let mut accum = init;
- match self.state {
- ChainState::Both | ChainState::Back => {
- accum = self.b.rfold(accum, &mut f);
- }
- _ => { }
- }
- match self.state {
- ChainState::Both | ChainState::Front => {
- accum = self.a.rfold(accum, &mut f);
- }
- _ => { }
- }
- accum
- }
-
-}
-
-// Note: *both* must be fused to handle double-ended iterators.
-#[stable(feature = "fused", since = "1.26.0")]
-impl<A, B> FusedIterator for Chain<A, B>
- where A: FusedIterator,
- B: FusedIterator<Item=A::Item>,
-{}
-
-#[unstable(feature = "trusted_len", issue = "37572")]
-unsafe impl<A, B> TrustedLen for Chain<A, B>
- where A: TrustedLen, B: TrustedLen<Item=A::Item>,
-{}
-
-/// An iterator that iterates two other iterators simultaneously.
-///
-/// This `struct` is created by the [`zip`] method on [`Iterator`]. See its
-/// documentation for more.
-///
-/// [`zip`]: trait.Iterator.html#method.zip
-/// [`Iterator`]: trait.Iterator.html
-#[derive(Clone, Debug)]
-#[must_use = "iterators are lazy and do nothing unless consumed"]
-#[stable(feature = "rust1", since = "1.0.0")]
-pub struct Zip<A, B> {
- a: A,
- b: B,
- // index and len are only used by the specialized version of zip
- index: usize,
- len: usize,
-}
-
-#[stable(feature = "rust1", since = "1.0.0")]
-impl<A, B> Iterator for Zip<A, B> where A: Iterator, B: Iterator
-{
- type Item = (A::Item, B::Item);
-
- #[inline]
- fn next(&mut self) -> Option<Self::Item> {
- ZipImpl::next(self)
- }
-
- #[inline]
- fn size_hint(&self) -> (usize, Option<usize>) {
- ZipImpl::size_hint(self)
- }
-
- #[inline]
- fn nth(&mut self, n: usize) -> Option<Self::Item> {
- ZipImpl::nth(self, n)
- }
-}
-
-#[stable(feature = "rust1", since = "1.0.0")]
-impl<A, B> DoubleEndedIterator for Zip<A, B> where
- A: DoubleEndedIterator + ExactSizeIterator,
- B: DoubleEndedIterator + ExactSizeIterator,
-{
- #[inline]
- fn next_back(&mut self) -> Option<(A::Item, B::Item)> {
- ZipImpl::next_back(self)
- }
-}
-
-// Zip specialization trait
-#[doc(hidden)]
-trait ZipImpl<A, B> {
- type Item;
- fn new(a: A, b: B) -> Self;
- fn next(&mut self) -> Option<Self::Item>;
- fn size_hint(&self) -> (usize, Option<usize>);
- fn nth(&mut self, n: usize) -> Option<Self::Item>;
- fn super_nth(&mut self, mut n: usize) -> Option<Self::Item> {
- while let Some(x) = self.next() {
- if n == 0 { return Some(x) }
- n -= 1;
- }
- None
- }
- fn next_back(&mut self) -> Option<Self::Item>
- where A: DoubleEndedIterator + ExactSizeIterator,
- B: DoubleEndedIterator + ExactSizeIterator;
-}
-
-// General Zip impl
-#[doc(hidden)]
-impl<A, B> ZipImpl<A, B> for Zip<A, B>
- where A: Iterator, B: Iterator
-{
- type Item = (A::Item, B::Item);
- default fn new(a: A, b: B) -> Self {
- Zip {
- a,
- b,
- index: 0, // unused
- len: 0, // unused
- }
- }
-
- #[inline]
- default fn next(&mut self) -> Option<(A::Item, B::Item)> {
- self.a.next().and_then(|x| {
- self.b.next().and_then(|y| {
- Some((x, y))
- })
- })
- }
-
- #[inline]
- default fn nth(&mut self, n: usize) -> Option<Self::Item> {
- self.super_nth(n)
- }
-
- #[inline]
- default fn next_back(&mut self) -> Option<(A::Item, B::Item)>
- where A: DoubleEndedIterator + ExactSizeIterator,
- B: DoubleEndedIterator + ExactSizeIterator
- {
- let a_sz = self.a.len();
- let b_sz = self.b.len();
- if a_sz != b_sz {
- // Adjust a, b to equal length
- if a_sz > b_sz {
- for _ in 0..a_sz - b_sz { self.a.next_back(); }
- } else {
- for _ in 0..b_sz - a_sz { self.b.next_back(); }
- }
- }
- match (self.a.next_back(), self.b.next_back()) {
- (Some(x), Some(y)) => Some((x, y)),
- (None, None) => None,
- _ => unreachable!(),
- }
- }
-
- #[inline]
- default fn size_hint(&self) -> (usize, Option<usize>) {
- let (a_lower, a_upper) = self.a.size_hint();
- let (b_lower, b_upper) = self.b.size_hint();
-
- let lower = cmp::min(a_lower, b_lower);
-
- let upper = match (a_upper, b_upper) {
- (Some(x), Some(y)) => Some(cmp::min(x,y)),
- (Some(x), None) => Some(x),
- (None, Some(y)) => Some(y),
- (None, None) => None
- };
-
- (lower, upper)
- }
-}
-
-#[doc(hidden)]
-impl<A, B> ZipImpl<A, B> for Zip<A, B>
- where A: TrustedRandomAccess, B: TrustedRandomAccess
-{
- fn new(a: A, b: B) -> Self {
- let len = cmp::min(a.len(), b.len());
- Zip {
- a,
- b,
- index: 0,
- len,
- }
- }
-
- #[inline]
- fn next(&mut self) -> Option<(A::Item, B::Item)> {
- if self.index < self.len {
- let i = self.index;
- self.index += 1;
- unsafe {
- Some((self.a.get_unchecked(i), self.b.get_unchecked(i)))
- }
- } else if A::may_have_side_effect() && self.index < self.a.len() {
- // match the base implementation's potential side effects
- unsafe {
- self.a.get_unchecked(self.index);
- }
- self.index += 1;
- None
- } else {
- None
- }
- }
-
- #[inline]
- fn size_hint(&self) -> (usize, Option<usize>) {
- let len = self.len - self.index;
- (len, Some(len))
- }
-
- #[inline]
- fn nth(&mut self, n: usize) -> Option<Self::Item> {
- let delta = cmp::min(n, self.len - self.index);
- let end = self.index + delta;
- while self.index < end {
- let i = self.index;
- self.index += 1;
- if A::may_have_side_effect() {
- unsafe { self.a.get_unchecked(i); }
- }
- if B::may_have_side_effect() {
- unsafe { self.b.get_unchecked(i); }
- }
- }
-
- self.super_nth(n - delta)
- }
-
- #[inline]
- fn next_back(&mut self) -> Option<(A::Item, B::Item)>
- where A: DoubleEndedIterator + ExactSizeIterator,
- B: DoubleEndedIterator + ExactSizeIterator
- {
- // Adjust a, b to equal length
- if A::may_have_side_effect() {
- let sz = self.a.len();
- if sz > self.len {
- for _ in 0..sz - cmp::max(self.len, self.index) {
- self.a.next_back();
- }
- }
- }
- if B::may_have_side_effect() {
- let sz = self.b.len();
- if sz > self.len {
- for _ in 0..sz - self.len {
- self.b.next_back();
- }
- }
- }
- if self.index < self.len {
- self.len -= 1;
- let i = self.len;
- unsafe {
- Some((self.a.get_unchecked(i), self.b.get_unchecked(i)))
- }
- } else {
- None
- }
- }
-}
-
-#[stable(feature = "rust1", since = "1.0.0")]
-impl<A, B> ExactSizeIterator for Zip<A, B>
- where A: ExactSizeIterator, B: ExactSizeIterator {}
-
-#[doc(hidden)]
-unsafe impl<A, B> TrustedRandomAccess for Zip<A, B>
- where A: TrustedRandomAccess,
- B: TrustedRandomAccess,
-{
- unsafe fn get_unchecked(&mut self, i: usize) -> (A::Item, B::Item) {
- (self.a.get_unchecked(i), self.b.get_unchecked(i))
- }
-
- fn may_have_side_effect() -> bool {
- A::may_have_side_effect() || B::may_have_side_effect()
- }
-}
-
-#[stable(feature = "fused", since = "1.26.0")]
-impl<A, B> FusedIterator for Zip<A, B>
- where A: FusedIterator, B: FusedIterator, {}
-
-#[unstable(feature = "trusted_len", issue = "37572")]
-unsafe impl<A, B> TrustedLen for Zip<A, B>
- where A: TrustedLen, B: TrustedLen,
-{}
-
-/// An iterator that maps the values of `iter` with `f`.
-///
-/// This `struct` is created by the [`map`] method on [`Iterator`]. See its
-/// documentation for more.
-///
-/// [`map`]: trait.Iterator.html#method.map
-/// [`Iterator`]: trait.Iterator.html
-///
-/// # Notes about side effects
-///
-/// The [`map`] iterator implements [`DoubleEndedIterator`], meaning that
-/// you can also [`map`] backwards:
-///
-/// ```rust
-/// let v: Vec<i32> = vec![1, 2, 3].into_iter().map(|x| x + 1).rev().collect();
-///
-/// assert_eq!(v, [4, 3, 2]);
-/// ```
-///
-/// [`DoubleEndedIterator`]: trait.DoubleEndedIterator.html
-///
-/// But if your closure has state, iterating backwards may act in a way you do
-/// not expect. Let's go through an example. First, in the forward direction:
-///
-/// ```rust
-/// let mut c = 0;
-///
-/// for pair in vec!['a', 'b', 'c'].into_iter()
-/// .map(|letter| { c += 1; (letter, c) }) {
-/// println!("{:?}", pair);
-/// }
-/// ```
-///
-/// This will print "('a', 1), ('b', 2), ('c', 3)".
-///
-/// Now consider this twist where we add a call to `rev`. This version will
-/// print `('c', 1), ('b', 2), ('a', 3)`. Note that the letters are reversed,
-/// but the values of the counter still go in order. This is because `map()` is
-/// still being called lazily on each item, but we are popping items off the
-/// back of the vector now, instead of shifting them from the front.
-///
-/// ```rust
-/// let mut c = 0;
-///
-/// for pair in vec!['a', 'b', 'c'].into_iter()
-/// .map(|letter| { c += 1; (letter, c) })
-/// .rev() {
-/// println!("{:?}", pair);
-/// }
-/// ```
-#[must_use = "iterators are lazy and do nothing unless consumed"]
-#[stable(feature = "rust1", since = "1.0.0")]
-#[derive(Clone)]
-pub struct Map<I, F> {
- iter: I,
- f: F,
-}
-
-#[stable(feature = "core_impl_debug", since = "1.9.0")]
-impl<I: fmt::Debug, F> fmt::Debug for Map<I, F> {
- fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
- f.debug_struct("Map")
- .field("iter", &self.iter)
- .finish()
- }
-}
-
-#[stable(feature = "rust1", since = "1.0.0")]
-impl<B, I: Iterator, F> Iterator for Map<I, F> where F: FnMut(I::Item) -> B {
- type Item = B;
-
- #[inline]
- fn next(&mut self) -> Option<B> {
- self.iter.next().map(&mut self.f)
- }
-
- #[inline]
- fn size_hint(&self) -> (usize, Option<usize>) {
- self.iter.size_hint()
- }
-
- fn try_fold<Acc, G, R>(&mut self, init: Acc, mut g: G) -> R where
- Self: Sized, G: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
- {
- let f = &mut self.f;
- self.iter.try_fold(init, move |acc, elt| g(acc, f(elt)))
- }
-
- fn fold<Acc, G>(self, init: Acc, mut g: G) -> Acc
- where G: FnMut(Acc, Self::Item) -> Acc,
- {
- let mut f = self.f;
- self.iter.fold(init, move |acc, elt| g(acc, f(elt)))
- }
-}
-
-#[stable(feature = "rust1", since = "1.0.0")]
-impl<B, I: DoubleEndedIterator, F> DoubleEndedIterator for Map<I, F> where
- F: FnMut(I::Item) -> B,
-{
- #[inline]
- fn next_back(&mut self) -> Option<B> {
- self.iter.next_back().map(&mut self.f)
- }
-
- fn try_rfold<Acc, G, R>(&mut self, init: Acc, mut g: G) -> R where
- Self: Sized, G: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
- {
- let f = &mut self.f;
- self.iter.try_rfold(init, move |acc, elt| g(acc, f(elt)))
- }
-
- fn rfold<Acc, G>(self, init: Acc, mut g: G) -> Acc
- where G: FnMut(Acc, Self::Item) -> Acc,
- {
- let mut f = self.f;
- self.iter.rfold(init, move |acc, elt| g(acc, f(elt)))
- }
-}
-
-#[stable(feature = "rust1", since = "1.0.0")]
-impl<B, I: ExactSizeIterator, F> ExactSizeIterator for Map<I, F>
- where F: FnMut(I::Item) -> B
-{
- fn len(&self) -> usize {
- self.iter.len()
- }
-
- fn is_empty(&self) -> bool {
- self.iter.is_empty()
- }
-}
-
-#[stable(feature = "fused", since = "1.26.0")]
-impl<B, I: FusedIterator, F> FusedIterator for Map<I, F>
- where F: FnMut(I::Item) -> B {}
-
-#[unstable(feature = "trusted_len", issue = "37572")]
-unsafe impl<B, I, F> TrustedLen for Map<I, F>
- where I: TrustedLen,
- F: FnMut(I::Item) -> B {}
-
-#[doc(hidden)]
-unsafe impl<B, I, F> TrustedRandomAccess for Map<I, F>
- where I: TrustedRandomAccess,
- F: FnMut(I::Item) -> B,
-{
- unsafe fn get_unchecked(&mut self, i: usize) -> Self::Item {
- (self.f)(self.iter.get_unchecked(i))
- }
- #[inline]
- fn may_have_side_effect() -> bool { true }
-}
-
-/// An iterator that filters the elements of `iter` with `predicate`.
-///
-/// This `struct` is created by the [`filter`] method on [`Iterator`]. See its
-/// documentation for more.
-///
-/// [`filter`]: trait.Iterator.html#method.filter
-/// [`Iterator`]: trait.Iterator.html
-#[must_use = "iterators are lazy and do nothing unless consumed"]
-#[stable(feature = "rust1", since = "1.0.0")]
-#[derive(Clone)]
-pub struct Filter<I, P> {
- iter: I,
- predicate: P,
-}
-
-#[stable(feature = "core_impl_debug", since = "1.9.0")]
-impl<I: fmt::Debug, P> fmt::Debug for Filter<I, P> {
- fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
- f.debug_struct("Filter")
- .field("iter", &self.iter)
- .finish()
- }
-}
-
-#[stable(feature = "rust1", since = "1.0.0")]
-impl<I: Iterator, P> Iterator for Filter<I, P> where P: FnMut(&I::Item) -> bool {
- type Item = I::Item;
-
- #[inline]
- fn next(&mut self) -> Option<I::Item> {
- for x in &mut self.iter {
- if (self.predicate)(&x) {
- return Some(x);
- }
- }
- None
- }
-
- #[inline]
- fn size_hint(&self) -> (usize, Option<usize>) {
- let (_, upper) = self.iter.size_hint();
- (0, upper) // can't know a lower bound, due to the predicate
- }
-
- // this special case allows the compiler to make `.filter(_).count()`
- // branchless. Barring perfect branch prediction (which is unattainable in
- // the general case), this will be much faster in >90% of cases (containing
- // virtually all real workloads) and only a tiny bit slower in the rest.
- //
- // Having this specialization thus allows us to write `.filter(p).count()`
- // where we would otherwise write `.map(|x| p(x) as usize).sum()`, which is
- // less readable and also less backwards-compatible to Rust before 1.10.
- //
- // Using the branchless version will also simplify the LLVM byte code, thus
- // leaving more budget for LLVM optimizations.
- #[inline]
- fn count(mut self) -> usize {
- let mut count = 0;
- for x in &mut self.iter {
- count += (self.predicate)(&x) as usize;
- }
- count
- }
-
- #[inline]
- fn try_fold<Acc, Fold, R>(&mut self, init: Acc, mut fold: Fold) -> R where
- Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
- {
- let predicate = &mut self.predicate;
- self.iter.try_fold(init, move |acc, item| if predicate(&item) {
- fold(acc, item)
- } else {
- Try::from_ok(acc)
- })
- }
-
- #[inline]
- fn fold<Acc, Fold>(self, init: Acc, mut fold: Fold) -> Acc
- where Fold: FnMut(Acc, Self::Item) -> Acc,
- {
- let mut predicate = self.predicate;
- self.iter.fold(init, move |acc, item| if predicate(&item) {
- fold(acc, item)
- } else {
- acc
- })
- }
-}
-
-#[stable(feature = "rust1", since = "1.0.0")]
-impl<I: DoubleEndedIterator, P> DoubleEndedIterator for Filter<I, P>
- where P: FnMut(&I::Item) -> bool,
-{
- #[inline]
- fn next_back(&mut self) -> Option<I::Item> {
- for x in self.iter.by_ref().rev() {
- if (self.predicate)(&x) {
- return Some(x);
- }
- }
- None
- }
-
- #[inline]
- fn try_rfold<Acc, Fold, R>(&mut self, init: Acc, mut fold: Fold) -> R where
- Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
- {
- let predicate = &mut self.predicate;
- self.iter.try_rfold(init, move |acc, item| if predicate(&item) {
- fold(acc, item)
- } else {
- Try::from_ok(acc)
- })
- }
-
- #[inline]
- fn rfold<Acc, Fold>(self, init: Acc, mut fold: Fold) -> Acc
- where Fold: FnMut(Acc, Self::Item) -> Acc,
- {
- let mut predicate = self.predicate;
- self.iter.rfold(init, move |acc, item| if predicate(&item) {
- fold(acc, item)
- } else {
- acc
- })
- }
-}
-
-#[stable(feature = "fused", since = "1.26.0")]
-impl<I: FusedIterator, P> FusedIterator for Filter<I, P>
- where P: FnMut(&I::Item) -> bool {}
-
-/// An iterator that uses `f` to both filter and map elements from `iter`.
-///
-/// This `struct` is created by the [`filter_map`] method on [`Iterator`]. See its
-/// documentation for more.
-///
-/// [`filter_map`]: trait.Iterator.html#method.filter_map
-/// [`Iterator`]: trait.Iterator.html
-#[must_use = "iterators are lazy and do nothing unless consumed"]
-#[stable(feature = "rust1", since = "1.0.0")]
-#[derive(Clone)]
-pub struct FilterMap<I, F> {
- iter: I,
- f: F,
-}
-
-#[stable(feature = "core_impl_debug", since = "1.9.0")]
-impl<I: fmt::Debug, F> fmt::Debug for FilterMap<I, F> {
- fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
- f.debug_struct("FilterMap")
- .field("iter", &self.iter)
- .finish()
- }
-}
-
-#[stable(feature = "rust1", since = "1.0.0")]
-impl<B, I: Iterator, F> Iterator for FilterMap<I, F>
- where F: FnMut(I::Item) -> Option<B>,
-{
- type Item = B;
-
- #[inline]
- fn next(&mut self) -> Option<B> {
- for x in self.iter.by_ref() {
- if let Some(y) = (self.f)(x) {
- return Some(y);
- }
- }
- None
- }
-
- #[inline]
- fn size_hint(&self) -> (usize, Option<usize>) {
- let (_, upper) = self.iter.size_hint();
- (0, upper) // can't know a lower bound, due to the predicate
- }
-
- #[inline]
- fn try_fold<Acc, Fold, R>(&mut self, init: Acc, mut fold: Fold) -> R where
- Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
- {
- let f = &mut self.f;
- self.iter.try_fold(init, move |acc, item| match f(item) {
- Some(x) => fold(acc, x),
- None => Try::from_ok(acc),
- })
- }
-
- #[inline]
- fn fold<Acc, Fold>(self, init: Acc, mut fold: Fold) -> Acc
- where Fold: FnMut(Acc, Self::Item) -> Acc,
- {
- let mut f = self.f;
- self.iter.fold(init, move |acc, item| match f(item) {
- Some(x) => fold(acc, x),
- None => acc,
- })
- }
-}
-
-#[stable(feature = "rust1", since = "1.0.0")]
-impl<B, I: DoubleEndedIterator, F> DoubleEndedIterator for FilterMap<I, F>
- where F: FnMut(I::Item) -> Option<B>,
-{
- #[inline]
- fn next_back(&mut self) -> Option<B> {
- for x in self.iter.by_ref().rev() {
- if let Some(y) = (self.f)(x) {
- return Some(y);
- }
- }
- None
- }
-
- #[inline]
- fn try_rfold<Acc, Fold, R>(&mut self, init: Acc, mut fold: Fold) -> R where
- Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
- {
- let f = &mut self.f;
- self.iter.try_rfold(init, move |acc, item| match f(item) {
- Some(x) => fold(acc, x),
- None => Try::from_ok(acc),
- })
- }
-
- #[inline]
- fn rfold<Acc, Fold>(self, init: Acc, mut fold: Fold) -> Acc
- where Fold: FnMut(Acc, Self::Item) -> Acc,
- {
- let mut f = self.f;
- self.iter.rfold(init, move |acc, item| match f(item) {
- Some(x) => fold(acc, x),
- None => acc,
- })
- }
-}
-
-#[stable(feature = "fused", since = "1.26.0")]
-impl<B, I: FusedIterator, F> FusedIterator for FilterMap<I, F>
- where F: FnMut(I::Item) -> Option<B> {}
-
-/// An iterator that yields the current count and the element during iteration.
-///
-/// This `struct` is created by the [`enumerate`] method on [`Iterator`]. See its
-/// documentation for more.
-///
-/// [`enumerate`]: trait.Iterator.html#method.enumerate
-/// [`Iterator`]: trait.Iterator.html
-#[derive(Clone, Debug)]
-#[must_use = "iterators are lazy and do nothing unless consumed"]
-#[stable(feature = "rust1", since = "1.0.0")]
-pub struct Enumerate<I> {
- iter: I,
- count: usize,
-}
-
-#[stable(feature = "rust1", since = "1.0.0")]
-impl<I> Iterator for Enumerate<I> where I: Iterator {
- type Item = (usize, <I as Iterator>::Item);
-
- /// # Overflow Behavior
- ///
- /// The method does no guarding against overflows, so enumerating more than
- /// `usize::MAX` elements either produces the wrong result or panics. If
- /// debug assertions are enabled, a panic is guaranteed.
- ///
- /// # Panics
- ///
- /// Might panic if the index of the element overflows a `usize`.
- #[inline]
- #[rustc_inherit_overflow_checks]
- fn next(&mut self) -> Option<(usize, <I as Iterator>::Item)> {
- self.iter.next().map(|a| {
- let ret = (self.count, a);
- // Possible undefined overflow.
- self.count += 1;
- ret
- })
- }
-
- #[inline]
- fn size_hint(&self) -> (usize, Option<usize>) {
- self.iter.size_hint()
- }
-
- #[inline]
- #[rustc_inherit_overflow_checks]
- fn nth(&mut self, n: usize) -> Option<(usize, I::Item)> {
- self.iter.nth(n).map(|a| {
- let i = self.count + n;
- self.count = i + 1;
- (i, a)
- })
- }
-
- #[inline]
- fn count(self) -> usize {
- self.iter.count()
- }
-
- #[inline]
- #[rustc_inherit_overflow_checks]
- fn try_fold<Acc, Fold, R>(&mut self, init: Acc, mut fold: Fold) -> R where
- Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
- {
- let count = &mut self.count;
- self.iter.try_fold(init, move |acc, item| {
- let acc = fold(acc, (*count, item));
- *count += 1;
- acc
- })
- }
-
- #[inline]
- #[rustc_inherit_overflow_checks]
- fn fold<Acc, Fold>(self, init: Acc, mut fold: Fold) -> Acc
- where Fold: FnMut(Acc, Self::Item) -> Acc,
- {
- let mut count = self.count;
- self.iter.fold(init, move |acc, item| {
- let acc = fold(acc, (count, item));
- count += 1;
- acc
- })
- }
-}
-
-#[stable(feature = "rust1", since = "1.0.0")]
-impl<I> DoubleEndedIterator for Enumerate<I> where
- I: ExactSizeIterator + DoubleEndedIterator
-{
- #[inline]
- fn next_back(&mut self) -> Option<(usize, <I as Iterator>::Item)> {
- self.iter.next_back().map(|a| {
- let len = self.iter.len();
- // Can safely add, `ExactSizeIterator` promises that the number of
- // elements fits into a `usize`.
- (self.count + len, a)
- })
- }
-
- #[inline]
- fn try_rfold<Acc, Fold, R>(&mut self, init: Acc, mut fold: Fold) -> R where
- Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
- {
- // Can safely add and subtract the count, as `ExactSizeIterator` promises
- // that the number of elements fits into a `usize`.
- let mut count = self.count + self.iter.len();
- self.iter.try_rfold(init, move |acc, item| {
- count -= 1;
- fold(acc, (count, item))
- })
- }
-
- #[inline]
- fn rfold<Acc, Fold>(self, init: Acc, mut fold: Fold) -> Acc
- where Fold: FnMut(Acc, Self::Item) -> Acc,
- {
- // Can safely add and subtract the count, as `ExactSizeIterator` promises
- // that the number of elements fits into a `usize`.
- let mut count = self.count + self.iter.len();
- self.iter.rfold(init, move |acc, item| {
- count -= 1;
- fold(acc, (count, item))
- })
- }
-}
-
-#[stable(feature = "rust1", since = "1.0.0")]
-impl<I> ExactSizeIterator for Enumerate<I> where I: ExactSizeIterator {
- fn len(&self) -> usize {
- self.iter.len()
- }
-
- fn is_empty(&self) -> bool {
- self.iter.is_empty()
- }
-}
-
-#[doc(hidden)]
-unsafe impl<I> TrustedRandomAccess for Enumerate<I>
- where I: TrustedRandomAccess
-{
- unsafe fn get_unchecked(&mut self, i: usize) -> (usize, I::Item) {
- (self.count + i, self.iter.get_unchecked(i))
- }
-
- fn may_have_side_effect() -> bool {
- I::may_have_side_effect()
- }
-}
-
-#[stable(feature = "fused", since = "1.26.0")]
-impl<I> FusedIterator for Enumerate<I> where I: FusedIterator {}
-
-#[unstable(feature = "trusted_len", issue = "37572")]
-unsafe impl<I> TrustedLen for Enumerate<I>
- where I: TrustedLen,
-{}
-
-
-/// An iterator with a `peek()` that returns an optional reference to the next
-/// element.
-///
-/// This `struct` is created by the [`peekable`] method on [`Iterator`]. See its
-/// documentation for more.
-///
-/// [`peekable`]: trait.Iterator.html#method.peekable
-/// [`Iterator`]: trait.Iterator.html
-#[derive(Clone, Debug)]
-#[must_use = "iterators are lazy and do nothing unless consumed"]
-#[stable(feature = "rust1", since = "1.0.0")]
-pub struct Peekable<I: Iterator> {
- iter: I,
- /// Remember a peeked value, even if it was None.
- peeked: Option<Option<I::Item>>,
-}
-
-// Peekable must remember if a None has been seen in the `.peek()` method.
-// It ensures that `.peek(); .peek();` or `.peek(); .next();` only advances the
-// underlying iterator at most once. This does not by itself make the iterator
-// fused.
-#[stable(feature = "rust1", since = "1.0.0")]
-impl<I: Iterator> Iterator for Peekable<I> {
- type Item = I::Item;
-
- #[inline]
- fn next(&mut self) -> Option<I::Item> {
- match self.peeked.take() {
- Some(v) => v,
- None => self.iter.next(),
- }
- }
-
- #[inline]
- #[rustc_inherit_overflow_checks]
- fn count(mut self) -> usize {
- match self.peeked.take() {
- Some(None) => 0,
- Some(Some(_)) => 1 + self.iter.count(),
- None => self.iter.count(),
- }
- }
-
- #[inline]
- fn nth(&mut self, n: usize) -> Option<I::Item> {
- match self.peeked.take() {
- Some(None) => None,
- Some(v @ Some(_)) if n == 0 => v,
- Some(Some(_)) => self.iter.nth(n - 1),
- None => self.iter.nth(n),
- }
- }
-
- #[inline]
- fn last(mut self) -> Option<I::Item> {
- let peek_opt = match self.peeked.take() {
- Some(None) => return None,
- Some(v) => v,
- None => None,
- };
- self.iter.last().or(peek_opt)
- }
-
- #[inline]
- fn size_hint(&self) -> (usize, Option<usize>) {
- let peek_len = match self.peeked {
- Some(None) => return (0, Some(0)),
- Some(Some(_)) => 1,
- None => 0,
- };
- let (lo, hi) = self.iter.size_hint();
- let lo = lo.saturating_add(peek_len);
- let hi = hi.and_then(|x| x.checked_add(peek_len));
- (lo, hi)
- }
-
- #[inline]
- fn try_fold<B, F, R>(&mut self, init: B, mut f: F) -> R where
- Self: Sized, F: FnMut(B, Self::Item) -> R, R: Try<Ok=B>
- {
- let acc = match self.peeked.take() {
- Some(None) => return Try::from_ok(init),
- Some(Some(v)) => f(init, v)?,
- None => init,
- };
- self.iter.try_fold(acc, f)
- }
-
- #[inline]
- fn fold<Acc, Fold>(self, init: Acc, mut fold: Fold) -> Acc
- where Fold: FnMut(Acc, Self::Item) -> Acc,
- {
- let acc = match self.peeked {
- Some(None) => return init,
- Some(Some(v)) => fold(init, v),
- None => init,
- };
- self.iter.fold(acc, fold)
- }
-}
-
-#[stable(feature = "rust1", since = "1.0.0")]
-impl<I: ExactSizeIterator> ExactSizeIterator for Peekable<I> {}
-
-#[stable(feature = "fused", since = "1.26.0")]
-impl<I: FusedIterator> FusedIterator for Peekable<I> {}
-
-impl<I: Iterator> Peekable<I> {
- /// Returns a reference to the next() value without advancing the iterator.
- ///
- /// Like [`next`], if there is a value, it is wrapped in a `Some(T)`.
- /// But if the iteration is over, `None` is returned.
- ///
- /// [`next`]: trait.Iterator.html#tymethod.next
- ///
- /// Because `peek()` returns a reference, and many iterators iterate over
- /// references, there can be a possibly confusing situation where the
- /// return value is a double reference. You can see this effect in the
- /// examples below.
- ///
- /// # Examples
- ///
- /// Basic usage:
- ///
- /// ```
- /// let xs = [1, 2, 3];
- ///
- /// let mut iter = xs.iter().peekable();
- ///
- /// // peek() lets us see into the future
- /// assert_eq!(iter.peek(), Some(&&1));
- /// assert_eq!(iter.next(), Some(&1));
- ///
- /// assert_eq!(iter.next(), Some(&2));
- ///
- /// // The iterator does not advance even if we `peek` multiple times
- /// assert_eq!(iter.peek(), Some(&&3));
- /// assert_eq!(iter.peek(), Some(&&3));
- ///
- /// assert_eq!(iter.next(), Some(&3));
- ///
- /// // After the iterator is finished, so is `peek()`
- /// assert_eq!(iter.peek(), None);
- /// assert_eq!(iter.next(), None);
- /// ```
- #[inline]
- #[stable(feature = "rust1", since = "1.0.0")]
- pub fn peek(&mut self) -> Option<&I::Item> {
- let iter = &mut self.iter;
- self.peeked.get_or_insert_with(|| iter.next()).as_ref()
- }
-}
-
-/// An iterator that rejects elements while `predicate` is true.
-///
-/// This `struct` is created by the [`skip_while`] method on [`Iterator`]. See its
-/// documentation for more.
-///
-/// [`skip_while`]: trait.Iterator.html#method.skip_while
-/// [`Iterator`]: trait.Iterator.html
-#[must_use = "iterators are lazy and do nothing unless consumed"]
-#[stable(feature = "rust1", since = "1.0.0")]
-#[derive(Clone)]
-pub struct SkipWhile<I, P> {
- iter: I,
- flag: bool,
- predicate: P,
-}
-
-#[stable(feature = "core_impl_debug", since = "1.9.0")]
-impl<I: fmt::Debug, P> fmt::Debug for SkipWhile<I, P> {
- fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
- f.debug_struct("SkipWhile")
- .field("iter", &self.iter)
- .field("flag", &self.flag)
- .finish()
- }
-}
-
-#[stable(feature = "rust1", since = "1.0.0")]
-impl<I: Iterator, P> Iterator for SkipWhile<I, P>
- where P: FnMut(&I::Item) -> bool
-{
- type Item = I::Item;
-
- #[inline]
- fn next(&mut self) -> Option<I::Item> {
- let flag = &mut self.flag;
- let pred = &mut self.predicate;
- self.iter.find(move |x| {
- if *flag || !pred(x) {
- *flag = true;
- true
- } else {
- false
- }
- })
- }
-
- #[inline]
- fn size_hint(&self) -> (usize, Option<usize>) {
- let (_, upper) = self.iter.size_hint();
- (0, upper) // can't know a lower bound, due to the predicate
- }
-
- #[inline]
- fn try_fold<Acc, Fold, R>(&mut self, mut init: Acc, mut fold: Fold) -> R where
- Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
- {
- if !self.flag {
- match self.next() {
- Some(v) => init = fold(init, v)?,
- None => return Try::from_ok(init),
- }
- }
- self.iter.try_fold(init, fold)
- }
-
- #[inline]
- fn fold<Acc, Fold>(mut self, mut init: Acc, mut fold: Fold) -> Acc
- where Fold: FnMut(Acc, Self::Item) -> Acc,
- {
- if !self.flag {
- match self.next() {
- Some(v) => init = fold(init, v),
- None => return init,
- }
- }
- self.iter.fold(init, fold)
- }
-}
-
-#[stable(feature = "fused", since = "1.26.0")]
-impl<I, P> FusedIterator for SkipWhile<I, P>
- where I: FusedIterator, P: FnMut(&I::Item) -> bool {}
-
-/// An iterator that only accepts elements while `predicate` is true.
-///
-/// This `struct` is created by the [`take_while`] method on [`Iterator`]. See its
-/// documentation for more.
-///
-/// [`take_while`]: trait.Iterator.html#method.take_while
-/// [`Iterator`]: trait.Iterator.html
-#[must_use = "iterators are lazy and do nothing unless consumed"]
-#[stable(feature = "rust1", since = "1.0.0")]
-#[derive(Clone)]
-pub struct TakeWhile<I, P> {
- iter: I,
- flag: bool,
- predicate: P,
-}
-
-#[stable(feature = "core_impl_debug", since = "1.9.0")]
-impl<I: fmt::Debug, P> fmt::Debug for TakeWhile<I, P> {
- fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
- f.debug_struct("TakeWhile")
- .field("iter", &self.iter)
- .field("flag", &self.flag)
- .finish()
- }
-}
-
-#[stable(feature = "rust1", since = "1.0.0")]
-impl<I: Iterator, P> Iterator for TakeWhile<I, P>
- where P: FnMut(&I::Item) -> bool
-{
- type Item = I::Item;
-
- #[inline]
- fn next(&mut self) -> Option<I::Item> {
- if self.flag {
- None
- } else {
- self.iter.next().and_then(|x| {
- if (self.predicate)(&x) {
- Some(x)
- } else {
- self.flag = true;
- None
- }
- })
- }
- }
-
- #[inline]
- fn size_hint(&self) -> (usize, Option<usize>) {
- if self.flag {
- (0, Some(0))
- } else {
- let (_, upper) = self.iter.size_hint();
- (0, upper) // can't know a lower bound, due to the predicate
- }
- }
-
- #[inline]
- fn try_fold<Acc, Fold, R>(&mut self, init: Acc, mut fold: Fold) -> R where
- Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
- {
- if self.flag {
- Try::from_ok(init)
- } else {
- let flag = &mut self.flag;
- let p = &mut self.predicate;
- self.iter.try_fold(init, move |acc, x|{
- if p(&x) {
- LoopState::from_try(fold(acc, x))
- } else {
- *flag = true;
- LoopState::Break(Try::from_ok(acc))
- }
- }).into_try()
- }
- }
-}
-
-#[stable(feature = "fused", since = "1.26.0")]
-impl<I, P> FusedIterator for TakeWhile<I, P>
- where I: FusedIterator, P: FnMut(&I::Item) -> bool {}
-
-/// An iterator that skips over `n` elements of `iter`.
-///
-/// This `struct` is created by the [`skip`] method on [`Iterator`]. See its
-/// documentation for more.
-///
-/// [`skip`]: trait.Iterator.html#method.skip
-/// [`Iterator`]: trait.Iterator.html
-#[derive(Clone, Debug)]
-#[must_use = "iterators are lazy and do nothing unless consumed"]
-#[stable(feature = "rust1", since = "1.0.0")]
-pub struct Skip<I> {
- iter: I,
- n: usize
-}
-
-#[stable(feature = "rust1", since = "1.0.0")]
-impl<I> Iterator for Skip<I> where I: Iterator {
- type Item = <I as Iterator>::Item;
-
- #[inline]
- fn next(&mut self) -> Option<I::Item> {
- if self.n == 0 {
- self.iter.next()
- } else {
- let old_n = self.n;
- self.n = 0;
- self.iter.nth(old_n)
- }
- }
-
- #[inline]
- fn nth(&mut self, n: usize) -> Option<I::Item> {
- // Can't just add n + self.n due to overflow.
- if self.n == 0 {
- self.iter.nth(n)
- } else {
- let to_skip = self.n;
- self.n = 0;
- // nth(n) skips n+1
- if self.iter.nth(to_skip-1).is_none() {
- return None;
- }
- self.iter.nth(n)
- }
- }
-
- #[inline]
- fn count(self) -> usize {
- self.iter.count().saturating_sub(self.n)
- }
-
- #[inline]
- fn last(mut self) -> Option<I::Item> {
- if self.n == 0 {
- self.iter.last()
- } else {
- let next = self.next();
- if next.is_some() {
- // recurse. n should be 0.
- self.last().or(next)
- } else {
- None
- }
- }
- }
-
- #[inline]
- fn size_hint(&self) -> (usize, Option<usize>) {
- let (lower, upper) = self.iter.size_hint();
-
- let lower = lower.saturating_sub(self.n);
- let upper = upper.map(|x| x.saturating_sub(self.n));
-
- (lower, upper)
- }
-
- #[inline]
- fn try_fold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R where
- Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
- {
- let n = self.n;
- self.n = 0;
- if n > 0 {
- // nth(n) skips n+1
- if self.iter.nth(n - 1).is_none() {
- return Try::from_ok(init);
- }
- }
- self.iter.try_fold(init, fold)
- }
-
- #[inline]
- fn fold<Acc, Fold>(mut self, init: Acc, fold: Fold) -> Acc
- where Fold: FnMut(Acc, Self::Item) -> Acc,
- {
- if self.n > 0 {
- // nth(n) skips n+1
- if self.iter.nth(self.n - 1).is_none() {
- return init;
- }
- }
- self.iter.fold(init, fold)
- }
-}
-
-#[stable(feature = "rust1", since = "1.0.0")]
-impl<I> ExactSizeIterator for Skip<I> where I: ExactSizeIterator {}
-
-#[stable(feature = "double_ended_skip_iterator", since = "1.9.0")]
-impl<I> DoubleEndedIterator for Skip<I> where I: DoubleEndedIterator + ExactSizeIterator {
- fn next_back(&mut self) -> Option<Self::Item> {
- if self.len() > 0 {
- self.iter.next_back()
- } else {
- None
- }
- }
-
- fn try_rfold<Acc, Fold, R>(&mut self, init: Acc, mut fold: Fold) -> R where
- Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
- {
- let mut n = self.len();
- if n == 0 {
- Try::from_ok(init)
- } else {
- self.iter.try_rfold(init, move |acc, x| {
- n -= 1;
- let r = fold(acc, x);
- if n == 0 { LoopState::Break(r) }
- else { LoopState::from_try(r) }
- }).into_try()
- }
- }
-}
-
-#[stable(feature = "fused", since = "1.26.0")]
-impl<I> FusedIterator for Skip<I> where I: FusedIterator {}
-
-/// An iterator that only iterates over the first `n` iterations of `iter`.
-///
-/// This `struct` is created by the [`take`] method on [`Iterator`]. See its
-/// documentation for more.
-///
-/// [`take`]: trait.Iterator.html#method.take
-/// [`Iterator`]: trait.Iterator.html
-#[derive(Clone, Debug)]
-#[must_use = "iterators are lazy and do nothing unless consumed"]
-#[stable(feature = "rust1", since = "1.0.0")]
-pub struct Take<I> {
- iter: I,
- n: usize
-}
-
-#[stable(feature = "rust1", since = "1.0.0")]
-impl<I> Iterator for Take<I> where I: Iterator{
- type Item = <I as Iterator>::Item;
-
- #[inline]
- fn next(&mut self) -> Option<<I as Iterator>::Item> {
- if self.n != 0 {
- self.n -= 1;
- self.iter.next()
- } else {
- None
- }
- }
-
- #[inline]
- fn nth(&mut self, n: usize) -> Option<I::Item> {
- if self.n > n {
- self.n -= n + 1;
- self.iter.nth(n)
- } else {
- if self.n > 0 {
- self.iter.nth(self.n - 1);
- self.n = 0;
- }
- None
- }
- }
-
- #[inline]
- fn size_hint(&self) -> (usize, Option<usize>) {
- if self.n == 0 {
- return (0, Some(0));
- }
-
- let (lower, upper) = self.iter.size_hint();
-
- let lower = cmp::min(lower, self.n);
-
- let upper = match upper {
- Some(x) if x < self.n => Some(x),
- _ => Some(self.n)
- };
-
- (lower, upper)
- }
-
- #[inline]
- fn try_fold<Acc, Fold, R>(&mut self, init: Acc, mut fold: Fold) -> R where
- Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
- {
- if self.n == 0 {
- Try::from_ok(init)
- } else {
- let n = &mut self.n;
- self.iter.try_fold(init, move |acc, x| {
- *n -= 1;
- let r = fold(acc, x);
- if *n == 0 { LoopState::Break(r) }
- else { LoopState::from_try(r) }
- }).into_try()
- }
- }
-}
-
-#[stable(feature = "rust1", since = "1.0.0")]
-impl<I> ExactSizeIterator for Take<I> where I: ExactSizeIterator {}
-
-#[stable(feature = "fused", since = "1.26.0")]
-impl<I> FusedIterator for Take<I> where I: FusedIterator {}
-
-#[unstable(feature = "trusted_len", issue = "37572")]
-unsafe impl<I: TrustedLen> TrustedLen for Take<I> {}
-
-/// An iterator to maintain state while iterating another iterator.
-///
-/// This `struct` is created by the [`scan`] method on [`Iterator`]. See its
-/// documentation for more.
-///
-/// [`scan`]: trait.Iterator.html#method.scan
-/// [`Iterator`]: trait.Iterator.html
-#[must_use = "iterators are lazy and do nothing unless consumed"]
-#[stable(feature = "rust1", since = "1.0.0")]
-#[derive(Clone)]
-pub struct Scan<I, St, F> {
- iter: I,
- f: F,
- state: St,
-}
-
-#[stable(feature = "core_impl_debug", since = "1.9.0")]
-impl<I: fmt::Debug, St: fmt::Debug, F> fmt::Debug for Scan<I, St, F> {
- fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
- f.debug_struct("Scan")
- .field("iter", &self.iter)
- .field("state", &self.state)
- .finish()
- }
-}
-
-#[stable(feature = "rust1", since = "1.0.0")]
-impl<B, I, St, F> Iterator for Scan<I, St, F> where
- I: Iterator,
- F: FnMut(&mut St, I::Item) -> Option<B>,
-{
- type Item = B;
-
- #[inline]
- fn next(&mut self) -> Option<B> {
- self.iter.next().and_then(|a| (self.f)(&mut self.state, a))
- }
-
- #[inline]
- fn size_hint(&self) -> (usize, Option<usize>) {
- let (_, upper) = self.iter.size_hint();
- (0, upper) // can't know a lower bound, due to the scan function
- }
-
- #[inline]
- fn try_fold<Acc, Fold, R>(&mut self, init: Acc, mut fold: Fold) -> R where
- Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
- {
- let state = &mut self.state;
- let f = &mut self.f;
- self.iter.try_fold(init, move |acc, x| {
- match f(state, x) {
- None => LoopState::Break(Try::from_ok(acc)),
- Some(x) => LoopState::from_try(fold(acc, x)),
- }
- }).into_try()
- }
-}
-
-/// An iterator that maps each element to an iterator, and yields the elements
-/// of the produced iterators.
-///
-/// This `struct` is created by the [`flat_map`] method on [`Iterator`]. See its
-/// documentation for more.
-///
-/// [`flat_map`]: trait.Iterator.html#method.flat_map
-/// [`Iterator`]: trait.Iterator.html
-#[must_use = "iterators are lazy and do nothing unless consumed"]
-#[stable(feature = "rust1", since = "1.0.0")]
-pub struct FlatMap<I, U: IntoIterator, F> {
- inner: FlattenCompat<Map<I, F>, <U as IntoIterator>::IntoIter>
-}
-
-#[stable(feature = "rust1", since = "1.0.0")]
-impl<I: Clone, U: Clone + IntoIterator, F: Clone> Clone for FlatMap<I, U, F>
- where <U as IntoIterator>::IntoIter: Clone
-{
- fn clone(&self) -> Self { FlatMap { inner: self.inner.clone() } }
-}
-
-#[stable(feature = "core_impl_debug", since = "1.9.0")]
-impl<I: fmt::Debug, U: IntoIterator, F> fmt::Debug for FlatMap<I, U, F>
- where U::IntoIter: fmt::Debug
-{
- fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
- f.debug_struct("FlatMap").field("inner", &self.inner).finish()
- }
-}
-
-#[stable(feature = "rust1", since = "1.0.0")]
-impl<I: Iterator, U: IntoIterator, F> Iterator for FlatMap<I, U, F>
- where F: FnMut(I::Item) -> U,
-{
- type Item = U::Item;
-
- #[inline]
- fn next(&mut self) -> Option<U::Item> { self.inner.next() }
-
- #[inline]
- fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() }
-
- #[inline]
- fn try_fold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R where
- Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
- {
- self.inner.try_fold(init, fold)
- }
-
- #[inline]
- fn fold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
- where Fold: FnMut(Acc, Self::Item) -> Acc,
- {
- self.inner.fold(init, fold)
- }
-}
-
-#[stable(feature = "rust1", since = "1.0.0")]
-impl<I: DoubleEndedIterator, U, F> DoubleEndedIterator for FlatMap<I, U, F>
- where F: FnMut(I::Item) -> U,
- U: IntoIterator,
- U::IntoIter: DoubleEndedIterator
-{
- #[inline]
- fn next_back(&mut self) -> Option<U::Item> { self.inner.next_back() }
-
- #[inline]
- fn try_rfold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R where
- Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
- {
- self.inner.try_rfold(init, fold)
- }
-
- #[inline]
- fn rfold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
- where Fold: FnMut(Acc, Self::Item) -> Acc,
- {
- self.inner.rfold(init, fold)
- }
-}
-
-#[stable(feature = "fused", since = "1.26.0")]
-impl<I, U, F> FusedIterator for FlatMap<I, U, F>
- where I: FusedIterator, U: IntoIterator, F: FnMut(I::Item) -> U {}
-
-/// An iterator that flattens one level of nesting in an iterator of things
-/// that can be turned into iterators.
-///
-/// This `struct` is created by the [`flatten`] method on [`Iterator`]. See its
-/// documentation for more.
-///
-/// [`flatten`]: trait.Iterator.html#method.flatten
-/// [`Iterator`]: trait.Iterator.html
-#[must_use = "iterators are lazy and do nothing unless consumed"]
-#[stable(feature = "iterator_flatten", since = "1.29.0")]
-pub struct Flatten<I: Iterator>
-where I::Item: IntoIterator {
- inner: FlattenCompat<I, <I::Item as IntoIterator>::IntoIter>,
-}
-
-#[stable(feature = "iterator_flatten", since = "1.29.0")]
-impl<I, U> fmt::Debug for Flatten<I>
- where I: Iterator + fmt::Debug, U: Iterator + fmt::Debug,
- I::Item: IntoIterator<IntoIter = U, Item = U::Item>,
-{
- fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
- f.debug_struct("Flatten").field("inner", &self.inner).finish()
- }
-}
-
-#[stable(feature = "iterator_flatten", since = "1.29.0")]
-impl<I, U> Clone for Flatten<I>
- where I: Iterator + Clone, U: Iterator + Clone,
- I::Item: IntoIterator<IntoIter = U, Item = U::Item>,
-{
- fn clone(&self) -> Self { Flatten { inner: self.inner.clone() } }
-}
-
-#[stable(feature = "iterator_flatten", since = "1.29.0")]
-impl<I, U> Iterator for Flatten<I>
- where I: Iterator, U: Iterator,
- I::Item: IntoIterator<IntoIter = U, Item = U::Item>
-{
- type Item = U::Item;
-
- #[inline]
- fn next(&mut self) -> Option<U::Item> { self.inner.next() }
-
- #[inline]
- fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() }
-
- #[inline]
- fn try_fold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R where
- Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
- {
- self.inner.try_fold(init, fold)
- }
-
- #[inline]
- fn fold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
- where Fold: FnMut(Acc, Self::Item) -> Acc,
- {
- self.inner.fold(init, fold)
- }
-}
-
-#[stable(feature = "iterator_flatten", since = "1.29.0")]
-impl<I, U> DoubleEndedIterator for Flatten<I>
- where I: DoubleEndedIterator, U: DoubleEndedIterator,
- I::Item: IntoIterator<IntoIter = U, Item = U::Item>
-{
- #[inline]
- fn next_back(&mut self) -> Option<U::Item> { self.inner.next_back() }
-
- #[inline]
- fn try_rfold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R where
- Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
- {
- self.inner.try_rfold(init, fold)
- }
-
- #[inline]
- fn rfold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
- where Fold: FnMut(Acc, Self::Item) -> Acc,
- {
- self.inner.rfold(init, fold)
- }
-}
-
-#[stable(feature = "iterator_flatten", since = "1.29.0")]
-impl<I, U> FusedIterator for Flatten<I>
- where I: FusedIterator, U: Iterator,
- I::Item: IntoIterator<IntoIter = U, Item = U::Item> {}
-
-/// Adapts an iterator by flattening it, for use in `flatten()` and `flat_map()`.
-fn flatten_compat<I, U>(iter: I) -> FlattenCompat<I, U> {
- FlattenCompat { iter, frontiter: None, backiter: None }
-}
-
-/// Real logic of both `Flatten` and `FlatMap` which simply delegate to
-/// this type.
-#[derive(Clone, Debug)]
-struct FlattenCompat<I, U> {
- iter: I,
- frontiter: Option<U>,
- backiter: Option<U>,
-}
-
-impl<I, U> Iterator for FlattenCompat<I, U>
- where I: Iterator, U: Iterator,
- I::Item: IntoIterator<IntoIter = U, Item = U::Item>
-{
- type Item = U::Item;
-
- #[inline]
- fn next(&mut self) -> Option<U::Item> {
- loop {
- if let Some(ref mut inner) = self.frontiter {
- if let elt@Some(_) = inner.next() { return elt }
- }
- match self.iter.next() {
- None => return self.backiter.as_mut().and_then(|it| it.next()),
- Some(inner) => self.frontiter = Some(inner.into_iter()),
- }
- }
- }
-
- #[inline]
- fn size_hint(&self) -> (usize, Option<usize>) {
- let (flo, fhi) = self.frontiter.as_ref().map_or((0, Some(0)), |it| it.size_hint());
- let (blo, bhi) = self.backiter.as_ref().map_or((0, Some(0)), |it| it.size_hint());
- let lo = flo.saturating_add(blo);
- match (self.iter.size_hint(), fhi, bhi) {
- ((0, Some(0)), Some(a), Some(b)) => (lo, a.checked_add(b)),
- _ => (lo, None)
- }
- }
-
- #[inline]
- fn try_fold<Acc, Fold, R>(&mut self, mut init: Acc, mut fold: Fold) -> R where
- Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
- {
- if let Some(ref mut front) = self.frontiter {
- init = front.try_fold(init, &mut fold)?;
- }
- self.frontiter = None;
-
- {
- let frontiter = &mut self.frontiter;
- init = self.iter.try_fold(init, |acc, x| {
- let mut mid = x.into_iter();
- let r = mid.try_fold(acc, &mut fold);
- *frontiter = Some(mid);
- r
- })?;
- }
- self.frontiter = None;
-
- if let Some(ref mut back) = self.backiter {
- init = back.try_fold(init, &mut fold)?;
- }
- self.backiter = None;
-
- Try::from_ok(init)
- }
-
- #[inline]
- fn fold<Acc, Fold>(self, init: Acc, mut fold: Fold) -> Acc
- where Fold: FnMut(Acc, Self::Item) -> Acc,
- {
- self.frontiter.into_iter()
- .chain(self.iter.map(IntoIterator::into_iter))
- .chain(self.backiter)
- .fold(init, |acc, iter| iter.fold(acc, &mut fold))
- }
-}
-
-impl<I, U> DoubleEndedIterator for FlattenCompat<I, U>
- where I: DoubleEndedIterator, U: DoubleEndedIterator,
- I::Item: IntoIterator<IntoIter = U, Item = U::Item>
-{
- #[inline]
- fn next_back(&mut self) -> Option<U::Item> {
- loop {
- if let Some(ref mut inner) = self.backiter {
- if let elt@Some(_) = inner.next_back() { return elt }
- }
- match self.iter.next_back() {
- None => return self.frontiter.as_mut().and_then(|it| it.next_back()),
- next => self.backiter = next.map(IntoIterator::into_iter),
- }
- }
- }
-
- #[inline]
- fn try_rfold<Acc, Fold, R>(&mut self, mut init: Acc, mut fold: Fold) -> R where
- Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
- {
- if let Some(ref mut back) = self.backiter {
- init = back.try_rfold(init, &mut fold)?;
- }
- self.backiter = None;
-
- {
- let backiter = &mut self.backiter;
- init = self.iter.try_rfold(init, |acc, x| {
- let mut mid = x.into_iter();
- let r = mid.try_rfold(acc, &mut fold);
- *backiter = Some(mid);
- r
- })?;
- }
- self.backiter = None;
-
- if let Some(ref mut front) = self.frontiter {
- init = front.try_rfold(init, &mut fold)?;
- }
- self.frontiter = None;
-
- Try::from_ok(init)
- }
-
- #[inline]
- fn rfold<Acc, Fold>(self, init: Acc, mut fold: Fold) -> Acc
- where Fold: FnMut(Acc, Self::Item) -> Acc,
- {
- self.frontiter.into_iter()
- .chain(self.iter.map(IntoIterator::into_iter))
- .chain(self.backiter)
- .rfold(init, |acc, iter| iter.rfold(acc, &mut fold))
- }
-}
-
-/// An iterator that yields `None` forever after the underlying iterator
-/// yields `None` once.
-///
-/// This `struct` is created by the [`fuse`] method on [`Iterator`]. See its
-/// documentation for more.
-///
-/// [`fuse`]: trait.Iterator.html#method.fuse
-/// [`Iterator`]: trait.Iterator.html
-#[derive(Clone, Debug)]
-#[must_use = "iterators are lazy and do nothing unless consumed"]
-#[stable(feature = "rust1", since = "1.0.0")]
-pub struct Fuse<I> {
- iter: I,
- done: bool
-}
-
-#[stable(feature = "fused", since = "1.26.0")]
-impl<I> FusedIterator for Fuse<I> where I: Iterator {}
-
-#[stable(feature = "rust1", since = "1.0.0")]
-impl<I> Iterator for Fuse<I> where I: Iterator {
- type Item = <I as Iterator>::Item;
-
- #[inline]
- default fn next(&mut self) -> Option<<I as Iterator>::Item> {
- if self.done {
- None
- } else {
- let next = self.iter.next();
- self.done = next.is_none();
- next
- }
- }
-
- #[inline]
- default fn nth(&mut self, n: usize) -> Option<I::Item> {
- if self.done {
- None
- } else {
- let nth = self.iter.nth(n);
- self.done = nth.is_none();
- nth
- }
- }
-
- #[inline]
- default fn last(self) -> Option<I::Item> {
- if self.done {
- None
- } else {
- self.iter.last()
- }
- }
-
- #[inline]
- default fn count(self) -> usize {
- if self.done {
- 0
- } else {
- self.iter.count()
- }
- }
-
- #[inline]
- default fn size_hint(&self) -> (usize, Option<usize>) {
- if self.done {
- (0, Some(0))
- } else {
- self.iter.size_hint()
- }
- }
-
- #[inline]
- default fn try_fold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R where
- Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
- {
- if self.done {
- Try::from_ok(init)
- } else {
- let acc = self.iter.try_fold(init, fold)?;
- self.done = true;
- Try::from_ok(acc)
- }
- }
-
- #[inline]
- default fn fold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
- where Fold: FnMut(Acc, Self::Item) -> Acc,
- {
- if self.done {
- init
- } else {
- self.iter.fold(init, fold)
- }
- }
-}
-
-#[stable(feature = "rust1", since = "1.0.0")]
-impl<I> DoubleEndedIterator for Fuse<I> where I: DoubleEndedIterator {
- #[inline]
- default fn next_back(&mut self) -> Option<<I as Iterator>::Item> {
- if self.done {
- None
- } else {
- let next = self.iter.next_back();
- self.done = next.is_none();
- next
- }
- }
-
- #[inline]
- default fn try_rfold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R where
- Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
- {
- if self.done {
- Try::from_ok(init)
- } else {
- let acc = self.iter.try_rfold(init, fold)?;
- self.done = true;
- Try::from_ok(acc)
- }
- }
-
- #[inline]
- default fn rfold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
- where Fold: FnMut(Acc, Self::Item) -> Acc,
- {
- if self.done {
- init
- } else {
- self.iter.rfold(init, fold)
- }
- }
-}
-
-unsafe impl<I> TrustedRandomAccess for Fuse<I>
- where I: TrustedRandomAccess,
-{
- unsafe fn get_unchecked(&mut self, i: usize) -> I::Item {
- self.iter.get_unchecked(i)
- }
-
- fn may_have_side_effect() -> bool {
- I::may_have_side_effect()
- }
-}
-
-#[stable(feature = "fused", since = "1.26.0")]
-impl<I> Iterator for Fuse<I> where I: FusedIterator {
- #[inline]
- fn next(&mut self) -> Option<<I as Iterator>::Item> {
- self.iter.next()
- }
-
- #[inline]
- fn nth(&mut self, n: usize) -> Option<I::Item> {
- self.iter.nth(n)
- }
-
- #[inline]
- fn last(self) -> Option<I::Item> {
- self.iter.last()
- }
-
- #[inline]
- fn count(self) -> usize {
- self.iter.count()
- }
-
- #[inline]
- fn size_hint(&self) -> (usize, Option<usize>) {
- self.iter.size_hint()
- }
-
- #[inline]
- fn try_fold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R where
- Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
- {
- self.iter.try_fold(init, fold)
- }
-
- #[inline]
- fn fold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
- where Fold: FnMut(Acc, Self::Item) -> Acc,
- {
- self.iter.fold(init, fold)
- }
-}
-
-#[stable(feature = "fused", since = "1.26.0")]
-impl<I> DoubleEndedIterator for Fuse<I>
- where I: DoubleEndedIterator + FusedIterator
-{
- #[inline]
- fn next_back(&mut self) -> Option<<I as Iterator>::Item> {
- self.iter.next_back()
- }
-
- #[inline]
- fn try_rfold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R where
- Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
- {
- self.iter.try_rfold(init, fold)
- }
-
- #[inline]
- fn rfold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
- where Fold: FnMut(Acc, Self::Item) -> Acc,
- {
- self.iter.rfold(init, fold)
- }
-}
-
-
-#[stable(feature = "rust1", since = "1.0.0")]
-impl<I> ExactSizeIterator for Fuse<I> where I: ExactSizeIterator {
- fn len(&self) -> usize {
- self.iter.len()
- }
-
- fn is_empty(&self) -> bool {
- self.iter.is_empty()
- }
-}
-
-/// An iterator that calls a function with a reference to each element before
-/// yielding it.
-///
-/// This `struct` is created by the [`inspect`] method on [`Iterator`]. See its
-/// documentation for more.
-///
-/// [`inspect`]: trait.Iterator.html#method.inspect
-/// [`Iterator`]: trait.Iterator.html
-#[must_use = "iterators are lazy and do nothing unless consumed"]
-#[stable(feature = "rust1", since = "1.0.0")]
-#[derive(Clone)]
-pub struct Inspect<I, F> {
- iter: I,
- f: F,
-}
-
-#[stable(feature = "core_impl_debug", since = "1.9.0")]
-impl<I: fmt::Debug, F> fmt::Debug for Inspect<I, F> {
- fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
- f.debug_struct("Inspect")
- .field("iter", &self.iter)
- .finish()
- }
-}
-
-impl<I: Iterator, F> Inspect<I, F> where F: FnMut(&I::Item) {
- #[inline]
- fn do_inspect(&mut self, elt: Option<I::Item>) -> Option<I::Item> {
- if let Some(ref a) = elt {
- (self.f)(a);
- }
-
- elt
- }
-}
-
-#[stable(feature = "rust1", since = "1.0.0")]
-impl<I: Iterator, F> Iterator for Inspect<I, F> where F: FnMut(&I::Item) {
- type Item = I::Item;
-
- #[inline]
- fn next(&mut self) -> Option<I::Item> {
- let next = self.iter.next();
- self.do_inspect(next)
- }
-
- #[inline]
- fn size_hint(&self) -> (usize, Option<usize>) {
- self.iter.size_hint()
- }
-
- #[inline]
- fn try_fold<Acc, Fold, R>(&mut self, init: Acc, mut fold: Fold) -> R where
- Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
- {
- let f = &mut self.f;
- self.iter.try_fold(init, move |acc, item| { f(&item); fold(acc, item) })
- }
-
- #[inline]
- fn fold<Acc, Fold>(self, init: Acc, mut fold: Fold) -> Acc
- where Fold: FnMut(Acc, Self::Item) -> Acc,
- {
- let mut f = self.f;
- self.iter.fold(init, move |acc, item| { f(&item); fold(acc, item) })
- }
-}
-
-#[stable(feature = "rust1", since = "1.0.0")]
-impl<I: DoubleEndedIterator, F> DoubleEndedIterator for Inspect<I, F>
- where F: FnMut(&I::Item),
-{
- #[inline]
- fn next_back(&mut self) -> Option<I::Item> {
- let next = self.iter.next_back();
- self.do_inspect(next)
- }
-
- #[inline]
- fn try_rfold<Acc, Fold, R>(&mut self, init: Acc, mut fold: Fold) -> R where
- Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
- {
- let f = &mut self.f;
- self.iter.try_rfold(init, move |acc, item| { f(&item); fold(acc, item) })
- }
-
- #[inline]
- fn rfold<Acc, Fold>(self, init: Acc, mut fold: Fold) -> Acc
- where Fold: FnMut(Acc, Self::Item) -> Acc,
- {
- let mut f = self.f;
- self.iter.rfold(init, move |acc, item| { f(&item); fold(acc, item) })
- }
-}
-
-#[stable(feature = "rust1", since = "1.0.0")]
-impl<I: ExactSizeIterator, F> ExactSizeIterator for Inspect<I, F>
- where F: FnMut(&I::Item)
-{
- fn len(&self) -> usize {
- self.iter.len()
- }
-
- fn is_empty(&self) -> bool {
- self.iter.is_empty()
- }
-}
-
-#[stable(feature = "fused", since = "1.26.0")]
-impl<I: FusedIterator, F> FusedIterator for Inspect<I, F>
- where F: FnMut(&I::Item) {}
projects / rustc.git / blobdiff