Sort Lines & Remove Duplicates — Rust source

// sort-lines — Rust polyglot showcase port.
//
// Pure line-sorting logic — deterministic, stdlib-only. Splits on newlines
// and applies the requested operation. Never panics.
//
// CosmoDev polyglot showcase port of sort-lines, ported from
// src/lib/sortLines.ts. Display source — part of CosmoDev's polyglot
// tool pages.

use std::cmp::Ordering;
use std::collections::HashSet;

/// Selects the line operation to apply.
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub enum SortMode {
    Asc,
    Desc,
    LengthAsc,
    LengthDesc,
    Reverse,
    Shuffle,
    Unique,
}

/// Optional tweaks to comparison and shuffle behaviour. `None` means "use the
/// default", mirroring the TS optional fields (omitted !== false).
#[derive(Default)]
pub struct SortOptions {
    pub case_sensitive: Option<bool>, // default true
    pub trim: Option<bool>,            // default false
    pub natural: Option<bool>,         // default false
    pub seed: Option<u32>,             // default 1
}

/// The output of [`sort_lines`].
pub struct SortResult {
    pub lines: Vec<String>,
    pub text: String,
    pub removed_duplicates: usize,
}

/// mulberry32 — a small deterministic PRNG returning floats in [0, 1).
///
/// Deterministic by design (not cryptographic): a given seed reproduces the
/// same shuffle. All arithmetic uses wrapping 32-bit ops; `>>` on `u32` is the
/// unsigned shift, so the bitstream matches JS's bitwise reference exactly.
pub fn mulberry32(seed: u32) -> impl FnMut() -> f64 {
    let mut a = seed;
    move || {
        a = a.wrapping_add(0x6d2b79f5);
        let mut t = (a ^ (a >> 15)).wrapping_mul(1 | a);
        t = (t.wrapping_add((t ^ (t >> 7)).wrapping_mul(61 | t))) ^ t;
        f64::from(t ^ (t >> 14)) / 4_294_967_296.0
    }
}

/// Splits `s` into alternating runs of ASCII digits and non-digits — the
/// basis of natural-order comparison.
///
/// Walks byte-by-byte, grouping consecutive bytes with the same digit-ness.
/// Because ASCII digits (0x30..=0x39) are always single-byte leading bytes in
/// UTF-8, slice boundaries always land on char boundaries, so the returned
/// `&str` slices are always valid.
fn digit_chunks(s: &str) -> Vec<&str> {
    let bytes = s.as_bytes();
    let mut out = Vec::new();
    let mut start = 0;
    while start < bytes.len() {
        let cur_is_digit = bytes[start].is_ascii_digit();
        let mut i = start;
        while i < bytes.len() && bytes[i].is_ascii_digit() == cur_is_digit {
            i += 1;
        }
        out.push(&s[start..i]);
        start = i;
    }
    out
}

/// Reports whether `s` begins with an ASCII digit. Empty strings return false
/// (mirrors `/^\d/.test('') === false`), which matters for the empty-chunk
/// fallback path.
fn starts_with_digit(s: &str) -> bool {
    match s.as_bytes().first() {
        Some(&b) => b.is_ascii_digit(),
        None => false,
    }
}

/// Natural-order comparator: numeric chunks compare by value so "file2" sorts
/// before "file10" instead of lexicographically.
fn natural_compare(a: &str, b: &str, case_sensitive: bool) -> Ordering {
    // Build the normalised views once and borrow the cheaper representation.
    let owned_a;
    let owned_b;
    let ax: &str = if case_sensitive {
        a
    } else {
        owned_a = a.to_lowercase();
        &owned_a
    };
    let bx: &str = if case_sensitive {
        b
    } else {
        owned_b = b.to_lowercase();
        &owned_b
    };

    let mut aa = digit_chunks(ax);
    let mut bb = digit_chunks(bx);
    if aa.is_empty() {
        aa.push(ax);
    }
    if bb.is_empty() {
        bb.push(bx);
    }

    let n = aa.len().min(bb.len());
    for i in 0..n {
        let an = starts_with_digit(aa[i]);
        let bn = starts_with_digit(bb[i]);
        if an != bn {
            // A digit-run vs a text-run: compare as raw strings.
            return aa[i].cmp(bb[i]);
        }
        if an {
            // Chunks are pure ASCII digits, so parse never fails.
            let av: i64 = aa[i].parse().unwrap_or(0);
            let bv: i64 = bb[i].parse().unwrap_or(0);
            match av.cmp(&bv) {
                Ordering::Equal => {}
                other => return other,
            }
        } else if aa[i] != bb[i] {
            return aa[i].cmp(bb[i]);
        }
    }
    // All compared chunks equal: the shorter run-list wins.
    aa.len().cmp(&bb.len())
}

/// Character count (Unicode codepoints). Matches the TS `.length` for BMP
/// characters; used for length-based modes.
fn char_len(s: &str) -> usize {
    s.chars().count()
}

/// Apply `mode` to the lines of `input` and return the result. All non-unique
/// modes return `removed_duplicates == 0`.
pub fn sort_lines(input: &str, mode: SortMode, opts: &SortOptions) -> SortResult {
    let case_sensitive = opts.case_sensitive.unwrap_or(true);
    let should_trim = opts.trim.unwrap_or(false);
    let natural = opts.natural.unwrap_or(false);
    let seed = opts.seed.unwrap_or(1);

    // "".split('\n') yields [""] — one empty line — and the rest degrades.
    let mut lines: Vec<String> = input.split('\n').map(String::from).collect();
    if should_trim {
        for l in lines.iter_mut() {
            *l = String::from(l.trim());
        }
    }

    let norm = |s: &str| -> String {
        if case_sensitive {
            s.to_owned()
        } else {
            s.to_lowercase()
        }
    };

    let mut removed_duplicates = 0usize;

    match mode {
        SortMode::Unique => {
            // Keep first occurrence of each normalised line; count the rest.
            let mut seen: HashSet<String> = HashSet::with_capacity(lines.len());
            let mut out: Vec<String> = Vec::with_capacity(lines.len());
            for l in lines.drain(..) {
                let key = norm(&l);
                if !seen.insert(key) {
                    removed_duplicates += 1;
                } else {
                    out.push(l);
                }
            }
            lines = out;
        }

        SortMode::Shuffle => {
            // Fisher-Yates with the seeded PRNG -> reproducible ordering.
            let mut rng = mulberry32(seed);
            let len = lines.len();
            for i in (1..len).rev() {
                let j = (rng() * (i as f64 + 1.0)) as usize;
                lines.swap(i, j);
            }
        }

        SortMode::Reverse => {
            lines.reverse();
        }

        SortMode::LengthAsc | SortMode::LengthDesc => {
            // sort_by is stable, so equal lengths keep input order — equivalent
            // to the TS decorate-by-index step.
            lines.sort_by(|a, b| char_len(a).cmp(&char_len(b)));
            if mode == SortMode::LengthDesc {
                lines.reverse();
            }
        }

        _ => {
            // Asc / Desc. Direction is folded into the comparator, so equal
            // elements keep their input order in BOTH directions (stable).
            let reverse = mode == SortMode::Desc;
            if natural {
                // Natural compare isn't expressible as a plain sort key, so
                // go through Ordering directly; stability handles ties.
                lines.sort_by(|a, b| {
                    let c = natural_compare(a, b, case_sensitive);
                    if reverse {
                        c.reverse()
                    } else {
                        c
                    }
                });
            } else {
                // Codepoint ordering (Rust str::cmp) matches JS localeCompare's
                // default for ASCII input.
                lines.sort_by(|a, b| {
                    let c = norm(a).cmp(&norm(b));
                    if reverse {
                        c.reverse()
                    } else {
                        c
                    }
                });
            }
        }
    }

    let text = lines.join("\n");
    SortResult {
        lines,
        text,
        removed_duplicates,
    }
}