universal_radix_sort 1.0.0

//! String Radix Sort implementation.
//!
//! This module provides MSD (Most Significant Digit) first radix sorting
//! for strings with proper lexicographical ordering.
//!
//! # Overview
//!
//! String sorting requires special handling due to variable-length data.
//! This implementation supports both:
//! - **MSB-first**: Optimal for lexicographical ordering with early termination
//! - **LSB-first**: Fallback for compatibility with fixed-width processing
//!
//! # Performance Considerations
//!
//! - Uses UTF-8 byte extraction (256 radix) instead of UTF-16 (65536 radix)
//! - Avoids excessive memory allocation with adaptive counting
//! - Handles empty strings and variable lengths correctly
//!
//! # Examples
//!
//! ```rust
//! use universal_radix_sort::{RadixSort, RadixDataType, SortDirection};
//!
//! let mut strings = vec!["banana".to_string(), "apple".to_string(), "cherry".to_string()];
//! let sorter = RadixSort::<String>::new(RadixDataType::String, SortDirection::Ascending);
//! sorter.sort(&mut strings).unwrap();
//! assert_eq!(strings, vec!["apple", "banana", "cherry"]);
//! ```

use crate::{ProcessingOrder, RadixDataType, RadixError, RadixResult, RadixSort, RadixSortable};

impl<T> RadixSort<T>
where
    T: RadixSortable,
{
    /// Generic string sorting that works with [`RadixSortable`] trait.
    ///
    /// This method uses the trait's string methods to properly handle
    /// variable-length strings.
    ///
    /// # Arguments
    ///
    /// * `slice` - The mutable slice of strings to sort
    ///
    /// # Returns
    ///
    /// `Ok(())` on success, `Err(RadixError)` if sorting fails.
    ///
    /// # Errors
    ///
    /// Returns `UnsupportedOperation` if the type is not `String` or `&str`.
    pub(crate) fn sort_strings_generic(&self, slice: &mut [T]) -> RadixResult<()> {
        if slice.len() <= 1 {
            return Ok(());
        }

        // Verify we're sorting strings by data type
        if T::data_type() != RadixDataType::String {
            return Err(RadixError::unsupported_operation(
                "sort_strings_generic requires RadixDataType::String",
            ));
        }

        // FIX: Use trait method that now exists in RadixSortable
        let max_len = slice.iter().map(|s| T::string_length(s)).max().unwrap_or(0);

        if max_len == 0 {
            return Ok(());
        }

        // Use MSD-first for strings (lexicographical order)
        if self.processing_order == ProcessingOrder::MsbFirst {
            self.msd_radix_sort_generic(slice, 0, max_len)
        } else {
            // Fallback to LSB-first with padding
            self.lsb_radix_sort_generic(slice, max_len)
        }
    }

    /// MSD (Most Significant Digit) first radix sort for generic string types.
    ///
    /// # Arguments
    ///
    /// * `slice` - The mutable slice to sort
    /// * `start` - Start index of the current segment
    /// * `max_len` - Maximum string length in the collection
    ///
    /// # Returns
    ///
    /// `Ok(())` on success, `Err(RadixError)` if sorting fails.
    fn msd_radix_sort_generic(
        &self,
        slice: &mut [T],
        start: usize,
        max_len: usize,
    ) -> RadixResult<()> {
        self.msd_radix_sort_recursive(slice, start, slice.len(), 0, max_len)
    }

    /// Recursive MSD radix sort implementation.
    ///
    /// # Arguments
    ///
    /// * `slice` - The mutable slice to sort
    /// * `start` - Start index of current segment
    /// * `end` - End index of current segment
    /// * `char_index` - Current character position being processed
    /// * `max_len` - Maximum string length
    ///
    /// # Returns
    ///
    /// `Ok(())` on success
    fn msd_radix_sort_recursive(
        &self,
        slice: &mut [T],
        start: usize,
        end: usize,
        char_index: usize,
        max_len: usize,
    ) -> RadixResult<()> {
        if start >= end.saturating_sub(1) || char_index >= max_len {
            return Ok(());
        }

        const RADIX: usize = 256; // UTF-8 bytes
        let mut count = [0usize; RADIX + 1]; // +1 for strings shorter than char_index

        // Count occurrences
        for i in start..end {
            // FIX: Use trait method that now exists
            let byte = T::string_byte_at(&slice[i], char_index) as usize;
            count[byte + 1] += 1;
        }

        // Prefix sum
        for i in 1..count.len() {
            count[i] += count[i - 1];
        }

        // Create output buffer
        let mut output: Vec<T> = Vec::with_capacity(end - start);
        // Initialize with clones from input
        for i in start..end {
            output.push(slice[i].clone());
        }

        // Distribute to output
        let count_copy = count;
        for i in start..end {
            let byte = T::string_byte_at(&slice[i], char_index) as usize;
            let pos = count_copy[byte];
            output[pos - count_copy[0]] = slice[i].clone();
            count[byte] += 1;
        }

        // Copy back
        for (i, item) in output.into_iter().enumerate() {
            slice[start + i] = item;
        }

        // Recursively sort each bucket
        let mut prev_end = start;
        for i in 0..RADIX + 1 {
            let bucket_end = start + count[i] - count[0];
            if bucket_end > prev_end + 1 {
                self.msd_radix_sort_recursive(
                    slice,
                    prev_end,
                    bucket_end,
                    char_index + 1,
                    max_len,
                )?;
            }
            prev_end = bucket_end;
        }

        Ok(())
    }

    /// LSB (Least Significant Byte) first radix sort for generic string types.
    ///
    /// # Arguments
    ///
    /// * `slice` - The mutable slice to sort
    /// * `max_len` - Maximum string length
    ///
    /// # Returns
    ///
    /// `Ok(())` on success, `Err(RadixError)` if sorting fails.
    fn lsb_radix_sort_generic(&self, slice: &mut [T], max_len: usize) -> RadixResult<()> {
        let mut buffer: Vec<T> = Vec::with_capacity(slice.len());
        // Initialize with clones from input
        for item in slice.iter() {
            buffer.push(item.clone());
        }

        // Sort from last character to first
        for char_index in (0..max_len).rev() {
            self.counting_sort_strings_by_char_generic(slice, &mut buffer, char_index);
            slice.swap_with_slice(&mut buffer);
        }

        Ok(())
    }

    /// Counting sort for strings by a specific character position.
    ///
    /// # Arguments
    ///
    /// * `input` - The input slice to sort
    /// * `output` - The output buffer
    /// * `char_index` - The character position to sort by
    fn counting_sort_strings_by_char_generic(
        &self,
        input: &mut [T],
        output: &mut [T],
        char_index: usize,
    ) {
        const RADIX: usize = 256;
        let mut count = [0usize; RADIX + 1];
        let len = input.len();

        // Count
        for item in input.iter() {
            // FIX: Use trait method that now exists
            let byte = T::string_byte_at(item, char_index) as usize;
            count[byte + 1] += 1;
        }

        // Prefix sum
        for i in 1..count.len() {
            count[i] += count[i - 1];
        }

        // Build output (stable)
        for i in 0..len {
            let byte = T::string_byte_at(&input[i], char_index) as usize;
            output[count[byte]] = input[i].clone();
            count[byte] += 1;
        }
    }
}

// Specialized implementation for String type
impl RadixSort<String> {
    /// MSD (Most Significant Digit) first radix sort for [`String`].
    ///
    /// This is more efficient for strings as it allows early termination when
    /// differences are found in higher-order characters.
    ///
    /// # Arguments
    ///
    /// * `slice` - The mutable slice of Strings to sort
    ///
    /// # Returns
    ///
    /// `Ok(())` on success, `Err(RadixError)` if sorting fails.
    pub fn sort_strings_msd(&self, slice: &mut [String]) -> RadixResult<()> {
        if slice.len() <= 1 {
            return Ok(());
        }

        // Find maximum string length for MSD sorting
        let max_len = slice.iter().map(|s| s.len()).max().unwrap_or(0);
        if max_len == 0 {
            return Ok(());
        }

        // Use MSD-first for strings (lexicographical order)
        if self.processing_order == ProcessingOrder::MsbFirst {
            self.msd_radix_sort_strings(slice, 0, slice.len(), 0, max_len)?;
        } else {
            // Fallback to LSB-first with padding
            self.lsb_radix_sort_strings_impl(slice, max_len)?;
        }

        Ok(())
    }

    /// MSD radix sort implementation for [`String`] slice.
    ///
    /// # Arguments
    ///
    /// * `slice` - The mutable slice to sort
    /// * `start` - Start index of the current segment
    /// * `end` - End index of the current segment
    /// * `char_index` - Current character position being processed
    /// * `max_len` - Maximum string length in the collection
    ///
    /// # Returns
    ///
    /// `Ok(())` on success, `Err(RadixError)` if sorting fails.
    fn msd_radix_sort_strings(
        &self,
        slice: &mut [String],
        start: usize,
        end: usize,
        char_index: usize,
        max_len: usize,
    ) -> RadixResult<()> {
        if start >= end.saturating_sub(1) || char_index >= max_len {
            return Ok(());
        }

        const RADIX: usize = 256; // UTF-8 bytes
        let mut count = [0usize; RADIX + 1]; // +1 for strings shorter than char_index

        // Count occurrences
        for i in start..end {
            let byte = slice[i].as_bytes().get(char_index).copied().unwrap_or(0) as usize;
            count[byte + 1] += 1;
        }

        // Prefix sum
        for i in 1..count.len() {
            count[i] += count[i - 1];
        }

        // Create output buffer
        let mut output: Vec<String> = Vec::with_capacity(end - start);
        for _ in 0..(end - start) {
            output.push(String::new());
        }

        // Distribute to output
        let count_copy = count;
        for i in start..end {
            let byte = slice[i].as_bytes().get(char_index).copied().unwrap_or(0) as usize;
            let pos = count_copy[byte];
            output[pos - count_copy[0]] = slice[i].clone();
            count[byte] += 1;
        }

        // Copy back
        for (i, item) in output.into_iter().enumerate() {
            slice[start + i] = item;
        }

        // Recursively sort each bucket
        let mut prev_end = start;
        for i in 0..RADIX + 1 {
            let bucket_end = start + count[i] - count[0];
            if bucket_end > prev_end + 1 {
                self.msd_radix_sort_strings(slice, prev_end, bucket_end, char_index + 1, max_len)?;
            }
            prev_end = bucket_end;
        }

        Ok(())
    }

    /// LSB radix sort implementation for [`String`] slice.
    ///
    /// # Arguments
    ///
    /// * `slice` - The mutable slice to sort
    /// * `max_len` - Maximum string length
    ///
    /// # Returns
    ///
    /// `Ok(())` on success.
    fn lsb_radix_sort_strings_impl(&self, slice: &mut [String], max_len: usize) -> RadixResult<()> {
        let mut buffer: Vec<String> = vec![String::new(); slice.len()];

        for char_index in (0..max_len).rev() {
            self.counting_sort_strings_by_char_impl(slice, &mut buffer, char_index);
            slice.swap_with_slice(&mut buffer);
        }

        Ok(())
    }

    /// Counting sort for strings by a specific character position.
    ///
    /// # Arguments
    ///
    /// * `input` - The input slice to sort
    /// * `output` - The output buffer
    /// * `char_index` - The character position to sort by
    fn counting_sort_strings_by_char_impl(
        &self,
        input: &mut [String],
        output: &mut [String],
        char_index: usize,
    ) {
        const RADIX: usize = 256;
        let mut count = [0usize; RADIX + 1];
        let len = input.len();

        // Count
        for item in input.iter() {
            let byte = item.as_bytes().get(char_index).copied().unwrap_or(0) as usize;
            count[byte + 1] += 1;
        }

        // Prefix sum
        for i in 1..count.len() {
            count[i] += count[i - 1];
        }

        // Build output (stable)
        for i in 0..len {
            let byte = input[i].as_bytes().get(char_index).copied().unwrap_or(0) as usize;
            output[count[byte]] = input[i].clone();
            count[byte] += 1;
        }
    }
}

// Specialized implementation for &str type
impl RadixSort<&str> {
    /// MSD radix sort for `&str` slice.
    ///
    /// # Arguments
    ///
    /// * `slice` - The mutable slice to sort
    ///
    /// # Returns
    ///
    /// `Ok(())` on success.
    pub fn sort_str_slice_msd(&self, slice: &mut [&str]) -> RadixResult<()> {
        if slice.len() <= 1 {
            return Ok(());
        }

        let max_len = slice.iter().map(|s| s.len()).max().unwrap_or(0);
        if max_len == 0 {
            return Ok(());
        }

        if self.processing_order == ProcessingOrder::MsbFirst {
            self.msd_radix_sort_str_slice(slice, 0, slice.len(), 0, max_len)?;
        } else {
            self.lsb_radix_sort_str_slice_impl(slice, max_len)?;
        }

        Ok(())
    }

    /// MSD radix sort implementation for `&str` slice.
    ///
    /// # Arguments
    ///
    /// * `slice` - The mutable slice to sort
    /// * `start` - Start index
    /// * `end` - End index
    /// * `char_index` - Current character position
    /// * `max_len` - Maximum string length
    ///
    /// # Returns
    ///
    /// `Ok(())` on success.
    fn msd_radix_sort_str_slice(
        &self,
        slice: &mut [&str],
        start: usize,
        end: usize,
        char_index: usize,
        max_len: usize,
    ) -> RadixResult<()> {
        if start >= end.saturating_sub(1) || char_index >= max_len {
            return Ok(());
        }

        const RADIX: usize = 256;
        let mut count = [0usize; RADIX + 1];

        // Count
        for i in start..end {
            let byte = slice[i].as_bytes().get(char_index).copied().unwrap_or(0) as usize;
            count[byte + 1] += 1;
        }

        // Prefix sum
        for i in 1..count.len() {
            count[i] += count[i - 1];
        }

        // Output buffer - FIX: Use Vec with proper initialization
        let mut output: Vec<&str> = Vec::with_capacity(end - start);
        for i in start..end {
            output.push(slice[i]);
        }

        // Distribute
        let count_copy = count;
        for i in start..end {
            let byte = slice[i].as_bytes().get(char_index).copied().unwrap_or(0) as usize;
            let pos = count_copy[byte];
            output[pos - count_copy[0]] = slice[i];
            count[byte] += 1;
        }

        // Copy back
        for (i, item) in output.into_iter().enumerate() {
            slice[start + i] = item;
        }

        // Recursive sort
        let mut prev_end = start;
        for i in 0..RADIX + 1 {
            let bucket_end = start + count[i] - count[0];
            if bucket_end > prev_end + 1 {
                self.msd_radix_sort_str_slice(
                    slice,
                    prev_end,
                    bucket_end,
                    char_index + 1,
                    max_len,
                )?;
            }
            prev_end = bucket_end;
        }

        Ok(())
    }

    /// LSB radix sort for `&str` slice.
    ///
    /// # Arguments
    ///
    /// * `slice` - The mutable slice to sort
    /// * `max_len` - Maximum string length
    ///
    /// # Returns
    ///
    /// `Ok(())` on success.
    fn lsb_radix_sort_str_slice_impl(&self, slice: &mut [&str], max_len: usize) -> RadixResult<()> {
        let mut buffer: Vec<&str> = Vec::with_capacity(slice.len());
        for &s in slice.iter() {
            buffer.push(s);
        }

        for char_index in (0..max_len).rev() {
            self.counting_sort_str_by_char_impl(slice, &mut buffer, char_index);
            slice.swap_with_slice(&mut buffer);
        }

        Ok(())
    }

    /// Counting sort for `&str` by character position.
    ///
    /// # Arguments
    ///
    /// * `input` - The input slice to sort
    /// * `char_index` - The character position to sort by
    fn counting_sort_str_by_char_impl<'a>(
        &self,
        input: &mut [&'a str],
        output: &mut [&'a str],
        char_index: usize,
    ) {
        const RADIX: usize = 256;
        let mut count = [0usize; RADIX + 1];
        let len = input.len();

        // Count
        for item in input.iter() {
            let byte = item.as_bytes().get(char_index).copied().unwrap_or(0) as usize;
            count[byte + 1] += 1;
        }

        // Prefix sum
        for i in 1..count.len() {
            count[i] += count[i - 1];
        }

        // Build output (stable)
        for i in 0..len {
            let byte = input[i].as_bytes().get(char_index).copied().unwrap_or(0) as usize;
            output[count[byte]] = input[i];
            count[byte] += 1;
        }
    }
}

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

    #[test]
    fn test_sort_strings_basic() {
        let mut strings = vec![
            "banana".to_string(),
            "apple".to_string(),
            "cherry".to_string(),
        ];
        let sorter = RadixSort::<String>::new(RadixDataType::String, SortDirection::Ascending);
        sorter.sort(&mut strings).unwrap();
        assert_eq!(strings, vec!["apple", "banana", "cherry"]);
    }

    #[test]
    fn test_sort_strings_different_lengths() {
        let mut strings = vec!["a".to_string(), "abc".to_string(), "ab".to_string()];
        let sorter = RadixSort::<String>::default();
        sorter.sort(&mut strings).unwrap();
        assert_eq!(strings, vec!["a", "ab", "abc"]);
    }

    #[test]
    fn test_sort_strings_descending() {
        let mut strings = vec![
            "banana".to_string(),
            "apple".to_string(),
            "cherry".to_string(),
        ];
        let sorter = RadixSort::<String>::new(RadixDataType::String, SortDirection::Descending);
        sorter.sort(&mut strings).unwrap();
        assert_eq!(strings, vec!["cherry", "banana", "apple"]);
    }

    #[test]
    fn test_sort_strings_empty() {
        let mut strings: Vec<String> = vec![];
        let sorter = RadixSort::<String>::default();
        sorter.sort(&mut strings).unwrap();
        assert!(strings.is_empty());
    }

    #[test]
    fn test_sort_strings_with_empty_strings() {
        let mut strings = vec!["b".to_string(), "".to_string(), "a".to_string()];
        let sorter = RadixSort::<String>::default();
        sorter.sort(&mut strings).unwrap();
        assert_eq!(strings, vec!["", "a", "b"]);
    }

    #[test]
    fn test_sort_str_slice() {
        let mut strings = vec!["banana", "apple", "cherry"];
        let sorter = RadixSort::<&str>::default();
        sorter.sort(&mut strings).unwrap();
        assert_eq!(strings, vec!["apple", "banana", "cherry"]);
    }
}