// DDSF.cpp : Defines the entry point for the console application.
//#include "stdafx.h"
#include "stdio.h"
#include "stdlib.h"
#include "iostream"
#include "string"
#include "windows.h"
using namespace std;
int time=0;
struct pcb
{
	int arrive_time;
	int service_time;
	int run_time;
	string name;
	int complete_time;
	bool finished;
	pcb *prior;
	pcb *next;
};
pcb *application_pcb,*ready_pcb,*complete_pcb,*runing_pcb;
//------------------------------------------------------------------------------------------------
pcb *init_head_pcb()
{
	pcb *head_pcb;
	head_pcb=new pcb;
	head_pcb->name="";
	head_pcb->arrive_time=-1;
	head_pcb->service_time=-1;
	head_pcb->complete_time=-1;
	head_pcb->run_time=0;
	head_pcb->finished=false;
	head_pcb->prior=NULL;
	head_pcb->next=NULL;
	return head_pcb;
}
//------------------------------------------------------------------------------------------------
void init_pcb(string name,int arrive_time,int service_time)
{
	pcb *pcb_init,*rear_init;
	pcb_init=new pcb;
	pcb_init->name=name;
	pcb_init->arrive_time=arrive_time;
	pcb_init->service_time=service_time;
	pcb_init->run_time=0;
	pcb_init->complete_time=4000;
	rear_init=application_pcb;
    while(rear_init->next!=NULL)
		rear_init=rear_init->next;
    pcb_init->prior=rear_init;
	rear_init->next=pcb_init;
	pcb_init->next=NULL;
	
}
//------------------------------------------------------------------------------------------------
void init_job()
{

	init_pcb("A",0,4);
	init_pcb("t",0,7);
	init_pcb("B",1,3);
	init_pcb("C",2,5);
	init_pcb("D",3,2);
	init_pcb("E",4,4);
}
//------------------------------------------------------------------------------------------------
void suanfa(string flag)
{
	void show();
	void show_ready();
	pcb *rear_fcfs;
	int flag_int=1;
	int jump=1;
	int flag_int1=0;
	time=0;
	while(application_pcb->next!=NULL||ready_pcb->next!=NULL)
	{
//		for(int i=0;i<999999999;i++)
//			;
		rear_fcfs=application_pcb;
		while(rear_fcfs->next!=NULL)
		{
			rear_fcfs=rear_fcfs->next;
			if(rear_fcfs->arrive_time<=time)
			{
				pcb *rear_ready_fcfs,*rear_temp;
				rear_temp=rear_fcfs;

				 rear_fcfs=rear_fcfs->prior;                       //  關鍵處理 

				rear_ready_fcfs=ready_pcb;
				while(rear_ready_fcfs->next!=NULL)
				{
					rear_ready_fcfs=rear_ready_fcfs->next;
				}
				rear_ready_fcfs->next=rear_temp;
				if(rear_temp->next==NULL)
					rear_temp->prior->next=NULL;
				else
				{
					rear_temp->prior->next=rear_temp->next;
					rear_temp->next->prior=rear_temp->prior;
				}
				rear_temp->prior=rear_ready_fcfs;
				rear_temp->next=NULL;
			}
		}
		if(ready_pcb->next==NULL)
		{
			runing_pcb=NULL;
			time++;
		}
		else
		{
			if(flag=="fcfs"||flag=="FCFS")
			{
				runing_pcb=ready_pcb->next;					
			}
			else if(flag=="sjf"||flag=="SJF")
			{
				pcb *rear_sjf;
				if(flag_int==1)
				{
					rear_sjf=ready_pcb;
					runing_pcb=rear_sjf->next;
					while(rear_sjf->next!=NULL)
					{
						rear_sjf=rear_sjf->next;
						if(rear_sjf->service_time<runing_pcb->service_time)
							runing_pcb=rear_sjf;
					}
				}
				flag_int=0;
				
			}
			else if(flag=="timeover"||flag=="TIMEOVER")
			{
				if(time==0)
				{
					cout<<"輸入時間片：";
					cin>>jump;
					runing_pcb=ready_pcb;
				}
				if(runing_pcb->next==NULL)
					runing_pcb=ready_pcb;
				runing_pcb=runing_pcb->next;
				
				              
			}
			flag_int1=0;
		    for(int i=0;i<jump;i++)
			{
				if(flag_int1==0)
				    runing_pcb->run_time=runing_pcb->run_time+1;
				if(runing_pcb->run_time==runing_pcb->service_time)
				{
					pcb *rear_complete,*temp_complete;
					rear_complete=complete_pcb;
					temp_complete=runing_pcb;
					runing_pcb=runing_pcb->prior;
					while(rear_complete->next!=NULL)
						rear_complete=rear_complete->next;
					rear_complete->next=temp_complete;
					if(temp_complete->next==NULL)
						temp_complete->prior->next=NULL;
					else
					{
						temp_complete->prior->next=temp_complete->next;
						temp_complete->next->prior=temp_complete->prior;
					}
					temp_complete->prior=rear_complete;
					temp_complete->next=NULL;
					temp_complete->complete_time=time+1;
					//-------------------------------------------------					
					flag_int=1;
					flag_int1=1;
				}
			
				
				system("cls");
				cout<<"^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\n\n";
				cout<<"\t\tos_算法調度程序"<<endl<<endl;
				cout<<"正在運行的程序：";
				cout<<runing_pcb->name<<"\t已經運行時間：";
				cout<<runing_pcb->run_time;
				
				cout<<"\ttime\t"<<(time+1)<<endl;
				cout<<"--------------------------------------"<<endl<<endl;
				show_ready();
				cout<<"--------------------------------------"<<endl;
				cout<<"已經完成的進程："<<endl;
				
				cout<<"--------------------------------------"<<endl<<endl;
				show();
				time=time+1;
				for(int i=0;i<999999999;i++)
			          ;
			}
			
		}
	}
}
//------------------------------------------------------------------------------------------------
//------------------------------------------------------------------------------------------------
void contorl()
{
	void show();
	string command;
	cout<<"選擇算法： ";
	cin>>command;
	getchar();
	while(command!="exit")
	{
		suanfa(command);
		cout<<"選擇算法： ";
		cin>>command;
		getchar();
	}
}
//------------------------------------------------------------------------------------------------
void show()
{
	
	pcb *rear_show;
	rear_show=complete_pcb;
	int trans_time;
	float title=0.0;
	float title1=0.0;
	int count=0;
	float average_t,average_h;
	float complete_trans_time;                                                   // 帶權周轉時間
	cout<<"進程"<<"  "<<"到達"<<"   "<<"服務"<<"   "<<"完成"<<"         周轉"<<"  帶權周轉"<<endl;
	while(rear_show->next!=NULL)
	{
		
		rear_show=rear_show->next;
		trans_time=rear_show->complete_time-rear_show->arrive_time;
		complete_trans_time=(float)trans_time/rear_show->service_time;
		cout<<rear_show->name<<"      "<<rear_show->arrive_time<<"\t"<<rear_show->service_time<<"\t";
		cout<<rear_show->complete_time<<"\t  "<<trans_time<<"\t "<<complete_trans_time<<endl;
		title=title+trans_time;
		title1=title1+complete_trans_time;
		count++;
	}
	average_t=(float)title/count;
	average_h=title1/count;
	cout<<"average_t\t"<<average_t<<endl;
	cout<<"average_h\t"<<average_h<<endl;
}
//------------------------------------------------------------------------------------------------
void show_ready()
{
	
	pcb *rear_show;
	rear_show=ready_pcb;
	int trans_time;
	float complete_trans_time;                                                   // 帶權周轉時間
	cout<<"進程"<<"  "<<"到達"<<"   "<<"服務"<<"   "<<"已經運行"<<endl;
	while(rear_show->next!=NULL)
	{
		
		rear_show=rear_show->next;
		trans_time=rear_show->complete_time-rear_show->arrive_time;
		complete_trans_time=(float)trans_time/rear_show->service_time;
		cout<<rear_show->name<<"      "<<rear_show->arrive_time<<"\t"<<rear_show->service_time<<"\t";
	cout<<rear_show->run_time<<endl;
	}
}
//------------------------------------------------------------------------------------------------
int main()
{
	system("color 6a");
	application_pcb=init_head_pcb();
	ready_pcb=init_head_pcb();
	complete_pcb=init_head_pcb();
	init_job();
	contorl();
	
	return 0;
}