std::iterator: Use ExactSize, inheriting DoubleEndedIterator

Address discussion with acrichto; inherit DoubleEndedIterator so that
`.rposition()` can be a default method, and that the nische of the trait
is clear. Use assertions when using `.size_hint()` in reverse enumerate
and `.rposition()`

4 files changed, 43 insertions, 52 deletions

diff --git a/src/libstd/iterator.rs b/src/libstd/iterator.rs
index 77e51e01c0c..83e07dc1379 100644
--- a/src/libstd/iterator.rs
+++ b/src/libstd/iterator.rs
@@ -604,26 +604,42 @@ impl<'self, A, T: DoubleEndedIterator<&'self mut A>> MutableDoubleEndedIterator
     }
 }
 
-/// A double-ended iterator with known size
-pub trait ExactSizeDoubleEndedIterator<A> {
+
+/// 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 iterator that knows its exact length
+///
+/// This trait is a helper for iterators like the vector iterator, so that
+/// it can support double-ended enumeration.
+///
+/// `Iterator::size_hint` *must* return the exact size of the iterator.
+/// Note that the size must fit in `uint`.
+pub trait ExactSize<A> : DoubleEndedIterator<A> {
     /// Return the index of the last element satisfying the specified predicate
     ///
     /// If no element matches, None is returned.
     #[inline]
-    fn rposition(&mut self, predicate: &fn(A) -> bool) -> Option<uint>;
-}
-
-impl<A, T: DoubleEndedIterator<A> + ExactSizeHint> ExactSizeDoubleEndedIterator<A> for T {
     fn rposition(&mut self, predicate: &fn(A) -> bool) -> Option<uint> {
-        let (size, _) = self.size_hint();
-        let mut i = size;
+        let (lower, upper) = self.size_hint();
+        assert!(upper == Some(lower));
+        let mut i = lower;
         loop {
             match self.next_back() {
                 None => break,
                 Some(x) => {
                     i = match i.checked_sub(&1) {
                         Some(x) => x,
-                        None => fail!("rposition: incorrect ExactSizeHint")
+                        None => fail!("rposition: incorrect ExactSize")
                     };
                     if predicate(x) {
                         return Some(i)
@@ -635,37 +651,13 @@ impl<A, T: DoubleEndedIterator<A> + ExactSizeHint> ExactSizeDoubleEndedIterator<
     }
 }
 
-/// 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 iterator that knows its exact length
-///
-/// This trait is a helper for iterators like the vector iterator, so that
-/// it can support double-ended enumeration.
-///
-/// `Iterator::size_hint` *must* return the exact size of the iterator.
-/// Note that the size must fit in `uint`.
-pub trait ExactSizeHint {}
-
 // All adaptors that preserve the size of the wrapped iterator are fine
 // Adaptors that may overflow in `size_hint` are not, i.e. `Chain`.
-impl<T: ExactSizeHint> ExactSizeHint for Enumerate<T> {}
-impl<'self, A, T: ExactSizeHint> ExactSizeHint for Inspect<'self, A, T> {}
-impl<T: ExactSizeHint> ExactSizeHint for Invert<T> {}
-impl<'self, A, B, T: ExactSizeHint> ExactSizeHint for Map<'self, A, B, T> {}
-impl<A, T: ExactSizeHint> ExactSizeHint for Peekable<A, T> {}
-impl<T: ExactSizeHint> ExactSizeHint for Skip<T> {}
-impl<T: ExactSizeHint> ExactSizeHint for Take<T> {}
-impl<T: ExactSizeHint, U: ExactSizeHint> ExactSizeHint for Zip<T, U> {}
+impl<A, T: ExactSize<A>> ExactSize<(uint, A)> for Enumerate<T> {}
+impl<'self, A, T: ExactSize<A>> ExactSize<A> for Inspect<'self, A, T> {}
+impl<A, T: ExactSize<A>> ExactSize<A> for Invert<T> {}
+impl<'self, A, B, T: ExactSize<A>> ExactSize<B> for Map<'self, A, B, T> {}
+impl<A, B, T: ExactSize<A>, U: ExactSize<B>> ExactSize<(A, B)> for Zip<T, U> {}
 
 /// An double-ended iterator with the direction inverted
 #[deriving(Clone)]
@@ -967,14 +959,14 @@ impl<A, B, T: Iterator<A>, U: Iterator<B>> Iterator<(A, B)> for Zip<T, U> {
     }
 }
 
-impl<A, B,
-     T: DoubleEndedIterator<A> + ExactSizeHint,
-     U: DoubleEndedIterator<B> + ExactSizeHint> DoubleEndedIterator<(A, B)>
+impl<A, B, T: ExactSize<A>, U: ExactSize<B>> DoubleEndedIterator<(A, B)>
 for Zip<T, U> {
     #[inline]
     fn next_back(&mut self) -> Option<(A, B)> {
-        let (a_sz, _) = self.a.size_hint();
-        let (b_sz, _) = self.b.size_hint();
+        let (a_sz, a_upper) = self.a.size_hint();
+        let (b_sz, b_upper) = self.b.size_hint();
+        assert!(a_upper == Some(a_sz));
+        assert!(b_upper == Some(b_sz));
         if a_sz < b_sz {
             for _ in range(0, b_sz - a_sz) { self.b.next_back(); }
         } else if a_sz > b_sz {
@@ -1168,15 +1160,14 @@ impl<A, T: Iterator<A>> Iterator<(uint, A)> for Enumerate<T> {
     }
 }
 
-impl<A, T: DoubleEndedIterator<A> + ExactSizeHint> DoubleEndedIterator<(uint, A)>
-for Enumerate<T> {
+impl<A, T: ExactSize<A>> DoubleEndedIterator<(uint, A)> for Enumerate<T> {
     #[inline]
     fn next_back(&mut self) -> Option<(uint, A)> {
         match self.iter.next_back() {
             Some(a) => {
-                let (len, _) = self.iter.size_hint();
-                let ret = Some((self.count + len, a));
-                ret
+                let (lower, upper) = self.iter.size_hint();
+                assert!(upper == Some(lower));
+                Some((self.count + lower, a))
             }
             _ => None
         }
diff --git a/src/libstd/prelude.rs b/src/libstd/prelude.rs
index e8eb6d871ee..8f202ee8531 100644
--- a/src/libstd/prelude.rs
+++ b/src/libstd/prelude.rs
@@ -52,7 +52,7 @@ pub use hash::Hash;
 pub use num::Times;
 pub use iterator::{FromIterator, Extendable};
 pub use iterator::{Iterator, DoubleEndedIterator, RandomAccessIterator, ClonableIterator};
-pub use iterator::{OrdIterator, MutableDoubleEndedIterator, ExactSizeDoubleEndedIterator};
+pub use iterator::{OrdIterator, MutableDoubleEndedIterator, ExactSize};
 pub use num::{Num, NumCast, CheckedAdd, CheckedSub, CheckedMul};
 pub use num::{Orderable, Signed, Unsigned, Round};
 pub use num::{Algebraic, Trigonometric, Exponential, Hyperbolic};
diff --git a/src/libstd/str.rs b/src/libstd/str.rs
index 0360d4ac72f..d1afbaf5699 100644
--- a/src/libstd/str.rs
+++ b/src/libstd/str.rs
@@ -24,7 +24,7 @@ use container::{Container, Mutable};
 use num::Times;
 use iterator::{Iterator, FromIterator, Extendable};
 use iterator::{Filter, AdditiveIterator, Map};
-use iterator::{Invert, DoubleEndedIterator, ExactSizeDoubleEndedIterator};
+use iterator::{Invert, DoubleEndedIterator, ExactSize};
 use libc;
 use num::{Saturating};
 use option::{None, Option, Some};
diff --git a/src/libstd/vec.rs b/src/libstd/vec.rs
index f8aaf653645..769f2651bac 100644
--- a/src/libstd/vec.rs
+++ b/src/libstd/vec.rs
@@ -2303,8 +2303,8 @@ iterator!{impl VecIterator -> &'self T}
 double_ended_iterator!{impl VecIterator -> &'self T}
 pub type RevIterator<'self, T> = Invert<VecIterator<'self, T>>;
 
-impl<'self, T> ExactSizeHint for VecIterator<'self, T> {}
-impl<'self, T> ExactSizeHint for VecMutIterator<'self, T> {}
+impl<'self, T> ExactSize<&'self T> for VecIterator<'self, T> {}
+impl<'self, T> ExactSize<&'self mut T> for VecMutIterator<'self, T> {}
 
 impl<'self, T> Clone for VecIterator<'self, T> {
     fn clone(&self) -> VecIterator<'self, T> { *self }