Add a Buildable interface for constructing general sequences. Work on #2921.

3 files changed, 125 insertions, 9 deletions

diff --git a/src/libcore/at_vec.rs b/src/libcore/at_vec.rs
index a32f74e737f..a161cc8d6f7 100644
--- a/src/libcore/at_vec.rs
+++ b/src/libcore/at_vec.rs
@@ -24,9 +24,6 @@ extern mod rusti {
     fn move_val_init<T>(&dst: T, -src: T);
 }
 
-/// A function used to initialize the elements of a vector
-type InitOp<T> = fn(uint) -> T;
-
 /// Returns the number of elements the vector can hold without reallocating
 #[inline(always)]
 pure fn capacity<T>(&&v: @[const T]) -> uint {
@@ -115,7 +112,7 @@ pure fn map<T, U>(v: &[T], f: fn(T) -> U) -> @[U] {
  * Creates an immutable vector of size `n_elts` and initializes the elements
  * to the value returned by the function `op`.
  */
-pure fn from_fn<T>(n_elts: uint, op: InitOp<T>) -> @[T] {
+pure fn from_fn<T>(n_elts: uint, op: iter::InitOp<T>) -> @[T] {
     do build_sized(n_elts) |push| {
         let mut i: uint = 0u;
         while i < n_elts { push(op(i)); i += 1u; }
diff --git a/src/libcore/iter.rs b/src/libcore/iter.rs
index 39adaa313ed..3606f826b0e 100644
--- a/src/libcore/iter.rs
+++ b/src/libcore/iter.rs
@@ -1,3 +1,6 @@
+/// A function used to initialize the elements of a sequence
+type InitOp<T> = fn(uint) -> T;
+
 trait BaseIter<A> {
     pure fn each(blk: fn(A) -> bool);
     pure fn size_hint() -> option<uint>;
@@ -29,6 +32,26 @@ trait CopyableIter<A:copy> {
     pure fn find(p: fn(A) -> bool) -> option<A>;
 }
 
+// A trait for sequences that can be by imperatively pushing elements
+// onto them.
+trait Buildable<A> {
+    /**
+     * Builds a buildable sequence by calling a provided function with
+     * an argument function that pushes an element onto the back of
+     * the sequence.
+     * This version takes an initial size for the sequence.
+     *
+     * # Arguments
+     *
+     * * size - A hint for an initial size of the sequence
+     * * builder - A function that will construct the sequence. It recieves
+     *             as an argument a function that will push an element
+     *             onto the sequence being constructed.
+     */
+     static pure fn build_sized(size: uint,
+                                builder: fn(push: pure fn(+A))) -> self;
+}
+
 pure fn eachi<A,IA:BaseIter<A>>(self: IA, blk: fn(uint, A) -> bool) {
     let mut i = 0u;
     for self.each |a| {
@@ -172,6 +195,105 @@ pure fn find<A: copy,IA:BaseIter<A>>(self: IA,
     return none;
 }
 
+// Some functions for just building
+
+/**
+ * Builds a sequence by calling a provided function with an argument
+ * function that pushes an element to the back of a sequence.
+ *
+ * # Arguments
+ *
+ * * builder - A function that will construct the sequence. It recieves
+ *             as an argument a function that will push an element
+ *             onto the sequence being constructed.
+ */
+#[inline(always)]
+pure fn build<A,B: Buildable<A>>(builder: fn(push: pure fn(+A))) -> B {
+    build_sized(4, builder)
+}
+
+/**
+ * Builds a sequence by calling a provided function with an argument
+ * function that pushes an element to the back of a sequence.
+ * This version takes an initial size for the sequence.
+ *
+ * # Arguments
+ *
+ * * size - An option, maybe containing initial size of the sequence
+ *          to reserve
+ * * builder - A function that will construct the sequence. It recieves
+ *             as an argument a function that will push an element
+ *             onto the sequence being constructed.
+ */
+#[inline(always)]
+pure fn build_sized_opt<A,B: Buildable<A>>(
+    size: option<uint>,
+    builder: fn(push: pure fn(+A))) -> B {
+
+    build_sized(size.get_default(4), builder)
+}
+
+// Functions that combine iteration and building
+
+/// Apply a function to each element of an iterable and return the results
+fn map<T,IT: BaseIter<T>,U,BU: Buildable<U>>(v: IT, f: fn(T) -> U) -> BU {
+    do build_sized_opt(v.size_hint()) |push| {
+        for v.each() |elem| {
+            push(f(elem));
+        }
+    }
+}
+
+/**
+ * Creates and initializes a generic sequence from a function
+ *
+ * Creates a generic sequence of size `n_elts` and initializes the elements
+ * to the value returned by the function `op`.
+ */
+pure fn from_fn<T,BT: Buildable<T>>(n_elts: uint, op: InitOp<T>) -> BT {
+    do build_sized(n_elts) |push| {
+        let mut i: uint = 0u;
+        while i < n_elts { push(op(i)); i += 1u; }
+    }
+}
+
+/**
+ * Creates and initializes a generic sequence with some element
+ *
+ * Creates an immutable vector of size `n_elts` and initializes the elements
+ * to the value `t`.
+ */
+pure fn from_elem<T: copy,BT: Buildable<T>>(n_elts: uint, t: T) -> BT {
+    do build_sized(n_elts) |push| {
+        let mut i: uint = 0u;
+        while i < n_elts { push(t); i += 1u; }
+    }
+}
+
+/// Appending two generic sequences
+#[inline(always)]
+pure fn append<T: copy,IT: BaseIter<T>,BT: Buildable<T>>(
+    lhs: IT, rhs: IT) -> BT {
+    let size_opt = lhs.size_hint().chain(
+        |sz1| rhs.size_hint().map(|sz2| sz1+sz2));
+    do build_sized_opt(size_opt) |push| {
+        for lhs.each |x| { push(x); }
+        for rhs.each |x| { push(x); }
+    }
+}
+
+/// Copies a generic sequence, possibly converting it to a different
+/// type of sequence.
+#[inline(always)]
+pure fn copy_seq<T: copy,IT: BaseIter<T>,BT: Buildable<T>>(
+    v: IT) -> BT {
+    do build_sized_opt(v.size_hint()) |push| {
+        for v.each |x| { push(x); }
+    }
+}
+
+
+
 /*
 #[test]
 fn test_enumerate() {
diff --git a/src/libcore/vec.rs b/src/libcore/vec.rs
index b02abdffcec..cbbaf3f73ab 100644
--- a/src/libcore/vec.rs
+++ b/src/libcore/vec.rs
@@ -110,9 +110,6 @@ extern mod rusti {
     fn move_val_init<T>(&dst: T, -src: T);
 }
 
-/// A function used to initialize the elements of a vector
-type InitOp/&<T> = fn(uint) -> T;
-
 /// Returns true if a vector contains no elements
 pure fn is_empty<T>(v: &[const T]) -> bool {
     as_const_buf(v, |_p, len| len == 0u)
@@ -188,7 +185,7 @@ pure fn len<T>(&&v: &[const T]) -> uint {
  * Creates an immutable vector of size `n_elts` and initializes the elements
  * to the value returned by the function `op`.
  */
-pure fn from_fn<T>(n_elts: uint, op: InitOp<T>) -> ~[T] {
+pure fn from_fn<T>(n_elts: uint, op: iter::InitOp<T>) -> ~[T] {
     let mut v = ~[];
     unchecked{reserve(v, n_elts);}
     let mut i: uint = 0u;
@@ -679,7 +676,7 @@ fn grow<T: copy>(&v: ~[const T], n: uint, initval: T) {
  * * init_op - A function to call to retreive each appended element's
  *             value
  */
-fn grow_fn<T>(&v: ~[const T], n: uint, op: InitOp<T>) {
+fn grow_fn<T>(&v: ~[const T], n: uint, op: iter::InitOp<T>) {
     reserve_at_least(v, len(v) + n);
     let mut i: uint = 0u;
     while i < n { push(v, op(i)); i += 1u; }