2 * Private macros and functions for use by the edit_distance implementation.
4 * @copyright 2016 Kevin Locke <kevin@kevinlocke.name>
5 * MIT license - see LICENSE file for details
7 #ifndef CCAN_EDIT_DISTANCE_PRIVATE_H
8 #define CCAN_EDIT_DISTANCE_PRIVATE_H
10 #include "edit_distance.h"
12 /** Unsafe (arguments evaluated multiple times) 3-value minimum. */
13 #define ED_MIN2(a, b) ((a) < (b) ? (a) : (b))
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)))
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)
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)
27 /** Index of element in lower triangular matrix. */
28 #define ED_TMAT_IND(r, c) (ED_TMAT_SIZE(r) + c)
31 * Calculates non-trivial LCS distance (for internal use).
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].
39 ed_dist edit_distance_lcs(const ed_elem *src, ed_size slen,
40 const ed_elem *tgt, ed_size tlen);
43 * Calculates non-trivial Levenshtein distance (for internal use).
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].
51 ed_dist edit_distance_lev(const ed_elem *src, ed_size slen,
52 const ed_elem *tgt, ed_size tlen);
55 * Calculates non-trivial Restricted Damerau-Levenshtein distance (for internal
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
65 ed_dist edit_distance_rdl(const ed_elem *src, ed_size slen,
66 const ed_elem *tgt, ed_size tlen);
69 * Calculates non-trivial Damerau-Levenshtein distance (for internal use).
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
78 ed_dist edit_distance_dl(const ed_elem *src, ed_size slen,
79 const ed_elem *tgt, ed_size tlen);