git.ozlabs.org Git - ccan/blob - 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