use ptree::TreeBuilder;
use std::cmp::Ordering;

// Min. order: 3
const ORDER: usize = 5;

#[derive(Debug)]
struct Node<T> {
    entries: [Option<T>; ORDER - 1],
    children: [Option<usize>; ORDER],
}

impl<T: Ord> Node<T> {
    fn new() -> Node<T> {
        Node {
            entries: Default::default(),
            children: Default::default(),
        }
    }
}

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, Cmp: Compare<T>> {
    v: Vec<Node<T>>,
    root: usize,
    cmp: std::marker::PhantomData<Cmp>,
}

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
            .iter()
            .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]
    }
    fn get_mut(&mut self, node: usize, elem: usize) -> &mut Option<T> {
        &mut self.v[node].entries[elem]
    }
    fn get_child(&self, node: usize, child: usize) -> &Option<usize> {
        &self.v[node].children[child]
    }
    fn get_child_mut(&mut self, node: usize, child: usize) -> &mut Option<usize> {
        &mut self.v[node].children[child]
    }

    fn count(&self) -> usize {
        self.count_from(self.root)
    }
    fn count_in(&self, node: usize) -> usize {
        self.v[node].entries.iter().filter(|e| e.is_some()).count()
    }
    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
    }

    pub fn find<'a>(&'a self, value: &T) -> Option<&'a T> {
        self.find_from(self.root, value).map(|e| e.0)
    }
    // Returns reference to value if found, and node/entry indices.
    fn find_from<'a>(&'a self, node: usize, value: &T) -> Option<(&'a T, usize, usize)> {
        let mut j = 0;
        // Break once we arrived at the entry right of the correct child, if we don't return
        // earlier.

        if false {
            // Comment this in if binary search within nodes makes sense. Usually it takes longer than a contiguous scan.
            j = self.binary_node_search(node, value);
            if j < ORDER - 1 {
                if let Some(el) = self.get(node, j) {
                    if Cmp::cmp(value, el) == Ordering::Equal {
                        return Some((el, node, j));
                    }
                }
            }
        } else {
            for i in 0..ORDER {
                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, node, i)),
                            Ordering::Greater => continue,
                        }
                    } else {
                        j = i;
                        break;
                    }
                } else {
                    j = i;
                    break;
                }
            }
        }
        if let Some(ch) = self.get_child(node, j) {
            return self.find_from(*ch, value);
        }
        None
    }

    // Find equal or next-greater element in node array.
    fn binary_node_search(&self, node: usize, value: &T) -> usize {
        let mut lo = 0;
        let mut hi = ORDER - 2 - self.free(node);
        let mut mid = hi / 2;

        while lo < hi {
            if let Some(el) = self.get(node, mid) {
                match Cmp::cmp(value, el) {
                    Ordering::Less => {
                        hi = mid;
                        mid = lo + (hi - lo) / 2;
                        continue;
                    }
                    Ordering::Equal => return mid,
                    Ordering::Greater => {
                        lo = mid + 1; // We already know that mid cannot be a potential result; skip it.
                        mid = lo + (hi - lo) / 2;
                        continue;
                    }
                }
            } else {
                // This shouldn't occur in a contiguous node.
                unimplemented!();
            }
        }
        if let Some(el) = self.get(node, lo) {
            if Ordering::Greater == Cmp::cmp(value, el) {
                return lo + 1;
            }
        }
        return lo;
    }

    /// Insert a value into an existing node, preserving the order.
    /// Requires that at least one slot be free.
    fn insert_inline(
        &mut self,
        node: usize,
        value: T,
        left: Option<usize>,
        right: Option<usize>,
    ) -> usize {
        assert!(self.free(node) >= 1);
        let mut loc = ORDER - 2;

        let node = &mut self.v[node];
        for i in 0..ORDER - 1 {
            if let Some(ref el) = node.entries[i] {
                if Cmp::cmp(&value, el) == Ordering::Less {
                    // Found right location. Shift remaining elements.
                    loc = i;
                    break;
                }
            } else {
                loc = i;
                break;
            }
        }

        for i in 0..(ORDER - 2 - loc) {
            node.entries[ORDER - 2 - i] = node.entries[ORDER - 3 - i].take();
            node.children[ORDER - 1 - i] = node.children[ORDER - 2 - i].take();
        }
        node.entries[loc] = Some(value);
        node.children[loc] = left;
        node.children[loc + 1] = right;

        loc
    }

    /// Split a node, returning the IDs of the two new nodes and the pivot value.
    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();

        let mut right = Node::<T>::new();

        let pivotix = (ORDER - 1) / 2;
        let pivot = self.get_mut(node, pivotix).take();

        // Pivot-left child remains in left node.
        for i in pivotix + 1..ORDER {
            right.children[i - pivotix - 1] = self.get_child_mut(leftix, i).take();
        }
        // Make sure to move all children pointers!
        //right.children[ORDER - pivotix] = self.get_child_mut(leftix, ORDER - 1).take();
        for i in pivotix + 1..ORDER - 1 {
            right.entries[i - pivotix - 1] = self.get_mut(leftix, i).take();
        }

        self.v.push(right);
        (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 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();
            let rootix = self.v.len();
            newroot.children[0] = Some(l);
            newroot.children[1] = Some(r);
            newroot.entries[0] = Some(pivot);

            self.root = rootix;

            self.v.push(newroot);
            true
        } else {
            true
        }
    }

    /// Insert value recursively. If a split occurs, returns (left, pivot, right) tuple.
    fn insert_into(&mut self, node: usize, value: T) -> Option<(usize, T, usize)> {
        // BTree initialized?
        if self.v.len() == 0 {
            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 {
            self.insert_inline(node, value, None, None);
            return None;
        } else if self.is_leaf(node) && self.free(node) < 1 {
            // Leaf node but full - needs to be split.
            let (l, pivot, r) = self.split(node);

            // Insert value into left or right subtree.
            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 to descend into.
            for i in 0..ORDER {
                if i < ORDER - 1 {
                    if let Some(el) = self.get(node, i) {
                        match Cmp::cmp(&value, 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) {
                            split = self.insert_into(*ch, value);
                            break;
                        }
                        panic!(
                            "Internal node missing child? {} => {:?}",
                            node, self.v[node]
                        );
                    }
                } else {
                    if let Some(ch) = self.get_child(node, i) {
                        split = self.insert_into(*ch, value);
                        break;
                    } else {
                        // This code is dead. Protect it, later remove it:
                        panic!("This code should not be used");

                        let (l, pivot, r) = self.split(node);

                        // Insert value into left or right subtree.
                        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 Some((l, pivot, r));
                    }
                }
            }

            // Merge split if one happened below us.
            if let Some((l, pivot, r)) = split {
                if self.free(node) >= 1 {
                    // We can insert the split here.
                    self.insert_inline(node, pivot, Some(l), Some(r));
                    return None;
                } else {
                    // Split this node too.
                    let (nl, npivot, nr) = self.split(node);
                    match pivot.cmp(&npivot) {
                        Ordering::Less => self.insert_inline(nl, pivot, Some(l), Some(r)),
                        Ordering::Greater => self.insert_inline(nr, pivot, Some(l), Some(r)),
                        _ => panic!("Attempting to insert duplicate element"),
                    };
                    return Some((nl, npivot, nr));
                }
            } else {
                return None;
            }
        }
    }

    pub fn delete(&mut self, entry: &T) -> Option<T> {
        match self.find_from(self.root, entry) {
            None => None,
            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)
            );
        }
    }

    fn delete_entry(&mut self, node: usize, entry: usize) -> T {
        // Entry must exist!!
        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();
                assert!(self.get_child(node, i).is_none());
                if self.get(node, i).is_none() {
                    break;
                }
            }
            // TO DO: rotate or merge. Need access to parent!
            assert!(self.get_child(node, self.count_in(node)).is_none());
            return d.unwrap();
        } else {
            // Non-leaf.
            // 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 (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)
                    } else {
                        (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")
                }
                (None, None) => panic!("delete_entry in leaf node, but expected internal node"),
            };

            // Recurse into subtree.
            *self.get_mut(node, entry) = Some(self.delete_entry(candidate, ix));

            // Merge nodes if either node is too small.
            if need_restructure {
                // 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 {
                        // Yes!
                        let to_move = self.get_mut(node, entry).take().unwrap();
                        if leftcount < rightcount {
                            self.insert_into(l, to_move);
                            *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));
                        }
                    }
                } else {
                    // Need to merge two nodes.
                    // Remove current entry and add it to a new node, together with left and right
                    // nodes' entries.
                    let mut newnode = Node::new();
                    let mut count = 0;

                    // Move elements.
                    let left = self.get_child(node, entry).unwrap();
                    // Move left elements first.
                    for i in 0..ORDER - 1 {
                        newnode.entries[i] = self.get_mut(left, i).take();
                        count += 1;
                    }
                    // Move old pivot eleement.
                    newnode.entries[count] = self.get_mut(node, entry).take();
                    count += 1;
                    // Move right elements.
                    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();
                            count += 1;
                        }
                    }

                    let newnodeix = self.v.len();
                    self.v.push(newnode);
                    *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();
                    }
                }
            }

            return d.unwrap();
        }
    }
}
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);
        let mut o: Vec<u8> = Vec::new();
        ptree::write_tree(&t.build(), &mut o);
        String::from_utf8(o).unwrap()
    }
    fn print_subtree(&self, tb: &mut TreeBuilder, node: usize) {
        let node = &self.v[node];
        for i in 0..ORDER {
            if let Some(ch) = node.children[i] {
                self.print_subtree(tb.begin_child(format!("<{}>", ch)), ch);
                tb.end_child();
            }
            if i < ORDER - 1 {
                tb.add_empty_child(format!("{:?}", node.entries[i]));
            }
        }
    }
}

#[cfg(test)]
mod tests {
    use super::BTree;
    use rand::{rngs::StdRng, RngCore, SeedableRng};
    #[test]
    fn basic_test() {
        let mut bt = BTree::new(16);

        let ns = &[
            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);
        }
        for (i, e) in bt.v.iter().enumerate() {
            println!("{} {:?}", i, e);
        }
        assert_eq!(bt.count(), ns.len());
    }

    #[test]
    fn test_delete() {
        let mut bt = BTree::new(16);

        let ns = &[
            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);
        }
        for e in ns {
            println!("\n\ndeleting {}", e);
            println!("{}", bt.debug_print());
            assert_eq!(bt.delete(e), Some(*e));
        }
    }

    #[test]
    fn randomized_all_reachable() {
        time_test::time_test!("10 x 1000 inserts");
        for seed in &[1, 2, 3, 4, 5, 6, 7, 8, 9, 10] {
            let mut rng = StdRng::seed_from_u64(*seed);
            let N = 100;
            let mut bt = BTree::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());
            }
            //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 = 100;
        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));
        }
    }

    #[test]
    fn randomized_stdbtree_test() {
        time_test::time_test!("10 x 1000 inserts");
        for seed in &[1, 2, 3, 4, 5, 6, 7, 8, 9, 10] {
            let mut rng = StdRng::seed_from_u64(*seed);
            let N = 100;
            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());
            }
        }
    }

    #[test]
    fn test_binary_node_search() {
        let mut bt = BTree::new(10);
        for i in 0..super::ORDER/2 {
            bt.insert(i);
        }

        println!("{}", bt.debug_print());
        assert_eq!(bt.binary_node_search(bt.root, &19), 15);
        for i in 0..super::ORDER - 1 {
            assert_eq!(
                bt.binary_node_search(bt.root, &i),
                std::cmp::min(i, super::ORDER/2)
            );
        }
    }
}