Fuzzy Search,
Built to Learn From

pub fn compute_optimized(source: &str, target: &str) -> usize {
    let mut src: Vec<char> = source.chars().collect();
    let mut tgt: Vec<char> = target.chars().collect();
    let (m, n) = (src.len(), tgt.len());
    if m == 0 { return n; }
    if n == 0 { return m; }

    // Put shorter string in column dim → smaller row allocation
    let (src, tgt, m, n) = if m < n {
        (tgt, src, n, m)
    } else {
        (src, tgt, m, n)
    };

    let mut prev: Vec<usize> = (0..=n).collect();
    let mut curr: Vec<usize> = vec![0; n+1];

    for i in 1..=m {
        curr[0] = i;
        for j in 1..=n {
            let cost = usize::from(src[i-1] != tgt[j-1]);
            curr[j] = min(curr[j-1]+1,
                       min(prev[j]+1, prev[j-1]+cost));
        }
        // Swap — O(1), just pointer exchange
        std::mem::swap(&mut prev, &mut curr);
    }
    prev[n]
}

pub fn compute_fast(source: &str, target: &str) -> usize {
    // ASCII: every char = 1 byte, skip Vec<char> allocation
    if source.is_ascii() && target.is_ascii() {
        return fast_bytes(source.as_bytes(), target.as_bytes());
    }
    let src: Vec<char> = source.chars().collect();
    let tgt: Vec<char> = target.chars().collect();
    fast_chars(&src, &tgt)
}

fn fast_bytes(src: &[u8], tgt: &[u8]) -> usize {
    let (m, n) = (src.len(), tgt.len());
    let (src, tgt) = if m < n { (tgt, src) } else { (src, tgt) };

    // Gap cost = 1 ⇒ no cell exceeds max(m, n). Pick the narrowest
    // integer type that can hold it — u8 fits 99% of fuzzy-search inputs.
    let max_dist = src.len();
    if max_dist <= u8::MAX as usize {
        fast_bytes_dp::<u8>(src, tgt)   // 1-byte cells: entire DP fits in L1
    } else if max_dist <= u16::MAX as usize {
        fast_bytes_dp::<u16>(src, tgt)  // 2-byte cells
    } else {
        fast_bytes_dp::<u32>(src, tgt)  // 4-byte cells (4 B strings…)
    }
}

// Monomorphised per cell type — three tight specialised loops.
fn fast_bytes_dp<T: DpCell>(src: &[u8], tgt: &[u8]) -> usize {
    let (m, n) = (src.len(), tgt.len());
    let mut prev: Vec<T> = (0..=n).map(T::from_usize).collect();
    let mut curr: Vec<T> = vec![T::from_usize(0); n+1];

    for i in 1..=m {
        curr[0] = T::from_usize(i);
        let s = src[i-1];
        for j in 1..=n {
            let cost = if s == tgt[j-1] { T::from_usize(0) } else { T::ONE };
            curr[j] = curr[j-1].add(T::ONE)
                .min(prev[j].add(T::ONE))
                .min(prev[j-1].add(cost));
        }
        std::mem::swap(&mut prev, &mut curr);
    }
    prev[n].to_usize()
}

pub fn compute_myers(source: &str, target: &str) -> usize {
    if source.is_ascii() && target.is_ascii() {
        let (a, b) = (source.as_bytes(), target.as_bytes());
        if a.len().min(b.len()) <= 64 {
            return myers_bytes(a, b);
        }
    }
    Self::compute_fast(source, target)
}

fn myers_bytes(a: &[u8], b: &[u8]) -> usize {
    // Shorter string becomes the pattern `p` (fits in one u64)
    let (p, t) = if a.len() <= b.len() { (a, b) } else { (b, a) };
    let m = p.len();
    if m == 0 { return t.len(); }

    // Peq[c] = bitmask of positions where byte c occurs in p
    let mut peq = [0u64; 128];  // ASCII only — 128 slots are enough
    for (i, &c) in p.iter().enumerate() {
        peq[(c & 0x7F) as usize] |= 1u64 << i;
    }

    let mask   = if m == 64 { u64::MAX } else { (1u64 << m) - 1 };
    let top    = 1u64 << (m - 1);
    let mut pv = mask;   // all deltas +1 initially (column = 0,1,…,m)
    let mut mv = 0u64;
    let mut score = m;

    for &c in t {
        let eq = peq[(c & 0x7F) as usize];
        let xv = eq | mv;
        // The carry trick: propagates match runs in one addition
        let xh = (((eq & pv).wrapping_add(pv)) ^ pv) | eq;

        let mut ph = mv | !(xh | pv);
        let mut mh = pv & xh;

        if ph & top != 0 { score += 1; }
        if mh & top != 0 { score -= 1; }

        ph = (ph << 1) | 1;   mh <<= 1;
        pv = (mh & mask) | !((xv | ph) & mask);
        pv &= mask;
        mv = ph & xv & mask;
    }
    score
}