1 files changed, 110 insertions, 0 deletions
diff --git a/fuzzy.c b/fuzzy.c
new file mode 100644
index 0000000..f5d9b50
--- /dev/null
+++ b/fuzzy.c
@@ -0,0 +1,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;
+}