#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;
typedef struct
{
    int OccurTime; // 事件发生时刻
    int NType;     // 事件类型，0表示到达事件，1-4表示四个窗口的离开事件
} Event, ElemType;

typedef struct LNode
{
    ElemType data;
    struct LNode *next;
} LNode, *LinkList;

typedef LinkList EventList;
typedef struct
{
    int ArrivalTime; // 到达时刻
    int Duration;    // 办理事务所需事件
} QElemType;

typedef struct QNode
{
    QElemType data;
    struct QNode *next;
} QNode, *QueuePtr;

typedef struct
{
    QueuePtr front; // 队头指针
    QueuePtr rear;  // 队尾指针
} LinkQueue;

EventList ev;       // 事件表
Event en;           // 事件
LinkQueue q[5];     // 四个客户队列
QElemType customer; // 客户记录
int TotalTime, CustomerNum, CloseTime;
void Bank_Simulation(int CloseTime);                                   // 银行业务模拟，统计一天内客户在银行逗留的平均时间
int cmp(Event a, Event b);                                             // 比较事件发生先后
void OpenForDay();                                                     // 银行开门
void OrderInsert(EventList L, Event en, int (*cmp)(Event a, Event b)); // 插入事件
void CustomerArrived();                                                // 客户进门
void CustomerDepature();                                               // 客户离开
int Minimum(LinkQueue Q[5]);                                           // 求长度最短队列
Status InitList(LinkList &L);                                          // 链表初始化
Status ListInsert_L(LinkList &L, int i, ElemType e);                   // 在第i个位置之前插入元素e
Status ListEmpty(LinkList L);                                          // 判断链表是否为空
Status DelFirst(LinkList L, LNode *&q);                                // 删除链表中第一个结点并以q返回
LNode *GetHead(LinkList L);                                            // 返回链表头结点
ElemType GetCurElem(LNode *p);                                         // 已知p指向线性链表中的一个结点，返回p所指结点中元素的值
void PrintEventList();                                                 // 打印事件链表
Status ListTraverse(LinkList &L);                                      // 遍历链表 
Status InitQueue(LinkQueue &Q);                                        // 链队列的初始化
Status EnQueue(LinkQueue &Q, QElemType e);                             // 入队
Status DeQueue(LinkQueue &Q, QElemType &e);                            // 出队
int QueueLength(LinkQueue Q);                                          // 返回队列的长度
Status GetHead(LinkQueue Q, QElemType &e);                             // 获取队头元素 注：由于参数个数不同，发生函数重载
Status QueueEmpty(LinkQueue Q);                                        // 判断队列是否为空
void PrintQueue();                                                     // 打印队列
Status QueueTraverse(LinkQueue Q);                                     // 遍历队列Q 

/*
系统每次随机生成的是
1）当前客户的柜台被服务时间
2）当前客户和下一个客户到达的间隔时间
每个客户在银行的等待时间取决于队列里前一个节点的离开时间，而不是自己的到达时间+服务时间。*/

int main()
{
    srand((unsigned)time(NULL)); // 设定随机数种子
    printf("请输入银行的营业时间(min)：");
    scanf("%d", &CloseTime);
    Bank_Simulation(CloseTime);
    return 0;
}
void Bank_Simulation(int CloseTime) // 银行业务模拟，统计一天内客户在银行逗留的平均时间
{
    OpenForDay(); // 开始营业
    LNode *p;
    while (!ListEmpty(ev))
    {
        DelFirst(GetHead(ev), p);
        printf("********action********\n");
        en = GetCurElem(p);
        if (en.NType == 0)
        {
            CustomerArrived();
        }
        else
        {
            CustomerDepature();
        }
        PrintQueue();
        PrintEventList();
    }
    printf("The Average Time is %f\n", (float)TotalTime / CustomerNum);
}
int cmp(Event a, Event b) // 比较事件发生先后
{
    if (a.OccurTime > b.OccurTime)
        return 1;
    if (a.OccurTime = b.OccurTime)
        return 0;
    if (a.OccurTime < b.OccurTime)
        return -1;
}

void OpenForDay() // 银行开门
// 初始化操作
{
    TotalTime = 0;   // 初始化累计时间为0
    CustomerNum = 0; // 初始化客户数为0
    InitList(ev);    // 初始化事件链表为空表
    en.OccurTime = 0;
    en.NType = 0; // 设定第一个客户到达事件
    OrderInsert(ev, en, cmp);
    for (int i = 1; i <= 4; i++)
    {
        InitQueue(q[i]); // 将四个银行窗口队列初始化
    }
}

void OrderInsert(EventList L, Event en, int (*cmp)(Event a, Event b)) // 插入事件
// 事件插入函数，将不同事件按发生时间递增排序
{
    LNode *p = L;
    int i = 1;
    while (p->next && cmp(en, p->next->data) > 0) // 找到事件发生时间所在事件链表中的位置
    {
        p = p->next;
        i++;
    }
    ListInsert_L(ev, i, en); // 插入该事件
}

void CustomerArrived() // 客户进门
// 处理客户到达事件，en.NType=0
{
    CustomerNum++;
    int durtime = rand() % 30 + 1;    // 客户处理事务时间
    int intertime = rand() % 8;       // 下一个客户到达的时间间隔
    int t = en.OccurTime + intertime; // 下一个客户到达的时刻
    if (t < CloseTime)                // 如果他在营业时间内进来
    {
        printf("一个新客户在银行营业%2dmin后进来，办理业务花费了%2dmin，下一个客户过了%2dmin后进来\n", en.OccurTime, durtime, intertime);
        OrderInsert(ev, {t, 0}, cmp); // 插入客户进门事件，NType=0为到达事件
    }

    int i = Minimum(q); // 客户找最短队开始排队
    EnQueue(q[i], {en.OccurTime, durtime});
    if (QueueLength(q[i]) == 1)
    {
        OrderInsert(ev, {en.OccurTime + durtime, i}, cmp); // 队列长度为1时，设定一个离开事件
    }
}

void CustomerDepature() // 客户离开
{
    int i = en.NType;
    DeQueue(q[i], customer);                          // 删除第i队列的排头客户
    TotalTime += en.OccurTime - customer.ArrivalTime; // 累计客户逗留时间
    if (!QueueEmpty(q[i]))
    {
        GetHead(q[i], customer);
        OrderInsert(ev, {en.OccurTime + customer.Duration, i}, cmp); // 插入事件
    }
}

int Minimum(LinkQueue Q[5]) // 求长度最短队列
{
    int minLength = QueueLength(Q[1]);
    int i = 1;
    for (int j = 2; j < 5; j++)
    {
        if (minLength > QueueLength(Q[j]))
        {
            minLength = QueueLength(Q[j]);
            i = j;
        }
    }
    return i;
}

Status InitList(LinkList &L) // 链表初始化
{
    L = (LinkList)malloc(sizeof(LNode));
    if (!L)
    {
        exit(OVERFLOW);
    }
    L->next = NULL;
    return OK;
}

Status ListInsert_L(LinkList &L, int i, ElemType e) // 在第i个位置之前插入元素e
{
    LinkList p = L;
    int j = 0;
    while (p && j < i - 1) // 注意是i-1,因为要找被插入元素的前一个元素
    {
        p = p->next;
        j++;
    }
    if (!p || j > i - 1)
    {
        return ERROR;
    }
    LinkList s = (LinkList)malloc(sizeof(LNode));
    if (!s)
    {
        exit(OVERFLOW);
    }
    s->data = e;
    s->next = p->next;
    p->next = s;
    return OK;
}
Status ListEmpty(LinkList L) // 判断链表是否为空
// 空表：头指针和头结点仍然存在，但头结点指向NULL
{
    if (L->next)
    {
        return FALSE;
    }
    else
    {
        return TRUE;
    }
}
Status DelFirst(LinkList L, LNode *&q) // 删除链表中第一个结点并以q返回
{
    if (!L->next)
    {
        return ERROR;
    }
    q = L->next;
    L->next = q->next;
    return OK;
}
LNode *GetHead(LinkList L) // 返回链表头结点
{
    return L;
}

ElemType GetCurElem(LNode *p) // 已知p指向线性链表中的一个结点，返回p所指结点中元素的值
{
    return p->data;
}

void PrintEventList() // 打印事件链表 
{
    printf("Current Eventlist is:\n");
    ListTraverse(ev);
}
Status ListTraverse(LinkList &L) // 遍历链表  
{
    LNode *p = L->next;
    if (!p)
    {
        printf("List is empty.\n");
        return ERROR;
    }

    while (p != NULL)
    {
        printf("OccurTime:%d,Event Type:%d\n", p->data.OccurTime, p->data.NType);
        p = p->next;
    }
    printf("\n");
    return OK;
}

Status InitQueue(LinkQueue &Q) // 链队列的初始化
{
    Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode));
    if (!Q.front)
    {
        exit(OVERFLOW);
    }
    Q.front->next = NULL;
    return OK;
}
Status EnQueue(LinkQueue &Q, QElemType e) // 入队
{
    QNode *p = (QueuePtr)malloc(sizeof(QNode));
    if (!p)
    {
        exit(OVERFLOW);
    }
    p->data = e;
    p->next = NULL;
    Q.rear->next = p;
    Q.rear = p;
    return OK;
}
Status DeQueue(LinkQueue &Q, QElemType &e) // 出队
{
    if (Q.front == Q.rear)
    {
        return ERROR;
    }
    QNode *p = Q.front->next;
    e = p->data;
    Q.front->next = p->next;
    if (Q.rear == p) // 注意这里要考虑到,当队列中最后一个元素被删后，队列尾指针也丢失了，因此需对队尾指针重新复制(指向头结点)
    {
        Q.rear = Q.front;
    }
    free(p);
    return OK;
}

int QueueLength(LinkQueue Q) // 返回队列的长度
{
    int count = 0;
    QNode *p = Q.front->next;
    while (p)
    {
        p = p->next;
        count++;
    }
    return count;
}

Status GetHead(LinkQueue Q, QElemType &e) // 获取队头元素
{
    if (Q.front == Q.rear)
    {
        return ERROR;
    }
    e = Q.front->next->data;
}
Status QueueEmpty(LinkQueue Q) // 判断队列是否为空
{
    if (Q.front == Q.rear)
    {
        return TRUE;
    }
    return FALSE;
}
void PrintQueue() // 打印队列
{
    // 打印当前队列  
    int i;
    for (i = 1; i <= 4; i++)
    {
        printf("窗口 %d 有 %d 个客户:", i, QueueLength(q[i]));
        QueueTraverse(q[i]);
    }
    printf("\n");
}
Status QueueTraverse(LinkQueue Q) // 遍历队列Q  
{
    QNode *p = Q.front->next;
    if (!p)
    {
        printf("--Is empty.\n");
        return ERROR;
    }
    while (p)
    {
        printf("(到达时刻 %d min 办理业务需要花费 %d min) ", p->data.ArrivalTime, p->data.Duration);
        p = p->next;
    }
    printf("\n");
    return OK;
}