#include <math.h>
#include <stddef.h>

#include "sorters.h"
#include "common.h"

struct array {
	char  *base;
	size_t nmel;
};

/* buf must be large enough to hold as->nmel elements */
static void merge_blocks(char *buf, struct array *as, size_t bs_nmel, size_t width, cmpfun cmp)
{
	char *a = buf;
	char *b = as->base + as->nmel * width;
	char *target = as->base;

	swap(a, as->base, as->nmel * width);

	while (as->nmel > 0 && bs_nmel > 0) {
		if (cmp(a, b) <= 0) {
			swap(target, a, width);
			a += width; as->nmel--;
		} else {
			swap(target, b, width);
			b += width; bs_nmel--;
		}
		target += width;
	}

	swap(target, a, as->nmel * width);
}

static char *find_min_block(char *base, size_t count, size_t bwidth, size_t width, cmpfun cmp)
{
	char *min = base;
	for (base += bwidth, count--; count--; base += bwidth) {
		if (cmp(min + bwidth - width, base) > 0) min = base;
	}
	return min;
}

static size_t roll(struct array *a, struct array *b,
	size_t bwidth, size_t width, char **mina, cmpfun cmp)
{
	size_t iters = 0;
	while (b->nmel && cmp(b->base , *mina + bwidth - width) < 0) {
		swap(a->base, b->base, bwidth);
		if (*mina == a->base) *mina = b->base;
		a->base += bwidth;
		b->base += bwidth;
		b->nmel--;
		iters++;
	}
	return iters;
}

void wikisort(void *unsorted, size_t nmel, size_t width, cmpfun cmp)
{
	char *base = unsorted;

	if (nmel <= MAX_SORTNET) {
		sorting_network(base, nmel, width, cmp);
		return;
	}

	size_t bnmel  = sqrt(nmel);   /* elements in a block */
	size_t bcount = nmel / bnmel;
	size_t bwidth = bnmel * width;

	/* temporary buffer: nmel is measured in array elements */
	struct array buf = { .base = base, .nmel = bnmel + nmel % bnmel };

	/* A and B subarrays: nmel is measured in blocks of bnmel elements each */
	struct array a = { .base = buf.base +  width * buf.nmel, .nmel = (bcount - 1) / 2 };
	struct array b = { .base =   a.base + bwidth *   a.nmel, .nmel =  bcount - 1 - a.nmel };

	/* sort the buffer as if it were part of the a array */
	wikisort(buf.base, buf.nmel + a.nmel * bnmel, width, cmp);
	wikisort(b.base,              b.nmel * bnmel, width, cmp);

	/* if already sorted, nothing to do */
	if (cmp(b.base - width, b.base) <= 0) return;

	/* if blocks in b are all less than those in a, just need a rotate */
	if (cmp(base + (nmel - 1) * width, base) <= 0) {
		rotate(base, nmel * width, (a.nmel * bnmel + buf.nmel) * width);
		return;
	}

	struct array penda = { 0 };
	size_t pendb_nmel = 0;
	char *mina = a.base;
	while (a.nmel) {
		size_t rolled_blocks = b.nmel ? roll(&a, &b, bwidth, width, &mina, cmp) : 0;

		/* move mina block to immediately after rolled b blocks */
		if (mina != a.base) swap(mina, a.base, bwidth);

		/* rotate mina into correct spot in the last rolled b */
		pendb_nmel += rolled_blocks * bnmel;
		if (pendb_nmel) {
			size_t offset = pendb_nmel - binary_search(a.base, a.base - pendb_nmel * width, pendb_nmel, width, cmp);
			rotate(a.base - offset * width, (bnmel + offset) * width, offset * width);

			pendb_nmel -= offset;
			if (penda.nmel && pendb_nmel) {
				merge_blocks(buf.base, &penda, pendb_nmel, width, cmp);
			}

			penda.base = a.base - offset * width;
			penda.nmel = bnmel;
			pendb_nmel = offset;
		} else {
			penda.nmel = 0;
			pendb_nmel = 0;
		}

		a.base += bwidth;
		if (--a.nmel) {
			mina = find_min_block(a.base, a.nmel, bwidth, width, cmp);
		}
	}

	if (penda.nmel) {
		merge_blocks(buf.base, &penda, b.nmel * bnmel + pendb_nmel, width, cmp);
	}

	wikisort(buf.base, buf.nmel, width, cmp);
	distribute_buffer(buf.base, buf.nmel, nmel - buf.nmel, width, cmp);
}