--- a/src/lib.rs	Fri Jul 08 18:19:38 2022 -0700
+++ b/src/lib.rs	Fri Jul 08 22:54:30 2022 -0700
@@ -2,7 +2,7 @@
 use std::cmp::Ordering;
 
 // Min. order: 3
-const ORDER: usize = 20;
+const ORDER: usize = 5;
 
 #[derive(Debug)]
 struct Node<T> {
@@ -356,11 +356,261 @@
         }
     }
 
-
     pub fn delete(&mut self, entry: &T) -> Option<T> {
         match self.find_from(self.root, entry) {
             None => None,
-            Some((_, node, nodeentry)) => Some(self.delete_entry(node, nodeentry))
+            Some((_, node, nodeentry)) => self.delete_recursive(self.root, Some(entry), None),
+        }
+    }
+
+    fn delete_recursive(
+        &mut self,
+        from: usize,
+        entry: Option<&T>,
+        mut entryix: Option<usize>,
+    ) -> Option<T> {
+        let mut deleted = None;
+        println!("deleting in {}", from);
+
+        if entryix.is_none() {
+            let entry = entry.unwrap();
+            // If we don't know the index of the entry to delete:
+            // First, iterate through this node's elements and delete recursively if needed.
+            for i in 0..ORDER - 1 {
+                if let Some(current) = self.get(from, i) {
+                    println!("comparing {:?}, {:?}", entry, current);
+                    match Cmp::cmp(entry, current) {
+                        Ordering::Less => {
+                            if let Some(ch) = self.get_child(from, i) {
+                                deleted = self
+                                    .delete_recursive(*ch, Some(entry), None)
+                                    .map(|e| (e, i));
+                                break;
+                            } else {
+                                continue;
+                            }
+                        }
+                        Ordering::Equal => {
+                            // found!
+                            entryix = Some(i);
+                            break;
+                        }
+                        Ordering::Greater => {
+                            if i == self.count_in(from) - 1 {
+                                if let Some(ch) = self.get_child(from, i + 1) {
+                                    // Descend into child-after-last entry
+                                    deleted = self
+                                        .delete_recursive(*ch, Some(entry), None)
+                                        .map(|e| (e, i + 1));
+                                    break;
+                                }
+                            } else {
+                                continue;
+                            }
+                        }
+                    }
+                } else {
+                    break;
+                }
+            }
+        }
+
+        // Distinguish cases:
+        // 1. Current node has entry to delete.
+        // 2. Deletion occured in some subnode. Check immediate children if rebalancing is needed.
+
+        println!("Back in {}", from);
+        println!("Found {:?} , {:?}", entryix, deleted);
+        if let Some(entryix) = entryix {
+            // 1. Current node has entry to be deleted.
+            //
+            if self.is_leaf(from) {
+                // If we're in a leaf, simple deletion is ok.
+                let d = self.get_mut(from, entryix).take();
+                for i in entryix..ORDER - 2 {
+                    *self.get_mut(from, i) = self.get_mut(from, i + 1).take();
+                }
+                return d;
+            } else {
+                // Non-leaf: need to rotate or merge.
+                let leftchild = self.get_child(from, entryix).unwrap();
+                let rightchild = self.get_child(from, entryix + 1).unwrap();
+                let leftcount = self.count_in(leftchild);
+                let rightcount = self.count_in(rightchild);
+
+                let d = self.get_mut(from, entryix).take();
+
+                // Enough entries in children.
+                if leftcount + rightcount > ORDER - 1 {
+                    let lefttoright = leftcount > rightcount;
+                    if lefttoright {
+                        // Remove last element from left node, recursively.
+                        let formerleft = self.delete_recursive(
+                            leftchild,
+                            None,
+                            Some(self.count_in(leftchild) - 1),
+                        );
+                        *self.get_mut(from, entryix) = formerleft;
+                    } else {
+                        // right to left
+                        let formerright = self.delete_recursive(rightchild, None, Some(0));
+                        *self.get_mut(from, entryix) = formerright;
+                    }
+                    return d;
+                } else {
+                    // Need to merge both children; discard entry-to-be-deleted
+                    let newnodeix = self.merge_nodes(from, entryix, /* discard= */ true);
+                    if from == self.root && self.count_in(self.root) == 0 {
+                        self.root = newnodeix;
+                    }
+                    return d;
+                }
+            }
+        } else if let Some((d, child)) = deleted {
+            // Entry was deleted in sub-operation.
+            // Check if invariants fulfilled.
+            if self.count_in(child) >= ORDER / 2 {
+                return Some(d);
+            } else {
+                // Child doesn't have enough entries. Attempt rotation or merge.
+
+                // Can rotate?
+                let leftchild;
+                let rightchild;
+                let entryix;
+                if child < ORDER - 1 {
+                    if child < self.count_in(from) {
+                        leftchild = self.get_child(from, child).unwrap();
+                        rightchild = self.get_child(from, child + 1).unwrap();
+                        entryix = child;
+                    } else {
+                        leftchild = self.get_child(from, child - 1).unwrap();
+                        rightchild = self.get_child(from, child).unwrap();
+                        entryix = child - 1;
+                    }
+                } else {
+                    // If child is right-most child.
+                    leftchild = self.get_child(from, child - 1).unwrap();
+                    rightchild = self.get_child(from, child).unwrap();
+                    entryix = child - 1;
+                }
+                let leftcount = self.count_in(leftchild);
+                let rightcount = self.count_in(rightchild);
+
+                // Enough entries in children to rotate.
+                if leftcount + rightcount + 1 > ORDER - 1 {
+                    let piv = self.get_mut(from, entryix).take();
+                    let lefttoright = leftcount > rightcount;
+                    if lefttoright {
+                        // Remove last element from left node, recursively.
+                        let formerleft = self.delete_recursive(
+                            leftchild,
+                            None,
+                            Some(self.count_in(leftchild) - 1),
+                        );
+                        self.insert_into(rightchild, piv.unwrap());
+                        *self.get_mut(from, entryix) = formerleft;
+                    } else {
+                        // right to left
+                        let formerright = self.delete_recursive(rightchild, None, Some(0));
+                        self.insert_into(leftchild, piv.unwrap());
+                        *self.get_mut(from, entryix) = formerright;
+                    }
+                } else {
+                    // Need to merge both children; do not discard pivot entry (entry between
+                    // children to be merged).
+                    let newnodeix;
+                    if child < ORDER - 1 && child < self.count_in(from) {
+                        newnodeix = self.merge_nodes(from, child, /* discard= */ false);
+                    } else {
+                        newnodeix = self.merge_nodes(from, child - 1, false);
+                    }
+                    if from == self.root && self.count_in(self.root) == 0 {
+                        self.root = newnodeix;
+                    }
+                }
+                return Some(d);
+            }
+        } else {
+            unimplemented!();
+        }
+    }
+
+    fn merge_nodes(&mut self, parent: usize, parentix: usize, discard: bool) -> usize {
+        let mut newnode = Node::new();
+        let mut count = 0;
+
+        println!("merging nodes at {} with child {}", parent, parentix);
+        // Move elements.
+        let left = self.get_child(parent, parentix).unwrap();
+        // Move left elements first.
+        for i in 0..ORDER - 1 {
+            newnode.entries[i] = self.get_mut(left, i).take();
+            newnode.children[i] = self.get_child_mut(left, i).take();
+            if newnode.entries[i].is_none() {
+                break;
+            }
+            count += 1;
+        }
+        // Copy left node's rightmost child
+        newnode.children[count+1] = self.get_child_mut(left, count+1).take();
+        // Move old pivot eleement.
+        if !discard {
+            newnode.entries[count] = self.get_mut(parent, parentix).take();
+            count += 1;
+        }
+        // Move right elements.
+        let right = *self.get_child(parent, parentix + 1);
+        println!("merge_nodes: right = {:?}", right);
+        let filled = count;
+        if let Some(right) = right {
+            for i in filled..ORDER - 1 {
+                newnode.entries[i] = self.get_mut(right, i - filled).take();
+                newnode.children[i] = self.get_child_mut(right, i-filled).take();
+                if newnode.entries[i].is_none() {
+                    break;
+                }
+                count += 1;
+            }
+            newnode.children[count] = self.get_child_mut(right, count-filled+1).take();
+        }
+
+        let newnodeix = self.v.len();
+        self.v.push(newnode);
+        *self.get_child_mut(parent, parentix) = Some(newnodeix);
+
+        // TODO!! Recycle nodes!!
+        for i in parentix..ORDER - 2 {
+            *self.get_mut(parent, i) = self.get_mut(parent, i + 1).take();
+            *self.get_child_mut(parent, i + 1) = self.get_child_mut(parent, i + 2).take();
+        }
+        newnodeix
+    }
+
+    fn rotate(&mut self, node: usize, ix: usize, lefttoright: bool) {
+        let leftchild = *self.get_child(node, ix);
+        let rightchild = *self.get_child(node, ix + 1);
+
+        if let (Some(leftchild), Some(rightchild)) = (leftchild, rightchild) {
+            let piv = self.get_mut(node, ix).take();
+            if lefttoright {
+                self.insert_into(rightchild, piv.unwrap());
+                *self.get_child_mut(rightchild, 0) = self.get_child_mut(leftchild, self.count_in(leftchild)).take();
+                // Remove last element from left node, recursively.
+                let formerleft =
+                    self.delete_recursive(leftchild, None, Some(self.count_in(leftchild) - 1));
+                *self.get_mut(node, ix) = formerleft;
+            } else {
+                // right to left
+                let formerright = self.delete_recursive(rightchild, None, Some(0));
+                self.insert_into(leftchild, piv.unwrap());
+                *self.get_mut(node, ix) = formerright;
+            }
+        } else {
+            panic!(
+                "Cannot rotate asymmetrically: {:?}",
+                (leftchild, rightchild)
+            );
         }
     }
 
@@ -369,8 +619,8 @@
         if self.is_leaf(node) {
             // Shift, and return.
             let d = self.get_mut(node, entry).take();
-            for i in entry..ORDER-1 {
-                *self.get_mut(node, i) = self.get_mut(node, i+1).take();
+            for i in entry..ORDER - 1 {
+                *self.get_mut(node, i) = self.get_mut(node, i + 1).take();
                 assert!(self.get_child(node, i).is_none());
                 if self.get(node, i).is_none() {
                     break;
@@ -384,18 +634,23 @@
             // Remove entry;
             // rotate left or right subtree element into place by removing it from there as well.
             let d = self.get_mut(node, entry).take();
-            let (left, right) = (self.v[node].children[entry], self.v[node].children[entry+1]);
+            let (left, right) = (
+                self.v[node].children[entry],
+                self.v[node].children[entry + 1],
+            );
             let (candidate, ix, need_restructure) = match (left, right) {
                 (Some(l), Some(r)) => {
                     let (leftcount, rightcount) = (self.count_in(l), self.count_in(r));
                     if leftcount <= rightcount {
-                        (r, 0, rightcount < ORDER/2)
+                        (r, 0, rightcount < ORDER / 2)
                     } else {
-                        (l, leftcount-1, leftcount < ORDER/2)
+                        (l, leftcount - 1, leftcount < ORDER / 2)
                     }
-                },
-                (Some(l), None) => (l, self.count_in(l)-1, self.count_in(l) < ORDER/2),
-                (None, Some(r)) => panic!("Tree architecture fault: no left subchild but right subchild"),
+                }
+                (Some(l), None) => (l, self.count_in(l) - 1, self.count_in(l) < ORDER / 2),
+                (None, Some(r)) => {
+                    panic!("Tree architecture fault: no left subchild but right subchild")
+                }
                 (None, None) => panic!("delete_entry in leaf node, but expected internal node"),
             };
 
@@ -407,7 +662,7 @@
                 // Can we rotate into place?
                 if let (Some(l), Some(r)) = (left, right) {
                     let (leftcount, rightcount) = (self.count_in(l), self.count_in(r));
-                    if leftcount+rightcount > ORDER {
+                    if leftcount + rightcount > ORDER {
                         // Yes!
                         let to_move = self.get_mut(node, entry).take().unwrap();
                         if leftcount < rightcount {
@@ -415,7 +670,7 @@
                             *self.get_mut(node, entry) = Some(self.delete_entry(r, 0));
                         } else {
                             self.insert_into(r, to_move);
-                            *self.get_mut(node, entry) = Some(self.delete_entry(l, leftcount-1));
+                            *self.get_mut(node, entry) = Some(self.delete_entry(l, leftcount - 1));
                         }
                     }
                 } else {
@@ -428,7 +683,7 @@
                     // Move elements.
                     let left = self.get_child(node, entry).unwrap();
                     // Move left elements first.
-                    for i in 0..ORDER-1 {
+                    for i in 0..ORDER - 1 {
                         newnode.entries[i] = self.get_mut(left, i).take();
                         count += 1;
                     }
@@ -436,10 +691,10 @@
                     newnode.entries[count] = self.get_mut(node, entry).take();
                     count += 1;
                     // Move right elements.
-                    let right = *self.get_child(node, entry+1);
+                    let right = *self.get_child(node, entry + 1);
                     if let Some(right) = right {
-                        for i in count..ORDER-1 {
-                            newnode.entries[i] = self.get_mut(right, i-count).take();
+                        for i in count..ORDER - 1 {
+                            newnode.entries[i] = self.get_mut(right, i - count).take();
                             count += 1;
                         }
                     }
@@ -449,9 +704,9 @@
                     *self.get_child_mut(node, entry) = Some(newnodeix);
 
                     // TODO!! Recycle nodes!!
-                    for i in entry..ORDER-2 {
-                        *self.get_mut(node, i) = self.get_mut(node, i+1).take();
-                        *self.get_child_mut(node, i+1) = self.get_child_mut(node, i+2).take();
+                    for i in entry..ORDER - 2 {
+                        *self.get_mut(node, i) = self.get_mut(node, i + 1).take();
+                        *self.get_child_mut(node, i + 1) = self.get_child_mut(node, i + 2).take();
                     }
                 }
             }
@@ -491,7 +746,7 @@
         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,
+            15, 2, 21, 35, 4, 62, 38, 27, 88, 1, 12, 45, 11, 16, 23, 20, 22, 24, 25, 26, 28, 29,
             30, 31, 32,
         ];
 
@@ -509,18 +764,17 @@
         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,
+            15, 2, 21, 35, 4, 62, 38, 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!("{}", bt.debug_print());
         for e in ns {
-            println!("deleting {}", e);
+            println!("\n\ndeleting {}", e);
             println!("{}", bt.debug_print());
-            bt.delete(e);
+            assert_eq!(bt.delete(e), Some(*e));
         }
     }
 
@@ -598,7 +852,7 @@
     #[test]
     fn test_binary_node_search() {
         let mut bt = BTree::new(10);
-        for i in 0..super::ORDER - 5 {
+        for i in 0..super::ORDER/2 {
             bt.insert(i);
         }
 
@@ -607,7 +861,7 @@
         for i in 0..super::ORDER - 1 {
             assert_eq!(
                 bt.binary_node_search(bt.root, &i),
-                std::cmp::min(i, super::ORDER - 5)
+                std::cmp::min(i, super::ORDER/2)
             );
         }
     }