#include <iostream>
#include <vector>
#include <iomanip>
using namespace std;

class BankersAlgorithm {
private:
    int n; // 进程数量
    int m; // 资源类型数量
    vector<vector<int>> allocation; // 分配矩阵
    vector<vector<int>> max; // 最大需求矩阵
    vector<vector<int>> need; // 需求矩阵
    vector<int> available; // 可用资源向量
    
public:
    // 构造函数，初始化银行家算法
    BankersAlgorithm(int processes, int resources) {
        n = processes;
        m = resources;
        allocation.resize(n, vector<int>(m, 0));
        max.resize(n, vector<int>(m, 0));
        need.resize(n, vector<int>(m, 0));
        available.resize(m, 0);
    }
    
    // 加载测试数据集1：安全状态测试
    void loadTestData1() {
        cout << "加载测试数据集1：安全状态测试（5进程，3资源）" << endl;
        n = 5; m = 3;

        // 重新调整矩阵大小
        allocation.resize(n, vector<int>(m));
        max.resize(n, vector<int>(m));
        need.resize(n, vector<int>(m));
        available.resize(m);

        // 可用资源向量
        available = {3, 3, 2};

        // 分配矩阵
        allocation = {
            {0, 1, 0},
            {2, 0, 0},
            {3, 0, 2},
            {2, 1, 1},
            {0, 0, 2}
        };

        // 最大需求矩阵
        max = {
            {7, 5, 3},
            {3, 2, 2},
            {9, 0, 2},
            {2, 2, 2},
            {4, 3, 3}
        };

        calculateNeedMatrix();
        cout << "测试数据集1加载完成！预期：系统安全，安全序列如P1->P3->P4->P2->P0" << endl;
    }

    // 加载测试数据集2：不安全状态测试
    void loadTestData2() {
        cout << "加载测试数据集2：不安全状态测试（3进程，3资源）" << endl;
        n = 3; m = 3;

        // 重新调整矩阵大小
        allocation.resize(n, vector<int>(m));
        max.resize(n, vector<int>(m));
        need.resize(n, vector<int>(m));
        available.resize(m);

        // 可用资源向量
        available = {1, 0, 0};

        // 分配矩阵
        allocation = {
            {1, 2, 0},
            {2, 0, 1},
            {0, 1, 2}
        };

        // 最大需求矩阵
        max = {
            {3, 3, 2},
            {4, 2, 2},
            {3, 3, 3}
        };

        calculateNeedMatrix();
        cout << "测试数据集2加载完成！预期：系统不安全" << endl;
    }

    // 加载测试数据集3：边界情况测试
    void loadTestData3() {
        cout << "加载测试数据集3：边界情况测试（2进程，2资源）" << endl;
        n = 2; m = 2;

        // 重新调整矩阵大小
        allocation.resize(n, vector<int>(m));
        max.resize(n, vector<int>(m));
        need.resize(n, vector<int>(m));
        available.resize(m);

        // 可用资源向量
        available = {2, 2};

        // 分配矩阵
        allocation = {
            {1, 0},
            {0, 1}
        };

        // 最大需求矩阵
        max = {
            {3, 2},
            {2, 3}
        };

        calculateNeedMatrix();
        cout << "测试数据集3加载完成！预期：系统安全，安全序列如P0->P1或P1->P0" << endl;
    }

    // 输入系统状态信息
    void inputSystemState() {
        cout << "请输入可用资源向量Available（" << m << "个资源类型）：";
        for (int i = 0; i < m; i++) {
            cin >> available[i];
        }

        cout << "请输入分配矩阵Allocation：" << endl;
        for (int i = 0; i < n; i++) {
            cout << "进程P" << i << "：";
            for (int j = 0; j < m; j++) {
                cin >> allocation[i][j];
            }
        }

        cout << "请输入最大需求矩阵Max：" << endl;
        for (int i = 0; i < n; i++) {
            cout << "进程P" << i << "：";
            for (int j = 0; j < m; j++) {
                cin >> max[i][j];
            }
        }

        // 计算需求矩阵Need = Max - Allocation
        calculateNeedMatrix();
    }

    // 计算需求矩阵
    void calculateNeedMatrix() {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                need[i][j] = max[i][j] - allocation[i][j];
            }
        }
    }

    // 显示当前系统状态
    void displaySystemState() {
        cout << "\n=== 当前系统状态 ===" << endl;

        // 显示可用资源
        cout << "可用资源Available：";
        for (int i = 0; i < m; i++) {
            cout << setw(4) << available[i];
        }
        cout << endl;

        // 显示各矩阵
        cout << "\n进程\t分配矩阵Allocation\t最大需求矩阵Max\t\t需求矩阵Need" << endl;
        for (int i = 0; i < n; i++) {
            cout << "P" << i << "\t";

            // 分配矩阵
            for (int j = 0; j < m; j++) {
                cout << setw(3) << allocation[i][j];
            }
            cout << "\t\t";

            // 最大需求矩阵
            for (int j = 0; j < m; j++) {
                cout << setw(3) << max[i][j];
            }
            cout << "\t\t";

            // 需求矩阵
            for (int j = 0; j < m; j++) {
                cout << setw(3) << need[i][j];
            }
            cout << endl;
        }
    }

    // 安全性检查，返回是否安全及安全序列
    bool safetyCheck(vector<int>& safeSequence) {
        vector<int> work = available; // 工作向量，初始值为Available
        vector<bool> finish(n, false); // 完成标记数组
        safeSequence.clear();

        cout << "\n=== 安全性检查过程 ===" << endl;
        cout << "初始工作向量Work：";
        for (int i = 0; i < m; i++) {
            cout << setw(4) << work[i];
        }
        cout << endl;

        int count = 0; // 已完成的进程数量

        // 循环查找可以完成的进程
        while (count < n) {
            bool found = false;

            for (int i = 0; i < n; i++) {
                // 如果进程i未完成且Need[i] <= Work
                if (!finish[i]) {
                    bool canFinish = true;
                    for (int j = 0; j < m; j++) {
                        if (need[i][j] > work[j]) {
                            canFinish = false;
                            break;
                        }
                    }

                    if (canFinish) {
                        // 进程i可以完成
                        cout << "进程P" << i << "可以完成，需求：";
                        for (int j = 0; j < m; j++) {
                            cout << setw(3) << need[i][j];
                        }
                        cout << " <= 工作向量：";
                        for (int j = 0; j < m; j++) {
                            cout << setw(3) << work[j];
                        }
                        cout << endl;

                        // 更新工作向量：Work = Work + Allocation[i]
                        for (int j = 0; j < m; j++) {
                            work[j] += allocation[i][j];
                        }

                        finish[i] = true;
                        safeSequence.push_back(i);
                        count++;
                        found = true;

                        cout << "完成后工作向量：";
                        for (int j = 0; j < m; j++) {
                            cout << setw(4) << work[j];
                        }
                        cout << endl << endl;
                        break;
                    }
                }
            }

            // 如果没有找到可以完成的进程，系统不安全
            if (!found) {
                cout << "无法找到可完成的进程，系统处于不安全状态！" << endl;
                return false;
            }
        }

        return true;
    }

    // 资源请求处理
    bool requestResources(int processId, vector<int>& request) {
        cout << "\n=== 处理进程P" << processId << "的资源请求 ===" << endl;
        cout << "请求向量Request：";
        for (int i = 0; i < m; i++) {
            cout << setw(4) << request[i];
        }
        cout << endl;

        // 步骤1：检查Request <= Need
        cout << "检查Request <= Need：";
        for (int i = 0; i < m; i++) {
            if (request[i] > need[processId][i]) {
                cout << "失败！请求超过需求量" << endl;
                return false;
            }
        }
        cout << "通过" << endl;

        // 步骤2：检查Request <= Available
        cout << "检查Request <= Available：";
        for (int i = 0; i < m; i++) {
            if (request[i] > available[i]) {
                cout << "失败！请求超过可用资源" << endl;
                return false;
            }
        }
        cout << "通过" << endl;

        // 步骤3：试探性分配
        cout << "进行试探性分配..." << endl;

        // 保存原始状态
        vector<int> originalAvailable = available;
        vector<vector<int>> originalAllocation = allocation;
        vector<vector<int>> originalNeed = need;

        // 修改系统状态
        for (int i = 0; i < m; i++) {
            available[i] -= request[i];
            allocation[processId][i] += request[i];
            need[processId][i] -= request[i];
        }

        cout << "试探性分配后的状态：" << endl;
        displaySystemState();

        // 步骤4：执行安全性检查
        vector<int> safeSequence;
        bool isSafe = safetyCheck(safeSequence);

        if (isSafe) {
            cout << "系统处于安全状态！" << endl;
            cout << "安全序列：";
            for (int i = 0; i < safeSequence.size(); i++) {
                cout << "P" << safeSequence[i];
                if (i < safeSequence.size() - 1) cout << " -> ";
            }
            cout << endl;
            cout << "资源分配成功！" << endl;
            return true;
        } else {
            // 恢复原始状态
            available = originalAvailable;
            allocation = originalAllocation;
            need = originalNeed;
            cout << "分配后系统不安全，拒绝分配，恢复原状态" << endl;
            return false;
        }
    }

    // 显示数据选择菜单
    void showDataMenu() {
        cout << "\n=== 选择测试数据或手动输入 ===" << endl;
        cout << "1. 使用测试数据集1（5进程3资源，安全状态）" << endl;
        cout << "2. 使用测试数据集2（3进程3资源，不安全状态）" << endl;
        cout << "3. 使用测试数据集3（2进程2资源，边界测试）" << endl;
        cout << "4. 手动输入系统参数和数据" << endl;
        cout << "请选择：";
    }

    // 显示菜单
    void showMenu() {
        cout << "\n=== 银行家算法菜单 ===" << endl;
        cout << "1. 显示当前系统状态" << endl;
        cout << "2. 安全性检查" << endl;
        cout << "3. 资源请求处理" << endl;
        cout << "4. 重新选择/输入系统数据" << endl;
        cout << "5. 测试推荐资源请求" << endl;
        cout << "0. 退出程序" << endl;
        cout << "请选择操作：";
    }

    // 提供推荐的测试请求
    void showRecommendedRequests() {
        cout << "\n=== 推荐的测试请求 ===" << endl;

        if (n == 5 && m == 3) {
            // 测试数据集1的推荐请求
            cout << "当前是测试数据集1，推荐测试请求：" << endl;
            cout << "1. P1请求(1,0,2) - 预期：被拒绝（超过可用资源）" << endl;
            cout << "2. P4请求(3,3,0) - 预期：被拒绝（超过可用资源）" << endl;
            cout << "3. P1请求(0,2,0) - 预期：可能被接受" << endl;
            cout << "4. P3请求(0,1,1) - 预期：应该被接受" << endl;
        } else if (n == 3 && m == 3) {
            // 测试数据集2的推荐请求
            cout << "当前是测试数据集2，推荐测试请求：" << endl;
            cout << "1. 任何进程的任何合理请求都会被拒绝，因为系统已经不安全" << endl;
            cout << "2. P0请求(1,0,0) - 预期：被拒绝" << endl;
            cout << "3. P1请求(0,1,0) - 预期：被拒绝" << endl;
        } else if (n == 2 && m == 2) {
            // 测试数据集3的推荐请求
            cout << "当前是测试数据集3，推荐测试请求：" << endl;
            cout << "1. P0请求(2,2) - 预期：应该被接受" << endl;
            cout << "2. P1请求(2,2) - 预期：应该被接受" << endl;
            cout << "3. P0请求(1,1) - 预期：应该被接受" << endl;
        } else {
            cout << "当前是自定义数据，请根据需求矩阵和可用资源设计测试请求。" << endl;
        }
    }

    // 数据选择和初始化
    void initializeData() {
        int choice;
        showDataMenu();
        cin >> choice;

        switch (choice) {
            case 1:
                loadTestData1();
                break;
            case 2:
                loadTestData2();
                break;
            case 3:
                loadTestData3();
                break;
            case 4:
                cout << "请输入进程数量：";
                cin >> n;
                cout << "请输入资源类型数量：";
                cin >> m;

                // 重新调整矩阵大小
                allocation.resize(n, vector<int>(m, 0));
                max.resize(n, vector<int>(m, 0));
                need.resize(n, vector<int>(m, 0));
                available.resize(m, 0);

                inputSystemState();
                break;
            default:
                cout << "无效选择，使用测试数据集1" << endl;
                loadTestData1();
                break;
        }
    }
    // 运行银行家算法主程序
    void run() {
        cout << "=== 银行家算法死锁避免实验 ===" << endl;

        // 数据选择和初始化
        initializeData();

        // 显示初始状态
        displaySystemState();

        int choice;
        do {
            showMenu();
            cin >> choice;

            switch (choice) {
                case 1: {
                    displaySystemState();
                    break;
                }
                case 2: {
                    vector<int> safeSequence;
                    bool isSafe = safetyCheck(safeSequence);
                    if (isSafe) {
                        cout << "系统处于安全状态！" << endl;
                        cout << "安全序列：";
                        for (int i = 0; i < safeSequence.size(); i++) {
                            cout << "P" << safeSequence[i];
                            if (i < safeSequence.size() - 1) cout << " -> ";
                        }
                        cout << endl;
                    } else {
                        cout << "系统处于不安全状态！" << endl;
                    }
                    break;
                }
                case 3: {
                    int processId;
                    cout << "请输入请求资源的进程ID（0-" << n-1 << "）：";
                    cin >> processId;

                    if (processId < 0 || processId >= n) {
                        cout << "无效的进程ID！" << endl;
                        break;
                    }

                    vector<int> request(m);
                    cout << "请输入请求的资源向量（" << m << "个值）：";
                    for (int i = 0; i < m; i++) {
                        cin >> request[i];
                    }

                    requestResources(processId, request);
                    break;
                }
                case 4: {
                    initializeData();
                    displaySystemState();
                    break;
                }
                case 5: {
                    showRecommendedRequests();
                    break;
                }
                case 0: {
                    cout << "感谢使用银行家算法程序！" << endl;
                    break;
                }
                default: {
                    cout << "无效选择，请重新输入！" << endl;
                    break;
                }
            }
        } while (choice != 0);
    }
};

int main() {
    // 创建银行家算法实例并运行
    BankersAlgorithm banker(0, 0);
    banker.run();
    return 0;
}