#include <iostream>
#include <vector>
#include <iomanip>
#include <chrono>

#include <omp.h>

using Gens=std::vector<int>;
using Table=std::vector<Gens>;

struct Mult {
    int from, to, multiplicity;
    Mult() {}
    Mult(int from, int to, int multiplicity): from(from), to(to), multiplicity(multiplicity) {}
};

Table mults(const std::vector<Mult>& ms) {
    Table res;
    for (const auto &m : ms) {
        int N = res.size();
        res.emplace_back(m.multiplicity * 2, m.to);
        for (int i = 0; i < m.multiplicity * 2; i += 2) {
            res[N][i] = m.from;
        }
    }
    return res;
}

std::vector<Mult> ezmults(int ngens, const std::vector<Mult> &ms) {
    bool table[ngens][ngens];

    for (int i = 0; i < ngens; i++) {
        for (int j = 0; j < ngens; j++) {
            table[i][j] = false;
        }
    }

    for (const auto &m : ms) {
        table[m.from][m.to] = true;
        table[m.to][m.from] = true;
    }

    std::vector<Mult> res(ms);

    for (int i = 0; i < ngens; i++) {
        for (int j = i + 1; j < ngens; j++) {
            if (!table[i][j]) {
                res.push_back({i, j, 2});
            }
        }
    }

    return res;
}

/*
 * Order 4*res*res
 */
std::pair<Table, int> torus(int res) {
    return std::make_pair(mults(ezmults(4, {
        {0, 1, res},
        {2, 3, res},
    })), 4);
}

std::pair<Table, int> hypercube(int dim) {
    std::vector<Mult> hc_mults;
    hc_mults.emplace_back(0,1,4);
    for (int i = 2; i < dim; i++) {
        hc_mults.emplace_back(i-1, i, 3);
    }
    return std::make_pair(mults(ezmults(dim,hc_mults)), dim); 
}

/*
 * Order 14,400
 */
std::pair<Table, int> H4() {
    return std::make_pair(mults(ezmults(4, {
        {0, 1, 5},
        {1, 2, 3},
        {2, 3, 3},
    })), 4);
}

/*
 * Order 51,840
 */
std::pair<Table, int> E6() {
    return std::make_pair(mults(ezmults(6, {
        {0, 1, 3},
        {1, 2, 3},
        {2, 3, 3},
        {2, 4, 3},
        {4, 5, 3},
    })), 6);
}

/*
 * Order 2,903,040
 */
std::pair<Table, int> E7() {
    return std::make_pair(mults(ezmults(7, {
        {0, 1, 3},
        {1, 2, 3},
        {2, 3, 3},
        {2, 4, 3},
        {4, 5, 3},
        {5, 6, 3},
    })), 7);
}

/*
 * Order 696,729,600
 */
std::pair<Table, int> E8() {
    return std::make_pair(mults(ezmults(8, {
        {0, 1, 3},
        {1, 2, 3},
        {2, 3, 3},
        {2, 4, 3},
        {4, 5, 3},
        {5, 6, 3},
        {6, 7, 3},
    })), 8);
}

void pp(const Gens &g, int w) {
    for (const auto &e : g) {
        std::cout << std::setw(w) << e << " ";
    }
    std::cout << std::endl;
}

void pp(const Table &t) {
    std::cout << "| table:" << std::endl;
    int w = 3;

    for (size_t i = 0; i < t.size(); ++i) {
        std::cout << std::setw(w) << i << " | ";
        pp(t[i], w);
    }
}

void add_row(const int ngens, const std::vector<Gens> &rels,
    Table &cosets, std::vector<Table> &reltables,
    Table &starts, Table &ends) {

    int C = cosets.size();

    cosets.emplace_back(ngens, -1);

    for (unsigned int i = 0; i < rels.size(); ++i) {
        auto &table = reltables[i];

        unsigned int R = rels[i].size();

        table.emplace_back(R + 1, -1);
        table[C][0] = C;
        table[C][R] = C;

        starts[i].push_back(0);
        ends[i].push_back(R);
    }
}

int add_coset(const int ngens, const std::vector<Gens> &rels,
    Table &cosets, std::vector<Table> &reltables,
    Table &starts, Table &ends,
    int coset_scan_hint) {

    int C = cosets.size();

    for (int c = coset_scan_hint; c < C; ++c) {
        std::vector<int> &row = cosets[c];
        for (int g = 0; g < ngens; ++g) {
            if (row[g] == -1) {
                row[g] = C;
                add_row(ngens, rels, cosets, reltables, starts, ends);
                cosets[C][g] = c;
                return c;
            }
        }
    }

    return -1;
}


/**
 * learn until it can't
 */
void learn(Table &coset, const std::vector<Gens> &rels,
    std::vector<Table> &reltables, Table &starts, Table &ends) {

    unsigned int nrels = rels.size();

    while (true) {
        bool complete = true;

#pragma omp parallel for schedule(static, 1) reduction(&:complete)
        for (unsigned int r = 0; r < nrels; ++r) {
            auto &table = reltables[r];
            const auto &rel = rels[r];

            for (unsigned int c = 0; c < table.size(); c++) {
                auto &row = table[c];
                auto s = starts[r][c];
                auto e = ends[r][c];

                if (s == e - 1) continue;

                while (row[s + 1] == -1) {
                    const int &lookup = coset[row[s]][rel[s]];
                    if (lookup < 0) break;

                    s++;
                    row[s] = lookup;
                }

                while (row[e - 1] == -1) {
                    const int &lookup = coset[row[e]][rel[e - 1]];
                    if (lookup < 0) break;

                    e--;
                    row[e] = lookup;
                }

                if (s == e - 1) {
                    complete = false;

                    const int &gen = rel[s];
                    coset[row[s]][gen] = row[e];
                    coset[row[e]][gen] = row[s];
                }

                starts[r][c] = s;
                ends[r][c] = e;
            }
        }

        if (complete) break;
    }
}

Table solve_tc(int ngens, const Gens &subgens, const std::vector<Gens> &rels) {
    Table cosets;
    std::vector<Table> reltables(rels.size());

    // storing progress for each relation table row
    Table starts(rels.size()); // [rel_table][coset]
    Table ends(rels.size());

    // set up initial coset
    add_row(ngens, rels, cosets, reltables, starts, ends);
    for (const auto &gen : subgens) {
        cosets[0][gen] = 0;
    }

    int coset_scan_hint = 0;
    while (coset_scan_hint >= 0) {
        learn(cosets, rels, reltables, starts, ends);
        coset_scan_hint = add_coset(ngens, rels, cosets, reltables, starts, ends, coset_scan_hint);
    }

    return cosets;
}

int main(int argc, const char *argv[]) {
    if (argc < 2) {
        std::cerr << "missing type argument." << std::endl;
        return 1;
    }

    int type = std::strtol(argv[1], nullptr, 10);
    int arg = -1;
    std::pair<Table, int> res;
    switch (type) {
    case 0:
        if (argc < 3) {
            std::cerr << "Must provide a size for torus!" << std::endl;
            return 2;
        }
        arg = std::strtol(argv[2], nullptr, 10);
        res = torus(arg);
        break;
    case 1:
        res = H4();
        break;
    case 2:
        res = E6();
        break;
    case 3:
        res = E7();
        break;
    case 4:
        res = E8();
        break;
    case 5:
        if (argc < 3) {
            std::cerr << "Must provide a dimension for hypercube!" << std::endl;
            return 3;
        }
        arg = std::strtol(argv[2], nullptr, 10);
        res = hypercube(arg);
        break;
    default:
        std::cerr << "Not a valid type!" << std::endl;
        return 3;
    }

    const Table &rels = res.first;
    const int ngens = res.second;

    auto s = std::chrono::system_clock::now();
    auto cosets = solve_tc(ngens, {}, rels);
    auto e = std::chrono::system_clock::now();

    std::chrono::duration<float> diff = e - s;
    size_t order = cosets.size();

    // ngens,type,arg,time,order
    std::cout << type << ',' << arg << ',' << ngens << ',' << diff.count() << ',' << order << std::endl;

    return 0;
}