#include "colorizer.h"
#include <vector>
#include <algorithm>

#include <iostream>

bool is_colorable(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;
        }

    }

    return coloring_array[ColouringBitArray::Index(0,0)];
}


