mathhook_core/algebra/

zero_detection.rs

//! Advanced zero detection and algebraic simplification
//! Handles complex expressions that should simplify to zero

use crate::core::{Expression, Number};
use crate::simplify::Simplify;
use num_bigint::BigInt;
use num_traits::{One, Zero};

/// Trait for zero detection in expressions
pub trait ZeroDetection {
    fn is_algebraic_zero(&self) -> bool;
    fn detect_zero_patterns(&self) -> bool;
    fn simplify_to_zero(&self) -> Option<Expression>;
}

impl ZeroDetection for Expression {
    /// Detect if an expression is algebraically equivalent to zero
    fn is_algebraic_zero(&self) -> bool {
        // First try basic zero detection
        if self.is_zero() {
            return true;
        }

        // Try simplification
        let simplified = self.simplify();
        if simplified.is_zero() {
            return true;
        }

        // Try advanced zero detection patterns
        self.detect_zero_patterns()
    }

    /// Detect common patterns that equal zero
    fn detect_zero_patterns(&self) -> bool {
        match self {
            Expression::Add(terms) => self.detect_additive_zero_patterns(terms),

            Expression::Mul(factors) => {
                // If any factor is zero, the whole product is zero
                factors.iter().any(|f| f.is_zero() || f.is_algebraic_zero())
            }

            _ => false,
        }
    }

    /// Try to simplify expression to zero if it's algebraically zero
    fn simplify_to_zero(&self) -> Option<Expression> {
        if self.is_algebraic_zero() {
            Some(Expression::integer(0))
        } else {
            None
        }
    }
}

impl Expression {
    /// Detect zero patterns in addition expressions
    fn detect_additive_zero_patterns(&self, terms: &[Expression]) -> bool {
        // Pattern 1: x + (-x) = 0
        if self.has_additive_inverses(terms) {
            return true;
        }

        // Pattern 2: Collect like terms that cancel
        if self.terms_cancel_out(terms) {
            return true;
        }

        // Pattern 3: Complex algebraic identities
        if self.detect_complex_zero_identities(terms) {
            return true;
        }

        false
    }

    /// Check if terms contain additive inverses that cancel out
    fn has_additive_inverses(&self, terms: &[Expression]) -> bool {
        for (i, term1) in terms.iter().enumerate() {
            for (j, term2) in terms.iter().enumerate() {
                if i != j && self.are_additive_inverses(term1, term2) {
                    // Check if all other terms also have inverses or are zero
                    let remaining_terms: Vec<&Expression> = terms
                        .iter()
                        .enumerate()
                        .filter(|(k, _)| *k != i && *k != j)
                        .map(|(_, t)| t)
                        .collect();

                    if remaining_terms.is_empty() {
                        return true; // Only the two inverse terms
                    }

                    // Check if remaining terms also cancel
                    let remaining_expr =
                        Expression::add(remaining_terms.into_iter().cloned().collect());
                    if remaining_expr.is_algebraic_zero() {
                        return true;
                    }
                }
            }
        }
        false
    }

    /// Check if two expressions are additive inverses
    fn are_additive_inverses(&self, expr1: &Expression, expr2: &Expression) -> bool {
        match (expr1, expr2) {
            // Simple numeric case: 5 + (-5) = 0
            (Expression::Number(Number::Integer(a)), Expression::Number(Number::Integer(b))) => {
                *a + *b == 0
            }

            // Symbolic case: x + (-x) = 0
            (Expression::Symbol(s1), Expression::Mul(factors)) => {
                if factors.len() == 2 {
                    if let (Expression::Number(Number::Integer(n)), Expression::Symbol(s2)) =
                        (&factors[0], &factors[1])
                    {
                        *n == -1 && s1 == s2
                    } else if let (Expression::Symbol(s2), Expression::Number(Number::Integer(n))) =
                        (&factors[0], &factors[1])
                    {
                        *n == -1 && s1 == s2
                    } else {
                        false
                    }
                } else {
                    false
                }
            }

            // Reverse case: (-x) + x = 0
            (Expression::Mul(_factors), Expression::Symbol(_s1)) => {
                self.are_additive_inverses(expr2, expr1)
            }

            // Complex multiplication cases
            (Expression::Mul(factors1), Expression::Mul(factors2)) => {
                self.are_multiplicative_inverses(factors1, factors2)
            }

            _ => false,
        }
    }

    /// Check if two multiplication expressions are additive inverses
    fn are_multiplicative_inverses(
        &self,
        factors1: &[Expression],
        factors2: &[Expression],
    ) -> bool {
        // Check if one has a -1 factor and the rest are identical
        let (neg_factors, pos_factors) = if self.has_negative_one_factor(factors1) {
            (factors1, factors2)
        } else if self.has_negative_one_factor(factors2) {
            (factors2, factors1)
        } else {
            return false;
        };

        // Remove the -1 factor and compare
        let neg_without_minus_one: Vec<Expression> = neg_factors
            .iter()
            .filter(|f| !matches!(f, Expression::Number(Number::Integer(n)) if *n == -1))
            .cloned()
            .collect();

        // Compare the remaining factors
        self.are_factor_sets_equal(&neg_without_minus_one, pos_factors)
    }

    /// Check if factors contain -1
    fn has_negative_one_factor(&self, factors: &[Expression]) -> bool {
        factors
            .iter()
            .any(|f| matches!(f, Expression::Number(Number::Integer(n)) if *n == -1))
    }

    /// Check if two factor sets are equal (ignoring order)
    fn are_factor_sets_equal(&self, factors1: &[Expression], factors2: &[Expression]) -> bool {
        if factors1.len() != factors2.len() {
            return false;
        }

        // Simple comparison for now - could be more sophisticated
        for factor1 in factors1 {
            if !factors2.contains(factor1) {
                return false;
            }
        }

        true
    }

    /// Check if terms cancel out when collected
    fn terms_cancel_out(&self, terms: &[Expression]) -> bool {
        // Group like terms and check if coefficients sum to zero
        // Use Vec instead of HashMap due to Expression not implementing Eq+Hash
        let mut term_coefficients: Vec<(Expression, BigInt)> = Vec::new();

        for term in terms {
            let (coeff, base) = self.extract_coefficient_and_base_term(term);
            // Find existing entry or create new one
            let mut found = false;
            for (existing_expr, existing_coeff) in term_coefficients.iter_mut() {
                if *existing_expr == base {
                    *existing_coeff += &coeff;
                    found = true;
                    break;
                }
            }
            if !found {
                term_coefficients.push((base, coeff));
            }
        }

        // Check if all coefficients are zero
        term_coefficients.iter().all(|(_, coeff)| coeff.is_zero())
    }

    /// Extract coefficient and base term
    fn extract_coefficient_and_base_term(&self, term: &Expression) -> (BigInt, Expression) {
        match term {
            Expression::Number(Number::Integer(n)) => (BigInt::from(*n), Expression::integer(1)),
            Expression::Symbol(_) => (BigInt::one(), term.clone()),
            Expression::Mul(factors) => {
                let mut coefficient = BigInt::one();
                let mut base_factors = Vec::new();

                for factor in factors.iter() {
                    if let Expression::Number(Number::Integer(n)) = factor {
                        coefficient *= BigInt::from(*n);
                    } else {
                        base_factors.push(factor.clone());
                    }
                }

                let base = if base_factors.is_empty() {
                    Expression::integer(1)
                } else if base_factors.len() == 1 {
                    base_factors[0].clone()
                } else {
                    Expression::mul(base_factors)
                };

                (coefficient, base)
            }
            _ => (BigInt::one(), term.clone()),
        }
    }

    /// Detect complex algebraic identities that equal zero
    fn detect_complex_zero_identities(&self, terms: &[Expression]) -> bool {
        // This is where we'd implement detection of complex algebraic identities
        // like the one in the test case: 4 + 4*x - 2*(2 + 2*x) = 0

        // For now, try a simplified approach
        if terms.len() >= 3 {
            // Look for patterns like a + b*x - c*(d + e*x) where the expansion equals zero
            if let Some(expanded) = self.try_expand_and_simplify(terms) {
                return expanded.is_zero();
            }
        }

        false
    }

    /// Try to expand and simplify complex expressions
    fn try_expand_and_simplify(&self, terms: &[Expression]) -> Option<Expression> {
        // This is a simplified version of expansion
        // Full implementation would handle all cases

        let mut simplified_terms = Vec::new();

        for term in terms {
            match term {
                // Expand -c*(d + e*x) = -c*d - c*e*x
                Expression::Mul(factors) if factors.len() >= 2 => {
                    if let Some(expanded) = self.try_expand_multiplication(factors) {
                        if let Expression::Add(expanded_terms) = expanded {
                            simplified_terms.extend(expanded_terms.into_iter());
                        } else {
                            simplified_terms.push(expanded);
                        }
                    } else {
                        simplified_terms.push(term.clone());
                    }
                }
                _ => simplified_terms.push(term.clone()),
            }
        }

        let result = Expression::add(simplified_terms).simplify();
        Some(result)
    }

    /// Try to expand multiplication expressions
    fn try_expand_multiplication(&self, factors: &[Expression]) -> Option<Expression> {
        // Look for patterns like coefficient * (sum)
        if factors.len() == 2 {
            match (&factors[0], &factors[1]) {
                (Expression::Number(Number::Integer(coeff)), Expression::Add(terms)) => {
                    // Distribute: coeff * (a + b) = coeff*a + coeff*b
                    let distributed_terms: Vec<Expression> = terms
                        .iter()
                        .map(|term| {
                            Expression::mul(vec![Expression::integer(*coeff), term.clone()])
                        })
                        .collect();
                    Some(Expression::add(distributed_terms))
                }
                (Expression::Add(terms), Expression::Number(Number::Integer(coeff))) => {
                    // Distribute: (a + b) * coeff = a*coeff + b*coeff
                    let distributed_terms: Vec<Expression> = terms
                        .iter()
                        .map(|term| {
                            Expression::mul(vec![term.clone(), Expression::integer(*coeff)])
                        })
                        .collect();
                    Some(Expression::add(distributed_terms))
                }
                _ => None,
            }
        } else {
            None
        }
    }

    /// Advanced zero detection for specific algebraic patterns
    pub fn detect_advanced_zero_patterns(&self) -> bool {
        match self {
            // Pattern: (a + b) - (a + b) = 0
            Expression::Add(terms) if terms.len() == 2 => {
                if self.are_additive_inverses(&terms[0], &terms[1]) {
                    return true;
                }
                false
            }

            // Pattern: a*x + b*x - (a+b)*x = 0
            Expression::Add(terms) => {
                // Try factoring out common terms
                if let Some(factored) = self.try_factor_for_zero_detection(terms) {
                    return factored.is_zero();
                }
                false
            }

            _ => false,
        }
    }

    /// Try factoring expressions to detect zeros
    fn try_factor_for_zero_detection(&self, _terms: &[Expression]) -> Option<Expression> {
        // This would implement more sophisticated factoring for zero detection
        // For now, return None to indicate no factoring was possible
        None
    }
}

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

    #[test]
    fn test_zero_detection_basic() {
        // Test basic zero
        let zero = Expression::integer(0);
        assert!(zero.is_algebraic_zero());

        // Test x + (-x) = 0
        let x = symbol!(x);
        let expr = Expression::add(vec![
            Expression::symbol(x.clone()),
            Expression::mul(vec![Expression::integer(-1), Expression::symbol(x.clone())]),
        ]);

        // This should be detected as zero
        println!("x + (-x) = {}", expr);
        assert!(expr.is_algebraic_zero());
    }

    #[test]
    fn test_additive_inverse_detection() {
        let x = symbol!(x);

        let term1 = Expression::symbol(x.clone());
        let term2 = Expression::mul(vec![Expression::integer(-1), Expression::symbol(x.clone())]);

        let expr = Expression::integer(1); // Dummy for method access
        assert!(expr.are_additive_inverses(&term1, &term2));
    }

    #[test]
    fn test_numeric_zero_detection() {
        // Test 5 + (-5) = 0
        let expr = Expression::add(vec![Expression::integer(5), Expression::integer(-5)]);

        assert!(expr.is_algebraic_zero());
    }

    #[test]
    fn test_complex_zero_pattern() {
        let x = symbol!(x);

        // Test: 4 + 4*x - 2*(2 + 2*x) = 4 + 4*x - 4 - 4*x = 0
        let expr = Expression::add(vec![
            Expression::integer(4),
            Expression::mul(vec![Expression::integer(4), Expression::symbol(x.clone())]),
            Expression::mul(vec![
                Expression::integer(-2),
                Expression::add(vec![
                    Expression::integer(2),
                    Expression::mul(vec![Expression::integer(2), Expression::symbol(x.clone())]),
                ]),
            ]),
        ]);

        println!("Complex zero pattern: {}", expr);

        // This is a complex case that should expand to zero
        // For now, just test that it doesn't crash
        let is_zero = expr.is_algebraic_zero();
        println!("Is algebraic zero: {}", is_zero);
    }

    #[test]
    fn test_zero_simplification() {
        let x = symbol!(x);

        let expr = Expression::add(vec![
            Expression::symbol(x.clone()),
            Expression::mul(vec![Expression::integer(-1), Expression::symbol(x.clone())]),
        ]);

        if let Some(simplified) = expr.simplify_to_zero() {
            assert_eq!(simplified, Expression::integer(0));
        }
    }

    #[test]
    fn test_multiplication_zero_detection() {
        let x = symbol!(x);

        // Test 0 * x = 0
        let expr = Expression::mul(vec![Expression::integer(0), Expression::symbol(x.clone())]);

        assert!(expr.is_algebraic_zero());
    }
}