Implement DoubleEndedIterator on Range

Range is now invertable as long as its element type conforms to Integer.

Remove int::range_rev() et al in favor of range().invert().

5 files changed, 48 insertions, 54 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");
+        }
+    }
 }
diff --git a/src/libstd/num/int_macros.rs b/src/libstd/num/int_macros.rs
index 9842a570d7e..b692bedebfd 100644
--- a/src/libstd/num/int_macros.rs
+++ b/src/libstd/num/int_macros.rs
@@ -124,14 +124,6 @@ pub fn range_step_inclusive(start: $T, last: $T, step: $T, it: &fn($T) -> bool)
     range_step_core(start, last, step, Closed, it)
 }
 
-
-#[inline]
-/// Iterate over the range (`hi`..`lo`]
-pub fn range_rev(hi: $T, lo: $T, it: &fn($T) -> bool) -> bool {
-    if hi == min_value { return true; }
-    range_step_inclusive(hi-1, lo, -1 as $T, it)
-}
-
 impl Num for $T {}
 
 #[cfg(not(test))]
@@ -889,10 +881,6 @@ mod tests {
     fn test_ranges() {
         let mut l = ~[];
 
-        do range_rev(14,11) |i| {
-            l.push(i);
-            true
-        };
         do range_step(20,26,2) |i| {
             l.push(i);
             true
@@ -917,8 +905,7 @@ mod tests {
             l.push(i);
             true
         };
-        assert_eq!(l, ~[13,12,11,
-                        20,22,24,
+        assert_eq!(l, ~[20,22,24,
                         36,34,32,
                         max_value-2,
                         max_value-3,max_value-1,
@@ -926,9 +913,6 @@ mod tests {
                         min_value+3,min_value+1]);
 
         // None of the `fail`s should execute.
-        do range_rev(0,10) |_i| {
-            fail!(~"unreachable");
-        };
         do range_step(10,0,1) |_i| {
             fail!(~"unreachable");
         };
diff --git a/src/libstd/num/uint_macros.rs b/src/libstd/num/uint_macros.rs
index a2874c96703..29b8f29d87d 100644
--- a/src/libstd/num/uint_macros.rs
+++ b/src/libstd/num/uint_macros.rs
@@ -125,13 +125,6 @@ pub fn range_step_inclusive(start: $T, last: $T, step: $T_SIGNED, it: &fn($T) ->
     range_step_core(start, last, step, Closed, it)
 }
 
-#[inline]
-/// Iterate over the range (`hi`..`lo`]
-pub fn range_rev(hi: $T, lo: $T, it: &fn($T) -> bool) -> bool {
-    if hi == min_value { return true; }
-    range_step_inclusive(hi-1, lo, -1 as $T_SIGNED, it)
-}
-
 impl Num for $T {}
 
 #[cfg(not(test))]
@@ -654,10 +647,6 @@ mod tests {
     pub fn test_ranges() {
         let mut l = ~[];
 
-        do range_rev(14,11) |i| {
-            l.push(i);
-            true
-        };
         do range_step(20,26,2) |i| {
             l.push(i);
             true
@@ -683,8 +672,7 @@ mod tests {
             true
         };
 
-        assert_eq!(l, ~[13,12,11,
-                        20,22,24,
+        assert_eq!(l, ~[20,22,24,
                         36,34,32,
                         max_value-2,
                         max_value-3,max_value-1,
@@ -692,9 +680,6 @@ mod tests {
                         min_value+3,min_value+1]);
 
         // None of the `fail`s should execute.
-        do range_rev(0,0) |_i| {
-            fail!("unreachable");
-        };
         do range_step(10,0,1) |_i| {
             fail!("unreachable");
         };
diff --git a/src/libstd/run.rs b/src/libstd/run.rs
index ef3d881c5fe..694aa672af7 100644
--- a/src/libstd/run.rs
+++ b/src/libstd/run.rs
@@ -632,7 +632,6 @@ fn spawn_process_os(prog: &str, args: &[~str],
 
     use libc::funcs::posix88::unistd::{fork, dup2, close, chdir, execvp};
     use libc::funcs::bsd44::getdtablesize;
-    use int;
 
     mod rustrt {
         use libc::c_void;
@@ -665,10 +664,9 @@ fn spawn_process_os(prog: &str, args: &[~str],
             fail!("failure in dup3(err_fd, 2): %s", os::last_os_error());
         }
         // close all other fds
-        do int::range_rev(getdtablesize() as int, 3) |fd| {
+        for fd in range(3, getdtablesize()).invert() {
             close(fd as c_int);
-            true
-        };
+        }
 
         do with_dirp(dir) |dirp| {
             if !dirp.is_null() && chdir(dirp) == -1 {
diff --git a/src/libstd/trie.rs b/src/libstd/trie.rs
index a5efae542a1..5ef5526e516 100644
--- a/src/libstd/trie.rs
+++ b/src/libstd/trie.rs
@@ -282,13 +282,14 @@ impl<T> TrieNode<T> {
     }
 
     fn each_reverse<'a>(&'a self, f: &fn(&uint, &'a T) -> bool) -> bool {
-        do uint::range_rev(self.children.len(), 0) |idx| {
-            match self.children[idx] {
-                Internal(ref x) => x.each_reverse(|i,t| f(i,t)),
-                External(k, ref v) => f(&k, v),
-                Nothing => true
+        for elt in self.children.rev_iter() {
+            match *elt {
+                Internal(ref x) => if !x.each_reverse(|i,t| f(i,t)) { return false },
+                External(k, ref v) => if !f(&k, v) { return false },
+                Nothing => ()
             }
         }
+        true
     }
 
     fn mutate_values<'a>(&'a mut self, f: &fn(&uint, &mut T) -> bool) -> bool {
@@ -539,10 +540,9 @@ mod test_map {
     fn test_each_break() {
         let mut m = TrieMap::new();
 
-        do uint::range_rev(uint::max_value, uint::max_value - 10000) |x| {
+        for x in range(uint::max_value - 10000, uint::max_value).invert() {
             m.insert(x, x / 2);
-            true
-        };
+        }
 
         let mut n = uint::max_value - 10000;
         do m.each |k, v| {
@@ -580,10 +580,9 @@ mod test_map {
     fn test_each_reverse_break() {
         let mut m = TrieMap::new();
 
-        do uint::range_rev(uint::max_value, uint::max_value - 10000) |x| {
+        for x in range(uint::max_value - 10000, uint::max_value).invert() {
             m.insert(x, x / 2);
-            true
-        };
+        }
 
         let mut n = uint::max_value - 1;
         do m.each_reverse |k, v| {
@@ -634,10 +633,9 @@ mod test_map {
         let last = uint::max_value;
 
         let mut map = TrieMap::new();
-        do uint::range_rev(last, first) |x| {
+        for x in range(first, last).invert() {
             map.insert(x, x / 2);
-            true
-        };
+        }
 
         let mut i = 0;
         for (k, &v) in map.iter() {