pub fn distance(a: &str, b: &str) -> usize {
let a: Vec<char> = a.chars().collect();
let b: Vec<char> = b.chars().collect();
let (n, m) = (a.len(), b.len());
if n == 0 {
return m;
}
if m == 0 {
return n;
}
let mut prev: Vec<usize> = (0..=m).collect();
let mut cur = vec![0usize; m + 1];
for i in 1..=n {
cur[0] = i;
for j in 1..=m {
let cost = if a[i - 1] == b[j - 1] { 0 } else { 1 };
cur[j] = (prev[j] + 1).min(cur[j - 1] + 1).min(prev[j - 1] + cost);
}
std::mem::swap(&mut prev, &mut cur);
}
prev[m]
}
pub fn closest<'a, I>(input: &str, candidates: I) -> Option<&'a str>
where
I: IntoIterator<Item = &'a str>,
{
let max = threshold(input.len());
let mut best: Option<(&str, usize)> = None;
for c in candidates {
let d = distance(input, c);
if d <= max {
match best {
Some((_, bd)) if d >= bd => {}
_ => best = Some((c, d)),
}
}
}
best.map(|(c, _)| c)
}
pub fn suggestions<'a, I>(input: &str, candidates: I) -> Vec<&'a str>
where
I: IntoIterator<Item = &'a str>,
{
let max = threshold(input.len());
let mut scored: Vec<(&str, usize)> = candidates
.into_iter()
.map(|c| (c, distance(input, c)))
.filter(|(_, d)| *d <= max)
.collect();
scored.sort_by_key(|(_, d)| *d);
scored.into_iter().map(|(c, _)| c).collect()
}
fn threshold(len: usize) -> usize {
match len {
0..=2 => 1,
3..=5 => 2,
_ => 3,
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn distance_basics() {
assert_eq!(distance("", ""), 0);
assert_eq!(distance("abc", "abc"), 0);
assert_eq!(distance("abc", "abd"), 1);
assert_eq!(distance("kitten", "sitting"), 3);
assert_eq!(distance("", "abc"), 3);
}
#[test]
fn closest_within_threshold() {
let cands = ["remote", "commit", "checkout"];
assert_eq!(closest("remoat", cands.iter().copied()), Some("remote"));
assert_eq!(closest("comit", cands.iter().copied()), Some("commit"));
}
#[test]
fn closest_rejects_far() {
let cands = ["remote", "commit"];
assert_eq!(closest("xyzzy", cands.iter().copied()), None);
}
#[test]
fn short_words_need_close_match() {
let cands = ["add", "rm"];
assert_eq!(closest("ad", cands.iter().copied()), Some("add"));
}
#[test]
fn suggestions_sorted() {
let cands = ["list", "lint", "last"];
let s = suggestions("lst", cands.iter().copied());
assert!(!s.is_empty());
assert!(s.contains(&"list"));
}
}