core: Add binary_search and binary_search_elem methods to slices.

These are like the existing bsearch methods but if the search fails,
it returns the next insertion point.

The new `binary_search` returns a `BinarySearchResult` that is either
`Found` or `NotFound`. For convenience, the `found` and `not_found`
methods convert to `Option`, ala `Result`.

Deprecate bsearch and bsearch_elem.

8 files changed, 186 insertions, 47 deletions

diff --git a/src/etc/unicode.py b/src/etc/unicode.py
index 5424cd3b3ab..7663cd1e346 100755
--- a/src/etc/unicode.py
+++ b/src/etc/unicode.py
@@ -293,13 +293,12 @@ def emit_bsearch_range_table(f):
     f.write("""
 fn bsearch_range_table(c: char, r: &'static [(char,char)]) -> bool {
     use core::cmp::{Equal, Less, Greater};
-    use core::slice::ImmutableVector;
-    use core::option::None;
-    r.bsearch(|&(lo,hi)| {
+    use core::slice::ImmutableSlice;
+    r.binary_search(|&(lo,hi)| {
         if lo <= c && c <= hi { Equal }
         else if hi < c { Less }
         else { Greater }
-    }) != None
+    }).found().is_some()
 }\n
 """)
 
@@ -352,9 +351,10 @@ def emit_conversions_module(f, lowerupper, upperlower):
     f.write("pub mod conversions {")
     f.write("""
     use core::cmp::{Equal, Less, Greater};
-    use core::slice::ImmutableVector;
+    use core::slice::ImmutableSlice;
     use core::tuple::Tuple2;
     use core::option::{Option, Some, None};
+    use core::slice;
 
     pub fn to_lower(c: char) -> char {
         match bsearch_case_table(c, LuLl_table) {
@@ -371,11 +371,14 @@ def emit_conversions_module(f, lowerupper, upperlower):
     }
 
     fn bsearch_case_table(c: char, table: &'static [(char, char)]) -> Option<uint> {
-        table.bsearch(|&(key, _)| {
+        match table.binary_search(|&(key, _)| {
             if c == key { Equal }
             else if key < c { Less }
             else { Greater }
-        })
+        }) {
+            slice::Found(i) => Some(i),
+            slice::NotFound(_) => None,
+        }
     }
 
 """)
@@ -387,8 +390,8 @@ def emit_conversions_module(f, lowerupper, upperlower):
 
 def emit_grapheme_module(f, grapheme_table, grapheme_cats):
     f.write("""pub mod grapheme {
-    use core::option::{Some, None};
-    use core::slice::ImmutableVector;
+    use core::slice::ImmutableSlice;
+    use core::slice;
 
     #[allow(non_camel_case_types)]
     #[deriving(Clone)]
@@ -400,16 +403,16 @@ def emit_grapheme_module(f, grapheme_table, grapheme_cats):
 
     fn bsearch_range_value_table(c: char, r: &'static [(char, char, GraphemeCat)]) -> GraphemeCat {
         use core::cmp::{Equal, Less, Greater};
-        match r.bsearch(|&(lo, hi, _)| {
+        match r.binary_search(|&(lo, hi, _)| {
             if lo <= c && c <= hi { Equal }
             else if hi < c { Less }
             else { Greater }
         }) {
-            Some(idx) => {
+            slice::Found(idx) => {
                 let (_, _, cat) = r[idx];
                 cat
             }
-            None => GC_Any
+            slice::NotFound(_) => GC_Any
         }
     }
 
@@ -427,20 +430,21 @@ def emit_grapheme_module(f, grapheme_table, grapheme_cats):
 def emit_charwidth_module(f, width_table):
     f.write("pub mod charwidth {\n")
     f.write("    use core::option::{Option, Some, None};\n")
-    f.write("    use core::slice::ImmutableVector;\n")
+    f.write("    use core::slice::ImmutableSlice;\n")
+    f.write("    use core::slice;\n")
     f.write("""
     fn bsearch_range_value_table(c: char, is_cjk: bool, r: &'static [(char, char, u8, u8)]) -> u8 {
         use core::cmp::{Equal, Less, Greater};
-        match r.bsearch(|&(lo, hi, _, _)| {
+        match r.binary_search(|&(lo, hi, _, _)| {
             if lo <= c && c <= hi { Equal }
             else if hi < c { Less }
             else { Greater }
         }) {
-            Some(idx) => {
+            slice::Found(idx) => {
                 let (_, _, r_ncjk, r_cjk) = r[idx];
                 if is_cjk { r_cjk } else { r_ncjk }
             }
-            None => 1
+            slice::NotFound(_) => 1
         }
     }
 """)
@@ -525,19 +529,19 @@ def emit_norm_module(f, canon, compat, combine, norm_props):
 
     f.write("""
     fn bsearch_range_value_table(c: char, r: &'static [(char, char, u8)]) -> u8 {
-        use core::option::{Some, None};
         use core::cmp::{Equal, Less, Greater};
-        use core::slice::ImmutableVector;
-        match r.bsearch(|&(lo, hi, _)| {
+        use core::slice::ImmutableSlice;
+        use core::slice;
+        match r.binary_search(|&(lo, hi, _)| {
             if lo <= c && c <= hi { Equal }
             else if hi < c { Less }
             else { Greater }
         }) {
-            Some(idx) => {
+            slice::Found(idx) => {
                 let (_, _, result) = r[idx];
                 result
             }
-            None => 0
+            slice::NotFound(_) => 0
         }
     }\n
 """)
diff --git a/src/libcollections/slice.rs b/src/libcollections/slice.rs
index 9a625469140..aac5b24fa6f 100644
--- a/src/libcollections/slice.rs
+++ b/src/libcollections/slice.rs
@@ -102,6 +102,7 @@ pub use core::slice::{Chunks, Slice, ImmutableSlice, ImmutablePartialEqSlice};
 pub use core::slice::{ImmutableOrdSlice, MutableSlice, Items, MutItems};
 pub use core::slice::{MutSplits, MutChunks};
 pub use core::slice::{bytes, MutableCloneableSlice};
+pub use core::slice::{BinarySearchResult, Found, NotFound};
 
 // Functional utilities
 
diff --git a/src/libcore/slice.rs b/src/libcore/slice.rs
index e0088c4761b..4f6c346a411 100644
--- a/src/libcore/slice.rs
+++ b/src/libcore/slice.rs
@@ -51,6 +51,7 @@ use raw::{Repr};
 // Avoid conflicts with *both* the Slice trait (buggy) and the `slice::raw` module.
 use RawSlice = raw::Slice;
 
+
 //
 // Extension traits
 //
@@ -205,9 +206,26 @@ pub trait ImmutableSlice<'a, T> {
      * Returns the index where the comparator returned `Equal`, or `None` if
      * not found.
      */
+    #[deprecated = "use binary_search"]
     fn bsearch(&self, f: |&T| -> Ordering) -> Option<uint>;
 
     /**
+     * Binary search a sorted vector with a comparator function.
+     *
+     * The comparator function should implement an order consistent
+     * with the sort order of the underlying vector, returning an
+     * order code that indicates whether its argument is `Less`,
+     * `Equal` or `Greater` the desired target.
+     *
+     * If the value is found then `Found` is returned, containing the
+     * index of the matching element; if the value is not found then
+     * `NotFound` is returned, containing the index where a matching
+     * element could be inserted while maintaining sorted order.
+     */
+    #[unstable]
+    fn binary_search(&self, f: |&T| -> Ordering) -> BinarySearchResult;
+
+    /**
      * Returns an immutable reference to the first element in this slice
      * and adjusts the slice in place so that it no longer contains
      * that element. O(1).
@@ -377,6 +395,7 @@ impl<'a,T> ImmutableSlice<'a, T> for &'a [T] {
     }
 
 
+    #[deprecated = "use binary_search"]
     fn bsearch(&self, f: |&T| -> Ordering) -> Option<uint> {
         let mut base : uint = 0;
         let mut lim : uint = self.len();
@@ -396,6 +415,26 @@ impl<'a,T> ImmutableSlice<'a, T> for &'a [T] {
         return None;
     }
 
+    #[unstable]
+    fn binary_search(&self, f: |&T| -> Ordering) -> BinarySearchResult {
+        let mut base : uint = 0;
+        let mut lim : uint = self.len();
+
+        while lim != 0 {
+            let ix = base + (lim >> 1);
+            match f(&self[ix]) {
+                Equal => return Found(ix),
+                Less => {
+                    base = ix + 1;
+                    lim -= 1;
+                }
+                Greater => ()
+            }
+            lim >>= 1;
+        }
+        return NotFound(base);
+    }
+
     fn shift_ref(&mut self) -> Option<&'a T> {
         unsafe {
             let s: &mut RawSlice<T> = transmute(self);
@@ -826,13 +865,31 @@ pub trait ImmutableOrdSlice<T: Ord> {
      *
      * Returns the index of the element or None if not found.
      */
+    #[deprecated = "use binary_search_elem"]
     fn bsearch_elem(&self, x: &T) -> Option<uint>;
+
+    /**
+     * Binary search a sorted vector for a given element.
+     *
+     * If the value is found then `Found` is returned, containing the
+     * index of the matching element; if the value is not found then
+     * `NotFound` is returned, containing the index where a matching
+     * element could be inserted while maintaining sorted order.
+     */
+    #[unstable]
+    fn binary_search_elem(&self, x: &T) -> BinarySearchResult;
 }
 
 impl<'a, T: Ord> ImmutableOrdSlice<T> for &'a [T] {
+    #[deprecated = "use binary_search_elem"]
     fn bsearch_elem(&self, x: &T) -> Option<uint> {
         self.bsearch(|p| p.cmp(x))
     }
+
+    #[unstable]
+    fn binary_search_elem(&self, x: &T) -> BinarySearchResult {
+        self.binary_search(|p| p.cmp(x))
+    }
 }
 
 /// Trait for &[T] where T is Cloneable
@@ -1337,6 +1394,41 @@ impl<'a, T> DoubleEndedIterator<&'a mut [T]> for MutChunks<'a, T> {
 
 
 
+/// The result of calling `binary_search`.
+///
+/// `Found` means the search succeeded, and the contained value is the
+/// index of the matching element. `NotFound` means the search
+/// succeeded, and the contained value is an index where a matching
+/// value could be inserted while maintaining sort order.
+#[deriving(PartialEq, Show)]
+pub enum BinarySearchResult {
+    /// The index of the found value.
+    Found(uint),
+    /// The index where the value should have been found.
+    NotFound(uint)
+}
+
+impl BinarySearchResult {
+    /// Converts a `Found` to `Some`, `NotFound` to `None`.
+    /// Similar to `Result::ok`.
+    pub fn found(&self) -> Option<uint> {
+        match *self {
+            Found(i) => Some(i),
+            NotFound(_) => None
+        }
+    }
+
+    /// Convert a `Found` to `None`, `NotFound` to `Some`.
+    /// Similar to `Result::err`.
+    pub fn not_found(&self) -> Option<uint> {
+        match *self {
+            Found(_) => None,
+            NotFound(i) => Some(i)
+        }
+    }
+}
+
+
 
 //
 // Free functions
diff --git a/src/libcoretest/lib.rs b/src/libcoretest/lib.rs
index 0b8ae09c9a3..3864321586c 100644
--- a/src/libcoretest/lib.rs
+++ b/src/libcoretest/lib.rs
@@ -28,4 +28,5 @@ mod option;
 mod ptr;
 mod raw;
 mod result;
+mod slice;
 mod tuple;
diff --git a/src/libcoretest/slice.rs b/src/libcoretest/slice.rs
new file mode 100644
index 00000000000..1288756dea4
--- /dev/null
+++ b/src/libcoretest/slice.rs
@@ -0,0 +1,35 @@
+// Copyright 2014 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+use std::slice::{Found, NotFound};
+
+#[test]
+fn binary_search_not_found() {
+    let b = [1i, 2, 4, 6, 8, 9];
+    assert!(b.binary_search(|v| v.cmp(&6)) == Found(3));
+    let b = [1i, 2, 4, 6, 8, 9];
+    assert!(b.binary_search(|v| v.cmp(&5)) == NotFound(3));
+    let b = [1i, 2, 4, 6, 7, 8, 9];
+    assert!(b.binary_search(|v| v.cmp(&6)) == Found(3));
+    let b = [1i, 2, 4, 6, 7, 8, 9];
+    assert!(b.binary_search(|v| v.cmp(&5)) == NotFound(3));
+    let b = [1i, 2, 4, 6, 8, 9];
+    assert!(b.binary_search(|v| v.cmp(&8)) == Found(4));
+    let b = [1i, 2, 4, 6, 8, 9];
+    assert!(b.binary_search(|v| v.cmp(&7)) == NotFound(4));
+    let b = [1i, 2, 4, 6, 7, 8, 9];
+    assert!(b.binary_search(|v| v.cmp(&8)) == Found(5));
+    let b = [1i, 2, 4, 5, 6, 8, 9];
+    assert!(b.binary_search(|v| v.cmp(&7)) == NotFound(5));
+    let b = [1i, 2, 4, 5, 6, 8, 9];
+    assert!(b.binary_search(|v| v.cmp(&0)) == NotFound(0));
+    let b = [1i, 2, 4, 5, 6, 8];
+    assert!(b.binary_search(|v| v.cmp(&9)) == NotFound(6));
+}
diff --git a/src/libregex/vm.rs b/src/libregex/vm.rs
index 118c2f7a3ce..6bf3e149066 100644
--- a/src/libregex/vm.rs
+++ b/src/libregex/vm.rs
@@ -35,6 +35,7 @@
 
 use std::cmp;
 use std::mem;
+use std::slice;
 use std::slice::MutableSlice;
 use compile::{
     Program,
@@ -222,8 +223,8 @@ impl<'r, 't> Nfa<'r, 't> {
                     let negate = flags & FLAG_NEGATED > 0;
                     let casei = flags & FLAG_NOCASE > 0;
                     let found = ranges.as_slice();
-                    let found = found.bsearch(|&rc| class_cmp(casei, c, rc));
-                    let found = found.is_some();
+                    let found = found.binary_search(|&rc| class_cmp(casei, c, rc))
+                        .found().is_some();
                     if found ^ negate {
                         self.add(nlist, pc+1, caps);
                     }
@@ -513,7 +514,7 @@ pub fn is_word(c: Option<char>) -> bool {
     // Try the common ASCII case before invoking binary search.
     match c {
         '_' | '0' .. '9' | 'a' .. 'z' | 'A' .. 'Z' => true,
-        _ => PERLW.bsearch(|&(start, end)| {
+        _ => PERLW.binary_search(|&(start, end)| {
             if c >= start && c <= end {
                 Equal
             } else if start > c {
@@ -521,7 +522,7 @@ pub fn is_word(c: Option<char>) -> bool {
             } else {
                 Less
             }
-        }).is_some()
+        }).found().is_some()
     }
 }
 
diff --git a/src/libunicode/normalize.rs b/src/libunicode/normalize.rs
index c5e1773dcff..a60e95c3827 100644
--- a/src/libunicode/normalize.rs
+++ b/src/libunicode/normalize.rs
@@ -15,20 +15,21 @@
 
 use core::cmp::{Equal, Less, Greater};
 use core::option::{Option, Some, None};
+use core::slice;
 use core::slice::ImmutableSlice;
 use tables::normalization::{canonical_table, compatibility_table, composition_table};
 
 fn bsearch_table<T>(c: char, r: &'static [(char, &'static [T])]) -> Option<&'static [T]> {
-    match r.bsearch(|&(val, _)| {
+    match r.binary_search(|&(val, _)| {
         if c == val { Equal }
         else if val < c { Less }
         else { Greater }
     }) {
-        Some(idx) => {
+        slice::Found(idx) => {
             let (_, result) = r[idx];
             Some(result)
         }
-        None => None
+        slice::NotFound(_) => None
     }
 }
 
@@ -82,16 +83,16 @@ pub fn compose(a: char, b: char) -> Option<char> {
         match bsearch_table(a, composition_table) {
             None => None,
             Some(candidates) => {
-                match candidates.bsearch(|&(val, _)| {
+                match candidates.binary_search(|&(val, _)| {
                     if b == val { Equal }
                     else if val < b { Less }
                     else { Greater }
                 }) {
-                    Some(idx) => {
+                    slice::Found(idx) => {
                         let (_, result) = candidates[idx];
                         Some(result)
                     }
-                    None => None
+                    slice::NotFound(_) => None
                 }
             }
         }
diff --git a/src/libunicode/tables.rs b/src/libunicode/tables.rs
index e58fe589557..d6010cd8d7b 100644
--- a/src/libunicode/tables.rs
+++ b/src/libunicode/tables.rs
@@ -15,12 +15,11 @@
 fn bsearch_range_table(c: char, r: &'static [(char,char)]) -> bool {
     use core::cmp::{Equal, Less, Greater};
     use core::slice::ImmutableSlice;
-    use core::option::None;
-    r.bsearch(|&(lo,hi)| {
+    r.binary_search(|&(lo,hi)| {
         if lo <= c && c <= hi { Equal }
         else if hi < c { Less }
         else { Greater }
-    }) != None
+    }).found().is_some()
 }
 
 pub mod general_category {
@@ -6228,19 +6227,19 @@ pub mod normalization {
 
 
     fn bsearch_range_value_table(c: char, r: &'static [(char, char, u8)]) -> u8 {
-        use core::option::{Some, None};
         use core::cmp::{Equal, Less, Greater};
         use core::slice::ImmutableSlice;
-        match r.bsearch(|&(lo, hi, _)| {
+        use core::slice;
+        match r.binary_search(|&(lo, hi, _)| {
             if lo <= c && c <= hi { Equal }
             else if hi < c { Less }
             else { Greater }
         }) {
-            Some(idx) => {
+            slice::Found(idx) => {
                 let (_, _, result) = r[idx];
                 result
             }
-            None => 0
+            slice::NotFound(_) => 0
         }
     }
 
@@ -6357,6 +6356,7 @@ pub mod conversions {
     use core::slice::ImmutableSlice;
     use core::tuple::Tuple2;
     use core::option::{Option, Some, None};
+    use core::slice;
 
     pub fn to_lower(c: char) -> char {
         match bsearch_case_table(c, LuLl_table) {
@@ -6373,11 +6373,14 @@ pub mod conversions {
     }
 
     fn bsearch_case_table(c: char, table: &'static [(char, char)]) -> Option<uint> {
-        table.bsearch(|&(key, _)| {
+        match table.binary_search(|&(key, _)| {
             if c == key { Equal }
             else if key < c { Less }
             else { Greater }
-        })
+        }) {
+            slice::Found(i) => Some(i),
+            slice::NotFound(_) => None,
+        }
     }
 
     static LuLl_table: &'static [(char, char)] = &[
@@ -6916,19 +6919,20 @@ pub mod conversions {
 pub mod charwidth {
     use core::option::{Option, Some, None};
     use core::slice::ImmutableSlice;
+    use core::slice;
 
     fn bsearch_range_value_table(c: char, is_cjk: bool, r: &'static [(char, char, u8, u8)]) -> u8 {
         use core::cmp::{Equal, Less, Greater};
-        match r.bsearch(|&(lo, hi, _, _)| {
+        match r.binary_search(|&(lo, hi, _, _)| {
             if lo <= c && c <= hi { Equal }
             else if hi < c { Less }
             else { Greater }
         }) {
-            Some(idx) => {
+            slice::Found(idx) => {
                 let (_, _, r_ncjk, r_cjk) = r[idx];
                 if is_cjk { r_cjk } else { r_ncjk }
             }
-            None => 1
+            slice::NotFound(_) => 1
         }
     }
 
@@ -7112,8 +7116,8 @@ pub mod charwidth {
 }
 
 pub mod grapheme {
-    use core::option::{Some, None};
     use core::slice::ImmutableSlice;
+    use core::slice;
 
     #[allow(non_camel_case_types)]
     #[deriving(Clone)]
@@ -7132,16 +7136,16 @@ pub mod grapheme {
 
     fn bsearch_range_value_table(c: char, r: &'static [(char, char, GraphemeCat)]) -> GraphemeCat {
         use core::cmp::{Equal, Less, Greater};
-        match r.bsearch(|&(lo, hi, _)| {
+        match r.binary_search(|&(lo, hi, _)| {
             if lo <= c && c <= hi { Equal }
             else if hi < c { Less }
             else { Greater }
         }) {
-            Some(idx) => {
+            slice::Found(idx) => {
                 let (_, _, cat) = r[idx];
                 cat
             }
-            None => GC_Any
+            slice::NotFound(_) => GC_Any
         }
     }