///|
/// The Levenshtein distance between `s1` and `s2` (ninja's `EditDistance`).
/// Without replacements a substitution costs two edits. When
/// `max_edit_distance` is positive, the search stops early and returns
/// `max_edit_distance + 1` once every alignment is farther than that.
pub fn edit_distance(
s1 : String,
s2 : String,
allow_replacements~ : Bool = true,
max_edit_distance~ : Int32 = 0,
) -> Int32 {
// The classic dynamic program, keeping one row: row[x - 1] is the left
// entry, row[x] the top one and `previous` the top-left one.
let m = s1.length()
let n = s2.length()
let row = Array::makei(n + 1, fn(i) { i })
for y in 1..<=m {
row[0] = y
let mut best_this_row = row[0]
let mut previous = y - 1
for x in 1..<=n {
let old_row = row[x]
let same = s1.unsafe_get(y - 1) == s2.unsafe_get(x - 1)
row[x] = if allow_replacements {
@cmp.minimum(
previous + (if same { 0 } else { 1 }),
@cmp.minimum(row[x - 1], row[x]) + 1,
)
} else if same {
previous
} else {
@cmp.minimum(row[x - 1], row[x]) + 1
}
previous = old_row
best_this_row = @cmp.minimum(best_this_row, row[x])
}
if max_edit_distance != 0 && best_this_row > max_edit_distance {
return max_edit_distance + 1
}
}
row[n]
}
///|
/// The known path closest to `path`, within 3 edits, for "did you mean"
/// hints (ninja's `State::SpellcheckNode`). Ties go to the earliest node.
pub fn State::spellcheck_node(self : State, path : String) -> Node? {
let max_distance = 3
let mut min_distance = max_distance + 1
let mut result = None
for candidate, node in self.paths {
let distance = edit_distance(
candidate,
path,
max_edit_distance=max_distance,
)
if distance < min_distance {
min_distance = distance
result = Some(node)
}
}
result
}