--- a/.hgignore	Tue Jul 05 08:09:38 2022 -0700
+++ b/.hgignore	Tue Jul 05 09:40:05 2022 -0700
@@ -1,2 +1,4 @@
 ^target/
 ^Cargo.lock$
+^kcov-out
+callgrind.*

--- a/src/lib.rs	Tue Jul 05 08:09:38 2022 -0700
+++ b/src/lib.rs	Tue Jul 05 09:40:05 2022 -0700
@@ -19,20 +19,36 @@
     }
 }
 
+trait Compare<T> {
+    fn cmp(v1: &T, v2: &T) -> Ordering;
+}
+
+struct StandardCompare;
+
+impl<T: Ord> Compare<T> for StandardCompare {
+    fn cmp(v1: &T, v2: &T) -> Ordering {
+        v1.cmp(v2)
+    }
+}
+
 #[derive(Debug)]
-struct BTree<T> {
+struct BTree<T, Cmp: Compare<T>> {
     v: Vec<Node<T>>,
     root: usize,
+    cmp: std::marker::PhantomData<Cmp>,
 }
 
-impl<T: std::fmt::Debug + Ord> BTree<T> {
-    fn new(initial_capacity: usize) -> BTree<T> {
+impl<T: std::fmt::Debug + Ord> BTree<T, StandardCompare> {
+    fn new(initial_capacity: usize) -> BTree<T, StandardCompare> {
         BTree {
             v: Vec::with_capacity(initial_capacity),
             root: 0,
+            cmp: Default::default(),
         }
     }
+}
 
+impl<T: std::fmt::Debug + Ord, Cmp: Compare<T>> BTree<T, Cmp> {
     fn free(&self, node: usize) -> usize {
         self.v[node]
             .entries
@@ -73,14 +89,37 @@
         s
     }
 
-    fn find<'a>(&'a self, value: &T) -> &'a T {
-        panic!();
+    pub fn find<'a>(&'a self, value: &T) -> Option<&'a T> {
+        self.find_from(self.root, value)
     }
-    fn find_from<'a>(&'a self, node: usize, value: &T) -> &'a T {
+    fn find_from<'a>(&'a self, node: usize, value: &T) -> Option<&'a T> {
+        let mut j = 0;
+        // Break once we arrived at the entry right of the correct child, if we don't return
+        // earlier.
         for i in 0..ORDER {
-            if i < ORDER - 1 {}
+            if i < ORDER - 1 {
+                if let Some(el) = self.get(node, i) {
+                    match Cmp::cmp(value, el) {
+                        Ordering::Less => {
+                            j = i;
+                            break;
+                        }
+                        Ordering::Equal => return Some(el),
+                        Ordering::Greater => continue,
+                    }
+                } else {
+                    j = i;
+                    break;
+                }
+            } else {
+                j = i;
+                break;
+            }
         }
-        panic!();
+        if let Some(ch) = self.get_child(node, j) {
+            return self.find_from(*ch, value);
+        }
+        None
     }
 
     /// Insert a value into an existing node, preserving the order.
@@ -98,7 +137,7 @@
         let node = &mut self.v[node];
         for i in 0..ORDER - 1 {
             if let Some(ref el) = node.entries[i] {
-                if value.cmp(el) == Ordering::Less {
+                if Cmp::cmp(&value, el) == Ordering::Less {
                     // Found right location. Shift remaining elements.
                     loc = i;
                     break;
@@ -146,11 +185,13 @@
         (leftix, pivot.unwrap(), rightix)
     }
 
+    /// Returns true if the given node is a leaf (doesn't have children).
     fn is_leaf(&self, node: usize) -> bool {
         self.v[node].children.iter().all(|c| c.is_none())
     }
-    /// Insert & root splitting.
-    fn insert(&mut self, value: T) -> bool {
+
+    /// Insert a value into the BTree.
+    pub fn insert(&mut self, value: T) -> bool {
         if let Some((l, pivot, r)) = self.insert_into(self.root, value) {
             // Split root
             let mut newroot = Node::new();
@@ -181,26 +222,26 @@
             self.insert_inline(node, value, None, None);
             return None;
         } else if self.is_leaf(node) && self.free(node) < 1 {
-            // Leaf node but needs to be split.
+            // Leaf node but full - needs to be split.
             let (l, pivot, r) = self.split(node);
-            // Full leaf node?
 
             // Insert value into left or right subtree.
-            match value.cmp(&pivot) {
+            match Cmp::cmp(&value, &pivot) {
                 Ordering::Less => assert!(self.insert_into(l, value).is_none()),
                 Ordering::Greater => assert!(self.insert_into(r, value).is_none()),
                 _ => panic!("Attempting to insert duplicate element"),
             };
+            // Return fragments upwards to be inserted.
             return Some((l, pivot, r));
         } else {
             // Descend into node.
 
             let mut split = None;
-            // Find correct child.
+            // Find correct child to descend into.
             for i in 0..ORDER {
                 if i < ORDER - 1 {
                     if let Some(el) = self.get(node, i) {
-                        match value.cmp(el) {
+                        match Cmp::cmp(&value, el) {
                             Ordering::Less => {
                                 split = self.insert_into(self.get_child(node, i).unwrap(), value);
                                 break;
@@ -228,7 +269,7 @@
                         let (l, pivot, r) = self.split(node);
 
                         // Insert value into left or right subtree.
-                        match value.cmp(&pivot) {
+                        match Cmp::cmp(&value, &pivot) {
                             Ordering::Less => assert!(self.insert_into(l, value).is_none()),
                             Ordering::Greater => assert!(self.insert_into(r, value).is_none()),
                             _ => panic!("Attempting to insert duplicate element"),
@@ -261,7 +302,7 @@
         }
     }
 }
-impl<T: std::fmt::Debug> BTree<T> {
+impl<T: std::fmt::Debug, Cmp: Compare<T>> BTree<T, Cmp> {
     fn debug_print(&self) -> String {
         let mut t = TreeBuilder::new(format!("<{}>", self.root));
         self.print_subtree(&mut t, self.root);
@@ -289,7 +330,7 @@
     use rand::{rngs::StdRng, RngCore, SeedableRng};
     #[test]
     fn basic_test() {
-        let mut bt = BTree::<i32>::new(16);
+        let mut bt = BTree::new(16);
 
         let ns = &[
             15, 2, 21, 35, 4, 62, 31, 27, 88, 1, 12, 45, 11, 16, 23, 20, 22, 24, 25, 26, 28, 29,
@@ -311,7 +352,7 @@
         for seed in &[1, 2, 3, 4, 5, 6, 7, 8, 9, 10] {
             let mut rng = StdRng::seed_from_u64(*seed);
             let N = 1000;
-            let mut bt = BTree::<u32>::new(N / 2);
+            let mut bt = BTree::new(N / 2);
             for i in 0..N {
                 let rn = rng.next_u32();
                 bt.insert(rn);
@@ -321,6 +362,43 @@
                 }
                 assert_eq!(i + 1, bt.count());
             }
+            println!("{}", bt.debug_print());
+        }
+    }
+
+    #[test]
+    fn test_find() {
+        time_test::time_test!("1000 x insert/find");
+        let mut rng = StdRng::seed_from_u64(1);
+        let N = 1000;
+        let mut items = Vec::with_capacity(N);
+        let mut bt = BTree::new(N / 3);
+        for i in 0..N {
+            let rn = rng.next_u32();
+            bt.insert(rn);
+            items.push(rn);
+
+            for rn in items.iter() {
+                assert_eq!(bt.find(rn), Some(rn));
+            }
+        }
+
+        for (i, rn) in items.iter().enumerate() {
+            assert_eq!(bt.find(rn), Some(rn));
+        }
+    }
+
+    #[test]
+    fn test_find_sequential() {
+        time_test::time_test!("1000 x insert/find sequential");
+        let N = 1000;
+        let mut bt = BTree::new(N / 3);
+        for i in 0..N {
+            bt.insert(i);
+        }
+
+        for i in 0..N {
+            assert_eq!(bt.find(&i), Some(&i));
         }
     }