#include "Sort.h"

//NOTE: type-punned pointer warning can't be fixed without sacrificing speed

exh::Sort::Sort(exh::Particle *_value, unsigned int _value_size)
	: value(_value), value_size(_value_size)
{
}

exh::Sort::~Sort(void)
{
}

exh::Radix::Radix(exh::Particle *_value, unsigned int _value_size)
	:Sort(_value, _value_size)
{
	//memory consumption due to speed optimization
	//(1280 + value_size*2) * 4

//	count = new int[1024]; //256 * 4
//	index = new int[256];

	sortIndex = new int[value_size];
	sortIndex_temp = new int[value_size];

	for(unsigned int i = 0; i < value_size; i++)
	{
		sortIndex[i] = i;
	}
}

exh::Radix::~Radix(void)
{
	delete [] sortIndex;
	delete [] sortIndex_temp;

	/*delete [] count;
	delete [] index;
	count = NULL;
	index = NULL;
	sortIndex_temp = NULL;*/
}

void exh::Radix::radixPass(int *src, int *dst, unsigned int pass)
{
	unsigned int i;
	const unsigned int countOffset = 256 * pass;

	for(i = 0; i < value_size; i++)
	{
		count[countOffset + ((((unsigned int&)value[src[i]].position.z)>>(pass<<3))&0xff)]++;
	}

	if (pass != 3)
	{
		index[0] = 0;
		for(i = 1; i < 256; i++)
		{
			index[i] = index[i-1] + count[countOffset + i-1];
		}

		for(i = 0; i < value_size; i++)
		{
			dst[index[((((unsigned int&)value[src[i]].position.z)>>(pass<<3))&0xff)]++] = src[i];
		}
	}
	else
	{
		//4th pass places negative numbers to the right order in the list
		for(i = 128; i < 256; i++)
		{
			sumOfNegativeValues += count[countOffset + i];
		}

		index[0] = sumOfNegativeValues;
		index[255] = 0;
		index[254] = count[countOffset + 255];
		for(i = 1; i < 127; i++)
		{
			index[i] = index[i-1] + count[countOffset + i-1];
			index[254-i] = index[255-i] + count[countOffset + 255-i];
			index[256-i] += count[countOffset + 256-i];
		}
		index[127] = index[126] + count[countOffset + 126];
		index[128] += count[countOffset + 128];

		for(i = 0; i < value_size; i++)
		{
			unsigned char radix = ((((unsigned int&)value[src[i]].position.z)>>(pass<<3))&0xff);

			if (radix < 127)
			{
				dst[index[radix]++] = src[i];
			}
			else
			{
				dst[--index[radix]] = src[i];
			}
		}
	}
}

void exh::Radix::sort(void)
{
	sumOfNegativeValues = 0;

	for(unsigned int i = 0; i < 1024; i++)
	{
		count[i] = 0;
	}

	radixPass(sortIndex, sortIndex_temp, 0);
	radixPass(sortIndex_temp, sortIndex, 1);
	radixPass(sortIndex, sortIndex_temp, 2);
	radixPass(sortIndex_temp, sortIndex, 3);
}