#include<iostream>
#include<algorithm>
#include<iomanip>
#include<conio.h>
#include<vector>
#include<string>
using namespace std;
//------------------------------------------------------------------------------------------------
//進程輸入
struct process{
	double ctime;
	double utime;
	double time;
	string name;
};
bool flag(vector<process>& ps,string name0){
	if(ps.size ()==0) return 1;
	for(vector<process>::size_type i=0;i<ps.size ();i++)
       if(ps[i].name == name0) return 0;
	return 1;
}

void creat(vector<process>& ps0,process &p0){
	//cout<<endl;
p1:	cout<<"進程名: ";
	string name0;
    cin>> name0 ;
    if(!flag(ps0,name0)){ cout<<"進程名已經存在！重新輸入："<<endl;goto p1;}
	p0.name =name0;
	cout<<"到達時間(十進制數): ";
	cin>>p0.ctime ;
	cout<<"估計運行時間(十進制數): ";
	cin>>p0.utime ;
	p0.time =0;
	ps0.push_back (p0);
}

void print(vector<process>& ps){
	if(ps.size ()==0){cout<<"無進程"<<endl;return;}
	cout<<setw(12)<<"進程名"<<setw(10)<<"到達時間"<<setw(10)<<"運行時間"<<endl;
	for(vector<process>::size_type i=0;i<ps.size ();i++)
		cout<<setw(12)<<ps[i].name <<setw(10)<<ps[i].ctime<<setw(10)<<ps[i].utime<<endl;
	cout<<endl;
}
//-----------------------------------------------------------------------------------------------
//先來先服務算法

bool compare(const process& x,const process& y){
	return x.ctime <y.ctime ;
}
double time1(vector<process>& ps){
	double x=0;
	for(vector<process>::size_type i=0;i<ps.size ();i++)
	{
		if(i==0) {ps[0].time =ps[0].utime ;	x=x+ps[0].utime+ ps[0].ctime ;}                                                         
		else
		{
			if(x<ps[i].ctime){ps[i].time=ps[i].utime;x=ps[i].ctime+ps[i].utime;}
			else{ps[i].time =x + ps[i].utime -ps[i].ctime ;x=x+ps[i].utime;}
		}
	}
	x=0;
    for(vector<process>::size_type j=0;j<ps.size ();j++)
		x=x+ps[j].time ;
	return (x/ps.size ());	
}

double time2(vector<process>& ps){
	double x=0;
    for(vector<process>::size_type j=0;j<ps.size ();j++)
	     x=x+ps[j].time/ps[j].utime ; 
	return (x/ps.size ());	
}

void printf(vector<process>& ps){
	if(ps.size ()==0){cout<<"無進程"<<endl;return;}
	cout<<setw(12)<<"進程名"<<setw(10)<<"到達時間"<<setw(10)<<"運行時間"<<setw(10)<<"結束時間"<<setw(10)<<"周轉時間"<<endl;
	for(vector<process>::size_type i=0;i<ps.size ();i++)
		cout<<setw(12)<<ps[i].name <<setw(10)<<ps[i].ctime<<setw(10)<<ps[i].utime<<setw(10)<<ps[i].time + ps[i].ctime<<setw(10)<<ps[i].time<<endl;
	cout<<endl;
}

void fc_serve(vector<process>& ps){
	sort(ps.begin (),ps.end (),compare);
	cout<<endl;
    double x,y;
	x=time1(ps);
	y=time2(ps);
	cout<<"      先來先服務算法進程執行順序"<<endl;
	printf(ps);
	cout<<"      先來先服務算法評價："<<endl;
	cout<<"      平均周轉時間為："<<x<<endl;
	cout<<"      平均帶權周轉時間為："<<y<<endl;
}
//-----------------------------------------------------------------------------------------------
//非搶占短進程優先算法

bool compare0(const process& x,const process& y){
	return x.utime <y.utime ;
}

vector<process> select(vector<process>& ps,vector<process>& p){
	vector<process>::iterator iter0=ps.begin ();
	vector<process>::iterator iter1=iter0+1;
	if(ps.size ()==0 || iter1==ps.end ()) return ps;
	while(iter1->ctime ==iter0->ctime ) iter1=iter1+1;
	if(iter1!=iter0+1) sort(iter0,iter1,compare0);
	for( ;iter0!=iter1;++iter0) p.push_back (*iter0);
	double x=0;
	for(vector<process>::size_type i=0;i<p.size ();i++)
	    x=x+p[0].ctime+p[i].utime;
	while(iter1!=ps.end ()){
	    for( ; iter1!=ps.end () && iter1->ctime <=x;++iter1);
	    if(iter0==iter1) {p.push_back (*iter0);x=x+iter0->utime ; ++iter0; ++iter1;}
        else {
		   sort(iter0,iter1,compare0);
		   if(iter1==ps.end ()) {
			    for( ;iter0!=iter1; ++iter0)
			    	p.push_back (*iter0);
			    return p;
		   }
		p.push_back (*iter0);
		x=x+iter0->utime;
		++iter0;
		}
	}	
	return p;
}

void sp_serve(vector<process>& ps){
	sort(ps.begin (),ps.end (),compare);
	vector<process> p;
	p=select(ps,p);
	cout<<endl;
	double x,y;
	x=time1(p);
	y=time2(p);
	cout<<"      非搶占短進程優先算法進程執行順序"<<endl;
	printf(p);
	cout<<"      非搶占短進程優先算法評價："<<endl;
	cout<<"      平均周轉時間為："<<x<<endl;
	cout<<"      平均帶權周轉時間為："<<y<<endl;
}

//-----------------------------------------------------------------------------------------------
int main (){
	process p;
	vector<process> ps;
	char ch;
	cout<<"*******************************************"<<endl;
    cout<<"*                                         *"<<endl;
    cout<<"* 模擬進程調度的時間是以十進制方式實現的。*"<<endl;
	cout<<"*                                         *"<<endl;
	cout<<"*******************************************"<<endl;
	cout<<endl;
	do{
        cout<<"請輸入進程的基本信息："<<endl;
        creat(ps,p);
		cout<<"是否繼續輸入（是'Y'）：";
	    ch =_getch(); 
		cout<<endl;cout<<endl;
	}while(ch=='y' || ch=='Y');
	cout<<endl;cout<<endl;
	cout<<"      輸入的進程信息為："<<endl;
	print(ps);
	do{
	     cout<<endl;
		 cout<< "         ----= 算法菜單=------"<<endl; cout<<endl;
		 cout<< "       s - 非搶占短進程優先算法 "<<endl;
		 cout<< "       f - 先來先服務算法 "<<endl;
		 cout<< "       e - 退出 "<<endl;
		 ch =_getch(); 
		 switch(ch)
		 {
			 case 's' :
				 sp_serve(ps);
				 break;
			 case 'f' :
                 fc_serve(ps);
				 break;
			 case 'e':break;
			 default:
				 cout<<"操作錯誤！"<<endl;
		 }
		 cout<<endl;
	 }while(ch!='e');
	return 0;
}