std: merge Iterator and IteratorUtil

1 files changed, 192 insertions, 268 deletions

diff --git a/src/libstd/iterator.rs b/src/libstd/iterator.rs
index 3e0f9344600..48d058c6f1c 100644
--- a/src/libstd/iterator.rs
+++ b/src/libstd/iterator.rs
@@ -49,76 +49,7 @@ pub trait Iterator<A> {
     /// The common use case for the estimate is pre-allocating space to store the results.
     #[inline]
     fn size_hint(&self) -> (uint, Option<uint>) { (0, None) }
-}
-
-/// A range iterator able to yield elements from both ends
-pub trait DoubleEndedIterator<A>: Iterator<A> {
-    /// Yield an element from the end of the range, returning `None` if the range is empty.
-    fn next_back(&mut self) -> Option<A>;
-
-    /// Flip the direction of the iterator
-    ///
-    /// The inverted iterator flips the ends on an iterator that can already
-    /// be iterated from the front and from the back.
-    ///
-    ///
-    /// If the iterator also implements RandomAccessIterator, the inverted
-    /// iterator is also random access, with the indices starting at the back
-    /// of the original iterator.
-    ///
-    /// Note: Random access with inverted indices still only applies to the first
-    /// `uint::max_value` elements of the original iterator.
-    #[inline]
-    fn invert(self) -> Invert<Self> {
-        Invert{iter: self}
-    }
-}
 
-/// An object implementing random access indexing by `uint`
-///
-/// A `RandomAccessIterator` should be either infinite or a `DoubleEndedIterator`.
-pub trait RandomAccessIterator<A>: Iterator<A> {
-    /// Return the number of indexable elements. At most `std::uint::max_value`
-    /// elements are indexable, even if the iterator represents a longer range.
-    fn indexable(&self) -> uint;
-
-    /// Return an element at an index
-    fn idx(&self, index: uint) -> Option<A>;
-}
-
-/// An double-ended iterator with the direction inverted
-#[deriving(Clone)]
-pub struct Invert<T> {
-    priv iter: T
-}
-
-impl<A, T: DoubleEndedIterator<A>> Iterator<A> for Invert<T> {
-    #[inline]
-    fn next(&mut self) -> Option<A> { self.iter.next_back() }
-    #[inline]
-    fn size_hint(&self) -> (uint, Option<uint>) { self.iter.size_hint() }
-}
-
-impl<A, T: DoubleEndedIterator<A>> DoubleEndedIterator<A> for Invert<T> {
-    #[inline]
-    fn next_back(&mut self) -> Option<A> { self.iter.next() }
-}
-
-impl<A, T: DoubleEndedIterator<A> + RandomAccessIterator<A>> RandomAccessIterator<A>
-    for Invert<T> {
-    #[inline]
-    fn indexable(&self) -> uint { self.iter.indexable() }
-    #[inline]
-    fn idx(&self, index: uint) -> Option<A> {
-        self.iter.idx(self.indexable() - index - 1)
-    }
-}
-
-/// 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.
-pub trait IteratorUtil<A> {
     /// 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.
@@ -133,7 +64,10 @@ pub trait IteratorUtil<A> {
     /// assert_eq!(it.next().get(), &1);
     /// assert!(it.next().is_none());
     /// ~~~
-    fn chain_<U: Iterator<A>>(self, other: U) -> Chain<Self, U>;
+    #[inline]
+    fn chain_<U: Iterator<A>>(self, other: U) -> Chain<Self, U> {
+        Chain{a: self, b: other, flag: false}
+    }
 
     /// Creates an iterator which iterates over both this and the specified
     /// iterators simultaneously, yielding the two elements as pairs. When
@@ -149,7 +83,10 @@ pub trait IteratorUtil<A> {
     /// assert_eq!(it.next().get(), (&0, &1));
     /// assert!(it.next().is_none());
     /// ~~~
-    fn zip<B, U: Iterator<B>>(self, other: U) -> Zip<Self, U>;
+    #[inline]
+    fn zip<B, U: Iterator<B>>(self, other: U) -> Zip<Self, U> {
+        Zip{a: self, b: other}
+    }
 
     // FIXME: #5898: should be called map
     /// Creates a new iterator which will apply the specified function to each
@@ -164,7 +101,10 @@ pub trait IteratorUtil<A> {
     /// assert_eq!(it.next().get(), 4);
     /// assert!(it.next().is_none());
     /// ~~~
-    fn transform<'r, B>(self, f: &'r fn(A) -> B) -> Map<'r, A, B, Self>;
+    #[inline]
+    fn transform<'r, B>(self, f: &'r fn(A) -> B) -> Map<'r, A, B, Self> {
+        Map{iter: self, f: f}
+    }
 
     /// Creates an iterator which applies the predicate to each element returned
     /// by this iterator. Only elements which have the predicate evaluate to
@@ -178,7 +118,10 @@ pub trait IteratorUtil<A> {
     /// assert_eq!(it.next().get(), &2);
     /// assert!(it.next().is_none());
     /// ~~~
-    fn filter<'r>(self, predicate: &'r fn(&A) -> bool) -> Filter<'r, A, Self>;
+    #[inline]
+    fn filter<'r>(self, predicate: &'r fn(&A) -> bool) -> Filter<'r, A, Self> {
+        Filter{iter: self, predicate: predicate}
+    }
 
     /// Creates an iterator which both filters and maps elements.
     /// If the specified function returns None, the element is skipped.
@@ -192,7 +135,10 @@ pub trait IteratorUtil<A> {
     /// assert_eq!(it.next().get(), 4);
     /// assert!(it.next().is_none());
     /// ~~~
-    fn filter_map<'r,  B>(self, f: &'r fn(A) -> Option<B>) -> FilterMap<'r, A, B, Self>;
+    #[inline]
+    fn filter_map<'r, B>(self, f: &'r fn(A) -> Option<B>) -> FilterMap<'r, A, B, Self> {
+        FilterMap { iter: self, f: f }
+    }
 
     /// Creates an iterator which yields a pair of the value returned by this
     /// iterator plus the current index of iteration.
@@ -206,7 +152,10 @@ pub trait IteratorUtil<A> {
     /// assert_eq!(it.next().get(), (1, &200));
     /// assert!(it.next().is_none());
     /// ~~~
-    fn enumerate(self) -> Enumerate<Self>;
+    #[inline]
+    fn enumerate(self) -> Enumerate<Self> {
+        Enumerate{iter: self, count: 0}
+    }
 
     /// Creates an iterator which invokes the predicate on elements until it
     /// returns false. Once the predicate returns false, all further elements are
@@ -222,7 +171,10 @@ pub trait IteratorUtil<A> {
     /// assert_eq!(it.next().get(), &1);
     /// assert!(it.next().is_none());
     /// ~~~
-    fn skip_while<'r>(self, predicate: &'r fn(&A) -> bool) -> SkipWhile<'r, A, Self>;
+    #[inline]
+    fn skip_while<'r>(self, predicate: &'r fn(&A) -> bool) -> SkipWhile<'r, A, Self> {
+        SkipWhile{iter: self, flag: false, predicate: predicate}
+    }
 
     /// Creates an iterator which yields elements so long as the predicate
     /// returns true. After the predicate returns false for the first time, no
@@ -237,7 +189,10 @@ pub trait IteratorUtil<A> {
     /// assert_eq!(it.next().get(), &2);
     /// assert!(it.next().is_none());
     /// ~~~
-    fn take_while<'r>(self, predicate: &'r fn(&A) -> bool) -> TakeWhile<'r, A, Self>;
+    #[inline]
+    fn take_while<'r>(self, predicate: &'r fn(&A) -> bool) -> TakeWhile<'r, A, Self> {
+        TakeWhile{iter: self, flag: false, predicate: predicate}
+    }
 
     /// Creates an iterator which skips the first `n` elements of this iterator,
     /// and then it yields all further items.
@@ -251,7 +206,10 @@ pub trait IteratorUtil<A> {
     /// assert_eq!(it.next().get(), &5);
     /// assert!(it.next().is_none());
     /// ~~~
-    fn skip(self, n: uint) -> Skip<Self>;
+    #[inline]
+    fn skip(self, n: uint) -> Skip<Self> {
+        Skip{iter: self, n: n}
+    }
 
     // FIXME: #5898: should be called take
     /// Creates an iterator which yields the first `n` elements of this
@@ -267,7 +225,10 @@ pub trait IteratorUtil<A> {
     /// assert_eq!(it.next().get(), &3);
     /// assert!(it.next().is_none());
     /// ~~~
-    fn take_(self, n: uint) -> Take<Self>;
+    #[inline]
+    fn take_(self, n: uint) -> Take<Self> {
+        Take{iter: self, n: n}
+    }
 
     /// 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
@@ -289,8 +250,11 @@ pub trait IteratorUtil<A> {
     /// assert_eq!(it.next().get(), 120);
     /// assert!(it.next().is_none());
     /// ~~~
+    #[inline]
     fn scan<'r, St, B>(self, initial_state: St, f: &'r fn(&mut St, A) -> Option<B>)
-        -> Scan<'r, A, B, Self, St>;
+        -> Scan<'r, A, B, Self, St> {
+        Scan{iter: self, f: f, state: initial_state}
+    }
 
     /// Creates an iterator that maps each element to an iterator,
     /// and yields the elements of the produced iterators
@@ -309,8 +273,11 @@ pub trait IteratorUtil<A> {
     /// }
     /// ~~~
     // FIXME: #5898: should be called `flat_map`
+    #[inline]
     fn flat_map_<'r, B, U: Iterator<B>>(self, f: &'r fn(A) -> U)
-        -> FlatMap<'r, A, Self, U>;
+        -> FlatMap<'r, A, Self, U> {
+        FlatMap{iter: self, f: f, frontiter: None, backiter: None }
+    }
 
     /// Creates an iterator that calls a function with a reference to each
     /// element before yielding it. This is often useful for debugging an
@@ -329,7 +296,10 @@ pub trait IteratorUtil<A> {
     ///println(sum.to_str());
     /// ~~~
     // FIXME: #5898: should be called `peek`
-    fn peek_<'r>(self, f: &'r fn(&A)) -> Peek<'r, A, Self>;
+    #[inline]
+    fn peek_<'r>(self, f: &'r fn(&A)) -> Peek<'r, A, Self> {
+        Peek{iter: self, f: f}
+    }
 
     /// An adaptation of an external iterator to the for-loop protocol of rust.
     ///
@@ -342,7 +312,17 @@ pub trait IteratorUtil<A> {
     ///     printfln!("%d", i);
     /// }
     /// ~~~
-    fn advance(&mut self, f: &fn(A) -> bool) -> bool;
+    #[inline]
+    fn advance(&mut self, f: &fn(A) -> bool) -> bool {
+        loop {
+            match self.next() {
+                Some(x) => {
+                    if !f(x) { return false; }
+                }
+                None => { return true; }
+            }
+        }
+    }
 
     /// Loops through the entire iterator, collecting all of the elements into
     /// a container implementing `FromIterator`.
@@ -354,7 +334,10 @@ pub trait IteratorUtil<A> {
     /// let b: ~[int] = a.iter().transform(|&x| x).collect();
     /// assert!(a == b);
     /// ~~~
-    fn collect<B: FromIterator<A, Self>>(&mut self) -> B;
+    #[inline]
+    fn collect<B: FromIterator<A, Self>>(&mut self) -> B {
+        FromIterator::from_iterator(self)
+    }
 
     /// Loops through the entire iterator, collecting all of the elements into
     /// a unique vector. This is simply collect() specialized for vectors.
@@ -366,7 +349,10 @@ pub trait IteratorUtil<A> {
     /// let b: ~[int] = a.iter().transform(|&x| x).to_owned_vec();
     /// assert!(a == b);
     /// ~~~
-    fn to_owned_vec(&mut self) -> ~[A];
+    #[inline]
+    fn to_owned_vec(&mut self) -> ~[A] {
+        self.collect()
+    }
 
     /// Loops through `n` iterations, returning the `n`th element of the
     /// iterator.
@@ -379,7 +365,16 @@ pub trait IteratorUtil<A> {
     /// assert!(it.nth(2).get() == &3);
     /// assert!(it.nth(2) == None);
     /// ~~~
-    fn nth(&mut self, n: uint) -> Option<A>;
+    #[inline]
+    fn nth(&mut self, mut n: uint) -> Option<A> {
+        loop {
+            match self.next() {
+                Some(x) => if n == 0 { return Some(x) },
+                None => return None
+            }
+            n -= 1;
+        }
+    }
 
     /// Loops through the entire iterator, returning the last element of the
     /// iterator.
@@ -391,7 +386,12 @@ pub trait IteratorUtil<A> {
     /// assert!(a.iter().last().get() == &5);
     /// ~~~
     // FIXME: #5898: should be called `last`
-    fn last_(&mut self) -> Option<A>;
+    #[inline]
+    fn last_(&mut self) -> Option<A> {
+        let mut last = None;
+        for x in *self { last = Some(x); }
+        last
+    }
 
     /// Performs a fold operation over the entire iterator, returning the
     /// eventual state at the end of the iteration.
@@ -402,7 +402,17 @@ pub trait IteratorUtil<A> {
     /// let a = [1, 2, 3, 4, 5];
     /// assert!(a.iter().fold(0, |a, &b| a + b) == 15);
     /// ~~~
-    fn fold<B>(&mut self, start: B, f: &fn(B, A) -> B) -> B;
+    #[inline]
+    fn fold<B>(&mut self, init: B, f: &fn(B, A) -> B) -> B {
+        let mut accum = init;
+        loop {
+            match self.next() {
+                Some(x) => { accum = f(accum, x); }
+                None    => { break; }
+            }
+        }
+        accum
+    }
 
     // FIXME: #5898: should be called len
     /// Counts the number of elements in this iterator.
@@ -415,7 +425,10 @@ pub trait IteratorUtil<A> {
     /// assert!(it.len_() == 5);
     /// assert!(it.len_() == 0);
     /// ~~~
-    fn len_(&mut self) -> uint;
+    #[inline]
+    fn len_(&mut self) -> uint {
+        self.fold(0, |cnt, _x| cnt + 1)
+    }
 
     /// Tests whether the predicate holds true for all elements in the iterator.
     ///
@@ -426,7 +439,11 @@ pub trait IteratorUtil<A> {
     /// assert!(a.iter().all(|&x| *x > 0));
     /// assert!(!a.iter().all(|&x| *x > 2));
     /// ~~~
-    fn all(&mut self, f: &fn(A) -> bool) -> bool;
+    #[inline]
+    fn all(&mut self, f: &fn(A) -> bool) -> bool {
+        for x in *self { if !f(x) { return false; } }
+        true
+    }
 
     /// Tests whether any element of an iterator satisfies the specified
     /// predicate.
@@ -439,179 +456,6 @@ pub trait IteratorUtil<A> {
     /// assert!(it.any(|&x| *x == 3));
     /// assert!(!it.any(|&x| *x == 3));
     /// ~~~
-    fn any(&mut self, f: &fn(A) -> bool) -> bool;
-
-    /// Return the first element satisfying the specified predicate
-    fn find_(&mut self, predicate: &fn(&A) -> bool) -> Option<A>;
-
-    /// Return the index of the first element satisfying the specified predicate
-    fn position(&mut self, predicate: &fn(A) -> bool) -> Option<uint>;
-
-    /// Count the number of elements satisfying the specified predicate
-    fn count(&mut self, predicate: &fn(A) -> bool) -> uint;
-
-    /// Return the element that gives the maximum value from the specfied function
-    ///
-    /// # Example
-    ///
-    /// ~~~ {.rust}
-    /// let xs = [-3, 0, 1, 5, -10];
-    /// assert_eq!(*xs.iter().max_by(|x| x.abs()).unwrap(), -10);
-    /// ~~~
-    fn max_by<B: Ord>(&mut self, f: &fn(&A) -> B) -> Option<A>;
-
-    /// Return the element that gives the minimum value from the specfied function
-    ///
-    /// # Example
-    ///
-    /// ~~~ {.rust}
-    /// let xs = [-3, 0, 1, 5, -10];
-    /// assert_eq!(*xs.iter().min_by(|x| x.abs()).unwrap(), 0);
-    /// ~~~
-    fn min_by<B: Ord>(&mut self, f: &fn(&A) -> B) -> Option<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.
-impl<A, T: Iterator<A>> IteratorUtil<A> for T {
-    #[inline]
-    fn chain_<U: Iterator<A>>(self, other: U) -> Chain<T, U> {
-        Chain{a: self, b: other, flag: false}
-    }
-
-    #[inline]
-    fn zip<B, U: Iterator<B>>(self, other: U) -> Zip<T, U> {
-        Zip{a: self, b: other}
-    }
-
-    // FIXME: #5898: should be called map
-    #[inline]
-    fn transform<'r, B>(self, f: &'r fn(A) -> B) -> Map<'r, A, B, T> {
-        Map{iter: self, f: f}
-    }
-
-    #[inline]
-    fn filter<'r>(self, predicate: &'r fn(&A) -> bool) -> Filter<'r, A, T> {
-        Filter{iter: self, predicate: predicate}
-    }
-
-    #[inline]
-    fn filter_map<'r, B>(self, f: &'r fn(A) -> Option<B>) -> FilterMap<'r, A, B, T> {
-        FilterMap { iter: self, f: f }
-    }
-
-    #[inline]
-    fn enumerate(self) -> Enumerate<T> {
-        Enumerate{iter: self, count: 0}
-    }
-
-    #[inline]
-    fn skip_while<'r>(self, predicate: &'r fn(&A) -> bool) -> SkipWhile<'r, A, T> {
-        SkipWhile{iter: self, flag: false, predicate: predicate}
-    }
-
-    #[inline]
-    fn take_while<'r>(self, predicate: &'r fn(&A) -> bool) -> TakeWhile<'r, A, T> {
-        TakeWhile{iter: self, flag: false, predicate: predicate}
-    }
-
-    #[inline]
-    fn skip(self, n: uint) -> Skip<T> {
-        Skip{iter: self, n: n}
-    }
-
-    // FIXME: #5898: should be called take
-    #[inline]
-    fn take_(self, n: uint) -> Take<T> {
-        Take{iter: self, n: n}
-    }
-
-    #[inline]
-    fn scan<'r, St, B>(self, initial_state: St, f: &'r fn(&mut St, A) -> Option<B>)
-        -> Scan<'r, A, B, T, St> {
-        Scan{iter: self, f: f, state: initial_state}
-    }
-
-    #[inline]
-    fn flat_map_<'r, B, U: Iterator<B>>(self, f: &'r fn(A) -> U)
-        -> FlatMap<'r, A, T, U> {
-        FlatMap{iter: self, f: f, frontiter: None, backiter: None }
-    }
-
-    // FIXME: #5898: should be called `peek`
-    #[inline]
-    fn peek_<'r>(self, f: &'r fn(&A)) -> Peek<'r, A, T> {
-        Peek{iter: self, f: f}
-    }
-
-    /// A shim implementing the `for` loop iteration protocol for iterator objects
-    #[inline]
-    fn advance(&mut self, f: &fn(A) -> bool) -> bool {
-        loop {
-            match self.next() {
-                Some(x) => {
-                    if !f(x) { return false; }
-                }
-                None => { return true; }
-            }
-        }
-    }
-
-    #[inline]
-    fn collect<B: FromIterator<A, T>>(&mut self) -> B {
-        FromIterator::from_iterator(self)
-    }
-
-    #[inline]
-    fn to_owned_vec(&mut self) -> ~[A] {
-        self.collect()
-    }
-
-    /// Return the `n`th item yielded by an iterator.
-    #[inline]
-    fn nth(&mut self, mut n: uint) -> Option<A> {
-        loop {
-            match self.next() {
-                Some(x) => if n == 0 { return Some(x) },
-                None => return None
-            }
-            n -= 1;
-        }
-    }
-
-    /// Return the last item yielded by an iterator.
-    #[inline]
-    fn last_(&mut self) -> Option<A> {
-        let mut last = None;
-        for x in *self { last = Some(x); }
-        last
-    }
-
-    /// Reduce an iterator to an accumulated value
-    #[inline]
-    fn fold<B>(&mut self, init: B, f: &fn(B, A) -> B) -> B {
-        let mut accum = init;
-        loop {
-            match self.next() {
-                Some(x) => { accum = f(accum, x); }
-                None    => { break; }
-            }
-        }
-        accum
-    }
-
-    /// Count the number of items yielded by an iterator
-    #[inline]
-    fn len_(&mut self) -> uint { self.fold(0, |cnt, _x| cnt + 1) }
-
-    #[inline]
-    fn all(&mut self, f: &fn(A) -> bool) -> bool {
-        for x in *self { if !f(x) { return false; } }
-        true
-    }
-
     #[inline]
     fn any(&mut self, f: &fn(A) -> bool) -> bool {
         for x in *self { if f(x) { return true; } }
@@ -640,6 +484,7 @@ impl<A, T: Iterator<A>> IteratorUtil<A> for T {
         None
     }
 
+    /// Count the number of elements satisfying the specified predicate
     #[inline]
     fn count(&mut self, predicate: &fn(A) -> bool) -> uint {
         let mut i = 0;
@@ -649,6 +494,14 @@ impl<A, T: Iterator<A>> IteratorUtil<A> for T {
         i
     }
 
+    /// Return the element that gives the maximum value from the specfied function
+    ///
+    /// # Example
+    ///
+    /// ~~~ {.rust}
+    /// let xs = [-3, 0, 1, 5, -10];
+    /// assert_eq!(*xs.iter().max_by(|x| x.abs()).unwrap(), -10);
+    /// ~~~
     #[inline]
     fn max_by<B: Ord>(&mut self, f: &fn(&A) -> B) -> Option<A> {
         self.fold(None, |max: Option<(A, B)>, x| {
@@ -664,6 +517,14 @@ impl<A, T: Iterator<A>> IteratorUtil<A> for T {
         }).map_move(|(x, _)| x)
     }
 
+    /// Return the element that gives the minimum value from the specfied function
+    ///
+    /// # Example
+    ///
+    /// ~~~ {.rust}
+    /// let xs = [-3, 0, 1, 5, -10];
+    /// assert_eq!(*xs.iter().min_by(|x| x.abs()).unwrap(), 0);
+    /// ~~~
     #[inline]
     fn min_by<B: Ord>(&mut self, f: &fn(&A) -> B) -> Option<A> {
         self.fold(None, |min: Option<(A, B)>, x| {
@@ -680,6 +541,69 @@ impl<A, T: Iterator<A>> IteratorUtil<A> for T {
     }
 }
 
+/// A range iterator able to yield elements from both ends
+pub trait DoubleEndedIterator<A>: Iterator<A> {
+    /// Yield an element from the end of the range, returning `None` if the range is empty.
+    fn next_back(&mut self) -> Option<A>;
+
+    /// Flip the direction of the iterator
+    ///
+    /// The inverted iterator flips the ends on an iterator that can already
+    /// be iterated from the front and from the back.
+    ///
+    ///
+    /// If the iterator also implements RandomAccessIterator, the inverted
+    /// iterator is also random access, with the indices starting at the back
+    /// of the original iterator.
+    ///
+    /// Note: Random access with inverted indices still only applies to the first
+    /// `uint::max_value` elements of the original iterator.
+    #[inline]
+    fn invert(self) -> Invert<Self> {
+        Invert{iter: self}
+    }
+}
+
+/// An object implementing random access indexing by `uint`
+///
+/// A `RandomAccessIterator` should be either infinite or a `DoubleEndedIterator`.
+pub trait RandomAccessIterator<A>: Iterator<A> {
+    /// Return the number of indexable elements. At most `std::uint::max_value`
+    /// elements are indexable, even if the iterator represents a longer range.
+    fn indexable(&self) -> uint;
+
+    /// Return an element at an index
+    fn idx(&self, index: uint) -> Option<A>;
+}
+
+/// An double-ended iterator with the direction inverted
+#[deriving(Clone)]
+pub struct Invert<T> {
+    priv iter: T
+}
+
+impl<A, T: DoubleEndedIterator<A>> Iterator<A> for Invert<T> {
+    #[inline]
+    fn next(&mut self) -> Option<A> { self.iter.next_back() }
+    #[inline]
+    fn size_hint(&self) -> (uint, Option<uint>) { self.iter.size_hint() }
+}
+
+impl<A, T: DoubleEndedIterator<A>> DoubleEndedIterator<A> for Invert<T> {
+    #[inline]
+    fn next_back(&mut self) -> Option<A> { self.iter.next() }
+}
+
+impl<A, T: DoubleEndedIterator<A> + RandomAccessIterator<A>> RandomAccessIterator<A>
+    for Invert<T> {
+    #[inline]
+    fn indexable(&self) -> uint { self.iter.indexable() }
+    #[inline]
+    fn idx(&self, index: uint) -> Option<A> {
+        self.iter.idx(self.indexable() - index - 1)
+    }
+}
+
 /// A trait for iterators over elements which can be added together
 pub trait AdditiveIterator<A> {
     /// Iterates over the entire iterator, summing up all the elements
@@ -1882,7 +1806,7 @@ mod tests {
 
     #[test]
     fn test_all() {
-        let v = ~&[1, 2, 3, 4, 5];
+        let v: ~&[int] = ~&[1, 2, 3, 4, 5];
         assert!(v.iter().all(|&x| x < 10));
         assert!(!v.iter().all(|&x| x.is_even()));
         assert!(!v.iter().all(|&x| x > 100));
@@ -1891,7 +1815,7 @@ mod tests {
 
     #[test]
     fn test_any() {
-        let v = ~&[1, 2, 3, 4, 5];
+        let v: ~&[int] = ~&[1, 2, 3, 4, 5];
         assert!(v.iter().any(|&x| x < 10));
         assert!(v.iter().any(|&x| x.is_even()));
         assert!(!v.iter().any(|&x| x > 100));
@@ -1900,7 +1824,7 @@ mod tests {
 
     #[test]
     fn test_find() {
-        let v = &[1, 3, 9, 27, 103, 14, 11];
+        let v: &[int] = &[1, 3, 9, 27, 103, 14, 11];
         assert_eq!(*v.iter().find_(|x| *x & 1 == 0).unwrap(), 14);
         assert_eq!(*v.iter().find_(|x| *x % 3 == 0).unwrap(), 3);
         assert!(v.iter().find_(|x| *x % 12 == 0).is_none());
@@ -1924,13 +1848,13 @@ mod tests {
 
     #[test]
     fn test_max_by() {
-        let xs = [-3, 0, 1, 5, -10];
+        let xs: &[int] = &[-3, 0, 1, 5, -10];
         assert_eq!(*xs.iter().max_by(|x| x.abs()).unwrap(), -10);
     }
 
     #[test]
     fn test_min_by() {
-        let xs = [-3, 0, 1, 5, -10];
+        let xs: &[int] = &[-3, 0, 1, 5, -10];
         assert_eq!(*xs.iter().min_by(|x| x.abs()).unwrap(), 0);
     }