#include "stdafx.h"
#include "Threads.h"

/*
			100		1000	5000	10000	50000	100000	500000	1000000	5242880
-----------------------------------------------------------------------------------
Radix		86		155		436		827		4072	8125	58643	220147	2441194
Radix MT	476		543		728		1122	4021	7462	45861	147746	1683977
IntroSort	10		151		932		1990	11752	24035	125435	233972	1209109
std::sort	12		175		1068	2318	13454	28274	147500	290524	1448402

*/

//#define NB_TO_SORT	100
//#define NB_TO_SORT	1000
//#define NB_TO_SORT	5000
//#define NB_TO_SORT	10000
//#define NB_TO_SORT	50000
//#define NB_TO_SORT	100000
#define NB_TO_SORT	500000
//#define NB_TO_SORT	1000000
//#define NB_TO_SORT	5242880		// (1 << 20) * 5

//#define RADIX_SORTER	RadixSort
#define RADIX_SORTER	RadixSort3

static float* gValues = null;

void InitSortValues()
{
	SRand(0);
	gValues = new float[NB_TO_SORT];
	for(udword i=0;i<NB_TO_SORT;i++)
		gValues[i] = (UnitRandomFloat()-0.5f)*1000.0f;
}

void ReleaseSortValues()
{
	DELETEARRAY(gValues);
}

void TestRadix()
{
	udword Time;
	StartProfile(Time);

		RADIX_SORTER RS;
		const udword* Sorted = RS.Sort(gValues, NB_TO_SORT).GetRanks();

	EndProfile(Time);
	printf("%d (Radix)\n", Time/1024);

	for(udword i=0;i<NB_TO_SORT-1;i++)
		if(gValues[Sorted[i]]>gValues[Sorted[i+1]])
			printf("ERROR!\n");
}

struct RadixInfo
{
	udword			mNb;
	float*			mValues;
	RADIX_SORTER*	mRS;
};

static int gSortingThread(void* user_data)
{
	RadixInfo* tmp = (RadixInfo*)user_data;
	const udword* Sorted = tmp->mRS->Sort(tmp->mValues, tmp->mNb).GetRanks();
	return 0;
}

void TestRadix2()
{
	udword Time;
	StartProfile(Time);

	const udword Offset = NB_TO_SORT/2;

	RADIX_SORTER RS0;
	RadixInfo RI0;
	RI0.mNb		= Offset;
	RI0.mValues	= gValues;
	RI0.mRS		= &RS0;
	IceThread* SortingThread = CreateThread(gSortingThread, &RI0);

	RADIX_SORTER RS1;
	RadixInfo RI1;
	RI1.mNb		= Offset;
	RI1.mValues	= gValues + Offset;
	RI1.mRS		= &RS1;
	gSortingThread(&RI1);

	WaitThread(SortingThread, null);

	const udword* Sorted0 = RS0.GetRanks();
	const udword* Sorted1 = RS1.GetRanks();
	const udword* Last0 = RS0.GetRanks() + Offset;
	const udword* Last1 = RS1.GetRanks() + Offset;

	const float* Values0 = gValues;
	const float* Values1 = gValues + Offset;

	udword i = 0;
	udword* Ranks = new udword[NB_TO_SORT];
	float Value0 = Values0[*Sorted0];
	float Value1 = Values1[*Sorted1];
	while(Sorted0!=Last0 && Sorted1!=Last1)
	{
		if(Value0<Value1)
		{
			while(Sorted0!=Last0 && Values0[*Sorted0]<=Value1)
				Ranks[i++] = *Sorted0++;

			if(Sorted0!=Last0)
				Value0 = Values0[*Sorted0];
		}
		else
		{
			while(Sorted1!=Last1 && Values1[*Sorted1]<=Value0)
				Ranks[i++] = Offset + *Sorted1++;

			if(Sorted1!=Last1)
				Value1 = Values1[*Sorted1];
		}
	}
	while(Sorted0!=Last0)
		Ranks[i++] = *Sorted0++;
	while(Sorted1!=Last1)
		Ranks[i++] = Offset + *Sorted1++;

	EndProfile(Time);
	printf("%d (Radix MT)\n", Time/1024);

	for(udword i=0;i<NB_TO_SORT-1;i++)
		if(gValues[Ranks[i]]>gValues[Ranks[i+1]])
			printf("ERROR!\n");

	DELETEARRAY(Ranks);
}

	struct Key
	{
		float	mValue;
		int		mID;

		inline_	bool	operator==(const Key& p)	const	{ return mValue == p.mValue;	}
		inline_	bool	operator<=(const Key& p)	const	{ return mValue <= p.mValue;	}
		inline_	bool	operator>=(const Key& p)	const	{ return mValue >= p.mValue;	}
		inline_	bool	operator<(const Key& p)		const	{ return mValue < p.mValue;		}
		inline_	bool	operator>(const Key& p)		const	{ return mValue > p.mValue;		}
	};

#include <algorithm>
void TestStdSort()
{
	Key* Values = new Key[NB_TO_SORT];
	for(udword i=0;i<NB_TO_SORT;i++)
	{
		Values[i].mValue = gValues[i];
		Values[i].mID = i;
	}

	udword Time;
	StartProfile(Time);
		std::sort(Values, Values+NB_TO_SORT);
	EndProfile(Time);
	printf("%d (std::sort)\n", Time/1024);

	for(udword i=0;i<NB_TO_SORT-1;i++)
		if(Values[i]>Values[i+1])
			printf("ERROR!\n");

	DELETEARRAY(Values);
}

#include "IntroSort.h"
void TestIntroSort()
{
	Key* Values = new Key[NB_TO_SORT];
	for(udword i=0;i<NB_TO_SORT;i++)
	{
		Values[i].mValue = gValues[i];
		Values[i].mID = i;
	}

	udword Time;
	StartProfile(Time);
		IntroSort<Key> introSorter;
		introSorter.Sort(Values, NB_TO_SORT);
	EndProfile(Time);
	printf("%d (IntroSort)\n", Time/1024);

	for(udword i=0;i<NB_TO_SORT-1;i++)
		if(Values[i]>Values[i+1])
			printf("ERROR!\n");

	DELETEARRAY(Values);
}
