rustic_fuzz/
lib.rs

1pub fn fuzzy_sort<T: AsRef<str> + Clone>(to_sort: &[T], input: &str) -> Vec<T> {
2    let mut clone: Vec<T> = to_sort.to_vec();
3    let input_chars: Vec<char> = input.chars().collect();
4    clone.sort_by_key(|s| levenshtein_distance(s.as_ref(), &input_chars));
5
6    clone
7}
8
9pub fn fuzzy_sort_in_place<T: AsRef<str>>(to_sort: &mut [T], input: &str) {
10    let input_chars: Vec<char> = input.chars().collect();
11    to_sort.sort_by_key(|s| levenshtein_distance(s.as_ref(), &input_chars));
12}
13
14fn levenshtein_distance(u: &str, v_chars: &[char]) -> u32 {
15    let u_chars: Vec<char> = u.chars().collect();
16
17    let m = u_chars.len();
18    let n = v_chars.len();
19
20    let mut prev_row: Vec<u32> = (0..=n as u32).collect();
21    let mut current_row: Vec<u32> = vec![0; n + 1];
22
23    for i in 1..=m {
24        current_row[0] = i as u32;
25        for j in 1..=n {
26            let u_char = u_chars[i - 1];
27            let v_char = v_chars[j - 1];
28
29            let replacement_score = prev_row[j - 1] + (
30                if u_char == v_char { 0 } else { 1 }
31            );
32
33            let insert_score = current_row[j - 1] + 1;
34            let delete_score = prev_row[j] + 1;
35
36            current_row[j] = replacement_score
37                .min(insert_score)
38                .min(delete_score)
39        }
40
41        std::mem::swap(&mut prev_row, &mut current_row);
42    }
43
44    return prev_row[n];
45}
46
47#[test]
48fn fuzzy_sort_test() {
49    let test_cases = vec![
50        (
51            vec!["xxx".to_string(), "yyy".to_string(), "xx".to_string()],
52            "xxx",
53            vec!["xxx".to_string(), "xx".to_string(), "yyy".to_string()]
54        ),
55        (
56            vec!["apple".to_string(), "banana".to_string(), "cherry".to_string()],
57            "banana",
58            vec!["banana".to_string(), "apple".to_string(), "cherry".to_string()]
59        ),
60        (
61            vec!["rust".to_string(), "is".to_string(), "awesome".to_string()],
62            "awesome",
63            vec!["awesome".to_string(), "rust".to_string(), "is".to_string()]
64        ),
65    ];
66
67    test_cases.iter().for_each(|(arr, input, expected_sorted)| {
68        let sorted = fuzzy_sort(&arr, input);
69        assert_eq!(sorted, *expected_sorted);
70
71        let mut mutarr = arr.clone();
72        fuzzy_sort_in_place(mutarr.as_mut(), input);
73        assert_eq!(mutarr, *expected_sorted);
74    });
75}
76
77#[test]
78fn levenshtein_distance_test() {
79    vec![
80        ("hello, world", "hello- world", 1),
81        ("murice", "maurice", 1),
82        ("delete", "insert", 5),
83        ("Tier", "Tor", 2),
84        ("banana", "cherry", 6)
85    ].iter()
86    .for_each(|(u, v, expected_distance)| {
87        let distance = levenshtein_distance(u, &v.chars().collect::<Vec<_>>());
88        assert_eq!(distance, *expected_distance as u32);
89    });
90}
rustic_fuzz/lib.rs

rustic_fuzz/
lib.rs
