// Compositor.cpp: implementation of the CTaxis class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "Taxis.h"

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

CTaxis::CTaxis(STUDINFO pStudInfo[],UINT uiTaxisSort)
{
	this->pStudInfo=pStudInfo;

	//根據(jù)排序類別選擇排序方法
	switch(uiTaxisSort)
	{
	case TAXISBY_STUDNUM:
		QuickTaxis();
		break;

	case TAXISBY_AGE:
		HeapTaxis();
		break;

	case TAXISBY_ALLMARK:
		MergeTaxis();
		break;

	default:
		break;
	}
}

CTaxis::~CTaxis()
{

}

void CTaxis::MergeTaxis()
{
	MergeSort(pStudInfo,pStudInfo,0,9);
}

void CTaxis::HeapTaxis()
{
	int i;
	STUDINFO siTemp;

	//把L[1...10]建成大頂堆
	for(i=4;i>=0;i--)
		HeapAdjust(pStudInfo,i,9);

	for(i=9;i>0;--i)
	{
		siTemp=pStudInfo[0];
		pStudInfo[0]=pStudInfo[i];
		pStudInfo[i]=siTemp;

		HeapAdjust(pStudInfo,0,i-1);
	}
}

void CTaxis::QuickTaxis()
{
	QuickSort(pStudInfo,0,9);
}

UINT CTaxis::Partition(STUDINFO L[],UINT uiLow,UINT uiHigh)
{
	UINT uiPivotKey;//樞軸關(guān)鍵字
	STUDINFO siBkUp=L[uiLow];

	uiPivotKey=L[uiLow].uiStudNum;
	while(uiLow<uiHigh)
	{
		while(uiLow<uiHigh && L[uiHigh].uiStudNum>=uiPivotKey)
			uiHigh--;
		L[uiLow]=L[uiHigh];

		while(uiLow<uiHigh && L[uiLow].uiStudNum<=uiPivotKey)
			uiLow++;
		L[uiHigh]=L[uiLow];
	}
	L[uiLow]=siBkUp;

	return uiLow;
}

void CTaxis::QuickSort(STUDINFO L[],int nLow,int nHigh)
{
	UINT uiPivotLoc;

	if(nLow<nHigh)
	{
		uiPivotLoc=Partition(L,nLow,nHigh);
		QuickSort(L,nLow,uiPivotLoc-1); //對低子表遞歸排序
		QuickSort(L,uiPivotLoc+1,nHigh);//對高子表遞歸排序
	}
}

void CTaxis::Merge(STUDINFO SourceL[], STUDINFO DestL[], int i, int m, int n)
{
	UINT j,k;
	UINT l;

	//將SourceL中記錄由小到大的并入DestL
	for(j=m+1,k=i;i<=m && j<=n;++k)
		if((SourceL[i].pCourseInfo->uiMark+SourceL[i].pCourseInfo->pNext->uiMark)>
			(SourceL[j].pCourseInfo->uiMark+SourceL[j].pCourseInfo->pNext->uiMark))
			DestL[k]=SourceL[i++];
		else
			DestL[k]=SourceL[j++];

	if(i<=m)
		for(l=k;l<=n;l++)
			DestL[l]=SourceL[i+l-k];

	if(j<=n)
		for(l=k;l<=n;l++)
			DestL[l]=SourceL[j+l-k];
}

void CTaxis::MergeSort(STUDINFO SourceL[], STUDINFO DestL[], int s, int t)
{
	UINT uiMid;
	STUDINFO DestL2[10];

	if(s==t)
		DestL[s]=SourceL[s];
	else
	{
		uiMid=(s+t)/2;                      //將SourceL[s..t]平分為SourceL[s..uiMid]和SourceL[uiMid+1..t]
		MergeSort(SourceL,DestL2,s,uiMid);  //遞歸的將SourceL[s..uiMid]歸并為有序的DestL2[s..uiMid]
		MergeSort(SourceL,DestL2,uiMid+1,t);//遞歸的將SourceL[uiMid+1..t]歸并為有序的DestL2[uiMid+1..t]
		Merge(DestL2,DestL,s,uiMid,t);      //將DestL2[s..uiMid]和DestL2[uiMid+1..t]歸并到DestL[s..t]
	}
}

void CTaxis::HeapAdjust(STUDINFO L[], int s, int m)
{
	//已知L[s...m]中的記錄除L[s]之外均滿足堆的定義，本函數(shù)調(diào)整H[s],使L[s...m]成為一個(gè)大頂堆
	STUDINFO rc=L[s];
	UINT j;

	for(j=2*s+1;j<=m;j=2*j+1)
	{
		//沿較大值的孩子節(jié)點(diǎn)向下篩選
		if(j<m && L[j].uiAge<L[j+1].uiAge)
			j++;

		if(rc.uiAge>=L[j].uiAge)
			break;

		L[s]=L[j];
		s=j;
	}
	L[s]=rc;
}

void CTaxis::StudInfoJ2I(UINT i,UINT j)
{
	if(i==j)
		return;

	//pStudInfo[i]=pStudInfo[j]
	strcpy(pStudInfo[i].pName,pStudInfo[j].pName);
	pStudInfo[i].uiStudNum=pStudInfo[j].uiStudNum;
	pStudInfo[i].uiAge=pStudInfo[j].uiAge;
	strcpy(pStudInfo[i].pSex,pStudInfo[j].pSex);

	strcpy(pStudInfo[i].pCourseInfo->pCourse,pStudInfo[j].pCourseInfo->pCourse);
	pStudInfo[i].pCourseInfo->uiMark=pStudInfo[j].pCourseInfo->uiMark;
	strcpy(pStudInfo[i].pCourseInfo->pTeacher,pStudInfo[j].pCourseInfo->pTeacher);

	strcpy(pStudInfo[i].pCourseInfo->pNext->pCourse,pStudInfo[j].pCourseInfo->pNext->pCourse);
	pStudInfo[i].pCourseInfo->pNext->uiMark=pStudInfo[j].pCourseInfo->pNext->uiMark;
	strcpy(pStudInfo[i].pCourseInfo->pNext->pTeacher,pStudInfo[j].pCourseInfo->pNext->pTeacher);
}