// 時間片輪轉調度算法
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>

using namespace std;
enum STATUS {RUN,READY,WAIT,FINISH};

struct PCBNode
{		
	int  processID;	          //進程ID
	STATUS  status;	          //進程狀態
	int  priorityNum;	      //優先數
	int  reqTime;             //總的需要運行時間
	int  remainTime;          //剩下需要運行時間
	int  arriveTime;          //進入就緒隊列時間
	int  startTime;           //開始運行時間
	int  finishTime;          //結束運行時間
	int  totalTime;           //周轉時間
    float  weightTotalTime;	  //帶權周轉時間	
};

struct QueueNode 
{
	int ID;          //進程ID
	struct QueueNode * next;   //隊列中下一個進程指針
};

struct LinkQueue
{
	QueueNode *head;//隊首
};

void Fcfs(LinkQueue& Q,int& totalTimeSum, int& weightTotalTimeSum,PCBNode * ProcessTable);
//先來先服務算法
void InitialQueue(LinkQueue& Q,PCBNode * ProcessTable,const int processnum);

void Input(PCBNode * ProcessTable, const int processnum);

int main()
{
	LinkQueue Q;
	Q.head = NULL;
    const int processnum = 16;
	const int Round = 1;
	int totalTimeSum = 0;
	int	WeightTotalTimeSum = 0;
	PCBNode * ProcessTable=new PCBNode[processnum];
	
	Input(ProcessTable, processnum);
	InitialQueue(Q, ProcessTable, processnum);
	Fcfs(Q, totalTimeSum,WeightTotalTimeSum,ProcessTable);
	cout<<"先來先服務的平均周轉時間為:"<<totalTimeSum/processnum<<endl;
	cout<<"先來先服務的平均帶權周轉時間為:"<<WeightTotalTimeSum/processnum<<endl;

	delete [] ProcessTable;

	system("Pause");
	if(getchar()=='y')
		getchar();
	return 0;
}



void Fcfs(LinkQueue& Q, int& totalTimeSum, int& weightTotalTimeSum,PCBNode * ProcessTable)
{
	totalTimeSum = 0;
	weightTotalTimeSum = 0;//平均周轉時間
	QueueNode* p;
	QueueNode* q;
	
	p = Q.head->next;
	if (p !=NULL ) 
	{
		ProcessTable[p->ID].startTime = ProcessTable[p->ID].arriveTime;
		ProcessTable[p->ID].finishTime = ProcessTable[p->ID].arriveTime + ProcessTable[p->ID].reqTime;
	}
	
	for(q=p->next; q!=NULL; q=q->next)
	{
		
		if (ProcessTable[q->ID].arriveTime < ProcessTable[p->ID].finishTime)
		{
			ProcessTable[q->ID].startTime = ProcessTable[p->ID].finishTime;
			ProcessTable[q->ID].finishTime = ProcessTable[p->ID].finishTime + ProcessTable[q->ID].reqTime;
		}
		else//下個進程到達時間較晚
		{
			ProcessTable[q->ID].startTime = ProcessTable[q->ID].arriveTime;
			ProcessTable[q->ID].finishTime = ProcessTable[q->ID].arriveTime + ProcessTable[q->ID].reqTime;
		}
		p = q;
	}
	
	for(q=Q.head->next; q!=NULL; q=q->next)
	{
		ProcessTable[q->ID].totalTime = ProcessTable[q->ID].finishTime - ProcessTable[q->ID].arriveTime;
		ProcessTable[q->ID].weightTotalTime = ProcessTable[q->ID].totalTime/ProcessTable[q->ID].reqTime;		
		totalTimeSum += ProcessTable[q->ID].totalTime;
		weightTotalTimeSum += ProcessTable[q->ID].weightTotalTime;
	}	
	
	int t = 0;
	for(q=Q.head->next; q!=NULL; q=q->next)
	{
		cout<<"*********************"<<endl;
		while ( t<ProcessTable[q->ID].finishTime )
		{
			cout<<"時刻"<<t<<":  進程"<<q->ID<<"活動"<<endl;
			t++;
		}
		if (q->next != NULL)
		{	
			cout<<"時刻"<<t<<":  進程"<<q->ID<<"結束活動,開始下一個進程."<<endl;
			cout<<"進程"<<q->ID<<"的周轉時間為: "<<ProcessTable[q->ID].totalTime<<endl;
			cout<<"進程"<<q->ID<<"的帶權周轉時間為: "<<ProcessTable[q->ID].weightTotalTime<<endl<<endl;
		}
		else
		{
			cout<<"時刻"<<t<<":  進程"<<q->ID<<"結束活動."<<endl<<endl;
			cout<<"進程"<<q->ID<<"的周轉時間為: "<<ProcessTable[q->ID].totalTime<<endl;
			cout<<"進程"<<q->ID<<"的帶權周轉時間為: "<<ProcessTable[q->ID].weightTotalTime<<endl<<endl;			
		}
	}
	cout<<"所有進程結束活動."<<endl<<endl;

	p = Q.head;
	for(q=p->next; q!=NULL; q=q->next)
	{
		delete p;
		p = q;
	}
}

void InitialQueue(LinkQueue& Q, PCBNode * ProcessTable,const int processnum)
{
	//初始化
	
	for (int i=0;i<processnum;i++)
	{
		ProcessTable[i].processID=i;
		ProcessTable[i].reqTime=ProcessTable[i].remainTime;
		ProcessTable[i].finishTime=0;
		ProcessTable[i].startTime=0;	
		ProcessTable[i].status=WAIT;
		ProcessTable[i].totalTime=0;
		ProcessTable[i].weightTotalTime=0;		
	}
	
	Q.head = new QueueNode;
	Q.head->next = NULL;
	QueueNode * p;
	QueueNode * q;
	for (i=0;i<processnum;i++)
	{	
		p = new QueueNode;
		p->ID = i;
		p->next = NULL;
		if (i == 0)
		{
			Q.head->next = p;			
		}
		else
			q->next = p;
		
		q = p;
	}
}


void Input(PCBNode * ProcessTable, const int processnum)
{
	FILE *fp;		//讀入線程的相關內容
	if((fp=fopen("input.txt","r"))==NULL)
	{
		cout<<"can not open file!"<<endl;
		exit(0);
	}		
	for(int i=0;i<processnum;i++)
	{
		fscanf(fp,"%d %d %d",&ProcessTable[i].arriveTime,&ProcessTable[i].remainTime,&ProcessTable[i].priorityNum);
	}
	fclose(fp);
}