lib.rs

use std::cell::{Ref, RefCell};

pub struct BinaryTree<T> where T: Clone + PartialEq + PartialOrd {
    data: T,
    left: RefCell<Option<Box<BinaryTree<T>>>>,
    right: RefCell<Option<Box<BinaryTree<T>>>>,
}

impl<T> BinaryTree<T> where T: Clone + PartialEq + PartialOrd {
    pub fn new(root: T) -> Self {
        BinaryTree{
            data: root,
            left: RefCell::new(None),
            right: RefCell::new(None),
        }
    }

    pub fn data(&self) -> T {
        self.data.clone()
    }

    pub fn insert(&mut self, val: T) {
        if val <= self.data {
            let mut left = self.left.borrow_mut();
            if left.is_none() {
                *left = Some(Box::new(BinaryTree::<T>::new(val)));
            } else {
                left.as_mut().unwrap().insert(val);
            }
        } else {
            let mut right = self.right.borrow_mut();
            if right.is_none() {
                *right = Some(Box::new(BinaryTree::<T>::new(val)));
            } else {
                right.as_mut().unwrap().insert(val);
            }
        }
    }

    pub fn left(&self) -> Ref<Option<Box<BinaryTree<T>>>> {
        self.left.borrow()
    }

    pub fn right(&self) -> Ref<Option<Box<BinaryTree<T>>>> {
        self.right.borrow()
    }
    
    pub fn sorted(&self) -> Vec<T> {
        let mut out = vec![];
        let l = self.left.borrow();
        if l.is_some() {
            out.append(&mut l.as_ref().unwrap().sorted());
        }
        out.push(self.data.clone());
        let r = self.right.borrow();
        if r.is_some() {
            out.append(&mut r.as_ref().unwrap().sorted());
        }
        out
    }
}

pub fn add(left: usize, right: usize) -> usize {
    left + right
}

#[cfg(test)]
mod tests {
    use super::*;

    fn test_leaf<T: Clone + PartialEq + PartialOrd>(tree: &BinaryTree<T>, data: T, has_left: bool, has_right: bool) {
        assert!(data == tree.data());
        assert_eq!(tree.left().is_some(), has_left);
        assert_eq!(tree.right().is_some(), has_right);
    }

    fn make_tree<T: Clone + PartialEq + PartialOrd>(data: Vec<T>) -> Box<BinaryTree<T>>{
        if data.is_empty() {
            panic!("Cannot make empty tree");
        }
        let mut iter = data.iter();
        let mut tree = Box::new(BinaryTree::<T>::new(iter.next().unwrap().clone()));
        for x in iter {
            tree.insert(x.clone());
        }
        tree
    }

    #[test]
    fn data_is_retained() {
        let tested = make_tree::<u32>(vec![4]);
        test_leaf(&tested, 4, false, false);
    }

    #[test]
    fn smaller_number_at_left_node() {
        let tested = make_tree::<u32>(vec![4, 2]);
        test_leaf(&tested, 4, true, false);
        test_leaf(tested.left().as_ref().unwrap(), 2, false, false);
    }

    #[test]
    fn same_number_at_left_node() {
        let tested = make_tree::<u32>(vec![4, 4]);
        test_leaf(&tested, 4, true, false);
        test_leaf(tested.left().as_ref().unwrap(), 4, false, false);
    }

    #[test]
    fn greater_number_at_right_node() {
        let tested = make_tree::<u32>(vec![4,5]);
        test_leaf(&tested, 4, false, true);
        test_leaf(tested.right().as_ref().unwrap(), 5, false, false);
    }

    #[test]
    fn can_create_complex_tree() {
        let tested = make_tree::<u32>(vec![4,2,6,1,3,5,7]);
        test_leaf(&tested, 4, true, true);
        test_leaf(tested.left().as_ref().unwrap(), 2, true, true);
        test_leaf(tested.right().as_ref().unwrap(), 6, true, true);

        test_leaf(tested.left().as_ref().unwrap().left().as_ref().unwrap(), 1, false, false);
        test_leaf(tested.left().as_ref().unwrap().right().as_ref().unwrap(), 3, false, false);

        test_leaf(tested.right().as_ref().unwrap().left().as_ref().unwrap(), 5, false, false);
        test_leaf(tested.right().as_ref().unwrap().right().as_ref().unwrap(), 7, false, false);
    }
    
    fn test_sort<T: Clone + PartialEq + PartialOrd>(tree: &BinaryTree<T>, expected: Vec<T>) {
        let actual = tree.sorted();
        assert!(actual == expected);
    }
    
    #[test]
    fn can_sort_single_number() {
        let tested = make_tree::<u32>(vec![2]);
        test_sort(&tested, vec![2]);
    }

    #[test]
    fn can_sort_if_second_number_is_smaller_than_first() {
        let tested = make_tree::<u32>(vec![2, 1]);
        test_sort(&tested, vec![1, 2]);
    }

    #[test]
    fn can_sort_if_second_number_is_same_as_first() {
        let tested = make_tree::<u32>(vec![2, 2]);
        test_sort(&tested, vec![2, 2]);
    }

    #[test]
    fn can_sort_if_second_number_is_greater_than_first() {
        let tested = make_tree::<u32>(vec![2, 3]);
        test_sort(&tested, vec![2, 3]);
    }
    
    #[test]
    fn can_sort_complex_tree() {
        let tested = make_tree::<u32>(vec![2, 1, 3, 6, 7, 5]);
        test_sort(&tested, vec![1, 2, 3, 5, 6, 7]);
    }
}