2 * Defines shared edit distance functions.
4 * @copyright 2016 Kevin Locke <kevin@kevinlocke.name>
5 * MIT license - see LICENSE file for details
7 #include "edit_distance-params.h"
8 #include "edit_distance-private.h"
10 ed_dist edit_distance(const ed_elem *src, ed_size slen,
11 const ed_elem *tgt, ed_size tlen, enum ed_measure measure)
13 /* Remove common prefix. */
14 while (slen > 0 && tlen > 0 && ED_ELEM_EQUAL(src[0], tgt[0])) {
21 /* Remove common suffix. */
22 while (slen > 0 && tlen > 0 &&
23 ED_ELEM_EQUAL(src[slen - 1], tgt[tlen - 1])) {
28 #if defined(ED_COST_IS_SYMMETRIC)
29 /* Use smaller array for src. */
31 ED_SWAP(src, tgt, const ed_elem *);
32 ED_SWAP(slen, tlen, ed_size);
36 /* Early return when all insertions. */
38 #ifdef ED_INS_COST_CONST
39 return (ed_dist)tlen *ED_INS_COST();
42 for (ed_size i = 0; i < tlen; ++i) {
43 result += ED_INS_COST(tgt[i]);
48 #ifndef ED_COST_IS_SYMMETRIC
49 /* Early return when all deletions. */
51 # ifdef ED_DEL_COST_CONST
52 return (ed_dist)slen *ED_DEL_COST();
55 for (ed_size i = 0; i < slen; ++i) {
56 result += ED_DEL_COST(src[i]);
63 #if defined(ED_HAS_ELEM) && \
64 defined(ED_INS_COST_CONST) && \
65 defined(ED_SUB_COST_CONST)
66 /* Fast search for single-element source. */
68 /* Always tlen - 1 inserts (of non-src elements). */
69 ed_dist result = (ed_dist)(tlen - 1) * ED_INS_COST();
70 if (!ED_HAS_ELEM(tgt, src[0], tlen)) {
71 if (measure == EDIT_DISTANCE_LCS) {
72 /* If src is not present, delete + insert. */
73 result += ED_DEL_COST(src[0]) + ED_INS_COST();
75 /* If src is not present, substitute it out. */
76 result += ED_SUB_COST(,);
83 #if !defined(ED_COST_IS_SYMMETRIC) && \
84 defined(ED_HAS_ELEM) && \
85 defined(ED_DEL_COST_CONST) && \
86 defined(ED_SUB_COST_CONST)
87 /* Fast search for single-element target. */
89 /* Always slen - 1 deletes (of non-tgt elements). */
90 ed_dist result = (ed_dist)(slen - 1) * ED_DEL_COST();
91 if (!ED_HAS_ELEM(src, tgt[0], slen)) {
92 if (measure == EDIT_DISTANCE_LCS) {
93 /* If tgt is not present, delete + insert. */
94 result += ED_INS_COST(tgt[0]) + ED_DEL_COST();
96 /* If tgt is not present, substitute it out. */
97 result += ED_SUB_COST(,);
105 case EDIT_DISTANCE_LCS:
106 return edit_distance_lcs(src, slen, tgt, tlen);
107 case EDIT_DISTANCE_LEV:
108 return edit_distance_lev(src, slen, tgt, tlen);
109 case EDIT_DISTANCE_RDL:
110 return edit_distance_rdl(src, slen, tgt, tlen);
111 case EDIT_DISTANCE_DL:
112 return edit_distance_dl(src, slen, tgt, tlen);