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

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

#define TAIL(base,nmel,width) ((base) + ((nmel) - 1) * (width))

/* get index of last block whose head is less than the previous block's tail */
static size_t last_overlap(char *base, size_t bcount, size_t bwidth, size_t width, cmpfun cmp)
{
	for (char *cur = TAIL(base, bcount, bwidth); --bcount; cur -= bwidth)
		if (cmp(cur - width, cur) > 0) break;
	return bcount;
}

size_t merge(char *base, size_t anmel, size_t bnmel, size_t bufnmel, size_t width, cmpfun cmp)
{
	char *a_end   = base  +   anmel * width;
	char *b_end   = a_end +   bnmel * width;
	char *buf_end = b_end + bufnmel * width;
	size_t count = 0;

	while (bnmel) {
		char *a   =   a_end - width;
		char *b   =   b_end - width;
		char *buf = buf_end - width;

		if (cmp(a, b) > 0) { swap(a, buf, width); a_end = a; anmel--; }
		else               { swap(b, buf, width); b_end = b; bnmel--; }
		count++;
		buf_end = buf;
	}
	return count;
}

void grailsort(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 blknmel = sqrt(nmel);               /* elements in a block */
	size_t bufnmel = blknmel + nmel % blknmel; /* elements in the buffer */
	size_t bwidth  = blknmel * width;          /* size of a block in bytes */
	size_t blocks  = nmel / blknmel - 1;       /* number of blocks in a + b */
	size_t acount  = blocks / 2;
	size_t bcount  = blocks - acount;

	char *a = base;
	char *b = a + acount * bwidth;
	grailsort(a, acount * blknmel, width, cmp);
	grailsort(b, bcount * blknmel, width, cmp);

	/* sort all the a and b blocks together by their head elements */
	grailsort(base, blocks, bwidth, cmp);

	/* merge, starting from the end and working towards the beginning */
	size_t bufidx = blocks * blknmel;
	while (blocks > 1) {
		size_t overlap = last_overlap(base, blocks, bwidth, width, cmp);
		if (overlap) {
			bufidx -= merge(TAIL(base, overlap, bwidth), blknmel, bufidx - overlap*blknmel, bufnmel, width, cmp);
		}
		blocks = overlap;
	}

	if (bufidx) {
		rotate(base, (bufidx + bufnmel) * width, bufidx * width);
	}

distribute:
	grailsort(base, bufnmel, width, cmp);
	distribute_buffer(base, bufnmel, nmel - bufnmel, width, cmp);
}