| //! Fallible, streaming iteration. |
| //! |
| //! `FallibleStreamingIterator` differs from the standard library's `Iterator` trait in two ways: |
| //! iteration can fail, resulting in an error, and only one element of the iteration is available at |
| //! any time. |
| //! |
| //! While these iterators cannot be used with Rust `for` loops, `while let` loops offer a similar |
| //! level of ergonomics: |
| //! |
| //! ```ignore |
| //! while let Some(value) = it.next()? { |
| //! // use value |
| //! } |
| //! ``` |
| #![doc(html_root_url = "https://docs.rs/fallible-streaming-iterator/0.1")] |
| #![warn(missing_docs)] |
| #![cfg_attr(not(feature = "std"), no_std)] |
| |
| #[cfg(feature = "std")] |
| extern crate core; |
| |
| use core::cmp; |
| use core::marker::PhantomData; |
| |
| /// A fallible, streaming iterator. |
| pub trait FallibleStreamingIterator { |
| /// The type being iterated over. |
| type Item: ?Sized; |
| |
| /// The error type of iteration. |
| type Error; |
| |
| /// Advances the iterator to the next position. |
| /// |
| /// Iterators start just before the first item, so this method should be called before `get` |
| /// when iterating. |
| /// |
| /// The behavior of calling this method after `get` has returned `None`, or after this method |
| /// has returned an error is unspecified. |
| fn advance(&mut self) -> Result<(), Self::Error>; |
| |
| /// Returns the current element. |
| /// |
| /// The behavior of calling this method before any calls to `advance` is unspecified. |
| fn get(&self) -> Option<&Self::Item>; |
| |
| /// Advances the iterator, returning the next element. |
| /// |
| /// The default implementation simply calls `advance` followed by `get`. |
| #[inline] |
| fn next(&mut self) -> Result<Option<&Self::Item>, Self::Error> { |
| self.advance()?; |
| Ok((*self).get()) |
| } |
| |
| /// Returns bounds on the number of remaining elements in the iterator. |
| #[inline] |
| fn size_hint(&self) -> (usize, Option<usize>) { |
| (0, None) |
| } |
| |
| /// Determines if all elements of the iterator satisfy a predicate. |
| #[inline] |
| fn all<F>(&mut self, mut f: F) -> Result<bool, Self::Error> |
| where |
| Self: Sized, |
| F: FnMut(&Self::Item) -> bool, |
| { |
| while let Some(e) = self.next()? { |
| if !f(e) { |
| return Ok(false); |
| } |
| } |
| Ok(true) |
| } |
| |
| /// Determines if any elements of the iterator satisfy a predicate. |
| #[inline] |
| fn any<F>(&mut self, mut f: F) -> Result<bool, Self::Error> |
| where |
| Self: Sized, |
| F: FnMut(&Self::Item) -> bool, |
| { |
| self.all(|e| !f(e)).map(|r| !r) |
| } |
| |
| /// Borrows an iterator, rather than consuming it. |
| /// |
| /// This is useful to allow the application of iterator adaptors while still retaining ownership |
| /// of the original adaptor. |
| #[inline] |
| fn by_ref(&mut self) -> &mut Self |
| where |
| Self: Sized, |
| { |
| self |
| } |
| |
| /// Returns the number of remaining elements in the iterator. |
| #[inline] |
| fn count(mut self) -> Result<usize, Self::Error> |
| where |
| Self: Sized, |
| { |
| let mut count = 0; |
| while let Some(_) = self.next()? { |
| count += 1; |
| } |
| Ok(count) |
| } |
| |
| /// Returns an iterator which filters elements by a predicate. |
| #[inline] |
| fn filter<F>(self, f: F) -> Filter<Self, F> |
| where |
| Self: Sized, |
| F: FnMut(&Self::Item) -> bool, |
| { |
| Filter { it: self, f: f } |
| } |
| |
| /// Returns the first element of the iterator which satisfies a predicate. |
| #[inline] |
| fn find<F>(&mut self, mut f: F) -> Result<Option<&Self::Item>, Self::Error> |
| where |
| Self: Sized, |
| F: FnMut(&Self::Item) -> bool, |
| { |
| loop { |
| self.advance()?; |
| match self.get() { |
| Some(v) => { |
| if f(v) { |
| break; |
| } |
| } |
| None => break, |
| } |
| } |
| Ok((*self).get()) |
| } |
| |
| /// Calls a closure on each element of an iterator. |
| #[inline] |
| fn for_each<F>(mut self, mut f: F) -> Result<(), Self::Error> |
| where |
| Self: Sized, |
| F: FnMut(&Self::Item), |
| { |
| while let Some(value) = self.next()? { |
| f(value); |
| } |
| Ok(()) |
| } |
| |
| /// Returns an iterator which is well-behaved at the beginning and end of iteration. |
| #[inline] |
| fn fuse(self) -> Fuse<Self> |
| where |
| Self: Sized, |
| { |
| Fuse { |
| it: self, |
| state: FuseState::Start, |
| } |
| } |
| |
| /// Returns an iterator which applies a transform to elements. |
| #[inline] |
| fn map<F, B>(self, f: F) -> Map<Self, F, B> |
| where |
| Self: Sized, |
| F: FnMut(&Self::Item) -> B, |
| { |
| Map { |
| it: self, |
| f: f, |
| value: None, |
| } |
| } |
| |
| /// Returns an iterator which applies a transform to elements. |
| /// |
| /// Unlike `map`, the the closure provided to this method returns a reference into the original |
| /// value. |
| #[inline] |
| fn map_ref<F, B: ?Sized>(self, f: F) -> MapRef<Self, F> |
| where |
| Self: Sized, |
| F: Fn(&Self::Item) -> &B, |
| { |
| MapRef { it: self, f: f } |
| } |
| |
| /// Returns an iterator that applies a transform to errors. |
| #[inline] |
| fn map_err<F, B>(self, f: F) -> MapErr<Self, F> |
| where |
| Self: Sized, |
| F: Fn(Self::Error) -> B, |
| { |
| MapErr { it: self, f: f } |
| } |
| |
| /// Returns the `nth` element of the iterator. |
| #[inline] |
| fn nth(&mut self, n: usize) -> Result<Option<&Self::Item>, Self::Error> { |
| for _ in 0..n { |
| self.advance()?; |
| if let None = self.get() { |
| return Ok(None); |
| } |
| } |
| self.next() |
| } |
| |
| /// Returns the position of the first element matching a predicate. |
| #[inline] |
| fn position<F>(&mut self, mut f: F) -> Result<Option<usize>, Self::Error> |
| where |
| Self: Sized, |
| F: FnMut(&Self::Item) -> bool, |
| { |
| let mut pos = 0; |
| while let Some(v) = self.next()? { |
| if f(v) { |
| return Ok(Some(pos)); |
| } |
| pos += 1; |
| } |
| Ok(None) |
| } |
| |
| /// Returns an iterator which skips the first `n` elements. |
| #[inline] |
| fn skip(self, n: usize) -> Skip<Self> |
| where |
| Self: Sized, |
| { |
| Skip { it: self, n: n } |
| } |
| |
| /// Returns an iterator which skips the first sequence of elements matching a predicate. |
| #[inline] |
| fn skip_while<F>(self, f: F) -> SkipWhile<Self, F> |
| where |
| Self: Sized, |
| F: FnMut(&Self::Item) -> bool, |
| { |
| SkipWhile { |
| it: self, |
| f: f, |
| done: false, |
| } |
| } |
| |
| /// Returns an iterator which only returns the first `n` elements. |
| #[inline] |
| fn take(self, n: usize) -> Take<Self> |
| where |
| Self: Sized, |
| { |
| Take { |
| it: self, |
| n: n, |
| done: false, |
| } |
| } |
| |
| /// Returns an iterator which only returns the first sequence of elements matching a predicate. |
| #[inline] |
| fn take_while<F>(self, f: F) -> TakeWhile<Self, F> |
| where |
| Self: Sized, |
| F: FnMut(&Self::Item) -> bool, |
| { |
| TakeWhile { |
| it: self, |
| f: f, |
| done: false, |
| } |
| } |
| } |
| |
| /// A fallible, streaming iterator which can be advanced from either end. |
| pub trait DoubleEndedFallibleStreamingIterator: FallibleStreamingIterator { |
| /// Advances the state of the iterator to the next item from the end. |
| /// |
| /// Iterators start just after the last item, so this method should be called before `get` |
| /// when iterating. |
| /// |
| /// The behavior of calling this method after `get` has returned `None`, or after this method |
| /// or `advance` has returned an error is unspecified. |
| fn advance_back(&mut self) -> Result<(), Self::Error>; |
| |
| /// Advances the back of the iterator, returning the last element. |
| /// |
| /// The default implementation simply calls `advance_back` followed by `get`. |
| #[inline] |
| fn next_back(&mut self) -> Result<Option<&Self::Item>, Self::Error> { |
| self.advance_back()?; |
| Ok((*self).get()) |
| } |
| } |
| |
| impl<'a, I: ?Sized> FallibleStreamingIterator for &'a mut I |
| where |
| I: FallibleStreamingIterator, |
| { |
| type Item = I::Item; |
| type Error = I::Error; |
| |
| #[inline] |
| fn advance(&mut self) -> Result<(), I::Error> { |
| (**self).advance() |
| } |
| |
| #[inline] |
| fn get(&self) -> Option<&I::Item> { |
| (**self).get() |
| } |
| |
| #[inline] |
| fn size_hint(&self) -> (usize, Option<usize>) { |
| (**self).size_hint() |
| } |
| |
| #[inline] |
| fn next(&mut self) -> Result<Option<&I::Item>, I::Error> { |
| (**self).next() |
| } |
| } |
| |
| #[cfg(feature = "std")] |
| impl<I: ?Sized> FallibleStreamingIterator for Box<I> |
| where |
| I: FallibleStreamingIterator, |
| { |
| type Item = I::Item; |
| type Error = I::Error; |
| |
| #[inline] |
| fn advance(&mut self) -> Result<(), I::Error> { |
| (**self).advance() |
| } |
| |
| #[inline] |
| fn get(&self) -> Option<&I::Item> { |
| (**self).get() |
| } |
| |
| #[inline] |
| fn size_hint(&self) -> (usize, Option<usize>) { |
| (**self).size_hint() |
| } |
| |
| #[inline] |
| fn next(&mut self) -> Result<Option<&I::Item>, I::Error> { |
| (**self).next() |
| } |
| } |
| |
| /// Converts a normal `Iterator` over `Results` of references into a |
| /// `FallibleStreamingIterator`. |
| pub fn convert<'a, I, T, E>(it: I) -> Convert<'a, I, T> |
| where |
| I: Iterator<Item = Result<&'a T, E>>, |
| { |
| Convert { it: it, item: None } |
| } |
| |
| /// An iterator which wraps a normal `Iterator`. |
| pub struct Convert<'a, I, T: 'a> { |
| it: I, |
| item: Option<&'a T>, |
| } |
| |
| impl<'a, I, T, E> FallibleStreamingIterator for Convert<'a, I, T> |
| where |
| I: Iterator<Item = Result<&'a T, E>>, |
| { |
| type Item = T; |
| type Error = E; |
| |
| #[inline] |
| fn advance(&mut self) -> Result<(), E> { |
| self.item = match self.it.next() { |
| Some(Ok(v)) => Some(v), |
| Some(Err(e)) => return Err(e), |
| None => None, |
| }; |
| Ok(()) |
| } |
| |
| #[inline] |
| fn get(&self) -> Option<&T> { |
| self.item |
| } |
| |
| #[inline] |
| fn size_hint(&self) -> (usize, Option<usize>) { |
| self.it.size_hint() |
| } |
| } |
| |
| impl<'a, I, T, E> DoubleEndedFallibleStreamingIterator for Convert<'a, I, T> |
| where |
| I: DoubleEndedIterator<Item = Result<&'a T, E>>, |
| { |
| #[inline] |
| fn advance_back(&mut self) -> Result<(), E> { |
| self.item = match self.it.next_back() { |
| Some(Ok(v)) => Some(v), |
| Some(Err(e)) => return Err(e), |
| None => None, |
| }; |
| Ok(()) |
| } |
| } |
| |
| /// Returns an iterator over no items. |
| pub fn empty<T, E>() -> Empty<T, E> { |
| Empty(PhantomData) |
| } |
| |
| /// An iterator over no items. |
| pub struct Empty<T, E>(PhantomData<(T, E)>); |
| |
| impl<T, E> FallibleStreamingIterator for Empty<T, E> { |
| type Item = T; |
| type Error = E; |
| |
| #[inline] |
| fn advance(&mut self) -> Result<(), E> { |
| Ok(()) |
| } |
| |
| #[inline] |
| fn get(&self) -> Option<&T> { |
| None |
| } |
| |
| #[inline] |
| fn size_hint(&self) -> (usize, Option<usize>) { |
| (0, Some(0)) |
| } |
| } |
| |
| impl<T, E> DoubleEndedFallibleStreamingIterator for Empty<T, E> { |
| #[inline] |
| fn advance_back(&mut self) -> Result<(), E> { |
| Ok(()) |
| } |
| } |
| |
| /// An iterator which filters elements with a predicate. |
| pub struct Filter<I, F> { |
| it: I, |
| f: F, |
| } |
| |
| impl<I, F> FallibleStreamingIterator for Filter<I, F> |
| where |
| I: FallibleStreamingIterator, |
| F: FnMut(&I::Item) -> bool, |
| { |
| type Item = I::Item; |
| type Error = I::Error; |
| |
| #[inline] |
| fn advance(&mut self) -> Result<(), I::Error> { |
| while let Some(i) = self.it.next()? { |
| if (self.f)(i) { |
| break; |
| } |
| } |
| Ok(()) |
| } |
| |
| #[inline] |
| fn get(&self) -> Option<&I::Item> { |
| self.it.get() |
| } |
| |
| #[inline] |
| fn size_hint(&self) -> (usize, Option<usize>) { |
| (0, self.it.size_hint().1) |
| } |
| } |
| |
| #[derive(Copy, Clone)] |
| enum FuseState { |
| Start, |
| Middle, |
| End, |
| } |
| |
| /// An iterator which is well-behaved at the beginning and end of iteration. |
| pub struct Fuse<I> { |
| it: I, |
| state: FuseState, |
| } |
| |
| impl<I> FallibleStreamingIterator for Fuse<I> |
| where |
| I: FallibleStreamingIterator, |
| { |
| type Item = I::Item; |
| type Error = I::Error; |
| |
| #[inline] |
| fn advance(&mut self) -> Result<(), I::Error> { |
| match self.state { |
| FuseState::Start => { |
| match self.it.next() { |
| Ok(Some(_)) => self.state = FuseState::Middle, |
| Ok(None) => self.state = FuseState::End, |
| Err(e) => { |
| self.state = FuseState::End; |
| return Err(e); |
| } |
| }; |
| } |
| FuseState::Middle => match self.it.next() { |
| Ok(Some(_)) => {} |
| Ok(None) => self.state = FuseState::End, |
| Err(e) => { |
| self.state = FuseState::End; |
| return Err(e); |
| } |
| }, |
| FuseState::End => {} |
| } |
| Ok(()) |
| } |
| |
| #[inline] |
| fn get(&self) -> Option<&I::Item> { |
| match self.state { |
| FuseState::Middle => self.it.get(), |
| FuseState::Start | FuseState::End => None, |
| } |
| } |
| |
| #[inline] |
| fn size_hint(&self) -> (usize, Option<usize>) { |
| self.it.size_hint() |
| } |
| |
| #[inline] |
| fn next(&mut self) -> Result<Option<&I::Item>, I::Error> { |
| match self.state { |
| FuseState::Start => match self.it.next() { |
| Ok(Some(v)) => { |
| self.state = FuseState::Middle; |
| Ok(Some(v)) |
| } |
| Ok(None) => { |
| self.state = FuseState::End; |
| Ok(None) |
| } |
| Err(e) => { |
| self.state = FuseState::End; |
| Err(e) |
| } |
| }, |
| FuseState::Middle => match self.it.next() { |
| Ok(Some(v)) => Ok(Some(v)), |
| Ok(None) => { |
| self.state = FuseState::End; |
| Ok(None) |
| } |
| Err(e) => { |
| self.state = FuseState::End; |
| Err(e) |
| } |
| }, |
| FuseState::End => Ok(None), |
| } |
| } |
| } |
| |
| /// An iterator which applies a transform to elements. |
| pub struct Map<I, F, B> { |
| it: I, |
| f: F, |
| value: Option<B>, |
| } |
| |
| impl<I, F, B> FallibleStreamingIterator for Map<I, F, B> |
| where |
| I: FallibleStreamingIterator, |
| F: FnMut(&I::Item) -> B, |
| { |
| type Item = B; |
| type Error = I::Error; |
| |
| #[inline] |
| fn advance(&mut self) -> Result<(), I::Error> { |
| self.value = self.it.next()?.map(&mut self.f); |
| Ok(()) |
| } |
| |
| #[inline] |
| fn get(&self) -> Option<&B> { |
| self.value.as_ref() |
| } |
| |
| #[inline] |
| fn size_hint(&self) -> (usize, Option<usize>) { |
| self.it.size_hint() |
| } |
| } |
| |
| impl<I, F, B> DoubleEndedFallibleStreamingIterator for Map<I, F, B> |
| where |
| I: DoubleEndedFallibleStreamingIterator, |
| F: FnMut(&I::Item) -> B, |
| { |
| #[inline] |
| fn advance_back(&mut self) -> Result<(), I::Error> { |
| self.value = self.it.next_back()?.map(&mut self.f); |
| Ok(()) |
| } |
| } |
| |
| /// An iterator which applies a transform to elements. |
| pub struct MapRef<I, F> { |
| it: I, |
| f: F, |
| } |
| |
| impl<I, F, B: ?Sized> FallibleStreamingIterator for MapRef<I, F> |
| where |
| I: FallibleStreamingIterator, |
| F: Fn(&I::Item) -> &B, |
| { |
| type Item = B; |
| type Error = I::Error; |
| |
| #[inline] |
| fn advance(&mut self) -> Result<(), I::Error> { |
| self.it.advance() |
| } |
| |
| #[inline] |
| fn get(&self) -> Option<&B> { |
| self.it.get().map(&self.f) |
| } |
| |
| #[inline] |
| fn size_hint(&self) -> (usize, Option<usize>) { |
| self.it.size_hint() |
| } |
| } |
| |
| impl<I, F, B: ?Sized> DoubleEndedFallibleStreamingIterator for MapRef<I, F> |
| where |
| I: DoubleEndedFallibleStreamingIterator, |
| F: Fn(&I::Item) -> &B, |
| { |
| #[inline] |
| fn advance_back(&mut self) -> Result<(), I::Error> { |
| self.it.advance_back() |
| } |
| } |
| |
| /// An iterator which applies a transform to errors. |
| pub struct MapErr<I, F> { |
| it: I, |
| f: F, |
| } |
| |
| impl<I, F, B> FallibleStreamingIterator for MapErr<I, F> |
| where |
| I: FallibleStreamingIterator, |
| F: Fn(I::Error) -> B, |
| { |
| type Item = I::Item; |
| type Error = B; |
| |
| #[inline] |
| fn advance(&mut self) -> Result<(), B> { |
| self.it.advance().map_err(&mut self.f) |
| } |
| |
| #[inline] |
| fn get(&self) -> Option<&I::Item> { |
| self.it.get() |
| } |
| |
| #[inline] |
| fn next(&mut self) -> Result<Option<&I::Item>, B> { |
| self.it.next().map_err(&mut self.f) |
| } |
| |
| #[inline] |
| fn size_hint(&self) -> (usize, Option<usize>) { |
| self.it.size_hint() |
| } |
| } |
| |
| impl<I, F, B> DoubleEndedFallibleStreamingIterator for MapErr<I, F> |
| where |
| I: DoubleEndedFallibleStreamingIterator, |
| F: Fn(I::Error) -> B, |
| { |
| #[inline] |
| fn advance_back(&mut self) -> Result<(), B> { |
| self.it.advance_back().map_err(&mut self.f) |
| } |
| |
| #[inline] |
| fn next_back(&mut self) -> Result<Option<&I::Item>, B> { |
| self.it.next_back().map_err(&mut self.f) |
| } |
| } |
| |
| /// An iterator which skips a number of initial elements. |
| pub struct Skip<I> { |
| it: I, |
| n: usize, |
| } |
| |
| impl<I> FallibleStreamingIterator for Skip<I> |
| where |
| I: FallibleStreamingIterator, |
| { |
| type Item = I::Item; |
| type Error = I::Error; |
| |
| #[inline] |
| fn advance(&mut self) -> Result<(), I::Error> { |
| for _ in 0..self.n { |
| if let None = self.it.next()? { |
| return Ok(()); |
| } |
| } |
| self.n = 0; |
| self.advance() |
| } |
| |
| #[inline] |
| fn get(&self) -> Option<&I::Item> { |
| self.it.get() |
| } |
| |
| #[inline] |
| fn size_hint(&self) -> (usize, Option<usize>) { |
| let hint = self.it.size_hint(); |
| ( |
| hint.0.saturating_sub(self.n), |
| hint.1.map(|h| h.saturating_sub(self.n)), |
| ) |
| } |
| } |
| |
| /// An iterator which skips initial elements matching a predicate. |
| pub struct SkipWhile<I, F> { |
| it: I, |
| f: F, |
| done: bool, |
| } |
| |
| impl<I, F> FallibleStreamingIterator for SkipWhile<I, F> |
| where |
| I: FallibleStreamingIterator, |
| F: FnMut(&I::Item) -> bool, |
| { |
| type Item = I::Item; |
| type Error = I::Error; |
| |
| #[inline] |
| fn advance(&mut self) -> Result<(), I::Error> { |
| if !self.done { |
| self.done = true; |
| let f = &mut self.f; |
| self.it.find(|i| !f(i)).map(|_| ()) |
| } else { |
| self.it.advance() |
| } |
| } |
| |
| #[inline] |
| fn get(&self) -> Option<&I::Item> { |
| self.it.get() |
| } |
| |
| #[inline] |
| fn size_hint(&self) -> (usize, Option<usize>) { |
| let hint = self.it.size_hint(); |
| if self.done { |
| hint |
| } else { |
| (0, hint.1) |
| } |
| } |
| } |
| |
| /// An iterator which only returns a number of initial elements. |
| pub struct Take<I> { |
| it: I, |
| n: usize, |
| done: bool, |
| } |
| |
| impl<I> FallibleStreamingIterator for Take<I> |
| where |
| I: FallibleStreamingIterator, |
| { |
| type Item = I::Item; |
| type Error = I::Error; |
| |
| #[inline] |
| fn advance(&mut self) -> Result<(), I::Error> { |
| if self.n != 0 { |
| self.it.advance()?; |
| self.n -= 1; |
| } else { |
| self.done = true; |
| } |
| Ok(()) |
| } |
| |
| #[inline] |
| fn get(&self) -> Option<&I::Item> { |
| if self.done { |
| None |
| } else { |
| self.it.get() |
| } |
| } |
| |
| #[inline] |
| fn size_hint(&self) -> (usize, Option<usize>) { |
| let (lower, upper) = self.it.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) |
| } |
| } |
| |
| /// An iterator which only returns initial elements matching a predicate. |
| pub struct TakeWhile<I, F> { |
| it: I, |
| f: F, |
| done: bool, |
| } |
| |
| impl<I, F> FallibleStreamingIterator for TakeWhile<I, F> |
| where |
| I: FallibleStreamingIterator, |
| F: FnMut(&I::Item) -> bool, |
| { |
| type Item = I::Item; |
| type Error = I::Error; |
| |
| #[inline] |
| fn advance(&mut self) -> Result<(), I::Error> { |
| if let Some(v) = self.it.next()? { |
| if !(self.f)(v) { |
| self.done = true; |
| } |
| } |
| Ok(()) |
| } |
| |
| #[inline] |
| fn get(&self) -> Option<&I::Item> { |
| if self.done { |
| None |
| } else { |
| self.it.get() |
| } |
| } |
| |
| #[inline] |
| fn size_hint(&self) -> (usize, Option<usize>) { |
| if self.done { |
| (0, Some(0)) |
| } else { |
| (0, self.it.size_hint().1) |
| } |
| } |
| } |
| |
| #[cfg(test)] |
| mod test { |
| use super::*; |
| |
| fn _is_object_safe(_: &FallibleStreamingIterator<Item = (), Error = ()>) {} |
| fn _is_object_safe_double(_: &DoubleEndedFallibleStreamingIterator<Item = (), Error = ()>) {} |
| } |