typedef struct wstr {
	wchar_t *s;
	int n, alloc;
} wstr;



wstr *w_new()
{
	wstr *w = malloc(sizeof(wstr));
	w->alloc = 1;
	w->n = 0;
	w->s = malloc(sizeof(wchar_t));
	w->s[0] = 0;
	return w;
}

void w_append(wstr *w, wchar_t c)
{
	int n = w->n + 1;
	if (n >= w->alloc) {
		w->alloc *= 2;
		w->s = realloc(w->s, w->alloc * sizeof(wchar_t));
	}
	w->s[w->n++] = c;
	w->s[w->n] = 0;
}

wstr *w_make(wchar_t *s)
{
	int i, len = wcslen(s);
	wstr *w = w_new();
	for (i = 0; i < len; i++) w_append(w, s[i]);
	return w;
}

typedef void (*wtrans_func)(wstr *, wstr *);
void w_transform(wstr *in, wtrans_func f)
{
	wstr t, *out = w_new();
	f(in, out);
	t = *in; *in = *out; *out = t;
	w_del(out);
}


transfunc(nocase) {
	int i;
	wchar_t c;
	forchars(i, c, in) w_append(out, towlower(c));
}

transfunc(despace) {
	int i, gotspace = 0;
	wchar_t c;
	forchars(i, c, in) {
		if (!iswspace(c)) {
			if (gotspace && out->n)
				w_append(out, L' ');
			w_append(out, c);
			gotspace = 0;
		} else	gotspace = 1;
	}
}

static const wchar_t *const tbl_accent[] = { 
	L, L, L, L, L, L, L, L, L, L,
	L, L, L, L, L, L, L, L, L, L, L,
	L, L, L, L, L, L, L, L, L, L, L,
	L, L, L, L, L, L, L, L, L, L, L,
	L, L, L, L, L, L, L, L, L, L,
	L, L, L, L, L, L, L, L, L, L,
	L, L, L, L, L, L, L, L, L, L,
	L, L, L, L, L, L, L, L, L, L, L,
	L, L, L, L, L, L, L, L, L, L, L, L,
	L, L, L, L, L, L, L, L, L, L, L, L,
	L, L, L, L, L, L, L, L, L, L };

static const wchar_t *const tbl_ligature[] = {
	L, L, L, L, L, L,
	L, L, L, L, L, L, L, L, L, L,
	L, L, L, L, L, L, 
};

void w_char_repl(wstr *in, wstr *out, const wchar_t *const *tbl, int len)
{
	int i, j, k;
	wchar_t c;
	forchars(i, c, in) {
		for (j = k = 0; j < len; j += 2) {
			if (c != tbl[j][0]) continue;
			for (k = 0; tbl[j + 1][k]; k++)
				w_append(out, tbl[j + 1][k]);
			break;
		}
		if (!k) w_append(out, c);
	}
}

transfunc(noaccent) {
	w_char_repl(in, out, tbl_accent, sizeof(tbl_accent)/sizeof(wchar_t*));
}

transfunc(noligature) {
	w_char_repl(in, out, tbl_ligature, sizeof(tbl_ligature)/sizeof(wchar_t*));
}

static const wchar_t *const tbl_article[] = {
	L, L, L, L, L, L };

transfunc(noarticle) {
	int i, j, n;
	wchar_t c, c0 = 0;
	forchars(i, c, in) {
		if (!c0 || (iswalnum(c) && !iswalnum(c0))) { 
			for (j = N_ARTICLES - 1; j >= 0; j--) {
				n = wcslen(tbl_article[j]);
				if (wcsncasecmp(in->s + i, tbl_article[j], n))
					continue;
				if (iswalnum(in->s[i + n])) continue;
				i += n;
				break;
			}
			if (j < 0) w_append(out, c);
		} else
			w_append(out, c);
		c0 = c;
	}
}

enum { wi_space = 0, wi_case, wi_accent, wi_lig, wi_article, wi_numeric };






const wtrans_func trans_funcs[] = {
	w_despace, w_nocase, w_noaccent, w_noligature, w_noarticle, 0
};
const char *const flagnames[] = {
	,
	,
	,
	,
	,
	,
};

typedef struct { wchar_t* s; wstr *w; } kw_t;
int w_numcmp(const void *a, const void *b)
{
	wchar_t *pa = ((const kw_t*)a)->w->s, *pb = ((const kw_t*)b)->w->s;
	int sa, sb, ea, eb;
	while (*pa && *pb) {
		if (iswdigit(*pa) && iswdigit(*pb)) {
			
			sa = sb = 0;
			while (pa[sa] == L'0') sa++;
			while (pb[sb] == L'0') sb++;
			
			ea = sa; eb = sb;
			while (iswdigit(pa[ea])) ea++;
			while (iswdigit(pb[eb])) eb++;
			if (eb - sb > ea - sa) return -1;
			if (eb - sb < ea - sa) return 1;
			while (sb < eb) {
				if (pa[sa] > pb[sb]) return 1;
				if (pa[sa] < pb[sb]) return -1;
				sa++; sb++;
			}

			pa += ea; pb += eb;
		}
		else if (iswdigit(*pa)) return 1;
		else if (iswdigit(*pb)) return -1;
		else {
			if (*pa > *pb) return 1;
			if (*pa < *pb) return -1;
			pa++; pb++;
		}
	}
	return (!*pa && !*pb) ? 0 : *pa ?  1 : -1;
}

int w_cmp(const void *a, const void *b)
{
	return wcscmp(((const kw_t*)a)->w->s, ((const kw_t*)b)->w->s);
}

void natural_sort(wchar_t **strings, int len, int flags)
{
	int i, j;
	kw_t *kws = malloc(sizeof(kw_t) * len);

	for (i = 0; i < len; i++) {
		kws[i].s = strings[i];
		kws[i].w = w_make(strings[i]);
		for (j = 0; j < wi_numeric; j++)
			if (flags & (1 << j) && trans_funcs[j])
				w_transform(kws[i].w, trans_funcs[j]);
	}

	qsort(kws, len, sizeof(kw_t), (flags & WS_NUMERIC) ? w_numcmp : w_cmp);
	for (i = 0; i < len; i++) {
		w_del(kws[i].w);
		strings[i] = kws[i].s;
	}
	free(kws);
}

const wchar_t *const test[] = {
	L, L, L, L,
	L,
	L,
	L,
};


void test_sort(int flags)
{
	int i, j;
	const wchar_t *str[N_STRINGS];
	memcpy(str, test, sizeof(test));

	printf();
	for (i = 0, j = flags; j; i++, j >>= 1)
		if ((j & 1))
			printf(, flagnames[i], j > 1 ? :);

	natural_sort((wchar_t **)str, N_STRINGS, flags);

	for (i = 0; i < N_STRINGS; i++)
		printf(, str[i]);
	printf();
}

int main()
{
	setlocale(LC_CTYPE, );

	test_sort(WS_NOSPACE);
	test_sort(WS_NOCASE);
	test_sort(WS_NUMERIC);
	test_sort(WS_NOARTICLE|WS_NOSPACE);
	test_sort(WS_NOCASE|WS_NOSPACE|WS_ACCENT);
	test_sort(WS_LIGATURE|WS_NOCASE|WS_NOSPACE|WS_NUMERIC|WS_ACCENT|WS_NOARTICLE);

	return 0;
}