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