#include <iostream>
#include <algorithm>
#include <cstring>
#include <stdlib.h>

using namespace std;
const int N = 10;

int n, m;

int cnt;

int Available[N];
int Max[N][N];
int Allocation[N][N];
int Need[N][N];
int path[N];

bool Finish[N];
bool st[N];

//函数部分，为了不出现函数的未声明情况，所以用c语言的命名方法
void interface();
void attention();
void init_Available();
void init_Max();
void init_Allocation();
void init_Need();
void cur_Available();
void now_table_print();
bool safe();
bool bank_first(int id, int request[]);
bool bank_second(int request[]);
bool bank(int id, int request[]);
void resource();
void safe_table_print();
void safe_path_print();
//


void interface()
{
    printf("请输入操作的指令， 按 1 继续， 按 0 退出。\n");
    int op;
    cin >> op;

    if (op == 1)
    {
        printf("\n");
        printf("\n");
        printf("----------------------------------\n");
        printf("----------------------------------\n");
        printf("----------银行家算法模拟----------\n");
        printf("----------------------------------\n");
        printf("----------------------------------\n");
        printf("\n");
        printf("\n");
    }
    else
        exit(0);

}

void attention()
{
    printf("请输入进程数还有每个进程的资源数:     \n");
    cin >> n >> m;
}

void init_Available()
{
    printf("请输入系统全部可用资源数量Available:      \n");
    for (int i = 0; i < m; i ++ )
        cin >> Available[i];
}

void init_Max()
{
    printf("请输入Max矩阵:      \n");
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < m; j ++ )
            cin >> Max[i][j];
}

void init_Allocation()
{
    printf("请输入已经分配的矩阵Allocation:      \n");
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < m; j ++ )
        cin >> Allocation[i][j];
}

void init_Need()
{
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < m; j ++ )
        Need[i][j] = Max[i][j] - Allocation[i][j];
}

void cur_Available()
{
    for (int j = 0; j < m; j ++ )
        for (int i = 0; i < n; i ++ )
        Available[j] -= Allocation[i][j];
}

void now_table_print()
{
    printf("\n");
    printf("-----------------------------此时刻资源分配情况--------------------------------\n");
    printf("|    进程名    |     Max     |   Allocation   |    Need    |    Available    |\n");

    for (int i = 0; i < n; i ++ )
    {
        printf("       p%d         ", i);

        for (int j = 0; j < m; j ++ )
            printf("%d   ", Max[i][j]);
        printf("\t ");

        for (int j = 0; j < m; j ++ )
            printf("%d   ", Allocation[i][j]);
        printf("\t ");

        for (int j = 0; j < m; j ++ )
            printf("%d   ", Need[i][j]);
        printf("\t");

        if (i == 0)
        {
            for(int j = 0; j < m; j ++ )
                printf("%d   ", Available[j]);
        }
        printf("\n");
    }
    printf("------------------------------------------------------------------------------\n");
}

bool safe_second(int id, int work[])
{
    for (int j = 0; j < m; j ++ )
        if (Need[id][j] > work[j]) return false;

    return true;
}

bool safe()
{
    int Work[m];

    for (int i = 0; i < n; i ++ ) st[i] = false;
    for (int i = 0; i < m; i ++ ) Work[i] = Available[i];

    for (int i = 0; i < n; i ++ )
    {
        int t = -1;
        for (int id = 0; id < n; id ++ )
            if (!st[id] && safe_second(id, Work))
                {
                    t = id;
                    break;
                }

        if (t == -1) return false;

        path[i] = t;
        st[t] = true;

        for (int j = 0; j < m; j ++ ) Work[j] += Allocation[t][j];
    }

    return true;
}

bool bank_first(int id, int request[])
{
    for (int j = 0; j < m; j ++ )
        if (request[j] > Need[id][j]) return false;

    return true;
}

bool bank_second(int request[])
{
    for (int j = 0; j < m; j ++ )
        if (request[j] > Available[j]) return false;

    return true;
}

bool bank(int id, int request[])
{
        if (bank_first(id, request))
        {
            if (bank_second(request))
            {
                for (int j = 0; j < m; j ++ )
                {
                    Available[j] -= request[j];
                    Allocation[id][j] += request[j];
                    Need[id][j] -= request[j];
                }

                if (safe())
                {
                    for (int i = 0; i < n; i ++ ) Finish[i] = st[i];
                    return true;
                }
                else
                {
                    for (int j = 0; j < m; j ++ )
                    {
                        Available[j] += request[j];
                        Allocation[id][j] -= request[j];
                        Need[id][j] += request[j];
                    }

                    return false;
                }
            }
            else
            {
                printf("尚且没有足够的资源，该进程资源需要等待\n");
                return false;
            }
        }
        else
        {
            printf("所需要得资源超过需要的最大值, 资源请求分配错误！");
            return false;
        }

    return true;
}

void resource()
{
    int id, request[m];

    printf("输入请求资源的线程的id：\n");
    cin >> id;

    printf("输入所需要的资源数：\n");
    for (int j = 0; j < m; j ++ )
        cin >> request[j];

    if (bank(id, request))
    {
        printf("资源申请通过，是否显示分配后的资源数值表： 按 1 显示， 按 2 继续分配, 按 3 显示安全分配表， 按 0 退出程序\n");

        int op;
        cin >> op;

        if (op == 1)
        {
            now_table_print();
            printf("继续分配请按 1 ， 退出程序请按 0 \n");

            int op1;
            cin >> op1;
            if (op1 == 1) resource();
            else exit(0);
        }
        else if (op == 2) resource();
        else if (op == 3) safe_table_print();
        else if (op == 0) exit(0);
    }
    else
    {
        printf("\n");
        printf("资源申请尝试失败!\n");
        printf("是否进行资源的重新申请？\n");
        printf("按 1 继续申请， 按 0 系统退出程序\n");

        int op;
        cin >> op;
        if (op == 1) resource();
        else if (op == 0) exit(0);
    }
}

void safe_table_print()
{
    int Work[m];
    int backup_availabe[m];
    for (int i = 0; i < m; i ++ ) backup_availabe[i] = Available[i];

    printf("\n");
    printf("------------------------------此时刻资源分配情况-----------------------------------------\n");
    printf(" 进程名   |    Work   |    Need   |   Allocation  |    Work + Allocation   |   Finish  |  \n");
    for (int i = 0; i < n; i ++ )
    {
        for (int j = 0; j < m; j ++ ) Work[j] = backup_availabe[j];
        int t = path[i];

        printf(" p%d      " ,t);

        for(int j = 0; j < m; j ++ )
            printf(" %2d",Work[j]);
        printf("\t");

        for(int j = 0; j < m; j ++ )
            printf(" %1d ",Need[t][j]);
        printf("\t");

        for(int j = 0; j < m; j ++ )
            printf("%1d ",Allocation[t][j]);
        printf("\t");


        for (int j = 0; j < m; j ++ )
            printf("  %4d ", Work[j] + Allocation[t][j]);
        printf("\t");

        for (int j = 0; j < m; j ++ )
            backup_availabe[j] = Work[j] + Allocation[t][j];

        printf("        True ");
        printf("\t");
        printf("\n");
    }
    printf("---------------------------------------------------------------------------------------\n");
    printf("\n");
    printf("请进行接下来的操作， 按 1 继续分配， 按 0 退出\n");

    int op;
    cin >> op;
    if (op == 1) resource();
    else if (op == 0) exit(0);

    printf("\n");
}

void safe_path_print()
{
    puts(" ");
    puts("存在一个安全序列如下: ");
    for (int i = 0; i < n; i ++ )
        printf(" P%d ", path[i]);
    puts(" ");
}

int main()
{
    interface();
    attention();
    init_Available();
    init_Max();
    init_Allocation();
    init_Need();
    cur_Available();

    now_table_print();

    printf("请输入操作的指令 按 1 进行安全检查， 按0 退出程序.\n");

    int op;
    cin >> op;
    if (op == 1)
    {
        if (safe())
        {
            safe_path_print();
            printf("初始系统状态安全， 相对应安全序列打表如下： \n");
            safe_table_print();
        }
        else
        {
            printf("初始系统不安全! 无法进行相应的资源申请，将退出系统程序！\n");
            exit(0);
        }
    }
    else exit(0);

    printf("接下来你想进行的操作， 按 1 资源分配申请， 按 0 退出程序.\n");
    printf("\n");

    int op1;
    cin >> op;

    if (op1 == 1) resource();
    else exit(0);

    return 0;
}