/***************************************************************************
*                                                                          *
*  Copyright (C) Golaem S.A.  All Rights Reserved.                         *
*                                                                          *
***************************************************************************/

#pragma once

#include <stdint.h>

namespace glm
{
	/*
	* Radix Sort
	*
	* For more details, refer to the following discussions:
	* - http://codercorner.com/RadixSortRevisited.htm
	* - http://stereopsis.com/radix.html
	*/

	/*
	* \brief Sort integer values in an array using a Radix Sort
	* \param values The array to sort
	* \param size The size of values array
	* \param signedValues Flag indicating if negative values must be handled
	* \return A new allocated array containing the matching index between input and sorted arrays (the 1st sorted value is in input array at position result[0], and so on)
	*/
	template< class Integer > 
	size_t* radixSortInteger( const Integer* values, size_t valuesCount, bool signedValues ) ;

	/*
	* \brief Sort integer values in an array using a Radix Sort. Unlike radixSortInteger, it also sorts the input structure
	* \param values The array to sort
	* \param size The size of values array
	* \param signedValues Flag indicating if negative values must be handled
	*/
	template< class Integer > 
	void radixSortIntegerSelf( Integer* values, size_t valuesCount, bool signedValues ) ;

	template< class Integer >
	void radixSortFreeOutputBuffer( Integer*& radixSortOuput )
	{
		GLM_FREE( radixSortOuput,  glm::MemoryStatIds::GolaemShared);
	}

	//------------------------------------------------------------
	// radixSortInteger
	//------------------------------------------------------------
	template< class Integer >
	inline size_t* 
		radixSortInteger( const Integer* values, size_t valuesCount, bool signedValues )
	{
		// Init data
		size_t negativeValuesCount( 0 ) ;
		size_t radixCount( sizeof( Integer ) ) ;

		size_t* offset = GLM_ALLOC_CAST(size_t*, sizeof(size_t) * 256, offset, glm::MemoryStatIds::GolaemShared)
		GLM_ASSERT( offset != NULL );

		size_t* counters = GLM_ALLOC_CAST(size_t*, sizeof(size_t) * 256 * radixCount, counters, glm::MemoryStatIds::GolaemShared)
		GLM_ASSERT( counters != NULL );
		memset(counters, 0, sizeof(size_t) * 256 * radixCount);

		size_t* indexMap = GLM_ALLOC_CAST(size_t*, sizeof(size_t) * valuesCount, indexMap, glm::MemoryStatIds::GolaemShared)
		GLM_ASSERT( indexMap != NULL );

		for( size_t i = 0 ; i < valuesCount ; ++i )
		{
			indexMap[i] = i ;
		}

		size_t* indexMapTmp = GLM_ALLOC_CAST(size_t*, sizeof(size_t) * valuesCount, indexMapTmp, glm::MemoryStatIds::GolaemShared)
		GLM_ASSERT( indexMapTmp != NULL );

		size_t* indexMapSwap = NULL;

		// Create histogram
		const uint8_t* radix( (uint8_t*)values ) ;
		const uint8_t* radixEnd( (uint8_t*)( &( values[valuesCount] ) ) ) ;
		while( radix < radixEnd )
		{
			for( size_t p = 0 ; p < radixCount ; ++p )
			{
				counters[p*256 + *radix++]++ ;
			}
		}

		// Count negative values, e.g. count values with first bit of MSB (last radix) set
		if( signedValues )
		{
			const size_t* counter( &( counters[((radixCount-1)*256)+128] ) ) ;
			const size_t* counterEnd( &( counters[radixCount*256] ) ) ;
			while( counter < counterEnd )
			{
				negativeValuesCount += *counter++ ;
			}
		}

		// Process a sort pass for each radix
		for( size_t p = 0 ; p < radixCount ; ++p )
		{
			// Check if pass on currrent radix is useless (e.g. if all radix are equals to the same value)
			// We first get the radix of the the first value to sort corresponding to current pass 'p'
			// If the number of radix counted is equal to the total number of input values, them this pass is useless
			const size_t* currentCounter( &( counters[p*256] ) ) ;
			const uint8_t* currentRadix( (uint8_t*)values + p ) ;
			if( currentCounter[*currentRadix] != valuesCount )
			{
				// Create offsets
				if( ( p == ( radixCount - 1 ) ) && signedValues )
				{
					// A specific treatment has to be done on last pass (conecrning MSB) to handle negative numbers
					// Negative numbers are in the right order, but they have to be 'slided' in front position
					offset[0] = negativeValuesCount ;
					for( size_t i = 1 ; i < 128 ; ++i )
					{
						offset[i] = offset[i-1] + currentCounter[i-1] ;
					}
					offset[128] = 0 ;
					for( size_t i = 129 ; i < 256 ; ++i )
					{
						offset[i] = offset[i-1] + currentCounter[i-1] ;
					}
				}
				else
				{
					offset[0] = 0 ;
					for( size_t i = 1 ; i < 256 ; ++i )
					{
						offset[i] = offset[i-1] + currentCounter[i-1] ;
					}
				}

				// Perform radix sort
				size_t currentId ;
				for( size_t i = 0 ; i < valuesCount ; ++i )
				{
					currentId = indexMap[i] ;
					indexMapTmp[offset[currentRadix[currentId*radixCount]]++] = currentId ;
				}

				// Swap index map pointers for next pass
				indexMapSwap = indexMap ;
				indexMap = indexMapTmp ;
				indexMapTmp = indexMapSwap ;
			}
		}

		// Clear data
		GLM_FREE( offset,  glm::MemoryStatIds::GolaemShared);
		GLM_FREE( counters,  glm::MemoryStatIds::GolaemShared);
		GLM_FREE( indexMapTmp,  glm::MemoryStatIds::GolaemShared);
		indexMapSwap = NULL;

		return indexMap ;
	}

	//------------------------------------------------------------
	// radixSortIntegerSelf
	//------------------------------------------------------------
	template< class Integer >
	inline void radixSortIntegerSelf( Integer* values, size_t valuesCount, bool signedValues )
	{
		size_t* sortedIndexes = radixSortInteger<Integer>(values, valuesCount, signedValues);

		Integer* oldValues = GLM_ALLOC_CAST(Integer*, sizeof(Integer) * valuesCount, oldValues, glm::MemoryStatIds::GolaemShared)
		GLM_ASSERT( oldValues != NULL );
		memcpy(oldValues, values, sizeof(Integer) * valuesCount );

		for(size_t index = 0; index < valuesCount; ++index)
		{
			size_t newIndex = sortedIndexes[index];
			values[index] = oldValues[newIndex];
		}
		GLM_FREE( oldValues,  glm::MemoryStatIds::GolaemShared);

		radixSortFreeOutputBuffer(sortedIndexes);
	}
}
