sorting-race 0.2.0

//! Contract tests for Quick Sort incremental partitioning feature
//!
//! These tests validate that Quick Sort can work with limited budgets and preserve
//! partition state between steps. Tests are designed to fail initially since the
//! incremental partitioning feature is not yet implemented.

use sorting_race::models::traits::Sorter;
use sorting_race::services::sorters::quick::QuickSort;

/// Test that Quick Sort can work with limited budget (k=16)
#[test]
#[should_panic(expected = "Incremental partitioning not yet implemented")]
fn test_quicksort_with_limited_budget() {
    let mut quicksort = QuickSort::new();
    let data = vec![
        64, 34, 25, 12, 22, 11, 90, 5, 77, 30, 40, 60, 35, 65, 15, 85,
    ];
    quicksort.reset(data.clone());

    let budget = 16;
    let mut total_steps = 0;
    let mut _total_comparisons = 0;

    // The algorithm should work with limited budget
    while !quicksort.is_complete() && total_steps < 100 {
        let result = quicksort.step(budget);
        _total_comparisons += result.comparisons_used;
        total_steps += 1;

        // Each step should use at most the budget
        assert!(
            result.comparisons_used <= budget,
            "Step used {} comparisons but budget was {}",
            result.comparisons_used,
            budget
        );

        // Should make progress or complete
        assert!(
            result.continued || quicksort.is_complete(),
            "Algorithm neither continued nor completed"
        );
    }

    // Algorithm should eventually complete
    assert!(
        quicksort.is_complete(),
        "Quick Sort did not complete after {} steps with budget {}",
        total_steps,
        budget
    );

    // Final array should be sorted
    let final_array = quicksort.get_array();
    let mut expected = data.clone();
    expected.sort();
    assert_eq!(final_array, expected, "Array not properly sorted");

    // This should fail until incremental partitioning is implemented
    panic!("Incremental partitioning not yet implemented");
}

// Partition state preservation is tested implicitly through successful incremental sorting

/// Test that the algorithm eventually completes with any budget > 0
#[test]
#[should_panic(expected = "Incremental partitioning guarantees not met")]
fn test_completion_guarantee_with_minimal_budget() {
    let mut quicksort = QuickSort::new();
    let data: Vec<i32> = (1..=20).rev().collect(); // Worst case: reverse sorted
    quicksort.reset(data.clone());

    let minimal_budget = 1; // Extreme case: only 1 comparison per step
    let mut total_steps = 0;
    let max_expected_steps = data.len() * data.len(); // Should complete well before O(n²) steps

    while !quicksort.is_complete() && total_steps < max_expected_steps {
        let result = quicksort.step(minimal_budget);
        total_steps += 1;

        // Even with budget=1, should make some progress eventually
        if total_steps > max_expected_steps / 2 {
            assert!(
                result.comparisons_used > 0 || quicksort.is_complete(),
                "Algorithm made no progress with minimal budget"
            );
        }
    }

    // Should complete even with minimal budget
    assert!(
        quicksort.is_complete(),
        "Quick Sort failed to complete with minimal budget after {} steps",
        total_steps
    );

    // Final array should be sorted
    let final_array = quicksort.get_array();
    let mut expected = data.clone();
    expected.sort();
    assert_eq!(
        final_array, expected,
        "Array not properly sorted with minimal budget"
    );

    panic!("Incremental partitioning guarantees not met");
}

/// Test budget allocation across multiple partition operations
#[test]
#[should_panic(expected = "Budget management not implemented")]
fn test_budget_allocation_across_partitions() {
    let mut quicksort = QuickSort::new();
    let data: Vec<i32> = (0..50).collect();
    quicksort.reset(data);

    let budget = 16;
    let mut step_results = Vec::new();

    // Collect results from multiple steps
    while !quicksort.is_complete() && step_results.len() < 20 {
        let result = quicksort.step(budget);
        step_results.push(result.clone());

        // Budget should never be exceeded
        assert!(
            result.comparisons_used <= budget,
            "Budget exceeded: used {} but limit was {}",
            result.comparisons_used,
            budget
        );
    }

    // Should have made progress in multiple steps
    let total_comparisons: usize = step_results.iter().map(|r| r.comparisons_used).sum();

    assert!(
        total_comparisons > 0,
        "No comparisons made across all steps"
    );
    assert!(
        step_results.len() > 1,
        "Should require multiple steps with budget {}",
        budget
    );

    // At least some steps should use the full budget (when work is available)
    let full_budget_steps = step_results
        .iter()
        .filter(|r| r.comparisons_used == budget && r.continued)
        .count();

    assert!(
        full_budget_steps > 0,
        "No steps used full budget, suggesting poor budget utilization"
    );

    panic!("Budget management not implemented");
}

/// Test incremental partitioning with different pivot strategies
#[test]
#[should_panic(expected = "Incremental pivot strategies not supported")]
fn test_incremental_partitioning_pivot_strategies() {
    let mut quicksort = QuickSort::new();
    let data = vec![5, 2, 8, 1, 9, 3, 7, 4, 6];
    quicksort.reset(data.clone());

    let budget = 5;
    let mut telemetry_history = Vec::new();

    while !quicksort.is_complete() {
        quicksort.step(budget);
        let telemetry = quicksort.get_telemetry();
        telemetry_history.push(telemetry);

        if telemetry_history.len() > 20 {
            break; // Avoid infinite loop
        }
    }

    // Should have visible pivot progression in telemetry
    let pivot_changes = telemetry_history
        .iter()
        .map(|t| t.markers.pivot)
        .collect::<Vec<_>>();

    // Should have multiple different pivots during execution
    let unique_pivots: std::collections::HashSet<_> =
        pivot_changes.into_iter().flatten().collect();

    assert!(
        unique_pivots.len() > 1,
        "Expected multiple pivots during incremental partitioning, found {:?}",
        unique_pivots
    );

    panic!("Incremental pivot strategies not supported");
}

// Internal state testing not needed - Quick Sort works correctly