universal_radix_sort 1.0.0

//! Integration tests for Universal Radix Sort.
//!
//! These tests verify the correctness of the Radix Sort implementation
//! across various data types and edge cases.

use universal_radix_sort::{RadixDataType, RadixSort, SortDirection};

#[test]
fn test_integer_sorting_comprehensive() {
    // Test various integer types
    let test_cases: Vec<(Vec<i64>, Vec<i64>)> = vec![
        (vec![5, 2, 8, 1, 9], vec![1, 2, 5, 8, 9]),
        (vec![-5, -2, -8, -1, -9], vec![-9, -8, -5, -2, -1]),
        (vec![0, 0, 0], vec![0, 0, 0]),
        (vec![i64::MAX, i64::MIN, 0], vec![i64::MIN, 0, i64::MAX]),
    ];

    for (input, expected) in test_cases {
        let mut data = input.clone();
        let sorter = RadixSort::<i64>::new(RadixDataType::SignedInteger, SortDirection::Ascending);
        sorter.sort(&mut data).unwrap();
        assert_eq!(data, expected, "Failed for input: {:?}", input);
    }
}

#[test]
fn test_float_sorting_comprehensive() {
    let mut data = vec![
        3.14f64,
        -1.25,
        0.0,
        -0.0,
        f64::INFINITY,
        f64::NEG_INFINITY,
        42.0,
    ];
    let sorter = RadixSort::<f64>::new(RadixDataType::Float, SortDirection::Ascending);
    sorter.sort(&mut data).unwrap();

    // Verify ordering (7 elements total)
    // Index 0: NEG_INFINITY
    assert_eq!(
        data[0],
        f64::NEG_INFINITY,
        "First element should be NEG_INFINITY"
    );

    // Index 1: Negative number (-1.25)
    assert!(
        data[1] < 0.0,
        "Second element should be negative, got {}",
        data[1]
    );

    // Index 2 & 3: Both zeros (0.0 and -0.0, order may vary)
    assert!(
        (data[2] == 0.0 || data[2] == -0.0) && (data[3] == 0.0 || data[3] == -0.0),
        "Index 2 and 3 should both be zeros, got {} and {}",
        data[2],
        data[3]
    );

    // Index 4 & 5: Positive numbers (3.14 and 42.0)
    assert!(data[4] > 0.0, "Index 4 should be positive, got {}", data[4]);
    assert!(data[5] > 0.0, "Index 5 should be positive, got {}", data[5]);

    // Index 6: INFINITY
    assert_eq!(data[6], f64::INFINITY, "Last element should be INFINITY");

    // Verify all elements are in correct order
    for i in 0..data.len() - 1 {
        assert!(
            data[i] <= data[i + 1] || (data[i].is_nan() && data[i + 1].is_nan()),
            "Sort order violated at index {}:{} <= {}",
            i,
            data[i],
            data[i + 1]
        );
    }
}

#[test]
fn test_float_with_nan() {
    // Separate test for NaN handling
    let mut data = vec![3.14f64, f64::NAN, -1.25, 0.5, f64::INFINITY];
    let sorter = RadixSort::<f64>::new(RadixDataType::Float, SortDirection::Ascending);
    sorter.sort(&mut data).unwrap();

    // NaN should be at the end
    assert!(data[4].is_nan(), "NaN should be at the end");

    // Other values should be sorted
    assert_eq!(data[0], -1.25);
    assert_eq!(data[1], 0.5);
    assert_eq!(data[2], 3.14);
    assert_eq!(data[3], f64::INFINITY);
}

#[test]
fn test_string_sorting_comprehensive() {
    let test_cases: Vec<(Vec<String>, Vec<String>)> = vec![
        (
            vec!["banana".into(), "apple".into(), "cherry".into()],
            vec!["apple".into(), "banana".into(), "cherry".into()],
        ),
        (
            vec!["z".into(), "a".into(), "m".into()],
            vec!["a".into(), "m".into(), "z".into()],
        ),
        (
            vec!["".into(), "a".into(), "ab".into()],
            vec!["".into(), "a".into(), "ab".into()],
        ),
    ];

    for (input, expected) in test_cases {
        let mut data = input.clone();
        let sorter = RadixSort::<String>::new(RadixDataType::String, SortDirection::Ascending);
        sorter.sort(&mut data).unwrap();
        assert_eq!(data, expected, "Failed for input: {:?}", input);
    }
}

#[test]
fn test_stability() {
    // Radix sort should be stable
    // We can't easily test this with primitive types, but the algorithm
    // implementation ensures stability through reverse iteration in counting sort
    let mut data = vec![5i64, 3, 5, 1, 3, 5];
    let sorter = RadixSort::<i64>::default();
    sorter.sort(&mut data).unwrap();
    assert_eq!(data, vec![1, 3, 3, 5, 5, 5]);
}

#[test]
fn test_large_dataset() {
    let mut data: Vec<i64> = (0..10000).rev().collect();
    let sorter = RadixSort::<i64>::default();
    sorter.sort(&mut data).unwrap();

    for i in 0..data.len() - 1 {
        assert!(data[i] <= data[i + 1], "Sort failed at index {}", i);
    }
}

#[test]
fn test_descending_order() {
    let mut data = vec![1i64, 2, 3, 4, 5];
    let sorter = RadixSort::<i64>::new(RadixDataType::SignedInteger, SortDirection::Descending);
    sorter.sort(&mut data).unwrap();
    assert_eq!(data, vec![5, 4, 3, 2, 1]);
}

#[test]
fn test_sort_to_vec() {
    let data = vec![5i64, 2, 8, 1, 9];
    let sorter = RadixSort::<i64>::default();
    let sorted = sorter.sort_to_vec(&data).unwrap();

    assert_eq!(sorted, vec![1, 2, 5, 8, 9]);
    assert_eq!(data, vec![5, 2, 8, 1, 9]); // Original unchanged
}