pub struct BinaryTree<T>
where
    T: std::fmt::Debug + Clone + Ord,
{
    elem: Option<Box<T>>,
    right: Option<Box<BinaryTree<T>>>,
    left: Option<Box<BinaryTree<T>>>,
}

pub type BinaryTreeNode<T> = BinaryTree<T>;

impl<T> BinaryTree<T>
where
    T: std::fmt::Debug + Clone + Ord,
{
    pub fn new(elem: T) -> BinaryTree<T> {
        BinaryTree {
            elem: Some(Box::new(elem)),
            right: None,
            left: None,
        }
    }

    pub fn delete(&mut self, del_elem: T) {
        if let Some(ref mut elem) = self.elem {
            if del_elem < **elem {
                if let Some(left) = &mut self.left {
                    left.delete(del_elem);
                }
            } else if del_elem > **elem {
                if let Some(right) = &mut self.right {
                    right.delete(del_elem);
                }
            } else {
                match (self.left.take(), self.right.take()) {
                    (None, right) => {
                        *self = BinaryTree {
                            elem: None,
                            left: None,
                            right,
                        };
                    }
                    (left, None) => {
                        *self = BinaryTree {
                            elem: None,
                            left,
                            right: None,
                        };
                    }
                    (Some(left), Some(right)) => {
                        let min_right = right.min().cloned();

                        *self = BinaryTree {
                            elem: min_right.map(Box::new),
                            left: Some(left),
                            right: Some(right),
                        };
                    }
                }
            }
        }
    }

    pub fn insert(&mut self, new_elem: T) {
        match &mut self.elem {
            Some(ref mut elem) => {
                if new_elem < **elem {
                    if let Some(left) = &mut self.left {
                        left.insert(new_elem);
                    } else {
                        self.left = Some(Box::new(BinaryTree::new(new_elem)));
                    }
                } else {
                    if let Some(right) = &mut self.right {
                        right.insert(new_elem);
                    } else {
                        self.right = Some(Box::new(BinaryTree::new(new_elem)));
                    }
                }
            }
            None => {
                self.elem = Some(Box::new(new_elem));
            }
        }
    }

    pub fn max(&self) -> Option<&T> {
        match &self.right {
            Some(right) => right.max(),
            None => self.elem.as_ref().map(|boxed_elem| &**boxed_elem),
        }
    }

    pub fn min(&self) -> Option<&T> {
        match &self.left {
            Some(left) => left.min(),
            None => self.elem.as_ref().map(|boxed_elem| &**boxed_elem),
        }
    }

    pub fn inorder(&self) {
        if let Some(left) = &self.left {
            left.inorder();
        }
        if let Some(elem) = &self.elem {
            println!("{:?}", elem);
        }
        if let Some(right) = &self.right {
            right.inorder();
        }
    }

    pub fn preorder(&self) {
        if let Some(elem) = &self.elem {
            println!("{:?}", elem);
        }
        if let Some(left) = &self.left {
            left.preorder();
        }
        if let Some(right) = &self.right {
            right.preorder();
        }
    }

    pub fn postorder(&self) {
        if let Some(left) = &self.left {
            left.postorder();
        }
        if let Some(right) = &self.right {
            right.postorder();
        }
        if let Some(elem) = &self.elem {
            println!("{:?}", elem);
        }
    }

    pub fn vec_insert(&mut self, elems: Vec<T>) {
        for i in elems {
            self.insert(i);
        }
    }
}

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

    #[test]
    fn test_min() {
        let mut a = BinaryTree::new(1);
        a.vec_insert([1, 2, 3, 4, 5, 6].to_vec());
        assert_eq!(a.min(), Some(&1));
    }
    #[test]
    fn test_max() {
        let mut a = BinaryTree::new("hola");
        a.vec_insert(["a", "b", "c", "adfasdfafas", "zzz"].to_vec());
        assert_eq!(a.max(), Some(&"zzz"));
    }
    #[test]
    fn test_string() {
        let mut a = BinaryTree::new(String::from("Hola"));
        let b: Vec<String> = vec!["Hola".to_string(), "adios".to_string()];
        a.vec_insert(b);
        assert_eq!(a.min(), Some(&"Hola".to_string()))
    }
}