--- a/Cargo.toml	Tue Jul 05 07:08:06 2022 -0700
+++ b/Cargo.toml	Tue Jul 05 08:09:38 2022 -0700
@@ -7,3 +7,5 @@
 
 [dependencies]
 ptree = "0.4"
+rand = "0.8.5"
+time-test = "0.2.3"

--- a/src/lib.rs	Tue Jul 05 07:08:06 2022 -0700
+++ b/src/lib.rs	Tue Jul 05 08:09:38 2022 -0700
@@ -2,21 +2,19 @@
 use std::cmp::Ordering;
 
 // Min. order: 3
-const ORDER: usize = 4;
+const ORDER: usize = 5;
 
 #[derive(Debug)]
 struct Node<T> {
     entries: [Option<T>; ORDER - 1],
     children: [Option<usize>; ORDER],
-    parent: Option<usize>,
 }
 
 impl<T: Ord> Node<T> {
-    fn new(parent: Option<usize>) -> Node<T> {
+    fn new() -> Node<T> {
         Node {
             entries: Default::default(),
             children: Default::default(),
-            parent: parent,
         }
     }
 }
@@ -42,6 +40,13 @@
             .map(|e| if e.is_some() { 0 } else { 1 })
             .sum()
     }
+    fn occupied(&self, node: usize) -> usize {
+        self.v[node]
+            .entries
+            .iter()
+            .map(|e| if e.is_some() { 1 } else { 0 })
+            .sum()
+    }
     fn get(&self, node: usize, elem: usize) -> &Option<T> {
         &self.v[node].entries[elem]
     }
@@ -55,6 +60,29 @@
         &mut self.v[node].children[child]
     }
 
+    fn count(&self) -> usize {
+        self.count_from(self.root)
+    }
+    fn count_from(&self, node: usize) -> usize {
+        let mut s = self.occupied(node);
+        for i in 0..ORDER {
+            if let Some(ch) = self.v[node].children[i] {
+                s += self.count_from(ch);
+            }
+        }
+        s
+    }
+
+    fn find<'a>(&'a self, value: &T) -> &'a T {
+        panic!();
+    }
+    fn find_from<'a>(&'a self, node: usize, value: &T) -> &'a T {
+        for i in 0..ORDER {
+            if i < ORDER - 1 {}
+        }
+        panic!();
+    }
+
     /// Insert a value into an existing node, preserving the order.
     /// Requires that at least one slot be free.
     fn insert_inline(
@@ -65,8 +93,6 @@
         right: Option<usize>,
     ) -> usize {
         assert!(self.free(node) >= 1);
-        let nodeix = node;
-
         let mut loc = ORDER - 2;
 
         let node = &mut self.v[node];
@@ -91,26 +117,17 @@
         node.children[loc] = left;
         node.children[loc + 1] = right;
 
-        if let Some(left) = left {
-            self.v[left].parent = Some(nodeix)
-        }
-        if let Some(right) = right {
-            self.v[right].parent = Some(nodeix);
-        }
         loc
     }
 
     /// Split a node, returning the IDs of the two new nodes and the pivot value.
-    /// Parent pointers need to be updated by caller.
     fn split(&mut self, node: usize) -> (usize, T, usize) {
         assert!(self.free(node) <= 1);
         // `node` will become left node.
         let leftix = node;
         let rightix = self.v.len();
 
-        println!("Starting split: {:?}", self.v[node]);
-
-        let mut right = Node::<T>::new(None); // Parent updated by caller!
+        let mut right = Node::<T>::new();
 
         let pivotix = (ORDER - 1) / 2;
         let pivot = self.get_mut(node, pivotix).take();
@@ -126,45 +143,22 @@
         }
 
         self.v.push(right);
-        println!(
-            "Finishing split: left {:?} right {:?} pivot {:?}",
-            self.v[leftix], self.v[rightix], pivot
-        );
         (leftix, pivot.unwrap(), rightix)
     }
 
     fn is_leaf(&self, node: usize) -> bool {
         self.v[node].children.iter().all(|c| c.is_none())
     }
-    fn update_right_child(&mut self, node: usize, ch: usize) {
-        for i in 0..ORDER - 1 {
-            if self.get(node, i).is_none() {
-                if let Some(subch) = self.get_child(node, i) {
-                    self.update_right_child(*subch, ch);
-                    return;
-                } else {
-                    *self.get_child_mut(node, i) = Some(ch);
-                    return;
-                }
-            }
-        }
-        // This means that even the last child slot was used so far.
-        self.update_right_child(self.get_child(node, ORDER - 1).unwrap(), ch);
-    }
-
     /// Insert & root splitting.
     fn insert(&mut self, value: T) -> bool {
         if let Some((l, pivot, r)) = self.insert_into(self.root, value) {
             // Split root
-            println!("Splitting root with new children {}, {}", l, r);
-            let mut newroot = Node::new(None);
+            let mut newroot = Node::new();
             let rootix = self.v.len();
             newroot.children[0] = Some(l);
             newroot.children[1] = Some(r);
             newroot.entries[0] = Some(pivot);
 
-            self.v[l].parent = Some(rootix);
-            self.v[r].parent = Some(rootix);
             self.root = rootix;
 
             self.v.push(newroot);
@@ -178,21 +172,18 @@
     fn insert_into(&mut self, node: usize, value: T) -> Option<(usize, T, usize)> {
         // BTree initialized?
         if self.v.len() == 0 {
-            println!("Initializing");
-            self.v.push(Node::new(None));
+            self.v.push(Node::new());
             self.insert_inline(self.root, value, None, None);
             return None;
         }
         // Leaf node with free space? We are finished.
         if self.is_leaf(node) && self.free(node) >= 1 {
-            println!("Leaf {} with free space", node);
             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.
             let (l, pivot, r) = self.split(node);
             // Full leaf node?
-            println!("Splitting leaf {} into {} {:?} {}", node, l, pivot, r);
 
             // Insert value into left or right subtree.
             match value.cmp(&pivot) {
@@ -203,16 +194,21 @@
             return Some((l, pivot, r));
         } else {
             // Descend into node.
-            println!("Scanning node {}", node);
 
             let mut split = None;
             // Find correct child.
-            for i in 0..ORDER - 1 {
-                if i < ORDER - 2 {
+            for i in 0..ORDER {
+                if i < ORDER - 1 {
                     if let Some(el) = self.get(node, i) {
-                        if value.cmp(el) == Ordering::Less {
-                            split = self.insert_into(self.get_child(node, i).unwrap(), value);
-                            break;
+                        match value.cmp(el) {
+                            Ordering::Less => {
+                                split = self.insert_into(self.get_child(node, i).unwrap(), value);
+                                break;
+                            }
+                            Ordering::Equal => {
+                                panic!("Attempting to insert duplicate element {:?}", value)
+                            }
+                            Ordering::Greater => continue,
                         }
                     } else {
                         if let Some(ch) = self.get_child(node, i) {
@@ -243,7 +239,6 @@
                 }
             }
 
-            println!("Split necessary? {:?}", split);
             // Merge split if one happened below us.
             if let Some((l, pivot, r)) = split {
                 if self.free(node) >= 1 {
@@ -291,20 +286,56 @@
 #[cfg(test)]
 mod tests {
     use super::BTree;
+    use rand::{rngs::StdRng, RngCore, SeedableRng};
     #[test]
     fn basic_test() {
         let mut bt = BTree::<i32>::new(16);
 
-        let ns = &[15, 2, 21, 35, 4, 62, 31, 27, 88, 1, 12, 45, 11, 16, 23];
+        let ns = &[
+            15, 2, 21, 35, 4, 62, 31, 27, 88, 1, 12, 45, 11, 16, 23, 20, 22, 24, 25, 26, 28, 29,
+            30, 31, 32,
+        ];
 
         for n in ns {
             bt.insert(*n);
-            println!("Inserting {}", n);
-            println!("root: {}", bt.root);
-            println!("{}", bt.debug_print());
         }
         for (i, e) in bt.v.iter().enumerate() {
             println!("{} {:?}", i, e);
         }
+        assert_eq!(bt.count(), ns.len());
+    }
+
+    #[test]
+    fn randomized_all_reachable() {
+        time_test::time_test!("10 x 100 inserts");
+        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);
+            for i in 0..N {
+                let rn = rng.next_u32();
+                bt.insert(rn);
+                if i + 1 != bt.count() {
+                    println!("inserting {}", rn);
+                    println!("seed = {}\n{}", seed, bt.debug_print());
+                }
+                assert_eq!(i + 1, bt.count());
+            }
+        }
+    }
+
+    #[test]
+    fn randomized_stdbtree_test() {
+        time_test::time_test!("10 x 100 inserts");
+        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 = std::collections::BTreeSet::new();
+            for i in 0..N {
+                let rn = rng.next_u32();
+                bt.insert(rn);
+                assert_eq!(i + 1, bt.len());
+            }
+        }
     }
 }