edit-distance 2.2.2

Levenshtein edit distance between strings, a measure for similarity.
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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118

extern crate edit_distance;

#[test]
fn simple() {
    assert_eq!(edit_distance::edit_distance("kitten", "sitting"), 3);
    assert_eq!(edit_distance::edit_distance("Tier", "Tor"), 2);
}

#[test]
fn same() {
    assert_eq!(edit_distance::edit_distance("kitten", "kitten"), 0);
}

#[test]
fn empty_a() {
    assert_eq!(edit_distance::edit_distance("", "kitten"), 6);
}

#[test]
fn empty_b() {
    assert_eq!(edit_distance::edit_distance("sitting", ""), 7);
}

#[test]
fn empty_both() {
    assert_eq!(edit_distance::edit_distance("", ""), 0);
}

#[test]
fn unicode_misc() {
    assert_eq!(edit_distance::edit_distance("üö", "uo"), 2);
}

#[test]
fn unicode_thai() {
    assert_eq!(edit_distance::edit_distance("ฎ ฏ ฐ", "a b c"), 3);
}

#[test]
fn unicode_misc_equal() {
    assert_eq!(
        edit_distance::edit_distance("☀☂☃☄", "☀☂☃☄"),
        0
    );
}

extern crate quickcheck;
use quickcheck::quickcheck;

#[test]
fn at_least_size_difference_property() {
    fn at_least_size_difference(a: String, b: String) -> bool {
        let size_a = a.chars().count();
        let size_b = b.chars().count();
        let diff = if size_a > size_b {
            size_a - size_b
        } else {
            size_b - size_a
        };
        edit_distance::edit_distance(&a, &b) >= diff
    }

    quickcheck(at_least_size_difference as fn(a: String, b: String) -> bool);
}

#[test]
fn at_most_length_of_longer_property() {
    fn at_most_size_of_longer(a: String, b: String) -> bool {
        let upper_bound = *[a.chars().count(), b.chars().count()].iter().max().unwrap();
        edit_distance::edit_distance(&a, &b) <= upper_bound
    }

    quickcheck(at_most_size_of_longer as fn(a: String, b: String) -> bool);
}

#[test]
fn zero_iff_a_equals_b_property() {
    fn zero_iff_a_equals_b(a: String, b: String) -> bool {
        let d = edit_distance::edit_distance(&a, &b);

        if a == b {
            d == 0
        } else {
            d > 0
        }
    }

    quickcheck(zero_iff_a_equals_b as fn(a: String, b: String) -> bool);
}

#[test]
fn triangle_inequality_property() {
    fn triangle_inequality(a: String, b: String, c: String) -> bool {
        edit_distance::edit_distance(&a, &b)
            <= edit_distance::edit_distance(&a, &c) + edit_distance::edit_distance(&b, &c)
    }

    quickcheck(triangle_inequality as fn(a: String, b: String, c: String) -> bool);
}

#[test]
fn accepts_different_string_types() {
    let owned = String::from("kitten");
    let borrowed = "sitting";
    let boxed = Box::<str>::from("kitten");

    assert_eq!(edit_distance::edit_distance(&owned, borrowed), 3);
    assert_eq!(edit_distance::edit_distance(owned.clone(), borrowed), 3);

    assert_eq!(edit_distance::edit_distance(&owned, borrowed), 3);

    assert_eq!(edit_distance::edit_distance(boxed, "sitting"), 3);

    assert_eq!(
        edit_distance::edit_distance(String::from("Tier"), String::from("Tor")),
        2
    );
}