#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <iomanip>
#include <random>
#include <memory>
#include <chrono>
#include "SDL2\SDL.h"
#include "SDL2\SDL_ttf.h"
using namespace std;

default_random_engine engine;
SDL_Window* window1{ nullptr }, *window2{ nullptr };
SDL_Renderer* renderer1{ nullptr }, *renderer2{ nullptr };
TTF_Font* font{ nullptr };
constexpr int winWidth{ 1100 };
constexpr int winHeight{ 840 };
constexpr int cellsN{ 20 };
constexpr int cellsPixelSize{ 22 };
constexpr int padding{ 1 };
vector<SDL_Texture*>numbers;

struct Cell {
    int row{};
    int col{};
};

struct TreeNode {
    int parent;
    vector<int> childrenList;
};

class Union
{
    int cellsN;
    vector<vector<bool>> state;
    vector<TreeNode> tree;
    vector<int> treeSize;
    map<int, set<int>> treeDepth;
    vector<int> offList;
    set<int> startPoints;
    map<int, SDL_Color> colors;

    Cell getRandomOffSite();
    void connect(const Cell& first, const Cell& second);
    TreeNode& root(const TreeNode& node);
    int getIdDepth(int);
    void updateDepthMap(int smallerNodeID, int biggerNodeID);
    void _updateChildrenDepth(int smallerNodeID, int removeOffest, int AddOffset);
public:
    Union(int size)
        :cellsN{ size },
        state(cellsN, vector<bool>(cellsN, false)),
        tree(cellsN*cellsN),
        treeSize(cellsN*cellsN, 1),
        offList(cellsN*cellsN)
    {
        for (int id = 0; id < tree.size(); id++) {
            tree[id].parent = offList[id] = id;
            treeDepth[0].insert(id);
        }
    }

    void drawState();
    void drawUnionGraph();
    void openSite();
    void degubPrintUnionState();
    void degubPrintDepthMap();
};

void errorCheck(bool);

int main(int argc, char* argv[])
{
    engine.seed(chrono::steady_clock::now().time_since_epoch().count());

    errorCheck(!SDL_Init(SDL_INIT_EVERYTHING));


    window1 = SDL_CreateWindow("Percolation Test",
                               10, SDL_WINDOWPOS_CENTERED,
                               winWidth, winHeight,
                               SDL_WINDOW_SHOWN);
    window2 = SDL_CreateWindow("UnionGraph Diplay",
                               800, SDL_WINDOWPOS_CENTERED,
                               winWidth, winHeight,
                               SDL_WINDOW_SHOWN);
    errorCheck(window1);
    errorCheck(window2);

    renderer1 = SDL_CreateRenderer(window1, -1, SDL_RENDERER_ACCELERATED | SDL_RENDERER_PRESENTVSYNC);
    renderer2 = SDL_CreateRenderer(window2, -1, SDL_RENDERER_ACCELERATED | SDL_RENDERER_PRESENTVSYNC);
    errorCheck(renderer1);
    errorCheck(renderer2);

    errorCheck(!TTF_Init());


    ///////////////////////////////////////////////////////////
    string fontPath = "Z:\\Asus\\Documenti\\Visual Studio 2017\\Percolation_Test\\Percolation_Test\\font\\arial.ttf";

    font = TTF_OpenFont(fontPath.c_str(), 10);
    errorCheck(font);

    numbers.resize(cellsN*cellsN);
    SDL_Color textColor{ 0,0,0,255 };
    for (size_t i = 0; i < numbers.size(); i++)
    {
        numbers[i] = nullptr;
        SDL_Surface* surface = TTF_RenderText_Blended(font, to_string(i).c_str(), textColor);
        numbers[i] = SDL_CreateTextureFromSurface(renderer2, surface);
        SDL_FreeSurface(surface);
    }

    SDL_Event event;
    auto myUnion = make_unique<Union>(cellsN);

    while (true)
    {
        SDL_PollEvent(&event);
        switch (event.type)
        {
            case SDL_KEYDOWN:
            {
                auto key = event.key.keysym.sym;
                if (key == SDLK_ESCAPE) {
                    myUnion = make_unique<Union>(cellsN);
                }

                if (key == SDLK_SPACE) {
                    SDL_Event wait{};
                    myUnion->degubPrintDepthMap();
                    while (wait.key.keysym.sym != SDLK_SPACE) {
                        SDL_PollEvent(&wait);
                    }
                }
            }
        }

        //draw
        SDL_SetRenderDrawColor(renderer1, 0, 0, 0, 255);
        SDL_SetRenderDrawColor(renderer2, 111, 0, 0, 255);
        SDL_RenderClear(renderer1);
        SDL_RenderClear(renderer2);

        myUnion->drawState();
        myUnion->drawUnionGraph();

        SDL_RenderPresent(renderer1);
        SDL_RenderPresent(renderer2);

        //update
        myUnion->openSite();

        //pause
        //SDL_Delay(400);
    }

    SDL_DestroyWindow(window1);
    SDL_DestroyWindow(window2);
    SDL_DestroyRenderer(renderer1);
    SDL_DestroyRenderer(renderer2);
    if (font) { TTF_CloseFont(font); }
    if (TTF_WasInit())TTF_Quit();
    for (auto p : numbers) {SDL_DestroyTexture(p);}
    SDL_Quit();
    return 0;
}
///////////////////////////////////////////////////////////

void errorCheck(bool b) {
    if (!b) {
        cout << SDL_GetError() << endl;
        exit(EXIT_FAILURE);
    }
}

void Union::drawState()
{
    int totalPadding = padding * (cellsN - 1);
    int totalGridSize = cellsN * cellsPixelSize;
    int offsetX = (winWidth - (totalGridSize + totalPadding)) / 2;
    int offsetY = (winHeight - (totalGridSize + totalPadding)) / 2;
    SDL_Rect rect{ offsetX ,offsetY, cellsPixelSize,cellsPixelSize };
    SDL_Color white{ 255,255,255,255 }, lightBlue{ 30,120,220,255 }, clr{};

    for (size_t i = 0; i < tree.size(); i++)
    {
        int row = i / cellsN;
        int col = i % cellsN;

        //is openSite?
        if (state[row][col])
        {
            //calculate cell position on screen
            int y = row * cellsPixelSize + row * padding;
            int x = col * cellsPixelSize + col * padding;
            rect.x = offsetX + x;
            rect.y = offsetY + y;

            //has a way to reach the top line?
            int rootOfID = root(tree[i]).parent;
            if (startPoints.find(rootOfID) != startPoints.end()) { clr = colors[rootOfID]; }
            else { clr = white; }

            SDL_SetRenderDrawColor(renderer1, clr.r, clr.g, clr.b, clr.a);
            SDL_RenderFillRect(renderer1, &rect);
        }
    }
}

void Union::drawUnionGraph()
{
    int borderH{ 20 }, borderV{ 20 };
    int innerBorder{ 10 };
    SDL_Rect client = { borderH, borderV, winWidth - borderH * 2, winHeight - borderV * 2 };

    //background
    SDL_SetRenderDrawColor(renderer2, 90, 90, 90, 255);
    SDL_RenderFillRect(renderer2, &client);

    int nodeWidth{ 30 }, nodeHeight{ 20 };
    int halfNodeW{ nodeWidth / 2 }, halfNodeH{ nodeHeight / 2 };
    SDL_Rect element{ 0,0,nodeWidth,nodeHeight };
    int depth = treeDepth.size();

    int currDepth{};
    for (auto&[Key, Set] : treeDepth)
    {
        int setSize = Set.size();
        int strideX = (client.w - innerBorder * 2) / setSize;
        int strideY = client.h / depth;
        int x = (client.x + innerBorder + strideX / 2) - halfNodeW;
        int y = (client.y + strideY / 2) - halfNodeH;

        element.x = x - strideX;
        element.y = y + strideY * currDepth;
        for (auto val : Set)
        {
            element.x += strideX;

            //element fill
            SDL_SetRenderDrawColor(renderer2, 255, 255, 255, 255);
            SDL_RenderFillRect(renderer2, &element);
            //element border
            SDL_SetRenderDrawColor(renderer2, 0, 0, 0, 255);
            SDL_RenderDrawRect(renderer2, &element);
            //number

            SDL_Rect textSize{ element.x + 7, element.y + 5, 0, 0 };
            TTF_SizeText(font, to_string(val).c_str(), &textSize.w, &textSize.h);
            SDL_RenderCopy(renderer2, numbers[val], NULL, &textSize);
        }

        //connection line
        if (currDepth != 0) {
            float p1_x = x +halfNodeW;
            float p1_y = element.y;
            float upperRowStrideX = (client.w - innerBorder * 2) / treeDepth[currDepth - 1].size();
            float upperRowX = (client.x + innerBorder + upperRowStrideX / 2) - halfNodeW;
            float p2_x{};
            float p2_y = y + nodeHeight + strideY * (currDepth - 1);

            for (auto val : Set)
            {
                int position{};
                for (auto other : treeDepth[currDepth - 1]) {
                    if (tree[val].parent == other) { break; }
                    position++;
                }

                p2_x = upperRowX + halfNodeW + (upperRowStrideX * position);
                SDL_RenderDrawLine(renderer2, p1_x, p1_y, p2_x, p2_y);
                p1_x += strideX;
            }
        }


        element.y += strideY;
        currDepth++;
    }


}

Cell Union::getRandomOffSite() {
    Cell cell{};
    if (!offList.empty())
    {
        uniform_int_distribution<int> distribution(0, offList.size() - 1);
        int randomID = distribution(engine);
        int site = offList[randomID];
        offList.erase(offList.begin() + randomID);
        cell.row = site / cellsN;
        cell.col = site % cellsN;
    }
    return cell;
}

void Union::openSite()
{
    Cell cell = getRandomOffSite();
    state[cell.row][cell.col] = true;

    if (cell.row == 0) {
        startPoints.insert(cell.col);
        uniform_int_distribution<int> c(20, 220);
        colors[cell.col] = SDL_Color{ (Uint8)c(engine), (Uint8)c(engine), (Uint8)c(engine), 255 };
    }

    connect(cell, Cell{ cell.row - 1, cell.col });//UP
    connect(cell, Cell{ cell.row    , cell.col + 1 });//RIGHT
    connect(cell, Cell{ cell.row + 1, cell.col });//DOWN
    connect(cell, Cell{ cell.row    , cell.col - 1 });//LEFT
}

void Union::connect(const Cell& first, const Cell& second)
{
    //first is expected to be valid
    if (second.row >= 0 && second.row < cellsN &&
        second.col >= 0 && second.col < cellsN)
    {
        if (state[second.row][second.col])
        {
            int firstID = (first.row * cellsN) + first.col;
            int secondID = (second.row * cellsN) + second.col;

            int rootA = root(tree[firstID]).parent;
            int rootB = root(tree[secondID]).parent;
            auto tempPair = minmax(rootA, rootB, [&](int lhs, int rhs) {return treeSize[lhs] < treeSize[rhs]; });

            TreeNode& rootSmaller = tree[tempPair.first];
            TreeNode& rootBigger = tree[tempPair.second];


            int& rootSmallerID = rootSmaller.parent;
            int& rootBiggerID = rootBigger.parent;

            if (rootSmallerID != rootBiggerID)
            {
                if (startPoints.find(rootSmallerID) != startPoints.end())
                {
                    startPoints.erase(rootSmallerID);
                    startPoints.insert(rootBiggerID);

                    //if rootBigger has no color, then is not connected to the top. Keep smaller color.
                    if (colors.find(rootBiggerID) == colors.end())
                    {
                        colors[rootBiggerID] = colors[rootSmallerID];
                    }
                }

                rootBigger.childrenList.push_back(rootSmallerID);

                updateDepthMap(rootSmallerID, rootBiggerID);

                rootSmallerID = rootBiggerID;
                treeSize[rootBiggerID] += treeSize[rootSmallerID];
            }
        }
    }
}
void Union::updateDepthMap(int smallerNodeID, int biggerNodeID)
{
    int smallerNodeDepth = getIdDepth(smallerNodeID);
    int biggerNodeDepth = getIdDepth(biggerNodeID);
    treeDepth[smallerNodeDepth].erase(smallerNodeID);
    treeDepth[biggerNodeDepth + 1].insert(smallerNodeID);

    _updateChildrenDepth(smallerNodeID, smallerNodeDepth + 1, biggerNodeDepth + 2);
}
void Union::_updateChildrenDepth(int smallerNodeID, int removeOffest, int AddOffset)
{
    for (int children : tree[smallerNodeID].childrenList)
    {
        // true = recursion -  false = Base Case
        if (!tree[children].childrenList.empty())
        {
            _updateChildrenDepth(children, removeOffest + 1, AddOffset + 1);
        }
        treeDepth[removeOffest].erase(children);
        treeDepth[AddOffset].insert(children);
    }
}

TreeNode& Union::root(const TreeNode& node)
{
    int self = node.parent;
    while (tree[self].parent != self) { self = tree[self].parent; }
    return tree[self];
}

int Union::getIdDepth(int ID)
{
    int depth{};
    for (auto&[key, Set] : treeDepth)
    {
        for (auto val : Set) {
            if (val == ID) { return depth; }
        }
        depth++;
    }
    return depth;
}

void Union::degubPrintUnionState()
{
    cout << "\n\n\n\n\n\n\n\n\n" << endl;
    int size = tree.size();
    for (size_t i = 0; i < size; i++)
    {
        if (!tree[i].childrenList.empty())
        {
            std::cout << "Child of " << setw(4) << i << " {" << flush;
            int count{};
            for (int child : tree[i].childrenList)
            {
                cout << setw(4) << child << " " << flush;

                if (count > 10) {
                    count = 0;
                    cout << "\n" << flush;
                    cout << setw(15) << '.';
                }
                count++;
            }
            cout << setw(4) << "}" << endl;
        }
    }
}

void Union::degubPrintDepthMap()
{
    int depth{};
    for (auto&[Key, Set] : treeDepth)
    {
        int  count{};
        cout << "Depth " << setw(2) << depth << "{" << flush;
        for (int val : Set)
        {
            cout << setw(3) << val << " " << flush;
            if (count > 10) {
                count = 0;
                cout << "\n" << flush;
                cout << setw(9) << '.';
            }
            count++;
        }
        cout << setw(4) << "}" << endl;
        depth++;
    }

}