csp-solver 0.4.0

//! Integration tests for [`csp_solver::AssignmentBuilder`].
//!
//! Each test exercises a single ergonomic shape of the bipartite
//! assignment COP wrapper: trivial diagonal, hard pin overrides,
//! penalty-driven unmatching, role groups, brute-force ground truth,
//! node-budget abort, and the two builder-validation error paths.

use csp_solver::{AssignmentError, SENTINEL, assignment};

// ---------------------------------------------------------------------------
// 1. Trivial 3×3 — eye-shape cost matrix, no groups, optimal is the identity
// ---------------------------------------------------------------------------
#[test]
fn simple_3x3_diagonal() {
    let sol = assignment()
        .rows(3)
        .cols(3)
        .cost(|i, k| if i == k { 0.0 } else { 10.0 })
        .unmatch_penalty(100.0)
        .solve()
        .expect("3x3 identity must be solvable");

    assert_eq!(sol.assign, vec![0, 1, 2]);
    assert_eq!(sol.cost, 0.0);
}

// ---------------------------------------------------------------------------
// 2. A pin overrides what would otherwise be the optimal assignment
// ---------------------------------------------------------------------------
#[test]
fn with_pin_overrides_cost() {
    // Diagonal-best matrix: row 0 → col 0 is the cheapest unconstrained
    // pick. Force row 0 to col 2 with a pin and verify the solver
    // honours it (and re-routes the rest of the assignment around it).
    let sol = assignment()
        .rows(3)
        .cols(3)
        .cost(|i, k| if i == k { 0.0 } else { 10.0 })
        .unmatch_penalty(1_000.0)
        .pin(0, 2)
        .solve()
        .expect("pin must not make a 3x3 problem infeasible");

    assert_eq!(sol.assign[0], 2, "row 0 must respect the hard pin to col 2");

    // Every column should be visited exactly once (no row falls back
    // to SENTINEL because the unmatch penalty dominates any reroute).
    let mut sorted = sol.assign.clone();
    sorted.sort();
    assert_eq!(sorted, vec![0, 1, 2], "all rows must be matched");
}

// ---------------------------------------------------------------------------
// 3. Unmatch penalty cheaper than every cell — both rows go to SENTINEL
// ---------------------------------------------------------------------------
#[test]
fn unmatch_when_penalty_low() {
    let sol = assignment()
        .rows(2)
        .cols(3)
        .cost(|_, _| 1_000.0)
        .unmatch_penalty(1.0)
        .solve()
        .expect("unmatching must always be feasible");

    assert_eq!(
        sol.assign,
        vec![SENTINEL, SENTINEL],
        "both rows must opt into the cheaper unmatch sentinel"
    );
    assert_eq!(sol.cost, 2.0);
}

// ---------------------------------------------------------------------------
// 4. Role groups: rows in group 0 may only match cols in group 0, etc.
// ---------------------------------------------------------------------------
#[test]
fn role_groups_separate_assignments() {
    // Four rows, four cols, split into two role groups of two each.
    // Costs are uniform, so the search has nothing to optimize beyond
    // group membership — the structural assertion is what we care
    // about.
    let row_groups = [0u8, 0, 1, 1];
    let col_groups = [0u8, 0, 1, 1];

    let sol = assignment()
        .rows(4)
        .cols(4)
        .cost(|_, _| 1.0)
        .row_group(|i| row_groups[i])
        .col_group(|k| col_groups[k])
        .unmatch_penalty(1_000.0)
        .solve()
        .expect("4x4 group-partitioned problem must be solvable");

    for (row, &assigned_col) in sol.assign.iter().enumerate() {
        assert_ne!(
            assigned_col, SENTINEL,
            "row {row} should not unmatch when a same-group column is available"
        );
        let col = assigned_col as usize;
        assert_eq!(
            row_groups[row], col_groups[col],
            "row {row} (group {}) was matched to col {col} (group {})",
            row_groups[row], col_groups[col],
        );
    }

    // Both groups should saturate their two-column capacity.
    let mut sorted = sol.assign.clone();
    sorted.sort();
    assert_eq!(sorted, vec![0, 1, 2, 3]);
}

// ---------------------------------------------------------------------------
// 5. Brute-force ground truth: 5 random 4×4 matrices, deterministic LCG
// ---------------------------------------------------------------------------
#[test]
fn brute_force_match_4x4() {
    const N: usize = 4;
    const TRIALS: usize = 5;

    let mut rng = Lcg::new(0xC0FFEE_u64);

    for trial in 0..TRIALS {
        let matrix: Vec<f64> = (0..N * N).map(|_| rng.next_unit() * 100.0).collect();

        // Brute-force minimum over all N! = 24 permutations.
        let mut perm: Vec<usize> = (0..N).collect();
        let mut best = f64::INFINITY;
        permute(&mut perm, 0, &mut |p| {
            let total: f64 = (0..N).map(|i| matrix[i * N + p[i]]).sum();
            if total < best {
                best = total;
            }
        });

        let sol = assignment()
            .rows(N)
            .cols(N)
            .cost(|i, k| matrix[i * N + k])
            .unmatch_penalty(1e9) // make unmatching prohibitively expensive
            .solve()
            .unwrap_or_else(|e| panic!("trial {trial}: builder failed: {e}"));

        // Costs may differ from `best` only by floating-point noise
        // (rounding from the bound check + summation order). Assert
        // a tight tolerance and bail otherwise.
        let delta = (sol.cost - best).abs();
        assert!(
            delta < 1e-9,
            "trial {trial}: builder cost {} disagrees with brute-force best {} (delta = {delta})",
            sol.cost,
            best,
        );

        // Sanity: every row must be matched (no SENTINEL leakage).
        assert!(
            sol.assign.iter().all(|&v| v != SENTINEL),
            "trial {trial}: rows should match under prohibitive unmatch penalty"
        );
    }
}

// ---------------------------------------------------------------------------
// 6. Node-budget exhaustion before any leaf is a typed, unambiguous error.
// ---------------------------------------------------------------------------
#[test]
fn node_budget_exhausted_returns_budget_exceeded() {
    // Scoring even one complete assignment on a 6×6 requires descending
    // six search frames (the budget is checked once per frame, before the
    // node is counted), so a one-node budget aborts at the second frame —
    // long before any leaf. With no best-so-far solution to hand back, the
    // B&B path must surface the dedicated `BudgetExceeded` variant: not
    // `Infeasible` (the problem is trivially satisfiable via the SENTINEL
    // escape) and not a silent `Ok`. This pins the R8 disambiguation that
    // replaced the earlier both-outcomes-blessed contract. Forced via
    // `solve_branch_and_bound` — this instance is group-free/pin-free, so
    // plain `.solve()` would dispatch to the budget-free LAP path.
    let result = assignment()
        .rows(6)
        .cols(6)
        .cost(|_, _| 1.0)
        .unmatch_penalty(2.0)
        .node_budget(Some(1))
        .solve_branch_and_bound();

    assert!(
        matches!(result, Err(AssignmentError::BudgetExceeded)),
        "a one-node budget on a 6x6 must return BudgetExceeded, got {result:?}"
    );
}

// ---------------------------------------------------------------------------
// 7. Validation: solving without dimensions returns DimensionsNotSet
// ---------------------------------------------------------------------------
#[test]
fn dimensions_not_set_returns_err() {
    let err = assignment()
        .solve()
        .expect_err("a builder with no dimensions cannot solve");
    assert!(matches!(err, AssignmentError::DimensionsNotSet));
}

// ---------------------------------------------------------------------------
// 8. Validation: solving without cost returns CostNotSet
// ---------------------------------------------------------------------------
#[test]
fn cost_not_set_returns_err() {
    let err = assignment()
        .rows(2)
        .cols(2)
        .solve()
        .expect_err("a builder with no cost matrix cannot solve");
    assert!(matches!(err, AssignmentError::CostNotSet));
}

// ===========================================================================
// Helpers
// ===========================================================================

/// Tiny linear-congruential generator. Used in lieu of pulling in
/// `rand` for a single deterministic test fixture; the constants are
/// the standard Numerical Recipes triple.
struct Lcg {
    state: u64,
}

impl Lcg {
    fn new(seed: u64) -> Self {
        Self { state: seed }
    }

    fn next_u64(&mut self) -> u64 {
        // Numerical Recipes constants — adequate for fixture
        // generation, not cryptographic quality.
        self.state = self
            .state
            .wrapping_mul(6364136223846793005)
            .wrapping_add(1442695040888963407);
        self.state
    }

    fn next_unit(&mut self) -> f64 {
        // Top 53 bits → uniform in [0, 1).
        ((self.next_u64() >> 11) as f64) / ((1u64 << 53) as f64)
    }
}

/// Heap's-algorithm-style permutation generator: invokes `f` once per
/// permutation of `perm`.
fn permute<F: FnMut(&[usize])>(perm: &mut Vec<usize>, k: usize, f: &mut F) {
    if k == perm.len() {
        f(perm);
        return;
    }
    for i in k..perm.len() {
        perm.swap(k, i);
        permute(perm, k + 1, f);
        perm.swap(k, i);
    }
}