edit_distance: calculate edit distance between strings
[ccan] / ccan / edit_distance / edit_distance-private.h
1 /** @file
2  * Private macros and functions for use by the edit_distance implementation.
3  *
4  * @copyright 2016 Kevin Locke <kevin@kevinlocke.name>
5  *            MIT license - see LICENSE file for details
6  */
7 #ifndef CCAN_EDIT_DISTANCE_PRIVATE_H
8 #define CCAN_EDIT_DISTANCE_PRIVATE_H
9
10 #include "edit_distance.h"
11
12 /** Unsafe (arguments evaluated multiple times) 3-value minimum. */
13 #define ED_MIN2(a, b) ((a) < (b) ? (a) : (b))
14
15 /** Unsafe (arguments evaluated multiple times) 3-value minimum. */
16 #define ED_MIN3(a, b, c) \
17         ((a) < (b) ? ((a) < (c) ? (a) : (c)) : ((b) < (c) ? (b) : (c)))
18
19 /** Swap variables @p a and @p b of a given type. */
20 #define ED_SWAP(a, b, Type) \
21         do { Type swaptmp = a; a = b; b = swaptmp; } while (0)
22
23 /** Number of elements in triangular matrix (with diagonal).
24  * @param rc Number of rows (or columns, since square). */
25 #define ED_TMAT_SIZE(rc) (((rc) + 1) * (rc) / 2)
26
27 /** Index of element in lower triangular matrix. */
28 #define ED_TMAT_IND(r, c) (ED_TMAT_SIZE(r) + c)
29
30 /**
31  * Calculates non-trivial LCS distance (for internal use).
32  * @private
33  * @param src Source array to calculate distance from (smaller when symmetric).
34  * @param slen Number of elements in @p src to consider (must be > 0).
35  * @param tgt Target array to calculate distance to.
36  * @param tlen Number of elements in @p tgt to consider (must be > 0).
37  * @return LCS distance from @p src[0..slen-1] to @p tgt[0..tlen-1].
38  */
39 ed_dist edit_distance_lcs(const ed_elem *src, ed_size slen,
40                           const ed_elem *tgt, ed_size tlen);
41
42 /**
43  * Calculates non-trivial Levenshtein distance (for internal use).
44  * @private
45  * @param src Source array to calculate distance from (smaller when symmetric).
46  * @param slen Number of elements in @p src to consider (must be > 0).
47  * @param tgt Target array to calculate distance to.
48  * @param tlen Number of elements in @p tgt to consider (must be > 0).
49  * @return Levenshtein distance from @p src[0..slen-1] to @p tgt[0..tlen-1].
50  */
51 ed_dist edit_distance_lev(const ed_elem *src, ed_size slen,
52                           const ed_elem *tgt, ed_size tlen);
53
54 /**
55  * Calculates non-trivial Restricted Damerau-Levenshtein distance (for internal
56  * use).
57  * @private
58  * @param src Source array to calculate distance from (smaller when symmetric).
59  * @param slen Number of elements in @p src to consider (must be > 0).
60  * @param tgt Target array to calculate distance to.
61  * @param tlen Number of elements in @p tgt to consider (must be > 0).
62  * @return Restricted Damerau-Levenshtein distance from @p src[0..slen-1] to
63  * @p tgt[0..tlen-1].
64  */
65 ed_dist edit_distance_rdl(const ed_elem *src, ed_size slen,
66                           const ed_elem *tgt, ed_size tlen);
67
68 /**
69  * Calculates non-trivial Damerau-Levenshtein distance (for internal use).
70  * @private
71  * @param src Source array to calculate distance from (smaller when symmetric).
72  * @param slen Number of elements in @p src to consider (must be > 0).
73  * @param tgt Target array to calculate distance to.
74  * @param tlen Number of elements in @p tgt to consider (must be > 0).
75  * @return Damerau-Levenshtein distance from @p src[0..slen-1] to
76  * @p tgt[0..tlen-1].
77  */
78 ed_dist edit_distance_dl(const ed_elem *src, ed_size slen,
79                          const ed_elem *tgt, ed_size tlen);
80
81 #endif