Add some binary search methods and tests for to servo::util::vec.

3 files changed, 107 insertions, 1 deletions

diff --git a/src/servo/servo.rc b/src/servo/servo.rc
index 7eb861d4284..2a6f77ff202 100755
--- a/src/servo/servo.rc
+++ b/src/servo/servo.rc
@@ -130,12 +130,14 @@ mod resource {
 }
 
 mod util {
-    mod tree;
     mod color;
     mod time;
+    mod tree;
     mod url;
+    mod vec;
 }
 
 mod opts;
 
+use servo_util = util;
 use servo_text = text;
diff --git a/src/servo/util/tree.rs b/src/servo/util/tree.rs
index 612834e61b6..031b4a98042 100644
--- a/src/servo/util/tree.rs
+++ b/src/servo/util/tree.rs
@@ -1,3 +1,5 @@
+use core::vec;
+
 // A generic tree datatype.
 //
 // TODO: Use traits.
diff --git a/src/servo/util/vec.rs b/src/servo/util/vec.rs
new file mode 100644
index 00000000000..1d476ab2420
--- /dev/null
+++ b/src/servo/util/vec.rs
@@ -0,0 +1,102 @@
+use core::cmp::{Ord, Eq};
+
+export BinarySearchMethods, binary_search, binary_search_index;
+
+trait BinarySearchMethods<T: Ord Eq> {
+    pure fn binary_search(&self, key: &T) -> Option<&self/T>;
+    pure fn binary_search_index(&self, key: &T) -> Option<uint>;
+}
+
+impl<T: Ord Eq> &[T]: BinarySearchMethods<T> {
+    pure fn binary_search(&self, key: &T) -> Option<&self/T> {
+        match self.binary_search_index(key) {
+            None => None,
+            Some(i) => Some(&self[i])
+        }
+    }
+
+    pure fn binary_search_index(&self, key: &T) -> Option<uint> {
+        if self.len() == 0 {
+            return None;
+        }
+
+        let mut low : int = 0;
+        let mut high : int = (self.len() as int) - 1;
+
+        while (low <= high) {
+            // http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html
+            let mid : int = (((low as uint) + (high as uint)) >> 1) as int;
+            let midv = &self[mid];
+
+            if (midv < key) {
+                low = mid + 1;
+            } else if (midv > key) {
+                high = mid - 1;
+            } else {
+                return Some(mid as uint);
+            }
+        }
+        return None;
+    }
+}
+
+fn test_find_all_elems<T: Eq Ord>(arr: &[T]) {
+    let mut i = 0;
+    while i < arr.len() {
+        assert test_match(&arr[i], arr.binary_search(&arr[i]));
+        i += 1;
+    }
+}
+
+fn test_miss_all_elems<T: Eq Ord>(arr: &[T], misses: &[T]) {
+    let mut i = 0;
+    while i < misses.len() {
+        let res = arr.binary_search(&misses[i]);
+        debug!("%? == %? ?", misses[i], res);
+        assert !test_match(&misses[i], arr.binary_search(&misses[i]));
+        i += 1;
+    }
+}
+
+fn test_match<T: Eq>(b: &T, a: Option<&T>) -> bool {
+    match a {
+        None => false,
+        Some(t) => t == b
+    }
+} 
+
+fn should_find_all_elements() {
+    #[test];
+
+    let arr_odd = [1, 2, 4, 6, 7, 8, 9];
+    let arr_even = [1, 2, 5, 6, 7, 8, 9, 42];
+    let arr_double = [1, 1, 2, 2, 6, 8, 22];
+    let arr_one = [234986325];
+    let arr_two = [3044, 8393];
+    let arr_three = [12, 23, 34];
+
+    test_find_all_elems(arr_odd);
+    test_find_all_elems(arr_even);
+    test_find_all_elems(arr_double);
+    test_find_all_elems(arr_one);
+    test_find_all_elems(arr_two);
+    test_find_all_elems(arr_three);
+}
+
+fn should_not_find_missing_elements() {
+    #[test];
+
+    let arr_odd = [1, 2, 4, 6, 7, 8, 9];
+    let arr_even = [1, 2, 5, 6, 7, 8, 9, 42];
+    let arr_double = [1, 1, 2, 2, 6, 8, 22];
+    let arr_one = [234986325];
+    let arr_two = [3044, 8393];
+    let arr_three = [12, 23, 34];
+
+    test_miss_all_elems(arr_odd, [-22, 0, 3, 5, 34938, 10, 11, 12]);
+    test_miss_all_elems(arr_even, [-1, 0, 3, 34938, 10, 11, 12]);
+    test_miss_all_elems(arr_double, [-1, 0, 3, 4, 34938, 10, 11, 12, 234, 234, 33]);
+    test_miss_all_elems(arr_one, [-1, 0, 3, 34938, 10, 11, 12, 234, 234, 33]);
+    test_miss_all_elems(arr_two, [-1, 0, 3, 34938, 10, 11, 12, 234, 234, 33]);
+    test_miss_all_elems(arr_three, [-2, 0, 1, 2, 3, 34938, 10, 11, 234, 234, 33]);
+}