diff options
Diffstat (limited to 'app/bin/levenshtein.c')
-rw-r--r-- | app/bin/levenshtein.c | 95 |
1 files changed, 49 insertions, 46 deletions
diff --git a/app/bin/levenshtein.c b/app/bin/levenshtein.c index 8dc56aa..d51af01 100644 --- a/app/bin/levenshtein.c +++ b/app/bin/levenshtein.c @@ -10,63 +10,66 @@ // Returns a size_t, depicting the difference between `a` and `b`. // See <https://en.wikipedia.org/wiki/Levenshtein_distance> for more information. size_t -levenshtein_n(const char *a, const size_t length, const char *b, const size_t bLength) { - // Shortcut optimizations / degenerate cases. - if (a == b) { - return 0; - } +levenshtein_n(const char *a, const size_t length, const char *b, + const size_t bLength) +{ + // Shortcut optimizations / degenerate cases. + if (a == b) { + return 0; + } - if (length == 0) { - return bLength; - } + if (length == 0) { + return bLength; + } - if (bLength == 0) { - return length; - } + if (bLength == 0) { + return length; + } - size_t *cache = calloc(length, sizeof(size_t)); - size_t index = 0; - size_t bIndex = 0; - size_t distance; - size_t bDistance; - size_t result; - char code; + size_t *cache = calloc(length, sizeof(size_t)); + size_t index = 0; + size_t bIndex = 0; + size_t distance; + size_t bDistance; + size_t result; + char code; - // initialize the vector. - while (index < length) { - cache[index] = index + 1; - index++; - } + // initialize the vector. + while (index < length) { + cache[index] = index + 1; + index++; + } - // Loop. - while (bIndex < bLength) { - code = b[bIndex]; - result = distance = bIndex++; - index = SIZE_MAX; + // Loop. + while (bIndex < bLength) { + code = b[bIndex]; + result = distance = bIndex++; + index = SIZE_MAX; - while (++index < length) { - bDistance = code == a[index] ? distance : distance + 1; - distance = cache[index]; + while (++index < length) { + bDistance = code == a[index] ? distance : distance + 1; + distance = cache[index]; - cache[index] = result = distance > result - ? bDistance > result - ? result + 1 - : bDistance - : bDistance > distance - ? distance + 1 - : bDistance; - } - } + cache[index] = result = distance > result + ? bDistance > result + ? result + 1 + : bDistance + : bDistance > distance + ? distance + 1 + : bDistance; + } + } - free(cache); + free(cache); - return result; + return result; } size_t -levenshtein(const char *a, const char *b) { - const size_t length = strlen(a); - const size_t bLength = strlen(b); +levenshtein(const char *a, const char *b) +{ + const size_t length = strlen(a); + const size_t bLength = strlen(b); - return levenshtein_n(a, length, b, bLength); + return levenshtein_n(a, length, b, bLength); } |