/* 
 * Author: Martin Matusiak <numerodix@gmail.com>
 * Licensed under the GNU Public License, version 3.
 */

#include <math.h>
#include <stdbool.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <time.h>


typedef unsigned long unit;
typedef unsigned long ulen;

typedef struct {
	char *name;
	ulen cmp;
	ulen ass;
	ulen rec;
} Metrics;


/* print array convenience function */
void p(unit* arr, ulen length) {
	for (ulen i=0; i<length; i++) printf("[%.2lu]  %ld\n", i, arr[i]); 
	printf("\n");
}

/* print algorithm metrics */
void p_metrics(char *f, double rt, int eq, int srtd, ulen length, ulen comparisons, ulen swaps, ulen rec) {
	printf("=== %s ===\n", f);
	printf("n          : %ld\n", length);
	printf("n*log(n)   : %ld\n", (ulen) (length*log2(length)));
	printf("n^2        : %ld\n", (ulen) pow(length, 2));
	if (rec) printf("calls      : %ld\n", rec);
	printf("comparisons: %ld\n", comparisons);
	printf("assignments: %ld\n", swaps);
	printf("runtime    : %fs\n", rt);
	if (!eq) printf("is sane    : FAIL\n");
	if (!srtd) printf("is sorted  : FAIL\n");
}

/* initialize array with data from a file */
unit* random_array(ulen length) {
	unit *arr = (unit*) malloc(sizeof(unit) * length);
	char *randfile = "/dev/urandom";

	FILE *rand_stream = fopen(randfile, "r");
	if (rand_stream == NULL
		|| (fread(arr, sizeof(unit), length, rand_stream) < length)
		|| fclose(rand_stream)) 
	{
		printf("Failed to read %s\n", randfile);
		exit(1);
	}

	return arr;
}

/* deep copy array */
unit *clone_array(unit *arr, ulen length) {
	unit *copy = (unit*) malloc(sizeof(unit) * length);
	memcpy(copy, arr, sizeof(unit) * length);
	return copy;
}

/* type agnostic check, first find smallest element, then iterate again
 * and compare. worst case: 2n (when sorted) */
int is_sorted(unit* arr, ulen length) {
	unit e = 1;
	for(ulen i=0; i<length; i++) {
		if (e > arr[i]) e = arr[i];
	}
	for(ulen i=0; i<length; i++) {
		if (e > arr[i]) return false;
		e = arr[i];
	}
	return true;
}

int cmp(const void *a, const void *b) {
	if (*((const unit*) a) < (*(const unit*) b)) return -1;
	if (*((const unit*) a) > (*(const unit*) b)) return 1;
	return 0;
}

/* equivalence check on arrays */
int is_equiv(unit *arr, unit *srtd, ulen length) {
	qsort(arr, length, sizeof(unit), &cmp);
	for(ulen i=0; i<length; i++) {
		if (arr[i] != srtd[i]) return false;
	}
	return true;
}

/* algorithm timing wrapper function */
void time_f(unit* arr, ulen length, Metrics (*f)(unit* arr, ulen length)) {
	unit *copy = clone_array(arr, length);

	clock_t c0 = clock();
	Metrics ms = (*f)(arr, length);
	clock_t c1 = clock();
	double runtime = (((double) c1 - c0) / CLOCKS_PER_SEC);

	int eq = is_equiv(copy,	arr, length);
	int srtd = is_sorted(arr, length);
	p_metrics(ms.name, runtime, eq, srtd, length, ms.cmp, ms.ass, ms.rec);
}

/* Sorting algorithms */

Metrics bubblesort(unit *arr, ulen length) {
	Metrics ms = {"bubblesort", 0, 0, 1};
	ulen swaps = 1;
	unit swap;
	for(ulen i=0; i<length-1 && swaps > 0; i++) {
		swaps = 0;
		for (ulen j=0; j<length-1; j++, ms.cmp++) {
			if (arr[j] > arr[j+1]) {
				swaps += 3;
				swap = arr[j];
				arr[j] = arr[j+1];
				arr[j+1] = swap;
			}
		}
		ms.ass += swaps;
	}
	return ms;
}

Metrics insertionsort(unit *arr, ulen length) {
	Metrics ms = {"insertionsort", 0, 0, 1};
	ulen j;
	unit swap;
	for(ulen i=1; i<length; i++, ms.ass+=2) {
		swap = arr[i];
		for(j=i-1; ms.cmp++, j>=0 && arr[j] > swap; j--, ms.ass++) {
			arr[j+1] = arr[j];
		}
		arr[j+1] = swap;
	}
	return ms;
}

Metrics selectionsort(unit *arr, ulen length) {
	Metrics ms = {"selectionsort", 0, 0, 1};
	unit swap;
	ulen cursor;
	for(ulen i=0; i<length-1; i++) {
		cursor = 0;
		for(ulen j=i+1; j<length; j++, ms.cmp+=2) {
			if (arr[i] > arr[j] && (cursor == 0 || arr[cursor] >= arr[j])) {
				cursor = j;
			}
		}
		if (cursor > 0) {
			swap = arr[i];
			arr[i] = arr[cursor];
			arr[cursor] = swap;
			ms.ass += 3;
		}
	}
	return ms;
}

Metrics mergesort(unit *arr, ulen length) {
	Metrics ms = {"mergesort", 0, 0, 1};
	if (length > 1) {
		ulen mid = length / 2;
		Metrics rms = mergesort(arr, mid);
		Metrics lms = mergesort(&arr[mid], length-mid);

		unit *temp = malloc(length * sizeof(unit)); 

		ulen i, l = 0, r = mid;
		for(i=0; i<length && l < mid && r < length; i++, ms.cmp++, ms.ass++) {
			if (arr[l] < arr[r]) {
				temp[i] = arr[l++];
			} else {
				temp[i] = arr[r++];
			}
		}
		if (l < mid)
			memcpy(&temp[i], &arr[l], (length-i) * sizeof(unit));
		if (r < length)
			memcpy(&temp[i], &arr[r], (length-i) * sizeof(unit));

		memcpy(arr, temp, length * sizeof(unit));
		free(temp);

		ms.cmp += lms.cmp + rms.cmp;
		ms.ass += lms.ass + rms.ass + (length - i) + length;
		ms.rec += lms.rec + rms.rec;
	}
	return ms;
}

Metrics quicksort(unit *arr, ulen length) {
	Metrics ms = {"quicksort", 0, 0, 1};
	if (length > 1) {
		unit pivot = arr[0];

		unit *left = malloc(length * sizeof(unit));
		unit *right = malloc(length * sizeof(unit));

		ulen l = 0, r = 0;
		for(ulen i=1; i<length; i++, ms.cmp++, ms.ass++) {
			if (arr[i] < pivot) {
				left[l++] = arr[i];
			} else {
				right[r++] = arr[i];
			}
		}

		arr[l] = pivot;
		memcpy(arr, left, l * sizeof(unit));
		memcpy(&arr[l+1], right, r * sizeof(unit));

		free(left);
		free(right);

		Metrics lms = quicksort(arr, l);
		Metrics rms = quicksort(&arr[l+1], r);

		ms.cmp += lms.cmp + rms.cmp;
		ms.ass += lms.ass + rms.ass + length + 1;
		ms.rec += lms.rec + rms.rec;
	}
	return ms;
}


int main() {
	ulen length = (ulen) 1e5;

	unit *arr1 = random_array(length);
	unit *arr2 = clone_array(arr1, length);
	unit *arr3 = clone_array(arr1, length);
	unit *arr4 = clone_array(arr1, length);
	unit *arr5 = clone_array(arr1, length);

	time_f(arr1, length, &mergesort);
	time_f(arr2, length, &quicksort);
	time_f(arr3, length, &insertionsort);
	time_f(arr4, length, &selectionsort);
	time_f(arr5, length, &bubblesort);

	return 0;
}