universal_radix_sort 1.0.0

//! Traits for Radix Sort type compatibility.
//!
//! This module defines the core traits that types must implement to be sortable
//! using the Radix Sort algorithm.
//!
//! # Overview
//!
//! The [`RadixSortable`] trait provides the interface for converting types to and from
//! their byte representations, which is essential for radix-based sorting operations.
//!
//! # Safety Requirements
//!
//! Implementors must ensure that:
//! - `to_radix_key()` produces consistent ordering relative to the original value
//! - `from_radix_key()` correctly reconstructs the original value
//! - The transformation is reversible: `from_radix_key(to_radix_key(x)) == x`
//!
//! # Examples
//!
//! ```rust
//! use universal_radix_sort::RadixSortable;
//!
//! // i64 already implements RadixSortable
//! let value: i64 = 42;
//! let key = i64::to_radix_key(value);
//! let restored = i64::from_radix_key(key);
//! assert_eq!(value, restored);
//! ```

use crate::{RadixDataType, RadixResult};

/// Trait for types that can be sorted using Radix Sort.
///
/// This trait provides the interface for converting types to and from their
/// byte representations, which is essential for radix-based sorting.
///
/// # Type Parameters
///
/// The associated type `RadixKey` must be:
/// - `Copy` - for efficient byte extraction
/// - `Eq` - for comparison operations
/// - `Ord` - for ordering during sorting
///
/// # Examples
///
/// ```rust
/// use universal_radix_sort::RadixSortable;
///
/// // Signed integer transformation
/// let key = i64::to_radix_key(-5i64);
/// // Key should be less than positive numbers' keys
///
/// // Float transformation (IEEE 754)
/// let float_key = f64::to_radix_key(3.14f64);
/// ```
pub trait RadixSortable: Sized + Clone {
    /// The unsigned integer type used for radix keys.
    ///
    /// This type must be large enough to hold the bit representation of `Self`.
    /// For example:
    /// - `i64` → `u64`
    /// - `f64` → `u64`
    /// - `String` → `u8` (per character)
    type RadixKey: Copy + Eq + Ord;

    /// Returns the data type category for this sortable type.
    ///
    /// # Returns
    ///
    /// A [`RadixDataType`] variant indicating the category of this type.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use universal_radix_sort::{RadixSortable, RadixDataType};
    ///
    /// assert_eq!(i64::data_type(), RadixDataType::SignedInteger);
    /// assert_eq!(f64::data_type(), RadixDataType::Float);
    /// ```
    fn data_type() -> RadixDataType;

    /// Converts the value to a radix-sortable key.
    ///
    /// This transformation must preserve ordering: if `a < b`, then
    /// `to_radix_key(a) < to_radix_key(b)`.
    ///
    /// # Arguments
    ///
    /// * `value` - The value to convert to a radix key
    ///
    /// # Returns
    ///
    /// The radix key representation suitable for byte-level sorting.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use universal_radix_sort::RadixSortable;
    ///
    /// let key = i64::to_radix_key(-5i64);
    /// // Key is transformed to maintain correct ordering
    /// assert!(key < i64::to_radix_key(5i64));
    /// ```
    fn to_radix_key(value: Self) -> Self::RadixKey;

    /// Converts a radix key back to the original value.
    ///
    /// # Arguments
    ///
    /// * `key` - The radix key to convert back to the original type
    ///
    /// # Returns
    ///
    /// The original value reconstructed from the radix key.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use universal_radix_sort::RadixSortable;
    ///
    /// let key = i64::to_radix_key(42i64);
    /// let value = i64::from_radix_key(key);
    /// assert_eq!(value, 42);
    /// ```
    fn from_radix_key(key: Self::RadixKey) -> Self;

    // src/traits.rs - Line 140-165 (FIXED)

    /// Extracts a specific byte from the radix key.
    ///
    /// This method extracts a single byte from the radix key at the specified
    /// position. Byte 0 is the least significant byte (LSB).
    ///
    /// # Arguments
    ///
    /// * `key` - The radix key to extract a byte from
    /// * `byte_index` - The byte position (0 = least significant byte)
    ///
    /// # Returns
    ///
    /// The byte value at the specified position.
    ///
    /// # Panics
    ///
    /// Panics if `byte_index` is out of range for the key size.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use universal_radix_sort::RadixSortable;
    ///
    /// let key: u64 = 0x1234567890ABCDEF;
    /// let byte0 = u64::extract_byte(key, 0); // 0xEF
    /// let byte7 = u64::extract_byte(key, 7); // 0x12
    /// ```
    fn extract_byte(key: Self::RadixKey, byte_index: usize) -> u8;

    /// Returns the number of bytes in the radix key representation.
    ///
    /// # Returns
    ///
    /// The size in bytes of the radix key.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use universal_radix_sort::RadixSortable;
    ///
    /// assert_eq!(i64::key_size(), 8);
    /// assert_eq!(f32::key_size(), 4);
    /// ```
    fn key_size() -> usize;

    /// Validates that the value can be sorted.
    ///
    /// # Arguments
    ///
    /// * `_value` - The value to validate (underscored as it's unused by default)
    ///
    /// # Returns
    ///
    /// `Ok(())` if valid, `Err(RadixError)` if invalid.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use universal_radix_sort::RadixSortable;
    ///
    /// assert!(i64::validate(&42).is_ok());
    /// ```
    #[inline]
    fn validate(_value: &Self) -> RadixResult<()> {
        Ok(())
    }

    /// Returns the string length for string types.
    ///
    /// For non-string types, this returns 0 by default.
    ///
    /// # Arguments
    ///
    /// * `_value` - The value to measure (unused for non-string types)
    ///
    /// # Returns
    ///
    /// The length of the string in bytes, or 0 for non-string types.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use universal_radix_sort::RadixSortable;
    ///
    /// assert_eq!(String::string_length(&"hello".to_string()), 5);
    /// assert_eq!(i64::string_length(&42), 0);
    /// ```
    #[inline]
    fn string_length(_value: &Self) -> usize {
        0
    }

    /// Extracts a byte at the given character index for string types.
    ///
    /// For non-string types, this returns 0 by default.
    ///
    /// # Arguments
    ///
    /// * `_value` - The value to extract from (unused for non-string types)
    /// * `_char_index` - The character index
    ///
    /// # Returns
    ///
    /// The byte value at the index, or 0 if out of bounds or non-string type.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use universal_radix_sort::RadixSortable;
    ///
    /// assert_eq!(String::string_byte_at(&"hello".to_string(), 0), b'h');
    /// assert_eq!(String::string_byte_at(&"hello".to_string(), 10), 0);
    /// ```
    #[inline]
    fn string_byte_at(_value: &Self, _char_index: usize) -> u8 {
        0
    }
}

// Implementation for unsigned integers
macro_rules! impl_radix_sortable_unsigned {
    ($($t:ty),*) => {
        $(
            impl RadixSortable for $t {
                type RadixKey = $t;

                #[inline]
                fn data_type() -> RadixDataType {
                    RadixDataType::UnsignedInteger
                }

                #[inline]
                fn to_radix_key(value: Self) -> Self::RadixKey {
                    value
                }

                #[inline]
                fn from_radix_key(key: Self::RadixKey) -> Self {
                    key
                }

                #[inline]
                fn extract_byte(key: Self::RadixKey, byte_index: usize) -> u8 {
                    ((key as u128) >> (byte_index * 8)) as u8
                }

                #[inline]
                fn key_size() -> usize {
                    std::mem::size_of::<Self>()
                }
            }
        )*
    };
}

impl_radix_sortable_unsigned!(u8, u16, u32, u64, u128, usize);

// Implementation for signed integers
macro_rules! impl_radix_sortable_signed {
    ($($t:ty => $u:ty),*) => {
        $(
            impl RadixSortable for $t {
                type RadixKey = $u;

                #[inline]
                fn data_type() -> RadixDataType {
                    RadixDataType::SignedInteger
                }

                #[inline]
                fn to_radix_key(value: Self) -> Self::RadixKey {
                    // Flip the sign bit to map signed to unsigned ordering
                    const SIGN_BIT: $u = 1 << (std::mem::size_of::<$t>() * 8 - 1);
                    (value as $u) ^ SIGN_BIT
                }

                #[inline]
                fn from_radix_key(key: Self::RadixKey) -> Self {
                    // Reverse the sign bit transformation
                    const SIGN_BIT: $u = 1 << (std::mem::size_of::<$t>() * 8 - 1);
                    (key ^ SIGN_BIT) as $t
                }

                #[inline]
                fn extract_byte(key: Self::RadixKey, byte_index: usize) -> u8 {
                    ((key as u128) >> (byte_index * 8)) as u8
                }

                #[inline]
                fn key_size() -> usize {
                    std::mem::size_of::<$u>()
                }
            }
        )*
    };
}

impl_radix_sortable_signed!(i8 => u8, i16 => u16, i32 => u32, i64 => u64, i128 => u128, isize => usize);

// Implementation for f32
impl RadixSortable for f32 {
    type RadixKey = u32;

    #[inline]
    fn data_type() -> RadixDataType {
        RadixDataType::Float
    }

    #[inline]
    fn to_radix_key(value: Self) -> Self::RadixKey {
        let bits = value.to_bits();

        // IEEE 754 transformation for correct ordering
        if value.is_nan() {
            // NaN values get the maximum key value (sorted to end)
            u32::MAX
        } else if bits & 0x8000_0000 != 0 {
            // Negative: flip ALL bits to reverse ordering
            !bits
        } else {
            // Positive: flip ONLY sign bit
            bits ^ 0x8000_0000
        }
    }

    #[inline]
    fn from_radix_key(key: Self::RadixKey) -> Self {
        // Check for NaN marker FIRST
        if key == u32::MAX {
            return f32::NAN;
        }

        // Reverse the transformation
        let bits = if key & 0x8000_0000 != 0 {
            // Was positive (sign bit set after transformation): flip sign bit back
            key ^ 0x8000_0000
        } else {
            // Was negative (sign bit clear after transformation): flip all bits back
            !key
        };

        f32::from_bits(bits)
    }

    #[inline]
    fn extract_byte(key: Self::RadixKey, byte_index: usize) -> u8 {
        ((key as u128) >> (byte_index * 8)) as u8
    }

    #[inline]
    fn key_size() -> usize {
        std::mem::size_of::<u32>()
    }

    #[inline]
    fn validate(_value: &Self) -> RadixResult<()> {
        // NaN and Infinity are allowed
        Ok(())
    }
}

// Implementation for f64
impl RadixSortable for f64 {
    type RadixKey = u64;

    #[inline]
    fn data_type() -> RadixDataType {
        RadixDataType::Float
    }

    #[inline]
    fn to_radix_key(value: Self) -> Self::RadixKey {
        let bits = value.to_bits();

        // IEEE 754 transformation for correct ordering
        if value.is_nan() {
            // NaN values get the maximum key value (sorted to end)
            u64::MAX
        } else if bits & 0x8000_0000_0000_0000 != 0 {
            // Negative: flip ALL bits to reverse ordering
            !bits
        } else {
            // Positive: flip ONLY sign bit
            bits ^ 0x8000_0000_0000_0000
        }
    }

    #[inline]
    fn from_radix_key(key: Self::RadixKey) -> Self {
        // Check for NaN marker FIRST
        if key == u64::MAX {
            return f64::NAN;
        }

        // Reverse the transformation
        let bits = if key & 0x8000_0000_0000_0000 != 0 {
            // Was positive (sign bit set after transformation): flip sign bit back
            key ^ 0x8000_0000_0000_0000
        } else {
            // Was negative (sign bit clear after transformation): flip all bits back
            !key
        };

        f64::from_bits(bits)
    }

    #[inline]
    fn extract_byte(key: Self::RadixKey, byte_index: usize) -> u8 {
        ((key as u128) >> (byte_index * 8)) as u8
    }

    #[inline]
    fn key_size() -> usize {
        std::mem::size_of::<u64>()
    }

    #[inline]
    fn validate(_value: &Self) -> RadixResult<()> {
        // NaN and Infinity are allowed
        Ok(())
    }
}

// Implementation for String
impl RadixSortable for String {
    type RadixKey = u8;

    #[inline]
    fn data_type() -> RadixDataType {
        RadixDataType::String
    }

    #[inline]
    fn to_radix_key(value: Self) -> Self::RadixKey {
        value.as_bytes().first().copied().unwrap_or(0)
    }

    #[inline]
    fn from_radix_key(_key: Self::RadixKey) -> Self {
        String::new()
    }

    #[inline]
    fn extract_byte(_key: Self::RadixKey, _byte_index: usize) -> u8 {
        0
    }

    #[inline]
    fn key_size() -> usize {
        1
    }

    #[inline]
    fn string_length(value: &Self) -> usize {
        value.len()
    }

    #[inline]
    fn string_byte_at(value: &Self, char_index: usize) -> u8 {
        value.as_bytes().get(char_index).copied().unwrap_or(0)
    }
}

// Implementation for &str
impl RadixSortable for &str {
    type RadixKey = u8;

    #[inline]
    fn data_type() -> RadixDataType {
        RadixDataType::String
    }

    #[inline]
    fn to_radix_key(value: Self) -> Self::RadixKey {
        value.as_bytes().first().copied().unwrap_or(0)
    }

    #[inline]
    fn from_radix_key(_key: Self::RadixKey) -> Self {
        ""
    }

    #[inline]
    fn extract_byte(_key: Self::RadixKey, _byte_index: usize) -> u8 {
        0
    }

    #[inline]
    fn key_size() -> usize {
        1
    }

    #[inline]
    fn string_length(value: &Self) -> usize {
        value.len()
    }

    #[inline]
    fn string_byte_at(value: &Self, char_index: usize) -> u8 {
        value.as_bytes().get(char_index).copied().unwrap_or(0)
    }
}