mathhook-core 0.2.0

//! Comprehensive Grevlex Monomial Ordering Tests
//!
//! Validates the graded reverse lexicographic (grevlex) ordering implementation.
//! Grevlex is the standard ordering for Gröbner basis computations.
//!
//! The implementation uses the definition where monomials are compared by:
//! 1. Total degree (higher degree > lower degree)
//! 2. If degrees equal: iterate exponents from right to left (reverse order)
//!    and return the REVERSED comparison of the first differing exponent

use mathhook_core::algebra::groebner::{MonomialOrder, MonomialOrdering};
use mathhook_core::core::Expression;
use mathhook_core::symbol;
use std::cmp::Ordering;

// Test grevlex by total degree: higher degree > lower degree
#[test]
fn test_grevlex_by_total_degree() {
    let x = symbol!(x);
    let y = symbol!(y);
    let vars = vec![x.clone(), y.clone()];

    // x (degree 1) vs x² (degree 2)
    let x1 = Expression::symbol(x.clone());
    let x2 = Expression::pow(Expression::symbol(x.clone()), Expression::integer(2));

    let order = MonomialOrder::Grevlex;
    let cmp = order.compare_monomials(&x2, &x1, &vars);

    assert_eq!(
        cmp,
        Ordering::Greater,
        "x² (degree 2) should be greater than x (degree 1)"
    );
}

// Test grevlex with same degree: reverse lexicographic tiebreaker
#[test]
fn test_grevlex_same_degree_reverse_lex() {
    let x = symbol!(x);
    let y = symbol!(y);
    let vars = vec![x.clone(), y.clone()];

    // x² (degree 2) vs xy (degree 2)
    let x2 = Expression::pow(Expression::symbol(x.clone()), Expression::integer(2));
    let xy = Expression::mul(vec![
        Expression::symbol(x.clone()),
        Expression::symbol(y.clone()),
    ]);

    let order = MonomialOrder::Grevlex;
    let cmp = order.compare_monomials(&x2, &xy, &vars);

    // Implementation: compare from right, reversed comparison
    // Position 1 (y): exp1=0, exp2=1; e2.cmp(e1) = Greater → x² > xy
    assert_eq!(
        cmp,
        Ordering::Greater,
        "x² should be greater than xy in grevlex"
    );
}

// Classic grevlex example: x²y vs xy²
#[test]
fn test_grevlex_classic_example() {
    let x = symbol!(x);
    let y = symbol!(y);
    let vars = vec![x.clone(), y.clone()];

    // x²y (degree 3, exponents [2, 1])
    let x2y = Expression::mul(vec![
        Expression::pow(Expression::symbol(x.clone()), Expression::integer(2)),
        Expression::symbol(y.clone()),
    ]);

    // xy² (degree 3, exponents [1, 2])
    let xy2 = Expression::mul(vec![
        Expression::symbol(x.clone()),
        Expression::pow(Expression::symbol(y.clone()), Expression::integer(2)),
    ]);

    let order = MonomialOrder::Grevlex;
    let cmp = order.compare_monomials(&x2y, &xy2, &vars);

    // Implementation: compare from right, reversed
    // Position 1 (y): exp1=1, exp2=2; e2.cmp(e1) = Greater → x²y > xy²? NO
    // Actually: e2=2, e1=1; 2.cmp(1) = Greater, so x²y < xy²? Let me verify...
    // x2y = [2,1], xy2 = [1,2]
    // Compare from right: position 1 first
    // e1=1, e2=2; e2.cmp(e1) = 2.cmp(1) = Greater
    // Return Greater → x²y > xy²? No wait, we return the result...
    //
    // Let me trace the actual code:
    // for (e1, e2) in exp1.iter().zip(exp2.iter()).rev() {
    //     match e2.cmp(e1) { ... }
    // }
    // For x2y=[2,1] vs xy2=[1,2]:
    // Position 1: e1=1, e2=2; e2.cmp(e1) = Greater → return Greater
    // So x2y compared to xy2 gives Greater
    assert_eq!(
        cmp,
        Ordering::Greater, // x²y < xy²
        "x²y should be greater than xy² in this implementation"
    );
}

// Test grevlex with three variables
#[test]
fn test_grevlex_three_variables() {
    let x = symbol!(x);
    let y = symbol!(y);
    let z = symbol!(z);
    let vars = vec![x.clone(), y.clone(), z.clone()];

    let xyz = Expression::mul(vec![
        Expression::symbol(x.clone()),
        Expression::symbol(y.clone()),
        Expression::symbol(z.clone()),
    ]);
    let x2z = Expression::mul(vec![
        Expression::pow(Expression::symbol(x.clone()), Expression::integer(2)),
        Expression::symbol(z.clone()),
    ]);
    let xy2 = Expression::mul(vec![
        Expression::symbol(x.clone()),
        Expression::pow(Expression::symbol(y.clone()), Expression::integer(2)),
    ]);

    let order = MonomialOrder::Grevlex;

    // Based on the implementation's actual behavior
    let cmp1 = order.compare_monomials(&x2z, &xyz, &vars);
    let cmp2 = order.compare_monomials(&xy2, &x2z, &vars);
    let cmp3 = order.compare_monomials(&xy2, &xyz, &vars);

    // Verify transitivity holds
    if cmp1 == Ordering::Less && cmp2 == Ordering::Less {
        assert_eq!(
            cmp3,
            Ordering::Less,
            "Transitivity: if a<b and b<c then a<c"
        );
    } else if cmp1 == Ordering::Greater && cmp2 == Ordering::Greater {
        assert_eq!(
            cmp3,
            Ordering::Greater,
            "Transitivity: if a>b and b>c then a>c"
        );
    }
}

// Test grevlex sorting of degree-2 monomials
// Based on the actual implementation, the correct order is:
// z² < xz < y² < xy < x²
#[test]
fn test_grevlex_sorting() {
    let x = symbol!(x);
    let y = symbol!(y);
    let z = symbol!(z);
    let vars = vec![x.clone(), y.clone(), z.clone()];

    let order = MonomialOrder::Grevlex;

    let y2 = Expression::pow(Expression::symbol(y.clone()), Expression::integer(2));
    let xy = Expression::mul(vec![
        Expression::symbol(x.clone()),
        Expression::symbol(y.clone()),
    ]);
    let x2 = Expression::pow(Expression::symbol(x.clone()), Expression::integer(2));
    let z2 = Expression::pow(Expression::symbol(z.clone()), Expression::integer(2));
    let xz = Expression::mul(vec![
        Expression::symbol(x.clone()),
        Expression::symbol(z.clone()),
    ]);

    let mut monomials = [y2.clone(), xy.clone(), x2.clone(), z2.clone(), xz.clone()];

    monomials.sort_by(|a, b| order.compare_monomials(a, b, &vars));

    // Correct order based on implementation: z² < xz < y² < xy < x²
    assert_eq!(monomials[0], z2, "First should be z²");
    assert_eq!(monomials[1], xz, "Second should be xz");
    assert_eq!(monomials[2], y2, "Third should be y²");
    assert_eq!(monomials[3], xy, "Fourth should be xy");
    assert_eq!(monomials[4], x2, "Fifth should be x²");
}

// Test sorting of degree-3 monomials
// Based on the actual implementation, the correct ascending order is:
// z³ < yz² < xz² < y²z < xyz < x²z < y³ < xy² < x²y < x³
#[test]
fn test_grevlex_vs_implementation_degree_3() {
    let x = symbol!(x);
    let y = symbol!(y);
    let z = symbol!(z);
    let vars = vec![x.clone(), y.clone(), z.clone()];

    let order = MonomialOrder::Grevlex;

    let z3 = Expression::pow(Expression::symbol(z.clone()), Expression::integer(3));
    let x3 = Expression::pow(Expression::symbol(x.clone()), Expression::integer(3));
    let xyz = Expression::mul(vec![
        Expression::symbol(x.clone()),
        Expression::symbol(y.clone()),
        Expression::symbol(z.clone()),
    ]);
    let y3 = Expression::pow(Expression::symbol(y.clone()), Expression::integer(3));
    let x2y = Expression::mul(vec![
        Expression::pow(Expression::symbol(x.clone()), Expression::integer(2)),
        Expression::symbol(y.clone()),
    ]);
    let xy2 = Expression::mul(vec![
        Expression::symbol(x.clone()),
        Expression::pow(Expression::symbol(y.clone()), Expression::integer(2)),
    ]);
    let xz2 = Expression::mul(vec![
        Expression::symbol(x.clone()),
        Expression::pow(Expression::symbol(z.clone()), Expression::integer(2)),
    ]);
    let yz2 = Expression::mul(vec![
        Expression::symbol(y.clone()),
        Expression::pow(Expression::symbol(z.clone()), Expression::integer(2)),
    ]);
    let x2z = Expression::mul(vec![
        Expression::pow(Expression::symbol(x.clone()), Expression::integer(2)),
        Expression::symbol(z.clone()),
    ]);
    let y2z = Expression::mul(vec![
        Expression::pow(Expression::symbol(y.clone()), Expression::integer(2)),
        Expression::symbol(z.clone()),
    ]);

    let mut monomials = vec![
        z3.clone(),
        x3.clone(),
        xyz.clone(),
        y3.clone(),
        x2y.clone(),
        xy2.clone(),
        xz2.clone(),
        yz2.clone(),
        x2z.clone(),
        y2z.clone(),
    ];

    monomials.sort_by(|a, b| order.compare_monomials(a, b, &vars));

    // Correct order based on implementation:
    // z³ < yz² < xz² < y²z < xyz < x²z < y³ < xy² < x²y < x³
    let expected = vec![
        z3.clone(),  // z³
        yz2.clone(), // yz²
        xz2.clone(), // xz²
        y2z.clone(), // y²z
        xyz.clone(), // xyz
        x2z.clone(), // x²z
        y3.clone(),  // y³
        xy2.clone(), // xy²
        x2y.clone(), // x²y
        x3.clone(),  // x³
    ];

    assert_eq!(monomials.len(), expected.len());

    for (i, (actual, expected)) in monomials.iter().zip(expected.iter()).enumerate() {
        assert_eq!(actual, expected, "Position {}: Order mismatch", i);
    }
}

// Test constant monomial (degree 0)
#[test]
fn test_constant_monomial() {
    let x = symbol!(x);
    let y = symbol!(y);
    let vars = vec![x.clone(), y.clone()];

    let one = Expression::integer(1);
    let x1 = Expression::symbol(x.clone());

    let order = MonomialOrder::Grevlex;
    let cmp = order.compare_monomials(&one, &x1, &vars);

    assert_eq!(cmp, Ordering::Less, "Constant should be smallest");
}

// Test with coefficients (should be ignored)
#[test]
fn test_grevlex_with_coefficients() {
    let x = symbol!(x);
    let y = symbol!(y);
    let vars = vec![x.clone(), y.clone()];

    let three_x2 = Expression::mul(vec![
        Expression::integer(3),
        Expression::pow(Expression::symbol(x.clone()), Expression::integer(2)),
    ]);
    let two_xy = Expression::mul(vec![
        Expression::integer(2),
        Expression::symbol(x.clone()),
        Expression::symbol(y.clone()),
    ]);

    let order = MonomialOrder::Grevlex;
    let cmp = order.compare_monomials(&three_x2, &two_xy, &vars);

    assert_eq!(cmp, Ordering::Greater, "x² > xy (coefficients ignored)");
}

// Test reflexivity
#[test]
fn test_grevlex_reflexivity() {
    let x = symbol!(x);
    let y = symbol!(y);
    let vars = vec![x.clone(), y.clone()];

    let xy = Expression::mul(vec![
        Expression::symbol(x.clone()),
        Expression::symbol(y.clone()),
    ]);

    let order = MonomialOrder::Grevlex;
    let cmp = order.compare_monomials(&xy, &xy, &vars);

    assert_eq!(cmp, Ordering::Equal);
}

// Test antisymmetry
#[test]
fn test_grevlex_antisymmetry() {
    let x = symbol!(x);
    let y = symbol!(y);
    let vars = vec![x.clone(), y.clone()];

    let x2 = Expression::pow(Expression::symbol(x.clone()), Expression::integer(2));
    let xy = Expression::mul(vec![
        Expression::symbol(x.clone()),
        Expression::symbol(y.clone()),
    ]);

    let order = MonomialOrder::Grevlex;
    let cmp1 = order.compare_monomials(&x2, &xy, &vars);
    let cmp2 = order.compare_monomials(&xy, &x2, &vars);

    assert_eq!(cmp1, Ordering::Greater);
    assert_eq!(cmp2, Ordering::Less);
}

// Test transitivity
#[test]
fn test_grevlex_transitivity() {
    let x = symbol!(x);
    let y = symbol!(y);
    let z = symbol!(z);
    let vars = vec![x.clone(), y.clone(), z.clone()];

    let xy2 = Expression::mul(vec![
        Expression::symbol(x.clone()),
        Expression::pow(Expression::symbol(y.clone()), Expression::integer(2)),
    ]);
    let x2z = Expression::mul(vec![
        Expression::pow(Expression::symbol(x.clone()), Expression::integer(2)),
        Expression::symbol(z.clone()),
    ]);
    let xyz = Expression::mul(vec![
        Expression::symbol(x.clone()),
        Expression::symbol(y.clone()),
        Expression::symbol(z.clone()),
    ]);

    let order = MonomialOrder::Grevlex;

    let cmp1 = order.compare_monomials(&xyz, &x2z, &vars);
    let cmp2 = order.compare_monomials(&x2z, &xy2, &vars);
    let cmp3 = order.compare_monomials(&xyz, &xy2, &vars);

    // Verify transitivity
    if cmp1 == Ordering::Less && cmp2 == Ordering::Less {
        assert_eq!(cmp3, Ordering::Less, "xyz < x²z < xy² → xyz < xy²");
    }
}