1 files changed, 110 insertions, 0 deletions
diff --git a/src/libstd/iterator.rs b/src/libstd/iterator.rs
index 4af7b3e2425..841b6134410 100644
--- a/src/libstd/iterator.rs
+++ b/src/libstd/iterator.rs
@@ -41,6 +41,13 @@ pub trait Extendable<A>: FromIterator<A> {
 /// An interface for dealing with "external iterators". These types of iterators
 /// can be resumed at any time as all state is stored internally as opposed to
 /// being located on the call stack.
+///
+/// The Iterator protocol states that an iterator yields a (potentially-empty,
+/// potentially-infinite) sequence of values, and returns `None` to signal that
+/// it's finished. The Iterator protocol does not define behavior after `None`
+/// is returned. A concrete Iterator implementation may choose to behave however
+/// it wishes, either by returning `None` infinitely, or by doing something
+/// else.
 pub trait Iterator<A> {
     /// Advance the iterator and return the next value. Return `None` when the end is reached.
     fn next(&mut self) -> Option<A>;
@@ -300,6 +307,36 @@ pub trait Iterator<A> {
         FlatMap{iter: self, f: f, frontiter: None, backiter: None }
     }
 
+    /// Creates an iterator that yields `None` forever after the underlying
+    /// iterator yields `None`. Random-access iterator behavior is not
+    /// affected, only single and double-ended iterator behavior.
+    ///
+    /// # Example
+    ///
+    /// ~~~ {.rust}
+    /// fn process<U: Iterator<int>>(it: U) -> int {
+    ///     let mut it = it.fuse();
+    ///     let mut sum = 0;
+    ///     for x in it {
+    ///         if x > 5 {
+    ///             break;
+    ///         }
+    ///         sum += x;
+    ///     }
+    ///     // did we exhaust the iterator?
+    ///     if it.next().is_none() {
+    ///         sum += 1000;
+    ///     }
+    ///     sum
+    /// }
+    /// let x = ~[1,2,3,7,8,9];
+    /// assert_eq!(process(x.move_iter()), 1006);
+    /// ~~~
+    #[inline]
+    fn fuse(self) -> Fuse<Self> {
+        Fuse{iter: self, done: false}
+    }
+
     /// Creates an iterator that calls a function with a reference to each
     /// element before yielding it. This is often useful for debugging an
     /// iterator pipeline.
@@ -1421,6 +1458,79 @@ impl<'self,
     }
 }
 
+/// An iterator that yields `None` forever after the underlying iterator
+/// yields `None` once.
+#[deriving(Clone, DeepClone)]
+pub struct Fuse<T> {
+    priv iter: T,
+    priv done: bool
+}
+
+impl<A, T: Iterator<A>> Iterator<A> for Fuse<T> {
+    #[inline]
+    fn next(&mut self) -> Option<A> {
+        if self.done {
+            None
+        } else {
+            match self.iter.next() {
+                None => {
+                    self.done = true;
+                    None
+                }
+                x => x
+            }
+        }
+    }
+
+    #[inline]
+    fn size_hint(&self) -> (uint, Option<uint>) {
+        if self.done {
+            (0, Some(0))
+        } else {
+            self.iter.size_hint()
+        }
+    }
+}
+
+impl<A, T: DoubleEndedIterator<A>> DoubleEndedIterator<A> for Fuse<T> {
+    #[inline]
+    fn next_back(&mut self) -> Option<A> {
+        if self.done {
+            None
+        } else {
+            match self.iter.next_back() {
+                None => {
+                    self.done = true;
+                    None
+                }
+                x => x
+            }
+        }
+    }
+}
+
+// Allow RandomAccessIterators to be fused without affecting random-access behavior
+impl<A, T: RandomAccessIterator<A>> RandomAccessIterator<A> for Fuse<T> {
+    #[inline]
+    fn indexable(&self) -> uint {
+        self.iter.indexable()
+    }
+
+    #[inline]
+    fn idx(&self, index: uint) -> Option<A> {
+        self.iter.idx(index)
+    }
+}
+
+impl<T> Fuse<T> {
+    /// Resets the fuse such that the next call to .next() or .next_back() will
+    /// call the underlying iterator again even if it prevously returned None.
+    #[inline]
+    fn reset_fuse(&mut self) {
+        self.done = false
+    }
+}
+
 /// An iterator that calls a function with a reference to each
 /// element before yielding it.
 pub struct Inspect<'self, A, T> {