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

#include "sorters.h"

static void swap(char *a, char *b, size_t width)
{
	while (width--) {
		char tmp = *a;
		*a++ = *b;
		*b++ = tmp;
	}
}

static void reverse(char *base, size_t nmel, size_t width)
{
	char *last = base + (nmel - 1) * width;
	while (last > base) {
		swap(base, last, width);
		base += width;
		last -= width;
	}
}

/* rotates left */
static void rotate(char *base, size_t nmel, size_t width, size_t shift)
{
	reverse(base, shift, width);
	reverse(base + shift * width, nmel - shift, width);
	reverse(base, nmel, width);
}

/* If a matching element exists, returns index of one of them.
   If none exists, returns index where such an element should be inserted. */
static size_t binary_search(const char *needle, char *haystack, size_t nmel, size_t width, cmpfun cmp)
{
	size_t baseidx = 0;
	while (nmel) {
		size_t tryidx = baseidx + nmel / 2;
		char *try = haystack + tryidx * width;
		int sign = cmp(try, needle);
		if (!sign) return tryidx;
		else if (sign < 0) {
			baseidx = tryidx + 1;
			nmel -= nmel / 2 + 1;
		}
		else {
			nmel /= 2;
		}
	}
	return baseidx;
}

static void distribute_buffer(char *base, size_t bufnmel, size_t sortnmel, size_t width, cmpfun cmp)
{
	char *sorted = base + bufnmel * width;
	while (bufnmel) {
		char *last = sorted - width;
		size_t equals;
		for (equals = 1; equals < bufnmel; equals++) {
			if (cmp(last, last - equals * width)) break;
		}

		size_t insertpos = binary_search(last, sorted, sortnmel, width, cmp);
		rotate(sorted - equals * width, insertpos + equals, width, equals);

		bufnmel  -= equals;
		sortnmel += equals;
		sorted   -= equals * width;
	}
}

#define MAX_SORTNET 8

static const uint8_t sortnet[][2] = {
	/* 0: index =  0 */
	/* 1: index =  0 */
	/* 2: index =  0 */
	{0,1},
	/* 3: index =  1 */
	{0,1}, {0,2}, {1,2},
	/* 4: index =  4 */
	{0,1}, {2,3}, {0,2}, {1,3}, {1,2},
	/* 5: index =  9 */
	{0,1}, {3,4}, {2,4}, {2,3}, {1,4}, {0,3}, {0,2}, {1,3}, {1,2},
	/* 6: index = 18 */
	{1,2}, {4,5}, {0,2}, {3,5}, {0,1}, {3,4}, {2,5}, {0,3}, {1,4}, {2,4},
	{1,3}, {2,3},
	/* 7: index = 30 */
	{1,2}, {3,4}, {5,6}, {0,2}, {3,5}, {4,6}, {0,1}, {4,5}, {2,6}, {0,4},
	{1,5}, {0,3}, {2,5}, {1,3}, {2,4}, {2,3},
	/* 8: index = 46 */
	{0,1}, {2,3}, {4,5}, {6,7}, {0,2}, {1,3}, {4,6}, {5,7}, {1,2}, {5,6},
	{0,4}, {3,7}, {1,5}, {2,6}, {1,4}, {3,6}, {2,4}, {3,5}, {3,4},
	/* 9: index = 65, if we used a sorting network this large */
};

static const uint8_t sortnet_index[] = { 0, 0, 0, 1, 4, 9, 18, 30, 46, 65 };

static void sorting_network(char *base, size_t nmel, size_t width, cmpfun cmp)
{
	for (int i = sortnet_index[nmel]; i < sortnet_index[nmel+1]; i++) {
		char *elem1 = base + sortnet[i][0] * width;
		char *elem2 = base + sortnet[i][1] * width;
		if (cmp(elem1, elem2) > 0) swap(elem1, elem2, width);
	}
}