#![stable(feature = "rust1", since = "1.0.0")]
use cmp;
use fmt;
use iter_private::TrustedRandomAccess;
use ops::Try;
use usize;
use intrinsics;
#[stable(feature = "rust1", since = "1.0.0")]
pub use self::iterator::Iterator;
#[unstable(feature = "step_trait",
reason = "likely to be replaced by finer-grained traits",
issue = "42168")]
pub use self::range::Step;
#[stable(feature = "rust1", since = "1.0.0")]
pub use self::sources::{Repeat, repeat};
#[stable(feature = "iterator_repeat_with", since = "1.28.0")]
pub use self::sources::{RepeatWith, repeat_with};
#[stable(feature = "iter_empty", since = "1.2.0")]
pub use self::sources::{Empty, empty};
#[stable(feature = "iter_once", since = "1.2.0")]
pub use self::sources::{Once, once};
#[unstable(feature = "iter_unfold", issue = "55977")]
pub use self::sources::{Unfold, unfold, Successors, successors};
#[stable(feature = "rust1", since = "1.0.0")]
pub use self::traits::{FromIterator, IntoIterator, DoubleEndedIterator, Extend};
#[stable(feature = "rust1", since = "1.0.0")]
pub use self::traits::{ExactSizeIterator, Sum, Product};
#[stable(feature = "fused", since = "1.26.0")]
pub use self::traits::FusedIterator;
#[unstable(feature = "trusted_len", issue = "37572")]
pub use self::traits::TrustedLen;
mod iterator;
mod range;
mod sources;
mod traits;
#[derive(PartialEq)]
enum LoopState<C, B> {
Continue(C),
Break(B),
}
impl<C, B> Try for LoopState<C, B> {
type Ok = C;
type Error = B;
#[inline]
fn into_result(self) -> Result<Self::Ok, Self::Error> {
match self {
LoopState::Continue(y) => Ok(y),
LoopState::Break(x) => Err(x),
}
}
#[inline]
fn from_error(v: Self::Error) -> Self { LoopState::Break(v) }
#[inline]
fn from_ok(v: Self::Ok) -> Self { LoopState::Continue(v) }
}
impl<C, B> LoopState<C, B> {
#[inline]
fn break_value(self) -> Option<B> {
match self {
LoopState::Continue(..) => None,
LoopState::Break(x) => Some(x),
}
}
}
impl<R: Try> LoopState<R::Ok, R> {
#[inline]
fn from_try(r: R) -> Self {
match Try::into_result(r) {
Ok(v) => LoopState::Continue(v),
Err(v) => LoopState::Break(Try::from_error(v)),
}
}
#[inline]
fn into_try(self) -> R {
match self {
LoopState::Continue(v) => Try::from_ok(v),
LoopState::Break(v) => v,
}
}
}
#[derive(Clone, Debug)]
#[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
#[stable(feature = "rust1", since = "1.0.0")]
pub struct Rev<T> {
iter: T
}
#[stable(feature = "rust1", since = "1.0.0")]
impl<I> Iterator for Rev<I> where I: DoubleEndedIterator {
type Item = <I as Iterator>::Item;
#[inline]
fn next(&mut self) -> Option<<I as Iterator>::Item> { self.iter.next_back() }
#[inline]
fn size_hint(&self) -> (usize, Option<usize>) { self.iter.size_hint() }
fn try_fold<B, F, R>(&mut self, init: B, f: F) -> R where
Self: Sized, F: FnMut(B, Self::Item) -> R, R: Try<Ok=B>
{
self.iter.try_rfold(init, f)
}
fn fold<Acc, F>(self, init: Acc, f: F) -> Acc
where F: FnMut(Acc, Self::Item) -> Acc,
{
self.iter.rfold(init, f)
}
#[inline]
fn find<P>(&mut self, predicate: P) -> Option<Self::Item>
where P: FnMut(&Self::Item) -> bool
{
self.iter.rfind(predicate)
}
#[inline]
fn rposition<P>(&mut self, predicate: P) -> Option<usize> where
P: FnMut(Self::Item) -> bool
{
self.iter.position(predicate)
}
}
#[stable(feature = "rust1", since = "1.0.0")]
impl<I> DoubleEndedIterator for Rev<I> where I: DoubleEndedIterator {
#[inline]
fn next_back(&mut self) -> Option<<I as Iterator>::Item> { self.iter.next() }
fn try_rfold<B, F, R>(&mut self, init: B, f: F) -> R where
Self: Sized, F: FnMut(B, Self::Item) -> R, R: Try<Ok=B>
{
self.iter.try_fold(init, f)
}
fn rfold<Acc, F>(self, init: Acc, f: F) -> Acc
where F: FnMut(Acc, Self::Item) -> Acc,
{
self.iter.fold(init, f)
}
fn rfind<P>(&mut self, predicate: P) -> Option<Self::Item>
where P: FnMut(&Self::Item) -> bool
{
self.iter.find(predicate)
}
}
#[stable(feature = "rust1", since = "1.0.0")]
impl<I> ExactSizeIterator for Rev<I>
where I: ExactSizeIterator + DoubleEndedIterator
{
fn len(&self) -> usize {
self.iter.len()
}
fn is_empty(&self) -> bool {
self.iter.is_empty()
}
}
#[stable(feature = "fused", since = "1.26.0")]
impl<I> FusedIterator for Rev<I>
where I: FusedIterator + DoubleEndedIterator {}
#[unstable(feature = "trusted_len", issue = "37572")]
unsafe impl<I> TrustedLen for Rev<I>
where I: TrustedLen + DoubleEndedIterator {}
#[stable(feature = "iter_cloned", since = "1.1.0")]
#[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
#[derive(Clone, Debug)]
pub struct Cloned<I> {
it: I,
}
#[stable(feature = "iter_cloned", since = "1.1.0")]
impl<'a, I, T: 'a> Iterator for Cloned<I>
where I: Iterator<Item=&'a T>, T: Clone
{
type Item = T;
fn next(&mut self) -> Option<T> {
self.it.next().cloned()
}
fn size_hint(&self) -> (usize, Option<usize>) {
self.it.size_hint()
}
fn try_fold<B, F, R>(&mut self, init: B, mut f: F) -> R where
Self: Sized, F: FnMut(B, Self::Item) -> R, R: Try<Ok=B>
{
self.it.try_fold(init, move |acc, elt| f(acc, elt.clone()))
}
fn fold<Acc, F>(self, init: Acc, mut f: F) -> Acc
where F: FnMut(Acc, Self::Item) -> Acc,
{
self.it.fold(init, move |acc, elt| f(acc, elt.clone()))
}
}
#[stable(feature = "iter_cloned", since = "1.1.0")]
impl<'a, I, T: 'a> DoubleEndedIterator for Cloned<I>
where I: DoubleEndedIterator<Item=&'a T>, T: Clone
{
fn next_back(&mut self) -> Option<T> {
self.it.next_back().cloned()
}
fn try_rfold<B, F, R>(&mut self, init: B, mut f: F) -> R where
Self: Sized, F: FnMut(B, Self::Item) -> R, R: Try<Ok=B>
{
self.it.try_rfold(init, move |acc, elt| f(acc, elt.clone()))
}
fn rfold<Acc, F>(self, init: Acc, mut f: F) -> Acc
where F: FnMut(Acc, Self::Item) -> Acc,
{
self.it.rfold(init, move |acc, elt| f(acc, elt.clone()))
}
}
#[stable(feature = "iter_cloned", since = "1.1.0")]
impl<'a, I, T: 'a> ExactSizeIterator for Cloned<I>
where I: ExactSizeIterator<Item=&'a T>, T: Clone
{
fn len(&self) -> usize {
self.it.len()
}
fn is_empty(&self) -> bool {
self.it.is_empty()
}
}
#[stable(feature = "fused", since = "1.26.0")]
impl<'a, I, T: 'a> FusedIterator for Cloned<I>
where I: FusedIterator<Item=&'a T>, T: Clone
{}
#[doc(hidden)]
unsafe impl<'a, I, T: 'a> TrustedRandomAccess for Cloned<I>
where I: TrustedRandomAccess<Item=&'a T>, T: Clone
{
default unsafe fn get_unchecked(&mut self, i: usize) -> Self::Item {
self.it.get_unchecked(i).clone()
}
#[inline]
default fn may_have_side_effect() -> bool { true }
}
#[doc(hidden)]
unsafe impl<'a, I, T: 'a> TrustedRandomAccess for Cloned<I>
where I: TrustedRandomAccess<Item=&'a T>, T: Copy
{
unsafe fn get_unchecked(&mut self, i: usize) -> Self::Item {
*self.it.get_unchecked(i)
}
#[inline]
fn may_have_side_effect() -> bool { false }
}
#[unstable(feature = "trusted_len", issue = "37572")]
unsafe impl<'a, I, T: 'a> TrustedLen for Cloned<I>
where I: TrustedLen<Item=&'a T>,
T: Clone
{}
#[derive(Clone, Debug)]
#[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
#[stable(feature = "rust1", since = "1.0.0")]
pub struct Cycle<I> {
orig: I,
iter: I,
}
#[stable(feature = "rust1", since = "1.0.0")]
impl<I> Iterator for Cycle<I> where I: Clone + Iterator {
type Item = <I as Iterator>::Item;
#[inline]
fn next(&mut self) -> Option<<I as Iterator>::Item> {
match self.iter.next() {
None => { self.iter = self.orig.clone(); self.iter.next() }
y => y
}
}
#[inline]
fn size_hint(&self) -> (usize, Option<usize>) {
match self.orig.size_hint() {
sz @ (0, Some(0)) => sz,
(0, _) => (0, None),
_ => (usize::MAX, None)
}
}
}
#[stable(feature = "fused", since = "1.26.0")]
impl<I> FusedIterator for Cycle<I> where I: Clone + Iterator {}
#[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
#[stable(feature = "iterator_step_by", since = "1.28.0")]
#[derive(Clone, Debug)]
pub struct StepBy<I> {
iter: I,
step: usize,
first_take: bool,
}
#[stable(feature = "iterator_step_by", since = "1.28.0")]
impl<I> Iterator for StepBy<I> where I: Iterator {
type Item = I::Item;
#[inline]
fn next(&mut self) -> Option<Self::Item> {
if self.first_take {
self.first_take = false;
self.iter.next()
} else {
self.iter.nth(self.step)
}
}
#[inline]
fn size_hint(&self) -> (usize, Option<usize>) {
let inner_hint = self.iter.size_hint();
if self.first_take {
let f = |n| if n == 0 { 0 } else { 1 + (n-1)/(self.step+1) };
(f(inner_hint.0), inner_hint.1.map(f))
} else {
let f = |n| n / (self.step+1);
(f(inner_hint.0), inner_hint.1.map(f))
}
}
#[inline]
fn nth(&mut self, mut n: usize) -> Option<Self::Item> {
if self.first_take {
self.first_take = false;
let first = self.iter.next();
if n == 0 {
return first;
}
n -= 1;
}
let mut step = self.step + 1;
if n == usize::MAX {
self.iter.nth(step - 1);
} else {
n += 1;
}
loop {
let mul = n.checked_mul(step);
if unsafe { intrinsics::likely(mul.is_some()) } {
return self.iter.nth(mul.unwrap() - 1);
}
let div_n = usize::MAX / n;
let div_step = usize::MAX / step;
let nth_n = div_n * n;
let nth_step = div_step * step;
let nth = if nth_n > nth_step {
step -= div_n;
nth_n
} else {
n -= div_step;
nth_step
};
self.iter.nth(nth - 1);
}
}
}
#[stable(feature = "iterator_step_by", since = "1.28.0")]
impl<I> ExactSizeIterator for StepBy<I> where I: ExactSizeIterator {}
#[derive(Clone, Debug)]
#[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
#[stable(feature = "rust1", since = "1.0.0")]
pub struct Chain<A, B> {
a: A,
b: B,
state: ChainState,
}
#[derive(Clone, Debug)]
enum ChainState {
Both,
Front,
Back,
}
#[stable(feature = "rust1", since = "1.0.0")]
impl<A, B> Iterator for Chain<A, B> where
A: Iterator,
B: Iterator<Item = A::Item>
{
type Item = A::Item;
#[inline]
fn next(&mut self) -> Option<A::Item> {
match self.state {
ChainState::Both => match self.a.next() {
elt @ Some(..) => elt,
None => {
self.state = ChainState::Back;
self.b.next()
}
},
ChainState::Front => self.a.next(),
ChainState::Back => self.b.next(),
}
}
#[inline]
#[rustc_inherit_overflow_checks]
fn count(self) -> usize {
match self.state {
ChainState::Both => self.a.count() + self.b.count(),
ChainState::Front => self.a.count(),
ChainState::Back => self.b.count(),
}
}
fn try_fold<Acc, F, R>(&mut self, init: Acc, mut f: F) -> R where
Self: Sized, F: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
{
let mut accum = init;
match self.state {
ChainState::Both | ChainState::Front => {
accum = self.a.try_fold(accum, &mut f)?;
if let ChainState::Both = self.state {
self.state = ChainState::Back;
}
}
_ => { }
}
if let ChainState::Back = self.state {
accum = self.b.try_fold(accum, &mut f)?;
}
Try::from_ok(accum)
}
fn fold<Acc, F>(self, init: Acc, mut f: F) -> Acc
where F: FnMut(Acc, Self::Item) -> Acc,
{
let mut accum = init;
match self.state {
ChainState::Both | ChainState::Front => {
accum = self.a.fold(accum, &mut f);
}
_ => { }
}
match self.state {
ChainState::Both | ChainState::Back => {
accum = self.b.fold(accum, &mut f);
}
_ => { }
}
accum
}
#[inline]
fn nth(&mut self, mut n: usize) -> Option<A::Item> {
match self.state {
ChainState::Both | ChainState::Front => {
for x in self.a.by_ref() {
if n == 0 {
return Some(x)
}
n -= 1;
}
if let ChainState::Both = self.state {
self.state = ChainState::Back;
}
}
ChainState::Back => {}
}
if let ChainState::Back = self.state {
self.b.nth(n)
} else {
None
}
}
#[inline]
fn find<P>(&mut self, mut predicate: P) -> Option<Self::Item> where
P: FnMut(&Self::Item) -> bool,
{
match self.state {
ChainState::Both => match self.a.find(&mut predicate) {
None => {
self.state = ChainState::Back;
self.b.find(predicate)
}
v => v
},
ChainState::Front => self.a.find(predicate),
ChainState::Back => self.b.find(predicate),
}
}
#[inline]
fn last(self) -> Option<A::Item> {
match self.state {
ChainState::Both => {
let a_last = self.a.last();
let b_last = self.b.last();
b_last.or(a_last)
},
ChainState::Front => self.a.last(),
ChainState::Back => self.b.last()
}
}
#[inline]
fn size_hint(&self) -> (usize, Option<usize>) {
let (a_lower, a_upper) = self.a.size_hint();
let (b_lower, b_upper) = self.b.size_hint();
let lower = a_lower.saturating_add(b_lower);
let upper = match (a_upper, b_upper) {
(Some(x), Some(y)) => x.checked_add(y),
_ => None
};
(lower, upper)
}
}
#[stable(feature = "rust1", since = "1.0.0")]
impl<A, B> DoubleEndedIterator for Chain<A, B> where
A: DoubleEndedIterator,
B: DoubleEndedIterator<Item=A::Item>,
{
#[inline]
fn next_back(&mut self) -> Option<A::Item> {
match self.state {
ChainState::Both => match self.b.next_back() {
elt @ Some(..) => elt,
None => {
self.state = ChainState::Front;
self.a.next_back()
}
},
ChainState::Front => self.a.next_back(),
ChainState::Back => self.b.next_back(),
}
}
fn try_rfold<Acc, F, R>(&mut self, init: Acc, mut f: F) -> R where
Self: Sized, F: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
{
let mut accum = init;
match self.state {
ChainState::Both | ChainState::Back => {
accum = self.b.try_rfold(accum, &mut f)?;
if let ChainState::Both = self.state {
self.state = ChainState::Front;
}
}
_ => { }
}
if let ChainState::Front = self.state {
accum = self.a.try_rfold(accum, &mut f)?;
}
Try::from_ok(accum)
}
fn rfold<Acc, F>(self, init: Acc, mut f: F) -> Acc
where F: FnMut(Acc, Self::Item) -> Acc,
{
let mut accum = init;
match self.state {
ChainState::Both | ChainState::Back => {
accum = self.b.rfold(accum, &mut f);
}
_ => { }
}
match self.state {
ChainState::Both | ChainState::Front => {
accum = self.a.rfold(accum, &mut f);
}
_ => { }
}
accum
}
}
#[stable(feature = "fused", since = "1.26.0")]
impl<A, B> FusedIterator for Chain<A, B>
where A: FusedIterator,
B: FusedIterator<Item=A::Item>,
{}
#[unstable(feature = "trusted_len", issue = "37572")]
unsafe impl<A, B> TrustedLen for Chain<A, B>
where A: TrustedLen, B: TrustedLen<Item=A::Item>,
{}
#[derive(Clone, Debug)]
#[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
#[stable(feature = "rust1", since = "1.0.0")]
pub struct Zip<A, B> {
a: A,
b: B,
index: usize,
len: usize,
}
#[stable(feature = "rust1", since = "1.0.0")]
impl<A, B> Iterator for Zip<A, B> where A: Iterator, B: Iterator
{
type Item = (A::Item, B::Item);
#[inline]
fn next(&mut self) -> Option<Self::Item> {
ZipImpl::next(self)
}
#[inline]
fn size_hint(&self) -> (usize, Option<usize>) {
ZipImpl::size_hint(self)
}
#[inline]
fn nth(&mut self, n: usize) -> Option<Self::Item> {
ZipImpl::nth(self, n)
}
}
#[stable(feature = "rust1", since = "1.0.0")]
impl<A, B> DoubleEndedIterator for Zip<A, B> where
A: DoubleEndedIterator + ExactSizeIterator,
B: DoubleEndedIterator + ExactSizeIterator,
{
#[inline]
fn next_back(&mut self) -> Option<(A::Item, B::Item)> {
ZipImpl::next_back(self)
}
}
#[doc(hidden)]
trait ZipImpl<A, B> {
type Item;
fn new(a: A, b: B) -> Self;
fn next(&mut self) -> Option<Self::Item>;
fn size_hint(&self) -> (usize, Option<usize>);
fn nth(&mut self, n: usize) -> Option<Self::Item>;
fn super_nth(&mut self, mut n: usize) -> Option<Self::Item> {
while let Some(x) = self.next() {
if n == 0 { return Some(x) }
n -= 1;
}
None
}
fn next_back(&mut self) -> Option<Self::Item>
where A: DoubleEndedIterator + ExactSizeIterator,
B: DoubleEndedIterator + ExactSizeIterator;
}
#[doc(hidden)]
impl<A, B> ZipImpl<A, B> for Zip<A, B>
where A: Iterator, B: Iterator
{
type Item = (A::Item, B::Item);
default fn new(a: A, b: B) -> Self {
Zip {
a,
b,
index: 0,
len: 0,
}
}
#[inline]
default fn next(&mut self) -> Option<(A::Item, B::Item)> {
self.a.next().and_then(|x| {
self.b.next().and_then(|y| {
Some((x, y))
})
})
}
#[inline]
default fn nth(&mut self, n: usize) -> Option<Self::Item> {
self.super_nth(n)
}
#[inline]
default fn next_back(&mut self) -> Option<(A::Item, B::Item)>
where A: DoubleEndedIterator + ExactSizeIterator,
B: DoubleEndedIterator + ExactSizeIterator
{
let a_sz = self.a.len();
let b_sz = self.b.len();
if a_sz != b_sz {
if a_sz > b_sz {
for _ in 0..a_sz - b_sz { self.a.next_back(); }
} else {
for _ in 0..b_sz - a_sz { self.b.next_back(); }
}
}
match (self.a.next_back(), self.b.next_back()) {
(Some(x), Some(y)) => Some((x, y)),
(None, None) => None,
_ => unreachable!(),
}
}
#[inline]
default fn size_hint(&self) -> (usize, Option<usize>) {
let (a_lower, a_upper) = self.a.size_hint();
let (b_lower, b_upper) = self.b.size_hint();
let lower = cmp::min(a_lower, b_lower);
let upper = match (a_upper, b_upper) {
(Some(x), Some(y)) => Some(cmp::min(x,y)),
(Some(x), None) => Some(x),
(None, Some(y)) => Some(y),
(None, None) => None
};
(lower, upper)
}
}
#[doc(hidden)]
impl<A, B> ZipImpl<A, B> for Zip<A, B>
where A: TrustedRandomAccess, B: TrustedRandomAccess
{
fn new(a: A, b: B) -> Self {
let len = cmp::min(a.len(), b.len());
Zip {
a,
b,
index: 0,
len,
}
}
#[inline]
fn next(&mut self) -> Option<(A::Item, B::Item)> {
if self.index < self.len {
let i = self.index;
self.index += 1;
unsafe {
Some((self.a.get_unchecked(i), self.b.get_unchecked(i)))
}
} else if A::may_have_side_effect() && self.index < self.a.len() {
unsafe {
self.a.get_unchecked(self.index);
}
self.index += 1;
None
} else {
None
}
}
#[inline]
fn size_hint(&self) -> (usize, Option<usize>) {
let len = self.len - self.index;
(len, Some(len))
}
#[inline]
fn nth(&mut self, n: usize) -> Option<Self::Item> {
let delta = cmp::min(n, self.len - self.index);
let end = self.index + delta;
while self.index < end {
let i = self.index;
self.index += 1;
if A::may_have_side_effect() {
unsafe { self.a.get_unchecked(i); }
}
if B::may_have_side_effect() {
unsafe { self.b.get_unchecked(i); }
}
}
self.super_nth(n - delta)
}
#[inline]
fn next_back(&mut self) -> Option<(A::Item, B::Item)>
where A: DoubleEndedIterator + ExactSizeIterator,
B: DoubleEndedIterator + ExactSizeIterator
{
if A::may_have_side_effect() {
let sz = self.a.len();
if sz > self.len {
for _ in 0..sz - cmp::max(self.len, self.index) {
self.a.next_back();
}
}
}
if B::may_have_side_effect() {
let sz = self.b.len();
if sz > self.len {
for _ in 0..sz - self.len {
self.b.next_back();
}
}
}
if self.index < self.len {
self.len -= 1;
let i = self.len;
unsafe {
Some((self.a.get_unchecked(i), self.b.get_unchecked(i)))
}
} else {
None
}
}
}
#[stable(feature = "rust1", since = "1.0.0")]
impl<A, B> ExactSizeIterator for Zip<A, B>
where A: ExactSizeIterator, B: ExactSizeIterator {}
#[doc(hidden)]
unsafe impl<A, B> TrustedRandomAccess for Zip<A, B>
where A: TrustedRandomAccess,
B: TrustedRandomAccess,
{
unsafe fn get_unchecked(&mut self, i: usize) -> (A::Item, B::Item) {
(self.a.get_unchecked(i), self.b.get_unchecked(i))
}
fn may_have_side_effect() -> bool {
A::may_have_side_effect() || B::may_have_side_effect()
}
}
#[stable(feature = "fused", since = "1.26.0")]
impl<A, B> FusedIterator for Zip<A, B>
where A: FusedIterator, B: FusedIterator, {}
#[unstable(feature = "trusted_len", issue = "37572")]
unsafe impl<A, B> TrustedLen for Zip<A, B>
where A: TrustedLen, B: TrustedLen,
{}
#[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
#[stable(feature = "rust1", since = "1.0.0")]
#[derive(Clone)]
pub struct Map<I, F> {
iter: I,
f: F,
}
#[stable(feature = "core_impl_debug", since = "1.9.0")]
impl<I: fmt::Debug, F> fmt::Debug for Map<I, F> {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
f.debug_struct("Map")
.field("iter", &self.iter)
.finish()
}
}
#[stable(feature = "rust1", since = "1.0.0")]
impl<B, I: Iterator, F> Iterator for Map<I, F> where F: FnMut(I::Item) -> B {
type Item = B;
#[inline]
fn next(&mut self) -> Option<B> {
self.iter.next().map(&mut self.f)
}
#[inline]
fn size_hint(&self) -> (usize, Option<usize>) {
self.iter.size_hint()
}
fn try_fold<Acc, G, R>(&mut self, init: Acc, mut g: G) -> R where
Self: Sized, G: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
{
let f = &mut self.f;
self.iter.try_fold(init, move |acc, elt| g(acc, f(elt)))
}
fn fold<Acc, G>(self, init: Acc, mut g: G) -> Acc
where G: FnMut(Acc, Self::Item) -> Acc,
{
let mut f = self.f;
self.iter.fold(init, move |acc, elt| g(acc, f(elt)))
}
}
#[stable(feature = "rust1", since = "1.0.0")]
impl<B, I: DoubleEndedIterator, F> DoubleEndedIterator for Map<I, F> where
F: FnMut(I::Item) -> B,
{
#[inline]
fn next_back(&mut self) -> Option<B> {
self.iter.next_back().map(&mut self.f)
}
fn try_rfold<Acc, G, R>(&mut self, init: Acc, mut g: G) -> R where
Self: Sized, G: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
{
let f = &mut self.f;
self.iter.try_rfold(init, move |acc, elt| g(acc, f(elt)))
}
fn rfold<Acc, G>(self, init: Acc, mut g: G) -> Acc
where G: FnMut(Acc, Self::Item) -> Acc,
{
let mut f = self.f;
self.iter.rfold(init, move |acc, elt| g(acc, f(elt)))
}
}
#[stable(feature = "rust1", since = "1.0.0")]
impl<B, I: ExactSizeIterator, F> ExactSizeIterator for Map<I, F>
where F: FnMut(I::Item) -> B
{
fn len(&self) -> usize {
self.iter.len()
}
fn is_empty(&self) -> bool {
self.iter.is_empty()
}
}
#[stable(feature = "fused", since = "1.26.0")]
impl<B, I: FusedIterator, F> FusedIterator for Map<I, F>
where F: FnMut(I::Item) -> B {}
#[unstable(feature = "trusted_len", issue = "37572")]
unsafe impl<B, I, F> TrustedLen for Map<I, F>
where I: TrustedLen,
F: FnMut(I::Item) -> B {}
#[doc(hidden)]
unsafe impl<B, I, F> TrustedRandomAccess for Map<I, F>
where I: TrustedRandomAccess,
F: FnMut(I::Item) -> B,
{
unsafe fn get_unchecked(&mut self, i: usize) -> Self::Item {
(self.f)(self.iter.get_unchecked(i))
}
#[inline]
fn may_have_side_effect() -> bool { true }
}
#[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
#[stable(feature = "rust1", since = "1.0.0")]
#[derive(Clone)]
pub struct Filter<I, P> {
iter: I,
predicate: P,
}
#[stable(feature = "core_impl_debug", since = "1.9.0")]
impl<I: fmt::Debug, P> fmt::Debug for Filter<I, P> {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
f.debug_struct("Filter")
.field("iter", &self.iter)
.finish()
}
}
#[stable(feature = "rust1", since = "1.0.0")]
impl<I: Iterator, P> Iterator for Filter<I, P> where P: FnMut(&I::Item) -> bool {
type Item = I::Item;
#[inline]
fn next(&mut self) -> Option<I::Item> {
for x in &mut self.iter {
if (self.predicate)(&x) {
return Some(x);
}
}
None
}
#[inline]
fn size_hint(&self) -> (usize, Option<usize>) {
let (_, upper) = self.iter.size_hint();
(0, upper)
}
#[inline]
fn count(mut self) -> usize {
let mut count = 0;
for x in &mut self.iter {
count += (self.predicate)(&x) as usize;
}
count
}
#[inline]
fn try_fold<Acc, Fold, R>(&mut self, init: Acc, mut fold: Fold) -> R where
Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
{
let predicate = &mut self.predicate;
self.iter.try_fold(init, move |acc, item| if predicate(&item) {
fold(acc, item)
} else {
Try::from_ok(acc)
})
}
#[inline]
fn fold<Acc, Fold>(self, init: Acc, mut fold: Fold) -> Acc
where Fold: FnMut(Acc, Self::Item) -> Acc,
{
let mut predicate = self.predicate;
self.iter.fold(init, move |acc, item| if predicate(&item) {
fold(acc, item)
} else {
acc
})
}
}
#[stable(feature = "rust1", since = "1.0.0")]
impl<I: DoubleEndedIterator, P> DoubleEndedIterator for Filter<I, P>
where P: FnMut(&I::Item) -> bool,
{
#[inline]
fn next_back(&mut self) -> Option<I::Item> {
for x in self.iter.by_ref().rev() {
if (self.predicate)(&x) {
return Some(x);
}
}
None
}
#[inline]
fn try_rfold<Acc, Fold, R>(&mut self, init: Acc, mut fold: Fold) -> R where
Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
{
let predicate = &mut self.predicate;
self.iter.try_rfold(init, move |acc, item| if predicate(&item) {
fold(acc, item)
} else {
Try::from_ok(acc)
})
}
#[inline]
fn rfold<Acc, Fold>(self, init: Acc, mut fold: Fold) -> Acc
where Fold: FnMut(Acc, Self::Item) -> Acc,
{
let mut predicate = self.predicate;
self.iter.rfold(init, move |acc, item| if predicate(&item) {
fold(acc, item)
} else {
acc
})
}
}
#[stable(feature = "fused", since = "1.26.0")]
impl<I: FusedIterator, P> FusedIterator for Filter<I, P>
where P: FnMut(&I::Item) -> bool {}
#[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
#[stable(feature = "rust1", since = "1.0.0")]
#[derive(Clone)]
pub struct FilterMap<I, F> {
iter: I,
f: F,
}
#[stable(feature = "core_impl_debug", since = "1.9.0")]
impl<I: fmt::Debug, F> fmt::Debug for FilterMap<I, F> {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
f.debug_struct("FilterMap")
.field("iter", &self.iter)
.finish()
}
}
#[stable(feature = "rust1", since = "1.0.0")]
impl<B, I: Iterator, F> Iterator for FilterMap<I, F>
where F: FnMut(I::Item) -> Option<B>,
{
type Item = B;
#[inline]
fn next(&mut self) -> Option<B> {
for x in self.iter.by_ref() {
if let Some(y) = (self.f)(x) {
return Some(y);
}
}
None
}
#[inline]
fn size_hint(&self) -> (usize, Option<usize>) {
let (_, upper) = self.iter.size_hint();
(0, upper)
}
#[inline]
fn try_fold<Acc, Fold, R>(&mut self, init: Acc, mut fold: Fold) -> R where
Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
{
let f = &mut self.f;
self.iter.try_fold(init, move |acc, item| match f(item) {
Some(x) => fold(acc, x),
None => Try::from_ok(acc),
})
}
#[inline]
fn fold<Acc, Fold>(self, init: Acc, mut fold: Fold) -> Acc
where Fold: FnMut(Acc, Self::Item) -> Acc,
{
let mut f = self.f;
self.iter.fold(init, move |acc, item| match f(item) {
Some(x) => fold(acc, x),
None => acc,
})
}
}
#[stable(feature = "rust1", since = "1.0.0")]
impl<B, I: DoubleEndedIterator, F> DoubleEndedIterator for FilterMap<I, F>
where F: FnMut(I::Item) -> Option<B>,
{
#[inline]
fn next_back(&mut self) -> Option<B> {
for x in self.iter.by_ref().rev() {
if let Some(y) = (self.f)(x) {
return Some(y);
}
}
None
}
#[inline]
fn try_rfold<Acc, Fold, R>(&mut self, init: Acc, mut fold: Fold) -> R where
Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
{
let f = &mut self.f;
self.iter.try_rfold(init, move |acc, item| match f(item) {
Some(x) => fold(acc, x),
None => Try::from_ok(acc),
})
}
#[inline]
fn rfold<Acc, Fold>(self, init: Acc, mut fold: Fold) -> Acc
where Fold: FnMut(Acc, Self::Item) -> Acc,
{
let mut f = self.f;
self.iter.rfold(init, move |acc, item| match f(item) {
Some(x) => fold(acc, x),
None => acc,
})
}
}
#[stable(feature = "fused", since = "1.26.0")]
impl<B, I: FusedIterator, F> FusedIterator for FilterMap<I, F>
where F: FnMut(I::Item) -> Option<B> {}
#[derive(Clone, Debug)]
#[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
#[stable(feature = "rust1", since = "1.0.0")]
pub struct Enumerate<I> {
iter: I,
count: usize,
}
#[stable(feature = "rust1", since = "1.0.0")]
impl<I> Iterator for Enumerate<I> where I: Iterator {
type Item = (usize, <I as Iterator>::Item);
#[inline]
#[rustc_inherit_overflow_checks]
fn next(&mut self) -> Option<(usize, <I as Iterator>::Item)> {
self.iter.next().map(|a| {
let ret = (self.count, a);
self.count += 1;
ret
})
}
#[inline]
fn size_hint(&self) -> (usize, Option<usize>) {
self.iter.size_hint()
}
#[inline]
#[rustc_inherit_overflow_checks]
fn nth(&mut self, n: usize) -> Option<(usize, I::Item)> {
self.iter.nth(n).map(|a| {
let i = self.count + n;
self.count = i + 1;
(i, a)
})
}
#[inline]
fn count(self) -> usize {
self.iter.count()
}
#[inline]
#[rustc_inherit_overflow_checks]
fn try_fold<Acc, Fold, R>(&mut self, init: Acc, mut fold: Fold) -> R where
Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
{
let count = &mut self.count;
self.iter.try_fold(init, move |acc, item| {
let acc = fold(acc, (*count, item));
*count += 1;
acc
})
}
#[inline]
#[rustc_inherit_overflow_checks]
fn fold<Acc, Fold>(self, init: Acc, mut fold: Fold) -> Acc
where Fold: FnMut(Acc, Self::Item) -> Acc,
{
let mut count = self.count;
self.iter.fold(init, move |acc, item| {
let acc = fold(acc, (count, item));
count += 1;
acc
})
}
}
#[stable(feature = "rust1", since = "1.0.0")]
impl<I> DoubleEndedIterator for Enumerate<I> where
I: ExactSizeIterator + DoubleEndedIterator
{
#[inline]
fn next_back(&mut self) -> Option<(usize, <I as Iterator>::Item)> {
self.iter.next_back().map(|a| {
let len = self.iter.len();
(self.count + len, a)
})
}
#[inline]
fn try_rfold<Acc, Fold, R>(&mut self, init: Acc, mut fold: Fold) -> R where
Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
{
let mut count = self.count + self.iter.len();
self.iter.try_rfold(init, move |acc, item| {
count -= 1;
fold(acc, (count, item))
})
}
#[inline]
fn rfold<Acc, Fold>(self, init: Acc, mut fold: Fold) -> Acc
where Fold: FnMut(Acc, Self::Item) -> Acc,
{
let mut count = self.count + self.iter.len();
self.iter.rfold(init, move |acc, item| {
count -= 1;
fold(acc, (count, item))
})
}
}
#[stable(feature = "rust1", since = "1.0.0")]
impl<I> ExactSizeIterator for Enumerate<I> where I: ExactSizeIterator {
fn len(&self) -> usize {
self.iter.len()
}
fn is_empty(&self) -> bool {
self.iter.is_empty()
}
}
#[doc(hidden)]
unsafe impl<I> TrustedRandomAccess for Enumerate<I>
where I: TrustedRandomAccess
{
unsafe fn get_unchecked(&mut self, i: usize) -> (usize, I::Item) {
(self.count + i, self.iter.get_unchecked(i))
}
fn may_have_side_effect() -> bool {
I::may_have_side_effect()
}
}
#[stable(feature = "fused", since = "1.26.0")]
impl<I> FusedIterator for Enumerate<I> where I: FusedIterator {}
#[unstable(feature = "trusted_len", issue = "37572")]
unsafe impl<I> TrustedLen for Enumerate<I>
where I: TrustedLen,
{}
#[derive(Clone, Debug)]
#[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
#[stable(feature = "rust1", since = "1.0.0")]
pub struct Peekable<I: Iterator> {
iter: I,
peeked: Option<Option<I::Item>>,
}
#[stable(feature = "rust1", since = "1.0.0")]
impl<I: Iterator> Iterator for Peekable<I> {
type Item = I::Item;
#[inline]
fn next(&mut self) -> Option<I::Item> {
match self.peeked.take() {
Some(v) => v,
None => self.iter.next(),
}
}
#[inline]
#[rustc_inherit_overflow_checks]
fn count(mut self) -> usize {
match self.peeked.take() {
Some(None) => 0,
Some(Some(_)) => 1 + self.iter.count(),
None => self.iter.count(),
}
}
#[inline]
fn nth(&mut self, n: usize) -> Option<I::Item> {
if n == 0 {
match self.peeked.take() {
Some(v) => v,
None => self.iter.nth(n),
}
} else {
match self.peeked.take() {
Some(None) => None,
Some(Some(_)) => self.iter.nth(n - 1),
None => self.iter.nth(n),
}
}
}
#[inline]
fn last(mut self) -> Option<I::Item> {
let peek_opt = match self.peeked.take() {
Some(None) => return None,
Some(v) => v,
None => None,
};
self.iter.last().or(peek_opt)
}
#[inline]
fn size_hint(&self) -> (usize, Option<usize>) {
let peek_len = match self.peeked {
Some(None) => return (0, Some(0)),
Some(Some(_)) => 1,
None => 0,
};
let (lo, hi) = self.iter.size_hint();
let lo = lo.saturating_add(peek_len);
let hi = hi.and_then(|x| x.checked_add(peek_len));
(lo, hi)
}
#[inline]
fn try_fold<B, F, R>(&mut self, init: B, mut f: F) -> R where
Self: Sized, F: FnMut(B, Self::Item) -> R, R: Try<Ok=B>
{
let acc = match self.peeked.take() {
Some(None) => return Try::from_ok(init),
Some(Some(v)) => f(init, v)?,
None => init,
};
self.iter.try_fold(acc, f)
}
#[inline]
fn fold<Acc, Fold>(self, init: Acc, mut fold: Fold) -> Acc
where Fold: FnMut(Acc, Self::Item) -> Acc,
{
let acc = match self.peeked {
Some(None) => return init,
Some(Some(v)) => fold(init, v),
None => init,
};
self.iter.fold(acc, fold)
}
}
#[stable(feature = "rust1", since = "1.0.0")]
impl<I: ExactSizeIterator> ExactSizeIterator for Peekable<I> {}
#[stable(feature = "fused", since = "1.26.0")]
impl<I: FusedIterator> FusedIterator for Peekable<I> {}
impl<I: Iterator> Peekable<I> {
#[inline]
#[stable(feature = "rust1", since = "1.0.0")]
pub fn peek(&mut self) -> Option<&I::Item> {
if self.peeked.is_none() {
self.peeked = Some(self.iter.next());
}
match self.peeked {
Some(Some(ref value)) => Some(value),
Some(None) => None,
_ => unreachable!(),
}
}
}
#[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
#[stable(feature = "rust1", since = "1.0.0")]
#[derive(Clone)]
pub struct SkipWhile<I, P> {
iter: I,
flag: bool,
predicate: P,
}
#[stable(feature = "core_impl_debug", since = "1.9.0")]
impl<I: fmt::Debug, P> fmt::Debug for SkipWhile<I, P> {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
f.debug_struct("SkipWhile")
.field("iter", &self.iter)
.field("flag", &self.flag)
.finish()
}
}
#[stable(feature = "rust1", since = "1.0.0")]
impl<I: Iterator, P> Iterator for SkipWhile<I, P>
where P: FnMut(&I::Item) -> bool
{
type Item = I::Item;
#[inline]
fn next(&mut self) -> Option<I::Item> {
let flag = &mut self.flag;
let pred = &mut self.predicate;
self.iter.find(move |x| {
if *flag || !pred(x) {
*flag = true;
true
} else {
false
}
})
}
#[inline]
fn size_hint(&self) -> (usize, Option<usize>) {
let (_, upper) = self.iter.size_hint();
(0, upper)
}
#[inline]
fn try_fold<Acc, Fold, R>(&mut self, mut init: Acc, mut fold: Fold) -> R where
Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
{
if !self.flag {
match self.next() {
Some(v) => init = fold(init, v)?,
None => return Try::from_ok(init),
}
}
self.iter.try_fold(init, fold)
}
#[inline]
fn fold<Acc, Fold>(mut self, mut init: Acc, mut fold: Fold) -> Acc
where Fold: FnMut(Acc, Self::Item) -> Acc,
{
if !self.flag {
match self.next() {
Some(v) => init = fold(init, v),
None => return init,
}
}
self.iter.fold(init, fold)
}
}
#[stable(feature = "fused", since = "1.26.0")]
impl<I, P> FusedIterator for SkipWhile<I, P>
where I: FusedIterator, P: FnMut(&I::Item) -> bool {}
#[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
#[stable(feature = "rust1", since = "1.0.0")]
#[derive(Clone)]
pub struct TakeWhile<I, P> {
iter: I,
flag: bool,
predicate: P,
}
#[stable(feature = "core_impl_debug", since = "1.9.0")]
impl<I: fmt::Debug, P> fmt::Debug for TakeWhile<I, P> {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
f.debug_struct("TakeWhile")
.field("iter", &self.iter)
.field("flag", &self.flag)
.finish()
}
}
#[stable(feature = "rust1", since = "1.0.0")]
impl<I: Iterator, P> Iterator for TakeWhile<I, P>
where P: FnMut(&I::Item) -> bool
{
type Item = I::Item;
#[inline]
fn next(&mut self) -> Option<I::Item> {
if self.flag {
None
} else {
self.iter.next().and_then(|x| {
if (self.predicate)(&x) {
Some(x)
} else {
self.flag = true;
None
}
})
}
}
#[inline]
fn size_hint(&self) -> (usize, Option<usize>) {
let (_, upper) = self.iter.size_hint();
(0, upper)
}
#[inline]
fn try_fold<Acc, Fold, R>(&mut self, init: Acc, mut fold: Fold) -> R where
Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
{
if self.flag {
Try::from_ok(init)
} else {
let flag = &mut self.flag;
let p = &mut self.predicate;
self.iter.try_fold(init, move |acc, x|{
if p(&x) {
LoopState::from_try(fold(acc, x))
} else {
*flag = true;
LoopState::Break(Try::from_ok(acc))
}
}).into_try()
}
}
}
#[stable(feature = "fused", since = "1.26.0")]
impl<I, P> FusedIterator for TakeWhile<I, P>
where I: FusedIterator, P: FnMut(&I::Item) -> bool {}
#[derive(Clone, Debug)]
#[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
#[stable(feature = "rust1", since = "1.0.0")]
pub struct Skip<I> {
iter: I,
n: usize
}
#[stable(feature = "rust1", since = "1.0.0")]
impl<I> Iterator for Skip<I> where I: Iterator {
type Item = <I as Iterator>::Item;
#[inline]
fn next(&mut self) -> Option<I::Item> {
if self.n == 0 {
self.iter.next()
} else {
let old_n = self.n;
self.n = 0;
self.iter.nth(old_n)
}
}
#[inline]
fn nth(&mut self, n: usize) -> Option<I::Item> {
if self.n == 0 {
self.iter.nth(n)
} else {
let to_skip = self.n;
self.n = 0;
if self.iter.nth(to_skip-1).is_none() {
return None;
}
self.iter.nth(n)
}
}
#[inline]
fn count(self) -> usize {
self.iter.count().saturating_sub(self.n)
}
#[inline]
fn last(mut self) -> Option<I::Item> {
if self.n == 0 {
self.iter.last()
} else {
let next = self.next();
if next.is_some() {
self.last().or(next)
} else {
None
}
}
}
#[inline]
fn size_hint(&self) -> (usize, Option<usize>) {
let (lower, upper) = self.iter.size_hint();
let lower = lower.saturating_sub(self.n);
let upper = upper.map(|x| x.saturating_sub(self.n));
(lower, upper)
}
#[inline]
fn try_fold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R where
Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
{
let n = self.n;
self.n = 0;
if n > 0 {
if self.iter.nth(n - 1).is_none() {
return Try::from_ok(init);
}
}
self.iter.try_fold(init, fold)
}
#[inline]
fn fold<Acc, Fold>(mut self, init: Acc, fold: Fold) -> Acc
where Fold: FnMut(Acc, Self::Item) -> Acc,
{
if self.n > 0 {
if self.iter.nth(self.n - 1).is_none() {
return init;
}
}
self.iter.fold(init, fold)
}
}
#[stable(feature = "rust1", since = "1.0.0")]
impl<I> ExactSizeIterator for Skip<I> where I: ExactSizeIterator {}
#[stable(feature = "double_ended_skip_iterator", since = "1.9.0")]
impl<I> DoubleEndedIterator for Skip<I> where I: DoubleEndedIterator + ExactSizeIterator {
fn next_back(&mut self) -> Option<Self::Item> {
if self.len() > 0 {
self.iter.next_back()
} else {
None
}
}
fn try_rfold<Acc, Fold, R>(&mut self, init: Acc, mut fold: Fold) -> R where
Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
{
let mut n = self.len();
if n == 0 {
Try::from_ok(init)
} else {
self.iter.try_rfold(init, move |acc, x| {
n -= 1;
let r = fold(acc, x);
if n == 0 { LoopState::Break(r) }
else { LoopState::from_try(r) }
}).into_try()
}
}
}
#[stable(feature = "fused", since = "1.26.0")]
impl<I> FusedIterator for Skip<I> where I: FusedIterator {}
#[derive(Clone, Debug)]
#[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
#[stable(feature = "rust1", since = "1.0.0")]
pub struct Take<I> {
iter: I,
n: usize
}
#[stable(feature = "rust1", since = "1.0.0")]
impl<I> Iterator for Take<I> where I: Iterator{
type Item = <I as Iterator>::Item;
#[inline]
fn next(&mut self) -> Option<<I as Iterator>::Item> {
if self.n != 0 {
self.n -= 1;
self.iter.next()
} else {
None
}
}
#[inline]
fn nth(&mut self, n: usize) -> Option<I::Item> {
if self.n > n {
self.n -= n + 1;
self.iter.nth(n)
} else {
if self.n > 0 {
self.iter.nth(self.n - 1);
self.n = 0;
}
None
}
}
#[inline]
fn size_hint(&self) -> (usize, Option<usize>) {
let (lower, upper) = self.iter.size_hint();
let lower = cmp::min(lower, self.n);
let upper = match upper {
Some(x) if x < self.n => Some(x),
_ => Some(self.n)
};
(lower, upper)
}
#[inline]
fn try_fold<Acc, Fold, R>(&mut self, init: Acc, mut fold: Fold) -> R where
Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
{
if self.n == 0 {
Try::from_ok(init)
} else {
let n = &mut self.n;
self.iter.try_fold(init, move |acc, x| {
*n -= 1;
let r = fold(acc, x);
if *n == 0 { LoopState::Break(r) }
else { LoopState::from_try(r) }
}).into_try()
}
}
}
#[stable(feature = "rust1", since = "1.0.0")]
impl<I> ExactSizeIterator for Take<I> where I: ExactSizeIterator {}
#[stable(feature = "fused", since = "1.26.0")]
impl<I> FusedIterator for Take<I> where I: FusedIterator {}
#[unstable(feature = "trusted_len", issue = "37572")]
unsafe impl<I: TrustedLen> TrustedLen for Take<I> {}
#[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
#[stable(feature = "rust1", since = "1.0.0")]
#[derive(Clone)]
pub struct Scan<I, St, F> {
iter: I,
f: F,
state: St,
}
#[stable(feature = "core_impl_debug", since = "1.9.0")]
impl<I: fmt::Debug, St: fmt::Debug, F> fmt::Debug for Scan<I, St, F> {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
f.debug_struct("Scan")
.field("iter", &self.iter)
.field("state", &self.state)
.finish()
}
}
#[stable(feature = "rust1", since = "1.0.0")]
impl<B, I, St, F> Iterator for Scan<I, St, F> where
I: Iterator,
F: FnMut(&mut St, I::Item) -> Option<B>,
{
type Item = B;
#[inline]
fn next(&mut self) -> Option<B> {
self.iter.next().and_then(|a| (self.f)(&mut self.state, a))
}
#[inline]
fn size_hint(&self) -> (usize, Option<usize>) {
let (_, upper) = self.iter.size_hint();
(0, upper)
}
#[inline]
fn try_fold<Acc, Fold, R>(&mut self, init: Acc, mut fold: Fold) -> R where
Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
{
let state = &mut self.state;
let f = &mut self.f;
self.iter.try_fold(init, move |acc, x| {
match f(state, x) {
None => LoopState::Break(Try::from_ok(acc)),
Some(x) => LoopState::from_try(fold(acc, x)),
}
}).into_try()
}
}
#[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
#[stable(feature = "rust1", since = "1.0.0")]
pub struct FlatMap<I, U: IntoIterator, F> {
inner: FlattenCompat<Map<I, F>, <U as IntoIterator>::IntoIter>
}
#[stable(feature = "rust1", since = "1.0.0")]
impl<I: Clone, U: Clone + IntoIterator, F: Clone> Clone for FlatMap<I, U, F>
where <U as IntoIterator>::IntoIter: Clone
{
fn clone(&self) -> Self { FlatMap { inner: self.inner.clone() } }
}
#[stable(feature = "core_impl_debug", since = "1.9.0")]
impl<I: fmt::Debug, U: IntoIterator, F> fmt::Debug for FlatMap<I, U, F>
where U::IntoIter: fmt::Debug
{
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
f.debug_struct("FlatMap").field("inner", &self.inner).finish()
}
}
#[stable(feature = "rust1", since = "1.0.0")]
impl<I: Iterator, U: IntoIterator, F> Iterator for FlatMap<I, U, F>
where F: FnMut(I::Item) -> U,
{
type Item = U::Item;
#[inline]
fn next(&mut self) -> Option<U::Item> { self.inner.next() }
#[inline]
fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() }
#[inline]
fn try_fold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R where
Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
{
self.inner.try_fold(init, fold)
}
#[inline]
fn fold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
where Fold: FnMut(Acc, Self::Item) -> Acc,
{
self.inner.fold(init, fold)
}
}
#[stable(feature = "rust1", since = "1.0.0")]
impl<I: DoubleEndedIterator, U, F> DoubleEndedIterator for FlatMap<I, U, F>
where F: FnMut(I::Item) -> U,
U: IntoIterator,
U::IntoIter: DoubleEndedIterator
{
#[inline]
fn next_back(&mut self) -> Option<U::Item> { self.inner.next_back() }
#[inline]
fn try_rfold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R where
Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
{
self.inner.try_rfold(init, fold)
}
#[inline]
fn rfold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
where Fold: FnMut(Acc, Self::Item) -> Acc,
{
self.inner.rfold(init, fold)
}
}
#[stable(feature = "fused", since = "1.26.0")]
impl<I, U, F> FusedIterator for FlatMap<I, U, F>
where I: FusedIterator, U: IntoIterator, F: FnMut(I::Item) -> U {}
#[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
#[stable(feature = "iterator_flatten", since = "1.29.0")]
pub struct Flatten<I: Iterator>
where I::Item: IntoIterator {
inner: FlattenCompat<I, <I::Item as IntoIterator>::IntoIter>,
}
#[stable(feature = "iterator_flatten", since = "1.29.0")]
impl<I, U> fmt::Debug for Flatten<I>
where I: Iterator + fmt::Debug, U: Iterator + fmt::Debug,
I::Item: IntoIterator<IntoIter = U, Item = U::Item>,
{
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
f.debug_struct("Flatten").field("inner", &self.inner).finish()
}
}
#[stable(feature = "iterator_flatten", since = "1.29.0")]
impl<I, U> Clone for Flatten<I>
where I: Iterator + Clone, U: Iterator + Clone,
I::Item: IntoIterator<IntoIter = U, Item = U::Item>,
{
fn clone(&self) -> Self { Flatten { inner: self.inner.clone() } }
}
#[stable(feature = "iterator_flatten", since = "1.29.0")]
impl<I, U> Iterator for Flatten<I>
where I: Iterator, U: Iterator,
I::Item: IntoIterator<IntoIter = U, Item = U::Item>
{
type Item = U::Item;
#[inline]
fn next(&mut self) -> Option<U::Item> { self.inner.next() }
#[inline]
fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() }
#[inline]
fn try_fold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R where
Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
{
self.inner.try_fold(init, fold)
}
#[inline]
fn fold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
where Fold: FnMut(Acc, Self::Item) -> Acc,
{
self.inner.fold(init, fold)
}
}
#[stable(feature = "iterator_flatten", since = "1.29.0")]
impl<I, U> DoubleEndedIterator for Flatten<I>
where I: DoubleEndedIterator, U: DoubleEndedIterator,
I::Item: IntoIterator<IntoIter = U, Item = U::Item>
{
#[inline]
fn next_back(&mut self) -> Option<U::Item> { self.inner.next_back() }
#[inline]
fn try_rfold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R where
Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
{
self.inner.try_rfold(init, fold)
}
#[inline]
fn rfold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
where Fold: FnMut(Acc, Self::Item) -> Acc,
{
self.inner.rfold(init, fold)
}
}
#[stable(feature = "iterator_flatten", since = "1.29.0")]
impl<I, U> FusedIterator for Flatten<I>
where I: FusedIterator, U: Iterator,
I::Item: IntoIterator<IntoIter = U, Item = U::Item> {}
fn flatten_compat<I, U>(iter: I) -> FlattenCompat<I, U> {
FlattenCompat { iter, frontiter: None, backiter: None }
}
#[derive(Clone, Debug)]
struct FlattenCompat<I, U> {
iter: I,
frontiter: Option<U>,
backiter: Option<U>,
}
impl<I, U> Iterator for FlattenCompat<I, U>
where I: Iterator, U: Iterator,
I::Item: IntoIterator<IntoIter = U, Item = U::Item>
{
type Item = U::Item;
#[inline]
fn next(&mut self) -> Option<U::Item> {
loop {
if let Some(ref mut inner) = self.frontiter {
if let elt@Some(_) = inner.next() { return elt }
}
match self.iter.next() {
None => return self.backiter.as_mut().and_then(|it| it.next()),
Some(inner) => self.frontiter = Some(inner.into_iter()),
}
}
}
#[inline]
fn size_hint(&self) -> (usize, Option<usize>) {
let (flo, fhi) = self.frontiter.as_ref().map_or((0, Some(0)), |it| it.size_hint());
let (blo, bhi) = self.backiter.as_ref().map_or((0, Some(0)), |it| it.size_hint());
let lo = flo.saturating_add(blo);
match (self.iter.size_hint(), fhi, bhi) {
((0, Some(0)), Some(a), Some(b)) => (lo, a.checked_add(b)),
_ => (lo, None)
}
}
#[inline]
fn try_fold<Acc, Fold, R>(&mut self, mut init: Acc, mut fold: Fold) -> R where
Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
{
if let Some(ref mut front) = self.frontiter {
init = front.try_fold(init, &mut fold)?;
}
self.frontiter = None;
{
let frontiter = &mut self.frontiter;
init = self.iter.try_fold(init, |acc, x| {
let mut mid = x.into_iter();
let r = mid.try_fold(acc, &mut fold);
*frontiter = Some(mid);
r
})?;
}
self.frontiter = None;
if let Some(ref mut back) = self.backiter {
init = back.try_fold(init, &mut fold)?;
}
self.backiter = None;
Try::from_ok(init)
}
#[inline]
fn fold<Acc, Fold>(self, init: Acc, mut fold: Fold) -> Acc
where Fold: FnMut(Acc, Self::Item) -> Acc,
{
self.frontiter.into_iter()
.chain(self.iter.map(IntoIterator::into_iter))
.chain(self.backiter)
.fold(init, |acc, iter| iter.fold(acc, &mut fold))
}
}
impl<I, U> DoubleEndedIterator for FlattenCompat<I, U>
where I: DoubleEndedIterator, U: DoubleEndedIterator,
I::Item: IntoIterator<IntoIter = U, Item = U::Item>
{
#[inline]
fn next_back(&mut self) -> Option<U::Item> {
loop {
if let Some(ref mut inner) = self.backiter {
if let elt@Some(_) = inner.next_back() { return elt }
}
match self.iter.next_back() {
None => return self.frontiter.as_mut().and_then(|it| it.next_back()),
next => self.backiter = next.map(IntoIterator::into_iter),
}
}
}
#[inline]
fn try_rfold<Acc, Fold, R>(&mut self, mut init: Acc, mut fold: Fold) -> R where
Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
{
if let Some(ref mut back) = self.backiter {
init = back.try_rfold(init, &mut fold)?;
}
self.backiter = None;
{
let backiter = &mut self.backiter;
init = self.iter.try_rfold(init, |acc, x| {
let mut mid = x.into_iter();
let r = mid.try_rfold(acc, &mut fold);
*backiter = Some(mid);
r
})?;
}
self.backiter = None;
if let Some(ref mut front) = self.frontiter {
init = front.try_rfold(init, &mut fold)?;
}
self.frontiter = None;
Try::from_ok(init)
}
#[inline]
fn rfold<Acc, Fold>(self, init: Acc, mut fold: Fold) -> Acc
where Fold: FnMut(Acc, Self::Item) -> Acc,
{
self.frontiter.into_iter()
.chain(self.iter.map(IntoIterator::into_iter))
.chain(self.backiter)
.rfold(init, |acc, iter| iter.rfold(acc, &mut fold))
}
}
#[derive(Clone, Debug)]
#[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
#[stable(feature = "rust1", since = "1.0.0")]
pub struct Fuse<I> {
iter: I,
done: bool
}
#[stable(feature = "fused", since = "1.26.0")]
impl<I> FusedIterator for Fuse<I> where I: Iterator {}
#[stable(feature = "rust1", since = "1.0.0")]
impl<I> Iterator for Fuse<I> where I: Iterator {
type Item = <I as Iterator>::Item;
#[inline]
default fn next(&mut self) -> Option<<I as Iterator>::Item> {
if self.done {
None
} else {
let next = self.iter.next();
self.done = next.is_none();
next
}
}
#[inline]
default fn nth(&mut self, n: usize) -> Option<I::Item> {
if self.done {
None
} else {
let nth = self.iter.nth(n);
self.done = nth.is_none();
nth
}
}
#[inline]
default fn last(self) -> Option<I::Item> {
if self.done {
None
} else {
self.iter.last()
}
}
#[inline]
default fn count(self) -> usize {
if self.done {
0
} else {
self.iter.count()
}
}
#[inline]
default fn size_hint(&self) -> (usize, Option<usize>) {
if self.done {
(0, Some(0))
} else {
self.iter.size_hint()
}
}
#[inline]
default fn try_fold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R where
Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
{
if self.done {
Try::from_ok(init)
} else {
let acc = self.iter.try_fold(init, fold)?;
self.done = true;
Try::from_ok(acc)
}
}
#[inline]
default fn fold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
where Fold: FnMut(Acc, Self::Item) -> Acc,
{
if self.done {
init
} else {
self.iter.fold(init, fold)
}
}
}
#[stable(feature = "rust1", since = "1.0.0")]
impl<I> DoubleEndedIterator for Fuse<I> where I: DoubleEndedIterator {
#[inline]
default fn next_back(&mut self) -> Option<<I as Iterator>::Item> {
if self.done {
None
} else {
let next = self.iter.next_back();
self.done = next.is_none();
next
}
}
#[inline]
default fn try_rfold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R where
Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
{
if self.done {
Try::from_ok(init)
} else {
let acc = self.iter.try_rfold(init, fold)?;
self.done = true;
Try::from_ok(acc)
}
}
#[inline]
default fn rfold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
where Fold: FnMut(Acc, Self::Item) -> Acc,
{
if self.done {
init
} else {
self.iter.rfold(init, fold)
}
}
}
unsafe impl<I> TrustedRandomAccess for Fuse<I>
where I: TrustedRandomAccess,
{
unsafe fn get_unchecked(&mut self, i: usize) -> I::Item {
self.iter.get_unchecked(i)
}
fn may_have_side_effect() -> bool {
I::may_have_side_effect()
}
}
#[stable(feature = "fused", since = "1.26.0")]
impl<I> Iterator for Fuse<I> where I: FusedIterator {
#[inline]
fn next(&mut self) -> Option<<I as Iterator>::Item> {
self.iter.next()
}
#[inline]
fn nth(&mut self, n: usize) -> Option<I::Item> {
self.iter.nth(n)
}
#[inline]
fn last(self) -> Option<I::Item> {
self.iter.last()
}
#[inline]
fn count(self) -> usize {
self.iter.count()
}
#[inline]
fn size_hint(&self) -> (usize, Option<usize>) {
self.iter.size_hint()
}
#[inline]
fn try_fold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R where
Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
{
self.iter.try_fold(init, fold)
}
#[inline]
fn fold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
where Fold: FnMut(Acc, Self::Item) -> Acc,
{
self.iter.fold(init, fold)
}
}
#[stable(feature = "fused", since = "1.26.0")]
impl<I> DoubleEndedIterator for Fuse<I>
where I: DoubleEndedIterator + FusedIterator
{
#[inline]
fn next_back(&mut self) -> Option<<I as Iterator>::Item> {
self.iter.next_back()
}
#[inline]
fn try_rfold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R where
Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
{
self.iter.try_rfold(init, fold)
}
#[inline]
fn rfold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
where Fold: FnMut(Acc, Self::Item) -> Acc,
{
self.iter.rfold(init, fold)
}
}
#[stable(feature = "rust1", since = "1.0.0")]
impl<I> ExactSizeIterator for Fuse<I> where I: ExactSizeIterator {
fn len(&self) -> usize {
self.iter.len()
}
fn is_empty(&self) -> bool {
self.iter.is_empty()
}
}
#[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
#[stable(feature = "rust1", since = "1.0.0")]
#[derive(Clone)]
pub struct Inspect<I, F> {
iter: I,
f: F,
}
#[stable(feature = "core_impl_debug", since = "1.9.0")]
impl<I: fmt::Debug, F> fmt::Debug for Inspect<I, F> {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
f.debug_struct("Inspect")
.field("iter", &self.iter)
.finish()
}
}
impl<I: Iterator, F> Inspect<I, F> where F: FnMut(&I::Item) {
#[inline]
fn do_inspect(&mut self, elt: Option<I::Item>) -> Option<I::Item> {
if let Some(ref a) = elt {
(self.f)(a);
}
elt
}
}
#[stable(feature = "rust1", since = "1.0.0")]
impl<I: Iterator, F> Iterator for Inspect<I, F> where F: FnMut(&I::Item) {
type Item = I::Item;
#[inline]
fn next(&mut self) -> Option<I::Item> {
let next = self.iter.next();
self.do_inspect(next)
}
#[inline]
fn size_hint(&self) -> (usize, Option<usize>) {
self.iter.size_hint()
}
#[inline]
fn try_fold<Acc, Fold, R>(&mut self, init: Acc, mut fold: Fold) -> R where
Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
{
let f = &mut self.f;
self.iter.try_fold(init, move |acc, item| { f(&item); fold(acc, item) })
}
#[inline]
fn fold<Acc, Fold>(self, init: Acc, mut fold: Fold) -> Acc
where Fold: FnMut(Acc, Self::Item) -> Acc,
{
let mut f = self.f;
self.iter.fold(init, move |acc, item| { f(&item); fold(acc, item) })
}
}
#[stable(feature = "rust1", since = "1.0.0")]
impl<I: DoubleEndedIterator, F> DoubleEndedIterator for Inspect<I, F>
where F: FnMut(&I::Item),
{
#[inline]
fn next_back(&mut self) -> Option<I::Item> {
let next = self.iter.next_back();
self.do_inspect(next)
}
#[inline]
fn try_rfold<Acc, Fold, R>(&mut self, init: Acc, mut fold: Fold) -> R where
Self: Sized, Fold: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
{
let f = &mut self.f;
self.iter.try_rfold(init, move |acc, item| { f(&item); fold(acc, item) })
}
#[inline]
fn rfold<Acc, Fold>(self, init: Acc, mut fold: Fold) -> Acc
where Fold: FnMut(Acc, Self::Item) -> Acc,
{
let mut f = self.f;
self.iter.rfold(init, move |acc, item| { f(&item); fold(acc, item) })
}
}
#[stable(feature = "rust1", since = "1.0.0")]
impl<I: ExactSizeIterator, F> ExactSizeIterator for Inspect<I, F>
where F: FnMut(&I::Item)
{
fn len(&self) -> usize {
self.iter.len()
}
fn is_empty(&self) -> bool {
self.iter.is_empty()
}
}
#[stable(feature = "fused", since = "1.26.0")]
impl<I: FusedIterator, F> FusedIterator for Inspect<I, F>
where F: FnMut(&I::Item) {}