/*
	HeapSort.cpp

*/

#include "stdafx.h"
#include "HeapSort.h"
#include <emmintrin.h>

#pragma optimize( "t", on )

static void __stdcall SwapUU(void* p1, void* p2)
{
	char	*c1 = ( char* ) p1, *c2 = ( char* ) p2, cdata;
	size_t	sztRecLength = sizeof( SortRecStruct );
	__m128i	XmmTemp;
	DWORD	dwTemp;

	while( sztRecLength >= 16 )
	{
		XmmTemp = _mm_loadu_si128( ( __m128i* ) c1 );
		_mm_storeu_si128( ( __m128i* ) c1, _mm_loadu_si128( ( __m128i* ) c2 ) );
		_mm_storeu_si128( ( __m128i* ) c2, XmmTemp );
		c1 += 16; c2 += 16; sztRecLength -= 16;
	}
	if( sztRecLength >= 8 )
	{
		XmmTemp = _mm_loadl_epi64( ( __m128i* ) c1 );
		_mm_storel_epi64( ( __m128i* ) c1, _mm_loadl_epi64( ( __m128i* ) c2 ) );
		_mm_storel_epi64( ( __m128i* ) c2, XmmTemp );
		c1 += 8; c2 += 8; sztRecLength -= 8;
	}
	if( sztRecLength >= 4 )
	{
		dwTemp = *( ( DWORD* ) c1 );
		*( ( int* ) c1 ) = *( ( DWORD* ) c2 );
		*( ( DWORD* ) c2 ) = dwTemp;
		c1 += 4; c2 += 4; sztRecLength -=4;
	}
	while( sztRecLength-- )
	{
		cdata = *c1; *c1++ = *c2; *c2++ = cdata;
	}
}

static void __stdcall DualSort(SortRecStruct* p1, SortRecStruct* p2)
{
	if( p1->Key > p2->Key )
		SwapUU( p1, p2 );
}

static void ShiftDownAB(SortRecStruct* pArray, size_t pTop, size_t pBtm)
{
	size_t	root, child, unswap;

	//input:  end represents the limit of how far down the heap to sift.
	root = pTop;
	while( root * 2 + 1 < pBtm )	// (While the root has at least one child)
	{
		child = root * 2 + 1;	// (root*2 + 1 points to the left child)
		unswap = root;	// (keeps track of child to swap with)
		// (check if root is smaller than left child)
		if( pArray[ unswap ].Key < pArray[ child ].Key )
			unswap = child;
		// (check if right child exists, and if it's bigger than what we're currently swapping with)
		//if( child + 1 < pBtm && pArray[ unswap ] < pArray[ child + 1 ] )
		if( ( child < pBtm ) && ( pArray[ unswap ].Key < pArray[ child + 1 ].Key ) )
			unswap = child + 1;
		//(check if we need to swap at all)
		if( unswap != root )
		{
			SwapUU( &pArray[ root ], &pArray[ unswap ] );
			root = unswap;	// (repeat to continue sifting down the child now)
		}
		else
			break;
	}
}

static void siftUp(SortRecStruct *pArray, size_t pTop, size_t pBtm)
{
	size_t	child, parent;

	// input:  start represents the limit of how far up the heap to sift.
	// end is the node to sift up.
	child = pBtm;
	while( child > pTop )
	{
		//parent = ( size_t ) floor( ( child - 1 ) / 2.0 );
		parent = ( child - 1 ) / 2;
		if( pArray[ parent ].Key < pArray[ child ].Key )	// then (out of max-heap order)
		{
			SwapUU( &pArray[ parent ], &pArray[ child ] );
			child = parent;	// (repeat to continue sifting up the parent now)
		}
		else
			return;
	}
}

static void HeapifyA(SortRecStruct* pArray, size_t pRecCount)
{
	size_t		start;

	//(start is assigned the index in a of the last parent node)
	/*
	if( pRecCount & 1 )
		start = ( pRecCount ) / 2;
	else
		start = ( pRecCount - 1 ) / 2;
	*/
	start = pRecCount / 2 + ( pRecCount & 1 );
	//while( start >= 0 )
	while( start != ( size_t ) -1 )
	{
		//( sift down the node at index start to the proper place such that all nodes below
		//the start index are in heap order )
         ShiftDownAB( pArray, start, pRecCount - 1 );
         start = start - 1;
	}
	//(after sifting down the root all nodes/elements are in heap order)
}

DWORD __stdcall HeapSortA(SortRecStruct* pArray, size_t pRecCount, bool* pAbort)
{
	size_t	 sztPtr;

	if( pRecCount > 1 )
	{
		HeapifyA( pArray, pRecCount );
		if( *pAbort ) return 1223;
		sztPtr = ( int ) ( pRecCount - 1 );	// in languages with zero-based arrays the children are 2*i+1 and 2*i+2
		while( sztPtr > 0 )
		{
			//(swap the root(maximum value) of the heap with the last element of the heap)
			SwapUU( &pArray[ sztPtr ], &pArray[ 0 ] );
			//(decrease the size of the heap by one so that the previous max value will stay in its proper placement) 
			sztPtr = sztPtr - 1;
			//(put the heap back in max-heap order)
			ShiftDownAB( pArray, 0, sztPtr );
			if( *pAbort ) return 1223;
		}
		DualSort( pArray, &pArray[ 1 ] );
		DualSort( &pArray[ pRecCount - 2 ], &pArray[ pRecCount - 1 ] );
	}
	return 0;
}

static void heapifyB(SortRecStruct* pArray, size_t count)
{
	size_t	sztPtr;
	//(sztPtr is assigned the index of the first (left) child of the root)

	sztPtr = 1;
	while( sztPtr < count )
	{
		//(sift up the node at index end to the proper place such that all nodes above the end index are in heap order)
		siftUp( pArray, 0, sztPtr );
		sztPtr = sztPtr + 1;
	}
	// (after sifting up the last node all nodes are in heap order)
}

DWORD __stdcall HeapSortB(SortRecStruct* pArray, size_t pRecCount, bool* pAbort)
{
	size_t	 sztPtr;

	if( pRecCount > 1 )
	{
		heapifyB( pArray, pRecCount );
		if( *pAbort ) return 1223;
		sztPtr = ( int ) ( pRecCount - 1 );	// in languages with zero-based arrays the children are 2*i+1 and 2*i+2
		while( sztPtr > 0 )
		{
			//(swap the root(maximum value) of the heap with the last element of the heap)
			SwapUU( &pArray[ sztPtr ], &pArray[ 0 ] );
			//(decrease the size of the heap by one so that the previous max value will stay in its proper placement) 
			sztPtr = sztPtr - 1;
			//(put the heap back in max-heap order)
			ShiftDownAB( pArray, 0, sztPtr );
			if( *pAbort ) return 1223;
		}
		DualSort( pArray, &pArray[ 1 ] );
		DualSort( &pArray[ pRecCount - 2 ], &pArray[ pRecCount - 1 ] );
	}
	return 0;
}

static void __stdcall ShiftDownC(SortRecStruct* pArray, size_t pRoot, size_t pBtm)
{
	size_t	sztChild;

	sztChild = pRoot * 2;
	while( sztChild <= pBtm )
	{
		if( sztChild != pBtm && pArray[ sztChild ].Key <= pArray[ sztChild + 1 ].Key )
			sztChild++;
		//
		if( pArray[ sztChild ].Key > pArray[ pRoot ].Key  )
		{
			SwapUU( &pArray[ sztChild ], &pArray[ pRoot ] );
			pRoot = sztChild; sztChild = pRoot * 2;
		}
		else
		{
			break;	// = return
		}
	}
}

static DWORD __stdcall HeapSortCR(SortRecStruct* pArray, size_t pTop, size_t pBtm, bool* pAbort)
{
	size_t		sztPtr, sztCount;
	SortRecStruct	*nNewArray;

	sztCount = pBtm - pTop + 1;
	if( sztCount >= 2 )
	{
		nNewArray = &pArray[ pTop ];
		for( sztPtr = sztCount / 2; sztPtr != ( size_t ) -1; sztPtr-- )
		{
			//ShiftDownC( nNewArray, sztPtr, sztCount - 1 );
			ShiftDownC( nNewArray, sztPtr, pBtm );
		}
		if( *pAbort ) return 1223;
		//
		for( sztPtr = sztCount - 1; sztPtr >= 1; sztPtr-- )
		{
			SwapUU( &nNewArray[ 0 ], &nNewArray[ sztPtr ] );
			ShiftDownC( nNewArray, 0, sztPtr - 1 );
			if( *pAbort ) return 1223;
		}
	}
	return 0;
}

DWORD __stdcall HeapSortC(SortRecStruct* pArray, size_t pRecCount, bool* pAbort)
{
	return HeapSortCR( pArray, 0, pRecCount - 1, pAbort );
}