binary_tree.rs

#[derive(Debug)]
enum BinaryTree<T: Ord> {
    Leaf {
        lhs: Box<BinaryTree<T>>,
        rhs: Box<BinaryTree<T>>,
        val: (T, Value),
    },
    Empty,
}

impl<T: Ord> BinaryTree<T> {
    pub fn new() -> BinaryTree<T> {
        BinaryTree::Empty
    }

    pub fn insert(&mut self, key: T, new_val: Value) {
        match self {
            &mut BinaryTree::Leaf { ref mut lhs, ref mut rhs, ref val } => {
                match key.cmp(&val.0) {
                    Ordering::Greater =>
                        lhs.insert(key, new_val),
                    Ordering::Less =>
                        rhs.insert(key, new_val),
                    _ => return
                }
            },
            &mut BinaryTree::Empty => {
                *self = BinaryTree::Leaf {
                    lhs: Box::new(BinaryTree::Empty),
                    rhs: Box::new(BinaryTree::Empty),
                    val: (key, new_val),
                }
            }
        }
    }

    pub fn is_empty(&self) -> bool {
        match self {
            &BinaryTree::Leaf { .. } =>
                false,
            &BinaryTree::Empty =>
                true,
        }
    }
}