universal_radix_sort 1.0.0

//! Core Radix Sort implementation module.
//!
//! This module contains the main `RadixSort` struct and orchestrates the sorting
//! operations for different data types.

mod float;
mod integer;
mod string;

use crate::{ProcessingOrder, RadixDataType, RadixResult, RadixSortable, SortDirection};
use std::marker::PhantomData;

/// Universal Radix Sort implementation.
///
/// This struct provides a generic interface for sorting collections using the Radix Sort
/// algorithm. It supports multiple data types including integers, floating-point numbers,
/// and strings.
///
/// # Type Parameters
///
/// * `T` - The type of elements to sort (must implement `RadixSortable`)
///
/// # Examples
///
/// ```rust
/// use universal_radix_sort::{RadixSort, RadixDataType, SortDirection};
///
/// // Sort integers in ascending order
/// let mut numbers = vec![5, 2, 8, 1, 9];
/// let sorter = RadixSort::<i64>::new(RadixDataType::SignedInteger, SortDirection::Ascending);
/// sorter.sort(&mut numbers);
/// assert_eq!(numbers, vec![1, 2, 5, 8, 9]);
///
/// // Sort in descending order
/// let mut numbers = vec![5, 2, 8, 1, 9];
/// let sorter = RadixSort::<i64>::new(RadixDataType::SignedInteger, SortDirection::Descending);
/// sorter.sort(&mut numbers);
/// assert_eq!(numbers, vec![9, 8, 5, 2, 1]);
/// ```
///
/// # Performance
///
/// - **Time Complexity**: O(n·k) where n is the number of elements and k is the number of bytes
/// - **Space Complexity**: O(n) for the temporary buffer
///
/// # Stability
///
/// Radix Sort is a stable sorting algorithm, meaning that equal elements maintain their
/// relative order after sorting.
pub struct RadixSort<T>
where
    T: RadixSortable,
{
    /// The data type being sorted.
    data_type: RadixDataType,
    /// The sort direction (ascending or descending).
    direction: SortDirection,
    /// The byte processing order (LSB-first or MSB-first).
    processing_order: ProcessingOrder,
    /// Phantom data for the generic type.
    _phantom: PhantomData<T>,
}

impl<T> RadixSort<T>
where
    T: RadixSortable,
{
    /// Creates a new RadixSort instance.
    ///
    /// # Arguments
    ///
    /// * `data_type` - The data type category for sorting strategy selection
    /// * `direction` - The sort direction (ascending or descending)
    ///
    /// # Returns
    ///
    /// A new `RadixSort` instance configured with the specified parameters
    ///
    /// # Examples
    ///
    /// ```rust
    /// use universal_radix_sort::{RadixSort, RadixDataType, SortDirection};
    ///
    /// let sorter = RadixSort::<i64>::new(
    ///     RadixDataType::SignedInteger,
    ///     SortDirection::Ascending,
    /// );
    /// ```
    pub fn new(data_type: RadixDataType, direction: SortDirection) -> Self {
        Self {
            data_type,
            direction,
            processing_order: ProcessingOrder::LsbFirst,
            _phantom: PhantomData,
        }
    }

    /// Creates a new RadixSort instance with custom processing order.
    ///
    /// # Arguments
    ///
    /// * `data_type` - The data type category
    /// * `direction` - The sort direction
    /// * `processing_order` - The byte processing order
    ///
    /// # Examples
    ///
    /// ```rust
    /// use universal_radix_sort::{RadixSort, RadixDataType, SortDirection, ProcessingOrder};
    ///
    /// let sorter = RadixSort::<String>::with_processing_order(
    ///     RadixDataType::String,
    ///     SortDirection::Ascending,
    ///     ProcessingOrder::MsbFirst,
    /// );
    /// ```
    pub fn with_processing_order(
        data_type: RadixDataType,
        direction: SortDirection,
        processing_order: ProcessingOrder,
    ) -> Self {
        Self {
            data_type,
            direction,
            processing_order,
            _phantom: PhantomData,
        }
    }

    /// Sorts a mutable slice in-place.
    ///
    /// This method modifies the input slice directly without allocating a new collection.
    ///
    /// # Arguments
    ///
    /// * `slice` - The mutable slice to sort
    ///
    /// # Returns
    ///
    /// `Ok(())` on success, `Err(RadixError)` if sorting fails
    ///
    /// # Examples
    ///
    /// ```rust
    /// use universal_radix_sort::{RadixSort, RadixDataType, SortDirection};
    ///
    /// let mut numbers = vec![5, 2, 8, 1, 9];
    /// let sorter = RadixSort::<i64>::new(RadixDataType::SignedInteger, SortDirection::Ascending);
    /// sorter.sort(&mut numbers).unwrap();
    /// assert_eq!(numbers, vec![1, 2, 5, 8, 9]);
    /// ```
    ///
    /// # Performance
    ///
    /// - Allocates O(n) temporary buffer for stability
    /// - Does not allocate a new collection
    pub fn sort(&self, slice: &mut [T]) -> RadixResult<()> {
        if slice.is_empty() {
            return Ok(());
        }

        // Validate all elements
        for item in slice.iter() {
            T::validate(item)?;
        }

        // Dispatch to type-specific implementation
        let result = match self.data_type {
            RadixDataType::UnsignedInteger | RadixDataType::SignedInteger => {
                self.sort_integers(slice)
            }
            RadixDataType::Float => self.sort_floats(slice),
            RadixDataType::String => self.sort_strings_generic(slice),
        };

        result?;

        // Reverse if descending order
        if self.direction.is_descending() {
            slice.reverse();
        }

        Ok(())
    }

    /// Sorts a collection and returns a new sorted vector.
    ///
    /// This method does not modify the input collection.
    ///
    /// # Arguments
    ///
    /// * `collection` - The collection to sort
    ///
    /// # Returns
    ///
    /// A new sorted vector, or `Err(RadixError)` if sorting fails
    ///
    /// # Examples
    ///
    /// ```rust
    /// use universal_radix_sort::{RadixSort, RadixDataType, SortDirection};
    ///
    /// let numbers = vec![5, 2, 8, 1, 9];
    /// let sorter = RadixSort::<i64>::new(RadixDataType::SignedInteger, SortDirection::Ascending);
    /// let sorted = sorter.sort_to_vec(&numbers).unwrap();
    /// assert_eq!(sorted, vec![1, 2, 5, 8, 9]);
    /// // Original is unchanged
    /// assert_eq!(numbers, vec![5, 2, 8, 1, 9]);
    /// ```
    pub fn sort_to_vec(&self, collection: &[T]) -> RadixResult<Vec<T>> {
        let mut result = collection.to_vec();
        self.sort(&mut result)?;
        Ok(result)
    }

    /// Returns the configured data type.
    #[inline]
    pub fn data_type(&self) -> RadixDataType {
        self.data_type
    }

    /// Returns the configured sort direction.
    #[inline]
    pub fn direction(&self) -> SortDirection {
        self.direction
    }

    /// Returns the configured processing order.
    #[inline]
    pub fn processing_order(&self) -> ProcessingOrder {
        self.processing_order
    }
}

// Default implementation
impl<T> Default for RadixSort<T>
where
    T: RadixSortable,
{
    /// Creates a default RadixSort with SignedInteger type and Ascending direction.
    fn default() -> Self {
        Self::new(T::data_type(), SortDirection::Ascending)
    }
}