iterator: add a size_hint default method

also adds an implementation for the vector iterators

1 files changed, 49 insertions, 0 deletions

diff --git a/src/libstd/iterator.rs b/src/libstd/iterator.rs
index 394066f1d4c..fa27f4560c1 100644
--- a/src/libstd/iterator.rs
+++ b/src/libstd/iterator.rs
@@ -17,6 +17,8 @@ implementing the `Iterator` trait.
 
 */
 
+#[allow(default_methods)]; // solid enough for the use case here
+
 use cmp;
 use iter::{FromIter, Times};
 use num::{Zero, One};
@@ -31,6 +33,12 @@ use clone::Clone;
 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>;
+
+    /// Return a lower bound and upper bound on the remaining length of the iterator.
+    ///
+    /// The common use case for the estimate is pre-allocating space to store the results.
+    #[cfg(not(stage0))]
+    fn size_hint(&self) -> (Option<uint>, Option<uint>) { (None, None) }
 }
 
 /// Iterator adaptors provided for every `Iterator` implementation. The adaptor objects are also
@@ -594,6 +602,27 @@ impl<A, T: Iterator<A>, U: Iterator<A>> Iterator<A> for ChainIterator<A, T, U> {
             self.b.next()
         }
     }
+
+    #[inline]
+    #[cfg(not(stage0))]
+    fn size_hint(&self) -> (Option<uint>, Option<uint>) {
+        let (a_lower, a_upper) = self.a.size_hint();
+        let (b_lower, b_upper) = self.b.size_hint();
+
+        let lower = match (a_lower, b_lower) {
+            (Some(x), Some(y)) => Some(x + y),
+            (Some(x), None) => Some(x),
+            (None, Some(y)) => Some(y),
+            (None, None) => None
+        };
+
+        let upper = match (a_upper, b_upper) {
+            (Some(x), Some(y)) => Some(x + y),
+            _ => None
+        };
+
+        (lower, upper)
+    }
 }
 
 /// An iterator which iterates two other iterators simultaneously
@@ -627,6 +656,12 @@ impl<'self, A, B, T: Iterator<A>> Iterator<B> for MapIterator<'self, A, B, T> {
             _ => None
         }
     }
+
+    #[inline]
+    #[cfg(not(stage0))]
+    fn size_hint(&self) -> (Option<uint>, Option<uint>) {
+        self.iter.size_hint()
+    }
 }
 
 /// An iterator which filters the elements of `iter` with `predicate`
@@ -647,6 +682,13 @@ impl<'self, A, T: Iterator<A>> Iterator<A> for FilterIterator<'self, A, T> {
         }
         None
     }
+
+    #[inline]
+    #[cfg(not(stage0))]
+    fn size_hint(&self) -> (Option<uint>, Option<uint>) {
+        let (_, upper) = self.iter.size_hint();
+        (None, upper) // can't know a lower bound, due to the predicate
+    }
 }
 
 /// An iterator which uses `f` to both filter and map elements from `iter`
@@ -666,6 +708,13 @@ impl<'self, A, B, T: Iterator<A>> Iterator<B> for FilterMapIterator<'self, A, B,
         }
         None
     }
+
+    #[inline]
+    #[cfg(not(stage0))]
+    fn size_hint(&self) -> (Option<uint>, Option<uint>) {
+        let (_, upper) = self.iter.size_hint();
+        (None, upper) // can't know a lower bound, due to the predicate
+    }
 }
 
 /// An iterator which yields the current count and the element during iteration