alpm_lint/
utils.rs

1/// Trait for calculating edit distance between two types.
2pub(crate) trait EditDistance {
3    /// Calculate edit distance between `self` and `other`.
4    fn edit_distance(&self, other: &Self) -> usize;
5}
6
7impl EditDistance for &[u8] {
8    /// Calculate edit distance between `self` and `other` using the Levenshtein distance algorithm.
9    fn edit_distance(&self, other: &Self) -> usize {
10        let mut dp = vec![vec![0; other.len() + 1]; self.len() + 1];
11
12        for i in 0..=self.len() {
13            for j in 0..=other.len() {
14                if i == 0 {
15                    dp[i][j] = j;
16                } else if j == 0 {
17                    dp[i][j] = i;
18                } else if self[i - 1] == other[j - 1] {
19                    dp[i][j] = dp[i - 1][j - 1];
20                } else {
21                    dp[i][j] = 1 + dp[i - 1][j - 1].min(dp[i - 1][j]).min(dp[i][j - 1]);
22                }
23            }
24        }
25
26        dp[self.len()][other.len()]
27    }
28}
29
30impl EditDistance for String {
31    /// Calculate edit distance between `self` and `other`.
32    ///
33    /// Delegates to the byte slice implementation.
34    fn edit_distance(&self, other: &Self) -> usize {
35        self.as_bytes().edit_distance(&other.as_bytes())
36    }
37}
38
39impl EditDistance for &str {
40    /// Calculate edit distance between `self` and `other`.
41    ///
42    /// Delegates to the byte slice implementation.
43    fn edit_distance(&self, other: &Self) -> usize {
44        self.as_bytes().edit_distance(&other.as_bytes())
45    }
46}
47
48#[cfg(test)]
49mod tests {
50    use rstest::rstest;
51
52    use super::*;
53
54    #[rstest]
55    #[case("kitten", "sitting", 3)]
56    #[case("flaw", "lawn", 2)]
57    #[case("intention", "execution", 5)]
58    #[case("", "", 0)]
59    #[case("a", "", 1)]
60    #[case("", "a", 1)]
61    fn test_edit_distance(#[case] s1: &str, #[case] s2: &str, #[case] expected: usize) {
62        let distance = s1.edit_distance(&s2);
63        assert_eq!(distance, expected);
64    }
65}
alpm_lint/utils.rs

alpm_lint/
utils.rs
