float.rs
//! Floating-point Radix Sort implementation.
//!
//! This module provides radix sorting for f32 and f64 types with proper
//! IEEE 754 handling for NaN, Infinity, and negative zero.
//!
//! # IEEE 754 Transformation
//!
//! Floating-point numbers require special bit manipulation to sort correctly:
//! - **Positive numbers**: Flip the sign bit only
//! - **Negative numbers**: Flip all bits (reverses ordering)
//! - **NaN values**: Map to maximum key value (sorted to end)
//!
//! # Examples
//!
//! ```rust
//! use universal_radix_sort::{RadixSort, RadixDataType, SortDirection};
//!
//! let mut values = vec![3.14f64, -1.25, 0.5, f64::NAN, -99.9];
//! let sorter = RadixSort::<f64>::new(RadixDataType::Float, SortDirection::Ascending);
//! sorter.sort(&mut values).unwrap();
//! // NaN is at the end
//! assert!(values[4].is_nan());
//! ```
use crate::{RadixResult, RadixSort, RadixSortable};
impl<T> RadixSort<T>
where
T: RadixSortable,
{
/// Performs radix sort on floating-point types.
///
/// Handles IEEE 754 special values correctly:
/// - NaN values are placed at the end
/// - Negative infinity sorts before all finite numbers
/// - Positive infinity sorts after all finite numbers
/// - Negative zero equals positive zero in ordering
///
/// # Arguments
///
/// * `slice` - The mutable slice of floats to sort
///
/// # Returns
///
/// `Ok(())` on success
///
/// # Examples
///
/// ```rust
/// use universal_radix_sort::{RadixSort, RadixDataType, SortDirection};
///
/// let mut values = vec![3.14f64, -1.25, 0.5, f64::NAN, -99.9];
/// let sorter = RadixSort::<f64>::new(RadixDataType::Float, SortDirection::Ascending);
/// sorter.sort(&mut values).unwrap();
/// // NaN is at the end
/// assert!(values[4].is_nan());
/// ```
pub(crate) fn sort_floats(&self, slice: &mut [T]) -> RadixResult<()> {
if slice.len() <= 1 {
return Ok(());
}
let key_size = T::key_size();
// Convert to radix keys (handles IEEE 754 transformation)
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());
// Initialize with first key's value (will be overwritten)
if let Some(&first_key) = keys.first() {
key_buffer.resize(keys.len(), first_key);
} else {
return Ok(());
}
// LSB-first radix sort on keys
for byte_index in 0..key_size {
self.counting_sort_float_bytes(&mut keys, &mut key_buffer, byte_index);
keys.swap_with_slice(&mut key_buffer);
}
// Convert back to original float values
for (i, key) in keys.iter().enumerate() {
slice[i] = T::from_radix_key(*key);
}
Ok(())
}
/// Counting sort for floating-point byte positions.
///
/// Similar to integer counting sort but optimized for float key distribution.
///
/// # 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_float_bytes(
&self,
input: &mut [T::RadixKey],
output: &mut [T::RadixKey],
byte_index: usize,
) {
const RADIX: usize = 256;
let mut count = [0usize; RADIX];
// Count occurrences
for &key in input.iter() {
let byte_value = T::extract_byte(key, byte_index) as usize;
count[byte_value] += 1;
}
// Prefix sum
let mut sum = 0;
for i in 0..RADIX {
sum += count[i];
count[i] = sum;
}
// Build output (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_f64_basic() {
let mut values = vec![3.14f64, -1.25, 0.5, -99.9, 42.0];
let sorter = RadixSort::<f64>::new(RadixDataType::Float, SortDirection::Ascending);
sorter.sort(&mut values).unwrap();
assert_eq!(values, vec![-99.9, -1.25, 0.5, 3.14, 42.0]);
}
#[test]
fn test_sort_f64_with_nan() {
let mut values = vec![3.14f64, f64::NAN, -1.25, 0.5];
let sorter = RadixSort::<f64>::new(RadixDataType::Float, SortDirection::Ascending);
sorter.sort(&mut values).unwrap();
// NaN should be at the end
assert!(values[3].is_nan());
// Other values should be sorted
assert_eq!(values[..3], [-1.25, 0.5, 3.14]);
}
#[test]
fn test_sort_f64_with_infinity() {
let mut values = vec![3.14f64, f64::INFINITY, -1.25, f64::NEG_INFINITY, 0.5];
let sorter = RadixSort::<f64>::new(RadixDataType::Float, SortDirection::Ascending);
sorter.sort(&mut values).unwrap();
assert_eq!(values[0], f64::NEG_INFINITY);
assert_eq!(values[4], f64::INFINITY);
}
#[test]
fn test_sort_f32_basic() {
let mut values = vec![3.14f32, -1.25, 0.5, -99.9];
let sorter = RadixSort::<f32>::new(RadixDataType::Float, SortDirection::Ascending);
sorter.sort(&mut values).unwrap();
assert_eq!(values, vec![-99.9, -1.25, 0.5, 3.14]);
}
#[test]
fn test_sort_f64_descending() {
let mut values = vec![3.14f64, -1.25, 0.5];
let sorter = RadixSort::<f64>::new(RadixDataType::Float, SortDirection::Descending);
sorter.sort(&mut values).unwrap();
assert_eq!(values, vec![3.14, 0.5, -1.25]);
}
#[test]
fn test_negative_zero() {
let mut values = vec![0.0f64, -0.0, 1.0, -1.0];
let sorter = RadixSort::<f64>::default();
sorter.sort(&mut values).unwrap();
// -0.0 and 0.0 are equal in ordering
assert!(values[0] == -1.0);
assert!(values[1] == 0.0 || values[1] == -0.0);
}
}
traits.rs
//! 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 = value.to_radix_key();
//! 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 = (-5i64).to_radix_key();
/// // Key should be less than positive numbers' keys
///
/// // Float transformation (IEEE 754)
/// let float_key = 3.14f64.to_radix_key();
/// ```
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 = (-5i64).to_radix_key();
/// // Key is transformed to maintain correct ordering
/// ```
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 = 42u64;
/// 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)
}
}
integration_test.rs
//! 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::{RadixSort, RadixDataType, 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 (NaN excluded as it's at the end)
assert_eq!(data[0], f64::NEG_INFINITY);
assert!(data[1] < 0.0);
assert!(data[2] == 0.0 || data[2] == -0.0);
assert!(data[3] > 0.0);
assert_eq!(data[6], 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
}