gnu_sort/

zero_copy.rs

use crate::locale;
use crate::simd_compare::SIMDCompare;
use memmap2::Mmap;
use std::cmp::Ordering;
use std::fs::File;
use std::io::{self, BufRead, BufReader};
use std::path::Path;

/// Zero-copy line representation that points directly into memory-mapped data
#[derive(Debug, Clone, Copy)]
pub struct Line {
    /// Pointer to the start of the line in the mapped memory
    start: *const u8,
    /// Length of the line (excluding newline)
    len: u32,
}

// SAFETY: Line is safe to send between threads because:
// 1. It only contains pointers to immutable memory-mapped data
// 2. The memory-mapped files remain valid for the entire lifetime of the sort operation
// 3. No thread can mutate the underlying memory during sorting
unsafe impl Send for Line {}
unsafe impl Sync for Line {}

impl Line {
    /// Create a new Line from a slice
    pub fn new(data: &[u8]) -> Self {
        Self {
            start: data.as_ptr(),
            len: data.len() as u32,
        }
    }

    /// Get the line data as a byte slice
    /// # Safety
    /// The caller must ensure that:
    /// 1. The memory this Line points to is still valid (not freed)
    /// 2. The memory-mapped file has not been unmapped
    /// 3. No other code is mutating this memory region
    pub unsafe fn as_bytes(&self) -> &[u8] {
        // SAFETY: We create a slice from the raw pointer with the stored length.
        // The caller guarantees the memory is still valid and immutable.
        unsafe { std::slice::from_raw_parts(self.start, self.len as usize) }
    }

    /// Extract a field from the line based on field separator
    /// Fields are 1-indexed (field 1 is the first field)
    pub fn extract_field(&self, field_num: usize, separator: Option<char>) -> Option<&[u8]> {
        if field_num == 0 {
            return None;
        }

        let bytes = unsafe { self.as_bytes() };

        // If no separator specified, use whitespace
        if separator.is_none() {
            return self.extract_field_by_whitespace(bytes, field_num);
        }

        let sep_byte = separator.unwrap() as u8;
        let mut field_count = 1;
        let mut field_start = 0;

        for (i, &byte) in bytes.iter().enumerate() {
            if byte == sep_byte {
                if field_count == field_num {
                    return Some(&bytes[field_start..i]);
                }
                field_count += 1;
                field_start = i + 1;
            }
        }

        // Check if we're looking for the last field
        if field_count == field_num && field_start < bytes.len() {
            return Some(&bytes[field_start..]);
        }

        None
    }

    /// Extract field by whitespace (default behavior when no separator is specified)
    /// Fields include leading whitespace from previous field separator (GNU sort behavior)
    fn extract_field_by_whitespace<'a>(
        &self,
        bytes: &'a [u8],
        field_num: usize,
    ) -> Option<&'a [u8]> {
        if field_num == 1 {
            // Special case: field 1 starts at beginning of line
            // Skip leading whitespace to find start of field 1
            let mut field_start = 0;
            for (i, &byte) in bytes.iter().enumerate() {
                if byte != b' ' && byte != b'\t' {
                    field_start = i;
                    break;
                }
            }

            // Find the end of field 1 (first whitespace or end of line)
            for (i, &byte) in bytes[field_start..].iter().enumerate() {
                if byte == b' ' || byte == b'\t' {
                    return Some(&bytes[field_start..field_start + i]);
                }
            }
            return Some(&bytes[field_start..]); // Entire remaining line is field 1
        }

        // For fields > 1, use a different approach
        // First, skip initial whitespace and find all field boundaries
        let mut field_boundaries = Vec::new();
        let mut in_field = false;
        let mut field_start = 0;

        for (i, &byte) in bytes.iter().enumerate() {
            let is_whitespace = byte == b' ' || byte == b'\t';

            if !is_whitespace && !in_field {
                // Starting a new field
                field_start = i;
                in_field = true;
            } else if is_whitespace && in_field {
                // Ending a field
                field_boundaries.push(field_start..i);
                in_field = false;
            }
        }

        // Handle case where line ends with a field (no trailing whitespace)
        if in_field {
            field_boundaries.push(field_start..bytes.len());
        }

        if field_num > field_boundaries.len() {
            return None;
        }

        let target_field = &field_boundaries[field_num - 1];

        // For field 1, return just the field content
        if field_num == 1 {
            return Some(&bytes[target_field.clone()]);
        }

        // For fields > 1, include the whitespace before the field
        // Find where the previous field ended
        let prev_field_end = if field_num > 1 {
            field_boundaries[field_num - 2].end
        } else {
            0
        };

        // The field includes whitespace from previous field end to current field end
        Some(&bytes[prev_field_end..target_field.end])
    }

    /// Extract a key region from the line based on SortKey specification
    pub fn extract_key(
        &self,
        key: &crate::config::SortKey,
        separator: Option<char>,
    ) -> Option<&[u8]> {
        // Extract the starting field
        let start_field_data = self.extract_field(key.start_field, separator)?;

        // If no end field specified, use just the start field
        if key.end_field.is_none() {
            // Apply character positions if specified
            if let Some(start_char) = key.start_char {
                if start_char > 0 && start_char <= start_field_data.len() {
                    return Some(&start_field_data[start_char - 1..]);
                }
            }
            return Some(start_field_data);
        }

        // Complex case: range of fields
        // For now, just extract from start field to end field
        // This is a simplified implementation
        let bytes = unsafe { self.as_bytes() };

        // Find start position
        let start_pos = if let Some(field_data) = self.extract_field(key.start_field, separator) {
            let offset = field_data.as_ptr() as usize - bytes.as_ptr() as usize;
            if let Some(start_char) = key.start_char {
                if start_char > 0 && start_char <= field_data.len() {
                    offset + start_char - 1
                } else {
                    offset
                }
            } else {
                offset
            }
        } else {
            return None;
        };

        // Find end position
        let end_pos = if let Some(end_field) = key.end_field {
            if let Some(field_data) = self.extract_field(end_field, separator) {
                let offset = field_data.as_ptr() as usize - bytes.as_ptr() as usize;
                let field_end = offset + field_data.len();
                if let Some(end_char) = key.end_char {
                    if end_char > 0 && end_char <= field_data.len() {
                        offset + end_char
                    } else {
                        field_end
                    }
                } else {
                    field_end
                }
            } else {
                bytes.len()
            }
        } else {
            bytes.len()
        };

        if start_pos < end_pos && start_pos < bytes.len() {
            Some(&bytes[start_pos..end_pos.min(bytes.len())])
        } else {
            None
        }
    }

    /// Fast numeric parsing for simple integers (optimized path)
    pub fn parse_int(&self) -> Option<i64> {
        // SAFETY: as_bytes() is safe here because Line was created from valid memory
        // that remains valid throughout the sorting operation
        let bytes = unsafe { self.as_bytes() };
        if bytes.is_empty() {
            return Some(0);
        }

        let mut start = 0;
        let negative = if bytes[0] == b'-' {
            start = 1;
            true
        } else {
            false
        };

        if start >= bytes.len() {
            return None;
        }

        let mut result: i64 = 0;
        for &byte in &bytes[start..] {
            if !byte.is_ascii_digit() {
                return None;
            }
            result = result.checked_mul(10)?;
            result = result.checked_add((byte - b'0') as i64)?;
        }

        Some(if negative { -result } else { result })
    }

    /// Parse as general numeric (supports scientific notation, inf, nan)
    pub fn parse_general_numeric(&self) -> f64 {
        let bytes = unsafe { self.as_bytes() };
        if let Ok(s) = std::str::from_utf8(bytes) {
            let trimmed = s.trim();

            // Handle special cases
            if trimmed.is_empty() {
                return 0.0;
            }

            // Parse as float (handles scientific notation automatically)
            match trimmed.parse::<f64>() {
                Ok(val) => val,
                Err(_) => {
                    // Check for special strings
                    let lower = trimmed.to_lowercase();
                    if lower == "inf" || lower == "+inf" || lower == "infinity" {
                        f64::INFINITY
                    } else if lower == "-inf" || lower == "-infinity" {
                        f64::NEG_INFINITY
                    } else if lower == "nan" {
                        f64::NAN
                    } else {
                        // Non-numeric strings sort to beginning (like GNU sort)
                        f64::NEG_INFINITY
                    }
                }
            }
        } else {
            f64::NEG_INFINITY
        }
    }

    /// Compare as general numeric values (scientific notation support)
    pub fn compare_general_numeric(&self, other: &Line) -> Ordering {
        let a = self.parse_general_numeric();
        let b = other.parse_general_numeric();

        // Handle NaN specially (NaN sorts last in GNU sort)
        match (a.is_nan(), b.is_nan()) {
            (true, true) => unsafe { self.as_bytes().cmp(other.as_bytes()) }, // Lexicographic tie-breaker
            (true, false) => Ordering::Greater,
            (false, true) => Ordering::Less,
            (false, false) => {
                // Use total_cmp for consistent ordering including -0.0 vs 0.0
                match a.total_cmp(&b) {
                    Ordering::Equal => {
                        // When numeric values are equal, use lexicographic comparison as tie-breaker
                        // This matches GNU sort behavior
                        unsafe { self.as_bytes().cmp(other.as_bytes()) }
                    }
                    other => other,
                }
            }
        }
    }

    /// Compare lines using field-based sorting with multiple keys
    pub fn compare_with_keys(
        &self,
        other: &Line,
        keys: &[crate::config::SortKey],
        separator: Option<char>,
        config: &crate::config::SortConfig,
    ) -> Ordering {
        if keys.is_empty() {
            // No keys specified, compare entire lines based on global options
            return self.compare_with_config(other, config);
        }

        // Compare using each key in order
        for key in keys {
            let self_field = self.extract_key(key, separator);
            let other_field = other.extract_key(key, separator);

            let cmp = match (self_field, other_field) {
                (Some(a), Some(b)) => {
                    // Create temporary Line structs for the extracted fields
                    let a_line = Line::new(a);
                    let b_line = Line::new(b);

                    // Compare based on key options
                    let result = if key.options.general_numeric {
                        a_line.compare_general_numeric(&b_line)
                    } else if key.options.numeric {
                        a_line.compare_numeric(&b_line)
                    } else if key.options.month {
                        a_line.compare_month(&b_line)
                    } else if key.options.version {
                        a_line.compare_version(&b_line)
                    } else if key.options.human_numeric {
                        a_line.compare_human_numeric(&b_line)
                    } else if key.options.dictionary_order && key.options.ignore_case {
                        a_line.compare_dictionary_order_ignore_case(&b_line)
                    } else if key.options.dictionary_order {
                        a_line.compare_dictionary_order(&b_line)
                    } else if key.options.ignore_case {
                        a_line.compare_ignore_case(&b_line)
                    } else if key.options.ignore_leading_blanks {
                        a_line.compare_lexicographic_with_blanks(&b_line, true)
                    } else {
                        a_line.compare_lexicographic(&b_line)
                    };

                    // Apply reverse if specified for this key
                    let final_result = if key.options.reverse {
                        result.reverse()
                    } else {
                        result
                    };

                    // Debug output if enabled (GNU sort compatible)
                    if config.debug {
                        let self_bytes = unsafe { self.as_bytes() };
                        let other_bytes = unsafe { other.as_bytes() };
                        let self_str = String::from_utf8_lossy(self_bytes);
                        let other_str = String::from_utf8_lossy(other_bytes);
                        let a_str = String::from_utf8_lossy(a);
                        let b_str = String::from_utf8_lossy(b);

                        // Convert Ordering to GNU sort style number
                        let cmp_val = match final_result {
                            Ordering::Greater => 1,
                            Ordering::Less => -1,
                            Ordering::Equal => 0,
                        };

                        eprintln!("; k1=<{a_str}>; k2=<{b_str}>; s1=<{self_str}>, s2=<{other_str}>; cmp1={cmp_val}");
                    }

                    final_result
                }
                (None, Some(_)) => Ordering::Less,
                (Some(_), None) => Ordering::Greater,
                (None, None) => Ordering::Equal,
            };

            if cmp != Ordering::Equal {
                return cmp;
            }
        }

        // All keys compared equal, use stable sort order (original line order)
        if config.stable {
            Ordering::Equal
        } else {
            // Use entire line as tie-breaker
            self.compare_lexicographic(other)
        }
    }

    /// Compare lines based on global configuration (when no keys are specified)
    pub fn compare_with_config(
        &self,
        other: &Line,
        config: &crate::config::SortConfig,
    ) -> Ordering {
        let cmp = match config.mode {
            crate::config::SortMode::GeneralNumeric => self.compare_general_numeric(other),
            crate::config::SortMode::Numeric => self.compare_numeric(other),
            crate::config::SortMode::Month => self.compare_month(other),
            crate::config::SortMode::Version => self.compare_version(other),
            crate::config::SortMode::HumanNumeric => self.compare_human_numeric(other),
            crate::config::SortMode::Lexicographic => {
                if config.dictionary_order && config.ignore_case {
                    self.compare_dictionary_order_ignore_case(other)
                } else if config.dictionary_order {
                    self.compare_dictionary_order(other)
                } else if config.ignore_case {
                    self.compare_ignore_case(other)
                } else if config.ignore_leading_blanks {
                    self.compare_lexicographic_with_blanks(other, true)
                } else {
                    self.compare_lexicographic(other)
                }
            }
            _ => {
                // For other modes, also check dictionary_order flag
                if config.dictionary_order {
                    self.compare_dictionary_order(other)
                } else if config.ignore_leading_blanks {
                    self.compare_lexicographic_with_blanks(other, true)
                } else {
                    self.compare_lexicographic(other)
                }
            }
        };

        if config.reverse {
            cmp.reverse()
        } else {
            cmp
        }
    }

    /// Fast comparison for numeric values (GNU sort style - no string conversion)
    pub fn compare_numeric(&self, other: &Line) -> Ordering {
        // Try fast path for simple integers
        if let (Some(a), Some(b)) = (self.parse_int(), other.parse_int()) {
            return a.cmp(&b);
        }

        // GNU sort style: compare as strings with numeric logic
        self.compare_numeric_string_style(other)
    }

    /// GNU sort-style numeric string comparison (key optimization!)
    fn compare_numeric_string_style(&self, other: &Line) -> Ordering {
        let a_bytes = unsafe { self.as_bytes() };
        let b_bytes = unsafe { other.as_bytes() };

        // Skip leading whitespace
        let a_start = self.skip_leading_space(a_bytes);
        let b_start = self.skip_leading_space(b_bytes);

        if a_start >= a_bytes.len() && b_start >= b_bytes.len() {
            return Ordering::Equal;
        }
        if a_start >= a_bytes.len() {
            return Ordering::Less;
        }
        if b_start >= b_bytes.len() {
            return Ordering::Greater;
        }

        let a_rest = &a_bytes[a_start..];
        let b_rest = &b_bytes[b_start..];

        // Check signs
        let (a_negative, a_num_start) = self.parse_sign(a_rest);
        let (b_negative, b_num_start) = self.parse_sign(b_rest);

        match (a_negative, b_negative) {
            (true, false) => Ordering::Less,
            (false, true) => Ordering::Greater,
            _ => {
                // Same sign - compare magnitudes
                let a_digits = &a_rest[a_num_start..];
                let b_digits = &b_rest[b_num_start..];

                // Skip leading zeros (GNU sort behavior)
                let a_no_zeros = self.skip_leading_zeros(a_digits);
                let b_no_zeros = self.skip_leading_zeros(b_digits);

                // Compare by digit count first (major optimization!)
                let a_digit_count = self.count_leading_digits(&a_digits[a_no_zeros..]);
                let b_digit_count = self.count_leading_digits(&b_digits[b_no_zeros..]);

                let magnitude_cmp = match a_digit_count.cmp(&b_digit_count) {
                    Ordering::Equal => {
                        // Same digit count - lexicographic comparison
                        a_digits[a_no_zeros..a_no_zeros + a_digit_count]
                            .cmp(&b_digits[b_no_zeros..b_no_zeros + b_digit_count])
                    }
                    other => other,
                };

                if a_negative {
                    magnitude_cmp.reverse()
                } else {
                    magnitude_cmp
                }
            }
        }
    }

    fn skip_leading_space(&self, bytes: &[u8]) -> usize {
        bytes
            .iter()
            .position(|&b| b != b' ' && b != b'\t')
            .unwrap_or(bytes.len())
    }

    fn parse_sign(&self, bytes: &[u8]) -> (bool, usize) {
        if bytes.is_empty() {
            return (false, 0);
        }
        match bytes[0] {
            b'-' => (true, 1),
            b'+' => (false, 1),
            _ => (false, 0),
        }
    }

    fn skip_leading_zeros(&self, bytes: &[u8]) -> usize {
        bytes.iter().position(|&b| b != b'0').unwrap_or(bytes.len())
    }

    fn count_leading_digits(&self, bytes: &[u8]) -> usize {
        bytes.iter().take_while(|&&b| b.is_ascii_digit()).count()
    }

    /// Byte-level numeric comparison for complex numbers
    #[allow(dead_code)]
    fn compare_numeric_bytes(&self, other: &Line) -> Ordering {
        let a_bytes = unsafe { self.as_bytes() };
        let b_bytes = unsafe { other.as_bytes() };

        // Skip leading whitespace
        let a_trimmed = a_bytes
            .iter()
            .skip_while(|&&b| b == b' ' || b == b'\t')
            .collect::<Vec<_>>();
        let b_trimmed = b_bytes
            .iter()
            .skip_while(|&&b| b == b' ' || b == b'\t')
            .collect::<Vec<_>>();

        if a_trimmed.is_empty() && b_trimmed.is_empty() {
            return Ordering::Equal;
        }
        if a_trimmed.is_empty() {
            return Ordering::Less;
        }
        if b_trimmed.is_empty() {
            return Ordering::Greater;
        }

        // Compare signs
        let a_negative = *a_trimmed[0] == b'-';
        let b_negative = *b_trimmed[0] == b'-';

        match (a_negative, b_negative) {
            (true, false) => Ordering::Less,
            (false, true) => Ordering::Greater,
            _ => {
                // Same sign, compare magnitudes
                let a_digits: Vec<u8> = a_trimmed
                    .iter()
                    .skip_while(|&&&b| b == b'-' || b == b'+')
                    .filter(|&&&b| b.is_ascii_digit())
                    .map(|&&b| b)
                    .collect();
                let b_digits: Vec<u8> = b_trimmed
                    .iter()
                    .skip_while(|&&&b| b == b'-' || b == b'+')
                    .filter(|&&&b| b.is_ascii_digit())
                    .map(|&&b| b)
                    .collect();

                let magnitude_cmp = match a_digits.len().cmp(&b_digits.len()) {
                    Ordering::Equal => a_digits.cmp(&b_digits),
                    other => other,
                };

                if a_negative {
                    magnitude_cmp.reverse()
                } else {
                    magnitude_cmp
                }
            }
        }
    }

    /// Get the length of the line
    pub fn len(&self) -> usize {
        self.len as usize
    }

    /// Check if the line is empty
    pub fn is_empty(&self) -> bool {
        self.len == 0
    }

    /// Locale-aware case-insensitive comparison
    pub fn compare_ignore_case(&self, other: &Line) -> Ordering {
        let a_bytes = unsafe { self.as_bytes() };
        let b_bytes = unsafe { other.as_bytes() };

        // Use locale-aware comparison if enabled
        if locale::LocaleConfig::is_enabled() {
            locale::smart_compare(a_bytes, b_bytes, true)
        } else {
            // Use SIMD for performance boost when locale is not enabled
            SIMDCompare::compare_case_insensitive_simd(a_bytes, b_bytes)
        }
    }

    /// Locale-aware lexicographic comparison
    pub fn compare_lexicographic(&self, other: &Line) -> Ordering {
        let a_bytes = unsafe { self.as_bytes() };
        let b_bytes = unsafe { other.as_bytes() };

        // Use locale-aware comparison if enabled
        if locale::LocaleConfig::is_enabled() {
            locale::smart_compare(a_bytes, b_bytes, false)
        } else {
            // Use SIMD for maximum performance when locale is not enabled
            SIMDCompare::compare_bytes_simd(a_bytes, b_bytes)
        }
    }

    /// Lexicographic comparison with option to ignore leading blanks
    pub fn compare_lexicographic_with_blanks(
        &self,
        other: &Line,
        ignore_leading_blanks: bool,
    ) -> Ordering {
        let mut a_bytes = unsafe { self.as_bytes() };
        let mut b_bytes = unsafe { other.as_bytes() };

        if ignore_leading_blanks {
            // Skip leading blanks (spaces and tabs)
            let a_start = a_bytes
                .iter()
                .position(|&b| b != b' ' && b != b'\t')
                .unwrap_or(a_bytes.len());
            let b_start = b_bytes
                .iter()
                .position(|&b| b != b' ' && b != b'\t')
                .unwrap_or(b_bytes.len());
            a_bytes = &a_bytes[a_start..];
            b_bytes = &b_bytes[b_start..];
        }

        // Use locale-aware comparison if enabled
        if locale::LocaleConfig::is_enabled() {
            locale::smart_compare(a_bytes, b_bytes, false)
        } else {
            // Use SIMD for maximum performance when locale is not enabled
            SIMDCompare::compare_bytes_simd(a_bytes, b_bytes)
        }
    }

    /// Dictionary order comparison (only alphanumeric characters and blanks)
    pub fn compare_dictionary_order(&self, other: &Line) -> Ordering {
        let a_bytes = unsafe { self.as_bytes() };
        let b_bytes = unsafe { other.as_bytes() };

        let a_filtered = self.filter_dictionary_order(a_bytes);
        let b_filtered = self.filter_dictionary_order(b_bytes);

        // Use locale-aware comparison if enabled
        if locale::LocaleConfig::is_enabled() {
            locale::smart_compare(&a_filtered, &b_filtered, false)
        } else {
            // Use SIMD for maximum performance when locale is not enabled
            SIMDCompare::compare_bytes_simd(&a_filtered, &b_filtered)
        }
    }

    /// Dictionary order with case-insensitive comparison
    pub fn compare_dictionary_order_ignore_case(&self, other: &Line) -> Ordering {
        let a_bytes = unsafe { self.as_bytes() };
        let b_bytes = unsafe { other.as_bytes() };

        let a_filtered = self.filter_dictionary_order(a_bytes);
        let b_filtered = self.filter_dictionary_order(b_bytes);

        // Use locale-aware comparison if enabled
        if locale::LocaleConfig::is_enabled() {
            locale::smart_compare(&a_filtered, &b_filtered, true)
        } else {
            // Use SIMD for performance boost when locale is not enabled
            SIMDCompare::compare_case_insensitive_simd(&a_filtered, &b_filtered)
        }
    }

    /// Filter bytes to keep only alphanumeric characters and blanks (spaces/tabs)
    /// This implements GNU sort's dictionary order (-d flag)
    fn filter_dictionary_order(&self, bytes: &[u8]) -> Vec<u8> {
        // Convert to string to properly handle Unicode
        if let Ok(s) = std::str::from_utf8(bytes) {
            s.chars()
                .filter(|c| c.is_alphanumeric() || *c == ' ' || *c == '\t')
                .collect::<String>()
                .into_bytes()
        } else {
            // Fallback for non-UTF8 - filter ASCII only
            bytes
                .iter()
                .filter(|&&b| b.is_ascii_alphanumeric() || b == b' ' || b == b'\t')
                .copied()
                .collect()
        }
    }

    /// Month-aware comparison (GNU sort compatible)
    pub fn compare_month(&self, other: &Line) -> Ordering {
        let a_bytes = unsafe { self.as_bytes() };
        let b_bytes = unsafe { other.as_bytes() };

        fn month_value(bytes: &[u8]) -> u8 {
            // Convert to uppercase for case-insensitive comparison
            let upper_bytes: Vec<u8> = bytes.iter().map(|b| b.to_ascii_uppercase()).collect();

            // Try to match month abbreviations (GNU sort standard)
            match upper_bytes.as_slice() {
                b"JAN" | b"JANUARY" => 1,
                b"FEB" | b"FEBRUARY" => 2,
                b"MAR" | b"MARCH" => 3,
                b"APR" | b"APRIL" => 4,
                b"MAY" => 5,
                b"JUN" | b"JUNE" => 6,
                b"JUL" | b"JULY" => 7,
                b"AUG" | b"AUGUST" => 8,
                b"SEP" | b"SEPTEMBER" => 9,
                b"OCT" | b"OCTOBER" => 10,
                b"NOV" | b"NOVEMBER" => 11,
                b"DEC" | b"DECEMBER" => 12,
                _ => 0, // Unknown month, will be compared lexicographically
            }
        }

        let a_month = month_value(a_bytes);
        let b_month = month_value(b_bytes);

        match (a_month, b_month) {
            // Both are recognized months - compare by month order
            (a, b) if a > 0 && b > 0 => a.cmp(&b),
            // Only a is a month - non-months come before months (GNU sort behavior)
            (a, 0) if a > 0 => Ordering::Greater,
            // Only b is a month - non-months come before months (GNU sort behavior)
            (0, b) if b > 0 => Ordering::Less,
            // Neither is a month - fall back to lexicographic comparison
            (0, 0) => self.compare_lexicographic(other),
            // Catch-all for any other cases (should not occur, but satisfies compiler)
            _ => self.compare_lexicographic(other),
        }
    }

    /// Version-aware comparison (GNU sort -V compatible)
    pub fn compare_version(&self, other: &Line) -> Ordering {
        let a_bytes = unsafe { self.as_bytes() };
        let b_bytes = unsafe { other.as_bytes() };

        // Convert to strings for version parsing
        let a_str = String::from_utf8_lossy(a_bytes);
        let b_str = String::from_utf8_lossy(b_bytes);

        Self::compare_version_strings(&a_str, &b_str)
    }

    /// Compare two version strings (like "1.2.3" vs "1.10.1")
    fn compare_version_strings(a: &str, b: &str) -> Ordering {
        // Split by non-alphanumeric characters and compare each component
        let a_parts = Self::version_tokenize(a);
        let b_parts = Self::version_tokenize(b);

        for (a_part, b_part) in a_parts.iter().zip(b_parts.iter()) {
            match Self::compare_version_component(a_part, b_part) {
                Ordering::Equal => continue,
                other => return other,
            }
        }

        // If all compared parts are equal, longer version wins
        a_parts.len().cmp(&b_parts.len())
    }

    /// Tokenize version string into alphanumeric components
    fn version_tokenize(s: &str) -> Vec<String> {
        let mut tokens = Vec::new();
        let mut current = String::new();
        let mut in_alpha = false;

        for ch in s.chars() {
            let is_alpha = ch.is_alphabetic();
            let is_digit = ch.is_ascii_digit();

            if is_alpha || is_digit {
                if in_alpha != is_alpha && !current.is_empty() {
                    tokens.push(current);
                    current = String::new();
                }
                current.push(ch);
                in_alpha = is_alpha;
            } else if !current.is_empty() {
                tokens.push(current);
                current = String::new();
            }
        }

        if !current.is_empty() {
            tokens.push(current);
        }

        tokens
    }

    /// Compare individual version components (numeric or alphabetic)
    fn compare_version_component(a: &str, b: &str) -> Ordering {
        // Check if both are numeric
        if let (Ok(a_num), Ok(b_num)) = (a.parse::<u64>(), b.parse::<u64>()) {
            return a_num.cmp(&b_num);
        }

        // Check if one is numeric and other is not (numeric comes first)
        match (
            a.chars().all(|c| c.is_ascii_digit()),
            b.chars().all(|c| c.is_ascii_digit()),
        ) {
            (true, false) => Ordering::Less,
            (false, true) => Ordering::Greater,
            _ => a.cmp(b), // Both non-numeric, lexicographic comparison
        }
    }

    /// Human numeric comparison (GNU sort -h compatible)
    pub fn compare_human_numeric(&self, other: &Line) -> Ordering {
        let a_bytes = unsafe { self.as_bytes() };
        let b_bytes = unsafe { other.as_bytes() };

        let a_string = String::from_utf8_lossy(a_bytes);
        let b_string = String::from_utf8_lossy(b_bytes);
        let a_str = a_string.trim();
        let b_str = b_string.trim();

        let a_val = Self::parse_human_numeric(a_str);
        let b_val = Self::parse_human_numeric(b_str);

        match (a_val, b_val) {
            (Some(a), Some(b)) => {
                match a.partial_cmp(&b) {
                    Some(ord) => ord,
                    None => a_str.cmp(b_str), // Handle NaN case
                }
            }
            (Some(_), None) => Ordering::Less, // Numbers before non-numbers
            (None, Some(_)) => Ordering::Greater, // Numbers before non-numbers
            (None, None) => a_str.cmp(b_str),  // Both non-numeric
        }
    }

    /// Parse human-readable numeric value (like "1K", "2.5M", "1G")
    fn parse_human_numeric(s: &str) -> Option<f64> {
        if s.is_empty() {
            return None;
        }

        let s = s.trim();
        let last_char = s.chars().last()?;

        let multiplier = match last_char.to_ascii_uppercase() {
            'K' => 1024.0,
            'M' => 1024.0 * 1024.0,
            'G' => 1024.0 * 1024.0 * 1024.0,
            'T' => 1024.0 * 1024.0 * 1024.0 * 1024.0,
            'P' => 1024.0 * 1024.0 * 1024.0 * 1024.0 * 1024.0,
            _ => {
                // No suffix, parse as regular number
                return s.parse::<f64>().ok();
            }
        };

        // Parse the numeric part (without the suffix)
        let numeric_part = s[..s.len() - 1].trim();
        let value = numeric_part.parse::<f64>().ok()?;

        Some(value * multiplier)
    }
}

/// Memory-mapped file with parsed lines
pub struct MappedFile {
    _mmap: Mmap, // Keep mmap alive
    lines: Vec<Line>,
}

impl MappedFile {
    /// Create a new SimpleMappedFile from a file path
    pub fn new(path: &Path) -> io::Result<Self> {
        let file = File::open(path)?;
        let mmap = unsafe { Mmap::map(&file)? };

        // Parse lines while keeping references to the mmap
        let lines = parse_lines(&mmap);

        Ok(Self { _mmap: mmap, lines })
    }

    /// Get the lines in this file
    pub fn lines(&self) -> &[Line] {
        &self.lines
    }
}

/// Fast line parsing that creates Line structs pointing into the mmap'd data
fn parse_lines(data: &[u8]) -> Vec<Line> {
    let mut lines = Vec::new();
    let mut start = 0;

    for (i, &byte) in data.iter().enumerate() {
        if byte == b'\n' {
            // Handle both Unix (\n) and Windows (\r\n) line endings
            let end = if i > 0 && data[i - 1] == b'\r' {
                i - 1
            } else {
                i
            };
            let line_data = &data[start..end];
            lines.push(Line::new(line_data));
            start = i + 1;
        }
    }

    // Handle last line if it doesn't end with newline
    if start < data.len() {
        let mut end = data.len();
        // Strip trailing \r if present
        if end > start && data[end - 1] == b'\r' {
            end -= 1;
        }
        let line_data = &data[start..end];
        lines.push(Line::new(line_data));
    }

    lines
}

/// Zero-copy line reader for streaming large files
pub struct ZeroCopyReader {
    reader: BufReader<File>,
    buffer: Vec<u8>,
    lines: Vec<Line>,
}

impl ZeroCopyReader {
    pub fn new(file: File) -> Self {
        Self {
            reader: BufReader::new(file),
            buffer: Vec::with_capacity(64 * 1024), // 64KB buffer
            lines: Vec::new(),
        }
    }

    /// Read next chunk of lines, reusing the internal buffer
    pub fn read_chunk(&mut self) -> io::Result<&[Line]> {
        self.buffer.clear();
        self.lines.clear();

        let mut total_read = 0;
        const CHUNK_SIZE: usize = 64 * 1024;

        // Read up to CHUNK_SIZE bytes
        while total_read < CHUNK_SIZE {
            let mut line_buf = Vec::new();
            let bytes_read = self.reader.read_until(b'\n', &mut line_buf)?;

            if bytes_read == 0 {
                break; // EOF
            }

            let start_idx = self.buffer.len();
            self.buffer.extend_from_slice(&line_buf);

            // Remove trailing newline if present
            let end_idx = if line_buf.ends_with(b"\n") {
                self.buffer.len() - 1
            } else {
                self.buffer.len()
            };

            let line_data = &self.buffer[start_idx..end_idx];
            self.lines.push(Line::new(line_data));

            total_read += bytes_read;
        }

        Ok(&self.lines)
    }
}

/// Optimized numeric comparison for Line structs
pub fn compare_numeric_lines(a: &Line, b: &Line) -> Ordering {
    unsafe {
        let a_bytes = a.as_bytes();
        let b_bytes = b.as_bytes();

        // Fast path for simple integer comparison
        if let (Some(a_num), Some(b_num)) = (parse_int(a_bytes), parse_int(b_bytes)) {
            return a_num.cmp(&b_num);
        }

        // Fall back to lexicographic comparison for complex numbers
        compare_numeric_bytes(a_bytes, b_bytes)
    }
}

/// Fast integer parsing for simple cases (digits only, no signs/decimals)
fn parse_int(bytes: &[u8]) -> Option<i64> {
    if bytes.is_empty() {
        return Some(0);
    }

    let mut result: i64 = 0;
    let mut negative = false;
    let mut start = 0;

    // Handle leading sign
    if bytes[0] == b'-' {
        negative = true;
        start = 1;
    } else if bytes[0] == b'+' {
        start = 1;
    }

    // Parse digits
    for &byte in &bytes[start..] {
        if !byte.is_ascii_digit() {
            return None; // Not a simple integer
        }

        result = result.checked_mul(10)?;
        result = result.checked_add((byte - b'0') as i64)?;
    }

    if negative {
        result = -result;
    }

    Some(result)
}

/// Numeric comparison for complex numbers (with decimals, scientific notation, etc.)
fn compare_numeric_bytes(a: &[u8], b: &[u8]) -> Ordering {
    // Skip leading whitespace
    let a = skip_whitespace(a);
    let b = skip_whitespace(b);

    // Handle empty strings
    match (a.is_empty(), b.is_empty()) {
        (true, true) => return Ordering::Equal,
        (true, false) => return Ordering::Less,
        (false, true) => return Ordering::Greater,
        (false, false) => {
            // Continue with comparison
        }
    }

    // Extract signs
    let (a_negative, a_digits) = extract_sign(a);
    let (b_negative, b_digits) = extract_sign(b);

    // Compare signs
    match (a_negative, b_negative) {
        (false, true) => return Ordering::Greater,
        (true, false) => return Ordering::Less,
        _ => {}
    }

    // Both have same sign, compare magnitudes
    let magnitude_cmp = compare_magnitude(a_digits, b_digits);

    if a_negative {
        magnitude_cmp.reverse()
    } else {
        magnitude_cmp
    }
}

fn skip_whitespace(bytes: &[u8]) -> &[u8] {
    let start = bytes
        .iter()
        .position(|&b| !b.is_ascii_whitespace())
        .unwrap_or(bytes.len());
    &bytes[start..]
}

fn extract_sign(bytes: &[u8]) -> (bool, &[u8]) {
    if bytes.starts_with(b"-") {
        (true, &bytes[1..])
    } else if bytes.starts_with(b"+") {
        (false, &bytes[1..])
    } else {
        (false, bytes)
    }
}

fn compare_magnitude(a: &[u8], b: &[u8]) -> Ordering {
    // Find decimal points
    let a_dot = a.iter().position(|&b| b == b'.');
    let b_dot = b.iter().position(|&b| b == b'.');

    let (a_int, a_frac) = match a_dot {
        Some(pos) => (&a[..pos], &a[pos + 1..]),
        None => (a, &[][..]),
    };

    let (b_int, b_frac) = match b_dot {
        Some(pos) => (&b[..pos], &b[pos + 1..]),
        None => (b, &[][..]),
    };

    // Compare integer parts
    let int_cmp = compare_integer_parts(a_int, b_int);
    if int_cmp != Ordering::Equal {
        return int_cmp;
    }

    // Compare fractional parts
    compare_fractional_parts(a_frac, b_frac)
}

fn compare_integer_parts(a: &[u8], b: &[u8]) -> Ordering {
    // Remove leading zeros
    let a = skip_leading_zeros(a);
    let b = skip_leading_zeros(b);

    // Compare lengths first
    let len_cmp = a.len().cmp(&b.len());
    if len_cmp != Ordering::Equal {
        return len_cmp;
    }

    // Same length, compare digit by digit
    a.cmp(b)
}

fn compare_fractional_parts(a: &[u8], b: &[u8]) -> Ordering {
    let max_len = a.len().max(b.len());

    for i in 0..max_len {
        let a_digit = a.get(i).copied().unwrap_or(b'0');
        let b_digit = b.get(i).copied().unwrap_or(b'0');

        let cmp = a_digit.cmp(&b_digit);
        if cmp != Ordering::Equal {
            return cmp;
        }
    }

    Ordering::Equal
}

fn skip_leading_zeros(bytes: &[u8]) -> &[u8] {
    let start = bytes.iter().position(|&b| b != b'0').unwrap_or(bytes.len());
    if start == bytes.len() {
        b"0" // All zeros, return single zero
    } else {
        &bytes[start..]
    }
}

/// Fast case-insensitive comparison with locale support
pub fn compare_case_insensitive(a: &[u8], b: &[u8]) -> Ordering {
    // Use locale-aware comparison if enabled
    if locale::LocaleConfig::is_enabled() {
        locale::smart_compare(a, b, true)
    } else {
        // Fast path for C/POSIX locale
        let min_len = a.len().min(b.len());

        for i in 0..min_len {
            let a_char = a[i].to_ascii_lowercase();
            let b_char = b[i].to_ascii_lowercase();

            match a_char.cmp(&b_char) {
                Ordering::Equal => continue,
                other => return other,
            }
        }

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

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

    #[test]
    fn test_simple_line_creation() {
        let data = b"hello world";
        let line = Line::new(data);

        unsafe {
            assert_eq!(line.as_bytes(), b"hello world");
        }
        assert_eq!(line.len(), 11);
    }

    #[test]
    fn test_numeric_comparison() {
        let a = Line::new(b"123");
        let b = Line::new(b"456");
        let c = Line::new(b"123");

        assert_eq!(compare_numeric_lines(&a, &b), Ordering::Less);
        assert_eq!(compare_numeric_lines(&b, &a), Ordering::Greater);
        assert_eq!(compare_numeric_lines(&a, &c), Ordering::Equal);
    }

    #[test]
    fn test_simple_int_parsing() {
        assert_eq!(parse_int(b"123"), Some(123));
        assert_eq!(parse_int(b"-456"), Some(-456));
        assert_eq!(parse_int(b"+789"), Some(789));
        assert_eq!(parse_int(b"0"), Some(0));
        assert_eq!(parse_int(b""), Some(0));
        assert_eq!(parse_int(b"12.34"), None); // Not simple
        assert_eq!(parse_int(b"abc"), None); // Not numeric
    }

    #[test]
    fn test_parse_lines_with_different_endings() {
        // Test Unix line endings
        let unix_data = b"line1\nline2\nline3";
        let unix_lines = parse_lines(unix_data);
        assert_eq!(unix_lines.len(), 3);
        unsafe {
            assert_eq!(unix_lines[0].as_bytes(), b"line1");
            assert_eq!(unix_lines[1].as_bytes(), b"line2");
            assert_eq!(unix_lines[2].as_bytes(), b"line3");
        }

        // Test Windows line endings
        let windows_data = b"line1\r\nline2\r\nline3\r\n";
        let windows_lines = parse_lines(windows_data);
        assert_eq!(windows_lines.len(), 3);
        unsafe {
            assert_eq!(windows_lines[0].as_bytes(), b"line1");
            assert_eq!(windows_lines[1].as_bytes(), b"line2");
            assert_eq!(windows_lines[2].as_bytes(), b"line3");
        }

        // Test mixed line endings
        let mixed_data = b"line1\r\nline2\nline3\r";
        let mixed_lines = parse_lines(mixed_data);
        assert_eq!(mixed_lines.len(), 3);
        unsafe {
            assert_eq!(mixed_lines[0].as_bytes(), b"line1");
            assert_eq!(mixed_lines[1].as_bytes(), b"line2");
            assert_eq!(mixed_lines[2].as_bytes(), b"line3");
        }

        // Test single line without ending
        let single_data = b"single_line";
        let single_lines = parse_lines(single_data);
        assert_eq!(single_lines.len(), 1);
        unsafe {
            assert_eq!(single_lines[0].as_bytes(), b"single_line");
        }
    }
}