#include <iostream>
#include <string>
#include <algorithm>
#include <fstream>
#include <sstream>
#include <clocale>
#include <cassert>
#include <cstring>
using namespace std;

#define OK 1
#define ERROR 0
#define DEFAULT_SIZE 100

#ifndef DEBUG
#define DEBUG 1
#endif




// 已定乘客
typedef struct passanger_booked {
    string name = "";
    int seatclass = 0;
    int seatcount = 0;
    struct passanger_booked *next = NULL;
} *PA_Node;

// 候补乘客
typedef struct passanger_waiting {
    string name = "";
    int seatclass = 0;
    int seatcount = 0;
    struct passanger_waiting *next = NULL;
} *PAW_Node;

// 航班
typedef struct flight {
    string destination = "";
    string flightno = "";
    string registerno = "";
    string date = "";
    int maxseat[3] = {0,0,0};     // 0:头等舱 1:商务舱 2:经济舱
    int bookedseat[3] = {0,0,0};  // 0:头等舱 1:商务舱 2:经济舱
    struct passanger_booked *pa_booked = NULL;
    struct passanger_waiting *pa_waiting = NULL;
    struct flight *next = NULL;
} *FL_Node;

// int init(FL_Node &FL);
// FL_Node new_flight(FL_Node &FL, string destination, string flightno, string registerno, string date, int maxseat[3], int bookedseat[3]);
// int new_PA(FL_Node &FL, string name, int seatclass, int seatcount);
// int new_PAW(FL_Node &FL, string name, int seatclass, int seatcount);
// int del_PA(FL_Node &FL, string name);
// int del_PAW(FL_Node &FL, string name);
int PAW_to_PA(FL_Node &FL);
// int save_to_file(FL_Node FL_head);
// int read_from_file(FL_Node &FL_head);
void clearMemory(FL_Node &FL_head);
bool cmp(string name1, string name2);

// 初始化航班链表
int init(FL_Node &FL)
{
    FL = NULL;
    return OK;
}

// 创建航班节点
// 后面的参数为可选参数，不填则默认为空并且预留大小为DEFAULT_SIZE的内存空间，填写则自动写入
FL_Node new_flight(FL_Node &FL, string destination = "", string flightno = "", string registerno = "", string date = "", int maxseat[3] = NULL, int bookedseat[3] = NULL)
{
    FL_Node p;
    p = new flight;
    if (p == NULL) {
        cerr << "内存分配失败！" << endl;
        return NULL;
    }

    if (!destination.empty())
        p->destination.assign(destination);
    if (!flightno.empty())
        p->flightno.assign(flightno);
    if (!registerno.empty())
        p->registerno.assign(registerno);
    if (!date.empty())
        p->date.assign(date);

    for (int i = 0; i < 3; i++) {
        if (maxseat)
            p->maxseat[i] = maxseat[i];
        else
            p->maxseat[i] = 0;
        if (bookedseat)
            p->bookedseat[i] = bookedseat[i];
        else
            p->bookedseat[i] = 0;
    }
    p->pa_booked = NULL;
    p->pa_waiting = NULL;
    p->next = NULL;
    if (FL == NULL) {
        FL = p;
    } else {
        FL_Node q = FL;
        if (cmp(p->destination, q->destination)) 
        {
            p->next = q;
            FL = p;
            return p;
        }
        else
        {
            while (q->next != NULL)
            {
                if (cmp(p->destination, q->next->destination))
                    break;
                q = q->next;
            }
            p->next = q->next;
            q->next = p;
        }
    }
    return p;
}

// 创建已定乘客节点
int new_PA(FL_Node &FL, string name, int seatclass, int seatcount)
{
    if (!FL)
    {
        cerr << "错误：输入NULL指针" << endl;
        if (DEBUG) assert(FL != NULL);
        return ERROR;
    }
    // 检查输入是否合法
    if (seatclass < 0 || seatclass > 2)
    {
        cout << "座位类型错误！" << endl;
        return ERROR;
    }
    if (seatcount < 0 || seatcount > FL->maxseat[seatclass])
    {
        cout << "座位数量错误！" << endl;
        return ERROR;
    }
    if (name.empty())
    {
        cout << "姓名不能为空！" << endl;
        return ERROR;
    }

    // 检查所订仓等余票是否足够
    if (FL->maxseat[seatclass] - FL->bookedseat[seatclass] < seatcount)
    {
        cout << "余票不足！" << endl;
        return -1;
    }

    // 创建新节点
    PA_Node p;
    p = new passanger_booked;
    if (p == NULL)
    {
        cerr << "内存分配失败！" << endl;
        return ERROR;
    }
    p->name.assign(name);
    p->seatclass = seatclass;
    p->seatcount = seatcount;
    p->next = NULL;
    FL->bookedseat[seatclass] += seatcount;

    // 将新节点插入链表
    if (FL->pa_booked == NULL)
        FL->pa_booked = p;
    else
    {
        PA_Node q = FL->pa_booked;
        if (cmp(p->name, q->name))
        {
            p->next = q;
            FL->pa_booked = p;
        }
        else
        {
            while (q->next != NULL)
            {
                if (cmp(p->name, q->next->name))
                    break;
                q = q->next;
            }
            p->next = q->next;
            q->next = p;
        }
    }
    return OK;
}

// 创建候补乘客节点
int new_PAW(FL_Node &FL, string name, int seatclass, int seatcount)
{
    if (!FL)
    {
        cerr << "错误：输入NULL指针" << endl;
        if (DEBUG) assert(FL != NULL);
        return ERROR;
    }
    // 检查输入是否合法
    if (seatclass < 0 || seatclass > 2)
    {
        cout << "座位类型错误！" << endl;
        return ERROR;
    }
    if (seatcount < 0 || seatcount > FL->maxseat[seatclass])
    {
        cout << "座位数量错误！" << endl;
        return ERROR;
    }
    if (name.empty())
    {
        cout << "姓名不能为空！" << endl;
        return ERROR;
    }

    // 创建新节点
    PAW_Node p;
    p = new passanger_waiting;
    if (p == NULL)
    {
        cerr << "内存分配失败！" << endl;
        return ERROR;
    }
    p->name.assign(name);
    p->seatclass = seatclass;
    p->seatcount = seatcount;
    p->next = NULL;

    // 将新节点插入链表
    if (FL->pa_waiting == NULL)
        FL->pa_waiting = p;
    else
    {
        PAW_Node q = FL->pa_waiting;


        while (q->next != NULL)
        {
            q = q->next;
        }
        q->next = p;
    }
    return OK;
}

// 删除已定乘客节点
int del_PA(FL_Node &FL, string name)
{
    if (!FL)
    {
        cerr << "错误：输入NULL指针" << endl;
        if (DEBUG) assert(FL != NULL);
        return ERROR;
    }
    PA_Node p = FL->pa_booked;
    PA_Node q = NULL;
    while (p != NULL)
    {
        if (p->name == name)
        {
            if (q == NULL)
            {
                FL->pa_booked = p->next;
            }
            else
            {
                q->next = p->next;
            }
            FL->bookedseat[p->seatclass] -= p->seatcount;
            p->name.clear();
            delete p;
            // 候补乘客入座
            PAW_to_PA(FL);
            return OK;
        }
        q = p;
        p = p->next;
    }
    //cout << "未找到该乘客！" << endl;
    return ERROR;
}

// 删除候补乘客节点
// 如有重名则删除第一个
int del_PAW(FL_Node &FL, string name)
{
    if (!FL)
    {
        cerr << "错误：输入NULL指针" << endl;
        if (DEBUG) assert(FL != NULL);
        return ERROR;
    }
    PAW_Node p = FL->pa_waiting;
    PAW_Node q = NULL;
    while (p != NULL)
    {
        if (p->name == name)
        {
            if (q == NULL)
            {
                FL->pa_waiting = p->next;
            }
            else
            {
                q->next = p->next;
            }
            p->name.clear();
            delete p;
            return OK;
        }
        q = p;
        p = p->next;
    }
    // cout << "未找到该乘客！" << endl;
    return ERROR;
}

// 候补乘客入座
int PAW_to_PA(FL_Node &FL)
{
    if (!FL)
    {
        cerr << "错误：输入NULL指针" << endl;
        if (DEBUG) assert(FL != NULL);
        return ERROR;
    }
    // 检查是否有候补乘客
    if (FL->pa_waiting == NULL)
    {
        cout << "没有候补乘客！" << endl;
        return ERROR;
    }

    // 依次检查是否有足够入座的候补乘客
    PAW_Node p = FL->pa_waiting;
    PAW_Node q = NULL;
    bool flag = false;
    while (p != NULL)
    {
        if (p->seatcount <= FL->maxseat[p->seatclass] - FL->bookedseat[p->seatclass])
        {
            //FL->bookedseat[p->seatclass] += p->seatcount;
            new_PA(FL, p->name, p->seatclass, p->seatcount);
            cout << "候补乘客" << p->name << "入座" << endl;
            if (q == NULL)
            {
                FL->pa_waiting = p->next;
            }
            else
            {
                q->next = p->next;
            }
            PAW_Node temp = p;
            p = p->next;
            temp->name.clear();
            delete temp;
            flag = true;
        }
        else
        {
            q = p;
            p = p->next;
        }
    }
    if (flag)
        return OK;
    else
    {
        cout << "没有满足入座条件的候补乘客！" << endl;
        return ERROR;
    }
}


// 保存
int save_to_file(FL_Node FL_head)
{
    if (!FL_head)
    {
        cerr << "错误：输入NULL指针" << endl;
        if (DEBUG) assert(FL_head != NULL);
        return ERROR;
    }
    ofstream fout;
    fout.open("data.txt", ios::out);
    if (!fout)
    {
        cerr << "文件打开失败！" << endl;
        return ERROR;
    }
    FL_Node p = FL_head;
    while (p != NULL)
    {
        // 将空格替换为下划线
        size_t pos = p->destination.find(" "); // size_t是刚好存放指针的数据类型
        if (pos != string::npos) p->destination.replace(pos, 1, "_");
        pos = p->flightno.find(" ");
        if (pos != string::npos) p->flightno.replace(pos, 1, "_");
        pos = p->registerno.find(" ");
        if (pos != string::npos) p->registerno.replace(pos, 1, "_");
        pos = p->date.find(" ");
        if (pos != string::npos) p->date.replace(pos, 1, "_");

        fout << p->destination << " " << p->flightno << " " << p->registerno << " " << p->date << " " << p->maxseat[0] << " " << p->maxseat[1] << " " << p->maxseat[2] << endl;
        PA_Node q = p->pa_booked;
        while (q != NULL)
        {
            pos = q->name.find(" ");
            if (pos != string::npos) q->name.replace(pos, 1, "_");
            fout << "PA " << q->name << " " << q->seatclass << " " << q->seatcount << endl;
            q = q->next;
        }
        PAW_Node r = p->pa_waiting;
        while (r != NULL)
        {
            pos = r->name.find(" ");
            if (pos != string::npos) r->name.replace(pos, 1, "_");
            fout << "PAW " << r->name << " " << r->seatclass << " " << r->seatcount << endl;
            r = r->next;
        }
        fout << "END_OF FILGHT 0 0" << endl;
        p = p->next;
    }
    fout.close();
    return OK;
}

// 清空内存并读取
int read_from_file(FL_Node &FL_head)
{
    clearMemory(FL_head); // 清空内存
    ifstream fin; // 读取文件流
    fin.open("data.txt", ios::in);
    if (!fin)
    {
        cerr << "文件打开失败！" << endl;
        return ERROR;
    }
    string line;
    while (getline(fin, line)) // 从fin读取一行放入line
    {
        if (line.empty())
            break;
        FL_Node p = new flight;
        istringstream iss(line); // istringstream是从string读取的流，与cin类似，这里将line放入iss流
        iss >> p->destination >> p->flightno >> p->registerno >> p->date >> p->maxseat[0] >> p->maxseat[1] >> p->maxseat[2];

        // 将下划线替换为空格
        size_t pos = p->destination.find("_");
        if (pos != string::npos) p->destination.replace(pos, 1, " ");
        pos = p->flightno.find("_");
        if (pos != string::npos) p->flightno.replace(pos, 1, " ");
        pos = p->registerno.find("_");
        if (pos != string::npos) p->registerno.replace(pos, 1, " ");
        pos = p->date.find("_");
        if (pos != string::npos) p->date.replace(pos, 1, " ");

        p->pa_booked = NULL;
        p->pa_waiting = NULL;
        p->next = NULL;
        for (int i = 0; i < 3; i++)
            p->bookedseat[i] = 0;

        FL_Node q = FL_head;
        if (q == NULL) // 首个节点
        {
            FL_head = p;
        }
        else
        {
            if (cmp(p->destination, q->destination)) // 比首个节点小，新的首节点
            {
                p->next = q;
                FL_head = p;
            }
            else
            {
                while (q->next != NULL) // 找到第一个比p大的节点
                {
                    if (cmp(p->destination, q->next->destination))
                        break;
                    q = q->next;
                }
                p->next = q->next; // 插入
                q->next = p;
            }
        }

        string name, type;
        int seatclass, seatcount;
        while (getline(fin, line))
        {
            istringstream iss(line);
            iss >> type >> name >> seatclass >> seatcount;
            pos = name.find("_");
            if (pos != string::npos) name.replace(pos, 1, " ");
            if (type == "PA")
                new_PA(p, name, seatclass, seatcount);
            else if (type == "PAW")
                new_PAW(p, name, seatclass, seatcount);
            else
                break;
        }
    }
    fin.close();
    return OK;
}

// 清空内存
void clearMemory(FL_Node &FL_head)
{
    FL_Node p = FL_head;
    while (p != NULL)
    {
        PA_Node q = p->pa_booked;
        while (q != NULL)
        {
            PA_Node temp = q;
            q = q->next;
            temp->name.clear();
            delete temp;
        }
        PAW_Node r = p->pa_waiting;
        while (r != NULL)
        {
            PAW_Node temp = r;
            r = r->next;
            temp->name.clear();
            delete temp;
        }
        FL_Node temp = p;
        p = p->next;
        temp->destination.clear();
        temp->flightno.clear();
        temp->registerno.clear();
        temp->date.clear();
        delete temp;
    }
    FL_head = NULL;
}

// a < b时返回true
bool cmp(string a, string b) {
    setlocale(LC_COLLATE, "zh_CN.gbk"); // 设置中文环境
    return strcoll(a.c_str(), b.c_str()) < 0; // 但是处理不了多音字，如：重庆->zhong qing
}