#include <stdlib.h>
#include <stdio.h>
#include <malloc.h>


/**
 * Optimized histogram sort, Theta(4n)
 * Also ensures all elements are unique
 * Sorted descending arrays are not modifed (returns 0, no uniqueness testing)
 * Sorted ascending arrays are simply reversed (returns 0, no uniqueness testing)
 * Original algorithm by Ain Isotamm http://vvv.cs.ut.ee/~isotamm/
 * Modified by Jorma Rebane http://nasm.ateh10.net/
 * 
 * @param values Array of integer values
 * @param count  Number of integer values in the array
 * @return New length of the sorted array. Or 0 if array already sorted.
 */
int spysort(int* values, int count)
{
	// spy the min-max values to calculate the span
	int min = values[0];
	int max = min;
	int ascending  = 1, descending = 1; // assume ascending/descending
	for (int i = 1; i < count; ++i) 
	{
		const int value = values[i];
		if (value < min)      min = value, ascending = 0;  // not ascending
		else if (value > max) max = value, descending = 0; // not descending
	}

	if (ascending) // the array is already sorted
		return 0;  // no change in size
	if (descending)
	{
		int* first = values;
		int* last  = first + count;
		while (first < last) // reverse the array
		{
			int temp = *first; // generic swap
			*first++ = *--last;
			*last    = temp;
		}
		return 0; // no change in size
	}

	const int size = (max - min) + 1; // the number of elements in the histogram

	// initialize histogram and set all elements to 0.
	// use static allocation for small histograms (alloca)
	char _sbuff[4096];
	char* histogram = size <= 4096 ? _sbuff : malloc(size);
	memset(histogram, 0, size);

	for (int i = 0; i < count; ++i) // populate the histogram
		histogram[values[i] - min] = 1;

	int outi = 0;
	for (int i = 0; i < size; ++i) // iterate the span and write out unique values
		if (histogram[i])
			values[outi++] = i + min;

	if (size > 4096) // free if we used malloc
		free(histogram);
	return size;
}



/**
 * Standard quicksort for reference
 */
int quicksort(int* values, int count);


/**
 * Ascending/Descending optimized quicksort
 */
int quicksort_opt(int* values, int count);



// measure highest accuracy time in seconds for both Windows and Linux
#if _WIN32
#define WIN32_LEAN_AND_MEAN
#include <Windows.h>
double timer_Time()
{
	static double timer_freq = 0.0;
	LARGE_INTEGER t;
	if (timer_freq == 0.0) // initialize high perf timer frequency
	{
		QueryPerformanceFrequency(&t);
		timer_freq = (double) t.QuadPart;
	}
	QueryPerformanceCounter(&t);
	return (double) t.QuadPart / timer_freq;
}
#else
#include <time.h>
double timer_Time()
{
	struct timespec tm;
	clock_gettime(CLOCK_REALTIME, &tm);
	return tm.tv_sec + (double) tm.tv_nsec / 1000000000.0;
}
#endif



// print out count elements from an array
void print_array(int* values, int count)
{
	printf("{ ");
	for (int i = 0; i < count; ++i)
		printf("%d ", values[i]);
	printf(" ... }\n");
}

// generic generate + sort with time measuring
void measure_ms(const char* name, int* values, int count, 
	              int (*algorithm)(int*,int), 
				  void(*generation_func)(int*, int))
{
	generation_func(values, count);
	double start = timer_Time();
	algorithm(values, count);

	double elapsed = (timer_Time() - start) * 1000.0;
	printf("%-10s = %4.4gms\n", name, elapsed);
}


// populate an array with pseudorandom values
void generate_rand(int* values, int count)
{
	srand(997); // seed with a consisten prime
	for (int i = 0; i < count; ++i)
		values[i] = rand();
}
// populate an array with sorted ascending values
void generate_sorted(int* values, int count)
{
	for (int i = 0; i < count; ++i)
		values[i] = i;
}
// populate an array with descending values
void generate_descending(int* values, int count)
{
	int n = count;
	for (int i = 0; i < count; ++i)
		values[i] = --n;
}

int main(int argc, char** argv)
{
	static int values[10000000];
	const int maxCount = 10000000;
	int measureCounts[] = { 
		50, 100, 250, 500, 750, 1000, 1500, 3000, 5000, 10000, 25000, 
		50000, 75000, 100000, 150000, 200000, 250000, 500000
	};
	const int numCounts = sizeof(measureCounts) / sizeof(int);

	for (int i = 0; i < numCounts; ++i)
	{
		int count = measureCounts[i];
		printf("---------------------\n");
		printf("| %d elements |\n", count);
		printf("-----------------------------------\n");
		measure_ms("  spysort random    ", values, count, spysort, generate_rand);
		measure_ms("  spysort sorted    ", values, count, spysort, generate_sorted);
		measure_ms("  spysort descending", values, count, spysort, generate_descending);
		measure_ms("    qsort random    ", values, count, quicksort, generate_rand);
		measure_ms("    qsort sorted    ", values, count, quicksort, generate_sorted);
		measure_ms("    qsort descending", values, count, quicksort, generate_descending);
		measure_ms("qsort_opt random    ", values, count, quicksort_opt, generate_rand);
		measure_ms("qsort_opt sorted    ", values, count, quicksort_opt, generate_sorted);
		measure_ms("qsort_opt descending", values, count, quicksort_opt, generate_descending);
		printf("-----------------------------------\n");
	}
	
	system("pause");
	return 0;
}




static void swap(int* first, int* second)
{
	int temp = *first;
	*first  = *second;
	*second = temp;
}

/**
 * Simple Quicksort implementation
 * @note Algorithm from http://en.wikipedia.org/wiki/Quicksort
 * @author ``left is the index of the leftmost element of the subarray´´
 * @author ``right is the index of the rightmost element of the subarray (inclusive)´´
 * @author ``number of elements in subarray = right-left+1´´
 */
static int qs_partition(int* list, int left, int right, int pivotIndex)
{
	const int pivotValue = list[pivotIndex];
	swap(&list[pivotIndex], &list[right]); // move pivot to end
	int storeIndex = left;
	for (int i = left; i < right; ++i)
	{
		if (list[i] < pivotValue)
		{
			swap(&list[i], &list[storeIndex]);
			++storeIndex;
		}
	}
	swap(&list[storeIndex], &list[right]); // move pivot to its final place
	return storeIndex;
}
static void qs_sort(int* list, int left, int right)
{
	if (left < right)
	{
		int pivotIndex = left + (right - left) / 2;
		pivotIndex = qs_partition(list, left, right, pivotIndex);

		qs_sort(list, left, pivotIndex - 1);
		qs_sort(list, pivotIndex + 1, right);
	}
}
int quicksort(int* values, int count)
{
	qs_sort(values, 0, count);
	return count;
}

int quicksort_opt(int* values, int count)
{
	int prev = values[0];
	int ascending  = 1, descending = 1; // assume ascending/descending
	for (int i = 1; i < count; ++i) 
	{
		const int value = values[i];
		if (value < prev)      ascending = 0;  // not ascending
		else if (value > prev) descending = 0; // not descending
		prev = value;
	}

	if (ascending)
		return 0; // nothing to do here

	if (descending)
	{
		int* first = values;
		int* last  = first + count;
		while (first < last) // reverse the array
		{
			int temp = *first; // generic swap
			*first++ = *--last;
			*last    = temp;
		}
		return 0;
	}

	qs_sort(values, 0, count);
	return count;
}