1#include <math/fixed.h>
2#include <math/levenshtein.h>
3#include <math/min_max.h>
4#include <mem/alloc.h>
5#include <stdbool.h>
6#include <stdint.h>
7#include <string.h>
8
9static inline char fuzzy_fold_char(char c, bool ignore_case) {
10 if (ignore_case && c >= 'A' && c <= 'Z')
11 return c + ('a' - 'A');
12
13 return c;
14}
15
16static int64_t fuzzy_substr_distance(const char *pattern, const char *text,
17 size_t p_len, size_t t_len,
18 bool ignore_case) {
19 int64_t *prev = vnews(prev, (t_len + 1));
20 int64_t *curr = vnews(curr, (t_len + 1));
21 int64_t best_dist = -1;
22
23 if (!prev || !curr)
24 goto out;
25
26 for (size_t j = 0; j <= t_len; j++)
27 prev[j] = 0;
28
29 for (size_t i = 1; i <= p_len; i++) {
30 curr[0] = i;
31
32 char pc = fuzzy_fold_char(c: pattern[i - 1], ignore_case);
33
34 for (size_t j = 1; j <= t_len; j++) {
35 char tc = fuzzy_fold_char(c: text[j - 1], ignore_case);
36
37 int64_t cost = pc == tc ? 0 : 1;
38
39 curr[j] = MIN(curr[j - 1] + 1, prev[j] + 1, prev[j - 1] + cost);
40 }
41
42 int64_t *tmp = prev;
43 prev = curr;
44 curr = tmp;
45 }
46
47 best_dist = prev[0];
48
49 for (size_t j = 1; j <= t_len; j++) {
50 if (prev[j] < best_dist)
51 best_dist = prev[j];
52 }
53
54out:
55 vfree(prev);
56 vfree(curr);
57
58 return best_dist;
59}
60
61/* [0, 1] */
62fx32_32_t fuzzy_substr_conf(const char *pattern, const char *text,
63 bool ignore_case) {
64 size_t p_len = strlen(str: pattern);
65 size_t t_len = strlen(str: text);
66
67 if (p_len == 0)
68 return FX_ONE;
69
70 if (t_len == 0)
71 return FX_ZERO;
72
73 int64_t best_dist =
74 fuzzy_substr_distance(pattern, text, p_len, t_len, ignore_case);
75
76 if (best_dist < 0)
77 return FX_ZERO;
78
79 if ((size_t) best_dist >= p_len)
80 return FX_ZERO;
81
82 fx32_32_t max_len = fx_from_int(x: p_len);
83 fx32_32_t dist = fx_div(a: fx_from_int(x: best_dist), b: max_len);
84
85 return FX_ONE - dist;
86}
87