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