const MAX_EDITS: usize = 3;
const CHARACTERS_PER_EDIT: usize = 3;
pub(super) const TEMPLE_EDITS: usize = 2;
const MAX_CHARACTER_BYTES: usize = 4;
fn edits_for(target: usize) -> usize {
(target / CHARACTERS_PER_EDIT).clamp(1, MAX_EDITS)
}
pub(super) fn cost(target: usize, candidate: usize, edits: usize) -> u64 {
let compared =
candidate + edits >= target && candidate.div_ceil(MAX_CHARACTER_BYTES) <= target + edits;
let table = if compared {
(target as u64 + 1) * (candidate.min(target + edits) as u64 + 1)
} else {
0
};
candidate as u64 + table
}
pub(super) fn closest_cost<'a>(target: &str, candidates: impl Iterator<Item = &'a str>) -> u64 {
let target = target.chars().count();
let edits = edits_for(target);
candidates
.map(|candidate| cost(target, candidate.len(), edits))
.sum()
}
pub(super) fn closest<'a>(
target: &str,
candidates: impl IntoIterator<Item = &'a str>,
) -> Option<&'a str> {
let target: Vec<char> = target.chars().collect();
let limit = edits_for(target.len());
let mut rows = Vec::new();
let mut best: Option<(usize, &str)> = None;
for candidate in candidates {
if candidate.chars().count().abs_diff(target.len()) > limit {
continue;
}
if let Some(distance) = edit_distance_within(&target, candidate, limit, &mut rows) {
let better = match best {
None => true,
Some(best) => (distance, candidate) < best,
};
if better {
best = Some((distance, candidate));
}
}
}
best.map(|(_, candidate)| candidate)
}
fn edit_distance_within(a: &[char], b: &str, limit: usize, rows: &mut Vec<usize>) -> Option<usize> {
let b: Vec<char> = b.chars().collect();
let width = b.len() + 1;
rows.clear();
rows.resize(3 * width, 0);
let (mut back2, mut back1, mut current) = (0, width, 2 * width);
for (j, cell) in rows[back1..back1 + width].iter_mut().enumerate() {
*cell = j;
}
let mut back1_min = 0;
for i in 1..=a.len() {
rows[current] = i;
let mut current_min = i;
for j in 1..width {
let cost = usize::from(a[i - 1] != b[j - 1]);
let mut distance = (rows[back1 + j] + 1)
.min(rows[current + j - 1] + 1)
.min(rows[back1 + j - 1] + cost);
if i > 1 && j > 1 && a[i - 1] == b[j - 2] && a[i - 2] == b[j - 1] {
distance = distance.min(rows[back2 + j - 2] + 1);
}
rows[current + j] = distance;
current_min = current_min.min(distance);
}
if current_min > limit && back1_min > limit {
return None;
}
back1_min = current_min;
(back2, back1, current) = (back1, current, back2);
}
let distance = rows[back1 + width - 1];
(distance <= limit).then_some(distance)
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn suggests_names_a_few_edits_away() {
assert_eq!(closest("nxet", ["next", "done"]), Some("next"));
let long = ["approve_refund_request"];
assert_eq!(closest("approve_refnd_rquest", long), Some(long[0]));
assert_eq!(closest("approve_rfnd_rqst", long), None);
}
}