#include <iostream>
#include <vector>
#include "gurobi_c++.h"

using namespace std;

int main(int, char**)
{
    // Small
    const int total_page_count = 5;
    const int pool_page_count = 2;
    const vector<int> page_accesses = {1,2,3,1};

    // Big
    // const int total_page_count = 200;
    // const int pool_page_count = 50;
    // const int page_access_count = 1000;
    // srand(321);
    // const vector<int> page_accesses = [](){ vector<int> res(page_access_count); for(auto& iter : res) { iter = rand()%total_page_count;} return res; }();

    try {
        GRBEnv env = GRBEnv();
        GRBModel model = GRBModel(env);

        // A bool for each step (page access) for each page
        vector<vector<GRBVar>> page_matrix;
        page_matrix.resize(page_accesses.size() + 1, vector<GRBVar>(total_page_count));

        // Add each field of the page matrix to the model
        for(auto& step : page_matrix) {
            for(auto& page : step) {
                page = model.addVar(0.0, 1.0, 0.0, GRB_BINARY);
            }
        }

        // Add constraints for the page accesses
        for(int s=0; s<page_accesses.size(); s++) {
            int accessed_page = page_accesses[s];
            string name = "access_" + to_string(s + 1);
            model.addConstr(page_matrix[s+1][accessed_page] == 1, name);
        }

        // Limit buffer pool size
        for(int s=0; s<page_matrix.size(); s++) {
            auto& step = page_matrix[s];
            GRBLinExpr expr = 0;
            for(int p=0; p<step.size(); p++) {
                expr += step[p];
            }
            string name = "pool_size_" + to_string(s);
            if(s == 0) {
                model.addConstr(expr == 0, name); // Start with empty pool
            } else {
                model.addConstr(expr <= pool_page_count, name);
            }
        }

        // Build objective function
        // ABS hack: https://math.stackexchange.com/questions/432003/converting-absolute-value-program-into-linear-program
        GRBLinExpr expr = 0;
        // for(int s=1; s<page_matrix.size(); s++) {
        //     auto& prev = page_matrix[s - 1];
        //     auto& cur = page_matrix[s];
        //     for(int p=0; p<cur.size(); p++) {
        //         string name = "aux_" + to_string(s) + "_" + to_string(p);
        //         GRBVar aux_1 = model.addVar(0.0, 1.0, 0.0, GRB_CONTINUOUS, name + "_1");
        //         model.addConstr(aux_1 == prev[p] - cur[p], "aux_constraint_" + name + "_1");
        //         GRBVar aux_2 = model.addVar(0.0, 1.0, 0.0, GRB_CONTINUOUS, name + "_2");
        //         model.addGenConstrAbs(aux_2, aux_1, "aux_constraint_" + name + "_2");
        //         expr += aux_2;
        //     }
        // }
        for(int s=1; s<page_matrix.size(); s++) {
            auto& prev = page_matrix[s - 1];
            auto& cur = page_matrix[s];
            for(int p=0; p<cur.size(); p++) {
                string name = "aux_" + to_string(s) + "_" + to_string(p);
                GRBVar t1 = model.addVar(0.0, 1.0, 0.0, GRB_BINARY, name + "_1");
                GRBVar t2 = model.addVar(0.0, 1.0, 0.0, GRB_BINARY, name + "_2");
                model.addConstr(t1 - t2 == prev[p] - cur[p], "aux_constraint_" + name);
                model.addConstr(t1 >= 0, "aux_constraint_" + name + "_1");
                model.addConstr(t2 >= 0, "aux_constraint_" + name + "_2");
                expr += t1 + t2;
            }
        }
        model.setObjective(expr, GRB_MINIMIZE);

        model.optimize();
        model.write("alex.lp");

        // Print page matrix
        int page_miss_count = 0;
        for(int s=0; s<page_matrix.size(); s++) {
            if(s == 0) {
                cout << s << " step (-): ";
            } else {
                cout << s << " step (" << page_accesses[s-1] << ")" << ": ";
            }
            for(int p=0; p<page_matrix[s].size(); p++) {
                double val = page_matrix[s][p].get(GRB_DoubleAttr_X); // .. not sure
                cout << (val == 1 ? 1 : 0)  << " ";
                assert((page_matrix[s][p].get(GRB_DoubleAttr_X) == 0) ^ (page_matrix[s][p].get(GRB_DoubleAttr_X) == 1));
                if(s > 0 && page_matrix[s-1][p].get(GRB_DoubleAttr_X) == 0 && page_matrix[s][p].get(GRB_DoubleAttr_X) == 1) {
                    page_miss_count++;
                }
            }
            cout << endl;
        }
        cout << "page_miss_count=" << page_miss_count << endl;
        cout << "done !" << endl;
    } catch(GRBException e) {
        cout << "Error code = " << e.getErrorCode() << endl;
        cout << e.getMessage() << endl;
    } catch (...) {
        cout << "Error during optimization" << endl;
    }

    return 0;
}