auto merge of #19858 : nick29581/rust/ranges, r=aturon

Closes #19794

r? @aturon for the first patch
r? @nikomatsakis for the rest

3 files changed, 135 insertions, 1 deletions

diff --git a/src/libcore/iter.rs b/src/libcore/iter.rs
index 1cd4d7b89d6..9c3e53a1ace 100644
--- a/src/libcore/iter.rs
+++ b/src/libcore/iter.rs
@@ -2542,6 +2542,64 @@ impl<A: Int> Iterator<A> for RangeStepInclusive<A> {
     }
 }
 
+
+/// The `Step` trait identifies objects which can be stepped over in both
+/// directions. The `steps_between` function provides a way to
+/// compare two Step objects (it could be provided using `step()` and `Ord`,
+/// but the implementation would be so inefficient as to be useless).
+#[unstable = "Trait is unstable."]
+pub trait Step: Ord {
+    /// Change self to the next object.
+    fn step(&mut self);
+    /// Change self to the previous object.
+    fn step_back(&mut self);
+    /// The steps_between two step objects.
+    /// a should always be less than b, so the result should never be negative.
+    /// Return None if it is not possible to calculate steps_between without
+    /// overflow.
+    fn steps_between(a: &Self, b: &Self) -> Option<uint>;
+}
+
+macro_rules! step_impl {
+    ($($t:ty)*) => ($(
+        #[unstable = "Trait is unstable."]
+        impl Step for $t {
+            #[inline]
+            fn step(&mut self) { *self += 1; }
+            #[inline]
+            fn step_back(&mut self) { *self -= 1; }
+            #[inline]
+            fn steps_between(a: &$t, b: &$t) -> Option<uint> {
+                debug_assert!(a < b);
+                Some((*a - *b) as uint)
+            }
+        }
+    )*)
+}
+
+macro_rules! step_impl_no_between {
+    ($($t:ty)*) => ($(
+        #[unstable = "Trait is unstable."]
+        impl Step for $t {
+            #[inline]
+            fn step(&mut self) { *self += 1; }
+            #[inline]
+            fn step_back(&mut self) { *self -= 1; }
+            #[inline]
+            fn steps_between(_a: &$t, _b: &$t) -> Option<uint> {
+                None
+            }
+        }
+    )*)
+}
+
+step_impl!(uint u8 u16 u32 int i8 i16 i32);
+#[cfg(target_word_size = "64")]
+step_impl!(u64 i64);
+#[cfg(target_word_size = "32")]
+step_impl_no_between!(u64 i64);
+
+
 /// An iterator that repeats an element endlessly
 #[deriving(Clone)]
 #[stable]
diff --git a/src/libcore/lib.rs b/src/libcore/lib.rs
index 9b6622a7127..9de723f38ee 100644
--- a/src/libcore/lib.rs
+++ b/src/libcore/lib.rs
@@ -59,7 +59,7 @@
 #![allow(unknown_features, raw_pointer_deriving)]
 #![feature(globs, intrinsics, lang_items, macro_rules, phase)]
 #![feature(simd, unsafe_destructor, slicing_syntax)]
-#![feature(default_type_params, unboxed_closures)]
+#![feature(default_type_params, unboxed_closures, associated_types)]
 #![deny(missing_docs)]
 
 mod macros;
diff --git a/src/libcore/ops.rs b/src/libcore/ops.rs
index e752fd11ee5..0cd8c1d69d1 100644
--- a/src/libcore/ops.rs
+++ b/src/libcore/ops.rs
@@ -51,7 +51,10 @@
 //! See the documentation for each trait for a minimum implementation that prints
 //! something to the screen.
 
+use clone::Clone;
+use iter::{Step, Iterator,DoubleEndedIterator,ExactSizeIterator};
 use kinds::Sized;
+use option::Option::{mod, Some, None};
 
 /// The `Drop` trait is used to run some code when a value goes out of scope. This
 /// is sometimes called a 'destructor'.
@@ -833,6 +836,79 @@ pub trait SliceMut<Sized? Idx, Sized? Result> for Sized? {
     fn slice_or_fail_mut<'a>(&'a mut self, from: &Idx, to: &Idx) -> &'a mut Result;
 }
 
+
+/// An unbounded range.
+#[deriving(Copy)]
+#[lang="full_range"]
+pub struct FullRange;
+
+/// A (half-open) range which is bounded at both ends.
+#[deriving(Copy)]
+#[lang="range"]
+pub struct Range<Idx> {
+    /// The lower bound of the range (inclusive).
+    pub start: Idx,
+    /// The upper bound of the range (exclusive).
+    pub end: Idx,
+}
+
+// FIXME(#19391) needs a snapshot
+//impl<Idx: Clone + Step<T=uint>> Iterator<Idx> for Range<Idx> {
+impl<Idx: Clone + Step> Iterator<Idx> for Range<Idx> {
+    #[inline]
+    fn next(&mut self) -> Option<Idx> {
+        if self.start < self.end {
+            let result = self.start.clone();
+            self.start.step();
+            return Some(result);
+        }
+
+        return None;
+    }
+
+    #[inline]
+    fn size_hint(&self) -> (uint, Option<uint>) {
+        if let Some(hint) = Step::steps_between(&self.end, &self.start) {
+            (hint, Some(hint))
+        } else {
+            (0, None)
+        }
+    }
+}
+
+impl<Idx: Clone + Step> DoubleEndedIterator<Idx> for Range<Idx> {
+    #[inline]
+    fn next_back(&mut self) -> Option<Idx> {
+        if self.start < self.end {
+            self.end.step_back();
+            return Some(self.end.clone());
+        }
+
+        return None;
+    }
+}
+
+impl<Idx: Clone + Step> ExactSizeIterator<Idx> for Range<Idx> {}
+
+/// A range which is only bounded below.
+#[deriving(Copy)]
+#[lang="range_from"]
+pub struct RangeFrom<Idx> {
+    /// The lower bound of the range (inclusive).
+    pub start: Idx,
+}
+
+impl<Idx: Clone + Step> Iterator<Idx> for RangeFrom<Idx> {
+    #[inline]
+    fn next(&mut self) -> Option<Idx> {
+        // Deliberately overflow so we loop forever.
+        let result = self.start.clone();
+        self.start.step();
+        return Some(result);
+    }
+}
+
+
 /// The `Deref` trait is used to specify the functionality of dereferencing
 /// operations like `*v`.
 ///