From 773b73c66c653f66ae056cecf9798de0686ef4ad Mon Sep 17 00:00:00 2001 From: Waffle Date: Thu, 8 Oct 2020 00:14:11 +0300 Subject: [PATCH] Split iterator adaptors into individual modules This commit also makes fields of `Take` private. I have no idea why they were `pub(super)` before. --- library/core/src/iter/adapters/cloned.rs | 142 + library/core/src/iter/adapters/copied.rs | 158 + library/core/src/iter/adapters/cycle.rs | 87 + library/core/src/iter/adapters/enumerate.rs | 242 ++ library/core/src/iter/adapters/filter.rs | 154 + library/core/src/iter/adapters/filter_map.rs | 153 + library/core/src/iter/adapters/flatten.rs | 3 +- library/core/src/iter/adapters/fuse.rs | 15 +- library/core/src/iter/adapters/inspect.rs | 169 ++ library/core/src/iter/adapters/map.rs | 217 ++ library/core/src/iter/adapters/map_while.rs | 103 + library/core/src/iter/adapters/mod.rs | 2873 +----------------- library/core/src/iter/adapters/peekable.rs | 303 ++ library/core/src/iter/adapters/rev.rs | 139 + library/core/src/iter/adapters/scan.rs | 113 + library/core/src/iter/adapters/skip.rs | 201 ++ library/core/src/iter/adapters/skip_while.rs | 128 + library/core/src/iter/adapters/step_by.rs | 235 ++ library/core/src/iter/adapters/take.rs | 211 ++ library/core/src/iter/adapters/take_while.rs | 141 + library/core/src/iter/adapters/zip.rs | 15 +- 21 files changed, 2969 insertions(+), 2833 deletions(-) create mode 100644 library/core/src/iter/adapters/cloned.rs create mode 100644 library/core/src/iter/adapters/copied.rs create mode 100644 library/core/src/iter/adapters/cycle.rs create mode 100644 library/core/src/iter/adapters/enumerate.rs create mode 100644 library/core/src/iter/adapters/filter.rs create mode 100644 library/core/src/iter/adapters/filter_map.rs create mode 100644 library/core/src/iter/adapters/inspect.rs create mode 100644 library/core/src/iter/adapters/map.rs create mode 100644 library/core/src/iter/adapters/map_while.rs create mode 100644 library/core/src/iter/adapters/peekable.rs create mode 100644 library/core/src/iter/adapters/rev.rs create mode 100644 library/core/src/iter/adapters/scan.rs create mode 100644 library/core/src/iter/adapters/skip.rs create mode 100644 library/core/src/iter/adapters/skip_while.rs create mode 100644 library/core/src/iter/adapters/step_by.rs create mode 100644 library/core/src/iter/adapters/take.rs create mode 100644 library/core/src/iter/adapters/take_while.rs diff --git a/library/core/src/iter/adapters/cloned.rs b/library/core/src/iter/adapters/cloned.rs new file mode 100644 index 00000000000..da523c83656 --- /dev/null +++ b/library/core/src/iter/adapters/cloned.rs @@ -0,0 +1,142 @@ +use crate::{ + iter::{ + adapters::zip::try_get_unchecked, adapters::TrustedRandomAccess, FusedIterator, TrustedLen, + }, + ops::Try, +}; + +/// 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`]: Iterator::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 { + it: I, +} + +impl Cloned { + pub(in crate::iter) fn new(it: I) -> Cloned { + Cloned { it } + } +} + +fn clone_try_fold(mut f: impl FnMut(Acc, T) -> R) -> impl FnMut(Acc, &T) -> R { + move |acc, elt| f(acc, elt.clone()) +} + +#[stable(feature = "iter_cloned", since = "1.1.0")] +impl<'a, I, T: 'a> Iterator for Cloned +where + I: Iterator, + T: Clone, +{ + type Item = T; + + fn next(&mut self) -> Option { + self.it.next().cloned() + } + + fn size_hint(&self) -> (usize, Option) { + self.it.size_hint() + } + + fn try_fold(&mut self, init: B, f: F) -> R + where + Self: Sized, + F: FnMut(B, Self::Item) -> R, + R: Try, + { + self.it.try_fold(init, clone_try_fold(f)) + } + + fn fold(self, init: Acc, f: F) -> Acc + where + F: FnMut(Acc, Self::Item) -> Acc, + { + self.it.map(T::clone).fold(init, f) + } + + unsafe fn __iterator_get_unchecked(&mut self, idx: usize) -> T + where + Self: TrustedRandomAccess, + { + // SAFETY: the caller must uphold the contract for + // `Iterator::__iterator_get_unchecked`. + unsafe { try_get_unchecked(&mut self.it, idx).clone() } + } +} + +#[stable(feature = "iter_cloned", since = "1.1.0")] +impl<'a, I, T: 'a> DoubleEndedIterator for Cloned +where + I: DoubleEndedIterator, + T: Clone, +{ + fn next_back(&mut self) -> Option { + self.it.next_back().cloned() + } + + fn try_rfold(&mut self, init: B, f: F) -> R + where + Self: Sized, + F: FnMut(B, Self::Item) -> R, + R: Try, + { + self.it.try_rfold(init, clone_try_fold(f)) + } + + fn rfold(self, init: Acc, f: F) -> Acc + where + F: FnMut(Acc, Self::Item) -> Acc, + { + self.it.map(T::clone).rfold(init, f) + } +} + +#[stable(feature = "iter_cloned", since = "1.1.0")] +impl<'a, I, T: 'a> ExactSizeIterator for Cloned +where + I: ExactSizeIterator, + 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 +where + I: FusedIterator, + T: Clone, +{ +} + +#[doc(hidden)] +#[unstable(feature = "trusted_random_access", issue = "none")] +unsafe impl TrustedRandomAccess for Cloned +where + I: TrustedRandomAccess, +{ + #[inline] + fn may_have_side_effect() -> bool { + true + } +} + +#[unstable(feature = "trusted_len", issue = "37572")] +unsafe impl<'a, I, T: 'a> TrustedLen for Cloned +where + I: TrustedLen, + T: Clone, +{ +} diff --git a/library/core/src/iter/adapters/copied.rs b/library/core/src/iter/adapters/copied.rs new file mode 100644 index 00000000000..98e231498c9 --- /dev/null +++ b/library/core/src/iter/adapters/copied.rs @@ -0,0 +1,158 @@ +use crate::{ + iter::{ + adapters::zip::try_get_unchecked, adapters::TrustedRandomAccess, FusedIterator, TrustedLen, + }, + ops::Try, +}; + +/// 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`]: Iterator::copied +/// [`Iterator`]: trait.Iterator.html +#[stable(feature = "iter_copied", since = "1.36.0")] +#[must_use = "iterators are lazy and do nothing unless consumed"] +#[derive(Clone, Debug)] +pub struct Copied { + it: I, +} + +impl Copied { + pub(in crate::iter) fn new(it: I) -> Copied { + Copied { it } + } +} + +fn copy_fold(mut f: impl FnMut(Acc, T) -> Acc) -> impl FnMut(Acc, &T) -> Acc { + move |acc, &elt| f(acc, elt) +} + +fn copy_try_fold(mut f: impl FnMut(Acc, T) -> R) -> impl FnMut(Acc, &T) -> R { + move |acc, &elt| f(acc, elt) +} + +#[stable(feature = "iter_copied", since = "1.36.0")] +impl<'a, I, T: 'a> Iterator for Copied +where + I: Iterator, + T: Copy, +{ + type Item = T; + + fn next(&mut self) -> Option { + self.it.next().copied() + } + + fn size_hint(&self) -> (usize, Option) { + self.it.size_hint() + } + + fn try_fold(&mut self, init: B, f: F) -> R + where + Self: Sized, + F: FnMut(B, Self::Item) -> R, + R: Try, + { + self.it.try_fold(init, copy_try_fold(f)) + } + + fn fold(self, init: Acc, f: F) -> Acc + where + F: FnMut(Acc, Self::Item) -> Acc, + { + self.it.fold(init, copy_fold(f)) + } + + fn nth(&mut self, n: usize) -> Option { + self.it.nth(n).copied() + } + + fn last(self) -> Option { + self.it.last().copied() + } + + fn count(self) -> usize { + self.it.count() + } + + unsafe fn __iterator_get_unchecked(&mut self, idx: usize) -> T + where + Self: TrustedRandomAccess, + { + // SAFETY: the caller must uphold the contract for + // `Iterator::__iterator_get_unchecked`. + *unsafe { try_get_unchecked(&mut self.it, idx) } + } +} + +#[stable(feature = "iter_copied", since = "1.36.0")] +impl<'a, I, T: 'a> DoubleEndedIterator for Copied +where + I: DoubleEndedIterator, + T: Copy, +{ + fn next_back(&mut self) -> Option { + self.it.next_back().copied() + } + + fn try_rfold(&mut self, init: B, f: F) -> R + where + Self: Sized, + F: FnMut(B, Self::Item) -> R, + R: Try, + { + self.it.try_rfold(init, copy_try_fold(f)) + } + + fn rfold(self, init: Acc, f: F) -> Acc + where + F: FnMut(Acc, Self::Item) -> Acc, + { + self.it.rfold(init, copy_fold(f)) + } +} + +#[stable(feature = "iter_copied", since = "1.36.0")] +impl<'a, I, T: 'a> ExactSizeIterator for Copied +where + I: ExactSizeIterator, + T: Copy, +{ + fn len(&self) -> usize { + self.it.len() + } + + fn is_empty(&self) -> bool { + self.it.is_empty() + } +} + +#[stable(feature = "iter_copied", since = "1.36.0")] +impl<'a, I, T: 'a> FusedIterator for Copied +where + I: FusedIterator, + T: Copy, +{ +} + +#[doc(hidden)] +#[unstable(feature = "trusted_random_access", issue = "none")] +unsafe impl TrustedRandomAccess for Copied +where + I: TrustedRandomAccess, +{ + #[inline] + fn may_have_side_effect() -> bool { + I::may_have_side_effect() + } +} + +#[stable(feature = "iter_copied", since = "1.36.0")] +unsafe impl<'a, I, T: 'a> TrustedLen for Copied +where + I: TrustedLen, + T: Copy, +{ +} diff --git a/library/core/src/iter/adapters/cycle.rs b/library/core/src/iter/adapters/cycle.rs new file mode 100644 index 00000000000..6e9a011f819 --- /dev/null +++ b/library/core/src/iter/adapters/cycle.rs @@ -0,0 +1,87 @@ +use crate::{iter::FusedIterator, ops::Try}; + +/// An iterator that repeats endlessly. +/// +/// This `struct` is created by the [`cycle`] method on [`Iterator`]. See its +/// documentation for more. +/// +/// [`cycle`]: Iterator::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 { + orig: I, + iter: I, +} + +impl Cycle { + pub(in crate::iter) fn new(iter: I) -> Cycle { + Cycle { orig: iter.clone(), iter } + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl Iterator for Cycle +where + I: Clone + Iterator, +{ + type Item = ::Item; + + #[inline] + fn next(&mut self) -> Option<::Item> { + match self.iter.next() { + None => { + self.iter = self.orig.clone(); + self.iter.next() + } + y => y, + } + } + + #[inline] + fn size_hint(&self) -> (usize, Option) { + // the cycle iterator is either empty or infinite + match self.orig.size_hint() { + sz @ (0, Some(0)) => sz, + (0, _) => (0, None), + _ => (usize::MAX, None), + } + } + + #[inline] + fn try_fold(&mut self, mut acc: Acc, mut f: F) -> R + where + F: FnMut(Acc, Self::Item) -> R, + R: Try, + { + // fully iterate the current iterator. this is necessary because + // `self.iter` may be empty even when `self.orig` isn't + acc = self.iter.try_fold(acc, &mut f)?; + self.iter = self.orig.clone(); + + // complete a full cycle, keeping track of whether the cycled + // iterator is empty or not. we need to return early in case + // of an empty iterator to prevent an infinite loop + let mut is_empty = true; + acc = self.iter.try_fold(acc, |acc, x| { + is_empty = false; + f(acc, x) + })?; + + if is_empty { + return try { acc }; + } + + loop { + self.iter = self.orig.clone(); + acc = self.iter.try_fold(acc, &mut f)?; + } + } + + // No `fold` override, because `fold` doesn't make much sense for `Cycle`, + // and we can't do anything better than the default. +} + +#[stable(feature = "fused", since = "1.26.0")] +impl FusedIterator for Cycle where I: Clone + Iterator {} diff --git a/library/core/src/iter/adapters/enumerate.rs b/library/core/src/iter/adapters/enumerate.rs new file mode 100644 index 00000000000..c42028ddeed --- /dev/null +++ b/library/core/src/iter/adapters/enumerate.rs @@ -0,0 +1,242 @@ +use crate::{ + iter::{ + adapters::{zip::try_get_unchecked, SourceIter, TrustedRandomAccess}, + FusedIterator, InPlaceIterable, TrustedLen, + }, + ops::{Add, AddAssign, Try}, +}; + +/// 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`]: Iterator::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 { + iter: I, + count: usize, +} +impl Enumerate { + pub(in crate::iter) fn new(iter: I) -> Enumerate { + Enumerate { iter, count: 0 } + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl Iterator for Enumerate +where + I: Iterator, +{ + type Item = (usize, ::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] + fn next(&mut self) -> Option<(usize, ::Item)> { + let a = self.iter.next()?; + let i = self.count; + // Possible undefined overflow. + AddAssign::add_assign(&mut self.count, 1); + Some((i, a)) + } + + #[inline] + fn size_hint(&self) -> (usize, Option) { + self.iter.size_hint() + } + + #[inline] + fn nth(&mut self, n: usize) -> Option<(usize, I::Item)> { + let a = self.iter.nth(n)?; + // Possible undefined overflow. + let i = Add::add(self.count, n); + self.count = Add::add(i, 1); + Some((i, a)) + } + + #[inline] + fn count(self) -> usize { + self.iter.count() + } + + #[inline] + fn try_fold(&mut self, init: Acc, fold: Fold) -> R + where + Self: Sized, + Fold: FnMut(Acc, Self::Item) -> R, + R: Try, + { + #[inline] + fn enumerate<'a, T, Acc, R>( + count: &'a mut usize, + mut fold: impl FnMut(Acc, (usize, T)) -> R + 'a, + ) -> impl FnMut(Acc, T) -> R + 'a { + move |acc, item| { + let acc = fold(acc, (*count, item)); + // Possible undefined overflow. + AddAssign::add_assign(count, 1); + acc + } + } + + self.iter.try_fold(init, enumerate(&mut self.count, fold)) + } + + #[inline] + fn fold(self, init: Acc, fold: Fold) -> Acc + where + Fold: FnMut(Acc, Self::Item) -> Acc, + { + #[inline] + fn enumerate( + mut count: usize, + mut fold: impl FnMut(Acc, (usize, T)) -> Acc, + ) -> impl FnMut(Acc, T) -> Acc { + move |acc, item| { + let acc = fold(acc, (count, item)); + // Possible undefined overflow. + AddAssign::add_assign(&mut count, 1); + acc + } + } + + self.iter.fold(init, enumerate(self.count, fold)) + } + + unsafe fn __iterator_get_unchecked(&mut self, idx: usize) -> ::Item + where + Self: TrustedRandomAccess, + { + // SAFETY: the caller must uphold the contract for + // `Iterator::__iterator_get_unchecked`. + let value = unsafe { try_get_unchecked(&mut self.iter, idx) }; + (Add::add(self.count, idx), value) + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl DoubleEndedIterator for Enumerate +where + I: ExactSizeIterator + DoubleEndedIterator, +{ + #[inline] + fn next_back(&mut self) -> Option<(usize, ::Item)> { + let a = self.iter.next_back()?; + let len = self.iter.len(); + // Can safely add, `ExactSizeIterator` promises that the number of + // elements fits into a `usize`. + Some((self.count + len, a)) + } + + #[inline] + fn nth_back(&mut self, n: usize) -> Option<(usize, ::Item)> { + let a = self.iter.nth_back(n)?; + let len = self.iter.len(); + // Can safely add, `ExactSizeIterator` promises that the number of + // elements fits into a `usize`. + Some((self.count + len, a)) + } + + #[inline] + fn try_rfold(&mut self, init: Acc, fold: Fold) -> R + where + Self: Sized, + Fold: FnMut(Acc, Self::Item) -> R, + R: Try, + { + // Can safely add and subtract the count, as `ExactSizeIterator` promises + // that the number of elements fits into a `usize`. + fn enumerate( + mut count: usize, + mut fold: impl FnMut(Acc, (usize, T)) -> R, + ) -> impl FnMut(Acc, T) -> R { + move |acc, item| { + count -= 1; + fold(acc, (count, item)) + } + } + + let count = self.count + self.iter.len(); + self.iter.try_rfold(init, enumerate(count, fold)) + } + + #[inline] + fn rfold(self, init: Acc, 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`. + fn enumerate( + mut count: usize, + mut fold: impl FnMut(Acc, (usize, T)) -> Acc, + ) -> impl FnMut(Acc, T) -> Acc { + move |acc, item| { + count -= 1; + fold(acc, (count, item)) + } + } + + let count = self.count + self.iter.len(); + self.iter.rfold(init, enumerate(count, fold)) + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl ExactSizeIterator for Enumerate +where + I: ExactSizeIterator, +{ + fn len(&self) -> usize { + self.iter.len() + } + + fn is_empty(&self) -> bool { + self.iter.is_empty() + } +} + +#[doc(hidden)] +#[unstable(feature = "trusted_random_access", issue = "none")] +unsafe impl TrustedRandomAccess for Enumerate +where + I: TrustedRandomAccess, +{ + fn may_have_side_effect() -> bool { + I::may_have_side_effect() + } +} + +#[stable(feature = "fused", since = "1.26.0")] +impl FusedIterator for Enumerate where I: FusedIterator {} + +#[unstable(feature = "trusted_len", issue = "37572")] +unsafe impl TrustedLen for Enumerate where I: TrustedLen {} + +#[unstable(issue = "none", feature = "inplace_iteration")] +unsafe impl SourceIter for Enumerate +where + I: SourceIter, +{ + type Source = S; + + #[inline] + unsafe fn as_inner(&mut self) -> &mut S { + // SAFETY: unsafe function forwarding to unsafe function with the same requirements + unsafe { SourceIter::as_inner(&mut self.iter) } + } +} + +#[unstable(issue = "none", feature = "inplace_iteration")] +unsafe impl InPlaceIterable for Enumerate {} diff --git a/library/core/src/iter/adapters/filter.rs b/library/core/src/iter/adapters/filter.rs new file mode 100644 index 00000000000..4de520eaca3 --- /dev/null +++ b/library/core/src/iter/adapters/filter.rs @@ -0,0 +1,154 @@ +use crate::{ + fmt, + iter::{adapters::SourceIter, FusedIterator, InPlaceIterable}, + ops::Try, +}; + +/// 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`]: Iterator::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 { + iter: I, + predicate: P, +} +impl Filter { + pub(in crate::iter) fn new(iter: I, predicate: P) -> Filter { + Filter { iter, predicate } + } +} + +#[stable(feature = "core_impl_debug", since = "1.9.0")] +impl fmt::Debug for Filter { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + f.debug_struct("Filter").field("iter", &self.iter).finish() + } +} + +fn filter_fold( + mut predicate: impl FnMut(&T) -> bool, + mut fold: impl FnMut(Acc, T) -> Acc, +) -> impl FnMut(Acc, T) -> Acc { + move |acc, item| if predicate(&item) { fold(acc, item) } else { acc } +} + +fn filter_try_fold<'a, T, Acc, R: Try>( + predicate: &'a mut impl FnMut(&T) -> bool, + mut fold: impl FnMut(Acc, T) -> R + 'a, +) -> impl FnMut(Acc, T) -> R + 'a { + move |acc, item| if predicate(&item) { fold(acc, item) } else { try { acc } } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl Iterator for Filter +where + P: FnMut(&I::Item) -> bool, +{ + type Item = I::Item; + + #[inline] + fn next(&mut self) -> Option { + self.iter.find(&mut self.predicate) + } + + #[inline] + fn size_hint(&self) -> (usize, Option) { + 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(self) -> usize { + #[inline] + fn to_usize(mut predicate: impl FnMut(&T) -> bool) -> impl FnMut(T) -> usize { + move |x| predicate(&x) as usize + } + + self.iter.map(to_usize(self.predicate)).sum() + } + + #[inline] + fn try_fold(&mut self, init: Acc, fold: Fold) -> R + where + Self: Sized, + Fold: FnMut(Acc, Self::Item) -> R, + R: Try, + { + self.iter.try_fold(init, filter_try_fold(&mut self.predicate, fold)) + } + + #[inline] + fn fold(self, init: Acc, fold: Fold) -> Acc + where + Fold: FnMut(Acc, Self::Item) -> Acc, + { + self.iter.fold(init, filter_fold(self.predicate, fold)) + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl DoubleEndedIterator for Filter +where + P: FnMut(&I::Item) -> bool, +{ + #[inline] + fn next_back(&mut self) -> Option { + self.iter.rfind(&mut self.predicate) + } + + #[inline] + fn try_rfold(&mut self, init: Acc, fold: Fold) -> R + where + Self: Sized, + Fold: FnMut(Acc, Self::Item) -> R, + R: Try, + { + self.iter.try_rfold(init, filter_try_fold(&mut self.predicate, fold)) + } + + #[inline] + fn rfold(self, init: Acc, fold: Fold) -> Acc + where + Fold: FnMut(Acc, Self::Item) -> Acc, + { + self.iter.rfold(init, filter_fold(self.predicate, fold)) + } +} + +#[stable(feature = "fused", since = "1.26.0")] +impl FusedIterator for Filter where P: FnMut(&I::Item) -> bool {} + +#[unstable(issue = "none", feature = "inplace_iteration")] +unsafe impl SourceIter for Filter +where + P: FnMut(&I::Item) -> bool, + I: SourceIter, +{ + type Source = S; + + #[inline] + unsafe fn as_inner(&mut self) -> &mut S { + // SAFETY: unsafe function forwarding to unsafe function with the same requirements + unsafe { SourceIter::as_inner(&mut self.iter) } + } +} + +#[unstable(issue = "none", feature = "inplace_iteration")] +unsafe impl InPlaceIterable for Filter where P: FnMut(&I::Item) -> bool {} diff --git a/library/core/src/iter/adapters/filter_map.rs b/library/core/src/iter/adapters/filter_map.rs new file mode 100644 index 00000000000..c7c63db3cdc --- /dev/null +++ b/library/core/src/iter/adapters/filter_map.rs @@ -0,0 +1,153 @@ +use crate::{ + fmt, + iter::{adapters::SourceIter, FusedIterator, InPlaceIterable}, + ops::ControlFlow, + ops::Try, +}; + +/// 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`]: Iterator::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 { + iter: I, + f: F, +} +impl FilterMap { + pub(in crate::iter) fn new(iter: I, f: F) -> FilterMap { + FilterMap { iter, f } + } +} + +#[stable(feature = "core_impl_debug", since = "1.9.0")] +impl fmt::Debug for FilterMap { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + f.debug_struct("FilterMap").field("iter", &self.iter).finish() + } +} + +fn filter_map_fold( + mut f: impl FnMut(T) -> Option, + mut fold: impl FnMut(Acc, B) -> Acc, +) -> impl FnMut(Acc, T) -> Acc { + move |acc, item| match f(item) { + Some(x) => fold(acc, x), + None => acc, + } +} + +fn filter_map_try_fold<'a, T, B, Acc, R: Try>( + f: &'a mut impl FnMut(T) -> Option, + mut fold: impl FnMut(Acc, B) -> R + 'a, +) -> impl FnMut(Acc, T) -> R + 'a { + move |acc, item| match f(item) { + Some(x) => fold(acc, x), + None => try { acc }, + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl Iterator for FilterMap +where + F: FnMut(I::Item) -> Option, +{ + type Item = B; + + #[inline] + fn next(&mut self) -> Option { + self.iter.find_map(&mut self.f) + } + + #[inline] + fn size_hint(&self) -> (usize, Option) { + let (_, upper) = self.iter.size_hint(); + (0, upper) // can't know a lower bound, due to the predicate + } + + #[inline] + fn try_fold(&mut self, init: Acc, fold: Fold) -> R + where + Self: Sized, + Fold: FnMut(Acc, Self::Item) -> R, + R: Try, + { + self.iter.try_fold(init, filter_map_try_fold(&mut self.f, fold)) + } + + #[inline] + fn fold(self, init: Acc, fold: Fold) -> Acc + where + Fold: FnMut(Acc, Self::Item) -> Acc, + { + self.iter.fold(init, filter_map_fold(self.f, fold)) + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl DoubleEndedIterator for FilterMap +where + F: FnMut(I::Item) -> Option, +{ + #[inline] + fn next_back(&mut self) -> Option { + #[inline] + fn find( + f: &mut impl FnMut(T) -> Option, + ) -> impl FnMut((), T) -> ControlFlow + '_ { + move |(), x| match f(x) { + Some(x) => ControlFlow::Break(x), + None => ControlFlow::CONTINUE, + } + } + + self.iter.try_rfold((), find(&mut self.f)).break_value() + } + + #[inline] + fn try_rfold(&mut self, init: Acc, fold: Fold) -> R + where + Self: Sized, + Fold: FnMut(Acc, Self::Item) -> R, + R: Try, + { + self.iter.try_rfold(init, filter_map_try_fold(&mut self.f, fold)) + } + + #[inline] + fn rfold(self, init: Acc, fold: Fold) -> Acc + where + Fold: FnMut(Acc, Self::Item) -> Acc, + { + self.iter.rfold(init, filter_map_fold(self.f, fold)) + } +} + +#[stable(feature = "fused", since = "1.26.0")] +impl FusedIterator for FilterMap where F: FnMut(I::Item) -> Option {} + +#[unstable(issue = "none", feature = "inplace_iteration")] +unsafe impl SourceIter for FilterMap +where + F: FnMut(I::Item) -> Option, + I: SourceIter, +{ + type Source = S; + + #[inline] + unsafe fn as_inner(&mut self) -> &mut S { + // SAFETY: unsafe function forwarding to unsafe function with the same requirements + unsafe { SourceIter::as_inner(&mut self.iter) } + } +} + +#[unstable(issue = "none", feature = "inplace_iteration")] +unsafe impl InPlaceIterable for FilterMap where + F: FnMut(I::Item) -> Option +{ +} diff --git a/library/core/src/iter/adapters/flatten.rs b/library/core/src/iter/adapters/flatten.rs index 96d0a60a327..60e5ea8054e 100644 --- a/library/core/src/iter/adapters/flatten.rs +++ b/library/core/src/iter/adapters/flatten.rs @@ -14,8 +14,9 @@ pub struct FlatMap { inner: FlattenCompat, ::IntoIter>, } + impl U> FlatMap { - pub(in super::super) fn new(iter: I, f: F) -> FlatMap { + pub(in crate::iter) fn new(iter: I, f: F) -> FlatMap { FlatMap { inner: FlattenCompat::new(iter.map(f)) } } } diff --git a/library/core/src/iter/adapters/fuse.rs b/library/core/src/iter/adapters/fuse.rs index 60ac3524e66..c159e67773b 100644 --- a/library/core/src/iter/adapters/fuse.rs +++ b/library/core/src/iter/adapters/fuse.rs @@ -1,10 +1,11 @@ -use super::InPlaceIterable; -use crate::intrinsics; -use crate::iter::adapters::zip::try_get_unchecked; -use crate::iter::adapters::SourceIter; -use crate::iter::TrustedRandomAccess; -use crate::iter::{DoubleEndedIterator, ExactSizeIterator, FusedIterator, Iterator}; -use crate::ops::Try; +use crate::{ + intrinsics, + iter::{ + adapters::{zip::try_get_unchecked, InPlaceIterable, SourceIter}, + DoubleEndedIterator, ExactSizeIterator, FusedIterator, Iterator, TrustedRandomAccess, + }, + ops::Try, +}; /// An iterator that yields `None` forever after the underlying iterator /// yields `None` once. diff --git a/library/core/src/iter/adapters/inspect.rs b/library/core/src/iter/adapters/inspect.rs new file mode 100644 index 00000000000..ae2e5eac728 --- /dev/null +++ b/library/core/src/iter/adapters/inspect.rs @@ -0,0 +1,169 @@ +use crate::{ + fmt, + iter::{adapters::SourceIter, FusedIterator, InPlaceIterable}, + ops::Try, +}; + +/// 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`]: Iterator::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 { + iter: I, + f: F, +} +impl Inspect { + pub(in crate::iter) fn new(iter: I, f: F) -> Inspect { + Inspect { iter, f } + } +} + +#[stable(feature = "core_impl_debug", since = "1.9.0")] +impl fmt::Debug for Inspect { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + f.debug_struct("Inspect").field("iter", &self.iter).finish() + } +} + +impl Inspect +where + F: FnMut(&I::Item), +{ + #[inline] + fn do_inspect(&mut self, elt: Option) -> Option { + if let Some(ref a) = elt { + (self.f)(a); + } + + elt + } +} + +fn inspect_fold( + mut f: impl FnMut(&T), + mut fold: impl FnMut(Acc, T) -> Acc, +) -> impl FnMut(Acc, T) -> Acc { + move |acc, item| { + f(&item); + fold(acc, item) + } +} + +fn inspect_try_fold<'a, T, Acc, R>( + f: &'a mut impl FnMut(&T), + mut fold: impl FnMut(Acc, T) -> R + 'a, +) -> impl FnMut(Acc, T) -> R + 'a { + move |acc, item| { + f(&item); + fold(acc, item) + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl Iterator for Inspect +where + F: FnMut(&I::Item), +{ + type Item = I::Item; + + #[inline] + fn next(&mut self) -> Option { + let next = self.iter.next(); + self.do_inspect(next) + } + + #[inline] + fn size_hint(&self) -> (usize, Option) { + self.iter.size_hint() + } + + #[inline] + fn try_fold(&mut self, init: Acc, fold: Fold) -> R + where + Self: Sized, + Fold: FnMut(Acc, Self::Item) -> R, + R: Try, + { + self.iter.try_fold(init, inspect_try_fold(&mut self.f, fold)) + } + + #[inline] + fn fold(self, init: Acc, fold: Fold) -> Acc + where + Fold: FnMut(Acc, Self::Item) -> Acc, + { + self.iter.fold(init, inspect_fold(self.f, fold)) + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl DoubleEndedIterator for Inspect +where + F: FnMut(&I::Item), +{ + #[inline] + fn next_back(&mut self) -> Option { + let next = self.iter.next_back(); + self.do_inspect(next) + } + + #[inline] + fn try_rfold(&mut self, init: Acc, fold: Fold) -> R + where + Self: Sized, + Fold: FnMut(Acc, Self::Item) -> R, + R: Try, + { + self.iter.try_rfold(init, inspect_try_fold(&mut self.f, fold)) + } + + #[inline] + fn rfold(self, init: Acc, fold: Fold) -> Acc + where + Fold: FnMut(Acc, Self::Item) -> Acc, + { + self.iter.rfold(init, inspect_fold(self.f, fold)) + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl ExactSizeIterator for Inspect +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 FusedIterator for Inspect where F: FnMut(&I::Item) {} + +#[unstable(issue = "none", feature = "inplace_iteration")] +unsafe impl SourceIter for Inspect +where + F: FnMut(&I::Item), + I: SourceIter, +{ + type Source = S; + + #[inline] + unsafe fn as_inner(&mut self) -> &mut S { + // SAFETY: unsafe function forwarding to unsafe function with the same requirements + unsafe { SourceIter::as_inner(&mut self.iter) } + } +} + +#[unstable(issue = "none", feature = "inplace_iteration")] +unsafe impl InPlaceIterable for Inspect where F: FnMut(&I::Item) {} diff --git a/library/core/src/iter/adapters/map.rs b/library/core/src/iter/adapters/map.rs new file mode 100644 index 00000000000..0691f997f7b --- /dev/null +++ b/library/core/src/iter/adapters/map.rs @@ -0,0 +1,217 @@ +use crate::{ + fmt, + iter::{ + adapters::{zip::try_get_unchecked, SourceIter, TrustedRandomAccess}, + FusedIterator, InPlaceIterable, TrustedLen, + }, + ops::Try, +}; + +/// 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`]: Iterator::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 = 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 { + iter: I, + f: F, +} +impl Map { + pub(in crate::iter) fn new(iter: I, f: F) -> Map { + Map { iter, f } + } +} + +#[stable(feature = "core_impl_debug", since = "1.9.0")] +impl fmt::Debug for Map { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + f.debug_struct("Map").field("iter", &self.iter).finish() + } +} + +fn map_fold( + mut f: impl FnMut(T) -> B, + mut g: impl FnMut(Acc, B) -> Acc, +) -> impl FnMut(Acc, T) -> Acc { + move |acc, elt| g(acc, f(elt)) +} + +fn map_try_fold<'a, T, B, Acc, R>( + f: &'a mut impl FnMut(T) -> B, + mut g: impl FnMut(Acc, B) -> R + 'a, +) -> impl FnMut(Acc, T) -> R + 'a { + move |acc, elt| g(acc, f(elt)) +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl Iterator for Map +where + F: FnMut(I::Item) -> B, +{ + type Item = B; + + #[inline] + fn next(&mut self) -> Option { + self.iter.next().map(&mut self.f) + } + + #[inline] + fn size_hint(&self) -> (usize, Option) { + self.iter.size_hint() + } + + fn try_fold(&mut self, init: Acc, g: G) -> R + where + Self: Sized, + G: FnMut(Acc, Self::Item) -> R, + R: Try, + { + self.iter.try_fold(init, map_try_fold(&mut self.f, g)) + } + + fn fold(self, init: Acc, g: G) -> Acc + where + G: FnMut(Acc, Self::Item) -> Acc, + { + self.iter.fold(init, map_fold(self.f, g)) + } + + unsafe fn __iterator_get_unchecked(&mut self, idx: usize) -> B + where + Self: TrustedRandomAccess, + { + // SAFETY: the caller must uphold the contract for + // `Iterator::__iterator_get_unchecked`. + unsafe { (self.f)(try_get_unchecked(&mut self.iter, idx)) } + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl DoubleEndedIterator for Map +where + F: FnMut(I::Item) -> B, +{ + #[inline] + fn next_back(&mut self) -> Option { + self.iter.next_back().map(&mut self.f) + } + + fn try_rfold(&mut self, init: Acc, g: G) -> R + where + Self: Sized, + G: FnMut(Acc, Self::Item) -> R, + R: Try, + { + self.iter.try_rfold(init, map_try_fold(&mut self.f, g)) + } + + fn rfold(self, init: Acc, g: G) -> Acc + where + G: FnMut(Acc, Self::Item) -> Acc, + { + self.iter.rfold(init, map_fold(self.f, g)) + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl ExactSizeIterator for Map +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 FusedIterator for Map where F: FnMut(I::Item) -> B {} + +#[unstable(feature = "trusted_len", issue = "37572")] +unsafe impl TrustedLen for Map +where + I: TrustedLen, + F: FnMut(I::Item) -> B, +{ +} + +#[doc(hidden)] +#[unstable(feature = "trusted_random_access", issue = "none")] +unsafe impl TrustedRandomAccess for Map +where + I: TrustedRandomAccess, +{ + #[inline] + fn may_have_side_effect() -> bool { + true + } +} + +#[unstable(issue = "none", feature = "inplace_iteration")] +unsafe impl SourceIter for Map +where + F: FnMut(I::Item) -> B, + I: SourceIter, +{ + type Source = S; + + #[inline] + unsafe fn as_inner(&mut self) -> &mut S { + // SAFETY: unsafe function forwarding to unsafe function with the same requirements + unsafe { SourceIter::as_inner(&mut self.iter) } + } +} + +#[unstable(issue = "none", feature = "inplace_iteration")] +unsafe impl InPlaceIterable for Map where F: FnMut(I::Item) -> B {} diff --git a/library/core/src/iter/adapters/map_while.rs b/library/core/src/iter/adapters/map_while.rs new file mode 100644 index 00000000000..a3dcbb4d82f --- /dev/null +++ b/library/core/src/iter/adapters/map_while.rs @@ -0,0 +1,103 @@ +use crate::{ + fmt, + iter::{adapters::SourceIter, InPlaceIterable}, + ops::{ControlFlow, Try}, +}; + +/// An iterator that only accepts elements while `predicate` returns `Some(_)`. +/// +/// This `struct` is created by the [`map_while`] method on [`Iterator`]. See its +/// documentation for more. +/// +/// [`map_while`]: Iterator::map_while +/// [`Iterator`]: trait.Iterator.html +#[must_use = "iterators are lazy and do nothing unless consumed"] +#[unstable(feature = "iter_map_while", reason = "recently added", issue = "68537")] +#[derive(Clone)] +pub struct MapWhile { + iter: I, + predicate: P, +} + +impl MapWhile { + pub(in crate::iter) fn new(iter: I, predicate: P) -> MapWhile { + MapWhile { iter, predicate } + } +} + +#[unstable(feature = "iter_map_while", reason = "recently added", issue = "68537")] +impl fmt::Debug for MapWhile { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + f.debug_struct("MapWhile").field("iter", &self.iter).finish() + } +} + +#[unstable(feature = "iter_map_while", reason = "recently added", issue = "68537")] +impl Iterator for MapWhile +where + P: FnMut(I::Item) -> Option, +{ + type Item = B; + + #[inline] + fn next(&mut self) -> Option { + let x = self.iter.next()?; + (self.predicate)(x) + } + + #[inline] + fn size_hint(&self) -> (usize, Option) { + let (_, upper) = self.iter.size_hint(); + (0, upper) // can't know a lower bound, due to the predicate + } + + #[inline] + fn try_fold(&mut self, init: Acc, mut fold: Fold) -> R + where + Self: Sized, + Fold: FnMut(Acc, Self::Item) -> R, + R: Try, + { + let Self { iter, predicate } = self; + iter.try_fold(init, |acc, x| match predicate(x) { + Some(item) => ControlFlow::from_try(fold(acc, item)), + None => ControlFlow::Break(try { acc }), + }) + .into_try() + } + + #[inline] + fn fold(mut self, init: Acc, fold: Fold) -> Acc + where + Self: Sized, + Fold: FnMut(Acc, Self::Item) -> Acc, + { + #[inline] + fn ok(mut f: impl FnMut(B, T) -> B) -> impl FnMut(B, T) -> Result { + move |acc, x| Ok(f(acc, x)) + } + + self.try_fold(init, ok(fold)).unwrap() + } +} + +#[unstable(issue = "none", feature = "inplace_iteration")] +unsafe impl SourceIter for MapWhile +where + P: FnMut(I::Item) -> Option, + I: SourceIter, +{ + type Source = S; + + #[inline] + unsafe fn as_inner(&mut self) -> &mut S { + // SAFETY: unsafe function forwarding to unsafe function with the same requirements + unsafe { SourceIter::as_inner(&mut self.iter) } + } +} + +#[unstable(issue = "none", feature = "inplace_iteration")] +unsafe impl InPlaceIterable for MapWhile where + P: FnMut(I::Item) -> Option +{ +} diff --git a/library/core/src/iter/adapters/mod.rs b/library/core/src/iter/adapters/mod.rs index 9586284e1d7..358049848e9 100644 --- a/library/core/src/iter/adapters/mod.rs +++ b/library/core/src/iter/adapters/mod.rs @@ -1,26 +1,67 @@ -use crate::cmp; -use crate::fmt; -use crate::intrinsics; -use crate::ops::{Add, AddAssign, ControlFlow, Try}; - -use super::from_fn; -use super::{ - DoubleEndedIterator, ExactSizeIterator, FusedIterator, InPlaceIterable, Iterator, TrustedLen, +use crate::{ + iter::{InPlaceIterable, Iterator}, + ops::{ControlFlow, Try}, }; mod chain; +mod cloned; +mod copied; +mod cycle; +mod enumerate; +mod filter; +mod filter_map; mod flatten; mod fuse; +mod inspect; +mod map; +mod map_while; +mod peekable; +mod rev; +mod scan; +mod skip; +mod skip_while; +mod step_by; +mod take; +mod take_while; mod zip; -pub use self::chain::Chain; -#[stable(feature = "rust1", since = "1.0.0")] -pub use self::flatten::{FlatMap, Flatten}; -pub use self::fuse::Fuse; -use self::zip::try_get_unchecked; +pub use self::{ + chain::Chain, + cycle::Cycle, + enumerate::Enumerate, + filter::Filter, + filter_map::FilterMap, + flatten::FlatMap, + fuse::Fuse, + inspect::Inspect, + map::Map, + peekable::Peekable, + rev::Rev, + scan::Scan, + skip::Skip, + skip_while::SkipWhile, + take::Take, + take_while::TakeWhile, + zip::Zip, +}; + +#[stable(feature = "iter_cloned", since = "1.1.0")] +pub use self::cloned::Cloned; + +#[stable(feature = "iterator_step_by", since = "1.28.0")] +pub use self::step_by::StepBy; + +#[stable(feature = "iterator_flatten", since = "1.29.0")] +pub use self::flatten::Flatten; + +#[stable(feature = "iter_copied", since = "1.36.0")] +pub use self::copied::Copied; + +#[unstable(feature = "iter_map_while", reason = "recently added", issue = "68537")] +pub use self::map_while::MapWhile; + #[unstable(feature = "trusted_random_access", issue = "none")] pub use self::zip::TrustedRandomAccess; -pub use self::zip::Zip; /// This trait provides transitive access to source-stage in an interator-adapter pipeline /// under the conditions that @@ -89,2810 +130,6 @@ pub unsafe trait SourceIter { unsafe fn as_inner(&mut self) -> &mut Self::Source; } -/// A double-ended iterator with the direction inverted. -/// -/// This `struct` is created by the [`rev`] method on [`Iterator`]. See its -/// documentation for more. -/// -/// [`rev`]: Iterator::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 { - iter: T, -} -impl Rev { - pub(super) fn new(iter: T) -> Rev { - Rev { iter } - } -} - -#[stable(feature = "rust1", since = "1.0.0")] -impl Iterator for Rev -where - I: DoubleEndedIterator, -{ - type Item = ::Item; - - #[inline] - fn next(&mut self) -> Option<::Item> { - self.iter.next_back() - } - #[inline] - fn size_hint(&self) -> (usize, Option) { - self.iter.size_hint() - } - - #[inline] - fn advance_by(&mut self, n: usize) -> Result<(), usize> { - self.iter.advance_back_by(n) - } - - #[inline] - fn nth(&mut self, n: usize) -> Option<::Item> { - self.iter.nth_back(n) - } - - fn try_fold(&mut self, init: B, f: F) -> R - where - Self: Sized, - F: FnMut(B, Self::Item) -> R, - R: Try, - { - self.iter.try_rfold(init, f) - } - - fn fold(self, init: Acc, f: F) -> Acc - where - F: FnMut(Acc, Self::Item) -> Acc, - { - self.iter.rfold(init, f) - } - - #[inline] - fn find

(&mut self, predicate: P) -> Option - where - P: FnMut(&Self::Item) -> bool, - { - self.iter.rfind(predicate) - } -} - -#[stable(feature = "rust1", since = "1.0.0")] -impl DoubleEndedIterator for Rev -where - I: DoubleEndedIterator, -{ - #[inline] - fn next_back(&mut self) -> Option<::Item> { - self.iter.next() - } - - #[inline] - fn advance_back_by(&mut self, n: usize) -> Result<(), usize> { - self.iter.advance_by(n) - } - - #[inline] - fn nth_back(&mut self, n: usize) -> Option<::Item> { - self.iter.nth(n) - } - - fn try_rfold(&mut self, init: B, f: F) -> R - where - Self: Sized, - F: FnMut(B, Self::Item) -> R, - R: Try, - { - self.iter.try_fold(init, f) - } - - fn rfold(self, init: Acc, f: F) -> Acc - where - F: FnMut(Acc, Self::Item) -> Acc, - { - self.iter.fold(init, f) - } - - fn rfind

(&mut self, predicate: P) -> Option - where - P: FnMut(&Self::Item) -> bool, - { - self.iter.find(predicate) - } -} - -#[stable(feature = "rust1", since = "1.0.0")] -impl ExactSizeIterator for Rev -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 FusedIterator for Rev where I: FusedIterator + DoubleEndedIterator {} - -#[unstable(feature = "trusted_len", issue = "37572")] -unsafe impl TrustedLen for Rev 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`]: Iterator::copied -/// [`Iterator`]: trait.Iterator.html -#[stable(feature = "iter_copied", since = "1.36.0")] -#[must_use = "iterators are lazy and do nothing unless consumed"] -#[derive(Clone, Debug)] -pub struct Copied { - it: I, -} - -impl Copied { - pub(super) fn new(it: I) -> Copied { - Copied { it } - } -} - -fn copy_fold(mut f: impl FnMut(Acc, T) -> Acc) -> impl FnMut(Acc, &T) -> Acc { - move |acc, &elt| f(acc, elt) -} - -fn copy_try_fold(mut f: impl FnMut(Acc, T) -> R) -> impl FnMut(Acc, &T) -> R { - move |acc, &elt| f(acc, elt) -} - -#[stable(feature = "iter_copied", since = "1.36.0")] -impl<'a, I, T: 'a> Iterator for Copied -where - I: Iterator, - T: Copy, -{ - type Item = T; - - fn next(&mut self) -> Option { - self.it.next().copied() - } - - fn size_hint(&self) -> (usize, Option) { - self.it.size_hint() - } - - fn try_fold(&mut self, init: B, f: F) -> R - where - Self: Sized, - F: FnMut(B, Self::Item) -> R, - R: Try, - { - self.it.try_fold(init, copy_try_fold(f)) - } - - fn fold(self, init: Acc, f: F) -> Acc - where - F: FnMut(Acc, Self::Item) -> Acc, - { - self.it.fold(init, copy_fold(f)) - } - - fn nth(&mut self, n: usize) -> Option { - self.it.nth(n).copied() - } - - fn last(self) -> Option { - self.it.last().copied() - } - - fn count(self) -> usize { - self.it.count() - } - - unsafe fn __iterator_get_unchecked(&mut self, idx: usize) -> T - where - Self: TrustedRandomAccess, - { - // SAFETY: the caller must uphold the contract for - // `Iterator::__iterator_get_unchecked`. - *unsafe { try_get_unchecked(&mut self.it, idx) } - } -} - -#[stable(feature = "iter_copied", since = "1.36.0")] -impl<'a, I, T: 'a> DoubleEndedIterator for Copied -where - I: DoubleEndedIterator, - T: Copy, -{ - fn next_back(&mut self) -> Option { - self.it.next_back().copied() - } - - fn try_rfold(&mut self, init: B, f: F) -> R - where - Self: Sized, - F: FnMut(B, Self::Item) -> R, - R: Try, - { - self.it.try_rfold(init, copy_try_fold(f)) - } - - fn rfold(self, init: Acc, f: F) -> Acc - where - F: FnMut(Acc, Self::Item) -> Acc, - { - self.it.rfold(init, copy_fold(f)) - } -} - -#[stable(feature = "iter_copied", since = "1.36.0")] -impl<'a, I, T: 'a> ExactSizeIterator for Copied -where - I: ExactSizeIterator, - T: Copy, -{ - fn len(&self) -> usize { - self.it.len() - } - - fn is_empty(&self) -> bool { - self.it.is_empty() - } -} - -#[stable(feature = "iter_copied", since = "1.36.0")] -impl<'a, I, T: 'a> FusedIterator for Copied -where - I: FusedIterator, - T: Copy, -{ -} - -#[doc(hidden)] -#[unstable(feature = "trusted_random_access", issue = "none")] -unsafe impl TrustedRandomAccess for Copied -where - I: TrustedRandomAccess, -{ - #[inline] - fn may_have_side_effect() -> bool { - I::may_have_side_effect() - } -} - -#[stable(feature = "iter_copied", since = "1.36.0")] -unsafe impl<'a, I, T: 'a> TrustedLen for Copied -where - I: TrustedLen, - 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`]: Iterator::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 { - it: I, -} -impl Cloned { - pub(super) fn new(it: I) -> Cloned { - Cloned { it } - } -} - -fn clone_try_fold(mut f: impl FnMut(Acc, T) -> R) -> impl FnMut(Acc, &T) -> R { - move |acc, elt| f(acc, elt.clone()) -} - -#[stable(feature = "iter_cloned", since = "1.1.0")] -impl<'a, I, T: 'a> Iterator for Cloned -where - I: Iterator, - T: Clone, -{ - type Item = T; - - fn next(&mut self) -> Option { - self.it.next().cloned() - } - - fn size_hint(&self) -> (usize, Option) { - self.it.size_hint() - } - - fn try_fold(&mut self, init: B, f: F) -> R - where - Self: Sized, - F: FnMut(B, Self::Item) -> R, - R: Try, - { - self.it.try_fold(init, clone_try_fold(f)) - } - - fn fold(self, init: Acc, f: F) -> Acc - where - F: FnMut(Acc, Self::Item) -> Acc, - { - self.it.map(T::clone).fold(init, f) - } - - unsafe fn __iterator_get_unchecked(&mut self, idx: usize) -> T - where - Self: TrustedRandomAccess, - { - // SAFETY: the caller must uphold the contract for - // `Iterator::__iterator_get_unchecked`. - unsafe { try_get_unchecked(&mut self.it, idx).clone() } - } -} - -#[stable(feature = "iter_cloned", since = "1.1.0")] -impl<'a, I, T: 'a> DoubleEndedIterator for Cloned -where - I: DoubleEndedIterator, - T: Clone, -{ - fn next_back(&mut self) -> Option { - self.it.next_back().cloned() - } - - fn try_rfold(&mut self, init: B, f: F) -> R - where - Self: Sized, - F: FnMut(B, Self::Item) -> R, - R: Try, - { - self.it.try_rfold(init, clone_try_fold(f)) - } - - fn rfold(self, init: Acc, f: F) -> Acc - where - F: FnMut(Acc, Self::Item) -> Acc, - { - self.it.map(T::clone).rfold(init, f) - } -} - -#[stable(feature = "iter_cloned", since = "1.1.0")] -impl<'a, I, T: 'a> ExactSizeIterator for Cloned -where - I: ExactSizeIterator, - 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 -where - I: FusedIterator, - T: Clone, -{ -} - -#[doc(hidden)] -#[unstable(feature = "trusted_random_access", issue = "none")] -unsafe impl TrustedRandomAccess for Cloned -where - I: TrustedRandomAccess, -{ - #[inline] - fn may_have_side_effect() -> bool { - true - } -} - -#[unstable(feature = "trusted_len", issue = "37572")] -unsafe impl<'a, I, T: 'a> TrustedLen for Cloned -where - I: TrustedLen, - T: Clone, -{ -} - -/// An iterator that repeats endlessly. -/// -/// This `struct` is created by the [`cycle`] method on [`Iterator`]. See its -/// documentation for more. -/// -/// [`cycle`]: Iterator::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 { - orig: I, - iter: I, -} -impl Cycle { - pub(super) fn new(iter: I) -> Cycle { - Cycle { orig: iter.clone(), iter } - } -} - -#[stable(feature = "rust1", since = "1.0.0")] -impl Iterator for Cycle -where - I: Clone + Iterator, -{ - type Item = ::Item; - - #[inline] - fn next(&mut self) -> Option<::Item> { - match self.iter.next() { - None => { - self.iter = self.orig.clone(); - self.iter.next() - } - y => y, - } - } - - #[inline] - fn size_hint(&self) -> (usize, Option) { - // the cycle iterator is either empty or infinite - match self.orig.size_hint() { - sz @ (0, Some(0)) => sz, - (0, _) => (0, None), - _ => (usize::MAX, None), - } - } - - #[inline] - fn try_fold(&mut self, mut acc: Acc, mut f: F) -> R - where - F: FnMut(Acc, Self::Item) -> R, - R: Try, - { - // fully iterate the current iterator. this is necessary because - // `self.iter` may be empty even when `self.orig` isn't - acc = self.iter.try_fold(acc, &mut f)?; - self.iter = self.orig.clone(); - - // complete a full cycle, keeping track of whether the cycled - // iterator is empty or not. we need to return early in case - // of an empty iterator to prevent an infinite loop - let mut is_empty = true; - acc = self.iter.try_fold(acc, |acc, x| { - is_empty = false; - f(acc, x) - })?; - - if is_empty { - return try { acc }; - } - - loop { - self.iter = self.orig.clone(); - acc = self.iter.try_fold(acc, &mut f)?; - } - } - - // No `fold` override, because `fold` doesn't make much sense for `Cycle`, - // and we can't do anything better than the default. -} - -#[stable(feature = "fused", since = "1.26.0")] -impl FusedIterator for Cycle 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`]: Iterator::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 { - iter: I, - step: usize, - first_take: bool, -} -impl StepBy { - pub(super) fn new(iter: I, step: usize) -> StepBy { - assert!(step != 0); - StepBy { iter, step: step - 1, first_take: true } - } -} - -#[stable(feature = "iterator_step_by", since = "1.28.0")] -impl Iterator for StepBy -where - I: Iterator, -{ - type Item = I::Item; - - #[inline] - fn next(&mut self) -> Option { - if self.first_take { - self.first_take = false; - self.iter.next() - } else { - self.iter.nth(self.step) - } - } - - #[inline] - fn size_hint(&self) -> (usize, Option) { - #[inline] - fn first_size(step: usize) -> impl Fn(usize) -> usize { - move |n| if n == 0 { 0 } else { 1 + (n - 1) / (step + 1) } - } - - #[inline] - fn other_size(step: usize) -> impl Fn(usize) -> usize { - move |n| n / (step + 1) - } - - let (low, high) = self.iter.size_hint(); - - if self.first_take { - let f = first_size(self.step); - (f(low), high.map(f)) - } else { - let f = other_size(self.step); - (f(low), high.map(f)) - } - } - - #[inline] - fn nth(&mut self, mut n: usize) -> Option { - 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 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); - } - } - - fn try_fold(&mut self, mut acc: Acc, mut f: F) -> R - where - F: FnMut(Acc, Self::Item) -> R, - R: Try, - { - #[inline] - fn nth(iter: &mut I, step: usize) -> impl FnMut() -> Option + '_ { - move || iter.nth(step) - } - - if self.first_take { - self.first_take = false; - match self.iter.next() { - None => return try { acc }, - Some(x) => acc = f(acc, x)?, - } - } - from_fn(nth(&mut self.iter, self.step)).try_fold(acc, f) - } - - fn fold(mut self, mut acc: Acc, mut f: F) -> Acc - where - F: FnMut(Acc, Self::Item) -> Acc, - { - #[inline] - fn nth(iter: &mut I, step: usize) -> impl FnMut() -> Option + '_ { - move || iter.nth(step) - } - - if self.first_take { - self.first_take = false; - match self.iter.next() { - None => return acc, - Some(x) => acc = f(acc, x), - } - } - from_fn(nth(&mut self.iter, self.step)).fold(acc, f) - } -} - -impl StepBy -where - I: ExactSizeIterator, -{ - // The zero-based index starting from the end of the iterator of the - // last element. Used in the `DoubleEndedIterator` implementation. - fn next_back_index(&self) -> usize { - let rem = self.iter.len() % (self.step + 1); - if self.first_take { - if rem == 0 { self.step } else { rem - 1 } - } else { - rem - } - } -} - -#[stable(feature = "double_ended_step_by_iterator", since = "1.38.0")] -impl DoubleEndedIterator for StepBy -where - I: DoubleEndedIterator + ExactSizeIterator, -{ - #[inline] - fn next_back(&mut self) -> Option { - self.iter.nth_back(self.next_back_index()) - } - - #[inline] - fn nth_back(&mut self, n: usize) -> Option { - // `self.iter.nth_back(usize::MAX)` does the right thing here when `n` - // is out of bounds because the length of `self.iter` does not exceed - // `usize::MAX` (because `I: ExactSizeIterator`) and `nth_back` is - // zero-indexed - let n = n.saturating_mul(self.step + 1).saturating_add(self.next_back_index()); - self.iter.nth_back(n) - } - - fn try_rfold(&mut self, init: Acc, mut f: F) -> R - where - F: FnMut(Acc, Self::Item) -> R, - R: Try, - { - #[inline] - fn nth_back( - iter: &mut I, - step: usize, - ) -> impl FnMut() -> Option + '_ { - move || iter.nth_back(step) - } - - match self.next_back() { - None => try { init }, - Some(x) => { - let acc = f(init, x)?; - from_fn(nth_back(&mut self.iter, self.step)).try_fold(acc, f) - } - } - } - - #[inline] - fn rfold(mut self, init: Acc, mut f: F) -> Acc - where - Self: Sized, - F: FnMut(Acc, Self::Item) -> Acc, - { - #[inline] - fn nth_back( - iter: &mut I, - step: usize, - ) -> impl FnMut() -> Option + '_ { - move || iter.nth_back(step) - } - - match self.next_back() { - None => init, - Some(x) => { - let acc = f(init, x); - from_fn(nth_back(&mut self.iter, self.step)).fold(acc, f) - } - } - } -} - -// StepBy can only make the iterator shorter, so the len will still fit. -#[stable(feature = "iterator_step_by", since = "1.28.0")] -impl ExactSizeIterator for StepBy where I: ExactSizeIterator {} - -/// 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`]: Iterator::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 = 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 { - iter: I, - f: F, -} -impl Map { - pub(super) fn new(iter: I, f: F) -> Map { - Map { iter, f } - } -} - -#[stable(feature = "core_impl_debug", since = "1.9.0")] -impl fmt::Debug for Map { - fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { - f.debug_struct("Map").field("iter", &self.iter).finish() - } -} - -fn map_fold( - mut f: impl FnMut(T) -> B, - mut g: impl FnMut(Acc, B) -> Acc, -) -> impl FnMut(Acc, T) -> Acc { - move |acc, elt| g(acc, f(elt)) -} - -fn map_try_fold<'a, T, B, Acc, R>( - f: &'a mut impl FnMut(T) -> B, - mut g: impl FnMut(Acc, B) -> R + 'a, -) -> impl FnMut(Acc, T) -> R + 'a { - move |acc, elt| g(acc, f(elt)) -} - -#[stable(feature = "rust1", since = "1.0.0")] -impl Iterator for Map -where - F: FnMut(I::Item) -> B, -{ - type Item = B; - - #[inline] - fn next(&mut self) -> Option { - self.iter.next().map(&mut self.f) - } - - #[inline] - fn size_hint(&self) -> (usize, Option) { - self.iter.size_hint() - } - - fn try_fold(&mut self, init: Acc, g: G) -> R - where - Self: Sized, - G: FnMut(Acc, Self::Item) -> R, - R: Try, - { - self.iter.try_fold(init, map_try_fold(&mut self.f, g)) - } - - fn fold(self, init: Acc, g: G) -> Acc - where - G: FnMut(Acc, Self::Item) -> Acc, - { - self.iter.fold(init, map_fold(self.f, g)) - } - - unsafe fn __iterator_get_unchecked(&mut self, idx: usize) -> B - where - Self: TrustedRandomAccess, - { - // SAFETY: the caller must uphold the contract for - // `Iterator::__iterator_get_unchecked`. - unsafe { (self.f)(try_get_unchecked(&mut self.iter, idx)) } - } -} - -#[stable(feature = "rust1", since = "1.0.0")] -impl DoubleEndedIterator for Map -where - F: FnMut(I::Item) -> B, -{ - #[inline] - fn next_back(&mut self) -> Option { - self.iter.next_back().map(&mut self.f) - } - - fn try_rfold(&mut self, init: Acc, g: G) -> R - where - Self: Sized, - G: FnMut(Acc, Self::Item) -> R, - R: Try, - { - self.iter.try_rfold(init, map_try_fold(&mut self.f, g)) - } - - fn rfold(self, init: Acc, g: G) -> Acc - where - G: FnMut(Acc, Self::Item) -> Acc, - { - self.iter.rfold(init, map_fold(self.f, g)) - } -} - -#[stable(feature = "rust1", since = "1.0.0")] -impl ExactSizeIterator for Map -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 FusedIterator for Map where F: FnMut(I::Item) -> B {} - -#[unstable(feature = "trusted_len", issue = "37572")] -unsafe impl TrustedLen for Map -where - I: TrustedLen, - F: FnMut(I::Item) -> B, -{ -} - -#[doc(hidden)] -#[unstable(feature = "trusted_random_access", issue = "none")] -unsafe impl TrustedRandomAccess for Map -where - I: TrustedRandomAccess, -{ - #[inline] - fn may_have_side_effect() -> bool { - true - } -} - -#[unstable(issue = "none", feature = "inplace_iteration")] -unsafe impl SourceIter for Map -where - F: FnMut(I::Item) -> B, - I: SourceIter, -{ - type Source = S; - - #[inline] - unsafe fn as_inner(&mut self) -> &mut S { - // SAFETY: unsafe function forwarding to unsafe function with the same requirements - unsafe { SourceIter::as_inner(&mut self.iter) } - } -} - -#[unstable(issue = "none", feature = "inplace_iteration")] -unsafe impl InPlaceIterable for Map where F: FnMut(I::Item) -> B {} - -/// 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`]: Iterator::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 { - iter: I, - predicate: P, -} -impl Filter { - pub(super) fn new(iter: I, predicate: P) -> Filter { - Filter { iter, predicate } - } -} - -#[stable(feature = "core_impl_debug", since = "1.9.0")] -impl fmt::Debug for Filter { - fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { - f.debug_struct("Filter").field("iter", &self.iter).finish() - } -} - -fn filter_fold( - mut predicate: impl FnMut(&T) -> bool, - mut fold: impl FnMut(Acc, T) -> Acc, -) -> impl FnMut(Acc, T) -> Acc { - move |acc, item| if predicate(&item) { fold(acc, item) } else { acc } -} - -fn filter_try_fold<'a, T, Acc, R: Try>( - predicate: &'a mut impl FnMut(&T) -> bool, - mut fold: impl FnMut(Acc, T) -> R + 'a, -) -> impl FnMut(Acc, T) -> R + 'a { - move |acc, item| if predicate(&item) { fold(acc, item) } else { try { acc } } -} - -#[stable(feature = "rust1", since = "1.0.0")] -impl Iterator for Filter -where - P: FnMut(&I::Item) -> bool, -{ - type Item = I::Item; - - #[inline] - fn next(&mut self) -> Option { - self.iter.find(&mut self.predicate) - } - - #[inline] - fn size_hint(&self) -> (usize, Option) { - 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(self) -> usize { - #[inline] - fn to_usize(mut predicate: impl FnMut(&T) -> bool) -> impl FnMut(T) -> usize { - move |x| predicate(&x) as usize - } - - self.iter.map(to_usize(self.predicate)).sum() - } - - #[inline] - fn try_fold(&mut self, init: Acc, fold: Fold) -> R - where - Self: Sized, - Fold: FnMut(Acc, Self::Item) -> R, - R: Try, - { - self.iter.try_fold(init, filter_try_fold(&mut self.predicate, fold)) - } - - #[inline] - fn fold(self, init: Acc, fold: Fold) -> Acc - where - Fold: FnMut(Acc, Self::Item) -> Acc, - { - self.iter.fold(init, filter_fold(self.predicate, fold)) - } -} - -#[stable(feature = "rust1", since = "1.0.0")] -impl DoubleEndedIterator for Filter -where - P: FnMut(&I::Item) -> bool, -{ - #[inline] - fn next_back(&mut self) -> Option { - self.iter.rfind(&mut self.predicate) - } - - #[inline] - fn try_rfold(&mut self, init: Acc, fold: Fold) -> R - where - Self: Sized, - Fold: FnMut(Acc, Self::Item) -> R, - R: Try, - { - self.iter.try_rfold(init, filter_try_fold(&mut self.predicate, fold)) - } - - #[inline] - fn rfold(self, init: Acc, fold: Fold) -> Acc - where - Fold: FnMut(Acc, Self::Item) -> Acc, - { - self.iter.rfold(init, filter_fold(self.predicate, fold)) - } -} - -#[stable(feature = "fused", since = "1.26.0")] -impl FusedIterator for Filter where P: FnMut(&I::Item) -> bool {} - -#[unstable(issue = "none", feature = "inplace_iteration")] -unsafe impl SourceIter for Filter -where - P: FnMut(&I::Item) -> bool, - I: SourceIter, -{ - type Source = S; - - #[inline] - unsafe fn as_inner(&mut self) -> &mut S { - // SAFETY: unsafe function forwarding to unsafe function with the same requirements - unsafe { SourceIter::as_inner(&mut self.iter) } - } -} - -#[unstable(issue = "none", feature = "inplace_iteration")] -unsafe impl InPlaceIterable for Filter 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`]: Iterator::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 { - iter: I, - f: F, -} -impl FilterMap { - pub(super) fn new(iter: I, f: F) -> FilterMap { - FilterMap { iter, f } - } -} - -#[stable(feature = "core_impl_debug", since = "1.9.0")] -impl fmt::Debug for FilterMap { - fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { - f.debug_struct("FilterMap").field("iter", &self.iter).finish() - } -} - -fn filter_map_fold( - mut f: impl FnMut(T) -> Option, - mut fold: impl FnMut(Acc, B) -> Acc, -) -> impl FnMut(Acc, T) -> Acc { - move |acc, item| match f(item) { - Some(x) => fold(acc, x), - None => acc, - } -} - -fn filter_map_try_fold<'a, T, B, Acc, R: Try>( - f: &'a mut impl FnMut(T) -> Option, - mut fold: impl FnMut(Acc, B) -> R + 'a, -) -> impl FnMut(Acc, T) -> R + 'a { - move |acc, item| match f(item) { - Some(x) => fold(acc, x), - None => try { acc }, - } -} - -#[stable(feature = "rust1", since = "1.0.0")] -impl Iterator for FilterMap -where - F: FnMut(I::Item) -> Option, -{ - type Item = B; - - #[inline] - fn next(&mut self) -> Option { - self.iter.find_map(&mut self.f) - } - - #[inline] - fn size_hint(&self) -> (usize, Option) { - let (_, upper) = self.iter.size_hint(); - (0, upper) // can't know a lower bound, due to the predicate - } - - #[inline] - fn try_fold(&mut self, init: Acc, fold: Fold) -> R - where - Self: Sized, - Fold: FnMut(Acc, Self::Item) -> R, - R: Try, - { - self.iter.try_fold(init, filter_map_try_fold(&mut self.f, fold)) - } - - #[inline] - fn fold(self, init: Acc, fold: Fold) -> Acc - where - Fold: FnMut(Acc, Self::Item) -> Acc, - { - self.iter.fold(init, filter_map_fold(self.f, fold)) - } -} - -#[stable(feature = "rust1", since = "1.0.0")] -impl DoubleEndedIterator for FilterMap -where - F: FnMut(I::Item) -> Option, -{ - #[inline] - fn next_back(&mut self) -> Option { - #[inline] - fn find( - f: &mut impl FnMut(T) -> Option, - ) -> impl FnMut((), T) -> ControlFlow + '_ { - move |(), x| match f(x) { - Some(x) => ControlFlow::Break(x), - None => ControlFlow::CONTINUE, - } - } - - self.iter.try_rfold((), find(&mut self.f)).break_value() - } - - #[inline] - fn try_rfold(&mut self, init: Acc, fold: Fold) -> R - where - Self: Sized, - Fold: FnMut(Acc, Self::Item) -> R, - R: Try, - { - self.iter.try_rfold(init, filter_map_try_fold(&mut self.f, fold)) - } - - #[inline] - fn rfold(self, init: Acc, fold: Fold) -> Acc - where - Fold: FnMut(Acc, Self::Item) -> Acc, - { - self.iter.rfold(init, filter_map_fold(self.f, fold)) - } -} - -#[stable(feature = "fused", since = "1.26.0")] -impl FusedIterator for FilterMap where F: FnMut(I::Item) -> Option {} - -#[unstable(issue = "none", feature = "inplace_iteration")] -unsafe impl SourceIter for FilterMap -where - F: FnMut(I::Item) -> Option, - I: SourceIter, -{ - type Source = S; - - #[inline] - unsafe fn as_inner(&mut self) -> &mut S { - // SAFETY: unsafe function forwarding to unsafe function with the same requirements - unsafe { SourceIter::as_inner(&mut self.iter) } - } -} - -#[unstable(issue = "none", feature = "inplace_iteration")] -unsafe impl InPlaceIterable for FilterMap where - F: FnMut(I::Item) -> Option -{ -} - -/// 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`]: Iterator::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 { - iter: I, - count: usize, -} -impl Enumerate { - pub(super) fn new(iter: I) -> Enumerate { - Enumerate { iter, count: 0 } - } -} - -#[stable(feature = "rust1", since = "1.0.0")] -impl Iterator for Enumerate -where - I: Iterator, -{ - type Item = (usize, ::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] - fn next(&mut self) -> Option<(usize, ::Item)> { - let a = self.iter.next()?; - let i = self.count; - // Possible undefined overflow. - AddAssign::add_assign(&mut self.count, 1); - Some((i, a)) - } - - #[inline] - fn size_hint(&self) -> (usize, Option) { - self.iter.size_hint() - } - - #[inline] - fn nth(&mut self, n: usize) -> Option<(usize, I::Item)> { - let a = self.iter.nth(n)?; - // Possible undefined overflow. - let i = Add::add(self.count, n); - self.count = Add::add(i, 1); - Some((i, a)) - } - - #[inline] - fn count(self) -> usize { - self.iter.count() - } - - #[inline] - fn try_fold(&mut self, init: Acc, fold: Fold) -> R - where - Self: Sized, - Fold: FnMut(Acc, Self::Item) -> R, - R: Try, - { - #[inline] - fn enumerate<'a, T, Acc, R>( - count: &'a mut usize, - mut fold: impl FnMut(Acc, (usize, T)) -> R + 'a, - ) -> impl FnMut(Acc, T) -> R + 'a { - move |acc, item| { - let acc = fold(acc, (*count, item)); - // Possible undefined overflow. - AddAssign::add_assign(count, 1); - acc - } - } - - self.iter.try_fold(init, enumerate(&mut self.count, fold)) - } - - #[inline] - fn fold(self, init: Acc, fold: Fold) -> Acc - where - Fold: FnMut(Acc, Self::Item) -> Acc, - { - #[inline] - fn enumerate( - mut count: usize, - mut fold: impl FnMut(Acc, (usize, T)) -> Acc, - ) -> impl FnMut(Acc, T) -> Acc { - move |acc, item| { - let acc = fold(acc, (count, item)); - // Possible undefined overflow. - AddAssign::add_assign(&mut count, 1); - acc - } - } - - self.iter.fold(init, enumerate(self.count, fold)) - } - - unsafe fn __iterator_get_unchecked(&mut self, idx: usize) -> ::Item - where - Self: TrustedRandomAccess, - { - // SAFETY: the caller must uphold the contract for - // `Iterator::__iterator_get_unchecked`. - let value = unsafe { try_get_unchecked(&mut self.iter, idx) }; - (Add::add(self.count, idx), value) - } -} - -#[stable(feature = "rust1", since = "1.0.0")] -impl DoubleEndedIterator for Enumerate -where - I: ExactSizeIterator + DoubleEndedIterator, -{ - #[inline] - fn next_back(&mut self) -> Option<(usize, ::Item)> { - let a = self.iter.next_back()?; - let len = self.iter.len(); - // Can safely add, `ExactSizeIterator` promises that the number of - // elements fits into a `usize`. - Some((self.count + len, a)) - } - - #[inline] - fn nth_back(&mut self, n: usize) -> Option<(usize, ::Item)> { - let a = self.iter.nth_back(n)?; - let len = self.iter.len(); - // Can safely add, `ExactSizeIterator` promises that the number of - // elements fits into a `usize`. - Some((self.count + len, a)) - } - - #[inline] - fn try_rfold(&mut self, init: Acc, fold: Fold) -> R - where - Self: Sized, - Fold: FnMut(Acc, Self::Item) -> R, - R: Try, - { - // Can safely add and subtract the count, as `ExactSizeIterator` promises - // that the number of elements fits into a `usize`. - fn enumerate( - mut count: usize, - mut fold: impl FnMut(Acc, (usize, T)) -> R, - ) -> impl FnMut(Acc, T) -> R { - move |acc, item| { - count -= 1; - fold(acc, (count, item)) - } - } - - let count = self.count + self.iter.len(); - self.iter.try_rfold(init, enumerate(count, fold)) - } - - #[inline] - fn rfold(self, init: Acc, 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`. - fn enumerate( - mut count: usize, - mut fold: impl FnMut(Acc, (usize, T)) -> Acc, - ) -> impl FnMut(Acc, T) -> Acc { - move |acc, item| { - count -= 1; - fold(acc, (count, item)) - } - } - - let count = self.count + self.iter.len(); - self.iter.rfold(init, enumerate(count, fold)) - } -} - -#[stable(feature = "rust1", since = "1.0.0")] -impl ExactSizeIterator for Enumerate -where - I: ExactSizeIterator, -{ - fn len(&self) -> usize { - self.iter.len() - } - - fn is_empty(&self) -> bool { - self.iter.is_empty() - } -} - -#[doc(hidden)] -#[unstable(feature = "trusted_random_access", issue = "none")] -unsafe impl TrustedRandomAccess for Enumerate -where - I: TrustedRandomAccess, -{ - fn may_have_side_effect() -> bool { - I::may_have_side_effect() - } -} - -#[stable(feature = "fused", since = "1.26.0")] -impl FusedIterator for Enumerate where I: FusedIterator {} - -#[unstable(feature = "trusted_len", issue = "37572")] -unsafe impl TrustedLen for Enumerate where I: TrustedLen {} - -#[unstable(issue = "none", feature = "inplace_iteration")] -unsafe impl SourceIter for Enumerate -where - I: SourceIter, -{ - type Source = S; - - #[inline] - unsafe fn as_inner(&mut self) -> &mut S { - // SAFETY: unsafe function forwarding to unsafe function with the same requirements - unsafe { SourceIter::as_inner(&mut self.iter) } - } -} - -#[unstable(issue = "none", feature = "inplace_iteration")] -unsafe impl InPlaceIterable for Enumerate {} - -/// 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`]: Iterator::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 { - iter: I, - /// Remember a peeked value, even if it was None. - peeked: Option>, -} -impl Peekable { - pub(super) fn new(iter: I) -> Peekable { - Peekable { iter, peeked: None } - } -} - -// 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 Iterator for Peekable { - type Item = I::Item; - - #[inline] - fn next(&mut self) -> Option { - 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 { - 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 { - 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) { - 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 = match hi { - Some(x) => x.checked_add(peek_len), - None => None, - }; - (lo, hi) - } - - #[inline] - fn try_fold(&mut self, init: B, mut f: F) -> R - where - Self: Sized, - F: FnMut(B, Self::Item) -> R, - R: Try, - { - let acc = match self.peeked.take() { - Some(None) => return try { init }, - Some(Some(v)) => f(init, v)?, - None => init, - }; - self.iter.try_fold(acc, f) - } - - #[inline] - fn 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 = "double_ended_peek_iterator", since = "1.38.0")] -impl DoubleEndedIterator for Peekable -where - I: DoubleEndedIterator, -{ - #[inline] - fn next_back(&mut self) -> Option { - match self.peeked.as_mut() { - Some(v @ Some(_)) => self.iter.next_back().or_else(|| v.take()), - Some(None) => None, - None => self.iter.next_back(), - } - } - - #[inline] - fn try_rfold(&mut self, init: B, mut f: F) -> R - where - Self: Sized, - F: FnMut(B, Self::Item) -> R, - R: Try, - { - match self.peeked.take() { - Some(None) => try { init }, - Some(Some(v)) => match self.iter.try_rfold(init, &mut f).into_result() { - Ok(acc) => f(acc, v), - Err(e) => { - self.peeked = Some(Some(v)); - Try::from_error(e) - } - }, - None => self.iter.try_rfold(init, f), - } - } - - #[inline] - fn rfold(self, init: Acc, mut fold: Fold) -> Acc - where - Fold: FnMut(Acc, Self::Item) -> Acc, - { - match self.peeked { - Some(None) => init, - Some(Some(v)) => { - let acc = self.iter.rfold(init, &mut fold); - fold(acc, v) - } - None => self.iter.rfold(init, fold), - } - } -} - -#[stable(feature = "rust1", since = "1.0.0")] -impl ExactSizeIterator for Peekable {} - -#[stable(feature = "fused", since = "1.26.0")] -impl FusedIterator for Peekable {} - -impl Peekable { - /// 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`]: Iterator::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() - } - - /// Consume and return the next value of this iterator if a condition is true. - /// - /// If `func` returns `true` for the next value of this iterator, consume and return it. - /// Otherwise, return `None`. - /// - /// # Examples - /// Consume a number if it's equal to 0. - /// ``` - /// #![feature(peekable_next_if)] - /// let mut iter = (0..5).peekable(); - /// // The first item of the iterator is 0; consume it. - /// assert_eq!(iter.next_if(|&x| x == 0), Some(0)); - /// // The next item returned is now 1, so `consume` will return `false`. - /// assert_eq!(iter.next_if(|&x| x == 0), None); - /// // `next_if` saves the value of the next item if it was not equal to `expected`. - /// assert_eq!(iter.next(), Some(1)); - /// ``` - /// - /// Consume any number less than 10. - /// ``` - /// #![feature(peekable_next_if)] - /// let mut iter = (1..20).peekable(); - /// // Consume all numbers less than 10 - /// while iter.next_if(|&x| x < 10).is_some() {} - /// // The next value returned will be 10 - /// assert_eq!(iter.next(), Some(10)); - /// ``` - #[unstable(feature = "peekable_next_if", issue = "72480")] - pub fn next_if(&mut self, func: impl FnOnce(&I::Item) -> bool) -> Option { - match self.next() { - Some(matched) if func(&matched) => Some(matched), - other => { - // Since we called `self.next()`, we consumed `self.peeked`. - assert!(self.peeked.is_none()); - self.peeked = Some(other); - None - } - } - } - - /// Consume and return the next item if it is equal to `expected`. - /// - /// # Example - /// Consume a number if it's equal to 0. - /// ``` - /// #![feature(peekable_next_if)] - /// let mut iter = (0..5).peekable(); - /// // The first item of the iterator is 0; consume it. - /// assert_eq!(iter.next_if_eq(&0), Some(0)); - /// // The next item returned is now 1, so `consume` will return `false`. - /// assert_eq!(iter.next_if_eq(&0), None); - /// // `next_if_eq` saves the value of the next item if it was not equal to `expected`. - /// assert_eq!(iter.next(), Some(1)); - /// ``` - #[unstable(feature = "peekable_next_if", issue = "72480")] - pub fn next_if_eq(&mut self, expected: &T) -> Option - where - T: ?Sized, - I::Item: PartialEq, - { - self.next_if(|next| next == expected) - } -} - -#[unstable(feature = "trusted_len", issue = "37572")] -unsafe impl TrustedLen for Peekable where I: TrustedLen {} - -#[unstable(issue = "none", feature = "inplace_iteration")] -unsafe impl SourceIter for Peekable -where - I: SourceIter, -{ - type Source = S; - - #[inline] - unsafe fn as_inner(&mut self) -> &mut S { - // SAFETY: unsafe function forwarding to unsafe function with the same requirements - unsafe { SourceIter::as_inner(&mut self.iter) } - } -} - -#[unstable(issue = "none", feature = "inplace_iteration")] -unsafe impl InPlaceIterable for Peekable {} - -/// An iterator that rejects elements while `predicate` returns `true`. -/// -/// This `struct` is created by the [`skip_while`] method on [`Iterator`]. See its -/// documentation for more. -/// -/// [`skip_while`]: Iterator::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 { - iter: I, - flag: bool, - predicate: P, -} -impl SkipWhile { - pub(super) fn new(iter: I, predicate: P) -> SkipWhile { - SkipWhile { iter, flag: false, predicate } - } -} - -#[stable(feature = "core_impl_debug", since = "1.9.0")] -impl fmt::Debug for SkipWhile { - 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 Iterator for SkipWhile -where - P: FnMut(&I::Item) -> bool, -{ - type Item = I::Item; - - #[inline] - fn next(&mut self) -> Option { - fn check<'a, T>( - flag: &'a mut bool, - pred: &'a mut impl FnMut(&T) -> bool, - ) -> impl FnMut(&T) -> bool + 'a { - move |x| { - if *flag || !pred(x) { - *flag = true; - true - } else { - false - } - } - } - - let flag = &mut self.flag; - let pred = &mut self.predicate; - self.iter.find(check(flag, pred)) - } - - #[inline] - fn size_hint(&self) -> (usize, Option) { - let (_, upper) = self.iter.size_hint(); - (0, upper) // can't know a lower bound, due to the predicate - } - - #[inline] - fn try_fold(&mut self, mut init: Acc, mut fold: Fold) -> R - where - Self: Sized, - Fold: FnMut(Acc, Self::Item) -> R, - R: Try, - { - if !self.flag { - match self.next() { - Some(v) => init = fold(init, v)?, - None => return try { init }, - } - } - self.iter.try_fold(init, fold) - } - - #[inline] - fn 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 FusedIterator for SkipWhile -where - I: FusedIterator, - P: FnMut(&I::Item) -> bool, -{ -} - -#[unstable(issue = "none", feature = "inplace_iteration")] -unsafe impl SourceIter for SkipWhile -where - P: FnMut(&I::Item) -> bool, - I: SourceIter, -{ - type Source = S; - - #[inline] - unsafe fn as_inner(&mut self) -> &mut S { - // SAFETY: unsafe function forwarding to unsafe function with the same requirements - unsafe { SourceIter::as_inner(&mut self.iter) } - } -} - -#[unstable(issue = "none", feature = "inplace_iteration")] -unsafe impl InPlaceIterable for SkipWhile where - F: FnMut(&I::Item) -> bool -{ -} - -/// An iterator that only accepts elements while `predicate` returns `true`. -/// -/// This `struct` is created by the [`take_while`] method on [`Iterator`]. See its -/// documentation for more. -/// -/// [`take_while`]: Iterator::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 { - iter: I, - flag: bool, - predicate: P, -} -impl TakeWhile { - pub(super) fn new(iter: I, predicate: P) -> TakeWhile { - TakeWhile { iter, flag: false, predicate } - } -} - -#[stable(feature = "core_impl_debug", since = "1.9.0")] -impl fmt::Debug for TakeWhile { - 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 Iterator for TakeWhile -where - P: FnMut(&I::Item) -> bool, -{ - type Item = I::Item; - - #[inline] - fn next(&mut self) -> Option { - if self.flag { - None - } else { - let x = self.iter.next()?; - if (self.predicate)(&x) { - Some(x) - } else { - self.flag = true; - None - } - } - } - - #[inline] - fn size_hint(&self) -> (usize, Option) { - 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(&mut self, init: Acc, fold: Fold) -> R - where - Self: Sized, - Fold: FnMut(Acc, Self::Item) -> R, - R: Try, - { - fn check<'a, T, Acc, R: Try>( - flag: &'a mut bool, - p: &'a mut impl FnMut(&T) -> bool, - mut fold: impl FnMut(Acc, T) -> R + 'a, - ) -> impl FnMut(Acc, T) -> ControlFlow + 'a { - move |acc, x| { - if p(&x) { - ControlFlow::from_try(fold(acc, x)) - } else { - *flag = true; - ControlFlow::Break(try { acc }) - } - } - } - - if self.flag { - try { init } - } else { - let flag = &mut self.flag; - let p = &mut self.predicate; - self.iter.try_fold(init, check(flag, p, fold)).into_try() - } - } - - #[inline] - fn fold(mut self, init: Acc, fold: Fold) -> Acc - where - Self: Sized, - Fold: FnMut(Acc, Self::Item) -> Acc, - { - #[inline] - fn ok(mut f: impl FnMut(B, T) -> B) -> impl FnMut(B, T) -> Result { - move |acc, x| Ok(f(acc, x)) - } - - self.try_fold(init, ok(fold)).unwrap() - } -} - -#[stable(feature = "fused", since = "1.26.0")] -impl FusedIterator for TakeWhile -where - I: FusedIterator, - P: FnMut(&I::Item) -> bool, -{ -} - -#[unstable(issue = "none", feature = "inplace_iteration")] -unsafe impl SourceIter for TakeWhile -where - P: FnMut(&I::Item) -> bool, - I: SourceIter, -{ - type Source = S; - - #[inline] - unsafe fn as_inner(&mut self) -> &mut S { - // SAFETY: unsafe function forwarding to unsafe function with the same requirements - unsafe { SourceIter::as_inner(&mut self.iter) } - } -} - -#[unstable(issue = "none", feature = "inplace_iteration")] -unsafe impl InPlaceIterable for TakeWhile where - F: FnMut(&I::Item) -> bool -{ -} - -/// An iterator that only accepts elements while `predicate` returns `Some(_)`. -/// -/// This `struct` is created by the [`map_while`] method on [`Iterator`]. See its -/// documentation for more. -/// -/// [`map_while`]: Iterator::map_while -/// [`Iterator`]: trait.Iterator.html -#[must_use = "iterators are lazy and do nothing unless consumed"] -#[unstable(feature = "iter_map_while", reason = "recently added", issue = "68537")] -#[derive(Clone)] -pub struct MapWhile { - iter: I, - predicate: P, -} - -impl MapWhile { - pub(super) fn new(iter: I, predicate: P) -> MapWhile { - MapWhile { iter, predicate } - } -} - -#[unstable(feature = "iter_map_while", reason = "recently added", issue = "68537")] -impl fmt::Debug for MapWhile { - fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { - f.debug_struct("MapWhile").field("iter", &self.iter).finish() - } -} - -#[unstable(feature = "iter_map_while", reason = "recently added", issue = "68537")] -impl Iterator for MapWhile -where - P: FnMut(I::Item) -> Option, -{ - type Item = B; - - #[inline] - fn next(&mut self) -> Option { - let x = self.iter.next()?; - (self.predicate)(x) - } - - #[inline] - fn size_hint(&self) -> (usize, Option) { - let (_, upper) = self.iter.size_hint(); - (0, upper) // can't know a lower bound, due to the predicate - } - - #[inline] - fn try_fold(&mut self, init: Acc, mut fold: Fold) -> R - where - Self: Sized, - Fold: FnMut(Acc, Self::Item) -> R, - R: Try, - { - let Self { iter, predicate } = self; - iter.try_fold(init, |acc, x| match predicate(x) { - Some(item) => ControlFlow::from_try(fold(acc, item)), - None => ControlFlow::Break(try { acc }), - }) - .into_try() - } - - #[inline] - fn fold(mut self, init: Acc, fold: Fold) -> Acc - where - Self: Sized, - Fold: FnMut(Acc, Self::Item) -> Acc, - { - #[inline] - fn ok(mut f: impl FnMut(B, T) -> B) -> impl FnMut(B, T) -> Result { - move |acc, x| Ok(f(acc, x)) - } - - self.try_fold(init, ok(fold)).unwrap() - } -} - -#[unstable(issue = "none", feature = "inplace_iteration")] -unsafe impl SourceIter for MapWhile -where - P: FnMut(I::Item) -> Option, - I: SourceIter, -{ - type Source = S; - - #[inline] - unsafe fn as_inner(&mut self) -> &mut S { - // SAFETY: unsafe function forwarding to unsafe function with the same requirements - unsafe { SourceIter::as_inner(&mut self.iter) } - } -} - -#[unstable(issue = "none", feature = "inplace_iteration")] -unsafe impl InPlaceIterable for MapWhile where - P: FnMut(I::Item) -> Option -{ -} - -/// 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`]: Iterator::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 { - iter: I, - n: usize, -} -impl Skip { - pub(super) fn new(iter: I, n: usize) -> Skip { - Skip { iter, n } - } -} - -#[stable(feature = "rust1", since = "1.0.0")] -impl Iterator for Skip -where - I: Iterator, -{ - type Item = ::Item; - - #[inline] - fn next(&mut self) -> Option { - 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 { - // Can't just add n + self.n due to overflow. - if self.n > 0 { - let to_skip = self.n; - self.n = 0; - // nth(n) skips n+1 - self.iter.nth(to_skip - 1)?; - } - self.iter.nth(n) - } - - #[inline] - fn count(mut self) -> usize { - if self.n > 0 { - // nth(n) skips n+1 - if self.iter.nth(self.n - 1).is_none() { - return 0; - } - } - self.iter.count() - } - - #[inline] - fn last(mut self) -> Option { - if self.n > 0 { - // nth(n) skips n+1 - self.iter.nth(self.n - 1)?; - } - self.iter.last() - } - - #[inline] - fn size_hint(&self) -> (usize, Option) { - let (lower, upper) = self.iter.size_hint(); - - let lower = lower.saturating_sub(self.n); - let upper = match upper { - Some(x) => Some(x.saturating_sub(self.n)), - None => None, - }; - - (lower, upper) - } - - #[inline] - fn try_fold(&mut self, init: Acc, fold: Fold) -> R - where - Self: Sized, - Fold: FnMut(Acc, Self::Item) -> R, - R: Try, - { - 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 { init }; - } - } - self.iter.try_fold(init, fold) - } - - #[inline] - fn 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 ExactSizeIterator for Skip where I: ExactSizeIterator {} - -#[stable(feature = "double_ended_skip_iterator", since = "1.9.0")] -impl DoubleEndedIterator for Skip -where - I: DoubleEndedIterator + ExactSizeIterator, -{ - fn next_back(&mut self) -> Option { - if self.len() > 0 { self.iter.next_back() } else { None } - } - - #[inline] - fn nth_back(&mut self, n: usize) -> Option { - let len = self.len(); - if n < len { - self.iter.nth_back(n) - } else { - if len > 0 { - // consume the original iterator - self.iter.nth_back(len - 1); - } - None - } - } - - fn try_rfold(&mut self, init: Acc, fold: Fold) -> R - where - Self: Sized, - Fold: FnMut(Acc, Self::Item) -> R, - R: Try, - { - fn check>( - mut n: usize, - mut fold: impl FnMut(Acc, T) -> R, - ) -> impl FnMut(Acc, T) -> ControlFlow { - move |acc, x| { - n -= 1; - let r = fold(acc, x); - if n == 0 { ControlFlow::Break(r) } else { ControlFlow::from_try(r) } - } - } - - let n = self.len(); - if n == 0 { try { init } } else { self.iter.try_rfold(init, check(n, fold)).into_try() } - } - - fn rfold(mut self, init: Acc, fold: Fold) -> Acc - where - Fold: FnMut(Acc, Self::Item) -> Acc, - { - #[inline] - fn ok(mut f: impl FnMut(Acc, T) -> Acc) -> impl FnMut(Acc, T) -> Result { - move |acc, x| Ok(f(acc, x)) - } - - self.try_rfold(init, ok(fold)).unwrap() - } -} - -#[stable(feature = "fused", since = "1.26.0")] -impl FusedIterator for Skip where I: FusedIterator {} - -#[unstable(issue = "none", feature = "inplace_iteration")] -unsafe impl SourceIter for Skip -where - I: SourceIter, -{ - type Source = S; - - #[inline] - unsafe fn as_inner(&mut self) -> &mut S { - // SAFETY: unsafe function forwarding to unsafe function with the same requirements - unsafe { SourceIter::as_inner(&mut self.iter) } - } -} - -#[unstable(issue = "none", feature = "inplace_iteration")] -unsafe impl InPlaceIterable for Skip {} - -/// 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`]: Iterator::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 { - pub(super) iter: I, - pub(super) n: usize, -} -impl Take { - pub(super) fn new(iter: I, n: usize) -> Take { - Take { iter, n } - } -} - -#[stable(feature = "rust1", since = "1.0.0")] -impl Iterator for Take -where - I: Iterator, -{ - type Item = ::Item; - - #[inline] - fn next(&mut self) -> Option<::Item> { - if self.n != 0 { - self.n -= 1; - self.iter.next() - } else { - None - } - } - - #[inline] - fn nth(&mut self, n: usize) -> Option { - 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) { - 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(&mut self, init: Acc, fold: Fold) -> R - where - Self: Sized, - Fold: FnMut(Acc, Self::Item) -> R, - R: Try, - { - fn check<'a, T, Acc, R: Try>( - n: &'a mut usize, - mut fold: impl FnMut(Acc, T) -> R + 'a, - ) -> impl FnMut(Acc, T) -> ControlFlow + 'a { - move |acc, x| { - *n -= 1; - let r = fold(acc, x); - if *n == 0 { ControlFlow::Break(r) } else { ControlFlow::from_try(r) } - } - } - - if self.n == 0 { - try { init } - } else { - let n = &mut self.n; - self.iter.try_fold(init, check(n, fold)).into_try() - } - } - - #[inline] - fn fold(mut self, init: Acc, fold: Fold) -> Acc - where - Self: Sized, - Fold: FnMut(Acc, Self::Item) -> Acc, - { - #[inline] - fn ok(mut f: impl FnMut(B, T) -> B) -> impl FnMut(B, T) -> Result { - move |acc, x| Ok(f(acc, x)) - } - - self.try_fold(init, ok(fold)).unwrap() - } -} - -#[unstable(issue = "none", feature = "inplace_iteration")] -unsafe impl SourceIter for Take -where - I: SourceIter, -{ - type Source = S; - - #[inline] - unsafe fn as_inner(&mut self) -> &mut S { - // SAFETY: unsafe function forwarding to unsafe function with the same requirements - unsafe { SourceIter::as_inner(&mut self.iter) } - } -} - -#[unstable(issue = "none", feature = "inplace_iteration")] -unsafe impl InPlaceIterable for Take {} - -#[stable(feature = "double_ended_take_iterator", since = "1.38.0")] -impl DoubleEndedIterator for Take -where - I: DoubleEndedIterator + ExactSizeIterator, -{ - #[inline] - fn next_back(&mut self) -> Option { - if self.n == 0 { - None - } else { - let n = self.n; - self.n -= 1; - self.iter.nth_back(self.iter.len().saturating_sub(n)) - } - } - - #[inline] - fn nth_back(&mut self, n: usize) -> Option { - let len = self.iter.len(); - if self.n > n { - let m = len.saturating_sub(self.n) + n; - self.n -= n + 1; - self.iter.nth_back(m) - } else { - if len > 0 { - self.iter.nth_back(len - 1); - } - None - } - } - - #[inline] - fn try_rfold(&mut self, init: Acc, fold: Fold) -> R - where - Self: Sized, - Fold: FnMut(Acc, Self::Item) -> R, - R: Try, - { - if self.n == 0 { - try { init } - } else { - let len = self.iter.len(); - if len > self.n && self.iter.nth_back(len - self.n - 1).is_none() { - try { init } - } else { - self.iter.try_rfold(init, fold) - } - } - } - - #[inline] - fn rfold(mut self, init: Acc, fold: Fold) -> Acc - where - Self: Sized, - Fold: FnMut(Acc, Self::Item) -> Acc, - { - if self.n == 0 { - init - } else { - let len = self.iter.len(); - if len > self.n && self.iter.nth_back(len - self.n - 1).is_none() { - init - } else { - self.iter.rfold(init, fold) - } - } - } -} - -#[stable(feature = "rust1", since = "1.0.0")] -impl ExactSizeIterator for Take where I: ExactSizeIterator {} - -#[stable(feature = "fused", since = "1.26.0")] -impl FusedIterator for Take where I: FusedIterator {} - -#[unstable(feature = "trusted_len", issue = "37572")] -unsafe impl TrustedLen for Take {} - -/// 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`]: Iterator::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 { - iter: I, - f: F, - state: St, -} -impl Scan { - pub(super) fn new(iter: I, state: St, f: F) -> Scan { - Scan { iter, state, f } - } -} - -#[stable(feature = "core_impl_debug", since = "1.9.0")] -impl fmt::Debug for Scan { - 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 Iterator for Scan -where - I: Iterator, - F: FnMut(&mut St, I::Item) -> Option, -{ - type Item = B; - - #[inline] - fn next(&mut self) -> Option { - let a = self.iter.next()?; - (self.f)(&mut self.state, a) - } - - #[inline] - fn size_hint(&self) -> (usize, Option) { - let (_, upper) = self.iter.size_hint(); - (0, upper) // can't know a lower bound, due to the scan function - } - - #[inline] - fn try_fold(&mut self, init: Acc, fold: Fold) -> R - where - Self: Sized, - Fold: FnMut(Acc, Self::Item) -> R, - R: Try, - { - fn scan<'a, T, St, B, Acc, R: Try>( - state: &'a mut St, - f: &'a mut impl FnMut(&mut St, T) -> Option, - mut fold: impl FnMut(Acc, B) -> R + 'a, - ) -> impl FnMut(Acc, T) -> ControlFlow + 'a { - move |acc, x| match f(state, x) { - None => ControlFlow::Break(try { acc }), - Some(x) => ControlFlow::from_try(fold(acc, x)), - } - } - - let state = &mut self.state; - let f = &mut self.f; - self.iter.try_fold(init, scan(state, f, fold)).into_try() - } - - #[inline] - fn fold(mut self, init: Acc, fold: Fold) -> Acc - where - Self: Sized, - Fold: FnMut(Acc, Self::Item) -> Acc, - { - #[inline] - fn ok(mut f: impl FnMut(B, T) -> B) -> impl FnMut(B, T) -> Result { - move |acc, x| Ok(f(acc, x)) - } - - self.try_fold(init, ok(fold)).unwrap() - } -} - -#[unstable(issue = "none", feature = "inplace_iteration")] -unsafe impl SourceIter for Scan -where - I: SourceIter, - F: FnMut(&mut St, I::Item) -> Option, -{ - type Source = S; - - #[inline] - unsafe fn as_inner(&mut self) -> &mut S { - // SAFETY: unsafe function forwarding to unsafe function with the same requirements - unsafe { SourceIter::as_inner(&mut self.iter) } - } -} - -#[unstable(issue = "none", feature = "inplace_iteration")] -unsafe impl InPlaceIterable for Scan where - F: FnMut(&mut St, I::Item) -> Option -{ -} - -/// 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`]: Iterator::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 { - iter: I, - f: F, -} -impl Inspect { - pub(super) fn new(iter: I, f: F) -> Inspect { - Inspect { iter, f } - } -} - -#[stable(feature = "core_impl_debug", since = "1.9.0")] -impl fmt::Debug for Inspect { - fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { - f.debug_struct("Inspect").field("iter", &self.iter).finish() - } -} - -impl Inspect -where - F: FnMut(&I::Item), -{ - #[inline] - fn do_inspect(&mut self, elt: Option) -> Option { - if let Some(ref a) = elt { - (self.f)(a); - } - - elt - } -} - -fn inspect_fold( - mut f: impl FnMut(&T), - mut fold: impl FnMut(Acc, T) -> Acc, -) -> impl FnMut(Acc, T) -> Acc { - move |acc, item| { - f(&item); - fold(acc, item) - } -} - -fn inspect_try_fold<'a, T, Acc, R>( - f: &'a mut impl FnMut(&T), - mut fold: impl FnMut(Acc, T) -> R + 'a, -) -> impl FnMut(Acc, T) -> R + 'a { - move |acc, item| { - f(&item); - fold(acc, item) - } -} - -#[stable(feature = "rust1", since = "1.0.0")] -impl Iterator for Inspect -where - F: FnMut(&I::Item), -{ - type Item = I::Item; - - #[inline] - fn next(&mut self) -> Option { - let next = self.iter.next(); - self.do_inspect(next) - } - - #[inline] - fn size_hint(&self) -> (usize, Option) { - self.iter.size_hint() - } - - #[inline] - fn try_fold(&mut self, init: Acc, fold: Fold) -> R - where - Self: Sized, - Fold: FnMut(Acc, Self::Item) -> R, - R: Try, - { - self.iter.try_fold(init, inspect_try_fold(&mut self.f, fold)) - } - - #[inline] - fn fold(self, init: Acc, fold: Fold) -> Acc - where - Fold: FnMut(Acc, Self::Item) -> Acc, - { - self.iter.fold(init, inspect_fold(self.f, fold)) - } -} - -#[stable(feature = "rust1", since = "1.0.0")] -impl DoubleEndedIterator for Inspect -where - F: FnMut(&I::Item), -{ - #[inline] - fn next_back(&mut self) -> Option { - let next = self.iter.next_back(); - self.do_inspect(next) - } - - #[inline] - fn try_rfold(&mut self, init: Acc, fold: Fold) -> R - where - Self: Sized, - Fold: FnMut(Acc, Self::Item) -> R, - R: Try, - { - self.iter.try_rfold(init, inspect_try_fold(&mut self.f, fold)) - } - - #[inline] - fn rfold(self, init: Acc, fold: Fold) -> Acc - where - Fold: FnMut(Acc, Self::Item) -> Acc, - { - self.iter.rfold(init, inspect_fold(self.f, fold)) - } -} - -#[stable(feature = "rust1", since = "1.0.0")] -impl ExactSizeIterator for Inspect -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 FusedIterator for Inspect where F: FnMut(&I::Item) {} - -#[unstable(issue = "none", feature = "inplace_iteration")] -unsafe impl SourceIter for Inspect -where - F: FnMut(&I::Item), - I: SourceIter, -{ - type Source = S; - - #[inline] - unsafe fn as_inner(&mut self) -> &mut S { - // SAFETY: unsafe function forwarding to unsafe function with the same requirements - unsafe { SourceIter::as_inner(&mut self.iter) } - } -} - -#[unstable(issue = "none", feature = "inplace_iteration")] -unsafe impl InPlaceIterable for Inspect where F: FnMut(&I::Item) {} - /// An iterator adapter that produces output as long as the underlying /// iterator produces `Result::Ok` values. /// diff --git a/library/core/src/iter/adapters/peekable.rs b/library/core/src/iter/adapters/peekable.rs new file mode 100644 index 00000000000..1822e10bdf6 --- /dev/null +++ b/library/core/src/iter/adapters/peekable.rs @@ -0,0 +1,303 @@ +use crate::{ + iter::{adapters::SourceIter, FusedIterator, InPlaceIterable, TrustedLen}, + ops::Try, +}; + +/// 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`]: Iterator::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 { + iter: I, + /// Remember a peeked value, even if it was None. + peeked: Option>, +} + +impl Peekable { + pub(in crate::iter) fn new(iter: I) -> Peekable { + Peekable { iter, peeked: None } + } +} + +// 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 Iterator for Peekable { + type Item = I::Item; + + #[inline] + fn next(&mut self) -> Option { + 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 { + 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 { + 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) { + 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 = match hi { + Some(x) => x.checked_add(peek_len), + None => None, + }; + (lo, hi) + } + + #[inline] + fn try_fold(&mut self, init: B, mut f: F) -> R + where + Self: Sized, + F: FnMut(B, Self::Item) -> R, + R: Try, + { + let acc = match self.peeked.take() { + Some(None) => return try { init }, + Some(Some(v)) => f(init, v)?, + None => init, + }; + self.iter.try_fold(acc, f) + } + + #[inline] + fn 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 = "double_ended_peek_iterator", since = "1.38.0")] +impl DoubleEndedIterator for Peekable +where + I: DoubleEndedIterator, +{ + #[inline] + fn next_back(&mut self) -> Option { + match self.peeked.as_mut() { + Some(v @ Some(_)) => self.iter.next_back().or_else(|| v.take()), + Some(None) => None, + None => self.iter.next_back(), + } + } + + #[inline] + fn try_rfold(&mut self, init: B, mut f: F) -> R + where + Self: Sized, + F: FnMut(B, Self::Item) -> R, + R: Try, + { + match self.peeked.take() { + Some(None) => try { init }, + Some(Some(v)) => match self.iter.try_rfold(init, &mut f).into_result() { + Ok(acc) => f(acc, v), + Err(e) => { + self.peeked = Some(Some(v)); + Try::from_error(e) + } + }, + None => self.iter.try_rfold(init, f), + } + } + + #[inline] + fn rfold(self, init: Acc, mut fold: Fold) -> Acc + where + Fold: FnMut(Acc, Self::Item) -> Acc, + { + match self.peeked { + Some(None) => init, + Some(Some(v)) => { + let acc = self.iter.rfold(init, &mut fold); + fold(acc, v) + } + None => self.iter.rfold(init, fold), + } + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl ExactSizeIterator for Peekable {} + +#[stable(feature = "fused", since = "1.26.0")] +impl FusedIterator for Peekable {} + +impl Peekable { + /// 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`]: Iterator::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() + } + + /// Consume and return the next value of this iterator if a condition is true. + /// + /// If `func` returns `true` for the next value of this iterator, consume and return it. + /// Otherwise, return `None`. + /// + /// # Examples + /// Consume a number if it's equal to 0. + /// ``` + /// #![feature(peekable_next_if)] + /// let mut iter = (0..5).peekable(); + /// // The first item of the iterator is 0; consume it. + /// assert_eq!(iter.next_if(|&x| x == 0), Some(0)); + /// // The next item returned is now 1, so `consume` will return `false`. + /// assert_eq!(iter.next_if(|&x| x == 0), None); + /// // `next_if` saves the value of the next item if it was not equal to `expected`. + /// assert_eq!(iter.next(), Some(1)); + /// ``` + /// + /// Consume any number less than 10. + /// ``` + /// #![feature(peekable_next_if)] + /// let mut iter = (1..20).peekable(); + /// // Consume all numbers less than 10 + /// while iter.next_if(|&x| x < 10).is_some() {} + /// // The next value returned will be 10 + /// assert_eq!(iter.next(), Some(10)); + /// ``` + #[unstable(feature = "peekable_next_if", issue = "72480")] + pub fn next_if(&mut self, func: impl FnOnce(&I::Item) -> bool) -> Option { + match self.next() { + Some(matched) if func(&matched) => Some(matched), + other => { + // Since we called `self.next()`, we consumed `self.peeked`. + assert!(self.peeked.is_none()); + self.peeked = Some(other); + None + } + } + } + + /// Consume and return the next item if it is equal to `expected`. + /// + /// # Example + /// Consume a number if it's equal to 0. + /// ``` + /// #![feature(peekable_next_if)] + /// let mut iter = (0..5).peekable(); + /// // The first item of the iterator is 0; consume it. + /// assert_eq!(iter.next_if_eq(&0), Some(0)); + /// // The next item returned is now 1, so `consume` will return `false`. + /// assert_eq!(iter.next_if_eq(&0), None); + /// // `next_if_eq` saves the value of the next item if it was not equal to `expected`. + /// assert_eq!(iter.next(), Some(1)); + /// ``` + #[unstable(feature = "peekable_next_if", issue = "72480")] + pub fn next_if_eq(&mut self, expected: &T) -> Option + where + T: ?Sized, + I::Item: PartialEq, + { + self.next_if(|next| next == expected) + } +} + +#[unstable(feature = "trusted_len", issue = "37572")] +unsafe impl TrustedLen for Peekable where I: TrustedLen {} + +#[unstable(issue = "none", feature = "inplace_iteration")] +unsafe impl SourceIter for Peekable +where + I: SourceIter, +{ + type Source = S; + + #[inline] + unsafe fn as_inner(&mut self) -> &mut S { + // SAFETY: unsafe function forwarding to unsafe function with the same requirements + unsafe { SourceIter::as_inner(&mut self.iter) } + } +} + +#[unstable(issue = "none", feature = "inplace_iteration")] +unsafe impl InPlaceIterable for Peekable {} diff --git a/library/core/src/iter/adapters/rev.rs b/library/core/src/iter/adapters/rev.rs new file mode 100644 index 00000000000..48ec0a80ad9 --- /dev/null +++ b/library/core/src/iter/adapters/rev.rs @@ -0,0 +1,139 @@ +use crate::{ + iter::{FusedIterator, TrustedLen}, + ops::Try, +}; + +/// A double-ended iterator with the direction inverted. +/// +/// This `struct` is created by the [`rev`] method on [`Iterator`]. See its +/// documentation for more. +/// +/// [`rev`]: Iterator::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 { + iter: T, +} + +impl Rev { + pub(in crate::iter) fn new(iter: T) -> Rev { + Rev { iter } + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl Iterator for Rev +where + I: DoubleEndedIterator, +{ + type Item = ::Item; + + #[inline] + fn next(&mut self) -> Option<::Item> { + self.iter.next_back() + } + #[inline] + fn size_hint(&self) -> (usize, Option) { + self.iter.size_hint() + } + + #[inline] + fn advance_by(&mut self, n: usize) -> Result<(), usize> { + self.iter.advance_back_by(n) + } + + #[inline] + fn nth(&mut self, n: usize) -> Option<::Item> { + self.iter.nth_back(n) + } + + fn try_fold(&mut self, init: B, f: F) -> R + where + Self: Sized, + F: FnMut(B, Self::Item) -> R, + R: Try, + { + self.iter.try_rfold(init, f) + } + + fn fold(self, init: Acc, f: F) -> Acc + where + F: FnMut(Acc, Self::Item) -> Acc, + { + self.iter.rfold(init, f) + } + + #[inline] + fn find

(&mut self, predicate: P) -> Option + where + P: FnMut(&Self::Item) -> bool, + { + self.iter.rfind(predicate) + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl DoubleEndedIterator for Rev +where + I: DoubleEndedIterator, +{ + #[inline] + fn next_back(&mut self) -> Option<::Item> { + self.iter.next() + } + + #[inline] + fn advance_back_by(&mut self, n: usize) -> Result<(), usize> { + self.iter.advance_by(n) + } + + #[inline] + fn nth_back(&mut self, n: usize) -> Option<::Item> { + self.iter.nth(n) + } + + fn try_rfold(&mut self, init: B, f: F) -> R + where + Self: Sized, + F: FnMut(B, Self::Item) -> R, + R: Try, + { + self.iter.try_fold(init, f) + } + + fn rfold(self, init: Acc, f: F) -> Acc + where + F: FnMut(Acc, Self::Item) -> Acc, + { + self.iter.fold(init, f) + } + + fn rfind

(&mut self, predicate: P) -> Option + where + P: FnMut(&Self::Item) -> bool, + { + self.iter.find(predicate) + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl ExactSizeIterator for Rev +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 FusedIterator for Rev where I: FusedIterator + DoubleEndedIterator {} + +#[unstable(feature = "trusted_len", issue = "37572")] +unsafe impl TrustedLen for Rev where I: TrustedLen + DoubleEndedIterator {} diff --git a/library/core/src/iter/adapters/scan.rs b/library/core/src/iter/adapters/scan.rs new file mode 100644 index 00000000000..12c11419c70 --- /dev/null +++ b/library/core/src/iter/adapters/scan.rs @@ -0,0 +1,113 @@ +use crate::{ + fmt, + iter::{adapters::SourceIter, InPlaceIterable}, + ops::{ControlFlow, Try}, +}; + +/// 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`]: Iterator::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 { + iter: I, + f: F, + state: St, +} + +impl Scan { + pub(in crate::iter) fn new(iter: I, state: St, f: F) -> Scan { + Scan { iter, state, f } + } +} + +#[stable(feature = "core_impl_debug", since = "1.9.0")] +impl fmt::Debug for Scan { + 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 Iterator for Scan +where + I: Iterator, + F: FnMut(&mut St, I::Item) -> Option, +{ + type Item = B; + + #[inline] + fn next(&mut self) -> Option { + let a = self.iter.next()?; + (self.f)(&mut self.state, a) + } + + #[inline] + fn size_hint(&self) -> (usize, Option) { + let (_, upper) = self.iter.size_hint(); + (0, upper) // can't know a lower bound, due to the scan function + } + + #[inline] + fn try_fold(&mut self, init: Acc, fold: Fold) -> R + where + Self: Sized, + Fold: FnMut(Acc, Self::Item) -> R, + R: Try, + { + fn scan<'a, T, St, B, Acc, R: Try>( + state: &'a mut St, + f: &'a mut impl FnMut(&mut St, T) -> Option, + mut fold: impl FnMut(Acc, B) -> R + 'a, + ) -> impl FnMut(Acc, T) -> ControlFlow + 'a { + move |acc, x| match f(state, x) { + None => ControlFlow::Break(try { acc }), + Some(x) => ControlFlow::from_try(fold(acc, x)), + } + } + + let state = &mut self.state; + let f = &mut self.f; + self.iter.try_fold(init, scan(state, f, fold)).into_try() + } + + #[inline] + fn fold(mut self, init: Acc, fold: Fold) -> Acc + where + Self: Sized, + Fold: FnMut(Acc, Self::Item) -> Acc, + { + #[inline] + fn ok(mut f: impl FnMut(B, T) -> B) -> impl FnMut(B, T) -> Result { + move |acc, x| Ok(f(acc, x)) + } + + self.try_fold(init, ok(fold)).unwrap() + } +} + +#[unstable(issue = "none", feature = "inplace_iteration")] +unsafe impl SourceIter for Scan +where + I: SourceIter, + F: FnMut(&mut St, I::Item) -> Option, +{ + type Source = S; + + #[inline] + unsafe fn as_inner(&mut self) -> &mut S { + // SAFETY: unsafe function forwarding to unsafe function with the same requirements + unsafe { SourceIter::as_inner(&mut self.iter) } + } +} + +#[unstable(issue = "none", feature = "inplace_iteration")] +unsafe impl InPlaceIterable for Scan where + F: FnMut(&mut St, I::Item) -> Option +{ +} diff --git a/library/core/src/iter/adapters/skip.rs b/library/core/src/iter/adapters/skip.rs new file mode 100644 index 00000000000..ff2d07c0c0d --- /dev/null +++ b/library/core/src/iter/adapters/skip.rs @@ -0,0 +1,201 @@ +use crate::{ + iter::{adapters::SourceIter, FusedIterator, InPlaceIterable}, + ops::{ControlFlow, Try}, +}; + +/// 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`]: Iterator::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 { + iter: I, + n: usize, +} + +impl Skip { + pub(in crate::iter) fn new(iter: I, n: usize) -> Skip { + Skip { iter, n } + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl Iterator for Skip +where + I: Iterator, +{ + type Item = ::Item; + + #[inline] + fn next(&mut self) -> Option { + 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 { + // Can't just add n + self.n due to overflow. + if self.n > 0 { + let to_skip = self.n; + self.n = 0; + // nth(n) skips n+1 + self.iter.nth(to_skip - 1)?; + } + self.iter.nth(n) + } + + #[inline] + fn count(mut self) -> usize { + if self.n > 0 { + // nth(n) skips n+1 + if self.iter.nth(self.n - 1).is_none() { + return 0; + } + } + self.iter.count() + } + + #[inline] + fn last(mut self) -> Option { + if self.n > 0 { + // nth(n) skips n+1 + self.iter.nth(self.n - 1)?; + } + self.iter.last() + } + + #[inline] + fn size_hint(&self) -> (usize, Option) { + let (lower, upper) = self.iter.size_hint(); + + let lower = lower.saturating_sub(self.n); + let upper = match upper { + Some(x) => Some(x.saturating_sub(self.n)), + None => None, + }; + + (lower, upper) + } + + #[inline] + fn try_fold(&mut self, init: Acc, fold: Fold) -> R + where + Self: Sized, + Fold: FnMut(Acc, Self::Item) -> R, + R: Try, + { + 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 { init }; + } + } + self.iter.try_fold(init, fold) + } + + #[inline] + fn 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 ExactSizeIterator for Skip where I: ExactSizeIterator {} + +#[stable(feature = "double_ended_skip_iterator", since = "1.9.0")] +impl DoubleEndedIterator for Skip +where + I: DoubleEndedIterator + ExactSizeIterator, +{ + fn next_back(&mut self) -> Option { + if self.len() > 0 { self.iter.next_back() } else { None } + } + + #[inline] + fn nth_back(&mut self, n: usize) -> Option { + let len = self.len(); + if n < len { + self.iter.nth_back(n) + } else { + if len > 0 { + // consume the original iterator + self.iter.nth_back(len - 1); + } + None + } + } + + fn try_rfold(&mut self, init: Acc, fold: Fold) -> R + where + Self: Sized, + Fold: FnMut(Acc, Self::Item) -> R, + R: Try, + { + fn check>( + mut n: usize, + mut fold: impl FnMut(Acc, T) -> R, + ) -> impl FnMut(Acc, T) -> ControlFlow { + move |acc, x| { + n -= 1; + let r = fold(acc, x); + if n == 0 { ControlFlow::Break(r) } else { ControlFlow::from_try(r) } + } + } + + let n = self.len(); + if n == 0 { try { init } } else { self.iter.try_rfold(init, check(n, fold)).into_try() } + } + + fn rfold(mut self, init: Acc, fold: Fold) -> Acc + where + Fold: FnMut(Acc, Self::Item) -> Acc, + { + #[inline] + fn ok(mut f: impl FnMut(Acc, T) -> Acc) -> impl FnMut(Acc, T) -> Result { + move |acc, x| Ok(f(acc, x)) + } + + self.try_rfold(init, ok(fold)).unwrap() + } +} + +#[stable(feature = "fused", since = "1.26.0")] +impl FusedIterator for Skip where I: FusedIterator {} + +#[unstable(issue = "none", feature = "inplace_iteration")] +unsafe impl SourceIter for Skip +where + I: SourceIter, +{ + type Source = S; + + #[inline] + unsafe fn as_inner(&mut self) -> &mut S { + // SAFETY: unsafe function forwarding to unsafe function with the same requirements + unsafe { SourceIter::as_inner(&mut self.iter) } + } +} + +#[unstable(issue = "none", feature = "inplace_iteration")] +unsafe impl InPlaceIterable for Skip {} diff --git a/library/core/src/iter/adapters/skip_while.rs b/library/core/src/iter/adapters/skip_while.rs new file mode 100644 index 00000000000..cda8f9188d2 --- /dev/null +++ b/library/core/src/iter/adapters/skip_while.rs @@ -0,0 +1,128 @@ +use crate::{ + fmt, + iter::{adapters::SourceIter, FusedIterator, InPlaceIterable}, + ops::Try, +}; + +/// An iterator that rejects elements while `predicate` returns `true`. +/// +/// This `struct` is created by the [`skip_while`] method on [`Iterator`]. See its +/// documentation for more. +/// +/// [`skip_while`]: Iterator::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 { + iter: I, + flag: bool, + predicate: P, +} + +impl SkipWhile { + pub(in crate::iter) fn new(iter: I, predicate: P) -> SkipWhile { + SkipWhile { iter, flag: false, predicate } + } +} + +#[stable(feature = "core_impl_debug", since = "1.9.0")] +impl fmt::Debug for SkipWhile { + 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 Iterator for SkipWhile +where + P: FnMut(&I::Item) -> bool, +{ + type Item = I::Item; + + #[inline] + fn next(&mut self) -> Option { + fn check<'a, T>( + flag: &'a mut bool, + pred: &'a mut impl FnMut(&T) -> bool, + ) -> impl FnMut(&T) -> bool + 'a { + move |x| { + if *flag || !pred(x) { + *flag = true; + true + } else { + false + } + } + } + + let flag = &mut self.flag; + let pred = &mut self.predicate; + self.iter.find(check(flag, pred)) + } + + #[inline] + fn size_hint(&self) -> (usize, Option) { + let (_, upper) = self.iter.size_hint(); + (0, upper) // can't know a lower bound, due to the predicate + } + + #[inline] + fn try_fold(&mut self, mut init: Acc, mut fold: Fold) -> R + where + Self: Sized, + Fold: FnMut(Acc, Self::Item) -> R, + R: Try, + { + if !self.flag { + match self.next() { + Some(v) => init = fold(init, v)?, + None => return try { init }, + } + } + self.iter.try_fold(init, fold) + } + + #[inline] + fn 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 FusedIterator for SkipWhile +where + I: FusedIterator, + P: FnMut(&I::Item) -> bool, +{ +} + +#[unstable(issue = "none", feature = "inplace_iteration")] +unsafe impl SourceIter for SkipWhile +where + P: FnMut(&I::Item) -> bool, + I: SourceIter, +{ + type Source = S; + + #[inline] + unsafe fn as_inner(&mut self) -> &mut S { + // SAFETY: unsafe function forwarding to unsafe function with the same requirements + unsafe { SourceIter::as_inner(&mut self.iter) } + } +} + +#[unstable(issue = "none", feature = "inplace_iteration")] +unsafe impl InPlaceIterable for SkipWhile where + F: FnMut(&I::Item) -> bool +{ +} diff --git a/library/core/src/iter/adapters/step_by.rs b/library/core/src/iter/adapters/step_by.rs new file mode 100644 index 00000000000..2ba56eeccba --- /dev/null +++ b/library/core/src/iter/adapters/step_by.rs @@ -0,0 +1,235 @@ +use crate::{intrinsics, iter::from_fn, ops::Try}; + +/// 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`]: Iterator::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 { + iter: I, + step: usize, + first_take: bool, +} + +impl StepBy { + pub(in crate::iter) fn new(iter: I, step: usize) -> StepBy { + assert!(step != 0); + StepBy { iter, step: step - 1, first_take: true } + } +} + +#[stable(feature = "iterator_step_by", since = "1.28.0")] +impl Iterator for StepBy +where + I: Iterator, +{ + type Item = I::Item; + + #[inline] + fn next(&mut self) -> Option { + if self.first_take { + self.first_take = false; + self.iter.next() + } else { + self.iter.nth(self.step) + } + } + + #[inline] + fn size_hint(&self) -> (usize, Option) { + #[inline] + fn first_size(step: usize) -> impl Fn(usize) -> usize { + move |n| if n == 0 { 0 } else { 1 + (n - 1) / (step + 1) } + } + + #[inline] + fn other_size(step: usize) -> impl Fn(usize) -> usize { + move |n| n / (step + 1) + } + + let (low, high) = self.iter.size_hint(); + + if self.first_take { + let f = first_size(self.step); + (f(low), high.map(f)) + } else { + let f = other_size(self.step); + (f(low), high.map(f)) + } + } + + #[inline] + fn nth(&mut self, mut n: usize) -> Option { + 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 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); + } + } + + fn try_fold(&mut self, mut acc: Acc, mut f: F) -> R + where + F: FnMut(Acc, Self::Item) -> R, + R: Try, + { + #[inline] + fn nth(iter: &mut I, step: usize) -> impl FnMut() -> Option + '_ { + move || iter.nth(step) + } + + if self.first_take { + self.first_take = false; + match self.iter.next() { + None => return try { acc }, + Some(x) => acc = f(acc, x)?, + } + } + from_fn(nth(&mut self.iter, self.step)).try_fold(acc, f) + } + + fn fold(mut self, mut acc: Acc, mut f: F) -> Acc + where + F: FnMut(Acc, Self::Item) -> Acc, + { + #[inline] + fn nth(iter: &mut I, step: usize) -> impl FnMut() -> Option + '_ { + move || iter.nth(step) + } + + if self.first_take { + self.first_take = false; + match self.iter.next() { + None => return acc, + Some(x) => acc = f(acc, x), + } + } + from_fn(nth(&mut self.iter, self.step)).fold(acc, f) + } +} + +impl StepBy +where + I: ExactSizeIterator, +{ + // The zero-based index starting from the end of the iterator of the + // last element. Used in the `DoubleEndedIterator` implementation. + fn next_back_index(&self) -> usize { + let rem = self.iter.len() % (self.step + 1); + if self.first_take { + if rem == 0 { self.step } else { rem - 1 } + } else { + rem + } + } +} + +#[stable(feature = "double_ended_step_by_iterator", since = "1.38.0")] +impl DoubleEndedIterator for StepBy +where + I: DoubleEndedIterator + ExactSizeIterator, +{ + #[inline] + fn next_back(&mut self) -> Option { + self.iter.nth_back(self.next_back_index()) + } + + #[inline] + fn nth_back(&mut self, n: usize) -> Option { + // `self.iter.nth_back(usize::MAX)` does the right thing here when `n` + // is out of bounds because the length of `self.iter` does not exceed + // `usize::MAX` (because `I: ExactSizeIterator`) and `nth_back` is + // zero-indexed + let n = n.saturating_mul(self.step + 1).saturating_add(self.next_back_index()); + self.iter.nth_back(n) + } + + fn try_rfold(&mut self, init: Acc, mut f: F) -> R + where + F: FnMut(Acc, Self::Item) -> R, + R: Try, + { + #[inline] + fn nth_back( + iter: &mut I, + step: usize, + ) -> impl FnMut() -> Option + '_ { + move || iter.nth_back(step) + } + + match self.next_back() { + None => try { init }, + Some(x) => { + let acc = f(init, x)?; + from_fn(nth_back(&mut self.iter, self.step)).try_fold(acc, f) + } + } + } + + #[inline] + fn rfold(mut self, init: Acc, mut f: F) -> Acc + where + Self: Sized, + F: FnMut(Acc, Self::Item) -> Acc, + { + #[inline] + fn nth_back( + iter: &mut I, + step: usize, + ) -> impl FnMut() -> Option + '_ { + move || iter.nth_back(step) + } + + match self.next_back() { + None => init, + Some(x) => { + let acc = f(init, x); + from_fn(nth_back(&mut self.iter, self.step)).fold(acc, f) + } + } + } +} + +// StepBy can only make the iterator shorter, so the len will still fit. +#[stable(feature = "iterator_step_by", since = "1.28.0")] +impl ExactSizeIterator for StepBy where I: ExactSizeIterator {} diff --git a/library/core/src/iter/adapters/take.rs b/library/core/src/iter/adapters/take.rs new file mode 100644 index 00000000000..982dbfcba3a --- /dev/null +++ b/library/core/src/iter/adapters/take.rs @@ -0,0 +1,211 @@ +use crate::{ + cmp, iter::FusedIterator, iter::InPlaceIterable, iter::TrustedLen, ops::ControlFlow, ops::Try, +}; + +use super::SourceIter; + +/// 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`]: Iterator::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 { + iter: I, + n: usize, +} + +impl Take { + pub(in crate::iter) fn new(iter: I, n: usize) -> Take { + Take { iter, n } + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl Iterator for Take +where + I: Iterator, +{ + type Item = ::Item; + + #[inline] + fn next(&mut self) -> Option<::Item> { + if self.n != 0 { + self.n -= 1; + self.iter.next() + } else { + None + } + } + + #[inline] + fn nth(&mut self, n: usize) -> Option { + 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) { + 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(&mut self, init: Acc, fold: Fold) -> R + where + Self: Sized, + Fold: FnMut(Acc, Self::Item) -> R, + R: Try, + { + fn check<'a, T, Acc, R: Try>( + n: &'a mut usize, + mut fold: impl FnMut(Acc, T) -> R + 'a, + ) -> impl FnMut(Acc, T) -> ControlFlow + 'a { + move |acc, x| { + *n -= 1; + let r = fold(acc, x); + if *n == 0 { ControlFlow::Break(r) } else { ControlFlow::from_try(r) } + } + } + + if self.n == 0 { + try { init } + } else { + let n = &mut self.n; + self.iter.try_fold(init, check(n, fold)).into_try() + } + } + + #[inline] + fn fold(mut self, init: Acc, fold: Fold) -> Acc + where + Self: Sized, + Fold: FnMut(Acc, Self::Item) -> Acc, + { + #[inline] + fn ok(mut f: impl FnMut(B, T) -> B) -> impl FnMut(B, T) -> Result { + move |acc, x| Ok(f(acc, x)) + } + + self.try_fold(init, ok(fold)).unwrap() + } +} + +#[unstable(issue = "none", feature = "inplace_iteration")] +unsafe impl SourceIter for Take +where + I: SourceIter, +{ + type Source = S; + + #[inline] + unsafe fn as_inner(&mut self) -> &mut S { + // SAFETY: unsafe function forwarding to unsafe function with the same requirements + unsafe { SourceIter::as_inner(&mut self.iter) } + } +} + +#[unstable(issue = "none", feature = "inplace_iteration")] +unsafe impl InPlaceIterable for Take {} + +#[stable(feature = "double_ended_take_iterator", since = "1.38.0")] +impl DoubleEndedIterator for Take +where + I: DoubleEndedIterator + ExactSizeIterator, +{ + #[inline] + fn next_back(&mut self) -> Option { + if self.n == 0 { + None + } else { + let n = self.n; + self.n -= 1; + self.iter.nth_back(self.iter.len().saturating_sub(n)) + } + } + + #[inline] + fn nth_back(&mut self, n: usize) -> Option { + let len = self.iter.len(); + if self.n > n { + let m = len.saturating_sub(self.n) + n; + self.n -= n + 1; + self.iter.nth_back(m) + } else { + if len > 0 { + self.iter.nth_back(len - 1); + } + None + } + } + + #[inline] + fn try_rfold(&mut self, init: Acc, fold: Fold) -> R + where + Self: Sized, + Fold: FnMut(Acc, Self::Item) -> R, + R: Try, + { + if self.n == 0 { + try { init } + } else { + let len = self.iter.len(); + if len > self.n && self.iter.nth_back(len - self.n - 1).is_none() { + try { init } + } else { + self.iter.try_rfold(init, fold) + } + } + } + + #[inline] + fn rfold(mut self, init: Acc, fold: Fold) -> Acc + where + Self: Sized, + Fold: FnMut(Acc, Self::Item) -> Acc, + { + if self.n == 0 { + init + } else { + let len = self.iter.len(); + if len > self.n && self.iter.nth_back(len - self.n - 1).is_none() { + init + } else { + self.iter.rfold(init, fold) + } + } + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl ExactSizeIterator for Take where I: ExactSizeIterator {} + +#[stable(feature = "fused", since = "1.26.0")] +impl FusedIterator for Take where I: FusedIterator {} + +#[unstable(feature = "trusted_len", issue = "37572")] +unsafe impl TrustedLen for Take {} diff --git a/library/core/src/iter/adapters/take_while.rs b/library/core/src/iter/adapters/take_while.rs new file mode 100644 index 00000000000..aae0b20b83c --- /dev/null +++ b/library/core/src/iter/adapters/take_while.rs @@ -0,0 +1,141 @@ +use crate::{ + fmt, + iter::{adapters::SourceIter, FusedIterator, InPlaceIterable}, + ops::{ControlFlow, Try}, +}; + +/// An iterator that only accepts elements while `predicate` returns `true`. +/// +/// This `struct` is created by the [`take_while`] method on [`Iterator`]. See its +/// documentation for more. +/// +/// [`take_while`]: Iterator::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 { + iter: I, + flag: bool, + predicate: P, +} + +impl TakeWhile { + pub(in crate::iter) fn new(iter: I, predicate: P) -> TakeWhile { + TakeWhile { iter, flag: false, predicate } + } +} + +#[stable(feature = "core_impl_debug", since = "1.9.0")] +impl fmt::Debug for TakeWhile { + 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 Iterator for TakeWhile +where + P: FnMut(&I::Item) -> bool, +{ + type Item = I::Item; + + #[inline] + fn next(&mut self) -> Option { + if self.flag { + None + } else { + let x = self.iter.next()?; + if (self.predicate)(&x) { + Some(x) + } else { + self.flag = true; + None + } + } + } + + #[inline] + fn size_hint(&self) -> (usize, Option) { + 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(&mut self, init: Acc, fold: Fold) -> R + where + Self: Sized, + Fold: FnMut(Acc, Self::Item) -> R, + R: Try, + { + fn check<'a, T, Acc, R: Try>( + flag: &'a mut bool, + p: &'a mut impl FnMut(&T) -> bool, + mut fold: impl FnMut(Acc, T) -> R + 'a, + ) -> impl FnMut(Acc, T) -> ControlFlow + 'a { + move |acc, x| { + if p(&x) { + ControlFlow::from_try(fold(acc, x)) + } else { + *flag = true; + ControlFlow::Break(try { acc }) + } + } + } + + if self.flag { + try { init } + } else { + let flag = &mut self.flag; + let p = &mut self.predicate; + self.iter.try_fold(init, check(flag, p, fold)).into_try() + } + } + + #[inline] + fn fold(mut self, init: Acc, fold: Fold) -> Acc + where + Self: Sized, + Fold: FnMut(Acc, Self::Item) -> Acc, + { + #[inline] + fn ok(mut f: impl FnMut(B, T) -> B) -> impl FnMut(B, T) -> Result { + move |acc, x| Ok(f(acc, x)) + } + + self.try_fold(init, ok(fold)).unwrap() + } +} + +#[stable(feature = "fused", since = "1.26.0")] +impl FusedIterator for TakeWhile +where + I: FusedIterator, + P: FnMut(&I::Item) -> bool, +{ +} + +#[unstable(issue = "none", feature = "inplace_iteration")] +unsafe impl SourceIter for TakeWhile +where + P: FnMut(&I::Item) -> bool, + I: SourceIter, +{ + type Source = S; + + #[inline] + unsafe fn as_inner(&mut self) -> &mut S { + // SAFETY: unsafe function forwarding to unsafe function with the same requirements + unsafe { SourceIter::as_inner(&mut self.iter) } + } +} + +#[unstable(issue = "none", feature = "inplace_iteration")] +unsafe impl InPlaceIterable for TakeWhile where + F: FnMut(&I::Item) -> bool +{ +} diff --git a/library/core/src/iter/adapters/zip.rs b/library/core/src/iter/adapters/zip.rs index 78712988eae..fdc4035a612 100644 --- a/library/core/src/iter/adapters/zip.rs +++ b/library/core/src/iter/adapters/zip.rs @@ -1,9 +1,10 @@ -use crate::cmp; -use crate::fmt::{self, Debug}; - -use super::super::{ - DoubleEndedIterator, ExactSizeIterator, FusedIterator, InPlaceIterable, Iterator, SourceIter, - TrustedLen, +use crate::{ + cmp, + fmt::{self, Debug}, + iter::{ + DoubleEndedIterator, ExactSizeIterator, FusedIterator, InPlaceIterable, Iterator, + SourceIter, TrustedLen, + }, }; /// An iterator that iterates two other iterators simultaneously. @@ -21,7 +22,7 @@ pub struct Zip { len: usize, } impl Zip { - pub(in super::super) fn new(a: A, b: B) -> Zip { + pub(in crate::iter) fn new(a: A, b: B) -> Zip { ZipImpl::new(a, b) } fn super_nth(&mut self, mut n: usize) -> Option<(A::Item, B::Item)> { -- 2.44.0