Composable external iterators
The Iterator
trait defines an interface for objects which implement iteration as a state machine.
Algorithms like zip
are provided as Iterator
implementations which wrap other objects implementing the Iterator
trait.
ChainIterator
- An iterator which strings two iterators togetherCounter
- An infinite iterator starting at start
and advancing by step
with each iterationEnumerateIterator
- An iterator which yields the current count and the element during iterationFilterIterator
- An iterator which filters the elements of iter
with predicate
FilterMapIterator
- An iterator which uses f
to both filter and map elements from iter
FlatMapIterator
- An iterator that maps each element to an iterator, and yields the elements of the produced iteratorsMapIterator
- An iterator which maps the values of iter
with f
ScanIterator
- An iterator to maintain state while iterating another iteratorSkipIterator
- An iterator which skips over n
elements of iter
.SkipWhileIterator
- An iterator which rejects elements while predicate
is trueTakeIterator
- An iterator which only iterates over the first n
iterations of iter
.TakeWhileIterator
- An iterator which only accepts elements while predicate
is trueUnfoldrIterator
- An iterator which just modifies the contained state throughout iteration.ZipIterator
- An iterator which iterates two other iterators simultaneouslyAdditiveIterator
- A trait for iterators over elements which can be added togetherFromIterator
- Conversion from an Iterator
Iterator
- An interface for dealing with "external iterators"IteratorUtil
- Iterator adaptors provided for every Iterator
implementationMultiplicativeIterator
- A trait for iterators over elements whose elements can be multiplied together.OrdIterator
- A trait for iterators over elements which can be compared to one anotherof IteratorUtil<A> for T where <A, T: Iterator<A>>
- Iterator adaptors provided for every Iterator
implementationof AdditiveIterator<A> for T where <A: Add<A, A> + Zero, T: Iterator<A>>
of MultiplicativeIterator<A> for T where <A: Mul<A, A> + One, T: Iterator<A>>
of OrdIterator<A> for T where <A: Ord, T: Iterator<A>>
of Iterator<A> for ChainIterator<A, T, U> where <A, T: Iterator<A>, U: Iterator<A>>
of Iterator<(A, B)> for ZipIterator<A, T, B, U> where <A, B, T: Iterator<A>, U: Iterator<B>>
of Iterator<B> for MapIterator<'self, A, B, T> where <'self, A, B, T: Iterator<A>>
of Iterator<A> for FilterIterator<'self, A, T> where <'self, A, T: Iterator<A>>
of Iterator<B> for FilterMapIterator<'self, A, B, T> where <'self, A, B, T: Iterator<A>>
of Iterator<(uint, A)> for EnumerateIterator<A, T> where <A, T: Iterator<A>>
of Iterator<A> for SkipWhileIterator<'self, A, T> where <'self, A, T: Iterator<A>>
of Iterator<A> for TakeWhileIterator<'self, A, T> where <'self, A, T: Iterator<A>>
of Iterator<A> for SkipIterator<A, T> where <A, T: Iterator<A>>
of Iterator<A> for TakeIterator<A, T> where <A, T: Iterator<A>>
of Iterator<B> for ScanIterator<'self, A, B, T, St> where <'self, A, B, T: Iterator<A>, St>
of Iterator<B> for FlatMapIterator<'self, A, B, T, U> where <'self, A, T: Iterator<A>, B, U: Iterator<B>>
for UnfoldrIterator<'self, A, St> where <'self, A, St>
of Iterator<A> for UnfoldrIterator<'self, A, St> where <'self, A, St>
for Counter<A> where <A>
of Iterator<A> for Counter<A> where <A: Add<A, A> + Clone>
ChainIterator
pub struct ChainIterator<A, T, U> {
priv a: T,
priv b: U,
priv flag: bool,
}
An iterator which strings two iterators together
Counter
pub struct Counter<A> {
/// The current state the counter is at (next value to be yielded)
state: A,
/// The amount that this iterator is stepping by
step: A,
}
An infinite iterator starting at start
and advancing by step
with each iteration
EnumerateIterator
pub struct EnumerateIterator<A, T> {
priv iter: T,
priv count: uint,
}
An iterator which yields the current count and the element during iteration
FilterIterator
pub struct FilterIterator<'self, A, T> {
priv iter: T,
priv predicate: &'self fn(&A) -> bool,
}
An iterator which filters the elements of iter
with predicate
FilterMapIterator
pub struct FilterMapIterator<'self, A, B, T> {
priv iter: T,
priv f: &'self fn(A) -> Option<B>,
}
An iterator which uses f
to both filter and map elements from iter
FlatMapIterator
pub struct FlatMapIterator<'self, A, B, T, U> {
priv iter: T,
priv f: &'self fn(A) -> U,
priv subiter: Option<U>,
}
An iterator that maps each element to an iterator, and yields the elements of the produced iterators
MapIterator
pub struct MapIterator<'self, A, B, T> {
priv iter: T,
priv f: &'self fn(A) -> B,
}
An iterator which maps the values of iter
with f
ScanIterator
pub struct ScanIterator<'self, A, B, T, St> {
priv iter: T,
priv f: &'self fn(&mut St, A) -> Option<B>,
/// The current internal state to be passed to the closure next.
state: St,
}
An iterator to maintain state while iterating another iterator
SkipIterator
pub struct SkipIterator<A, T> {
priv iter: T,
priv n: uint,
}
An iterator which skips over n
elements of iter
.
SkipWhileIterator
pub struct SkipWhileIterator<'self, A, T> {
priv iter: T,
priv flag: bool,
priv predicate: &'self fn(&A) -> bool,
}
An iterator which rejects elements while predicate
is true
TakeIterator
pub struct TakeIterator<A, T> {
priv iter: T,
priv n: uint,
}
An iterator which only iterates over the first n
iterations of iter
.
TakeWhileIterator
pub struct TakeWhileIterator<'self, A, T> {
priv iter: T,
priv flag: bool,
priv predicate: &'self fn(&A) -> bool,
}
An iterator which only accepts elements while predicate
is true
UnfoldrIterator
pub struct UnfoldrIterator<'self, A, St> {
priv f: &'self fn(&mut St) -> Option<A>,
/// Internal state that will be yielded on the next iteration
state: St,
}
An iterator which just modifies the contained state throughout iteration.
ZipIterator
pub struct ZipIterator<A, T, B, U> {
priv a: T,
priv b: U,
}
An iterator which iterates two other iterators simultaneously
AdditiveIterator
A trait for iterators over elements which can be added together
sum
fn sum(&mut self) -> A
Iterates over the entire iterator, summing up all the elements
let a = [1, 2, 3, 4, 5];
let mut it = a.iter().transform(|&x| x);
assert!(it.sum() == 15);
FromIterator
Conversion from an Iterator
from_iterator
fn from_iterator(iterator: &mut T) -> Self
Build a container with elements from an external iterator.
Iterator
An interface for dealing with "external iterators". These types of iterators can be resumed at any time as all state is stored internally as opposed to being located on the call stack.
next
fn next(&mut self) -> Option<A>
Advance the iterator and return the next value. Return None
when the end is reached.
size_hint
fn size_hint(&self) -> (Option<uint>, Option<uint>)
Return a lower bound and upper bound on the remaining length of the iterator.
The common use case for the estimate is pre-allocating space to store the results.
IteratorUtil
Iterator adaptors provided for every Iterator
implementation. The adaptor objects are also implementations of the Iterator
trait.
In the future these will be default methods instead of a utility trait.
chain_
fn chain_<U: Iterator<A>>(self, other: U) -> ChainIterator<A, Self, U>
Chain this iterator with another, returning a new iterator which will finish iterating over the current iterator, and then it will iterate over the other specified iterator.
let a = [0];
let b = [1];
let mut it = a.iter().chain_(b.iter());
assert_eq!(it.next().get(), &0);
assert_eq!(it.next().get(), &1);
assert!(it.next().is_none());
zip
fn zip<B, U: Iterator<B>>(self, other: U) -> ZipIterator<A, Self, B, U>
Creates an iterator which iterates over both this and the specified iterators simultaneously, yielding the two elements as pairs. When either iterator returns None, all further invocations of next() will return None.
let a = [0];
let b = [1];
let mut it = a.iter().zip(b.iter());
assert_eq!(it.next().get(), (&0, &1));
assert!(it.next().is_none());
transform
fn transform<'r, B>(self, f: &'r fn(A) -> B) -> MapIterator<'r, A, B, Self>
Creates a new iterator which will apply the specified function to each element returned by the first, yielding the mapped element instead.
let a = [1, 2];
let mut it = a.iter().transform(|&x| 2 * x);
assert_eq!(it.next().get(), 2);
assert_eq!(it.next().get(), 4);
assert!(it.next().is_none());
filter
fn filter<'r>(self, predicate: &'r fn(&A) -> bool) ->
FilterIterator<'r, A, Self>
Creates an iterator which applies the predicate to each element returned by this iterator. Only elements which have the predicate evaluate to true
will be yielded.
let a = [1, 2];
let mut it = a.iter().filter(|&x| *x > 1);
assert_eq!(it.next().get(), &2);
assert!(it.next().is_none());
filter_map
fn filter_map<'r, B>(self, f: &'r fn(A) -> Option<B>) ->
FilterMapIterator<'r, A, B, Self>
Creates an iterator which both filters and maps elements. If the specified function returns None, the element is skipped. Otherwise the option is unwrapped and the new value is yielded.
let a = [1, 2];
let mut it = a.iter().filter_map(|&x| if x > 1 {Some(2 * x)} else {None});
assert_eq!(it.next().get(), 4);
assert!(it.next().is_none());
enumerate
fn enumerate(self) -> EnumerateIterator<A, Self>
Creates an iterator which yields a pair of the value returned by this iterator plus the current index of iteration.
let a = [100, 200];
let mut it = a.iter().enumerate();
assert_eq!(it.next().get(), (0, &100));
assert_eq!(it.next().get(), (1, &200));
assert!(it.next().is_none());
skip_while
fn skip_while<'r>(self, predicate: &'r fn(&A) -> bool) ->
SkipWhileIterator<'r, A, Self>
Creates an iterator which invokes the predicate on elements until it returns false. Once the predicate returns false, all further elements are yielded.
let a = [1, 2, 3, 2, 1];
let mut it = a.iter().skip_while(|&a| *a < 3);
assert_eq!(it.next().get(), &3);
assert_eq!(it.next().get(), &2);
assert_eq!(it.next().get(), &1);
assert!(it.next().is_none());
take_while
fn take_while<'r>(self, predicate: &'r fn(&A) -> bool) ->
TakeWhileIterator<'r, A, Self>
Creates an iterator which yields elements so long as the predicate returns true. After the predicate returns false for the first time, no further elements will be yielded.
let a = [1, 2, 3, 2, 1];
let mut it = a.iter().take_while(|&a| *a < 3);
assert_eq!(it.next().get(), &1);
assert_eq!(it.next().get(), &2);
assert!(it.next().is_none());
skip
fn skip(self, n: uint) -> SkipIterator<A, Self>
Creates an iterator which skips the first n
elements of this iterator, and then it yields all further items.
let a = [1, 2, 3, 4, 5];
let mut it = a.iter().skip(3);
assert_eq!(it.next().get(), &4);
assert_eq!(it.next().get(), &5);
assert!(it.next().is_none());
take_
fn take_(self, n: uint) -> TakeIterator<A, Self>
Creates an iterator which yields the first n
elements of this iterator, and then it will always return None.
let a = [1, 2, 3, 4, 5];
let mut it = a.iter().take_(3);
assert_eq!(it.next().get(), &1);
assert_eq!(it.next().get(), &2);
assert_eq!(it.next().get(), &3);
assert!(it.next().is_none());
scan
fn scan<'r, St,
B>(self, initial_state: St, f: &'r fn(&mut St, A) -> Option<B>) ->
ScanIterator<'r, A, B, Self, St>
Creates a new iterator which behaves in a similar fashion to foldl. There is a state which is passed between each iteration and can be mutated as necessary. The yielded values from the closure are yielded from the ScanIterator instance when not None.
let a = [1, 2, 3, 4, 5];
let mut it = a.iter().scan(1, |fac, &x| {
*fac = *fac * x;
Some(*fac)
});
assert_eq!(it.next().get(), 1);
assert_eq!(it.next().get(), 2);
assert_eq!(it.next().get(), 6);
assert_eq!(it.next().get(), 24);
assert_eq!(it.next().get(), 120);
assert!(it.next().is_none());
flat_map_
fn flat_map_<'r, B, U: Iterator<B>>(self, f: &'r fn(A) -> U) ->
FlatMapIterator<'r, A, B, Self, U>
Creates an iterator that maps each element to an iterator, and yields the elements of the produced iterators
let xs = [2u, 3];
let ys = [0u, 1, 0, 1, 2];
let mut it = xs.iter().flat_map_(|&x| Counter::new(0u, 1).take_(x));
// Check that `it` has the same elements as `ys`
let mut i = 0;
for it.advance |x: uint| {
assert_eq!(x, ys[i]);
i += 1;
}
advance
fn advance(&mut self, f: &fn(A) -> bool) -> bool
An adaptation of an external iterator to the for-loop protocol of rust.
use std::iterator::Counter;
for Counter::new(0, 10).advance |i| {
io::println(fmt!("%d", i));
}
collect
fn collect<B: FromIterator<A, Self>>(&mut self) -> B
Loops through the entire iterator, collecting all of the elements into a container implementing FromIterator
.
let a = [1, 2, 3, 4, 5];
let b: ~[int] = a.iter().transform(|&x| x).collect();
assert!(a == b);
nth
fn nth(&mut self, n: uint) -> Option<A>
Loops through n
iterations, returning the n
th element of the iterator.
let a = [1, 2, 3, 4, 5];
let mut it = a.iter();
assert!(it.nth(2).get() == &3);
assert!(it.nth(2) == None);
last_
fn last_(&mut self) -> Option<A>
Loops through the entire iterator, returning the last element of the iterator.
let a = [1, 2, 3, 4, 5];
assert!(a.iter().last().get() == &5);
fold
fn fold<B>(&mut self, start: B, f: &fn(B, A) -> B) -> B
Performs a fold operation over the entire iterator, returning the eventual state at the end of the iteration.
let a = [1, 2, 3, 4, 5];
assert!(a.iter().fold(0, |a, &b| a + b) == 15);
len_
fn len_(&mut self) -> uint
Counts the number of elements in this iterator.
let a = [1, 2, 3, 4, 5];
let mut it = a.iter();
assert!(it.len_() == 5);
assert!(it.len_() == 0);
all
fn all(&mut self, f: &fn(A) -> bool) -> bool
Tests whether the predicate holds true for all elements in the iterator.
let a = [1, 2, 3, 4, 5];
assert!(a.iter().all(|&x| *x > 0));
assert!(!a.iter().all(|&x| *x > 2));
any_
fn any_(&mut self, f: &fn(A) -> bool) -> bool
Tests whether any element of an iterator satisfies the specified predicate.
let a = [1, 2, 3, 4, 5];
let mut it = a.iter();
assert!(it.any_(|&x| *x == 3));
assert!(!it.any_(|&x| *x == 3));
find_
fn find_(&mut self, predicate: &fn(&A) -> bool) -> Option<A>
Return the first element satisfying the specified predicate
position_
fn position_(&mut self, predicate: &fn(A) -> bool) -> Option<uint>
Return the index of the first element satisfying the specified predicate
count
fn count(&mut self, predicate: &fn(A) -> bool) -> uint
Count the number of elements satisfying the specified predicate
max_by
fn max_by<B: Ord>(&mut self, f: &fn(&A) -> B) -> Option<A>
Return the element that gives the maximum value from the specfied function
let xs = [-3, 0, 1, 5, -10];
assert_eq!(*xs.iter().max_by(|x| x.abs()).unwrap(), -10);
min_by
fn min_by<B: Ord>(&mut self, f: &fn(&A) -> B) -> Option<A>
Return the element that gives the minimum value from the specfied function
let xs = [-3, 0, 1, 5, -10];
assert_eq!(*xs.iter().min_by(|x| x.abs()).unwrap(), 0);
MultiplicativeIterator
A trait for iterators over elements whose elements can be multiplied together.
product
fn product(&mut self) -> A
Iterates over the entire iterator, multiplying all the elements
use std::iterator::Counter;
fn factorial(n: uint) -> uint {
Counter::new(1u, 1).take_while(|&i| i <= n).product()
}
assert!(factorial(0) == 1);
assert!(factorial(1) == 1);
assert!(factorial(5) == 120);
OrdIterator
A trait for iterators over elements which can be compared to one another. The type of each element must ascribe to the Ord
trait.
max
fn max(&mut self) -> Option<A>
Consumes the entire iterator to return the maximum element.
let a = [1, 2, 3, 4, 5];
assert!(a.iter().max().get() == &5);
min
fn min(&mut self) -> Option<A>
Consumes the entire iterator to return the minimum element.
let a = [1, 2, 3, 4, 5];
assert!(a.iter().min().get() == &1);
IteratorUtil<A>
for T
where <A, T: Iterator<A>>
Iterator adaptors provided for every Iterator
implementation. The adaptor objects are also implementations of the Iterator
trait.
In the future these will be default methods instead of a utility trait.
chain_
fn chain_<U: Iterator<A>>(self, other: U) -> ChainIterator<A, T, U>
zip
fn zip<B, U: Iterator<B>>(self, other: U) -> ZipIterator<A, T, B, U>
transform
fn transform<'r, B>(self, f: &'r fn(A) -> B) -> MapIterator<'r, A, B, T>
filter
fn filter<'r>(self, predicate: &'r fn(&A) -> bool) -> FilterIterator<'r, A, T>
filter_map
fn filter_map<'r, B>(self, f: &'r fn(A) -> Option<B>) ->
FilterMapIterator<'r, A, B, T>
enumerate
fn enumerate(self) -> EnumerateIterator<A, T>
skip_while
fn skip_while<'r>(self, predicate: &'r fn(&A) -> bool) ->
SkipWhileIterator<'r, A, T>
take_while
fn take_while<'r>(self, predicate: &'r fn(&A) -> bool) ->
TakeWhileIterator<'r, A, T>
skip
fn skip(self, n: uint) -> SkipIterator<A, T>
take_
fn take_(self, n: uint) -> TakeIterator<A, T>
scan
fn scan<'r, St,
B>(self, initial_state: St, f: &'r fn(&mut St, A) -> Option<B>) ->
ScanIterator<'r, A, B, T, St>
flat_map_
fn flat_map_<'r, B, U: Iterator<B>>(self, f: &'r fn(A) -> U) ->
FlatMapIterator<'r, A, B, T, U>
advance
fn advance(&mut self, f: &fn(A) -> bool) -> bool
A shim implementing the for
loop iteration protocol for iterator objects
collect
fn collect<B: FromIterator<A, T>>(&mut self) -> B
nth
fn nth(&mut self, mut n: uint) -> Option<A>
Return the n
th item yielded by an iterator.
last_
fn last_(&mut self) -> Option<A>
Return the last item yielded by an iterator.
fold
fn fold<B>(&mut self, init: B, f: &fn(B, A) -> B) -> B
Reduce an iterator to an accumulated value
len_
fn len_(&mut self) -> uint
Count the number of items yielded by an iterator
all
fn all(&mut self, f: &fn(A) -> bool) -> bool
any_
fn any_(&mut self, f: &fn(A) -> bool) -> bool
find_
fn find_(&mut self, predicate: &fn(&A) -> bool) -> Option<A>
Return the first element satisfying the specified predicate
position_
fn position_(&mut self, predicate: &fn(A) -> bool) -> Option<uint>
Return the index of the first element satisfying the specified predicate
count
fn count(&mut self, predicate: &fn(A) -> bool) -> uint
max_by
fn max_by<B: Ord>(&mut self, f: &fn(&A) -> B) -> Option<A>
min_by
fn min_by<B: Ord>(&mut self, f: &fn(&A) -> B) -> Option<A>
AdditiveIterator<A>
for T
where <A: Add<A, A> + Zero, T: Iterator<A>>
sum
fn sum(&mut self) -> A
MultiplicativeIterator<A>
for T
where <A: Mul<A, A> + One, T: Iterator<A>>
product
fn product(&mut self) -> A
OrdIterator<A>
for T
where <A: Ord, T: Iterator<A>>
max
fn max(&mut self) -> Option<A>
min
fn min(&mut self) -> Option<A>
Iterator<A>
for ChainIterator<A, T, U>
where <A, T: Iterator<A>, U: Iterator<A>>
next
fn next(&mut self) -> Option<A>
size_hint
fn size_hint(&self) -> (Option<uint>, Option<uint>)
Iterator<(A, B)>
for ZipIterator<A, T, B, U>
where <A, B, T: Iterator<A>, U: Iterator<B>>
next
fn next(&mut self) -> Option<(A, B)>
Iterator<B>
for MapIterator<'self, A, B, T>
where <'self, A, B, T: Iterator<A>>
next
fn next(&mut self) -> Option<B>
size_hint
fn size_hint(&self) -> (Option<uint>, Option<uint>)
Iterator<A>
for FilterIterator<'self, A, T>
where <'self, A, T: Iterator<A>>
next
fn next(&mut self) -> Option<A>
size_hint
fn size_hint(&self) -> (Option<uint>, Option<uint>)
Iterator<B>
for FilterMapIterator<'self, A, B, T>
where <'self, A, B, T: Iterator<A>>
next
fn next(&mut self) -> Option<B>
size_hint
fn size_hint(&self) -> (Option<uint>, Option<uint>)
Iterator<(uint, A)>
for EnumerateIterator<A, T>
where <A, T: Iterator<A>>
next
fn next(&mut self) -> Option<(uint, A)>
Iterator<A>
for SkipWhileIterator<'self, A, T>
where <'self, A, T: Iterator<A>>
next
fn next(&mut self) -> Option<A>
Iterator<A>
for TakeWhileIterator<'self, A, T>
where <'self, A, T: Iterator<A>>
next
fn next(&mut self) -> Option<A>
Iterator<A>
for SkipIterator<A, T>
where <A, T: Iterator<A>>
next
fn next(&mut self) -> Option<A>
Iterator<A>
for TakeIterator<A, T>
where <A, T: Iterator<A>>
next
fn next(&mut self) -> Option<A>
Iterator<B>
for ScanIterator<'self, A, B, T, St>
where <'self, A, B, T: Iterator<A>, St>
next
fn next(&mut self) -> Option<B>
Iterator<B>
for FlatMapIterator<'self, A, B, T, U>
where <'self, A, T: Iterator<A>, B, U: Iterator<B>>
next
fn next(&mut self) -> Option<B>
UnfoldrIterator<'self, A, St>
where <'self, A, St>
new
fn new<'a>(initial_state: St, f: &'a fn(&mut St) -> Option<A>) ->
UnfoldrIterator<'a, A, St>
Creates a new iterator with the specified closure as the "iterator function" and an initial state to eventually pass to the iterator
Iterator<A>
for UnfoldrIterator<'self, A, St>
where <'self, A, St>
next
fn next(&mut self) -> Option<A>
Counter<A>
where <A>
new
fn new(start: A, step: A) -> Counter<A>
Creates a new counter with the specified start/step
Iterator<A>
for Counter<A>
where <A: Add<A, A> + Clone>
next
fn next(&mut self) -> Option<A>