#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;
}