#ifndef _COMMON_QUICKSORT_TPP_
#define _COMMON_QUICKSORT_TPP_

template <class T>
QuickSort<T>::QuickSort(void)
: mlpItemList(0), mlpBlockItems(0)
{
}

template <class T>
QuickSort<T>::~QuickSort()
{
}

template <class T>
void QuickSort<T>::sortItems(Array<T> &arrayItems,SortOptions::SortOrder sortOrder)
{
	if(!arrayItems.size())return;
	mlpItemList=&arrayItems[0];
	if(SortOptions::Ascending==sortOrder)quickSort(0,arrayItems.size()-1);
	else quickSortDescending(0,arrayItems.size()-1);
}

template <class T>
void QuickSort<T>::sortItems(Block<T> &someBlock,SortOptions::SortOrder sortOrder)
{
	if(!someBlock.size())return;
	mlpBlockItems=&someBlock;
	if(SortOptions::Ascending==sortOrder)sortBlockAscending(0,someBlock.size()-1L);
	else sortBlockDescending(0,someBlock.size()-1L);
}

template <class T>
void QuickSort<T>::quickSort(long left,long right)
{
	long tempLeft(left);
	long tempRight(right);
	T tempItem;
	T swapItem;

	tempItem=*((T FAR*)(mlpItemList+((left+right)/2L)));
	do{
		while(*((T FAR*)(mlpItemList+tempLeft))<tempItem&&tempLeft<=right)tempLeft++;
		while(tempItem<*((T FAR*)(mlpItemList+tempRight))&&tempRight>=left)tempRight--;
		if(tempLeft>right)tempLeft--;
		if(tempRight<left)tempRight++;
		if(tempLeft<=tempRight)
		{
			swapItem=*((T FAR*)(mlpItemList+tempLeft));
			*((T FAR*)(mlpItemList+tempLeft))=*((T FAR*)(mlpItemList+tempRight));
			*((T FAR*)(mlpItemList+tempRight))=swapItem;
			tempLeft++;
			tempRight--;
		}
	}while(tempLeft<=tempRight);
	if(left<tempRight)quickSort(left,tempRight);
	if(tempLeft<right)quickSort(tempLeft,right);
}

template <class T>
void QuickSort<T>::quickSortDescending(long left,long right)
{
	long tempLeft(left);
	long tempRight(right);
	T tempItem;
	T swapItem;

	tempItem=*((T FAR*)(mlpItemList+((left+right)/2L)));
	do{
		while(*((T FAR*)(mlpItemList+tempLeft))>tempItem&&tempLeft<=right)tempLeft++;
		while(tempItem>*((T FAR*)(mlpItemList+tempRight))&&tempRight>=left)tempRight--;
		if(tempLeft>right)tempLeft--;
		if(tempRight<left)tempRight++;
		if(tempLeft<=tempRight)
		{
			swapItem=*((T FAR*)(mlpItemList+tempLeft));
			*((T FAR*)(mlpItemList+tempLeft))=*((T FAR*)(mlpItemList+tempRight));
			*((T FAR*)(mlpItemList+tempRight))=swapItem;
			tempLeft++;
			tempRight--;
		}
	}while(tempLeft<=tempRight);
	if(left<tempRight)quickSortDescending(left,tempRight);
	if(tempLeft<right)quickSortDescending(tempLeft,right);
}

template <class T>
void QuickSort<T>::sortBlockAscending(long left,long right)
{
	long tempLeft(left);
	long tempRight(right);
	T tempItem;
	T swapItem;

	tempItem=(*mlpBlockItems)[(left+right)/2L];
	do{
		while((*mlpBlockItems)[tempLeft]<tempItem&&tempLeft<=right)tempLeft++;
		while(tempItem<(*mlpBlockItems)[tempRight]&&tempRight>=left)tempRight--;
		if(tempLeft>right)tempLeft--;
    if(tempRight<left)tempRight++;
		if(tempLeft<=tempRight)
		{
			swapItem=(*mlpBlockItems)[tempLeft];
			(*mlpBlockItems)[tempLeft]=(*mlpBlockItems)[tempRight];
			(*mlpBlockItems)[tempRight]=swapItem;
			tempLeft++;
			tempRight--;
		}
	}while(tempLeft<=tempRight);
	if(left<tempRight)sortBlockAscending(left,tempRight);
	if(tempLeft<right)sortBlockAscending(tempLeft,right);
}

template <class T>
void QuickSort<T>::sortBlockDescending(long left,long right)
{
	long tempLeft(left);
	long tempRight(right);
	T tempItem;
	T swapItem;

	tempItem=(*mlpBlockItems)[(left+right)/2L];
	do{
		while((*mlpBlockItems)[tempLeft]>tempItem&&tempLeft<=right)tempLeft++;
		while(tempItem>(*mlpBlockItems)[tempRight]&&tempRight>=left)tempRight--;
		if(tempLeft>right)tempLeft--;
    if(tempRight<left)tempRight++;
		if(tempLeft<=tempRight)
		{
			swapItem=(*mlpBlockItems)[tempLeft];
			(*mlpBlockItems)[tempLeft]=(*mlpBlockItems)[tempRight];
      (*mlpBlockItems)[tempRight]=swapItem;
			tempLeft++;
			tempRight--;
		}
	}while(tempLeft<=tempRight);
	if(left<tempRight)sortBlockDescending(left,tempRight);
	if(tempLeft<right)sortBlockDescending(tempLeft,right);
}
#endif