use std::mem;

use std::cell::RefCell;
use std::rc::Rc;

type BareTree<T> = Rc<RefCell<Node<T>>>;
pub type Tree<T> = Option<BareTree<T>>;

#[derive(Debug, Clone)]
pub struct Node<T> {
    pub data: T,
    pub left: Tree<T>,
    pub right: Tree<T>,
    pub parent: Tree<T>,
}

impl<T> Node<T> {
    pub fn new(data: T) -> Tree<T> {
        Some(Rc::new(RefCell::new(Node {
            data,
            left: None,
            right: None,
            parent: None,
        })))
    }
}

pub struct BinarySearchTree<T> {
    pub root: Tree<T>,
    pub length: u64,
}

impl<T> BinarySearchTree<T>
where
    T: std::cmp::PartialOrd + std::clone::Clone + std::fmt::Debug,
{
    pub fn new() -> Self {
        BinarySearchTree {
            root: None,
            length: 0,
        }
    }

    pub fn add(&mut self, data: T) {
        self.length += 1;
        let root = mem::replace(&mut self.root, None);
        self.root = self.add_rec(root, data);
    }

    fn add_rec(&mut self, node: Tree<T>, data: T) -> Tree<T> {
        println!("visiting node: {:?}, with data: {:?}", node, data);
        match node {
            Some(n) => {
                if data <= n.clone().borrow().data {
                    n.borrow_mut().left = self.add_rec(n.borrow_mut().left.clone(), data);
                } else {
                    n.borrow_mut().right = self.add_rec(n.borrow_mut().right.clone(), data);
                }
                Some(n)
            }
            _ => Node::new(data),
        }
    }

}

mod tests {
    use super::*;

    #[test]
    fn create_bst() {
        let _ = BinarySearchTree::<u32>::new();
        assert!(true);
    }

    #[test]
    fn add_to_bst() {
        let mut bst = BinarySearchTree::<u32>::new();
        bst.add(1);
        bst.add(2);
        bst.add(3);
        bst.add(4);
        bst.add(5);
        bst.add(6);
        bst.add(7);
        assert!(true);
    }
}