/*《數據結構》清華大學的，藍皮（c語言篇）65頁
*/
/*模擬銀行業務，計算客戶平均逗留時間
*/
#include<stdio.h>
#include<stdlib.h>
#include<time.h>//srand()用到
typedef struct{
    int OccurTime;
    int NType;
}Event,ElemType;
typedef struct LNode{
    ElemType en;
    struct LNode *next;
}LNode;
typedef struct{
    int ArrivalTime;
    int Duration;
}QElemType;
typedef struct QNode
{
    QElemType data;
    struct QNode *next;
}QNode;
typedef struct{
    QNode * front;
    QNode * rear;
}LinkQueue;
LNode * ev;/*事件表*/
Event en;/*事件*/
LinkQueue q[5];
QElemType customer;/*客戶記錄*/
int TotalTime,CustomerNum;
int CloseTime;
int ListEmpty(LNode *ev)/*判斷是否為空*/
{
    if(ev->next==NULL)
        return 1;
    return 0;
}
void GetCurElem(LNode *ev)
{
    en.OccurTime=(ev->next->en).OccurTime;
    en.NType=(ev->next->en).NType;
}
void DelFirst(LNode *ev)
{
    ev=ev->next->next;
}
int cmp(Event *a,Event *b)
{
    int m=(*a).OccurTime-(*b).OccurTime;
    if(m==0)
        return 0;
    if(m>0)
        return 1;
    if(m<0)
        return -1;
}
void InitList()/*初始化事件表為空表*/
{
    ev=(LNode *)malloc(sizeof(LNode));
    ev->next=NULL;
}
int QueueLength(LinkQueue a)
{
    int length=0;
    QNode *p;
    for(p=(a.front)->next;p!=NULL;p=p->next)
        length++;
    return length;
}
void InitQueue(LinkQueue q[])/*初始化隊列*/
{
    int i;
    for(i=1;i<=4;i++)
    {
        q[i].front=q[i].rear=(QNode *)malloc(sizeof(QNode));
    if(!(q[i].front))
    {
        printf("Allocation failed!\n");
        return;
    }
    q[i].front->next=NULL;
    }
}
void GetHead(LinkQueue a,QElemType customer)/*獲得隊列的頭*/
{
    customer=a.front->next->data;
}
int  Minimum(LinkQueue q[])/*q 是隊列數組名*/
{
    int length[5];
    int min;
    int i,j;
    for(i=1;i<=4;i++)
        length[i]=QueueLength(q[i]);
    j=1;
    min=length[1];
    for(i=1;i<=4;i++)
    {
        if(length[i]<min)
        {
            min=length[i];
            j=i;
        }
    }
    return j;
}
void EnQueue(LinkQueue Q,QElemType e)
{
    QNode *p=(QNode *)malloc(sizeof(QNode));
    if(!p)
    {
        printf("Allocation failed!\n");
        exit(0);
    }
    (p->data).ArrivalTime=e.ArrivalTime;
    (p->data).Duration=e.Duration;
    Q.rear->next=p;
    Q.rear=p;
}
void DelQueue(LinkQueue Q,QElemType *e)
{
    QNode *p;
    if(Q.front==Q.rear)
    {
        printf("The queue is empty!\n");
        exit(0);
    }
    p=Q.front->next;
    (*e).ArrivalTime=(p->data).ArrivalTime;
    (*e).Duration=(p->data).Duration;
    Q.front->next=p->next;
    if(Q.rear==p)
        Q.rear=Q.front;
    free(p);
}
void PrintQueue(LinkQueue q[])
{
    QNode *p;
    int i;
    for(i=1;i<=4;i++)
    {
        printf("Queue[%d]:",i);
        p=q[i].front->next;
        while(p!=NULL)
        {
            printf("(%d %d)",(p->data).ArrivalTime,(p->data).Duration);
            p=p->next;
        }
        printf("\n");
    }
}
void OrderInsert(LNode *ev,Event * ab)
{
    LNode *p1,*p2;
    LNode *p0=(LNode *)malloc(sizeof(LNode));
    (p0->en).OccurTime=ab->OccurTime;
    (p0->en).NType=ab->NType;
    p0->next=NULL;
    p1=ev->next;
    if(p1==NULL)
    {
        ev->next=p0;
        p0->next=NULL;
    }
    else
    {
        while((cmp(&(p1->en),ab)<=0)&&(p1->next!=NULL))
        {
            p2=p1;
            p1=p1->next;
        }
        if(cmp(&(p1->en),ab)>0)
        {
            if(ev->next==p1)
                ev->next=p0;
            else
                p2->next=p0;
            p0->next=p1;
        }
        else
        {
            p1->next=p0;
            p0->next=NULL;
        }
    }
}
void Radom(int *durtime,int *intertime)/*產生兩個隨機數*/
{
    int stime;
    long ltime=time(NULL);
    stime=(unsigned int)ltime;
    srand(stime);
    *durtime=rand()%100;
    *intertime=rand()%100;
}
void PrintList(LNode *ev)
{
    LNode *p=ev->next;
    printf("(OccurTime,NType):");
    while(p!=NULL)
    {
        printf("(%d,%d)",p->en.OccurTime,p->en.NType);
        p=p->next;
    }
    printf("\n");
}



void OpenForDay()
{
    TotalTime=0;
    CustomerNum=0;
    InitList();
    en.OccurTime=0;en.NType=0;
    OrderInsert(ev,&en);
    PrintList(ev);
    InitQueue(q);
    PrintQueue(q);
} 
void CustomerArrived()
{
    int t,i;
    QElemType a;
    int durtime,intertime;
    CustomerNum++;
    Radom(&durtime,&intertime);
    t=en.OccurTime+intertime;
    en.OccurTime=t;
    en.NType=0;
    if(t<CloseTime)
        OrderInsert(ev,&en);
    i=Minimum(q);
    a.ArrivalTime=en.OccurTime;
    a.Duration=durtime;
    EnQueue(q[i],a);
    PrintQueue(q);
    if(QueueLength(q[i])==1)
    {
        en.OccurTime=en.OccurTime+durtime;
        en.NType=i;
        OrderInsert(ev,&en);
    }
}
int QueueEmpty(LinkQueue a)
{
    if(a.front==a.rear)
        return 1;
    return 0;
}
void CustomerDeparture()
{
    int i;
    en.OccurTime=en.OccurTime+customer.Duration;
    i=en.NType;
    DelQueue(q[i],&customer);
    TotalTime+=en.OccurTime-customer.ArrivalTime;
    if(!QueueEmpty(q[i]))
    {
        GetHead(q[i],customer);
        OrderInsert(ev,&en);
        PrintQueue(q);
    }
}
void Bank_Simulation(int CloseTime)
{
    OpenForDay();
    while(!ListEmpty(ev))
    {
        GetCurElem(ev);
        if(en.NType==0)
            CustomerArrived();
        else
            CustomerDeparture();
        DelFirst(ev);
    }
    printf("The avarage time each customer used is %f\n",(float)TotalTime/CustomerNum);
}
main()
{
    printf("Input the close time:");
    scanf("%d",&CloseTime);
    Bank_Simulation(CloseTime);
}