1
2
3
4
5 package lcs
6
7 import (
8 "log"
9 "math/rand"
10 "strings"
11 "testing"
12 )
13
14 type Btest struct {
15 a, b string
16 lcs []string
17 }
18
19 var Btests = []Btest{
20 {"aaabab", "abaab", []string{"abab", "aaab"}},
21 {"aabbba", "baaba", []string{"aaba"}},
22 {"cabbx", "cbabx", []string{"cabx", "cbbx"}},
23 {"c", "cb", []string{"c"}},
24 {"aaba", "bbb", []string{"b"}},
25 {"bbaabb", "b", []string{"b"}},
26 {"baaabb", "bbaba", []string{"bbb", "baa", "bab"}},
27 {"baaabb", "abbab", []string{"abb", "bab", "aab"}},
28 {"baaba", "aaabba", []string{"aaba"}},
29 {"ca", "cba", []string{"ca"}},
30 {"ccbcbc", "abba", []string{"bb"}},
31 {"ccbcbc", "aabba", []string{"bb"}},
32 {"ccb", "cba", []string{"cb"}},
33 {"caef", "axe", []string{"ae"}},
34 {"bbaabb", "baabb", []string{"baabb"}},
35
36 {"abcabba", "cbabac", []string{"caba", "baba", "cbba"}},
37 {"3456aaa", "aaa", []string{"aaa"}},
38 {"aaa", "aaa123", []string{"aaa"}},
39 {"aabaa", "aacaa", []string{"aaaa"}},
40 {"1a", "a", []string{"a"}},
41 {"abab", "bb", []string{"bb"}},
42 {"123", "ab", []string{""}},
43 {"a", "b", []string{""}},
44 {"abc", "123", []string{""}},
45 {"aa", "aa", []string{"aa"}},
46 {"abcde", "12345", []string{""}},
47 {"aaa3456", "aaa", []string{"aaa"}},
48 {"abcde", "12345a", []string{"a"}},
49 {"ab", "123", []string{""}},
50 {"1a2", "a", []string{"a"}},
51
52 {"babaab", "cccaba", []string{"aba"}},
53 {"aabbab", "cbcabc", []string{"bab"}},
54 {"abaabb", "bcacab", []string{"baab"}},
55 {"abaabb", "abaaaa", []string{"abaa"}},
56 {"bababb", "baaabb", []string{"baabb"}},
57 {"abbbaa", "cabacc", []string{"aba"}},
58 {"aabbaa", "aacaba", []string{"aaaa", "aaba"}},
59 }
60
61 func init() {
62 log.SetFlags(log.Lshortfile)
63 }
64
65 func check(t *testing.T, str string, lcs lcs, want []string) {
66 t.Helper()
67 if !lcs.valid() {
68 t.Errorf("bad lcs %v", lcs)
69 }
70 var got strings.Builder
71 for _, dd := range lcs {
72 got.WriteString(str[dd.X : dd.X+dd.Len])
73 }
74 ans := got.String()
75 for _, w := range want {
76 if ans == w {
77 return
78 }
79 }
80 t.Fatalf("str=%q lcs=%v want=%q got=%q", str, lcs, want, ans)
81 }
82
83 func checkDiffs(t *testing.T, before string, diffs []Diff, after string) {
84 t.Helper()
85 var ans strings.Builder
86 sofar := 0
87 for _, d := range diffs {
88 if sofar < d.Start {
89 ans.WriteString(before[sofar:d.Start])
90 }
91 ans.WriteString(after[d.ReplStart:d.ReplEnd])
92 sofar = d.End
93 }
94 ans.WriteString(before[sofar:])
95 if ans.String() != after {
96 t.Fatalf("diff %v took %q to %q, not to %q", diffs, before, ans.String(), after)
97 }
98 }
99
100 func lcslen(l lcs) int {
101 ans := 0
102 for _, d := range l {
103 ans += int(d.Len)
104 }
105 return ans
106 }
107
108
109 func randstr(s string, n int) string {
110 src := []rune(s)
111 x := make([]rune, n)
112 for i := 0; i < n; i++ {
113 x[i] = src[rand.Intn(len(src))]
114 }
115 return string(x)
116 }
117
118 func TestLcsFix(t *testing.T) {
119 tests := []struct{ before, after lcs }{
120 {lcs{diag{0, 0, 3}, diag{2, 2, 5}, diag{3, 4, 5}, diag{8, 9, 4}}, lcs{diag{0, 0, 2}, diag{2, 2, 1}, diag{3, 4, 5}, diag{8, 9, 4}}},
121 {lcs{diag{1, 1, 6}, diag{6, 12, 3}}, lcs{diag{1, 1, 5}, diag{6, 12, 3}}},
122 {lcs{diag{0, 0, 4}, diag{3, 5, 4}}, lcs{diag{0, 0, 3}, diag{3, 5, 4}}},
123 {lcs{diag{0, 20, 1}, diag{0, 0, 3}, diag{1, 20, 4}}, lcs{diag{0, 0, 3}, diag{3, 22, 2}}},
124 {lcs{diag{0, 0, 4}, diag{1, 1, 2}}, lcs{diag{0, 0, 4}}},
125 {lcs{diag{0, 0, 4}}, lcs{diag{0, 0, 4}}},
126 {lcs{}, lcs{}},
127 {lcs{diag{0, 0, 4}, diag{1, 1, 6}, diag{3, 3, 2}}, lcs{diag{0, 0, 1}, diag{1, 1, 6}}},
128 }
129 for n, x := range tests {
130 got := x.before.fix()
131 if len(got) != len(x.after) {
132 t.Errorf("got %v, expected %v, for %v", got, x.after, x.before)
133 }
134 olen := lcslen(x.after)
135 glen := lcslen(got)
136 if olen != glen {
137 t.Errorf("%d: lens(%d,%d) differ, %v, %v, %v", n, glen, olen, got, x.after, x.before)
138 }
139 }
140 }
141
View as plain text