cliard24 0.1.2

//! # Abstract Syntax Tree (AST) Module
//!
//! Provides the core data structures and algorithms for building, manipulating,
//! and evaluating expression trees representing arithmetic operations (+, -, *, /)
//! on literal numbers and variables.
//!
//! The AST supports:
//! - Binary arithmetic operations (addition, subtraction, multiplication, division)
//! - Literal numeric values and variables
//! - Expression evaluation with variable substitution
//! - Pre-calculation optimization for constant expressions
//! - Infix expression parsing and display

use crate::expression::{
    error::AstError,
    parser::{ExprToken, Expression},
};
use std::collections::{HashMap, VecDeque};

/// Numeric type used throughout the expression system
pub type ExprNum = f64;

/// Index type for referencing nodes within the expression tree
pub type NodeIdx = usize;

/// Calculate tolerance
pub const EXPR_EPSILON: f64 = 1e-6;

/// Binary arithmetic operators supported in expressions
///
/// Each operator encapsulates both the mathematical operation and associated metadata
/// such as precedence rules and commutativity properties.
#[cfg_attr(test, derive(Debug, PartialEq))]
#[derive(Clone, Copy)]
pub enum BinaryOpr {
    /// Addition operator (+)
    Add,
    /// Subtraction operator (-)
    Sub,
    /// Multiplication operator (*)
    Mul,
    /// Division operator (/)
    Div,
}

impl<'a> BinaryOpr {
    /// Converts a string representation to a binary operator
    ///
    /// # Arguments
    /// * `opr` - String slice representing the operator (e.g., "+", "-", "*", "/")
    ///
    /// # Returns
    /// - `Ok(BinaryOpr)` if the string represents a valid operator
    /// - `Err(AstError::UnknownOperator)` for unrecognized operator strings
    ///
    /// # Examples
    /// ```
    /// use cliard24::expression::ast::BinaryOpr;
    ///
    /// assert!(BinaryOpr::from_opr("+").is_ok());
    /// assert!(BinaryOpr::from_opr("?").is_err());
    /// ```
    #[inline]
    pub fn from_opr(opr: &'a str) -> Result<Self, AstError<'a>> {
        match opr {
            "+" => Ok(BinaryOpr::Add),
            "-" => Ok(BinaryOpr::Sub),
            "*" => Ok(BinaryOpr::Mul),
            "/" => Ok(BinaryOpr::Div),
            unkn => Err(AstError::UnknownOperator(unkn)),
        }
    }

    /// Returns an array containing all supported binary operators
    ///
    /// This is useful for iteration over all possible operations during solution finding.
    ///
    /// # Returns
    /// Array containing all four arithmetic operators: [Add, Sub, Mul, Div]
    #[inline]
    pub fn get_all_operators() -> [Self; 4] {
        [
            BinaryOpr::Add,
            BinaryOpr::Sub,
            BinaryOpr::Mul,
            BinaryOpr::Div,
        ]
    }

    /// Returns the precedence level of the operator (higher number = higher precedence)
    ///
    /// Precedence determines evaluation order in expressions without parentheses.
    /// Multiplication and division have higher precedence than addition and subtraction.
    ///
    /// # Returns
    /// - `2` for multiplication and division
    /// - `1` for addition and subtraction
    #[inline]
    pub fn get_precedence(&self) -> u8 {
        match self {
            BinaryOpr::Mul | BinaryOpr::Div => 2,
            BinaryOpr::Add | BinaryOpr::Sub => 1,
        }
    }

    /// Checks if the operator is commutative (order of operands doesn't matter)
    ///
    /// Commutative operations allow for optimization in solution finding by reducing
    /// redundant expression forms.
    ///
    /// # Returns
    /// - `true` for addition and multiplication
    /// - `false` for subtraction and division
    #[inline]
    pub fn is_commutation(&self) -> bool {
        matches!(self, BinaryOpr::Add | BinaryOpr::Mul)
    }

    /// Performs the arithmetic operation on two operands
    ///
    /// # Arguments
    /// * `left` - Left operand value
    /// * `right` - Right operand value
    ///
    /// # Returns
    /// - `Ok(ExprNum)` with the calculation result
    /// - `Err(AstError::DivisionByZero)` for division by zero
    /// - `Err(AstError::CalculationResultError)` for subnormal results
    ///
    /// # Panics
    /// This function does not panic but returns errors for exceptional conditions
    pub fn calc(&self, left: &ExprNum, right: &ExprNum) -> Result<ExprNum, AstError<'a>> {
        match self {
            BinaryOpr::Add => BinaryOpr::validate_calc_res(*left + *right),
            BinaryOpr::Sub => BinaryOpr::validate_calc_res(*left - *right),
            BinaryOpr::Mul => BinaryOpr::validate_calc_res(*left * *right),
            BinaryOpr::Div => {
                if right.abs() < EXPR_EPSILON {
                    return Err(AstError::DivisionByZero);
                }
                BinaryOpr::validate_calc_res(*left / *right)
            }
        }
    }

    /// Validate the calculation result
    ///
    /// # Arguments
    /// * `res` - the calculation result
    ///
    /// # Returns
    /// - `Ok(ExprNum)` with the calculation result
    /// - `Err(AstError::CalculationResultError)` for subnormal results
    ///
    /// # Panics
    /// This function does not panic but returns errors for exceptional conditions
    #[inline]
    fn validate_calc_res(res: ExprNum) -> Result<ExprNum, AstError<'a>> {
        if res.is_subnormal() {
            Err(AstError::CalculationResultError(res))
        } else {
            Ok(res)
        }
    }

    /// Returns the string representation of the operator
    ///
    /// # Returns
    /// String slice: "+", "-", "*", or "/"
    #[inline]
    pub fn as_str(&self) -> &'static str {
        match self {
            BinaryOpr::Add => "+",
            BinaryOpr::Sub => "-",
            BinaryOpr::Mul => "*",
            BinaryOpr::Div => "/",
        }
    }
}

/// Node types in the expression abstract syntax tree
///
/// The AST supports three types of nodes: literal values, variables, and binary operations.
/// This enum forms the building blocks for constructing complex arithmetic expressions.
#[cfg_attr(test, derive(Debug, PartialEq))]
pub enum ExprNode<'a> {
    /// Numeric literal value (e.g., 5, 3.14)
    Literal(ExprNum),
    /// Variable placeholder that requires substitution during evaluation (e.g., x, y)
    Variable(&'a str),
    /// Binary operation combining two sub-expressions
    BinaryOpr {
        /// The operator to apply
        opr: BinaryOpr,
        /// Index of the left child node in the expression tree
        l_idx: NodeIdx,
        /// Index of the right child node in the expression tree
        r_idx: NodeIdx,
    },
}

/// Expression tree structure for representing and evaluating arithmetic expressions
///
/// The tree stores all nodes in a flat vector and uses indices to represent parent-child relationships.
/// This design enables efficient traversal and evaluation while maintaining a simple memory layout.
///
/// # Invariants
/// - `nodes` and `pre_v` vectors always have the same length
/// - Node indices in binary operations always point to valid positions in `nodes`
/// - The root index, if present, points to a valid node
pub struct ExprTree<'a> {
    /// Flat storage of all nodes in the expression tree
    nodes: Vec<ExprNode<'a>>,
    /// Index of the root node in the `nodes` vector, if the tree is not empty
    root_idx: Option<NodeIdx>,
    /// Pre-calculated values for nodes that can be computed without variable substitution
    /// `None` indicates the value depends on variables and requires runtime evaluation
    pre_v: Vec<Option<ExprNum>>,
}

impl<'a> ExprTree<'a> {
    /// Creates a new empty expression tree
    ///
    /// # Returns
    /// New `ExprTree` instance with no nodes and no root
    pub fn new() -> Self {
        ExprTree {
            nodes: Vec::new(),
            root_idx: None,
            pre_v: Vec::new(),
        }
    }

    /// Creates an expression tree containing only a single literal value
    ///
    /// # Arguments
    /// * `value` - The numeric value to store in the tree
    ///
    /// # Returns
    /// New `ExprTree` with one literal node as root
    pub fn from_literal(value: ExprNum) -> Self {
        ExprTree {
            nodes: vec![ExprNode::Literal(value)],
            root_idx: Some(0),
            pre_v: vec![Some(value)],
        }
    }

    /// Creates an expression tree containing only a single variable
    ///
    /// # Arguments
    /// * `name` - The variable name
    ///
    /// # Returns
    /// New `ExprTree` with one variable node as root
    pub fn from_variable(name: &'a str) -> Self {
        ExprTree {
            nodes: vec![ExprNode::Variable(name)],
            root_idx: Some(0),
            pre_v: vec![None],
        }
    }

    /// Parses an infix expression string and constructs the corresponding expression tree
    ///
    /// # Arguments
    /// * `infix_expr` - String containing the infix expression (e.g., "3 + 4 * 2")
    ///
    /// # Returns
    /// - `Ok(ExprTree)` representing the parsed expression
    /// - `Err(AstError)` for syntax errors or invalid expressions
    ///
    /// # Examples
    /// ```
    /// use cliard24::expression::ast::ExprTree;
    ///
    /// let tree = ExprTree::from_expr("3 + 4 * 2").unwrap();
    /// assert_eq!(tree.to_string(), "3 + 4 * 2");
    /// ```
    pub fn from_expr(infix_expr: &'a str) -> Result<Self, AstError<'a>> {
        ExprTree::from_postfix_expression(Expression::from_expr(infix_expr)?.to_postfix()?)
    }

    /// Constructs an expression tree from an infix expression representation
    ///
    /// # Arguments
    /// * `expr` - Mutable reference to an `Expression` containing infix tokens
    ///
    /// # Returns
    /// - `Ok(ExprTree)` built from the expression
    /// - `Err(AstError)` for invalid expression structures
    ///
    /// # Note
    /// This method consumes the expression by converting it to postfix notation
    pub fn from_infix_expression(expr: &mut Expression<'a>) -> Result<Self, AstError<'a>> {
        ExprTree::from_postfix_expression(expr.to_postfix()?)
    }

    /// Constructs an expression tree from a postfix (RPN) expression
    ///
    /// Uses the shunting-yard algorithm principle: tokens are processed left-to-right,
    /// operands are pushed to a stack, and operators pop their operands from the stack.
    ///
    /// # Arguments
    /// * `expr` - Expression in postfix notation
    ///
    /// # Returns
    /// - `Ok(ExprTree)` representing the expression
    /// - `Err(AstError)` for invalid postfix expressions
    ///
    /// # Errors
    /// - `AstError::InvalidOperandCount` if operators don't have enough operands
    /// - `AstError::InvalidExpressionStructure` for parentheses in postfix expression
    pub fn from_postfix_expression(expr: &Expression<'a>) -> Result<Self, AstError<'a>> {
        let mut tree = ExprTree::new();
        let mut stack = Vec::new();

        for tk in expr.tokens.iter() {
            let node_idx = match tk {
                ExprToken::Literal(num) => tree.add_node(ExprNode::Literal(*num))?,
                ExprToken::Variable(var) => tree.add_node(ExprNode::Variable(var))?,
                ExprToken::BinaryOpr(opr) => {
                    // Pop operands from stack (right operand first due to stack LIFO nature)
                    let r_idx = stack.pop().ok_or(AstError::InvalidOperandCount {
                        operator: opr.as_str(),
                        expected: 2,
                        actual: stack.len(),
                    })?;
                    let l_idx = stack.pop().ok_or(AstError::InvalidOperandCount {
                        operator: opr.as_str(),
                        expected: 2,
                        actual: stack.len(),
                    })?;

                    tree.add_node(ExprNode::BinaryOpr {
                        opr: *opr,
                        l_idx,
                        r_idx,
                    })?
                }
                ExprToken::LeftParen | ExprToken::RightParen => {
                    return Err(AstError::InvalidExpressionStructure(
                        "Parentheses shouldn't appear in the postfix expression",
                    ));
                }
            };
            // Push the new node onto the operand stack
            stack.push(node_idx);
        }

        // The last node added becomes the root
        tree.root_idx = Some(tree.nodes.len() - 1);
        Ok(tree)
    }

    /// Combines this expression tree with another as a new binary operation
    ///
    /// Creates a new root node that applies the specified operator to the current tree
    /// and the provided right subtree. This is used for building complex expressions
    /// during the solution finding process.
    ///
    /// # Arguments
    /// * `right_subtree` - The tree to combine as the right operand
    /// * `root_opr` - The operator to apply to the combined trees
    ///
    /// # Returns
    /// - `Ok(&Self)` reference to the modified tree
    /// - `Err(AstError)` for invalid tree structures
    ///
    /// # Note
    /// This method consumes the right subtree (sets its root to None)
    pub fn combine_with(
        &mut self,
        right_subtree: &mut Self,
        root_opr: BinaryOpr,
    ) -> Result<&Self, AstError<'a>> {
        let orig_left_len = self.nodes.len();
        let root_l_idx = self.get_root_idx()?;
        let root_r_idx = orig_left_len + right_subtree.get_root_idx()?;

        // Adjust indices in the right subtree to account for the merge
        for node in right_subtree.nodes.iter_mut() {
            match node {
                ExprNode::BinaryOpr { l_idx, r_idx, .. } => {
                    *l_idx += orig_left_len;
                    *r_idx += orig_left_len;
                }
                ExprNode::Variable(_) | ExprNode::Literal(_) => continue,
            }
        }

        // Merge the trees
        self.nodes.append(&mut right_subtree.nodes);
        self.pre_v.append(&mut right_subtree.pre_v);

        // Create new root node combining both subtrees
        self.add_root(root_opr, root_l_idx, root_r_idx)?;

        // Invalidate the consumed subtree
        right_subtree.root_idx = None;
        Ok(self)
    }

    /// Adds a new node to the tree and returns its index
    ///
    /// # Arguments
    /// * `new_node` - The node to add to the tree
    ///
    /// # Returns
    /// - `Ok(usize)` index of the newly added node
    /// - `Err(AstError)` for pre-calculation errors
    ///
    /// # Note
    /// This method does not update the root index. Use `add_root` for root nodes.
    #[inline]
    pub fn add_node(&mut self, new_node: ExprNode<'a>) -> Result<usize, AstError<'a>> {
        let new_node_idx = self.nodes.len();
        self.nodes.push(new_node);
        self.pre_calc(new_node_idx)?; // Pre-calculate value if possible
        Ok(new_node_idx)
    }

    /// Adds a new root node to the tree
    ///
    /// Creates a binary operation node that becomes the new root of the expression tree.
    ///
    /// # Arguments
    /// * `opr` - Operator for the new root node
    /// * `l_idx` - Index of the left child node
    /// * `r_idx` - Index of the right child node
    ///
    /// # Returns
    /// - `Ok(usize)` index of the new root node
    /// - `Err(AstError)` for invalid child indices or calculation errors
    #[inline]
    pub fn add_root(
        &mut self,
        opr: BinaryOpr,
        l_idx: usize,
        r_idx: usize,
    ) -> Result<usize, AstError<'a>> {
        let new_node_idx = self.nodes.len();
        let new_root = ExprNode::BinaryOpr { opr, l_idx, r_idx };
        self.nodes.push(new_root);
        self.pre_calc(new_node_idx)?;
        self.root_idx = Some(new_node_idx);
        Ok(new_node_idx)
    }

    /// Pre-calculates the value of a node if it contains only literals
    ///
    /// This optimization avoids runtime calculation for constant sub-expressions.
    /// Variable nodes and operations depending on variables will have `None` values.
    ///
    /// # Arguments
    /// * `node_idx` - Index of the node to pre-calculate
    ///
    /// # Returns
    /// - `Ok(Option<ExprNum>)` the pre-calculated value if available
    /// - `Err(AstError)` for invalid node indices
    #[inline]
    pub fn pre_calc(&mut self, node_idx: usize) -> Result<Option<ExprNum>, AstError<'a>> {
        if node_idx > self.pre_v.len() {
            return Err(AstError::InvalidPrecalcIndex {
                index: node_idx,
                total_nodes: self.pre_v.len(),
            });
        } else if node_idx == self.pre_v.len() {
            self.pre_v.push(None);
        }

        match self.get_node(node_idx)? {
            ExprNode::Literal(num) => {
                self.pre_v[node_idx] = Some(*num);
            }
            ExprNode::Variable(_) => {
                self.pre_v[node_idx] = None; // Variables cannot be pre-calculated
            }
            ExprNode::BinaryOpr { opr, l_idx, r_idx } => {
                // Only pre-calculate if both children have known values
                if let (Some(left), Some(right)) = (self.pre_v[*l_idx], self.pre_v[*r_idx]) {
                    self.pre_v[node_idx] = opr.calc(&left, &right).ok();
                }
            }
        }
        Ok(self.pre_v[node_idx])
    }

    /// Retrieves a node by index with bounds checking
    ///
    /// # Arguments
    /// * `index` - Index of the node to retrieve
    ///
    /// # Returns
    /// - `Ok(&ExprNode)` reference to the requested node
    /// - `Err(AstError::InvalidNodeIndex)` if index is out of bounds
    #[inline]
    pub fn get_node(&self, index: NodeIdx) -> Result<&ExprNode<'a>, AstError<'a>> {
        self.nodes.get(index).ok_or(AstError::InvalidNodeIndex {
            index,
            total_nodes: self.nodes.len(),
        })
    }

    /// Returns the root node index, ensuring the tree is not empty
    ///
    /// # Returns
    /// - `Ok(NodeIdx)` index of the root node
    /// - `Err(AstError::EmptyExpression)` if the tree has no root
    #[inline]
    pub fn get_root_idx(&self) -> Result<NodeIdx, AstError<'a>> {
        self.root_idx.ok_or(AstError::EmptyExpression)
    }

    /// Retrieves the pre-calculated value for a node, if available
    ///
    /// # Arguments
    /// * `index` - Index of the node
    ///
    /// # Returns
    /// - `Ok(&Option<ExprNum>)` reference to the pre-calculated value
    /// - `Err(AstError)` for invalid node indices
    #[inline]
    pub fn get_pre_value(&self, index: NodeIdx) -> Result<&Option<ExprNum>, AstError<'a>> {
        self.pre_v.get(index).ok_or(AstError::InvalidNodeIndex {
            index,
            total_nodes: self.nodes.len(),
        })
    }

    /// Removes the most recently added node from the tree
    ///
    /// This is the inverse operation of `add_node` and is used for backtracking
    /// during expression tree construction.
    ///
    /// # Returns
    /// `Some(ExprNode)` if a node was removed, `None` if the tree was empty
    ///
    /// # Note
    /// Does not update the root index. The caller must maintain tree consistency.
    #[inline]
    pub fn pop_node(&mut self) -> Option<ExprNode<'a>> {
        self.pre_v.pop();
        self.nodes.pop()
    }

    /// Collects all variable names used in the expression tree
    ///
    /// This is used to determine which variables need values provided during evaluation.
    ///
    /// # Returns
    /// Vector containing references to all variable names in the tree
    pub fn check_variables(&self) -> Vec<&str> {
        self.nodes
            .iter()
            .filter_map(|node| {
                if let ExprNode::Variable(var) = node {
                    Some(*var)
                } else {
                    None
                }
            })
            .collect()
    }

    /// Performs level-order (BFS) traversal of operator nodes
    ///
    /// Returns indices in evaluation order (leaves first, root last).
    /// This ordering ensures that when evaluating, all children are computed before their parents.
    ///
    /// # Returns
    /// - `Ok(impl Iterator<Item = NodeIdx>)` iterator over node indices in evaluation order
    /// - `Err(AstError)` if the tree is empty or has invalid structure
    fn iter_level_order(&self) -> Result<impl Iterator<Item = NodeIdx>, AstError<'a>> {
        let mut levels_order = Vec::new();
        let mut queue = VecDeque::new();

        queue.push_back(self.get_root_idx()?);

        while let Some(cur_idx) = queue.pop_front() {
            match self.get_node(cur_idx)? {
                ExprNode::Variable(_) | ExprNode::Literal(_) => continue,
                ExprNode::BinaryOpr { l_idx, r_idx, .. } => {
                    levels_order.push(cur_idx);
                    queue.push_back(*l_idx);
                    queue.push_back(*r_idx);
                }
            }
        }

        Ok(levels_order.into_iter().rev())
    }

    /// Evaluates the expression tree with the given variable values
    ///
    /// # Arguments
    /// * `variables` - HashMap mapping variable names to their numeric values
    ///
    /// # Returns
    /// - `Ok(ExprNum)` result of the expression evaluation
    /// - `Err(AstError)` for uninitialized variables, division by zero, or evaluation errors
    ///
    /// # Examples
    /// ```
    /// use std::collections::HashMap;
    /// use cliard24::expression::ast::ExprTree;
    ///
    /// let tree = ExprTree::from_expr("x + 2 * y").unwrap();
    /// let mut vars = HashMap::new();
    /// vars.insert("x", 3.0);
    /// vars.insert("y", 4.0);
    /// let result = tree.eval(&vars).unwrap();
    /// assert_eq!(result, 11.0);
    /// ```
    pub fn eval(&self, variables: &HashMap<&str, ExprNum>) -> Result<ExprNum, AstError<'a>> {
        // Use pre-calculated value if available (expression has no variables)
        if let Some(pre_value) = self.pre_v[self.get_root_idx()?] {
            return Ok(pre_value);
        }

        let mut node_results = HashMap::new();

        // Evaluate nodes in reverse level order (leaves first, root last)
        for node_idx in self.iter_level_order()? {
            let node_res = match self.get_node(node_idx)? {
                ExprNode::Literal(num) => *num,
                ExprNode::Variable(var) => *variables
                    .get(var)
                    .ok_or(AstError::UninitializedVariable(var))?,
                ExprNode::BinaryOpr { l_idx, r_idx, opr } => {
                    let left = match self.get_node(*l_idx)? {
                        ExprNode::Literal(num) => num,
                        ExprNode::Variable(var) => variables
                            .get(var)
                            .ok_or(AstError::UninitializedVariable(var))?,
                        _ => node_results
                            .get(l_idx)
                            .ok_or(AstError::ExpressionEvaluationError(
                                "Operator left child nodes have not been calculated",
                            ))?,
                    };
                    let right = match self.get_node(*r_idx)? {
                        ExprNode::Literal(num) => num,
                        ExprNode::Variable(var) => variables
                            .get(var)
                            .ok_or(AstError::UninitializedVariable(var))?,
                        _ => node_results
                            .get(r_idx)
                            .ok_or(AstError::ExpressionEvaluationError(
                                "Operator right child nodes have not been calculated",
                            ))?,
                    };
                    opr.calc(left, right)?
                }
            };
            node_results.insert(node_idx, node_res);
        }

        Ok(node_results
            .get(&self.get_root_idx()?)
            .ok_or(AstError::ExpressionEvaluationError(
                "Root node have not been calculated",
            ))?
            .to_owned())
    }
}

impl<'a> Default for ExprTree<'a> {
    fn default() -> Self {
        Self::new()
    }
}

// Implementation of Display trait for pretty-printing expressions in infix notation
impl<'a> std::fmt::Display for ExprTree<'a> {
    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
        /// Recursive helper function for generating infix notation with proper parentheses
        ///
        /// # Arguments
        /// * `tree` - Reference to the expression tree
        /// * `f` - Formatter for output
        /// * `idx` - Current node index
        /// * `parent_opr` - Parent operator (for precedence determination)
        /// * `is_right_tree` - Whether this node is a right child of its parent
        ///
        /// # Returns
        /// `std::fmt::Result` indicating success or failure
        fn write_infix(
            tree: &ExprTree,
            f: &mut std::fmt::Formatter,
            idx: NodeIdx,
            parent_opr: Option<BinaryOpr>,
            is_right_tree: bool,
        ) -> std::fmt::Result {
            match tree.nodes.get(idx).ok_or(std::fmt::Error)? {
                ExprNode::Literal(n) => write!(f, "{}", n),
                ExprNode::Variable(v) => write!(f, "{}", v),
                ExprNode::BinaryOpr { opr, l_idx, r_idx } => {
                    // Determine if parentheses are needed based on operator precedence rules
                    let need_paren = parent_opr.is_some_and(|p_opr| {
                        let p_prec = p_opr.get_precedence();
                        let cur_prec = opr.get_precedence();

                        // Parentheses needed when current operator has lower precedence
                        cur_prec < p_prec ||
                        // Special cases for non-commutative operations
                        (cur_prec == p_prec && (
                            // Right child of non-commutative parent needs parentheses
                            (!p_opr.is_commutation() && is_right_tree) ||
                            // Non-commutative operation as left child needs parentheses
                            (!opr.is_commutation() && !is_right_tree)
                        ))
                    });

                    if need_paren {
                        write!(f, "(")?;
                    }

                    write_infix(tree, f, *l_idx, Some(*opr), false)?;
                    write!(f, " {} ", opr.as_str())?;
                    write_infix(tree, f, *r_idx, Some(*opr), true)?;

                    if need_paren {
                        write!(f, ")")?;
                    }
                    Ok(())
                }
            }
        }

        match self.root_idx {
            Some(idx) => write_infix(self, f, idx, None, false),
            None => write!(f, ""),
        }
    }
}

#[cfg(test)]
mod tests {
    use std::str::FromStr;

    use super::*;

    #[test]
    fn test_build_expression_tree() {
        let tree = ExprTree::from_expr("a_b_c+(22.2-((abc55*4_400) / 55))").unwrap();
        assert_eq!(
            tree.nodes,
            vec![
                ExprNode::Variable("a_b_c"),
                ExprNode::Literal(22.2),
                ExprNode::Variable("abc55"),
                ExprNode::Literal(4_400.0),
                ExprNode::BinaryOpr {
                    opr: BinaryOpr::Mul,
                    l_idx: 2,
                    r_idx: 3
                },
                ExprNode::Literal(55.0),
                ExprNode::BinaryOpr {
                    opr: BinaryOpr::Div,
                    l_idx: 4,
                    r_idx: 5
                },
                ExprNode::BinaryOpr {
                    opr: BinaryOpr::Sub,
                    l_idx: 1,
                    r_idx: 6,
                },
                ExprNode::BinaryOpr {
                    opr: BinaryOpr::Add,
                    l_idx: 0,
                    r_idx: 7
                },
            ]
        );
    }

    #[test]
    fn test_tree_levels_order() {
        let tree = ExprTree::from_expr("((5+2)-3)*(8/2)-15").unwrap();
        assert_eq!(
            tree.iter_level_order().unwrap().collect::<Vec<NodeIdx>>(),
            vec![2, 7, 4, 8, 10]
        );
    }

    #[test]
    fn test_tree_display() {
        let tree = ExprTree::from_expr("(((5+(2)-3)*(8/2)))-15").unwrap();
        assert_eq!(tree.to_string(), "(5 + 2 - 3) * 8 / 2 - 15".to_string());

        let tree = ExprTree::from_expr("5 * 4 - (1 - 5)").unwrap();
        assert_eq!(tree.to_string(), "5 * 4 - (1 - 5)".to_string());
    }

    #[test]
    fn test_expression_tree_variable() {
        let tree = ExprTree::from_expr("((a+b)-c)*(d/zero)-e").unwrap();
        assert_eq!(
            tree.check_variables(),
            vec!["a", "b", "c", "d", "zero", "e"]
        );
        assert!(tree.eval(&HashMap::from([("only_zero", 0.0)])).is_err());
        assert_eq!(
            tree.eval(&HashMap::from([
                ("a", 5.0),
                ("b", 2.0),
                ("c", 3.0),
                ("d", 8.0),
                ("e", 15.0),
                ("zero", 2.0),
            ]))
            .unwrap(),
            1.0
        );
    }

    #[test]
    fn test_eval_expression_tree() {
        let tree = ExprTree::from_expr("((5+2)-3)*(8/2)-15").unwrap();
        assert_eq!(tree.eval(&HashMap::new()).unwrap(), 1.0);
        let tree = ExprTree::from_expr("((5+2)-3)*(8/div_zero)-15").unwrap();
        assert_eq!(tree.check_variables(), vec!["div_zero"]);
        assert!(tree.eval(&HashMap::from([("div_zero", 0.0)])).is_err());
        let tree = ExprTree::from_expr("((5+2)-3)*(8/div_zero)-15").unwrap();
        assert_eq!(
            tree.eval(&HashMap::from([("div_zero", 4.0)])).unwrap(),
            -7.0
        );
    }

    #[test]
    fn test_combine_tree() {
        let values = [2.0, 4.0, 6.0, 8.0, 10.0];
        let mut trees = values
            .iter()
            .map(|v| ExprTree::from_literal(*v))
            .collect::<Vec<_>>();
        let mut final_tree = ExprTree::from_literal(1.0);
        let mut s_tmp = String::from_str("1").unwrap();
        for (i, t) in trees.iter_mut().enumerate() {
            let ct = final_tree.combine_with(t, BinaryOpr::Add).unwrap();
            s_tmp.push_str(&format!(" + {}", values[i]));
            assert_eq!(format!("{}", ct), s_tmp);
        }
    }

    #[test]
    fn test_pre_eval() {
        let values = [2.0, 4.0, 6.0, 8.0, 10.0];
        let mut trees = values
            .iter()
            .map(|v| ExprTree::from_literal(*v))
            .collect::<Vec<_>>();
        let mut final_tree = ExprTree::from_literal(1.0);
        let mut s_tmp = String::from_str("1").unwrap();
        for (i, t) in trees.iter_mut().enumerate() {
            let ct = final_tree.combine_with(t, BinaryOpr::Mul).unwrap();
            println!("{:?}\n{:?}\n{:?}", ct.nodes, ct.root_idx, ct.pre_v);
            s_tmp.push_str(&format!(" * {}", values[i]));
            assert_eq!(format!("{}", ct), s_tmp);
            assert_eq!(
                ct.eval(&HashMap::new()).unwrap(),
                ct.pre_v.last().unwrap().unwrap()
            );
        }
    }
}