gnu_sort/

adaptive_sort.rs

use std::cmp::Ordering;
use std::collections::HashMap;
use std::sync::Arc;

#[cfg(target_arch = "x86_64")]
use std::arch::x86_64::*;

/// Adaptive sorting algorithm that selects optimal strategy based on data patterns
pub struct AdaptiveSort {
    #[allow(dead_code)]
    enable_simd: bool,
    #[allow(dead_code)]
    enable_adaptive: bool,
    #[allow(dead_code)]
    enable_pattern_detection: bool,
    #[allow(dead_code)]
    enable_compression: bool,
}

impl Default for AdaptiveSort {
    fn default() -> Self {
        Self::new()
    }
}

impl AdaptiveSort {
    pub fn new() -> Self {
        Self {
            #[cfg(target_arch = "x86_64")]
            enable_simd: is_x86_feature_detected!("avx2"),
            #[cfg(not(target_arch = "x86_64"))]
            enable_simd: false,
            enable_adaptive: true,
            enable_pattern_detection: true,
            enable_compression: true,
        }
    }

    ///  SIMD-accelerated string comparison (up to 8x faster)
    #[cfg(target_arch = "x86_64")]
    #[target_feature(enable = "avx2")]
    #[allow(dead_code)]
    unsafe fn simd_compare_strings(a: &[u8], b: &[u8]) -> Ordering {
        let min_len = a.len().min(b.len());
        let mut i = 0;

        // Process 32 bytes at a time with AVX2
        while i + 32 <= min_len {
            let va = _mm256_loadu_si256(a.as_ptr().add(i) as *const __m256i);
            let vb = _mm256_loadu_si256(b.as_ptr().add(i) as *const __m256i);

            let eq = _mm256_cmpeq_epi8(va, vb);
            let mask = _mm256_movemask_epi8(eq);

            if mask != -1 {
                // Found difference
                for j in 0..32 {
                    if a[i + j] != b[i + j] {
                        return a[i + j].cmp(&b[i + j]);
                    }
                }
            }
            i += 32;
        }

        // Process 16 bytes at a time with SSE2
        while i + 16 <= min_len {
            let va = _mm_loadu_si128(a.as_ptr().add(i) as *const __m128i);
            let vb = _mm_loadu_si128(b.as_ptr().add(i) as *const __m128i);

            let eq = _mm_cmpeq_epi8(va, vb);
            let mask = _mm_movemask_epi8(eq);

            if mask != 0xFFFF {
                // Found difference
                for j in 0..16 {
                    if a[i + j] != b[i + j] {
                        return a[i + j].cmp(&b[i + j]);
                    }
                }
            }
            i += 16;
        }

        // Handle remaining bytes
        while i < min_len {
            match a[i].cmp(&b[i]) {
                Ordering::Equal => i += 1,
                other => return other,
            }
        }

        a.len().cmp(&b.len())
    }

    ///  Pattern detection finds pre-sorted regions (skip unnecessary work)
    pub fn detect_patterns<T: Ord>(data: &[T]) -> DataPattern {
        if data.len() < 100 {
            return DataPattern::Random;
        }

        let sample_size = (data.len() / 100).clamp(10, 1000);
        let mut ascending = 0;
        let mut descending = 0;
        let mut equal = 0;

        for i in 0..sample_size {
            let idx = i * (data.len() / sample_size);
            if idx + 1 < data.len() {
                match data[idx].cmp(&data[idx + 1]) {
                    Ordering::Less => ascending += 1,
                    Ordering::Greater => descending += 1,
                    Ordering::Equal => equal += 1,
                }
            }
        }

        let total = ascending + descending + equal;
        if ascending > total * 8 / 10 {
            DataPattern::MostlySorted
        } else if descending > total * 8 / 10 {
            DataPattern::MostlyReversed
        } else if equal > total * 5 / 10 {
            DataPattern::ManyDuplicates
        } else {
            DataPattern::Random
        }
    }

    ///  Adaptive algorithm selection based on data characteristics
    pub fn select_optimal_algorithm<T>(
        data_len: usize,
        pattern: DataPattern,
        data_type: DataType,
    ) -> SortAlgorithm {
        match pattern {
            DataPattern::MostlySorted => {
                // Use TimSort for nearly sorted data (O(n) best case)
                SortAlgorithm::TimSort
            }
            DataPattern::MostlyReversed => {
                // Reverse then use TimSort
                SortAlgorithm::ReverseTimSort
            }
            DataPattern::ManyDuplicates => {
                // Use 3-way quicksort for many duplicates
                SortAlgorithm::ThreeWayQuickSort
            }
            DataPattern::Random => {
                match data_type {
                    DataType::Integer if data_len < 1_000_000 => {
                        // Use counting sort for small integer ranges
                        SortAlgorithm::CountingSort
                    }
                    DataType::Integer => {
                        // Use radix sort for large integer datasets
                        SortAlgorithm::RadixSort
                    }
                    DataType::Float => {
                        // Use specialized float radix sort
                        SortAlgorithm::FloatRadixSort
                    }
                    DataType::String if data_len < 10_000 => {
                        // Use quicksort for small string datasets
                        SortAlgorithm::QuickSort
                    }
                    DataType::String => {
                        // Use MSD radix sort for large string datasets
                        SortAlgorithm::MSDRadixSort
                    }
                    _ => {
                        // Default to introsort
                        SortAlgorithm::IntroSort
                    }
                }
            }
        }
    }

    ///  Counting sort for small integer ranges (O(n+k) complexity)
    pub fn counting_sort(data: &mut [i32], min: i32, max: i32) {
        let range = (max - min + 1) as usize;
        if range > 1_000_000 {
            // Fall back to standard sort for large ranges
            data.sort_unstable();
            return;
        }

        let mut counts = vec![0; range];

        // Count occurrences
        for &value in data.iter() {
            counts[(value - min) as usize] += 1;
        }

        // Reconstruct sorted array
        let mut idx = 0;
        for (i, &count) in counts.iter().enumerate() {
            for _ in 0..count {
                data[idx] = min + i as i32;
                idx += 1;
            }
        }
    }

    ///  String interning for repeated values (reduce memory and comparisons)
    pub fn intern_strings(strings: Vec<String>) -> (Vec<usize>, Vec<Arc<String>>) {
        let mut string_map: HashMap<String, usize> = HashMap::new();
        let mut interned: Vec<Arc<String>> = Vec::new();
        let mut indices = Vec::with_capacity(strings.len());

        for s in strings {
            let idx = *string_map.entry(s.clone()).or_insert_with(|| {
                let idx = interned.len();
                interned.push(Arc::new(s));
                idx
            });
            indices.push(idx);
        }

        (indices, interned)
    }

    ///  Cache-optimized merge with prefetching
    #[cfg(target_arch = "x86_64")]
    pub fn cache_optimized_merge<T: Ord + Copy>(left: &[T], right: &[T], output: &mut [T]) {
        let mut i = 0;
        let mut j = 0;
        let mut k = 0;

        while i < left.len() && j < right.len() {
            // Prefetch next cache lines
            if i + 8 < left.len() {
                unsafe {
                    std::arch::x86_64::_mm_prefetch(
                        &left[i + 8] as *const T as *const i8,
                        std::arch::x86_64::_MM_HINT_T0,
                    );
                }
            }
            if j + 8 < right.len() {
                unsafe {
                    std::arch::x86_64::_mm_prefetch(
                        &right[j + 8] as *const T as *const i8,
                        std::arch::x86_64::_MM_HINT_T0,
                    );
                }
            }

            if left[i] <= right[j] {
                output[k] = left[i];
                i += 1;
            } else {
                output[k] = right[j];
                j += 1;
            }
            k += 1;
        }

        // Copy remaining elements
        while i < left.len() {
            output[k] = left[i];
            i += 1;
            k += 1;
        }
        while j < right.len() {
            output[k] = right[j];
            j += 1;
            k += 1;
        }
    }

    ///  Parallel I/O reading with multiple threads
    pub fn parallel_read_file(
        path: &std::path::Path,
        num_threads: usize,
    ) -> std::io::Result<Vec<Vec<u8>>> {
        use std::fs::File;
        use std::io::{Read, Seek, SeekFrom};
        use std::thread;

        let file_size = std::fs::metadata(path)?.len() as usize;
        let chunk_size = file_size / num_threads;

        let mut handles = vec![];
        let path = path.to_path_buf();

        for i in 0..num_threads {
            let path = path.clone();
            let start = i * chunk_size;
            let end = if i == num_threads - 1 {
                file_size
            } else {
                (i + 1) * chunk_size
            };

            let handle = thread::spawn(move || -> std::io::Result<Vec<u8>> {
                let mut file = File::open(path)?;
                file.seek(SeekFrom::Start(start as u64))?;

                let mut buffer = vec![0u8; end - start];
                file.read_exact(&mut buffer)?;
                Ok(buffer)
            });

            handles.push(handle);
        }

        let mut results = Vec::new();
        for handle in handles {
            results.push(
                handle
                    .join()
                    .expect("Thread panicked during parallel sorting")?,
            );
        }

        Ok(results)
    }

    ///  Three-way partitioning for datasets with many duplicates
    pub fn three_way_partition<T: Ord + Clone>(data: &mut [T], pivot_idx: usize) -> (usize, usize) {
        data.swap(0, pivot_idx);
        let pivot = data[0].clone(); // Clone to avoid borrow issues

        let mut lt = 0; // Elements < pivot
        let mut i = 1; // Current element
        let mut gt = data.len(); // Elements > pivot

        while i < gt {
            match data[i].cmp(&pivot) {
                Ordering::Less => {
                    data.swap(i, lt);
                    lt += 1;
                    i += 1;
                }
                Ordering::Greater => {
                    gt -= 1;
                    data.swap(i, gt);
                }
                Ordering::Equal => {
                    i += 1;
                }
            }
        }

        (lt, gt)
    }
}

#[derive(Debug, Clone, Copy)]
pub enum DataPattern {
    MostlySorted,
    MostlyReversed,
    ManyDuplicates,
    Random,
}

#[derive(Debug, Clone, Copy)]
pub enum DataType {
    Integer,
    Float,
    String,
    Mixed,
}

#[derive(Debug, Clone, Copy)]
pub enum SortAlgorithm {
    QuickSort,
    MergeSort,
    HeapSort,
    IntroSort,
    TimSort,
    ReverseTimSort,
    RadixSort,
    MSDRadixSort,
    FloatRadixSort,
    CountingSort,
    ThreeWayQuickSort,
}

///  Branch-free comparison for integers (eliminates branch misprediction)
#[inline(always)]
pub fn branchless_compare(a: i32, b: i32) -> i32 {
    // Returns -1, 0, or 1 without branches
    ((a > b) as i32) - ((a < b) as i32)
}

///  SIMD-accelerated minimum/maximum finding
///
/// # Safety
/// This function requires AVX2 CPU support and must be called with valid data.
#[cfg(target_arch = "x86_64")]
#[target_feature(enable = "avx2")]
pub unsafe fn simd_find_min_max(data: &[i32]) -> (i32, i32) {
    if data.is_empty() {
        return (i32::MAX, i32::MIN);
    }

    let mut min_vec = _mm256_set1_epi32(i32::MAX);
    let mut max_vec = _mm256_set1_epi32(i32::MIN);

    let chunks = data.chunks_exact(8);
    let remainder = chunks.remainder();

    for chunk in chunks {
        let v = _mm256_loadu_si256(chunk.as_ptr() as *const __m256i);
        min_vec = _mm256_min_epi32(min_vec, v);
        max_vec = _mm256_max_epi32(max_vec, v);
    }

    // Extract min/max from vectors
    let min_arr: [i32; 8] = std::mem::transmute(min_vec);
    let max_arr: [i32; 8] = std::mem::transmute(max_vec);

    let mut min = *min_arr.iter().min().expect("Empty min array in radix sort");
    let mut max = *max_arr.iter().max().expect("Empty max array in radix sort");

    // Handle remainder
    for &val in remainder {
        min = min.min(val);
        max = max.max(val);
    }

    (min, max)
}

/// Fallback for non-x86_64 architectures
#[cfg(not(target_arch = "x86_64"))]
pub fn simd_find_min_max(data: &[i32]) -> (i32, i32) {
    if data.is_empty() {
        return (i32::MAX, i32::MIN);
    }

    let mut min = data[0];
    let mut max = data[0];

    for &val in &data[1..] {
        min = min.min(val);
        max = max.max(val);
    }

    (min, max)
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_counting_sort() {
        let mut data = vec![5, 2, 8, 1, 9, 3, 7, 4, 6];
        AdaptiveSort::counting_sort(&mut data, 1, 9);
        assert_eq!(data, vec![1, 2, 3, 4, 5, 6, 7, 8, 9]);
    }

    #[test]
    fn test_pattern_detection() {
        // Need at least 100 elements for pattern detection
        let sorted: Vec<i32> = (1..=100).collect();
        assert!(matches!(
            AdaptiveSort::detect_patterns(&sorted),
            DataPattern::MostlySorted
        ));

        let reversed: Vec<i32> = (1..=100).rev().collect();
        assert!(matches!(
            AdaptiveSort::detect_patterns(&reversed),
            DataPattern::MostlyReversed
        ));

        // Test with many duplicates
        let mut duplicates = vec![1; 50];
        duplicates.extend(vec![2; 50]);
        assert!(matches!(
            AdaptiveSort::detect_patterns(&duplicates),
            DataPattern::ManyDuplicates
        ));

        // Test that small arrays return Random
        let small = vec![1, 2, 3, 4, 5];
        assert!(matches!(
            AdaptiveSort::detect_patterns(&small),
            DataPattern::Random
        ));
    }
}