auto merge of #8884 : blake2-ppc/rust/exact-size-hint, r=huonw

The message of the first commit explains (edited for changed trait name):

The trait `ExactSize` is introduced to solve a few small niggles:

* We can't reverse (`.invert()`) an enumeration iterator
* for a vector, we have `v.iter().position(f)` but `v.rposition(f)`.
* We can't reverse `Zip` even if both iterators are from vectors

`ExactSize` is an empty trait that is intended to indicate that an
iterator, for example `VecIterator`, knows its exact finite size and
reports it correctly using `.size_hint()`. Only adaptors that preserve
this at all times, can expose this trait further. (Where here we say
finite for fitting in uint).

---

It may seem complicated just to solve these small "niggles",
(It's really the reversible enumerate case that's the most interesting)
but only a few core iterators need to implement this trait.

While we gain more capabilities generically for some iterators,
it becomes a tad more complicated to figure out if a type has
the right trait impls for it.

1 files changed, 5 insertions, 42 deletions

diff --git a/src/libstd/vec.rs b/src/libstd/vec.rs
index 22c64c6b39c..f607d1612ad 100644
--- a/src/libstd/vec.rs
+++ b/src/libstd/vec.rs
@@ -274,7 +274,7 @@ impl<'self, T> Iterator<&'self [T]> for RSplitIterator<'self, T> {
             return Some(self.v);
         }
 
-        match self.v.rposition(|x| (self.pred)(x)) {
+        match self.v.iter().rposition(|x| (self.pred)(x)) {
             None => {
                 self.finished = true;
                 Some(self.v)
@@ -832,7 +832,6 @@ pub trait ImmutableVector<'self, T> {
     fn initn(&self, n: uint) -> &'self [T];
     fn last(&self) -> &'self T;
     fn last_opt(&self) -> Option<&'self T>;
-    fn rposition(&self, f: &fn(t: &T) -> bool) -> Option<uint>;
     fn flat_map<U>(&self, f: &fn(t: &T) -> ~[U]) -> ~[U];
     unsafe fn unsafe_ref(&self, index: uint) -> *T;
 
@@ -1049,21 +1048,6 @@ impl<'self,T> ImmutableVector<'self, T> for &'self [T] {
     }
 
     /**
-     * Find the last index matching some predicate
-     *
-     * Apply function `f` to each element of `v` in reverse order.  When
-     * function `f` returns true then an option containing the index is
-     * returned. If `f` matches no elements then None is returned.
-     */
-    #[inline]
-    fn rposition(&self, f: &fn(t: &T) -> bool) -> Option<uint> {
-        for (i, t) in self.rev_iter().enumerate() {
-            if f(t) { return Some(self.len() - i - 1); }
-        }
-        None
-    }
-
-    /**
      * Apply a function to each element of a vector and return a concatenation
      * of each result vector
      */
@@ -1145,7 +1129,7 @@ impl<'self,T:Eq> ImmutableEqVector<T> for &'self [T] {
     /// Find the last index containing a matching value
     #[inline]
     fn rposition_elem(&self, t: &T) -> Option<uint> {
-        self.rposition(|x| *x == *t)
+        self.iter().rposition(|x| *x == *t)
     }
 
     /// Return true if a vector contains an element with the given value
@@ -2319,6 +2303,9 @@ iterator!{impl VecIterator -> &'self T}
 double_ended_iterator!{impl VecIterator -> &'self T}
 pub type RevIterator<'self, T> = Invert<VecIterator<'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 }
 }
@@ -2924,16 +2911,6 @@ mod tests {
     }
 
     #[test]
-    fn test_rposition() {
-        fn f(xy: &(int, char)) -> bool { let (_x, y) = *xy; y == 'b' }
-        fn g(xy: &(int, char)) -> bool { let (_x, y) = *xy; y == 'd' }
-        let v = ~[(0, 'a'), (1, 'b'), (2, 'c'), (3, 'b')];
-
-        assert_eq!(v.rposition(f), Some(3u));
-        assert!(v.rposition(g).is_none());
-    }
-
-    #[test]
     fn test_bsearch_elem() {
         assert_eq!([1,2,3,4,5].bsearch_elem(&5), Some(4));
         assert_eq!([1,2,3,4,5].bsearch_elem(&4), Some(3));
@@ -3214,20 +3191,6 @@ mod tests {
 
     #[test]
     #[should_fail]
-    fn test_rposition_fail() {
-        let v = [(~0, @0), (~0, @0), (~0, @0), (~0, @0)];
-        let mut i = 0;
-        do v.rposition |_elt| {
-            if i == 2 {
-                fail!()
-            }
-            i += 1;
-            false
-        };
-    }
-
-    #[test]
-    #[should_fail]
     fn test_permute_fail() {
         let v = [(~0, @0), (~0, @0), (~0, @0), (~0, @0)];
         let mut i = 0;