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.

2 files changed, 27 insertions, 22 deletions

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
         }
     }