cargo-focus 0.1.0

A Cargo subcommand for managing `workspace.default-members`
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

use std::cmp::min;

pub fn levenshtein(a: &str, b: &str) -> usize {
    let a_chars: Vec<char> = a.chars().collect();
    let b_chars: Vec<char> = b.chars().collect();
    let mut prev: Vec<usize> = (0..=b_chars.len()).collect();
    let mut curr = vec![0; b_chars.len() + 1];

    for (i, ca) in a_chars.iter().enumerate() {
        curr[0] = i + 1;
        for (j, cb) in b_chars.iter().enumerate() {
            let cost = if ca == cb { 0 } else { 1 };
            curr[j + 1] = min(min(curr[j] + 1, prev[j + 1] + 1), prev[j] + cost);
        }
        std::mem::swap(&mut prev, &mut curr);
    }

    prev[b_chars.len()]
}

#[cfg(test)]
mod tests {
    use super::levenshtein;

    #[test]
    fn identity_and_empty_cases() {
        assert_eq!(levenshtein("", ""), 0);
        assert_eq!(levenshtein("focus", "focus"), 0);
        assert_eq!(levenshtein("", "focus"), 5);
        assert_eq!(levenshtein("focus", ""), 5);
    }

    #[test]
    fn single_edit_cases() {
        assert_eq!(levenshtein("focs", "focus"), 1); // insertion
        assert_eq!(levenshtein("focus", "focs"), 1); // deletion
        assert_eq!(levenshtein("focus", "focuz"), 1); // substitution
    }

    #[test]
    fn known_examples() {
        assert_eq!(levenshtein("kitten", "sitting"), 3);
        assert_eq!(levenshtein("cargo", "focus"), 5);
    }

    #[test]
    fn symmetric() {
        let a = "preset";
        let b = "present";
        assert_eq!(levenshtein(a, b), levenshtein(b, a));
    }
}