#include <basic_impl.hpp>

#include <cassert>
#include <map>
#include "colorizer.h"
#include <vector>

#include <algorithms/isomorphism/isomorphism_nauty.hpp>
#include <io/graph6.hpp>
#include <random/renumber.hpp>

#include <invariants.hpp>
#include <iostream>
#include <operations.hpp>
#include "algorithms/isomorphism/isomorphism_nauty.hpp"
#include "algorithms/isomorphism/automorphism_group.hpp"
#include "io/print_nice.hpp"
#include <nausparse.h>
#include <ctime>
#include <cstdio>
#include <algorithm>
#include <execution>
#include <utility>
#include <tuple>
#include <time.h>



using namespace ba_graph;


//std::vector<int>::iterator it;
int polePower3 [15];
int velkostSpravnychTrojic;
//std::map<int,unsigned char*> spravneTrojice;
std::map<int, std::vector<unsigned char>> spravneTrojice;
std::vector<unsigned long long int*> finalneFarbenia;
int vysledokJeRovnaky = 0;
unsigned long long int* spravnaMapa;

//upravena funkcia s colorizru, ktorá nám bude vraciať bitové pole všetkých ofarbení grafu a vector order
std::pair<ColouringBitArray, std::vector<std::pair<int, int>>> is_colored(std::vector<std::pair<int, int>> decomposition) {
    std::vector<std::pair<int, int>> order;
//as the second coordinate we save the degree of the vertex at step j
    ColouringBitArray coloring_array(1, true);

    //returns a function that checks if a vertex part of order is vertex
    auto vertex_is = [](int vertex) {return [=] (std::pair<int, int> element) {return element.first==vertex;};};


    for(auto p: decomposition) {
        auto it1 = std::find_if(order.begin(), order.end(), vertex_is(p.first));
        auto it2 = std::find_if(order.begin(), order.end(), vertex_is(p.second));
        auto degree = [&](auto it) { return (it==order.end()) ? 0 : it->second;};

        if (degree(it1) > degree(it2)) {std::swap(it1, it2); std::swap(p.first, p.second);}

        if (degree(it1) == 0 && degree(it2) == 0) {
            order.push_back({p.second, 1});
            order.push_back({p.first, 1});
            ColouringBitArray new_ca = coloring_array;
            auto newsize = coloring_array.size(); newsize+=newsize; newsize+=newsize; newsize+=newsize; newsize = coloring_array.size();
            new_ca.reserve(newsize);
            new_ca.concatenate_to_special(ColouringBitArray(coloring_array.size(), false));
            new_ca.concatenate_to_special(ColouringBitArray(coloring_array.size(), false));
            new_ca.concatenate_to_special(ColouringBitArray(coloring_array.size(), false));
            new_ca.concatenate_to_special(coloring_array);
            new_ca.concatenate_to_special(ColouringBitArray(coloring_array.size(), false));
            new_ca.concatenate_to_special(ColouringBitArray(coloring_array.size(), false));
            new_ca.concatenate_to_special(ColouringBitArray(coloring_array.size(), false));
            new_ca.concatenate_to_special(coloring_array);
            coloring_array = std::move(new_ca);
            continue;
        }

        if (degree(it1) == 0 && degree(it2) == 1) {
            int idx2 = it2-order.begin();
            order.erase(std::remove_if(order.begin(), order.end(), vertex_is(p.second)), order.end());
            order.push_back({p.second, 2});
            order.push_back({p.first, 1});
            auto [part0, part1, part2] = coloring_array.split3(idx2);
            coloring_array = ColouringBitArray(part0.size(), false);
            coloring_array.concatenate_to_special(part2);
            coloring_array.concatenate_to_special(part1);
            coloring_array.concatenate_to_special(part2);
            coloring_array.concatenate_to_special(ColouringBitArray(part0.size(), false));
            coloring_array.concatenate_to_special(part0);
            coloring_array.concatenate_to_special(part1);
            coloring_array.concatenate_to_special(part0);
            coloring_array.concatenate_to_special(ColouringBitArray(part0.size(), false));
            continue;
        }

        if (degree(it1) == 0 && degree(it2) == 2) {
            int idx2 = it2-order.begin();
            order.erase(std::remove_if(order.begin(), order.end(), vertex_is(p.second)), order.end());
            order.push_back({p.first, 1});
            auto [part0, part1, part2] = coloring_array.split3(idx2);
            coloring_array = std::move(part0);
            coloring_array.concatenate_to_special(part1);
            coloring_array.concatenate_to_special(part2);
            continue;
        }

        if (degree(it1) == 1 && degree(it2) == 1) {
            int idx1 = it1-order.begin();
            int idx2 = it2-order.begin();
            order.erase(std::remove_if(order.begin(), order.end(), vertex_is(p.first)), order.end());
            order.erase(std::remove_if(order.begin(), order.end(), vertex_is(p.second)), order.end());
            order.push_back({p.first, 2});
            order.push_back({p.second, 2});
            auto [part00, part01, part02, part10, part11, part12, part20, part21, part22] = coloring_array.split9(idx1, idx2);
            coloring_array = part11; coloring_array |= part22;
            coloring_array.concatenate_to_special(part01);
            coloring_array.concatenate_to_special(part02);
            coloring_array.concatenate_to_special(part10);
            part22|=part00;
            coloring_array.concatenate_to_special(part22);
            coloring_array.concatenate_to_special(part12);
            coloring_array.concatenate_to_special(part20);
            coloring_array.concatenate_to_special(part21);
            part11|=part00;
            coloring_array.concatenate_to_special(part11);
            continue;
        }


        if (degree(it1) == 1 && degree(it2) == 2) {
            int idx1 = it1-order.begin();
            int idx2 = it2-order.begin();
            order.erase(std::remove_if(order.begin(), order.end(), vertex_is(p.first)), order.end());
            order.erase(std::remove_if(order.begin(), order.end(), vertex_is(p.second)), order.end());
            order.push_back({p.first, 2});
            auto [part00, part01, part02, part10, part11, part12, part20, part21, part22] = coloring_array.split9(idx1, idx2);
            (void)part00;(void)part11;(void)part22;
            part12|=part21;
            coloring_array = part12;
            part02|=part20;
            coloring_array.concatenate_to_special(part02);
            part01|=part10;
            coloring_array.concatenate_to_special(part01);
            continue;
        }

        if (degree(it1) == 2 && degree(it2) == 2) {
            int idx1 = it1-order.begin();
            int idx2 = it2-order.begin();
            order.erase(std::remove_if(order.begin(), order.end(), vertex_is(p.first)), order.end());
            order.erase(std::remove_if(order.begin(), order.end(), vertex_is(p.second)), order.end());
            auto [part00, part01, part02, part10, part11, part12, part20, part21, part22] = coloring_array.split9(idx1, idx2);
            (void)part01;(void)part02;(void)part10;(void)part12;(void)part20;(void)part21;
            coloring_array = part00;
            coloring_array|=part11;
            coloring_array|=part22;
            continue;
        }

    }
/*for (auto const& i : order){
    std::cout << i.first <<" "<< i.second << "\n";
}*/
return std::pair(coloring_array,order);
}


Graph Kruznica(){
    Graph G(circuit(7));
    return G;
}


int power(int zaklad, int exponent){
    int pomoc = 1;
    for (int i=0; i< exponent; i++){
        pomoc = pomoc * zaklad;
    }
    return pomoc;
}

//premapovanie vrcholov stupna 2 pre grafy s piatimi zapojenými kružnicami
std::vector<std::pair<int, int>> graph_to_order (Graph &G){
    std::vector<std::pair<int, int>> order;
    std::map<int,int> prechodovaMapa;
    int vrcholVkruznici = 0;
    int pocet3 =15;
    for (auto &v : G){
        if(v.degree() == 2){
            prechodovaMapa[v.n().to_int()] = vrcholVkruznici;
            vrcholVkruznici ++;
        } else {
            prechodovaMapa[v.n().to_int()] = pocet3;
            pocet3++;
        }
    }
    for (auto ii : G.list(RP::all(), IP::primary())) {

        order.push_back(std::pair( prechodovaMapa[ii->n1().to_int()], prechodovaMapa[ii->n2().to_int()]));
    }
    return order;
}

//premapovanie vrcholov stupna 2 pre grafy s tromi zapojenými kružnicami
std::vector<std::pair<int, int>> graph_to_order2 (Graph &G){

    std::vector<std::pair<int, int>> order;
    std::map<int,int> prechodovaMapa;
    int vrcholVkruznici = 0;
    int pocet3 =15;
    for (auto &v : G){
        if(v.degree() == 2){
            prechodovaMapa[v.n().to_int()] = vrcholVkruznici/5 + (vrcholVkruznici%5)*3;
            vrcholVkruznici ++;
        } else {
            prechodovaMapa[v.n().to_int()] = pocet3;
            pocet3++;
        }
    }
    for (auto ii : G.list(RP::all(), IP::primary())) {
        order.push_back(std::pair( prechodovaMapa[ii->n1().to_int()], prechodovaMapa[ii->n2().to_int()]));
    }
    return order;
}

//pomocná funkcia na premapovanie indexu
int premapovanieOrderu( std::vector<unsigned char> pole, int  poleOrder [] ){
    int pom=0;
    for (int i=0; i<15; i++){
        pom = pom + pole[i] * polePower3[poleOrder[i]];
    }
    return pom;
}

//funckia, ktorá zabezpečuje premapovanie všetkých ofarbení grafu do podoby 64 bitových slov
unsigned long long int* convertCBA (ColouringBitArray &CBA,  std::map<int,std::vector<unsigned char>> &spravneTrojice,  int poleOrder[], unsigned long long int* spravnaMapa ) {
    int pocet = 0;
    unsigned long long int pom;
    unsigned long long int pom1;

    int premapovanyIndex;
     int pocetJednotiek = 0;

    bool overOrder = false;
    for (int i=0; i<15; i++){
        overOrder = poleOrder[i] != i;
        if (overOrder){
            break;
        }
    }

    for (auto const &i : spravneTrojice) {
        if (pocet % 64 == 0) {
            pom = 0;
            pom1 = 1;
        } else {
            pom1 = pom1 << 1;
        }
        if(overOrder) {
            premapovanyIndex = premapovanieOrderu(i.second, poleOrder);
            if (CBA[ColouringBitArray::Index(premapovanyIndex / 27, premapovanyIndex % 27)] == 1) {
                pom = pom | pom1;
                pocetJednotiek++;
            }
        } else {
            if (CBA[ColouringBitArray::Index(i.first / 27, i.first % 27)] == 1) {
                pom = pom | pom1;
                pocetJednotiek++;
            }
        }

        pocet++;
        if (pocet % 64 == 0) {
            spravnaMapa[(pocet / 64) -1] = pom;
        }
    }
    if(pocet%64 !=0){
        spravnaMapa[pocet/64] = pom;
    }
    //std::cout <<"VelkostSpravnychTrojic : "<<velkostSpravnychTrojic<<" | "<< pocetJednotiek <<" \n";
    return spravnaMapa;
}

//pomocné funkcie na overenie či sú 2 farbenia rovnaké
int suRovnake ( unsigned long long int* mapa1, unsigned long long int* &mapa2){
    int pom = 1;
    for(int i=0; i< velkostSpravnychTrojic; i++){

        if((mapa1[i] ^ mapa2[i]) != 0){

            if((mapa1[i]!=(mapa1[i] & mapa2[i]))){
                pom = 2;
            } else {
                pom = 0;
                break;
            }

        }
    }
    return pom;
}

bool jeRovnaky (unsigned long long int* graf1){
    vysledokJeRovnaky = 0;
    std::for_each(std::execution::seq, finalneFarbenia.begin(), finalneFarbenia.end(), [graf1](unsigned long long int* &graf2) {
        vysledokJeRovnaky = vysledokJeRovnaky + suRovnake(graf1, graf2);
    });
    return (vysledokJeRovnaky > 0);
}

// funkcie ktoré služia na overenie zafarbiiteňosti
bool suZafarbitelne (unsigned long long int graf1[],  unsigned long long int graf2 []){
    unsigned long long int pom;
    for (int i=0; i<velkostSpravnychTrojic;i++) {
        pom = graf1[i] & graf2[i];
        if (pom != 0) {
            break;
        }
    }
    return (pom != 0);
}

std::vector<bool> jeZafarbitelny (unsigned long long int graf1 [], std::vector<unsigned long long int*> &zoznamGrafov2){
    std::vector<bool> vysledok;
    for (auto graf2: zoznamGrafov2){
        vysledok.push_back(suZafarbitelne(graf1,graf2));
    }
    return vysledok;
}

//paralelné prechádzanie zoznamu
void paralelnePrechadzanieZoznamu (std::vector<std::string> &zoznamNacitanychGrafov){
    std::for_each(std::execution::par, zoznamNacitanychGrafov.begin(), zoznamNacitanychGrafov.end(), [](std::string &nacitanyGraf) {
        Graph g1 (read_sparse6(nacitanyGraf.begin()+1, nacitanyGraf.end()));

        std::pair<ColouringBitArray,std::vector<std::pair<int, int>>> pokus;
        pokus = is_colored(graph_to_order(g1));

        int poleOrder[15];
        int pocet = 0;
        for (auto i : pokus.second) {
            poleOrder[i.first] = pocet;
            pocet++;
        }

        for (auto i :  jeZafarbitelny(convertCBA(pokus.first, spravneTrojice, poleOrder,spravnaMapa), finalneFarbenia)) {
            if (i) {
                continue;
            } else {
                std::cout << "nasiel som nezafarbitleny: " << nacitanyGraf << "\n";
                break;
            }

        }
    });
}

int main(int argc, char* argv[])
{
    int t0 = time(NULL);


    if (argc<10) {
        printf("Too few args.\n");
        exit(1);
    }

    int from3 = atoi(argv[1]);
    int to3 = atoi(argv[2]);
    int step3 = atoi(argv[3]);
    std::string vstupnySubor3 = argv[4];
    int from5 = atoi(argv[5]);
    int to5 = atoi(argv[6]);
    int step5 = atoi(argv[7]);
    std::string vstupnySubor5 = argv[8];
    int pararelyzedFragment = atoi(argv[9]);

    std::ifstream fin3(vstupnySubor3);
    if (!fin3)
        throw std::runtime_error("cannot read file ");

    std::ifstream fin5(vstupnySubor5);
    if (!fin5)
        throw std::runtime_error("cannot read file ");

    std::string line;
    int count3 = 0;
    int count5 = 0;

    //pole obsahujúce mocniny 3
    polePower3[0] = 1;
    for(int i=1; i<15; i++){
        polePower3[i]= polePower3[i-1]*3;
    }


    unsigned char poleTrojic [243][8];
    for(int i = 0; i < 243; i++) {
        for (int j = 0; j < 3; j++) {
            poleTrojic[i][j] = 0;
        }
        int pom = i;
        for (int j = 0; j < 5; j++) {
            poleTrojic[i][7 - j] = pom % 3;
            poleTrojic[i][pom % 3]++;
            pom /= 3;
        }
    }
    std::vector<unsigned char> hodnota(15);
      for (int i=0; i<243; i++){
          for (int j=0; j<243; j++){
              for (int k=0; k<243; k++){
                  //parity check
                  if(((poleTrojic[i][0]+poleTrojic[j][0]+poleTrojic[k][0]) & 1) == 1 && ((poleTrojic[i][1]+poleTrojic[j][1]+poleTrojic[k][1]) & 1) == 1 &&
                          ((poleTrojic[i][2]+poleTrojic[j][2]+poleTrojic[k][2]) & 1) ==1){
                      for(int l=0; l<5; l++){
                          hodnota[l] = poleTrojic[k][7-l];
                          hodnota[l+5] = poleTrojic[j][7-l];
                          hodnota[l+10] = poleTrojic[i][7-l];
                      }
                      spravneTrojice[((i*243 + j)*243 + k)] = hodnota;
                  }
              }
          }
      }


    unsigned char pomocnePole [6][3] = {{0,1,2},{0,2,1},{1,0,2},{1,2,0},{2,0,1},{2,1,0}};

      //odstránenie permutácií farbenia
    for(auto const& i : spravneTrojice){
        for(int j=1; j<6; j++){
            int pom=0;

            for (int k=0; k<15; k++){
                pom = (pom << 1) + pom;
                pom = pom + pomocnePole[j][i.second[14-k]];
            }
            spravneTrojice.erase(pom);
        }
    }
    int t1 = time(NULL);

    velkostSpravnychTrojic =spravneTrojice.size()/64;
    if ((velkostSpravnychTrojic < 6) < spravneTrojice.size()){
        velkostSpravnychTrojic++;
    }

    std::vector<unsigned long long int> spravnaMapaVektor(velkostSpravnychTrojic);
    spravnaMapa = spravnaMapaVektor.data();

    //zmysluplné permutácie vrcholov 0 až 14 pre napojenie grafov s piatimi a tromi kružnicami
    int pomocnePolePermutacie[7776][15];
    for(unsigned char i1=0; i1<6; i1++){
        int j1 = i1*6;
        for(unsigned char i2=0; i2<6; i2++){
            int j2 = (j1+i2)*6;
            for(unsigned char i3=0; i3<6; i3++){
                int j3 = (j2+i3)*6;
                for(unsigned char i4=0; i4<6; i4++){
                    int j4 = (j3+i4)*6;
                    for(unsigned char i5=0; i5<6; i5++){
                        pomocnePolePermutacie[j4+i5][0] = pomocnePole[i1][0];
                        pomocnePolePermutacie[j4+i5][1] = pomocnePole[i1][1];
                        pomocnePolePermutacie[j4+i5][2] = pomocnePole[i1][2];
                        pomocnePolePermutacie[j4+i5][3] = pomocnePole[i2][0]+3;
                        pomocnePolePermutacie[j4+i5][4] = pomocnePole[i2][1]+3;
                        pomocnePolePermutacie[j4+i5][5] = pomocnePole[i2][2]+3;
                        pomocnePolePermutacie[j4+i5][6] = pomocnePole[i3][0]+6;
                        pomocnePolePermutacie[j4+i5][7] = pomocnePole[i3][1]+6;
                        pomocnePolePermutacie[j4+i5][8] = pomocnePole[i3][2]+6;
                        pomocnePolePermutacie[j4+i5][9] = pomocnePole[i4][0]+9;
                        pomocnePolePermutacie[j4+i5][10] = pomocnePole[i4][1]+9;
                        pomocnePolePermutacie[j4+i5][11] = pomocnePole[i4][2]+9;
                        pomocnePolePermutacie[j4+i5][12] = pomocnePole[i5][0]+12;
                        pomocnePolePermutacie[j4+i5][13] = pomocnePole[i5][1]+12;
                        pomocnePolePermutacie[j4+i5][14] = pomocnePole[i5][2]+12;
                    }
                }
            }
        }
    }
    int t2 = time(NULL);
    std:: cout<< "time2 = "<< t2 - t0 << " | " << t2-t1 <<  "\n";


    std::pair<ColouringBitArray,std::vector<std::pair<int, int>>> pokus2;

    while (std::getline(fin3, line)) {
        ++count3;
        if (count3 > to3 && to3 > 0)
            break;
        if (count3 < from3) continue;
        if (count3 % step3 != from3 % step3) continue;
        Graph g2 (read_sparse6(line.begin()+1, line.end()));



        std::vector<std::pair<int, int>> graph2 = graph_to_order2(g2);

        pokus2 = is_colored(graph2);


        int pocet = 0;
        std::map<int,int> mapOrder;
        for (auto i : pokus2.second){
            mapOrder[i.first] = pocet;
            pocet++;
        }

        int poleOrder[15];
        //vyskúšanie všetkých permutácií
        for(int i=0; i< power(6,5); i++){
            for(int j =0; j<15; j++){
                poleOrder[j] = mapOrder[pomocnePolePermutacie[i][j]];
            }
            finalneFarbenia.push_back(convertCBA(pokus2.first, spravneTrojice, poleOrder,spravnaMapa));

        }

        int t3 = time(NULL);
        std:: cout<< "time3 = "<< t3 - t0 << " | " << t3-t2 <<  "\n";
        t2 = t3;
    }
    fin3.close();




    int t5;
    std::vector<std::string> zoznamNacitanychGrafov;
    while (std::getline(fin5, line)) {
        ++count5;
        if (count5 > to5 && to5 > 0)
            break;
        if (count5 < from5) continue;
        if (count5 % step5 != from5 % step5)continue;
        //std::cout << count5 << " ";
        zoznamNacitanychGrafov.push_back(line);
        if(zoznamNacitanychGrafov.size() < pararelyzedFragment){
            continue;
        }
        paralelnePrechadzanieZoznamu(zoznamNacitanychGrafov);
        zoznamNacitanychGrafov.clear();


            t5 = time(NULL);
            std::cout << "time5 = "<<"(" << count5 << ")  " << t5 - t0 << " | " << t5 - t2 << "\n";
            t2 = t5;

    }
    paralelnePrechadzanieZoznamu(zoznamNacitanychGrafov);

    fin5.close();
    int tFinal = time(NULL);
    std::cout << "timeFinal = " << tFinal - t0 << "\n";


}