scalp 0.4.3

A declarative parsing library for pretty and highly customizable command-line interfaces.
Documentation 
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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101

use core::{mem::swap, ops::Deref};

pub struct Spell(Vec<usize>, Vec<usize>);

impl Spell {
    pub const fn new() -> Self {
        Self(Vec::new(), Vec::new())
    }

    pub fn suggest<T: Deref<Target = str>>(
        &mut self,
        word: &str,
        dictionary: impl IntoIterator<Item = T>,
        maximum: usize,
    ) -> Vec<(T, usize)> {
        let dictionary = dictionary.into_iter();
        let mut results = Vec::with_capacity(dictionary.size_hint().0);
        for candidate in dictionary {
            let distance = self.distance(word.as_bytes(), candidate.as_bytes());
            if distance <= maximum {
                results.push((candidate, distance));
            }
        }
        results.sort_by_key(|&(_, distance)| distance);
        results
    }

    fn distance(&mut self, left: &[u8], right: &[u8]) -> usize {
        let left_count = left.len();
        let right_count = right.len();
        if left_count > right_count {
            return self.distance(right, left);
        }

        let Self(previous, current) = self;
        previous.clear();
        previous.resize(left_count + 1, 0);
        current.resize(left_count + 1, 0);

        for i in 1..=right_count {
            current[0] = i;
            for j in 1..=left_count {
                let left = char::from(left[j - 1]).to_ascii_lowercase();
                let right = char::from(right[i - 1]).to_ascii_lowercase();
                let insert = current[j - 1] + 1;
                let delete = previous[j] + 1;
                let replace = previous[j - 1] + if left == right { 0 } else { 1 };
                current[j] = insert.min(delete).min(replace);
            }
            swap(previous, current);
        }

        previous[left_count]
    }
}

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

    #[test]
    fn distance() {
        let mut spell = Spell::new();
        assert_eq!(spell.distance(b"boba", b"boba"), 0);
        assert_eq!(spell.distance(b"boba", b"bobo"), 1);
        assert_eq!(spell.distance(b"boba", b"bobba"), 1);
        assert_eq!(spell.distance(b"boba", b"boa"), 1);
        assert_eq!(spell.distance(b"boba", b"fett"), 4);
    }

    #[test]
    fn suggest() {
        let results = Spell::new().suggest(
            "poulaye",
            [
                "poullayye",
                "poupou",
                "pilaye",
                "poulah",
                "piulaye",
                "paliyoo",
                "vladimarre",
                "poulaye",
                "p",
                "poulay",
            ],
            2,
        );
        assert_eq!(
            results,
            vec![
                ("poulaye", 0),
                ("piulaye", 1),
                ("poulay", 1),
                ("poullayye", 2),
                ("pilaye", 2),
                ("poulah", 2)
            ]
        );
    }
}