universal_radix_sort 1.0.0

//! Integer-specific Radix Sort implementation.
//!
//! This module provides optimized radix sorting for integer types using
//! Least Significant Byte (LSB) first processing.

use crate::{RadixResult, RadixSort, RadixSortable};

impl<T> RadixSort<T>
where
    T: RadixSortable,
{
    /// Performs radix sort on integer types.
    ///
    /// Uses LSB-first counting sort for each byte position.
    ///
    /// # Arguments
    ///
    /// * `slice` - The mutable slice of integers to sort
    ///
    /// # Returns
    ///
    /// `Ok(())` on success
    pub(crate) fn sort_integers(&self, slice: &mut [T]) -> RadixResult<()> {
        if slice.len() <= 1 {
            return Ok(());
        }

        let key_size = T::key_size();
        let mut buffer: Vec<T> = Vec::with_capacity(slice.len());
        unsafe {
            buffer.set_len(slice.len());
        }

        // Convert to radix keys
        let mut keys: Vec<T::RadixKey> = slice.iter().map(|v| T::to_radix_key(v.clone())).collect();
        let mut key_buffer: Vec<T::RadixKey> = Vec::with_capacity(keys.len());
        unsafe {
            key_buffer.set_len(keys.len());
        }

        // LSB-first radix sort on keys
        for byte_index in 0..key_size {
            self.counting_sort_by_byte(&mut keys, &mut key_buffer, byte_index);
            keys.swap_with_slice(&mut key_buffer);
        }

        // Convert back to original values
        for (i, key) in keys.iter().enumerate() {
            slice[i] = T::from_radix_key(*key);
        }

        Ok(())
    }

    /// Counting sort implementation for a single byte position.
    ///
    /// # Arguments
    ///
    /// * `input` - The input array of radix keys
    /// * `output` - The output buffer (must be same length as input)
    /// * `byte_index` - The byte position to sort by
    ///
    /// # Stability
    ///
    /// This implementation is stable - equal elements maintain their relative order.
    fn counting_sort_by_byte(
        &self,
        input: &mut [T::RadixKey],
        output: &mut [T::RadixKey],
        byte_index: usize,
    ) {
        const RADIX: usize = 256;
        let mut count = [0usize; RADIX];

        // Count occurrences of each byte value
        for &key in input.iter() {
            let byte_value = T::extract_byte(key, byte_index) as usize;
            count[byte_value] += 1;
        }

        // Convert to cumulative counts (prefix sum)
        let mut sum = 0;
        for i in 0..RADIX {
            sum += count[i];
            count[i] = sum;
        }

        // Build output array in reverse for stability
        for i in (0..input.len()).rev() {
            let byte_value = T::extract_byte(input[i], byte_index) as usize;
            count[byte_value] -= 1;
            output[count[byte_value]] = input[i];
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::{RadixDataType, SortDirection};

    #[test]
    fn test_sort_unsigned_integers() {
        let mut numbers = vec![170u64, 45, 75, 9000, 802, 24, 2, 66];
        let sorter =
            RadixSort::<u64>::new(RadixDataType::UnsignedInteger, SortDirection::Ascending);
        sorter.sort(&mut numbers).unwrap();
        assert_eq!(numbers, vec![2, 24, 45, 66, 75, 170, 802, 9000])
    }

    #[test]
    fn test_sort_signed_integers() {
        let mut numbers = vec![170i64, -45, 75, -9000, 802, 24, 2, 66];
        let sorter = RadixSort::<i64>::new(RadixDataType::SignedInteger, SortDirection::Ascending);
        sorter.sort(&mut numbers).unwrap();
        assert_eq!(numbers, vec![-9000, -45, 2, 24, 66, 75, 170, 802]);
    }

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

    #[test]
    fn test_empty_slice() {
        let mut numbers: Vec<i64> = vec![];
        let sorter = RadixSort::<i64>::default();
        assert!(sorter.sort(&mut numbers).is_ok());
        assert!(numbers.is_empty());
    }

    #[test]
    fn test_single_element() {
        let mut numbers = vec![42i64];
        let sorter = RadixSort::<i64>::default();
        sorter.sort(&mut numbers).unwrap();
        assert_eq!(numbers, vec![42]);
    }

    #[test]
    fn test_all_negative() {
        let mut numbers = vec![-5i64, -1, -100, -3];
        let sorter = RadixSort::<i64>::default();
        sorter.sort(&mut numbers).unwrap();
        assert_eq!(numbers, vec![-100, -5, -3, -1]);
    }

    #[test]
    fn test_duplicates() {
        let mut numbers = vec![5i64, 2, 5, 1, 2, 5];
        let sorter = RadixSort::<i64>::default();
        sorter.sort(&mut numbers).unwrap();
        assert_eq!(numbers, vec![1, 2, 2, 5, 5, 5]);
    }
}