Merge remote-tracking branch 'erickt/master'

Conflicts:
	src/libcore/vec.rs
	src/libstd/getopts.rs

8 files changed, 458 insertions, 30 deletions

diff --git a/doc/tutorial.md b/doc/tutorial.md
index f8be0d0a3ce..ad6dd68d823 100644
--- a/doc/tutorial.md
+++ b/doc/tutorial.md
@@ -922,8 +922,8 @@ for the parameter list, as in `{|| ...}`.
 Partial application is done using the `bind` keyword in Rust.
 
 ~~~~
-let daynum = bind vec::position(_, ["mo", "tu", "we", "do",
-                                    "fr", "sa", "su"]);
+let daynum = bind vec::position_elt(["mo", "tu", "we", "do",
+                                     "fr", "sa", "su"], _);
 ~~~~
 
 Binding a function produces a boxed closure (`fn@` type) in which some
diff --git a/src/comp/middle/alias.rs b/src/comp/middle/alias.rs
index 388fcb20c47..a6177e015c5 100644
--- a/src/comp/middle/alias.rs
+++ b/src/comp/middle/alias.rs
@@ -702,7 +702,7 @@ fn filter_invalid(src: list<@invalid>, bs: [binding]) -> list<@invalid> {
     while cur != list::nil {
         alt cur {
           list::cons(head, tail) {
-            let p = vec::position_pred(bs, {|b| b.node_id == head.node_id});
+            let p = vec::position(bs, {|b| b.node_id == head.node_id});
             if !is_none(p) { out = list::cons(head, @out); }
             cur = *tail;
           }
diff --git a/src/comp/middle/shape.rs b/src/comp/middle/shape.rs
index ef458a54f97..500a8591516 100644
--- a/src/comp/middle/shape.rs
+++ b/src/comp/middle/shape.rs
@@ -426,7 +426,7 @@ fn shape_of(ccx: @crate_ctxt, t: ty::t, ty_param_map: [uint]) -> [u8] {
       }
       ty::ty_param(n, _) {
         // Find the type parameter in the parameter list.
-        alt vec::position(n, ty_param_map) {
+        alt vec::position_elt(ty_param_map, n) {
           some(i) { s += [shape_var, i as u8]; }
           none { fail "ty param not found in ty_param_map"; }
         }
diff --git a/src/comp/middle/trans/base.rs b/src/comp/middle/trans/base.rs
index f330c48d636..37e410e9d5c 100644
--- a/src/comp/middle/trans/base.rs
+++ b/src/comp/middle/trans/base.rs
@@ -3395,7 +3395,7 @@ fn trans_rec(bcx: @block_ctxt, fields: [ast::field],
            have a record type") } };
     let temp_cleanups = [];
     for fld in fields {
-        let ix = option::get(vec::position_pred(ty_fields, {|ft|
+        let ix = option::get(vec::position(ty_fields, {|ft|
             str::eq(fld.node.ident, ft.ident)
         }));
         let dst = GEP_tup_like_1(bcx, t, addr, [0, ix as int]);
diff --git a/src/comp/middle/typeck.rs b/src/comp/middle/typeck.rs
index 9a37ec4a018..50f5dd21007 100644
--- a/src/comp/middle/typeck.rs
+++ b/src/comp/middle/typeck.rs
@@ -1480,7 +1480,7 @@ fn lookup_method(fcx: @fn_ctxt, isc: resolve::iscopes,
                     }
                 };
                 let ifce_methods = ty::iface_methods(tcx, iid);
-                alt vec::position_pred(*ifce_methods, {|m| m.ident == name}) {
+                alt vec::position(*ifce_methods, {|m| m.ident == name}) {
                   some(pos) {
                     let m = ifce_methods[pos];
                     ret some({method_ty: ty::mk_fn(tcx, m.fty),
diff --git a/src/libcore/vec.rs b/src/libcore/vec.rs
index bb88ad3c561..0dc5dea59bc 100644
--- a/src/libcore/vec.rs
+++ b/src/libcore/vec.rs
@@ -278,6 +278,110 @@ fn slice_mut<T: copy>(v: [const T], start: uint, end: uint) -> [mutable T] {
     ret result;
 }
 
+/*
+Function: split
+
+Split the vector `v` by applying each element against the predicate `f`.
+*/
+fn split<T: copy>(v: [T], f: fn(T) -> bool) -> [[T]] {
+    let ln = len(v);
+    if (ln == 0u) { ret [] }
+
+    let start = 0u;
+    let result = [];
+    while start < ln {
+        alt position_from(v, start, ln, f) {
+          none { break }
+          some(i) {
+            push(result, slice(v, start, i));
+            start = i + 1u;
+          }
+        }
+    }
+    push(result, slice(v, start, ln));
+    result
+}
+
+/*
+Function: splitn
+
+Split the vector `v` by applying each element against the predicate `f` up
+to `n` times.
+*/
+fn splitn<T: copy>(v: [T], n: uint, f: fn(T) -> bool) -> [[T]] {
+    let ln = len(v);
+    if (ln == 0u) { ret [] }
+
+    let start = 0u;
+    let count = n;
+    let result = [];
+    while start < ln && count > 0u {
+        alt position_from(v, start, ln, f) {
+          none { break }
+          some(i) {
+            push(result, slice(v, start, i));
+            // Make sure to skip the separator.
+            start = i + 1u;
+            count -= 1u;
+          }
+        }
+    }
+    push(result, slice(v, start, ln));
+    result
+}
+
+/*
+Function: rsplit
+
+Reverse split the vector `v` by applying each element against the predicate
+`f`.
+*/
+fn rsplit<T: copy>(v: [T], f: fn(T) -> bool) -> [[T]] {
+    let ln = len(v);
+    if (ln == 0u) { ret [] }
+
+    let end = ln;
+    let result = [];
+    while end > 0u {
+        alt rposition_from(v, 0u, end, f) {
+          none { break }
+          some(i) {
+            push(result, slice(v, i + 1u, end));
+            end = i;
+          }
+        }
+    }
+    push(result, slice(v, 0u, end));
+    reversed(result)
+}
+
+/*
+Function: rsplitn
+
+Reverse split the vector `v` by applying each element against the predicate
+`f` up to `n times.
+*/
+fn rsplitn<T: copy>(v: [T], n: uint, f: fn(T) -> bool) -> [[T]] {
+    let ln = len(v);
+    if (ln == 0u) { ret [] }
+
+    let end = ln;
+    let count = n;
+    let result = [];
+    while end > 0u && count > 0u {
+        alt rposition_from(v, 0u, end, f) {
+          none { break }
+          some(i) {
+            push(result, slice(v, i + 1u, end));
+            // Make sure to skip the separator.
+            end = i;
+            count -= 1u;
+          }
+        }
+    }
+    push(result, slice(v, 0u, end));
+    reversed(result)
+}
 
 // Mutators
 
@@ -487,6 +591,21 @@ fn concat<T: copy>(v: [const [const T]]) -> [T] {
 }
 
 /*
+Function: connect
+
+Concatenate a vector of vectors, placing a given separator between each
+*/
+fn connect<T: copy>(v: [const [const T]], sep: T) -> [T] {
+    let new: [T] = [];
+    let first = true;
+    for inner: [T] in v {
+        if first { first = false; } else { push(new, sep); }
+        new += inner;
+    }
+    ret new;
+}
+
+/*
 Function: foldl
 
 Reduce a vector from left to right
@@ -593,19 +712,59 @@ fn count<T>(x: T, v: [const T]) -> uint {
 /*
 Function: find
 
-Search for an element that matches a given predicate
+Search for the first element that matches a given predicate
 
 Apply function `f` to each element of `v`, starting from the first.
 When function `f` returns true then an option containing the element
 is returned. If `f` matches no elements then none is returned.
 */
 fn find<T: copy>(v: [T], f: fn(T) -> bool) -> option<T> {
-    for elt: T in v { if f(elt) { ret some(elt); } }
-    ret none;
+    find_from(v, 0u, len(v), f)
 }
 
 /*
-Function: position
+Function: find_from
+
+Search for the first element that matches a given predicate within a range
+
+Apply function `f` to each element of `v` within the range [`start`, `end`).
+When function `f` returns true then an option containing the element
+is returned. If `f` matches no elements then none is returned.
+*/
+fn find_from<T: copy>(v: [T], start: uint, end: uint, f: fn(T) -> bool) ->
+  option<T> {
+    option::map(position_from(v, start, end, f)) { |i| v[i] }
+}
+
+/*
+Function: rfind
+
+Search for the last element that matches a given predicate
+
+Apply function `f` to each element of `v` in reverse order. When function `f`
+returns true then an option containing the element is returned. If `f`
+matches no elements then none is returned.
+*/
+fn rfind<T: copy>(v: [T], f: fn(T) -> bool) -> option<T> {
+    rfind_from(v, 0u, len(v), f)
+}
+
+/*
+Function: rfind_from
+
+Search for the last element that matches a given predicate within a range
+
+Apply function `f` to each element of `v` in reverse order within the range
+[`start`, `end`). When function `f` returns true then an option containing
+the element is returned. If `f` matches no elements then none is returned.
+*/
+fn rfind_from<T: copy>(v: [T], start: uint, end: uint, f: fn(T) -> bool) ->
+  option<T> {
+    option::map(rposition_from(v, start, end, f)) { |i| v[i] }
+}
+
+/*
+Function: position_elt
 
 Find the first index containing a matching value
 
@@ -614,20 +773,86 @@ Returns:
 option::some(uint) - The first index containing a matching value
 option::none - No elements matched
 */
-fn position<T>(x: T, v: [T]) -> option<uint> {
-    let i: uint = 0u;
-    while i < len(v) { if x == v[i] { ret some::<uint>(i); } i += 1u; }
+fn position_elt<T>(v: [T], x: T) -> option<uint> {
+    position(v) { |y| x == y }
+}
+
+/*
+Function: position
+
+Find the first index matching some predicate
+
+Apply function `f` to each element of `v`.  When function `f` returns true
+then an option containing the index is returned. If `f` matches no elements
+then none is returned.
+*/
+fn position<T>(v: [T], f: fn(T) -> bool) -> option<uint> {
+    position_from(v, 0u, len(v), f)
+}
+
+/*
+Function: position_from
+
+Find the first index matching some predicate within a range
+
+Apply function `f` to each element of `v` between the range [`start`, `end`).
+When function `f` returns true then an option containing the index is
+returned. If `f` matches no elements then none is returned.
+*/
+fn position_from<T>(v: [T], start: uint, end: uint, f: fn(T) -> bool) ->
+  option<uint> {
+    assert start <= end;
+    assert end <= len(v);
+    let i = start;
+    while i < end { if f(v[i]) { ret some::<uint>(i); } i += 1u; }
     ret none;
 }
 
 /*
-Function: position_pred
+Function: rposition_elt
+
+Find the last index containing a matching value
+
+Returns:
+
+option::some(uint) - The last index containing a matching value
+option::none - No elements matched
+*/
+fn rposition_elt<T>(v: [T], x: T) -> option<uint> {
+    rposition(v) { |y| x == y }
+}
+
+/*
+Function: rposition
+
+Find the last index matching some predicate
 
-Find the first index for which the value matches some predicate
+Apply function `f` to each element of `v` in reverse order.  When function
+`f` returns true then an option containing the index is returned. If `f`
+matches no elements then none is returned.
 */
-fn position_pred<T>(v: [T], f: fn(T) -> bool) -> option<uint> {
-    let i: uint = 0u;
-    while i < len(v) { if f(v[i]) { ret some::<uint>(i); } i += 1u; }
+fn rposition<T>(v: [T], f: fn(T) -> bool) -> option<uint> {
+    rposition_from(v, 0u, len(v), f)
+}
+
+/*
+Function: rposition_from
+
+Find the last index matching some predicate within a range
+
+Apply function `f` to each element of `v` in reverse order between the range
+[`start`, `end`). When function `f` returns true then an option containing
+the index is returned. If `f` matches no elements then none is returned.
+*/
+fn rposition_from<T>(v: [T], start: uint, end: uint, f: fn(T) -> bool) ->
+  option<uint> {
+    assert start <= end;
+    assert end <= len(v);
+    let i = end;
+    while i > start {
+        if f(v[i - 1u]) { ret some::<uint>(i - 1u); }
+        i -= 1u;
+    }
     ret none;
 }
 
@@ -1444,21 +1669,174 @@ mod tests {
     }
 
     #[test]
-    fn test_position() {
-        let v1: [int] = [1, 2, 3, 3, 2, 5];
-        assert (position(1, v1) == option::some::<uint>(0u));
-        assert (position(2, v1) == option::some::<uint>(1u));
-        assert (position(5, v1) == option::some::<uint>(5u));
-        assert (position(4, v1) == option::none::<uint>);
+    fn test_position_elt() {
+        assert position_elt([], 1) == none;
+
+        let v1 = [1, 2, 3, 3, 2, 5];
+        assert position_elt(v1, 1) == some(0u);
+        assert position_elt(v1, 2) == some(1u);
+        assert position_elt(v1, 5) == some(5u);
+        assert position_elt(v1, 4) == none;
     }
 
     #[test]
-    fn test_position_pred() {
+    fn test_position() {
         fn less_than_three(&&i: int) -> bool { ret i < 3; }
         fn is_eighteen(&&i: int) -> bool { ret i == 18; }
-        let v1: [int] = [5, 4, 3, 2, 1];
-        assert position_pred(v1, less_than_three) == option::some::<uint>(3u);
-        assert position_pred(v1, is_eighteen) == option::none::<uint>;
+
+        assert position([], less_than_three) == none;
+
+        let v1 = [5, 4, 3, 2, 1];
+        assert position(v1, less_than_three) == some(3u);
+        assert position(v1, is_eighteen) == none;
+    }
+
+    #[test]
+    fn test_position_from() {
+        assert position_from([], 0u, 0u, f) == none;
+
+        fn f(xy: (int, char)) -> bool { let (_x, y) = xy; y == 'b' }
+        let v = [(0, 'a'), (1, 'b'), (2, 'c'), (3, 'b')];
+
+        assert position_from(v, 0u, 0u, f) == none;
+        assert position_from(v, 0u, 1u, f) == none;
+        assert position_from(v, 0u, 2u, f) == some(1u);
+        assert position_from(v, 0u, 3u, f) == some(1u);
+        assert position_from(v, 0u, 4u, f) == some(1u);
+
+        assert position_from(v, 1u, 1u, f) == none;
+        assert position_from(v, 1u, 2u, f) == some(1u);
+        assert position_from(v, 1u, 3u, f) == some(1u);
+        assert position_from(v, 1u, 4u, f) == some(1u);
+
+        assert position_from(v, 2u, 2u, f) == none;
+        assert position_from(v, 2u, 3u, f) == none;
+        assert position_from(v, 2u, 4u, f) == some(3u);
+
+        assert position_from(v, 3u, 3u, f) == none;
+        assert position_from(v, 3u, 4u, f) == some(3u);
+
+        assert position_from(v, 4u, 4u, f) == none;
+    }
+
+    #[test]
+    fn test_find() {
+        assert find([], f) == none;
+
+        fn f(xy: (int, char)) -> bool { let (_x, y) = xy; y == 'b' }
+        fn g(xy: (int, char)) -> bool { let (_x, y) = xy; y == 'd' }
+        let v = [(0, 'a'), (1, 'b'), (2, 'c'), (3, 'b')];
+
+        assert find(v, f) == some((1, 'b'));
+        assert find(v, g) == none;
+    }
+
+    #[test]
+    fn test_find_from() {
+        assert find_from([], 0u, 0u, f) == none;
+
+        fn f(xy: (int, char)) -> bool { let (_x, y) = xy; y == 'b' }
+        let v = [(0, 'a'), (1, 'b'), (2, 'c'), (3, 'b')];
+
+        assert find_from(v, 0u, 0u, f) == none;
+        assert find_from(v, 0u, 1u, f) == none;
+        assert find_from(v, 0u, 2u, f) == some((1, 'b'));
+        assert find_from(v, 0u, 3u, f) == some((1, 'b'));
+        assert find_from(v, 0u, 4u, f) == some((1, 'b'));
+
+        assert find_from(v, 1u, 1u, f) == none;
+        assert find_from(v, 1u, 2u, f) == some((1, 'b'));
+        assert find_from(v, 1u, 3u, f) == some((1, 'b'));
+        assert find_from(v, 1u, 4u, f) == some((1, 'b'));
+
+        assert find_from(v, 2u, 2u, f) == none;
+        assert find_from(v, 2u, 3u, f) == none;
+        assert find_from(v, 2u, 4u, f) == some((3, 'b'));
+
+        assert find_from(v, 3u, 3u, f) == none;
+        assert find_from(v, 3u, 4u, f) == some((3, 'b'));
+
+        assert find_from(v, 4u, 4u, f) == none;
+    }
+
+    #[test]
+    fn test_rposition() {
+        assert find([], f) == none;
+
+        fn f(xy: (int, char)) -> bool { let (_x, y) = xy; y == 'b' }
+        fn g(xy: (int, char)) -> bool { let (_x, y) = xy; y == 'd' }
+        let v = [(0, 'a'), (1, 'b'), (2, 'c'), (3, 'b')];
+
+        assert position(v, f) == some(1u);
+        assert position(v, g) == none;
+    }
+
+    #[test]
+    fn test_rposition_from() {
+        assert rposition_from([], 0u, 0u, f) == none;
+
+        fn f(xy: (int, char)) -> bool { let (_x, y) = xy; y == 'b' }
+        let v = [(0, 'a'), (1, 'b'), (2, 'c'), (3, 'b')];
+
+        assert rposition_from(v, 0u, 0u, f) == none;
+        assert rposition_from(v, 0u, 1u, f) == none;
+        assert rposition_from(v, 0u, 2u, f) == some(1u);
+        assert rposition_from(v, 0u, 3u, f) == some(1u);
+        assert rposition_from(v, 0u, 4u, f) == some(3u);
+
+        assert rposition_from(v, 1u, 1u, f) == none;
+        assert rposition_from(v, 1u, 2u, f) == some(1u);
+        assert rposition_from(v, 1u, 3u, f) == some(1u);
+        assert rposition_from(v, 1u, 4u, f) == some(3u);
+
+        assert rposition_from(v, 2u, 2u, f) == none;
+        assert rposition_from(v, 2u, 3u, f) == none;
+        assert rposition_from(v, 2u, 4u, f) == some(3u);
+
+        assert rposition_from(v, 3u, 3u, f) == none;
+        assert rposition_from(v, 3u, 4u, f) == some(3u);
+
+        assert rposition_from(v, 4u, 4u, f) == none;
+    }
+
+    #[test]
+    fn test_rfind() {
+        assert rfind([], f) == none;
+
+        fn f(xy: (int, char)) -> bool { let (_x, y) = xy; y == 'b' }
+        fn g(xy: (int, char)) -> bool { let (_x, y) = xy; y == 'd' }
+        let v = [(0, 'a'), (1, 'b'), (2, 'c'), (3, 'b')];
+
+        assert rfind(v, f) == some((3, 'b'));
+        assert rfind(v, g) == none;
+    }
+
+    #[test]
+    fn test_rfind_from() {
+        assert rfind_from([], 0u, 0u, f) == none;
+
+        fn f(xy: (int, char)) -> bool { let (_x, y) = xy; y == 'b' }
+        let v = [(0, 'a'), (1, 'b'), (2, 'c'), (3, 'b')];
+
+        assert rfind_from(v, 0u, 0u, f) == none;
+        assert rfind_from(v, 0u, 1u, f) == none;
+        assert rfind_from(v, 0u, 2u, f) == some((1, 'b'));
+        assert rfind_from(v, 0u, 3u, f) == some((1, 'b'));
+        assert rfind_from(v, 0u, 4u, f) == some((3, 'b'));
+
+        assert rfind_from(v, 1u, 1u, f) == none;
+        assert rfind_from(v, 1u, 2u, f) == some((1, 'b'));
+        assert rfind_from(v, 1u, 3u, f) == some((1, 'b'));
+        assert rfind_from(v, 1u, 4u, f) == some((3, 'b'));
+
+        assert rfind_from(v, 2u, 2u, f) == none;
+        assert rfind_from(v, 2u, 3u, f) == none;
+        assert rfind_from(v, 2u, 4u, f) == some((3, 'b'));
+
+        assert rfind_from(v, 3u, 3u, f) == none;
+        assert rfind_from(v, 3u, 4u, f) == some((3, 'b'));
+
+        assert rfind_from(v, 4u, 4u, f) == none;
     }
 
     #[test]
@@ -1496,6 +1874,48 @@ mod tests {
     }
 
     #[test]
+    fn test_split() {
+        fn f(&&x: int) -> bool { x == 3 }
+
+        assert split([], f) == [];
+        assert split([1, 2], f) == [[1, 2]];
+        assert split([3, 1, 2], f) == [[], [1, 2]];
+        assert split([1, 2, 3], f) == [[1, 2], []];
+        assert split([1, 2, 3, 4, 3, 5], f) == [[1, 2], [4], [5]];
+    }
+
+    #[test]
+    fn test_splitn() {
+        fn f(&&x: int) -> bool { x == 3 }
+
+        assert splitn([], 1u, f) == [];
+        assert splitn([1, 2], 1u, f) == [[1, 2]];
+        assert splitn([3, 1, 2], 1u, f) == [[], [1, 2]];
+        assert splitn([1, 2, 3], 1u, f) == [[1, 2], []];
+        assert splitn([1, 2, 3, 4, 3, 5], 1u, f) == [[1, 2], [4, 3, 5]];
+    }
+
+    #[test]
+    fn test_rsplit() {
+        fn f(&&x: int) -> bool { x == 3 }
+
+        assert rsplit([], f) == [];
+        assert rsplit([1, 2], f) == [[1, 2]];
+        assert rsplit([1, 2, 3], f) == [[1, 2], []];
+        assert rsplit([1, 2, 3, 4, 3, 5], f) == [[1, 2], [4], [5]];
+    }
+
+    #[test]
+    fn test_rsplitn() {
+        fn f(&&x: int) -> bool { x == 3 }
+
+        assert rsplitn([], 1u, f) == [];
+        assert rsplitn([1, 2], 1u, f) == [[1, 2]];
+        assert rsplitn([1, 2, 3], 1u, f) == [[1, 2], []];
+        assert rsplitn([1, 2, 3, 4, 3, 5], 1u, f) == [[1, 2, 3, 4], [5]];
+    }
+
+    #[test]
     // FIXME: Windows can't undwind
     #[ignore(cfg(target_os = "win32"))]
     fn test_init_empty() {
@@ -1514,6 +1934,13 @@ mod tests {
     }
 
     #[test]
+    fn test_connect() {
+        assert connect([], 0) == [];
+        assert connect([[1], [2, 3]], 0) == [1, 0, 2, 3];
+        assert connect([[1], [2], [3]], 0) == [1, 0, 2, 0, 3];
+    }
+
+    #[test]
     fn test_windowed () {
         assert [[1u,2u,3u],[2u,3u,4u],[3u,4u,5u],[4u,5u,6u]]
               == windowed (3u, [1u,2u,3u,4u,5u,6u]);
diff --git a/src/libstd/getopts.rs b/src/libstd/getopts.rs
index bc96cb65efa..48d83f0e5c2 100644
--- a/src/libstd/getopts.rs
+++ b/src/libstd/getopts.rs
@@ -149,7 +149,7 @@ fn name_str(nm: name) -> str {
 }
 
 fn find_opt(opts: [opt], nm: name) -> option<uint> {
-    vec::position_pred(opts, { |opt| opt.name == nm })
+    vec::position(opts, { |opt| opt.name == nm })
 }
 
 /*
diff --git a/src/libstd/map.rs b/src/libstd/map.rs
index 3f53270ed10..8da3d78552d 100644
--- a/src/libstd/map.rs
+++ b/src/libstd/map.rs
@@ -95,6 +95,7 @@ iface map<K: copy, V: copy> {
     Iterate over all the keys in the map
     */
     fn keys(fn(K));
+
     /*
     Iterate over all the values in the map
     */
@@ -631,4 +632,4 @@ mod tests {
         map.insert(key, "val");
         assert (option::get(map.find(key)) == "val");
     }
-}
\ No newline at end of file
+}