/* algo3-12.c 銀行業務模擬。實現算法3.6、3.7的程序 */
 #define Qu 4 /* 客戶隊列數 */
 #define Khjg 5 /* 兩相鄰到達的客戶的時間間隔最大值 */
 #define Blsj 30 /* 每個客戶辦理業務的時間最大值 */
 #include"c1.h"

 typedef struct /* 定義ElemType為結構體類型 */
 {
   int OccurTime; /* 事件發生時刻 */
   int NType; /* 事件類型，Qu表示到達事件,0至Qu-1表示Qu個窗口的離開事件 */
 }Event,ElemType; /* 事件類型，有序鏈表LinkList的數據元素類型 */

 #include"c2-5.h"
 typedef LinkList EventList; /* 事件鏈表類型，定義為有序鏈表 */
 #include"bo2-6.c" /* 使用已有的鏈表基本操作 */

 typedef struct
 {
   int ArrivalTime; /* 到達時刻 */
   int Duration; /* 辦理事務所需時間 */
 }QElemType; /* 定義QElemType(隊列的數據元素類型)為結構體類型; */

 #include"c3-2.h"
 #include"bo3-2.c" /* 使用已有的隊列基本操作 */

 /* 程序中用到的主要變量(全局)。算法3.7 */
 EventList ev; /* 事件表 */
 Event en; /* 事件 */
 Event et; /* 臨時變量 */
 LinkQueue q[Qu]; /* Qu個客戶隊列 */
 QElemType customer; /* 客戶記錄 */
 int TotalTime=0,CustomerNum=0; /* 累計客戶逗留時間,客戶數(初值為0) */
 int CloseTime; /* 銀行營業時間(單位是分) */

 int cmp(Event a,Event b)
 { /* 依事件a的發生時刻<、=或>事件b的發生時刻分別返回-1、0或1 */
   if(a.OccurTime==b.OccurTime)
     return 0;
   else
     return (a.OccurTime-b.OccurTime)/abs(a.OccurTime-b.OccurTime);
 }

 void OpenForDay()
 { /* 初始化操作 */
   int i;
   InitList(&ev); /* 初始化事件鏈表為空 */
   en.OccurTime=0; /* 設定第一個客戶到達事件 */
   en.NType=Qu; /* 到達 */
   OrderInsert(&ev,en,cmp); /* 插入事件表 */
   for(i=0;i<Qu;++i) /* 置空隊列 */
     InitQueue(&q[i]);
 }

 void Random(int *d,int *i)
 {
   *d=rand()%Blsj+1; /* 1到Blsj之間的隨機數 */
   *i=rand()%Khjg+1; /* 1到Khjg之間的隨機數 */
 }

 int Minimum(LinkQueue Q[]) /* 返回最短隊列的序號 */
 {
   int l[Qu];
   int i,k;
   for(i=0;i<Qu;i++)
     l[i]=QueueLength(Q[i]);
   k=0;
   for(i=1;i<Qu;i++)
     if(l[i]<l[0])
     {
       l[0]=l[i];
       k=i;
     }
   return k;
 }

 void CustomerArrived()
 { /* 處理客戶到達事件，en.NType=Qu */
   QElemType f;
   int durtime,intertime,i;
   ++CustomerNum;
   Random(&durtime,&intertime); /* 生成隨機數 */
   et.OccurTime=en.OccurTime+intertime; /* 下一客戶到達時刻 */
   et.NType=Qu; /* 隊列中只有一個客戶到達事件 */
   if(et.OccurTime<CloseTime) /* 銀行尚未關門，插入事件表 */
     OrderInsert(&ev,et,cmp);
   i=Minimum(q); /* 求長度最短隊列的序號,等長為最小的序號 */
   f.ArrivalTime=en.OccurTime;
   f.Duration=durtime;
   EnQueue(&q[i],f);
   if(QueueLength(q[i])==1)
   {
     et.OccurTime=en.OccurTime+durtime;
     et.NType=i;
     OrderInsert(&ev,et,cmp); /* 設定第i隊列的一個離開事件并插入事件表 */
   }
 }

 void CustomerDeparture()
 { /* 處理客戶離開事件，en.NTyPe<Qu */
   int i;
   i=en.NType;
   DeQueue(&q[i],&customer); /* 刪除第i隊列的排頭客戶 */
   TotalTime+=en.OccurTime-customer.ArrivalTime; /* 累計客戶逗留時間 */
   if(!QueueEmpty(q[i]))
   { /* 設定第i隊列的一個離開事件并插入事件表 */
     GetHead_Q(q[i],&customer);
     et.OccurTime=en.OccurTime+customer.Duration;
     et.NType=i;
     OrderInsert(&ev,et,cmp);
   }
 }

 void Bank_Simulation()
 {
   Link p;
   OpenForDay(); /* 初始化 */
   while(!ListEmpty(ev))
   {
     DelFirst(&ev,GetHead(ev),&p);
     en.OccurTime=GetCurElem(p).OccurTime;
     en.NType=GetCurElem(p).NType;
     if(en.NType==Qu)
       CustomerArrived(); /* 處理客戶到達事件 */
     else
       CustomerDeparture(); /* 處理客戶離開事件 */
   } /* 計算并輸出平均逗留時間 */
   printf("顧客總數:%d, 所有顧客共耗時:%d分鐘, 平均每人耗時: %d分鐘\n",CustomerNum,TotalTime,TotalTime/CustomerNum);
 }

 void main()
 {
   printf("請輸入銀行營業時間長度(單位:分)\n");
   scanf("%d",&CloseTime);
   Bank_Simulation();
 }