f4846188656c257049730a02ec3eb2f15964f538
[ccan] / ccan / edit_distance / edit_distance-params.h
1 /** @file
2  * Defines the tunable parameters for the edit_distance functions which can
3  * be changed at module-compile-time.
4  *
5  * The macros in this header can be redefined, either by editing this file or
6  * providing external definitions.  This makes it possible to calculate the
7  * weighted edit distance with arbitrary weighting.
8  *
9  * @copyright 2016 Kevin Locke <kevin@kevinlocke.name>
10  *            MIT license - see LICENSE file for details
11  */
12 #ifndef CCAN_EDIT_DISTANCE_PARAMS_H
13 #define CCAN_EDIT_DISTANCE_PARAMS_H
14
15 #ifndef ed_elem
16 # include <string.h>            /* memchr */
17 #endif
18
19 #ifndef ED_HASH_ELEM
20 # include <limits.h>            /* UCHAR_MAX */
21 #endif
22
23 #if !defined(ED_DEL_COST) && \
24                 !defined(ED_INS_COST) && \
25                 !defined(ED_SUB_COST) && \
26                 !defined(ED_TRA_COST)
27 /** Defined if costs are symmetric.
28  * (i.e. <code>distance(a, b) == distance(b, a) forall a,b</code>) */
29 # define ED_COST_IS_SYMMETRIC
30 #endif
31
32 #ifndef ED_DEL_COST
33 /** Cost to delete element @p e. */
34 # define ED_DEL_COST(e) 1
35 /** Defined if the cost to delete is the same for all elements. */
36 # define ED_DEL_COST_CONST
37 #endif
38
39 #ifndef ED_INS_COST
40 /** Cost to insert element @p e. */
41 # define ED_INS_COST(e) 1
42 /** Defined if the cost to insert is the same for all elements. */
43 # define ED_INS_COST_CONST
44 #endif
45
46 #ifndef ED_SUB_COST
47 /** Cost to substitute element @p f for element @p e (i.e. replace @p e with
48  * @p f ).
49  *
50  * All algorithms which use this macro expect that <code>ED_SUB_COST(e, f) +
51  * ED_SUB_COST(f, g) >= ED_SUB_COST(e, g)</code>.  They do not check for any
52  * substitution chains and will not find minimal distances when this assumption
53  * does not hold.
54  *
55  * Although it is possible to set <code>ED_SUB_COST(e, f) >= ED_DEL_COST(e) +
56  * ED_INS_COST(f)</code>.  If this is true for all @p e and @p f, consider
57  * using edit_distance_lcs() instead of edit_distance_lev() which calculates
58  * the same result more quickly by not considering substitutions which are
59  * never less costly than delete + insert.
60  */
61 # define ED_SUB_COST(e, f) 1
62 /** Defined if the cost to substitute is the same for all element pairs. */
63 # define ED_SUB_COST_CONST
64 #endif
65
66 #ifndef ED_TRA_COST
67 /** Cost to transpose elements @p ef to @p fe.
68  *
69  * @c edit_distance_dl requires <code>2 * ED_TRA_COST(e, f) >= ED_INS_COST(g) +
70  * ED_DEL_COST(h)</code> for all @c e,f,g,h.  See Trace Theorem 3 of
71  * Wagner-Lowrance. @cite Wagner75
72  */
73 # define ED_TRA_COST(e, f) 1
74 /** Defined if the cost to transpose is the same for all element pairs. */
75 # define ED_TRA_COST_CONST
76 #endif
77
78 #if defined(DOXYGEN)
79 /** Optimized array search function for single-array-heavy workloads.
80  *
81  * The expression generated by this macro must evaluate to @c true in a boolean
82  * context when @p elem is contained in the first @p len elements of @p arr and
83  * @c false otherwise.  @p len is guaranteed to be greater than 0.
84  *
85  * This macro is currently only used when #ED_INS_COST_CONST and
86  * #ED_SUB_COST_CONST are defined.
87  *
88  * @note
89  * Only define this macro when the search function is highly optimized and when
90  * single-element arrays are expected to be passed frequently, because it adds
91  * a conditional branch to each execution of the distance functions with
92  * non-empty arguments.
93  */
94 # define ED_HAS_ELEM(arr, elem, len) (memchr(arr, elem, len) != NULL)
95 #endif
96
97 #ifndef ED_ELEM_EQUAL
98 /** Are two elements equal? */
99 # define ED_ELEM_EQUAL(elem1, elem2) (elem1 == elem2)
100 #endif
101
102 #if !defined(ED_HASH_ELEM) && !defined(ed_elem)
103 /** Hash an element to a unique value in <code>[0, ED_HASH_MAX]</code>.
104  *
105  * Note:  This module does not use a "real" dictionary.  Hash collisions are
106  * not expected nor supported.  If elements can not be uniquely mapped to a
107  * reasonable range, consider implementing a "real" dictionary.
108  */
109 # define ED_HASH_ELEM(e) ((unsigned char)e)
110 /** Maximum value that can be returned from #ED_HASH_ELEM */
111 # define ED_HASH_MAX UCHAR_MAX
112 /** Can an array of #ED_HASH_MAX ::ed_dist values be stored on the stack? */
113 # define ED_HASH_ON_STACK
114 #endif
115
116 #ifndef ED_STACK_ELEMS
117 /** Maximum number of elements that will be allocated on the stack.
118  *
119  * Note: The threshold does not need to be tight since with
120  * <code>ED_STACK_ELEMS > ~100</code> algorithm cost will dominate @c malloc
121  * cost anyway.
122  */
123 # define ED_STACK_ELEMS 512
124 #endif
125
126 #endif