/*
	MinMaxSort.cpp
*/

#include "stdafx.h"
#include "MinMaxSort.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 int __stdcall MinMaxSortAR(SortRecStruct* pArray, size_t pTop, size_t pBtm, bool* pAbort)
{
	size_t	sztMaxPtr, sztMinPtr, sztScan;

	while( pTop < pBtm )
	{
		sztMinPtr = sztMaxPtr = pBtm; sztScan = pTop;
		do
		{
			if( pArray[ sztScan ].Key > pArray[ sztMaxPtr ].Key )
				sztMaxPtr = sztScan;
			if( pArray[ sztScan ].Key < pArray[ sztMinPtr ].Key )
				sztMinPtr = sztScan;
			sztScan++;
		}
		while( sztScan < pBtm );
		SwapUU( &pArray[ sztMaxPtr ], &pArray[ pBtm ] );
		if( sztMinPtr == pBtm )
			sztMinPtr = sztMaxPtr;
		pBtm--;
		SwapUU( &pArray[ sztMinPtr ], &pArray[ pTop++ ] );
		if( *pAbort ) return 1223;
	}
	return 0;
}

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

static DWORD __stdcall MinMaxSortBR(SortRecStruct* pTop, SortRecStruct* pBtm, bool* pAbort)
{
	SortRecStruct	*RecMaxPtr, *RecMinPtr, *RecScan;

	while( pTop < pBtm )
	{
		RecMinPtr = RecMaxPtr = pBtm; RecScan = pTop;
		do
		{
			if( RecScan->Key > RecMaxPtr->Key )
				RecMaxPtr = RecScan;
			if( RecScan->Key < RecMinPtr->Key )
				RecMinPtr = RecScan;
			RecScan++;
		}
		while( RecScan < pBtm );
		SwapUU( RecMaxPtr, pBtm );
		if( RecMinPtr == pBtm )
			RecMinPtr = RecMaxPtr;
		pBtm--;
		SwapUU( RecMinPtr, pTop++ );
		if( *pAbort ) return 1223;
	}
	return 0;
}

DWORD __stdcall MinMaxSortB(SortRecStruct* pArray, size_t pRecCount, bool* pAbort)
{
	return MinMaxSortBR( pArray, &pArray[ pRecCount - 1 ], pAbort );
}

static DWORD __stdcall MinMaxSortCR(SortRecStruct* pTop, SortRecStruct* pBtm, bool* pAbort)
{
	SortRecStruct	*RecMaxPtr, *RecMinPtr, *RecScan;
	DWORD	MaxKeyData, MinKeyData;

	while( pTop < pBtm )
	{
		MinKeyData = MaxKeyData = pBtm->Key; RecMinPtr = RecMaxPtr = pBtm; RecScan = pTop;
		do
		{
			if( RecScan->Key > MaxKeyData )
			{
				MaxKeyData = RecScan->Key; RecMaxPtr = RecScan;
			}
			if( RecScan->Key < MinKeyData )
			{
				MinKeyData = RecScan->Key; RecMinPtr = RecScan;
			}
			RecScan++;
		}
		while( RecScan < pBtm );
		SwapUU( RecMaxPtr, pBtm );
		if( RecMinPtr == pBtm )
			RecMinPtr = RecMaxPtr;
		pBtm--;
		SwapUU( RecMinPtr, pTop++ );
		if( *pAbort ) return 1223;
	}
	return 0;
}

DWORD __stdcall MinMaxSortC(SortRecStruct* pArray, size_t pRecCount, bool* pAbort)
{
	return MinMaxSortCR( pArray, &pArray[ pRecCount - 1 ], pAbort );
}