1 package misspell
2
3 import (
4 "math"
5 "testing"
6 )
7
8 func TestAlmostEqual(t *testing.T) {
9 t.Parallel()
10
11 tcs := []struct {
12 inA string
13 inB string
14 want bool
15 }{
16 {"", "", true},
17 {"", "a", true},
18 {"a", "a", true},
19 {"a", "b", true},
20 {"hello", "hell", true},
21 {"hello", "jello", true},
22 {"hello", "helol", true},
23 {"hello", "jelol", false},
24 }
25 for _, tc := range tcs {
26 got := AlmostEqual(tc.inA, tc.inB)
27 if got != tc.want {
28 t.Errorf("AlmostEqual(%q, %q) = %v, want %v", tc.inA, tc.inB, got, tc.want)
29 }
30
31 if got != AlmostEqual(tc.inB, tc.inA) {
32 t.Errorf("AlmostEqual(%q, %q) == %v != AlmostEqual(%q, %q)", tc.inA, tc.inB, got, tc.inB, tc.inA)
33 }
34 }
35 }
36
37 func FuzzAlmostEqual(f *testing.F) {
38 f.Add("", "")
39 f.Add("", "a")
40 f.Add("a", "a")
41 f.Add("a", "b")
42 f.Add("hello", "hell")
43 f.Add("hello", "jello")
44 f.Add("hello", "helol")
45 f.Add("hello", "jelol")
46 f.Fuzz(func(t *testing.T, a, b string) {
47 if len(a) > 10 || len(b) > 10 {
48
49 return
50 }
51 d := editDistance([]rune(a), []rune(b))
52 got := AlmostEqual(a, b)
53 if want := d <= 1; got != want {
54 t.Errorf("AlmostEqual(%q, %q) = %v, editDistance(%q, %q) = %d", a, b, got, a, b, d)
55 }
56 if got != AlmostEqual(b, a) {
57 t.Errorf("AlmostEqual(%q, %q) == %v != AlmostEqual(%q, %q)", a, b, got, b, a)
58 }
59 })
60 }
61
62
63
64
65
66 func editDistance(a, b []rune) int {
67 i, j := len(a), len(b)
68 m := math.MaxInt
69 if i == 0 && j == 0 {
70 return 0
71 }
72 if i > 0 {
73 m = min(m, editDistance(a[1:], b)+1)
74 }
75 if j > 0 {
76 m = min(m, editDistance(a, b[1:])+1)
77 }
78 if i > 0 && j > 0 {
79 d := editDistance(a[1:], b[1:])
80 if a[0] != b[0] {
81 d += 1
82 }
83 m = min(m, d)
84 }
85 if i > 1 && j > 1 && a[0] == b[1] && a[1] == b[0] {
86 d := editDistance(a[2:], b[2:])
87 if a[0] != b[0] {
88 d += 1
89 }
90 m = min(m, d)
91 }
92 return m
93 }
94
95 func min(a, b int) int {
96 if a < b {
97 return a
98 }
99 return b
100 }
101
View as plain text