auto merge of #8385 : cmr/rust/big-rollup, r=alexcrichton

This is a fairly large rollup, but I've tested everything locally, and none of
it should be platform-specific.

r=alexcrichton (bdfdbdd)
r=brson (d803c18)
r=alexcrichton (a5041d0)
r=bstrie (317412a)
r=alexcrichton (135c85e)
r=thestinger (8805baa)
r=pcwalton (0661178)
r=cmr (9397fe0)
r=cmr (caa4135)
r=cmr (6a21d93)
r=cmr (4dc3379)
r=cmr (0aa5154)
r=cmr (18be261)
r=thestinger (f10be03)

1 files changed, 32 insertions, 3 deletions

diff --git a/src/libstd/iterator.rs b/src/libstd/iterator.rs
index 29f54bd10fb..d10a5541e41 100644
--- a/src/libstd/iterator.rs
+++ b/src/libstd/iterator.rs
@@ -18,9 +18,9 @@ implementing the `Iterator` trait.
 */
 
 use cmp;
-use num::{Zero, One, Saturating};
+use num::{Zero, One, Integer, Saturating};
 use option::{Option, Some, None};
-use ops::{Add, Mul};
+use ops::{Add, Mul, Sub};
 use cmp::Ord;
 use clone::Clone;
 use uint;
@@ -1531,7 +1531,7 @@ pub fn range<A: Add<A, A> + Ord + Clone + One>(start: A, stop: A) -> Range<A> {
     Range{state: start, stop: stop, one: One::one()}
 }
 
-impl<A: Add<A, A> + Ord + Clone + One> Iterator<A> for Range<A> {
+impl<A: Add<A, A> + Ord + Clone> Iterator<A> for Range<A> {
     #[inline]
     fn next(&mut self) -> Option<A> {
         if self.state < self.stop {
@@ -1544,6 +1544,22 @@ impl<A: Add<A, A> + Ord + Clone + One> Iterator<A> for Range<A> {
     }
 }
 
+impl<A: Sub<A, A> + Integer + Ord + Clone> DoubleEndedIterator<A> for Range<A> {
+    #[inline]
+    fn next_back(&mut self) -> Option<A> {
+        if self.stop > self.state {
+            // Integer doesn't technically define this rule, but we're going to assume that every
+            // Integer is reachable from every other one by adding or subtracting enough Ones. This
+            // seems like a reasonable-enough rule that every Integer should conform to, even if it
+            // can't be statically checked.
+            self.stop = self.stop - self.one;
+            Some(self.stop.clone())
+        } else {
+            None
+        }
+    }
+}
+
 impl<A: Add<A, A> + Clone> Iterator<A> for Counter<A> {
     #[inline]
     fn next(&mut self) -> Option<A> {
@@ -2121,4 +2137,17 @@ mod tests {
         check_randacc_iter(xs.iter().cycle().take_(27), 27);
         check_randacc_iter(empty.iter().cycle(), 0);
     }
+
+    #[test]
+    fn test_double_ended_range() {
+        assert_eq!(range(11i, 14).invert().collect::<~[int]>(), ~[13i, 12, 11]);
+        for _ in range(10i, 0).invert() {
+            fail!("unreachable");
+        }
+
+        assert_eq!(range(11u, 14).invert().collect::<~[uint]>(), ~[13u, 12, 11]);
+        for _ in range(10u, 0).invert() {
+            fail!("unreachable");
+        }
+    }
 }