std: Implement .rposition() on double-ended iterators with known size

This is a generalization of the vector .rposition() method, to all
double-ended iterators that have the ExactSizeHint trait.

This resolves the slight asymmetry around `position` and `rposition`

* position from front is `vec.iter().position()`
* position from the back was, `vec.rposition()` is now `vec.iter().rposition()`

Additionally, other indexed sequences (only `extra::ringbuf` I think),
will have the same method available once it implements ExactSizeHint.

1 files changed, 32 insertions, 1 deletions

diff --git a/src/libstd/iterator.rs b/src/libstd/iterator.rs
index e2ac9f03395..d1b59c30978 100644
--- a/src/libstd/iterator.rs
+++ b/src/libstd/iterator.rs
@@ -18,7 +18,7 @@ implementing the `Iterator` trait.
 */
 
 use cmp;
-use num::{Zero, One, Integer, CheckedAdd, Saturating};
+use num::{Zero, One, Integer, CheckedAdd, CheckedSub, Saturating};
 use option::{Option, Some, None};
 use ops::{Add, Mul, Sub};
 use cmp::Ord;
@@ -604,6 +604,37 @@ impl<'self, A, T: DoubleEndedIterator<&'self mut A>> MutableDoubleEndedIterator
     }
 }
 
+/// A double-ended iterator with known size
+pub trait ExactSizeDoubleEndedIterator<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;
+        loop {
+            match self.next_back() {
+                None => break,
+                Some(x) => {
+                    i = match i.checked_sub(&1) {
+                        Some(x) => x,
+                        None => fail!("rposition: incorrect ExactSizeHint")
+                    };
+                    if predicate(x) {
+                        return Some(i)
+                    }
+                }
+            }
+        }
+        None
+    }
+}
+
 /// An object implementing random access indexing by `uint`
 ///
 /// A `RandomAccessIterator` should be either infinite or a `DoubleEndedIterator`.