1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
|
#include <stdint.h>
#include <string.h>
#include "str.h"
#include "arena.h"
typedef struct {
uint16_t score, start;
} FuzzyScore;
static inline char
to_lower(char c)
{
/* TODO: consider utf-8 support */
if (c >= 'A' && c <= 'Z') return c + ('a' - 'A');
return c;
}
static inline int
fz_start_score(Str s, Str p)
{
if (!p.n || str_eql(s, p)) return 0;
int n = 1;
int pi = 0, si = 0;
for (;;) {
if (to_lower(p.s[pi]) == to_lower(s.s[si])) {
si++;
pi++;
if (si == s.n) {
return pi < p.n ? -1 : n;
} else if (pi == p.n) {
return n;
}
} else {
si++;
n++;
if (si == s.n) return -1;
}
}
}
static inline FuzzyScore
fz_score(Str s, Str p)
{
if (!p.n) return (FuzzyScore) { 0, 0 };
int score = -1;
int score_start = 0;
for (int i = 0; i < s.n; i++) {
int f = fz_start_score(str_skip(s, i), p);
if (f == -1) continue;
if (score == -1 || f < score) {
score = f;
score_start = i;
}
}
if (score == -1) return (FuzzyScore) { 0xffff, 0 };
return (FuzzyScore) { score, score_start };
}
static inline int
fz_cmp(FuzzyScore a, FuzzyScore b, Str sa, Str sb)
{
if (a.score < b.score) return -1;
if (b.score < a.score) return 1;
if (sa.n < sb.n) return -1;
if (sb.n < sa.n) return 1;
return (b.start < a.start) - (a.start < b.start);
}
void
fz_qsort_opt(Str * restrict dest, FuzzyScore * restrict scr, int n)
{
int i = 0, j = n - 1;
FuzzyScore x = scr[n / 2];
Str xs = dest[n / 2];
do {
while (fz_cmp(scr[i], x, dest[i], xs) < 0) i++;
while (fz_cmp(x, scr[j], xs, dest[j]) < 0) j--;
if (i <= j) {
Str t0 = dest[i];
dest[i] = dest[j];
dest[j] = t0;
FuzzyScore t1 = scr[i];
scr[i] = scr[j];
scr[j] = t1;
i++;
j--;
}
} while (i <= j);
if (0 < j) fz_qsort_opt(dest, scr, j + 1);
if (i+1 < n) fz_qsort_opt(dest + i, scr + i, n - i);
}
int
fz_sort(Str * restrict out, const Str * restrict src, int n, Str pat, Arena *scratch)
{
FuzzyScore *scr = new_arr(scratch, FuzzyScore, n);
int scrn = 0;
for (int i = 0; i < n; i++) {
FuzzyScore s = fz_score(src[i], pat);
if (s.score != 0xffff) {
scr[scrn] = s;
out[scrn] = src[i];
scrn++;
}
}
if (pat.n > 0)
fz_qsort_opt(out, scr, scrn);
return scrn;
}
|
