#include <stdlib.h>

#include "util.h"

int cmpint(const void *p1, const void *p2) {
	return *(int*)p1 - *(int*)p2;
}

void quicksort(int *data, int start, int end) {
	qsort(&data[start], end-start+1, sizeof(int), cmpint);
}

void reverse(int *data, int start, int end) {
	int temp;
	while (start < end) {
		temp = data[start];
		data[start] = data[end];
		data[end] = temp;
		start++; end--;
	}
}

void permute(int *data, int count) {
	int i, p, t;
	for (i = count-1; i >= 0; i--) {
		p = (int) ((i+1) * (rand() / (RAND_MAX + 1.0)));
		t = data[i];
		data[i] = data[p];
		data[p] = t;
	}
}

void result_add(struct result_node **list, int value) {
	// make sure we have a list
	if (*list == NULL) {
		*list = (struct result_node *)malloc(sizeof(struct result_node));
		(*list)->value = value;
		(*list)->prob = 1;
		(*list)->next = NULL;
		return;
	}
	// walk the list
	struct result_node *cur = *list, *last = NULL;
	while ((cur != NULL) && (cur->value < value)) {
		last = cur;
		cur = cur->next;
	}
	// see what we have to do
	if (cur == NULL) {
		cur = (struct result_node *)malloc(sizeof(struct result_node));
		cur->value = value;
		cur->prob = 1;
		cur->next = NULL;
		last->next = cur;
		return;
	}
	else if (cur->value == value) {
		cur->prob++;
		return;
	}
	else if (last != NULL) {
		last->next = (struct result_node *)malloc(sizeof(struct result_node));
		last->next->value = value;
		last->next->prob = 1;
		last->next->next = cur;
	}
	else {
		*list = (struct result_node *)malloc(sizeof(struct result_node));
		(*list)->value = value;
		(*list)->prob = 1;
		(*list)->next = cur;
	}
}

inline void swapperm(int *data, int i, int j) {
	if (i == j)
		return;
	data[i] ^= data[j];
	data[j] ^= data[i];
	data[i] ^= data[j];
};

void _rec_all_permutations(int *data, int count, 
		void (*callback)(int *data, int count, void *arg, float farg), 
		void *arg, float farg, int n) {
	if (1 == n) {
		callback(data, count, arg, farg);
	}
	else {
		int c;
		for (c = 0; c < n; c++) {
			_rec_all_permutations(data, count, callback, arg, farg, n-1);
			swapperm(data,  n%2 == 1 ? 0 : c, n-1); 
		}
	}
}

void all_permutations(int *data, int count, 
		void (*callback)(int *data, int count, void *arg, float farg), 
		void *arg, float farg) {
	_rec_all_permutations(data, count, callback, arg, farg, count);
}

long factorial(int n) {
	long fact = 1;
	while (n > 0) {
		fact *= n--;
	}
	return fact;
}