mod tests;
/// Finds the Levenshtein distance between two strings.
-pub fn lev_distance(a: &str, b: &str) -> usize {
- // cases which don't require further computation
- if a.is_empty() {
- return b.chars().count();
- } else if b.is_empty() {
- return a.chars().count();
+///
+/// Returns None if the distance exceeds the limit.
+pub fn lev_distance(a: &str, b: &str, limit: usize) -> Option<usize> {
+ let n = a.chars().count();
+ let m = b.chars().count();
+ let min_dist = if n < m { m - n } else { n - m };
+
+ if min_dist > limit {
+ return None;
+ }
+ if n == 0 || m == 0 {
+ return (min_dist <= limit).then_some(min_dist);
}
- let mut dcol: Vec<_> = (0..=b.len()).collect();
- let mut t_last = 0;
+ let mut dcol: Vec<_> = (0..=m).collect();
for (i, sc) in a.chars().enumerate() {
let mut current = i;
dcol[j + 1] = cmp::min(dcol[j + 1], dcol[j]) + 1;
}
current = next;
- t_last = j;
}
}
- dcol[t_last + 1]
+
+ (dcol[m] <= limit).then_some(dcol[m])
}
/// Finds the best match for a given word in the given iterator.
/// on an edge case with a lower(upper)case letters mismatch.
#[cold]
pub fn find_best_match_for_name(
- name_vec: &[Symbol],
+ candidates: &[Symbol],
lookup: Symbol,
dist: Option<usize>,
) -> Option<Symbol> {
let lookup = lookup.as_str();
- let max_dist = dist.unwrap_or_else(|| cmp::max(lookup.len(), 3) / 3);
+ let lookup_uppercase = lookup.to_uppercase();
// Priority of matches:
// 1. Exact case insensitive match
// 2. Levenshtein distance match
// 3. Sorted word match
- if let Some(case_insensitive_match) =
- name_vec.iter().find(|candidate| candidate.as_str().to_uppercase() == lookup.to_uppercase())
- {
- return Some(*case_insensitive_match);
+ if let Some(c) = candidates.iter().find(|c| c.as_str().to_uppercase() == lookup_uppercase) {
+ return Some(*c);
}
- let levenshtein_match = name_vec
- .iter()
- .filter_map(|&name| {
- let dist = lev_distance(lookup, name.as_str());
- if dist <= max_dist { Some((name, dist)) } else { None }
- })
- // Here we are collecting the next structure:
- // (levenshtein_match, levenshtein_distance)
- .fold(None, |result, (candidate, dist)| match result {
- None => Some((candidate, dist)),
- Some((c, d)) => Some(if dist < d { (candidate, dist) } else { (c, d) }),
- });
- if levenshtein_match.is_some() {
- levenshtein_match.map(|(candidate, _)| candidate)
- } else {
- find_match_by_sorted_words(name_vec, lookup)
+
+ let mut dist = dist.unwrap_or_else(|| cmp::max(lookup.len(), 3) / 3);
+ let mut best = None;
+ for c in candidates {
+ match lev_distance(lookup, c.as_str(), dist) {
+ Some(0) => return Some(*c),
+ Some(d) => {
+ dist = d - 1;
+ best = Some(*c);
+ }
+ None => {}
+ }
}
+ if best.is_some() {
+ return best;
+ }
+
+ find_match_by_sorted_words(candidates, lookup)
}
fn find_match_by_sorted_words(iter_names: &[Symbol], lookup: &str) -> Option<Symbol> {