natlex_sort 0.1.0

use natord::compare as natord_compare;
use natord::compare_ignore_case as natord_compare_ignore;
use std::cmp::Ordering;
use std::hash::{Hash, Hasher};

// --- Core Comparison Functions ---

/// A hybrid comparator for string slices:
/// - If the two strings have the same length, performs a standard lexicographical (byte-wise) comparison.
/// - Otherwise, falls back to a natural order comparison (`natord::compare`).
///
/// This is useful for sorting lists containing both fixed-length identifiers (like ULIDs)
/// and variable-length names with embedded numbers (like filenames).
///
/// # Arguments
/// * `a`: The first string slice.
/// * `b`: The second string slice.
///
/// # Returns
/// An `Ordering` indicating whether `a` is less than, equal to, or greater than `b`.
pub fn nat_lex_cmp(a: &str, b: &str) -> Ordering {
  if a.len() == b.len() {
    a.cmp(b) // Standard lexicographical comparison
  } else {
    natord_compare(a, b) // Natural comparison for different lengths
  }
}

/// Case-insensitive version of `nat_lex_cmp`.
///
/// A hybrid comparator for string slices, ignoring ASCII case:
/// - If the two strings have the same length, performs a case-insensitive lexicographical comparison.
///   Uses standard lexicographical comparison as a tie-breaker for stability.
/// - Otherwise, falls back to a case-insensitive natural order comparison (`natord::compare_ignore_case`).
///
/// # Arguments
/// * `a`: The first string slice.
/// * `b`: The second string slice.
///
/// # Returns
/// An `Ordering` indicating whether `a` is less than, equal to, or greater than `b` (ignoring case).
pub fn nat_lex_cmp_ignore(a: &str, b: &str) -> Ordering {
  if a.len() == b.len() {
    // Case-insensitive lexicographical comparison for same length
    // Use iterator-based comparison for potentially better performance
    // and correct handling of Unicode case folding nuances if needed,
    // although str::eq_ignore_ascii_case is often sufficient and simpler.
    let mut a_chars = a.chars();
    let mut b_chars = b.chars();
    loop {
      match (a_chars.next(), b_chars.next()) {
        (Some(ca), Some(cb)) => {
          // Compare lowercase versions first
          let la = ca.to_ascii_lowercase();
          let lb = cb.to_ascii_lowercase();
          if la != lb {
            return la.cmp(&lb);
          }
          // If lowercase is equal, compare original for stability (optional but good)
          // This isn't strictly necessary if natord_compare_ignore doesn't do it,
          // but standard sort often benefits from stability. Let's check natord's behaviour.
          // A simpler approach for ASCII:
          // match la.cmp(&lb) {
          //     Ordering::Equal => {} // Continue if lowercase chars are equal
          //     other => return other,
          // }
          // Let's use eq_ignore_ascii_case and fallback to cmp like the byte version
          // (Assuming ASCII focus based on byte impl)
        }
        (None, None) => break, // Both strings ended at the same time
        (Some(_), None) => return Ordering::Greater, // a is longer
        (None, Some(_)) => return Ordering::Less, // b is longer
      }
    }
    // If case-insensitive comparison is equal, use case-sensitive for tie-breaking
    a.cmp(b)
    // A simpler, potentially faster ASCII-only alternative for same length:
    // a.to_ascii_lowercase().cmp(&b.to_ascii_lowercase()).then_with(|| a.cmp(b))
  } else {
    natord_compare_ignore(a, b) // Natural case-insensitive comparison for different lengths
  }
}

/// A hybrid comparator for byte slices:
/// - If the two slices have the same length, performs a standard lexicographical (byte-wise) comparison.
/// - Otherwise, attempts a natural order comparison suitable for ASCII text with embedded numbers.
///
/// **Note:** The natural comparison logic here is specialized:
/// 1. It iterates through bytes.
/// 2. When ASCII digits are found in both slices, it compares the numeric values:
///    - Leading zeros are skipped.
///    - Numbers with more significant digits are considered greater.
///    - If the number of significant digits is the same, compares digit bytes lexicographically.
/// 3. Non-digit bytes are compared lexicographically.
/// 4. Assumes ASCII encoding for digits and case handling. Non-ASCII bytes are compared bytewise.
/// 5. If the custom comparison results in equality up to the length of the shorter slice,
///    the final result is determined by `a.cmp(b)` (effectively comparing remaining bytes or lengths).
///
/// # Arguments
/// * `a`: The first byte slice.
/// * `b`: The second byte slice.
///
/// # Returns
/// An `Ordering`.
pub fn nat_lex_byte_cmp(a: &[u8], b: &[u8]) -> Ordering {
  if a.len() == b.len() {
    return a.cmp(b); // Standard lexicographical comparison for same length
  }

  // Custom natural-like comparison for different lengths
  let mut i = 0;
  let mut j = 0;

  while i < a.len() && j < b.len() {
    let ca = a[i];
    let cb = b[j];

    // Check for digits in both positions
    if ca.is_ascii_digit() && cb.is_ascii_digit() {
      // --- Numeric comparison block ---
      // Store start indices before skipping leading zeros
      let start_i = i;
      let start_j = j;

      // Skip leading zeros ('0')
      while i < a.len() && a[i] == b'0' {
        i += 1;
      }
      while j < b.len() && b[j] == b'0' {
        j += 1;
      }

      // Mark start of significant digits
      let num_start_i = i;
      let num_start_j = j;

      // Find end of numeric sequence
      while i < a.len() && a[i].is_ascii_digit() {
        i += 1;
      }
      while j < b.len() && b[j].is_ascii_digit() {
        j += 1;
      }

      // Compare lengths of significant digits
      let len_a = i - num_start_i;
      let len_b = j - num_start_j;

      if len_a != len_b {
        return len_a.cmp(&len_b); // Longer number (more digits) is greater
      }

      // If lengths are same, compare digit by digit (lexicographically)
      // This correctly orders numbers like "123" vs "124"
      for k in 0..len_a {
        let da = a[num_start_i + k];
        let db = b[num_start_j + k];
        if da != db {
          return da.cmp(&db);
        }
      }
      // If numbers are numerically equal (e.g., "07" vs "7" after skipping zeros and comparing '7'),
      // loop continues to compare subsequent characters.
      // We might have consumed different numbers of original bytes (due to leading zeros)
      // No: i and j are already advanced to the end of the number sequence.
      // Fallthrough will continue comparison *after* the numbers.
    } else {
      // --- Non-numeric comparison ---
      if ca != cb {
        return ca.cmp(&cb); // Compare bytes directly
      }
      // Move to the next bytes if current ones are equal
      i += 1;
      j += 1;
    }
  }

  // If one slice is a prefix of the other and they compared equally so far,
  // the standard byte comparison correctly handles ordering based on length.
  a.cmp(b)
}

/// Case-insensitive version of `nat_lex_byte_cmp`.
///
/// A hybrid comparator for byte slices, ignoring ASCII case:
/// - If the two slices have the same length, performs a case-insensitive lexicographical comparison.
///   Uses standard lexicographical comparison as a tie-breaker for stability.
/// - Otherwise, attempts a natural order comparison suitable for ASCII text with embedded numbers,
///   ignoring case for non-digit characters.
///
/// See `nat_lex_byte_cmp` for details on the natural comparison logic and ASCII assumptions.
pub fn nat_lex_byte_cmp_ignore(a: &[u8], b: &[u8]) -> Ordering {
  // --- Case 1: Equal lengths ---
  if a.len() == b.len() {
    // Perform full case-insensitive lexicographical compare.
    for idx in 0..a.len() {
      // Use to_ascii_lowercase for comparison
      let ca_lower = a[idx].to_ascii_lowercase();
      let cb_lower = b[idx].to_ascii_lowercase();
      if ca_lower != cb_lower {
        return ca_lower.cmp(&cb_lower);
      }
    }
    // If they are equal ignoring case, fallback to the raw comparison for stability.
    return a.cmp(b);
  }

  // --- Case 2: Different lengths - Custom natural-like comparison ---
  let mut i = 0;
  let mut j = 0;

  while i < a.len() && j < b.len() {
    // Get lowercase versions for non-numeric comparison
    let ca_lower = a[i].to_ascii_lowercase();
    let cb_lower = b[j].to_ascii_lowercase();

    // Check for digits (using original bytes - case doesn't matter for digits)
    if a[i].is_ascii_digit() && b[j].is_ascii_digit() {
      // --- Numeric comparison block (identical to nat_lex_byte_cmp) ---
      let start_i = i; // Keep track for original byte access if needed
      let start_j = j;

      while i < a.len() && a[i] == b'0' {
        i += 1;
      }
      while j < b.len() && b[j] == b'0' {
        j += 1;
      }

      let num_start_i = i;
      let num_start_j = j;

      while i < a.len() && a[i].is_ascii_digit() {
        i += 1;
      }
      while j < b.len() && b[j].is_ascii_digit() {
        j += 1;
      }

      let len_a = i - num_start_i;
      let len_b = j - num_start_j;

      if len_a != len_b {
        return len_a.cmp(&len_b);
      }

      // Compare digits using original bytes (case irrelevant)
      for k in 0..len_a {
        let da = a[num_start_i + k];
        let db = b[num_start_j + k];
        if da != db {
          return da.cmp(&db);
        }
      }
      // Fallthrough if numbers are identical
    } else {
      // --- Non-numeric case-insensitive comparison ---
      if ca_lower != cb_lower {
        return ca_lower.cmp(&cb_lower);
      }
      // Move to the next bytes if current ones are equal (case-insensitively)
      i += 1;
      j += 1;
    }
  }

  // Fallback comparison if one is a prefix of the other (case-sensitive tie-breaker)
  a.cmp(b)
}

// --- Owning Wrapper Structs ---

/// An owning string wrapper that provides natural-lexicographic ordering (`nat_lex_cmp`).
///
/// Equality (`Eq`, `PartialEq`) and ordering (`Ord`, `PartialOrd`) are based on `nat_lex_cmp`.
/// Hashing is based on the underlying string data.
#[derive(Debug, Eq, Clone)]
pub struct NatLexOrderedString(pub String);

impl Ord for NatLexOrderedString {
  fn cmp(&self, other: &Self) -> Ordering {
    nat_lex_cmp(&self.0, &other.0)
  }
}

impl PartialOrd for NatLexOrderedString {
  fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
    Some(self.cmp(other))
  }
}

impl PartialEq for NatLexOrderedString {
  fn eq(&self, other: &Self) -> bool {
    self.cmp(other) == Ordering::Equal
  }
}

impl Hash for NatLexOrderedString {
  fn hash<H: Hasher>(&self, state: &mut H) {
    // Hash the underlying string directly.
    // This ensures that if `a.0 == b.0`, then `hash(a) == hash(b)`.
    // Note: This does NOT guarantee that if `a.cmp(b) == Equal`, then `hash(a) == hash(b)`,
    // because `nat_lex_cmp` can return Equal for different strings (e.g., potentially "file07" vs "file7"
    // depending on exact natord behavior, although unlikely with the length check).
    // However, hashing the underlying data is the standard and safest approach.
    self.0.hash(state);
  }
}

// Optional: Add similar wrapper for case-insensitive comparison if needed
// #[derive(Debug, Eq, Clone)]
// pub struct NatLexOrderedStringIgnoreCase(pub String);
// ... implementations using nat_lex_cmp_ignore ...
// Remember to implement Hash manually here too, likely still hashing self.0

// --- Convenience Conversion Traits for Wrapper ---

impl From<&str> for NatLexOrderedString {
  fn from(value: &str) -> Self {
    NatLexOrderedString(value.to_string())
  }
}

impl From<Box<str>> for NatLexOrderedString {
  fn from(value: Box<str>) -> Self {
    NatLexOrderedString(value.into()) // Use Box<str> -> String conversion
  }
}

impl From<String> for NatLexOrderedString {
  fn from(value: String) -> Self {
    NatLexOrderedString(value)
  }
}

// Implement Into<String> for easier unwrapping
impl From<NatLexOrderedString> for String {
  fn from(value: NatLexOrderedString) -> Self {
    value.0
  }
}

// Keep Into<Box<str>> if it's useful
impl From<NatLexOrderedString> for Box<str> {
  fn from(value: NatLexOrderedString) -> Box<str> {
    value.0.into_boxed_str()
  }
}

// --- Standalone Sort Functions ---

/// Sorts a mutable slice of items implementing `AsRef<str>` in natural-lexicographic order.
/// Uses `nat_lex_cmp`.
///
/// # Examples
/// ```
/// # use natlex_sort::nat_lex_sort; // Assuming 'crate::' if in same crate
/// let mut keys = vec![
///     String::from("hub/note/2note.txt"),
///     String::from("hub/note/01JN7YC5RTJKNKKWNZ5FT9K2YS"), // Fixed length ID
///     String::from("hub/note/01JN4244RAKWNDR48TXFN2XJCY"), // Fixed length ID
///     String::from("hub/note/1note.txt"),
///     String::from("hub/note/10note.txt"),
/// ];
/// nat_lex_sort(&mut keys);
/// assert_eq!(keys, vec![
///     "hub/note/01JN4244RAKWNDR48TXFN2XJCY", // Sorted lexicographically (same length)
///     "hub/note/01JN7YC5RTJKNKKWNZ5FT9K2YS",
///     "hub/note/1note.txt", // Sorted naturally (different lengths)
///     "hub/note/2note.txt",
///     "hub/note/10note.txt",
/// ]);
/// ```
pub fn nat_lex_sort<T: AsRef<str>>(slice: &mut [T]) {
  slice.sort_by(|a, b| nat_lex_cmp(a.as_ref(), b.as_ref()));
}

/// Sorts a mutable slice of items implementing `AsRef<str>` in natural-lexicographic order, ignoring ASCII case.
/// Uses `nat_lex_cmp_ignore`.
pub fn nat_lex_sort_ignore_case<T: AsRef<str>>(slice: &mut [T]) {
  slice.sort_by(|a, b| nat_lex_cmp_ignore(a.as_ref(), b.as_ref()));
}

/// Sorts a mutable slice of byte slices (`&[u8]`) in natural-lexicographic order.
/// Uses `nat_lex_byte_cmp`. See its documentation for details on the comparison logic.
pub fn nat_lex_sort_bytes(slice: &mut [&[u8]]) {
  slice.sort_by(|a, b| nat_lex_byte_cmp(a, b));
}

/// Sorts a mutable slice of byte slices (`&[u8]`) in natural-lexicographic order, ignoring ASCII case.
/// Uses `nat_lex_byte_cmp_ignore`. See its documentation for details on the comparison logic.
pub fn nat_lex_sort_bytes_ignore_case(slice: &mut [&[u8]]) {
  slice.sort_by(|a, b| nat_lex_byte_cmp_ignore(a, b));
}

// --- Tests ---
#[cfg(test)]
mod tests {
  use super::*;
  use std::collections::HashSet;

  // Helper macro for creating Vec<String>
  macro_rules! vec_string {
        ($($x:expr),* $(,)?) => (vec![$($x.to_string()),*]);
    }

  // Helper macro for creating Vec<&[u8]>
  macro_rules! vec_bytes {
        ($($x:expr),* $(,)?) => (vec![$($x.as_bytes()),*]);
    }

  // --- nat_lex_cmp Tests ---
  #[test]
  fn test_cmp_fixed_length() {
    assert_eq!(nat_lex_cmp("id_abc", "id_abd"), Ordering::Less);
    assert_eq!(nat_lex_cmp("id_abd", "id_abc"), Ordering::Greater);
    assert_eq!(nat_lex_cmp("id_abc", "id_abc"), Ordering::Equal);
    assert_eq!(
      nat_lex_cmp("01JN4244RAKWNDR48TXFN2XJCY", "01JN7YC5RTJKNKKWNZ5FT9K2YS"),
      Ordering::Less
    ); // ULIDs
  }

  #[test]
  fn test_cmp_variable_length_natural() {
    assert_eq!(nat_lex_cmp("file1.txt", "file2.txt"), Ordering::Less);
    assert_eq!(nat_lex_cmp("file2.txt", "file10.txt"), Ordering::Less);
    assert_eq!(nat_lex_cmp("file10.txt", "file2.txt"), Ordering::Greater);
    assert_eq!(nat_lex_cmp("file07.txt", "file7.txt"), Ordering::Less); // natord behavior
    assert_eq!(nat_lex_cmp("img12.png", "img100.png"), Ordering::Less);
    assert_eq!(nat_lex_cmp("item 1", "item 2"), Ordering::Less);
    assert_eq!(nat_lex_cmp("item 2", "item 10"), Ordering::Less);
  }

  #[test]
  fn test_cmp_mixed_length_types() {
    // Fixed length vs variable length uses natural sort
    assert_eq!(nat_lex_cmp("id_abc", "id_10"), Ordering::Greater); // "abc" > "10" naturally
    assert_eq!(nat_lex_cmp("file2.txt", "file10.txt"), Ordering::Less); // var vs var -> natural
    assert_eq!(nat_lex_cmp("ID001", "ID002"), Ordering::Less); // fixed vs fixed -> lexicographical
    assert_eq!(nat_lex_cmp("ID001", "file1"), Ordering::Less); // fixed vs var -> natural ("ID001" < "file1")
  }

  #[test]
  fn test_cmp_leading_zeros_natural() {
    assert_eq!(nat_lex_cmp("v01", "v1"), Ordering::Less); // natord treats "01" < "1"
    assert_eq!(nat_lex_cmp("v1", "v001"), Ordering::Greater); // natord treats "1" > "001"
  }

  #[test]
  fn test_cmp_empty_strings() {
    assert_eq!(nat_lex_cmp("", ""), Ordering::Equal);
    assert_eq!(nat_lex_cmp("a", ""), Ordering::Greater);
    assert_eq!(nat_lex_cmp("", "a"), Ordering::Less);
  }

  // --- nat_lex_cmp_ignore Tests ---
  #[test]
  fn test_cmp_ignore_fixed_length() {
    assert_eq!(nat_lex_cmp_ignore("id_abc", "id_abd"), Ordering::Less);
    assert_eq!(nat_lex_cmp_ignore("id_ABC", "id_abd"), Ordering::Less); // Case ignored
    assert_eq!(nat_lex_cmp_ignore("id_abd", "id_ABC"), Ordering::Greater); // Case ignored
    assert_eq!(nat_lex_cmp_ignore("id_abc", "id_abc"), Ordering::Equal);

    // Differ only by case: Should use case-sensitive tie-breaker
    // "id_abc" vs "id_ABC" -> case-insensitively equal -> tie-breaker a.cmp(b) -> 'a' > 'A' -> Greater
    assert_eq!(nat_lex_cmp_ignore("id_abc", "id_ABC"), Ordering::Greater); // Equal ignoring case
                                                                         // Tie-breaking with case
  
    assert_eq!(nat_lex_cmp("id_ABC", "id_abc"), Ordering::Less); // Case sensitive original cmp
    assert_eq!(nat_lex_cmp_ignore("id_ABC", "id_abc"), Ordering::Less); // Should use case sensitive tie breaker
  }

  #[test]
  fn test_cmp_ignore_variable_length_natural() {
    assert_eq!(nat_lex_cmp_ignore("file1.txt", "File2.txt"), Ordering::Less);
    assert_eq!(
      nat_lex_cmp_ignore("FILE2.txt", "file10.txt"),
      Ordering::Less
    );
    assert_eq!(
      nat_lex_cmp_ignore("file10.TXT", "FILE2.txt"),
      Ordering::Greater
    );
    assert_eq!(
      nat_lex_cmp_ignore("file07.txt", "FILE7.txt"),
      Ordering::Less
    ); // natord ignore case behavior
    assert_eq!(
      nat_lex_cmp_ignore("img12.png", "IMG100.png"),
      Ordering::Less
    );
  }

  #[test]
  fn test_cmp_ignore_mixed_length_types() {
    // Different length examples -> use natural comparison
    assert_eq!(nat_lex_cmp_ignore("id_abc", "ID_10"), Ordering::Greater, "Natural comparison: 'abc' > '10'");
    assert_eq!(nat_lex_cmp_ignore("FILE2.txt", "file10.txt"), Ordering::Less, "Natural comparison: 2 < 10");
    assert_eq!(nat_lex_cmp_ignore("ID001", "file100"), Ordering::Greater, "Natural comparison: 1 < 100"); // Added true mixed-length case

    // Same length examples -> use case-insensitive lexicographical comparison
    assert_eq!(nat_lex_cmp_ignore("ID001", "id002"), Ordering::Less, "Lexicographical (i): '1' < '2'");
    assert_eq!(nat_lex_cmp_ignore("id001", "file1"), Ordering::Greater, "Lexicographical (i): 'i' > 'f'");
    assert_eq!(nat_lex_cmp_ignore("ID001", "FILE1"), Ordering::Greater, "Lexicographical (i): 'i' > 'f'");
  }

  // --- Sorting Function Tests ---
  #[test]
  fn test_sort_strings_fixed_length() {
    let mut keys = vec_string!["01JN7YC5RTJKNKKWNZ5FT9K2YS", "01JN4244RAKWNDR48TXFN2XJCY"];
    nat_lex_sort(&mut keys);
    assert_eq!(
      keys,
      vec_string!["01JN4244RAKWNDR48TXFN2XJCY", "01JN7YC5RTJKNKKWNZ5FT9K2YS"]
    );
  }

  #[test]
  fn test_sort_strings_variable_length() {
    let mut keys = vec_string!["2note.txt", "1note.txt", "10note.txt"];
    nat_lex_sort(&mut keys);
    assert_eq!(keys, vec_string!["1note.txt", "2note.txt", "10note.txt"]);
  }

  #[test]
  fn test_sort_strings_mixed_keys() {
    let mut keys = vec_string![
      "hub/note/2note.txt",
      "hub/note/01JN7YC5RTJKNKKWNZ5FT9K2YS",
      "hub/note/01JN4244RAKWNDR48TXFN2XJCY",
      "hub/note/1note.txt",
      "hub/note/10note.txt",
    ];
    nat_lex_sort(&mut keys);
    assert_eq!(
      keys,
      vec_string![
        "hub/note/01JN4244RAKWNDR48TXFN2XJCY", // Lexicographical (same length)
        "hub/note/01JN7YC5RTJKNKKWNZ5FT9K2YS",
        "hub/note/1note.txt", // Natural (different lengths)
        "hub/note/2note.txt",
        "hub/note/10note.txt",
      ]
    );
  }

  #[test]
  fn test_sort_strings_ignore_case() {
    let mut keys = vec_string![
      "Hub/Note/2note.txt",
      "hub/note/01jn7yc5rtjkknkwnz5ft9k2ys", // Lowercase fixed ID
      "hub/note/01JN4244RAKWNDR48TXFN2XJCY", // Uppercase fixed ID
      "hub/note/1Note.txt",
      "hub/note/10note.TXT",
    ];
    nat_lex_sort_ignore_case(&mut keys);
    assert_eq!(
      keys,
      vec_string![
        // Fixed length IDs sorted case-insensitively, then case-sensitively
        "hub/note/01JN4244RAKWNDR48TXFN2XJCY",
        "hub/note/01jn7yc5rtjkknkwnz5ft9k2ys",
        // Variable length filenames sorted naturally, ignoring case
        "hub/note/1Note.txt",
        "Hub/Note/2note.txt",
        "hub/note/10note.TXT",
      ]
    );
  }

  // --- Byte Comparison Tests ---
  #[test]
  fn test_byte_cmp_basic_numbers() {
    // Different lengths -> natural sort logic
    assert_eq!(
      nat_lex_byte_cmp(b"file7.txt", b"file10.txt"),
      Ordering::Less
    ); // 7 < 10
    assert_eq!(
      nat_lex_byte_cmp(b"file10.txt", b"file7.txt"),
      Ordering::Greater
    ); // 10 > 7
    assert_eq!(
      nat_lex_byte_cmp(b"file07.txt", b"file7.txt"),
      Ordering::Less
    ); // '0' skipped, lens equal, compare '7'=='7', then '.' < '7' (this ordering seems odd but consistent with the code)
       // Let's re-evaluate this case:
       // a = file07.txt, b = file7.txt
       // len diff -> nat sort
       // compare 'file' -> equal
       // check '0' vs '7' -> digits
       // skip '0' in a (i=5)
       // num_start_i = 5, num_start_j = 4
       // find end: a -> '7' (i=6), b -> '7' (j=5)
       // len_a = 1, len_b = 1 -> equal
       // compare digits: a[5]='7' vs b[4]='7' -> equal
       // continue loop: i=6, j=5
       // ca = a[6] = '.', cb = b[5] = '.' -> equal
       // continue loop: i=7, j=6
       // ca = a[7] = 't', cb = b[6] = 't' -> equal
       // ... compare 'txt' -> equal
       // loop ends
       // return a.cmp(b) => "file07.txt".cmp("file7.txt") => Less
    assert_eq!(
      nat_lex_byte_cmp(b"img12.png", b"img100.png"),
      Ordering::Less
    ); // 12 < 100
  }

  #[test]
  fn test_byte_cmp_same_length() {
    // Same length -> lexicographical sort logic
    assert_eq!(
      nat_lex_byte_cmp(b"file07.txt", b"file10.txt"),
      Ordering::Less
    ); // '0' < '1'
    assert_eq!(nat_lex_byte_cmp(b"abc123def", b"abc124def"), Ordering::Less); // '3' < '4'
    assert_eq!(
      nat_lex_byte_cmp(b"abc124def", b"abc123def"),
      Ordering::Greater
    );
    assert_eq!(
      nat_lex_byte_cmp(b"abc123def", b"abc123def"),
      Ordering::Equal
    );
  }

  #[test]
  fn test_byte_cmp_mixed_behavior() {
    // Compare same length (lex) vs different length (nat)
    assert_eq!(nat_lex_byte_cmp(b"id_10", b"id_abc"), Ordering::Less); // Different length -> nat -> 10 < abc
    assert_eq!(nat_lex_byte_cmp(b"id_abc", b"id_10"), Ordering::Greater);

    // Compare same length (lex)
    assert_eq!(nat_lex_byte_cmp(b"v1.2", b"v1.10"), Ordering::Less); // Lex: '.' < '1'

    // Compare different length (nat)
    assert_eq!(nat_lex_byte_cmp(b"v1.2", b"v1.10a"), Ordering::Less); // Nat: 2 < 10
  }

  #[test]
  fn test_byte_cmp_numeric_prefix() {
    assert_eq!(nat_lex_byte_cmp(b"1a", b"10a"), Ordering::Less); // Nat: 1 < 10
    assert_eq!(nat_lex_byte_cmp(b"10a", b"1a"), Ordering::Greater);
    assert_eq!(nat_lex_byte_cmp(b"a1", b"a1a"), Ordering::Less); // Prefix handled by final a.cmp(b)
    assert_eq!(nat_lex_byte_cmp(b"a1a", b"a1"), Ordering::Greater);
  }

  #[test]
  fn test_byte_cmp_ignore_case() {
    // Same length, case diff -> case-insensitive lex
    assert_eq!(
      nat_lex_byte_cmp_ignore(b"FileA.txt", b"filea.txt"),
      Ordering::Less
    ); // Tie-breaker: F < f
    assert_eq!(
      nat_lex_byte_cmp_ignore(b"filea.txt", b"FileA.txt"),
      Ordering::Greater
    );
    assert_eq!(
      nat_lex_byte_cmp_ignore(b"FILEA.TXT", b"fileb.txt"),
      Ordering::Less
    ); // a < b

    // Different length, case diff -> nat ignore case
    assert_eq!(
      nat_lex_byte_cmp_ignore(b"file7.txt", b"FILE10.txt"),
      Ordering::Less
    ); // 7 < 10
    assert_eq!(
      nat_lex_byte_cmp_ignore(b"IMG12.png", b"img100.png"),
      Ordering::Less
    ); // 12 < 100

    // This case demonstrates the custom logic:
    // "File"=="FILE" (case-insensitive)
    // Number "07" vs "7" -> skip '0', compare '7'=='7' -> numerically equal in this impl's nat phase
    // Compare rest ".txt"==".txt"
    // Nat phase ends in equality for compared parts.
    // Fallback to a.cmp(b): "File07.txt".cmp("FILE7.txt") -> 'i' > 'I' -> Greater
    assert_eq!(
      nat_lex_byte_cmp_ignore(b"File07.txt", b"FILE7.txt"),
      Ordering::Greater,
      "Nat(i) logic: '07'=='7' num, fallback cmp 'i' > 'I'"
    ); // CORRECTED EXPECTATION
  }

  // --- Byte Sorting Function Tests ---
  #[test]
  fn test_sort_bytes_simple() {
    let mut keys = vec_bytes!["2note.txt", "1note.txt", "10note.txt"];
    nat_lex_sort_bytes(&mut keys);
    assert_eq!(keys, vec_bytes!["1note.txt", "2note.txt", "10note.txt"]);
  }

  #[test]
  fn test_sort_bytes_mixed_keys() {
    let mut keys = vec_bytes![
      "hub/note/2note.txt",
      "hub/note/01JN7YC5RTJKNKKWNZ5FT9K2YS",
      "hub/note/01JN4244RAKWNDR48TXFN2XJCY",
      "hub/note/1note.txt",
      "hub/note/10note.txt",
    ];
    nat_lex_sort_bytes(&mut keys);
    let expected = vec_bytes![
      "hub/note/01JN4244RAKWNDR48TXFN2XJCY", // Lex (same length)
      "hub/note/01JN7YC5RTJKNKKWNZ5FT9K2YS",
      "hub/note/1note.txt", // Nat (diff length)
      "hub/note/2note.txt",
      "hub/note/10note.txt",
    ];
    assert_eq!(keys, expected);
  }

  #[test]
  fn test_sort_bytes_ignore_case() {
    let mut keys = vec_bytes![
      "Hub/Note/2note.txt",
      "hub/note/01jn7yc5rtjkknkwnz5ft9k2ys",
      "hub/note/01JN4244RAKWNDR48TXFN2XJCY",
      "hub/note/1Note.txt",
      "hub/note/10note.TXT",
    ];
    nat_lex_sort_bytes_ignore_case(&mut keys);
    let expected = vec_bytes![
      "hub/note/01JN4244RAKWNDR48TXFN2XJCY", // Case-insensitive lex, F < f tiebreak
      "hub/note/01jn7yc5rtjkknkwnz5ft9k2ys",
      "hub/note/1Note.txt", // Case-insensitive nat
      "Hub/Note/2note.txt",
      "hub/note/10note.TXT",
    ];
    assert_eq!(keys, expected);
  }

  // --- NatLexOrderedString Tests ---
  #[test]
  fn test_ordered_string_sorting() {
    let mut vec = vec![
      NatLexOrderedString::from("file10.txt"),
      NatLexOrderedString::from("file2.txt"), // Different length -> nat
      NatLexOrderedString::from("id002"),
      NatLexOrderedString::from("id001"), // Same length -> lex
    ];
    vec.sort();
    let expected = vec![
      NatLexOrderedString::from("file2.txt"),
      NatLexOrderedString::from("file10.txt"),
      NatLexOrderedString::from("id001"),
      NatLexOrderedString::from("id002"),
    ];
    assert_eq!(vec, expected);
  }

  #[test]
  fn test_ordered_string_hash() {
    // Test that identical underlying strings produce equal wrappers and equal hashes
    let s1 = NatLexOrderedString::from("test1");
    let s2 = NatLexOrderedString::from("test1");
    // Test that different underlying strings produce different wrappers (!=)
    // but might compare Equal via nat_lex_cmp in some cases (less likely with the length check)
    let s3 = NatLexOrderedString::from("test2");
    let s4 = NatLexOrderedString::from("test01"); // Different length
    let s5 = NatLexOrderedString::from("test1"); // Same length

    let mut set = HashSet::new();
    assert!(set.insert(s1.clone()));
    assert!(!set.insert(s2.clone())); // s2 should be equal to s1
    assert!(set.insert(s3.clone()));
    assert!(set.insert(s4.clone())); // Should be different from s1/s2 in hashset

    assert_eq!(s1, s2);
    assert_ne!(s1, s3);
    assert_ne!(s1, s4); // s1 != s4 via nat_lex_cmp
    assert_eq!(s1, s5);

    // Check hashes (relies on the default hasher, but good enough for a basic check)
    let hash = |s: &NatLexOrderedString| -> u64 {
      let mut hasher = std::collections::hash_map::DefaultHasher::new();
      s.hash(&mut hasher);
      hasher.finish()
    };

    assert_eq!(hash(&s1), hash(&s2));
    assert_eq!(hash(&s1), hash(&s5));
    assert_ne!(hash(&s1), hash(&s3));
    assert_ne!(hash(&s1), hash(&s4)); // Hash depends on underlying string "test1" vs "test01"
  }
}