// jincheng.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream.h>

#ifndef NULL
  #define NULL  0
#endif
#define MAXP 20                                    /*最大进程数*/
//--------------------------------------------------------------------
typedef struct jincheng                            /*进程控制快*/
   {
    char name;                                      /*进程名*/
    int grade;                                      /*优先级*/
    int arrive;                                     /*到达时间*/
    int serve;                                      /*服务时间*/
    int condition;                                  /*状态*/
    struct jincheng *next;                          /*下一进程*/
   }PCB;
//--------------------------------------------------------------------
void jiaohuan_fun(PCB P[MAXP],int i,int j)          /*交换*/
    {
     PCB a;
     a=P[i];P[i]=P[j];P[j]=a;     
    }
//---------------------------------------------------------------------
int input_func(PCB P[MAXP])                         /*输入函数*/
     {
       int i,j,n;
       cout<<"please input the process number:";    /*进程数*/
       cin>>n;
       cout<<"please input the message:"<<endl;     /*进程信息*/
       cout<<"Name Arrivetime Servetime Grade"<<endl;
       for(i=0;i<n;i++)
            {
             cin>>P[i].name;
             cin>>P[i].arrive;
             cin>>P[i].serve;
             cin>>P[i].grade;
             P[i].condition='W';
             P[i].next=NULL;
            }
       for(i=0;i<n-1;i++)                        /*按时间先后排序*/
         for(j=i+1;j<n;j++)
              if(P[i].arrive>P[j].arrive)                  
                jiaohuan_fun(P,i,j);              
       for(i=0;i<n-1;i++)                   /*同时到达按短作业优先*/
         for(j=i+1;j<n;j++)
              if(P[i].arrive==P[j].arrive&&P[i].serve>P[j].serve)                  
                jiaohuan_fun(P,i,j);               
       return n;
     }
//--------------------------------------------------------------------------
void  getnewqueue_fun(PCB P[MAXP],int n,PCB *H[3],int time,int isstop,int d)
{                                         /*获得新就绪队列*/
      static int now=0;
      int i;
      PCB *q,*q1,*q2;
      for(i=now;i<n;i++)                   /*将已提交进程插入就绪队列*/
         if((P[i].arrive)<=time)
           {  now++;
              if(H[P[i].grade]==NULL)
                H[P[i].grade]=&P[i];
              else{q=H[P[i].grade];
                   while(q->next!=NULL)
                     q=q->next;
                   q->next=&P[i];
                  }
           }
   if(isstop==1)                        /*进程已运行完*/
      H[d]=H[d]->next;
   if(isstop==0)                        /*进程未运行完*/
     {if(H[d]->next!=NULL)
        {q1=H[d];
         q2=q1->next;
         while(q2!=NULL&&(q2->arrive<time||(q2->arrive==time&&q2->serve<H[d]->serve)))
            {q1=q1->next;
             q2=q1->next;
            }
         if(q2==NULL)
            {q=H[d];
             q1->next=q;
             H[d]=H[d]->next;
             q->next=NULL;
            }
         else if(q1!=NULL)
            {q=H[d];
             q1->next=q;
             H[d]=H[d]->next;
             q->next=q2;
            }
        }
      }
   }

//------------------------------------------------------------------
void print_fun(PCB *H[3],char diao[10*MAXP],int countd)
{                                             /*输出就绪队列函数*/
int i;
PCB *q;
cout<<diao[countd-1]<<" ";
for(i=0;i<3;i++)
{
  cout<<i<<":";
  q=H[i];
  while(q!=NULL)
     {
         cout<<q->name<<" ";
         q=q->next;
     }
}
}
//------------------------------------------------------------------           
int main(int argc, char* argv[])
{
int n,time=0,isstop,countd=0,i,signNULL,sign,t[3]={1,2,4};
/*
  n进程个数 isstop进程是否结束 countd总调度次数
  signNULL就绪队列是否为空 sign是否有运行的
  t[3]时间片大小
*/
PCB p[MAXP],*H[3];
char diao[10*MAXP];            /*调度序列*/
for(i=0;i<3;i++)
     H[i]=NULL;
n=input_func(p);                /*输入*/
time=p[0].arrive;
isstop=2;
getnewqueue_fun(p,n,H,time,isstop,i); /*获得就绪队列*/

while(H[0]!=NULL||H[1]!=NULL||H[2]!=NULL)
{ sign=0;
   for(i=0;i<3&&sign==0;i++)
     {
         if(H[i]!=NULL)
           {sign=1;
            H[i]->condition='R';
            if(H[i]->serve>t[i])     /*在时间片内运行不完*/
              {H[i]->serve-=t[i];
               time+=t[i];
               H[i]->arrive=time;
               diao[countd]=H[i]->name;
               countd++;
               isstop=0;
               H[i]->condition='W';
               getnewqueue_fun(p,n,H,time,isstop,i);
              }
            else{time+=H[i]->serve;     /*在时间片内运行完*/
                 H[i]->serve=0;
                 H[i]->condition='F';
                 diao[countd]=H[i]->name;
                 countd++;
                 isstop=1;
                 getnewqueue_fun(p,n,H,time,isstop,i);
                 print_fun(H,diao,countd);
                 cout<<endl;
                }
           }
         
      }
signNULL=1;           /*看就绪队列是否为空*/
for(i=0;i<n;i++)
   if(H[i]!=NULL)
     signNULL=0;
if(signNULL)
   {for(sign=1,i=0;i<n&&sign;i++)
        if(p[i].condition=='W')
             {
              time=p[i].arrive;
              sign=0;
             }
    isstop=2;
    getnewqueue_fun(p,n,H,time,isstop,i);
    sign=0;
   }
}//end while
for(i=0;i<countd;i++)    /*输出总调度序列*/
   {cout<<diao[i];
    if(i%20==0&&i!=0)
      cout<<endl;
   }
cout<<endl;
return 0;
}