2 * Runnable public API tests of the edit_distance module.
4 * @copyright 2016 Kevin Locke <kevin@kevinlocke.name>
5 * MIT license - see LICENSE file for details
10 #include <ccan/build_assert/build_assert.h>
11 #include <ccan/edit_distance/edit_distance.h>
12 #include <ccan/tap/tap.h>
14 #define edit_distance_lcs_static(arr1, arr2) \
15 edit_distance(arr1, sizeof arr1 - 1, arr2, sizeof arr2 - 1, \
17 #define edit_distance_lev_static(arr1, arr2) \
18 edit_distance(arr1, sizeof arr1 - 1, arr2, sizeof arr2 - 1, \
20 #define edit_distance_rdl_static(arr1, arr2) \
21 edit_distance(arr1, sizeof arr1 - 1, arr2, sizeof arr2 - 1, \
23 #define edit_distance_dl_static(arr1, arr2) \
24 edit_distance(arr1, sizeof arr1 - 1, arr2, sizeof arr2 - 1, \
27 static void test_lcs(void)
30 ok1(edit_distance_lcs_static("", "") == 0);
31 ok1(edit_distance_lcs_static("a", "") == 1);
32 ok1(edit_distance_lcs_static("", "a") == 1);
33 ok1(edit_distance_lcs_static("a", "a") == 0);
34 ok1(edit_distance_lcs_static("a", "b") == 2);
35 ok1(edit_distance_lcs_static("b", "a") == 2);
37 /* Trivial search cases */
38 ok1(edit_distance_lcs_static("a", "bcdef") == 6);
39 ok1(edit_distance_lcs_static("a", "bcadef") == 5);
40 ok1(edit_distance_lcs_static("acdef", "b") == 6);
41 ok1(edit_distance_lcs_static("abcdef", "b") == 5);
43 /* Common prefix with single-char distance */
44 ok1(edit_distance_lcs_static("aa", "ab") == 2);
45 ok1(edit_distance_lcs_static("ab", "aa") == 2);
47 /* Common suffix with single-char distance */
48 ok1(edit_distance_lcs_static("aa", "ba") == 2);
49 ok1(edit_distance_lcs_static("ba", "aa") == 2);
51 /* Non-optimized cases (require Wagner-Fischer matrix) */
52 ok1(edit_distance_lcs_static("ab", "ba") == 2);
53 ok1(edit_distance_lcs_static("abc", "de") == 5);
54 ok1(edit_distance_lcs_static("abc", "def") == 6);
56 /* (Restricted) Transposition */
57 ok1(edit_distance_lcs_static("abcd", "ecbf") == 6);
59 /* (Unrestricted) Transposition */
60 ok1(edit_distance_lcs_static("ca", "abc") == 3);
62 /* Insert + Delete + Sub */
63 ok1(edit_distance_lcs_static("abcde", "xcdef") == 4);
65 /* Distance depends on multiple deletions in final row. */
66 ok1(edit_distance_lcs_static("aabcc", "bccdd") == 4);
68 /* Distance depends on multiple insertions in final column. */
69 ok1(edit_distance_lcs_static("bccdd", "aabcc") == 4);
72 static void test_lev(void)
75 ok1(edit_distance_lev_static("", "") == 0);
76 ok1(edit_distance_lev_static("a", "") == 1);
77 ok1(edit_distance_lev_static("", "a") == 1);
78 ok1(edit_distance_lev_static("a", "a") == 0);
79 ok1(edit_distance_lev_static("a", "b") == 1);
80 ok1(edit_distance_lev_static("b", "a") == 1);
82 /* Trivial search cases */
83 ok1(edit_distance_lev_static("a", "bcdef") == 5);
84 ok1(edit_distance_lev_static("a", "bcadef") == 5);
85 ok1(edit_distance_lev_static("acdef", "b") == 5);
86 ok1(edit_distance_lev_static("abcdef", "b") == 5);
88 /* Common prefix with single-char distance */
89 ok1(edit_distance_lev_static("aa", "ab") == 1);
90 ok1(edit_distance_lev_static("ab", "aa") == 1);
92 /* Common suffix with single-char distance */
93 ok1(edit_distance_lev_static("aa", "ba") == 1);
94 ok1(edit_distance_lev_static("ba", "aa") == 1);
96 /* Non-optimized cases (require Wagner-Fischer matrix) */
97 ok1(edit_distance_lev_static("ab", "ba") == 2);
98 ok1(edit_distance_lev_static("abc", "de") == 3);
99 ok1(edit_distance_lev_static("abc", "def") == 3);
101 /* (Restricted) Transposition */
102 ok1(edit_distance_lev_static("abcd", "ecbf") == 4);
104 /* (Unrestricted) Transposition */
105 ok1(edit_distance_lev_static("ca", "abc") == 3);
107 /* Insert + Delete + Sub */
108 ok1(edit_distance_lev_static("abcde", "xcdef") == 3);
110 /* Distance depends on multiple deletions in final row. */
111 ok1(edit_distance_lev_static("aabcc", "bccdd") == 4);
113 /* Distance depends on multiple insertions in final column. */
114 ok1(edit_distance_lev_static("bccdd", "aabcc") == 4);
117 static void test_rdl(void)
120 ok1(edit_distance_rdl_static("", "") == 0);
121 ok1(edit_distance_rdl_static("a", "") == 1);
122 ok1(edit_distance_rdl_static("", "a") == 1);
123 ok1(edit_distance_rdl_static("a", "a") == 0);
124 ok1(edit_distance_rdl_static("a", "b") == 1);
125 ok1(edit_distance_rdl_static("b", "a") == 1);
127 /* Trivial search cases */
128 ok1(edit_distance_rdl_static("a", "bcdef") == 5);
129 ok1(edit_distance_rdl_static("a", "bcadef") == 5);
130 ok1(edit_distance_rdl_static("acdef", "b") == 5);
131 ok1(edit_distance_rdl_static("abcdef", "b") == 5);
133 /* Common prefix with single-char distance */
134 ok1(edit_distance_rdl_static("aa", "ab") == 1);
135 ok1(edit_distance_rdl_static("ab", "aa") == 1);
137 /* Common suffix with single-char distance */
138 ok1(edit_distance_rdl_static("aa", "ba") == 1);
139 ok1(edit_distance_rdl_static("ba", "aa") == 1);
141 /* Non-optimized cases (require Wagner-Fischer matrix) */
142 ok1(edit_distance_rdl_static("ab", "ba") == 1);
143 ok1(edit_distance_rdl_static("abc", "de") == 3);
144 ok1(edit_distance_rdl_static("abc", "def") == 3);
146 /* (Restricted) Transposition */
147 ok1(edit_distance_rdl_static("abcd", "ecbf") == 3);
149 /* (Unrestricted) Transposition */
150 ok1(edit_distance_rdl_static("ca", "abc") == 3);
152 /* Insert + Delete + Sub */
153 ok1(edit_distance_rdl_static("abcde", "xcdef") == 3);
155 /* Distance depends on multiple deletions in final row. */
156 ok1(edit_distance_rdl_static("aabcc", "bccdd") == 4);
158 /* Distance depends on multiple insertions in final column. */
159 ok1(edit_distance_rdl_static("bccdd", "aabcc") == 4);
162 static void test_dl(void)
165 ok1(edit_distance_dl_static("", "") == 0);
166 ok1(edit_distance_dl_static("a", "") == 1);
167 ok1(edit_distance_dl_static("", "a") == 1);
168 ok1(edit_distance_dl_static("a", "a") == 0);
169 ok1(edit_distance_dl_static("a", "b") == 1);
170 ok1(edit_distance_dl_static("b", "a") == 1);
172 /* Trivial search cases */
173 ok1(edit_distance_dl_static("a", "bcdef") == 5);
174 ok1(edit_distance_dl_static("a", "bcadef") == 5);
175 ok1(edit_distance_dl_static("acdef", "b") == 5);
176 ok1(edit_distance_dl_static("abcdef", "b") == 5);
178 /* Common prefix with single-char distance */
179 ok1(edit_distance_dl_static("aa", "ab") == 1);
180 ok1(edit_distance_dl_static("ab", "aa") == 1);
182 /* Common suffix with single-char distance */
183 ok1(edit_distance_dl_static("aa", "ba") == 1);
184 ok1(edit_distance_dl_static("ba", "aa") == 1);
186 /* Non-optimized cases (require Wagner-Fischer matrix) */
187 ok1(edit_distance_dl_static("ab", "ba") == 1);
188 ok1(edit_distance_dl_static("abc", "de") == 3);
189 ok1(edit_distance_dl_static("abc", "def") == 3);
191 /* (Restricted) Transposition */
192 ok1(edit_distance_dl_static("abcd", "ecbf") == 3);
194 /* (Unrestricted) Transposition */
195 ok1(edit_distance_dl_static("ca", "abc") == 2);
197 /* Insert + Delete + Sub */
198 ok1(edit_distance_dl_static("abcde", "xcdef") == 3);
200 /* Distance depends on multiple deletions in final row. */
201 ok1(edit_distance_dl_static("aabcc", "bccdd") == 4);
203 /* Distance depends on multiple insertions in final column. */
204 ok1(edit_distance_dl_static("bccdd", "aabcc") == 4);
216 /* Unsupported edit distance measure */
217 enum ed_measure badmeasure = (enum ed_measure)-1;
218 ok1(edit_distance("ab", 2, "ba", 2, badmeasure) == (ed_dist)-1);
220 return exit_status();