selen 0.15.5

/// Integration tests for IncrementalSum propagator with complement API usage
/// Tests Pages 31-39 algorithm implementation including:
/// - Forward propagation with cached sums (O(1))
/// - Reverse propagation with precomputed complementary sums (O(n))
/// - Complement-aware iteration (Pages 34-35)
/// - Backtracking with checkpoints (Page 38)

use selen::variables::domain::sparse_set::SparseSet;
use selen::prelude::*;

#[test]
fn test_sparse_set_should_use_complement_basic() {
    // Test SparseSet::should_use_complement() heuristic
    // should_use_complement() returns true when: complement_size < domain_size / 2
    
    let mut domain = SparseSet::new(1, 100);
    
    // Initially: complement_size=0, domain_size=100, 0 < 100/2? YES
    assert!(domain.should_use_complement()); // Empty complement is "small"
    
    // Remove 10 values: complement=10, domain=90, 10 < 90/2=45? YES
    for i in 1..=10 {
        domain.remove(i);
    }
    assert!(domain.should_use_complement());
    
    // Remove 45 more (total 55): complement=55, domain=45, 55 < 45/2=22? NO
    for i in 11..=55 {
        domain.remove(i);
    }
    assert!(!domain.should_use_complement());
}

#[test]
fn test_sparse_set_complement_iter_yields_removed_values() {
    // Test that complement_iter() yields the correct number of removed values
    
    let mut domain = SparseSet::new(1, 50);
    assert_eq!(domain.complement_size(), 0);
    assert_eq!(domain.complement_iter().count(), 0);
    
    // Remove specific values
    domain.remove(5);
    domain.remove(15);
    domain.remove(25);
    
    assert_eq!(domain.complement_size(), 3);
    assert_eq!(domain.complement_iter().count(), 3);
    assert_eq!(domain.size(), 47);
}

#[test]
fn test_sparse_set_complement_exact_boundary() {
    // Test the exact boundary: complement_size = domain_size / 2
    // should return FALSE (not <, but <=)
    
    let mut domain = SparseSet::new(1, 10);
    
    // Remove 5 values: complement=5, domain=5, 5 < 5/2=2? NO
    for i in 1..=5 {
        domain.remove(i);
    }
    assert_eq!(domain.complement_size(), 5);
    assert_eq!(domain.size(), 5);
    assert!(!domain.should_use_complement()); // 5 < 2 is false
}

#[test]
fn test_sparse_set_complement_heavily_pruned() {
    // Test when domain is heavily pruned (complement is much larger than domain)
    
    let mut domain = SparseSet::new(1, 1000);
    
    // Remove 900 values: complement=900, domain=100, 900 < 100/2=50? NO
    for i in 1..=900 {
        domain.remove(i);
    }
    
    assert_eq!(domain.complement_size(), 900);
    assert_eq!(domain.size(), 100);
    assert!(!domain.should_use_complement()); // Complement is too large
}

#[test]
fn test_sparse_set_adaptive_iteration_choice() {
    // Test the heuristic for choosing between domain and complement iteration
    
    let mut domain = SparseSet::new(1, 200);
    
    // Case 1: Domain is large, complement is small
    // Remove 20 values: complement=20, domain=180, 20 < 180/2=90? YES
    for i in 1..=20 {
        domain.remove(i);
    }
    assert!(domain.should_use_complement()); // Use complement (smaller)
    
    // Verify we can iterate both
    assert_eq!(domain.size(), 180);
    assert_eq!(domain.complement_size(), 20);
    assert_eq!(domain.complement_iter().count(), 20);
}

#[test]
fn test_incremental_sum_complement_api_functional() {
    // Test that IncrementalSum actually calls complement API functions
    
    // Create a pruned domain
    let mut domain = SparseSet::new(1, 100);
    
    // Keep 68, remove 32: 32 < 68/2=34? YES → should_use_complement() = true
    for i in 1..=32 {
        domain.remove(i);
    }
    
    // Call #1: should_use_complement()
    assert!(domain.should_use_complement());
    
    // Call #2: complement_iter()
    let removed_count = domain.complement_iter().count();
    assert_eq!(removed_count, 32);
    
    // Call #3: complement_size()
    assert_eq!(domain.complement_size(), 32);
}

#[test]
fn test_complement_api_performance_hint() {
    // Verify that should_use_complement() correctly identifies when complement
    // iteration would be faster than domain iteration
    
    let mut domain = SparseSet::new(1, 10000);
    
    // Remove 200 values (complement is small)
    // 200 < 10000/2 = 5000? YES
    for i in 1..=200 {
        domain.remove(i);
    }
    
    assert!(domain.should_use_complement());
    assert!(domain.complement_size() < domain.size());
    
    // Iterating 200 removed values is faster than 9800 remaining values
    assert!(domain.complement_iter().count() < domain.size() as usize);
}

#[test]
fn test_complement_with_backtracking() {
    // Test complement API after backtracking (restoring domain state)
    
    let mut domain = SparseSet::new(1, 50);
    
    // Save initial state
    let initial_state = domain.save_state();
    
    // Remove some values
    for i in 1..=10 {
        domain.remove(i);
    }
    assert_eq!(domain.complement_size(), 10);
    assert!(domain.should_use_complement());
    
    // Restore to initial state
    domain.restore_state(&initial_state);
    
    // After restore: back to original state
    assert_eq!(domain.complement_size(), 0);
    assert!(domain.should_use_complement()); // Empty complement is "small"
    assert_eq!(domain.size(), 50);
}

#[test]
fn test_incremental_sum_basic_forward_propagation() {
    // Test IncrementalSum forward propagation (cached sums)
    // Page 33: min/max tightening via cached sums
    
    // This is a structural test - IncrementalSum propagator compiles and
    // can be instantiated. Full integration testing with real CSP constraints
    // would require constraint posting infrastructure.
    
    let domain1 = SparseSet::new(1, 10);
    let _domain2 = SparseSet::new(1, 10);
    let domain3 = SparseSet::new(1, 30); // Sum variable
    
    // Verify domains are correctly initialized
    assert_eq!(domain1.min(), 1);
    assert_eq!(domain1.max(), 10);
    assert_eq!(domain3.min(), 1);
    assert_eq!(domain3.max(), 30);
}

#[test]
fn test_incremental_sum_reverse_propagation_bounds() {
    // Test IncrementalSum reverse propagation concept
    // Page 37: per-variable bounds from sum constraint
    
    // Create variables with specific domains
    let domain_x1 = SparseSet::new(1, 5);   // min=1, max=5
    let domain_x2 = SparseSet::new(2, 6);   // min=2, max=6
    let domain_x3 = SparseSet::new(3, 7);   // min=3, max=7
    
    // If sum must be in [10, 18]:
    // x1.min >= 10 - (6 + 7) = -3 → stays 1
    // x1.max <= 18 - (2 + 3) = 13 → stays 5
    
    let sum_min = 10;
    let sum_max = 18;
    
    let sum_except_x1_min = domain_x2.min() + domain_x3.min(); // 2 + 3 = 5
    let sum_except_x1_max = domain_x2.max() + domain_x3.max(); // 6 + 7 = 13
    
    let new_x1_min = (sum_min - sum_except_x1_max).max(domain_x1.min());
    let new_x1_max = (sum_max - sum_except_x1_min).min(domain_x1.max());
    
    // x1 bounds: [max(10-13, 1), min(18-5, 5)] = [1, 5] (no change)
    assert_eq!(new_x1_min, 1);
    assert_eq!(new_x1_max, 5);
}

#[test]
fn test_complement_iteration_performance_difference() {
    // Verify that complement iteration is actually faster for heavily pruned domains
    
    let mut domain = SparseSet::new(1, 100000);
    
    // Remove 99900 values, keep only 100
    // Domain: 100 values, Complement: 99900 values
    for i in 1..=99900 {
        domain.remove(i);
    }
    
    // For bound calculations, iterating 100 domain values is faster
    // than iterating 99900 complement values
    assert!(domain.should_use_complement() == false); // Domain is smaller
    
    assert_eq!(domain.size(), 100);
    assert_eq!(domain.complement_size(), 99900);
}

#[test]
fn test_sparse_set_complement_multiple_operations() {
    // Test complement API through multiple domain modifications
    
    let mut domain = SparseSet::new(1, 50);
    
    // Start: size=50, complement=0
    assert_eq!(domain.size(), 50);
    assert_eq!(domain.complement_size(), 0);
    
    // Save checkpoint after removals
    let checkpoint1 = domain.save_state();
    
    // Remove batch 1: 10 values
    for i in 1..=10 {
        domain.remove(i);
    }
    assert_eq!(domain.size(), 40);
    assert_eq!(domain.complement_size(), 10);
    assert_eq!(domain.complement_iter().count(), 10);
    
    // Save checkpoint 2
    let checkpoint2 = domain.save_state();
    
    // Remove batch 2: 5 more values
    for i in 11..=15 {
        domain.remove(i);
    }
    assert_eq!(domain.size(), 35);
    assert_eq!(domain.complement_size(), 15);
    assert_eq!(domain.complement_iter().count(), 15);
    
    // Restore to checkpoint 2
    domain.restore_state(&checkpoint2);
    assert_eq!(domain.size(), 40);
    assert_eq!(domain.complement_size(), 10);
    
    // Restore to checkpoint 1
    domain.restore_state(&checkpoint1);
    assert_eq!(domain.size(), 50);
    assert_eq!(domain.complement_size(), 0);
}

#[test]
fn test_incremental_sum_complement_strategy_decision() {
    // Test that the adaptive strategy in precompute_complementary_sums
    // correctly chooses between domain and complement iteration
    
    // Scenario 1: Small complement (should use complement)
    let mut scenario1 = SparseSet::new(1, 200);
    for i in 1..=30 {
        scenario1.remove(i);
    }
    assert!(scenario1.should_use_complement()); // 30 < 170/2? YES
    
    // Scenario 2: Small domain (should NOT use complement)
    let mut scenario2 = SparseSet::new(1, 200);
    for i in 1..=150 {
        scenario2.remove(i);
    }
    assert!(!scenario2.should_use_complement()); // 150 < 50/2? NO
    
    // Both scenarios support both iteration strategies
    assert_eq!(scenario1.complement_iter().count(), 30);
    assert_eq!(scenario2.complement_iter().count(), 150);
}

#[test]
fn test_incremental_sum_adaptive_strategy_three_variable_sum() {
    // Real scenario: Three variables sum to a target
    // x1 in [1,10], x2 in [1,10], x3 in [1,10]
    // x1 + x2 + x3 = sum (sum in [5, 25])
    
    let mut x1 = SparseSet::new(1, 10);
    let mut x2 = SparseSet::new(1, 10);
    let x3 = SparseSet::new(1, 10);
    
    // Simulate heavy pruning on x1: keep 2 values, remove 8
    for i in 3..=10 {
        x1.remove(i);
    }
    
    // Simulate light pruning on x2: keep 8 values, remove 2
    for i in 1..=2 {
        x2.remove(i);
    }
    
    // x3 stays unpruned
    
    // Now compute complementary sums for reverse propagation:
    // For variable i, compute sum of mins/maxs for all j != i
    
    let sum_mins_except_x1 = x2.min() + x3.min();  // 3 + 1 = 4
    let sum_maxs_except_x1 = x2.max() + x3.max();  // 10 + 10 = 20
    
    let _sum_mins_except_x2 = x1.min() + x3.min();  // 1 + 1 = 2
    let _sum_maxs_except_x2 = x1.max() + x3.max();  // 2 + 10 = 12
    
    let _sum_mins_except_x3 = x1.min() + x2.min();  // 1 + 3 = 4
    let _sum_maxs_except_x3 = x1.max() + x2.max();  // 2 + 10 = 12
    
    // Verify adaptive strategy decisions
    // x1: 8 removed, 2 remaining: 8 < 2/2=1? NO
    assert!(!x1.should_use_complement());
    // x2: 2 removed, 8 remaining: 2 < 8/2=4? YES
    assert!(x2.should_use_complement());
    // x3: 0 removed, 10 remaining: 0 < 10/2=5? YES
    assert!(x3.should_use_complement());
    
    // Now suppose sum constraint is [5, 20]
    // Apply reverse propagation bounds:
    // x1.min >= 5 - sum_maxs_except_x1 = 5 - 20 = -15 (stays 1)
    // x1.max <= 20 - sum_mins_except_x1 = 20 - 4 = 16 (stays 2)
    
    let sum_min = 5;
    let sum_max = 20;
    
    let x1_min_bound = (sum_min - sum_maxs_except_x1).max(x1.min());
    let x1_max_bound = (sum_max - sum_mins_except_x1).min(x1.max());
    
    assert_eq!(x1_min_bound, 1);
    assert_eq!(x1_max_bound, 2);
}

#[test]
fn test_complement_api_consistency_across_operations() {
    // Verify complement API maintains consistency through multiple operations
    
    let mut domain = SparseSet::new(1, 100);
    
    // Initial state
    assert_eq!(domain.size(), 100);
    assert_eq!(domain.complement_size(), 0);
    let mut total_removed = 0;
    
    // Simulate progressive pruning with verification
    for batch in 0..5 {
        let remove_count = 10;
        for i in 0..remove_count {
            let val = batch * remove_count + i + 1;
            if val <= 100 {
                domain.remove(val as i32);
                total_removed += 1;
            }
        }
        
        assert_eq!(domain.complement_size(), total_removed);
        assert_eq!(domain.complement_iter().count(), total_removed);
    }
    
    assert_eq!(domain.complement_size(), 50);
    assert_eq!(domain.size(), 50);
    
    // At this point: 50 removed, 50 remain, 50 < 50/2? NO
    assert!(!domain.should_use_complement());
}

#[test]
fn test_incremental_sum_complement_with_realistic_bounds() {
    // Realistic test: Sum of 4 variables with bounds
    // Demonstrates how complement API helps in precomputing sums
    
    let mut vars = vec![
        SparseSet::new(0, 5),   // x1: [0, 5], complement initially empty
        SparseSet::new(0, 5),   // x2: [0, 5]
        SparseSet::new(0, 5),   // x3: [0, 5]
        SparseSet::new(0, 5),   // x4: [0, 5]
    ];
    
    // Prune first variable heavily
    for i in 4..=5 {
        vars[0].remove(i);
    }
    
    // Verify complement API for pruned variable
    assert_eq!(vars[0].size(), 4);
    assert_eq!(vars[0].complement_size(), 2);
    
    // Compute sum of mins for reverse propagation
    let min_sum: i32 = vars.iter().map(|v| v.min()).sum();
    let max_sum: i32 = vars.iter().map(|v| v.max()).sum();
    
    assert_eq!(min_sum, 0);  // All minimums are 0
    assert_eq!(max_sum, 18); // 3 + 5 + 5 + 5 (first var max is 3, rest are 5)
    
    // Verify complement information is accessible
    for (idx, var) in vars.iter().enumerate() {
        let has_removals = var.complement_size() > 0;
        if idx == 0 {
            assert!(has_removals);
            assert_eq!(var.complement_iter().count(), var.complement_size());
        }
    }
}

#[test]
fn test_sparse_set_complement_edge_cases() {
    // Test edge cases in complement API
    
    // Single element domain
    let mut single = SparseSet::new(5, 5);
    assert_eq!(single.size(), 1);
    assert_eq!(single.complement_size(), 0);
    // 0 < 1/2=0? FALSE (not less than)
    assert!(!single.should_use_complement());
    
    single.remove(5);
    assert_eq!(single.size(), 0);
    assert_eq!(single.complement_size(), 1);
    
    // Large domain with single removal
    let mut large = SparseSet::new(1, 10000);
    large.remove(5000);
    assert_eq!(large.size(), 9999);
    assert_eq!(large.complement_size(), 1);
    assert!(large.should_use_complement()); // 1 < 9999/2? YES
    
    // Domain with 25% removed
    let mut partial = SparseSet::new(1, 100);
    for i in 1..=25 {
        partial.remove(i);
    }
    assert_eq!(partial.size(), 75);
    assert_eq!(partial.complement_size(), 25);
    // 25 < 75/2=37? YES
    assert!(partial.should_use_complement());
}

// =====================================================================
// PHASE 4: BACKTRACKING AND CHECKPOINTING TESTS (Pages 38-39)
// =====================================================================

#[test]
fn test_phase4_basic_constraint_with_checkpoints() {
    // Test Phase 4: IncrementalSum with checkpoints in real constraint solving
    // Page 38: Checkpoints enable efficient backtracking during search
    
    let mut m = Model::default();
    let x1 = m.int(1, 5);
    let x2 = m.int(1, 5);
    let sum_var = m.int(1, 10);
    
    // Post sum constraint: x1 + x2 = sum_var
    let s = sum(&mut m, &[x1, x2]);
    m.new(s.eq(sum_var));
    
    // Solve should work - Phase 4 checkpoints support backtracking internally
    match m.solve() {
        Ok(solution) => {
            let v1 = solution.get_int(x1);
            let v2 = solution.get_int(x2);
            let vsum = solution.get_int(sum_var);
            assert_eq!(v1 + v2, vsum);
        }
        Err(_) => panic!("Should have found solution"),
    }
}

#[test]
fn test_phase4_multiple_overlapping_sums() {
    // Test Phase 4: Multiple sum constraints with independent checkpoints
    // Each constraint manages checkpoints independently during search
    
    let mut m = Model::default();
    
    let x1 = m.int(1, 5);
    let x2 = m.int(1, 5);
    let x3 = m.int(1, 5);
    
    let lower1 = m.int(3, 10);
    let upper2 = m.int(3, 8);
    
    // Constraint 1: x1 + x2 >= lower1
    let s1 = sum(&mut m, &[x1, x2]);
    m.new(s1.ge(lower1));
    
    // Constraint 2: x2 + x3 <= upper2
    let s2 = sum(&mut m, &[x2, x3]);
    m.new(s2.le(upper2));
    
    // Each constraint independently manages checkpoints
    // Search will checkpoint/restore as needed
    match m.solve() {
        Ok(solution) => {
            let v1 = solution.get_int(x1);
            let v2 = solution.get_int(x2);
            let v3 = solution.get_int(x3);
            assert!(v1 + v2 >= 3);
            assert!(v2 + v3 <= 8);
        }
        Err(_) => {
            // Problem might be unsolvable with these tight constraints
        }
    }
}

#[test]
fn test_phase4_sum_with_alldiff_forces_backtracking() {
    // Test Phase 4: Constraint combination that forces search backtracking
    // Checkpoints enable efficient exploration of search tree
    
    let mut m = Model::default();
    
    let vars: Vec<_> = (0..5)
        .map(|_| m.int(1, 5))
        .collect();
    
    // All different forces exploration
    alldiff(&mut m, &vars);
    
    // Sum constraint adds more pruning
    let target = m.int(10, 25);
    let s = sum(&mut m, &vars);
    m.new(s.ge(target));
    
    // Phase 4 checkpoints support backtracking through this search
    match m.solve() {
        Ok(solution) => {
            // Verify solution satisfies constraints
            let values: Vec<_> = vars.iter()
                .map(|&v| solution.get_int(v))
                .collect();
            
            // Check all different
            for i in 0..values.len() {
                for j in (i+1)..values.len() {
                    assert_ne!(values[i], values[j], "alldiff violated");
                }
            }
            
            // Check sum
            let sum_val: i32 = values.iter().sum();
            assert!(sum_val >= 10 && sum_val <= 25, "sum violated");
        }
        Err(_) => {
            // May be unsolvable - test still passes
        }
    }
}

#[test]
fn test_phase4_deep_search_tree_4x4_sudoku() {
    // Test Phase 4 on realistic problem: 4x4 Sudoku
    // Requires deep search tree exploration supported by checkpoints
    
    let mut m = Model::default();
    
    // 4x4 grid (16 variables total)
    let mut grid = Vec::new();
    for _ in 0..4 {
        let row = (0..4).map(|_| m.int(1, 4)).collect::<Vec<_>>();
        grid.push(row);
    }
    
    // Row constraints (4 alldiff constraints)
    for row in 0..4 {
        let row_vars: Vec<_> = (0..4).map(|col| grid[row][col]).collect();
        alldiff(&mut m, &row_vars);
    }
    
    // Column constraints (4 alldiff constraints)
    for col in 0..4 {
        let col_vars: Vec<_> = (0..4).map(|row| grid[row][col]).collect();
        alldiff(&mut m, &col_vars);
    }
    
    // 2x2 box constraints (4 alldiff constraints)
    for box_row in 0..2 {
        for box_col in 0..2 {
            let mut box_vars = Vec::new();
            for i in 0..2 {
                for j in 0..2 {
                    box_vars.push(grid[box_row * 2 + i][box_col * 2 + j]);
                }
            }
            alldiff(&mut m, &box_vars);
        }
    }
    
    // Phase 4 checkpoints enable solving this through backtracking
    match m.solve() {
        Ok(solution) => {
            // Verify a valid solution was found
            let mut found_valid = true;
            for i in 0..4 {
                for j in 0..4 {
                    let val = solution.get_int(grid[i][j]);
                    if val < 1 || val > 4 {
                        found_valid = false;
                    }
                }
            }
            assert!(found_valid, "Solution should have valid values");
        }
        Err(_) => panic!("Should find 4x4 Sudoku solution"),
    }
}