use std::fmt::Display;
/// A binary tree structure used to parse and evaluate an expression into RPN.
///
/// Work in progress.
///
/// Type parameter must implement `Copy` trait until borrowing is implemented.
pub struct Tree<T: Copy> {
    pub root_node: TreeNode<T>,
}
impl<T: Copy> Tree<T> {
    /// Takes reducer function input with following signature.
    ///
    /// The caller should ensure that reducer function returns same type as
    /// the left- and right-hand side.
    ///
    /// Example: adding LHS: <i32>, Parent: <i32>, RHS: <i32> to sum values in tree.
    pub fn reduce<R>(&self, reducer: fn(Option<R>, T, Option<R>) -> R) -> R {
        self.root_node.reduce(reducer)
    }

    /// Initialises a new Tree struct.
    ///
    /// Needs a root value
    pub fn new(root_val: T) -> Tree<T> {
        Tree::<T> {
            root_node: TreeNode::<T> {
                value: root_val,
                left: None,
                right: None,
            },
        }
    }

    /// Inserts a node to the left of the root node.
    pub fn insert_left(&mut self, v: T) {
        self.root_node.insert_left(v);
    }

    /// Inserts a node to the right of the root node.
    pub fn insert_right(&mut self, v: T) {
        self.root_node.insert_right(v);
    }
}
impl<T: Display + Copy> Display for Tree<T> {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(f, "{}", self.root_node)
    }
}

/// A node in a binary tree.
///
/// Can be used for many interesting algorithmic things.
pub struct TreeNode<T: Copy> {
    pub value: T,

    /// The left node, may be `None`.
    pub left: Option<Box<TreeNode<T>>>,

    /// The right node, may be `None`.
    pub right: Option<Box<TreeNode<T>>>,
}
impl<T: Copy + Display> Display for TreeNode<T> {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(
            f,
            "{}{}{}",
            match &self.left {
                Some(v) => format!("({})<-", v),
                None => "".to_string(),
            },
            format!("({})", self.value),
            match &self.right {
                Some(v) => format!("->({})", v),
                None => "".to_string(),
            }
        )
    }
}
impl<T: Copy> TreeNode<T> {

    /// Initialises a new node for a Tree.
    pub fn new(v: T) -> TreeNode<T> {
        TreeNode {
            value: v,
            left: None,
            right: None,
        }
    }

    /// Recursively reduces each element in tree.
    pub fn reduce<R>(&self, reducer: fn(Option<R>, T, Option<R>) -> R) -> R {
        let left_val = match &self.left {
            Some(node) => Some(node.reduce(reducer)),
            None => None,
        };
        let right_val = match &self.right {
            Some(node) => Some(node.reduce(reducer)),
            None => None,
        };
        reducer(left_val, self.value, right_val)
    }

    /// Recursively inserts to the left of node until there is one empty space.
    pub fn insert_left(&mut self, value: T) {
        if let Some(node) = &mut self.left {
            node.insert_left(value)
        }
        self.left = Some(Box::new(TreeNode {
            value,
            left: None,
            right: None,
        }));
    }

    /// Recursively inserts to the right of node until there is one empty space.
    pub fn insert_right(&mut self, value: T) {
        if let Some(node) = &mut self.right {
            node.insert_right(value)
        }
        self.right = Some(Box::new(TreeNode::new(value)))
    }
}