#include <iostream>
#include <fstream>
#include <vector>
#include <climits>
#include <random>
#include <chrono>
#include <string>
#include <iomanip>
#include <math.h>
#include <deque>
#include <algorithm>
#include "structures.h"
#include <stdlib.h>
#include <crtdbg.h>
#include <sstream>

const int MAX_SIZE = 4;

///@todo pliki naglowowe
//#include "functions.h"

void deleteChildrenList(el_child*& child);
void deleteKeyList(el_key*& key);
int sizeOfKeyList(el_key*& pH);
//TODO change path to relative
const std::string file_name = "C:/Users/Święty/Documents/B-tree project/note.txt";
node* root = nullptr;


void printKey(el_key* pK, std::ofstream*& myFile)
{
    if (myFile != nullptr)
        std::cout.rdbuf(myFile->rdbuf());
    while (pK)
    {
        std::cout << pK->key << " ";
        pK = pK->pNext;
    }
}

void printKey(el_key* pK, int number, std::ofstream*& myFile)   // print key from exact place
{
    if (pK)
    {
        if (myFile != nullptr)
            std::cout.rdbuf(myFile->rdbuf());
        el_key* p = pK;
        for (int i = 0; i < number; i++)
        {
            p = p->pNext;
        }
        std::cout << p->key << " ";
    }
}

void printKeyWithLevel(el_key* pK, int number, int level, std::ofstream*& myFile)
{
    if (myFile != nullptr)
        std::cout.rdbuf(myFile->rdbuf());
    std::cout << std::setw(level * 4);
    printKey(pK, number, myFile);
    std::cout << std::endl;
    std::cout << std::setw(0);
}

void printNode(node*& nodeP, std::ofstream*& myFile)
{

    if (nodeP)
    {
        int counter = 0;
        if (nodeP->pListChildren != nullptr) {
            el_child* tmpChild = nodeP->pListChildren;
            printNode(tmpChild->pChild, myFile);

            for (int i = 0; i < sizeOfKeyList(nodeP->pListKeys); i++)
            {
                printKey(nodeP->pListKeys, counter, myFile);
                tmpChild = tmpChild->pNext;
                printNode(tmpChild->pChild, myFile);
                counter++;
            }
        }
        else {
            printKey(nodeP->pListKeys, myFile);
        }
    }
}

void printStructure(node*& nodeP, int level, std::ofstream*& myFile)
{
    if (nodeP)
    {
        if (nodeP->pListChildren != nullptr) {
            int counter = 0;
            el_child* tmpChild = nodeP->pListChildren;
            printStructure(tmpChild->pChild, level + 1, myFile);
            for (int i = 0; i < sizeOfKeyList(nodeP->pListKeys); i++)
            {
                printKeyWithLevel(nodeP->pListKeys, counter, level, myFile);
                tmpChild = tmpChild->pNext;
                printStructure(tmpChild->pChild, level + 1, myFile);
                counter++;
            }
        }
        else {
            int counter = 0;
            for (int i = 0; i < sizeOfKeyList(nodeP->pListKeys); i++)
            {
                printKeyWithLevel(nodeP->pListKeys, counter, level, myFile);
                counter++;
            }
        }
    }
}

int addKey(el_key*& pK, const double& v)
{
    auto p = pK;
    if (not pK)     // if the listOfKeys is empty
    {
        pK = new el_key{ v, nullptr };
        return 0;
    }
    else if (pK->key > v)   // add key at the beggining
    {
        pK = new el_key{ v, pK };
        return 0;
    }
    else  // add value sorted way
    {
        int counter = 2;
        while (p->pNext && v > p->pNext->key)
        {
            p = p->pNext;
            counter++;
        }
        p->pNext = new el_key{ v, p->pNext };
        return counter;
    }
}

void removeKey(el_key*& pK, int value)
{
    auto p = pK;

    if (not pK) // if there is nothing to remove
    {
        return;
    }
    else if (pK->key == value)  // remove first element
    {
        pK = pK->pNext;
        delete p;
        return;
    }
    while (p->pNext) // remove element with value
    {
        if (p->pNext->key == value)
        {
            el_key* kToRemove = p->pNext;
            p->pNext = p->pNext->pNext;
            delete kToRemove;
            return;
        }
        p = p->pNext;
    }
}

int sizeOfKeyList(el_key*& pH)
{
    auto p = pH;
    int counter = 0;
    while (p)
    {
        counter++;
        p = p->pNext;
    }
    return counter;
}

void addChild(el_child*& pK, node* newNode, int number)
{
    auto p = pK;
    if (not pK)
    {
        pK = new el_child{ newNode, nullptr };
    }
    else if (number == 0)
    {
        pK = new el_child{ newNode, pK };
    }
    else
    {
        for (int i = 1; i < number; i++)
        {
            p = p->pNext;
        }
        p->pNext = new el_child{ newNode, p->pNext };
    }
}

void balanceRoot(node*& pointerToNode) {
    el_key* tmpP = pointerToNode->pListKeys;
    el_key* splitKey = nullptr;
    el_child* tmpChild = pointerToNode->pListChildren;
    el_child* splitChild = nullptr;
    int size = sizeOfKeyList(pointerToNode->pListKeys);

    for (int i = 1; i < size; i++) {
        if (tmpChild != nullptr)
            tmpChild = tmpChild->pNext;
        if (i == floor(size / 2)) {
            splitKey = tmpP->pNext; //find split key iterating over keylist
            if (tmpChild != nullptr) {
                splitChild = tmpChild->pNext;  //find split child iterating over childList
                tmpChild->pNext = nullptr;
            }
            tmpP->pNext = nullptr;
            break;
        }
        tmpP = tmpP->pNext;

    }

    node* newChild = new node{ splitKey->pNext , splitChild }; //new node splitted by new root value
    splitKey->pNext = nullptr;

    el_child* child2 = new el_child{ newChild, nullptr };   //create new child for fresh new rootNode using created node above
    el_child* child1 = new el_child{ pointerToNode, child2 }; //create new child for fresh new rootNode using old root node
    pointerToNode = new node{ splitKey, child1 }; //create node using splitted key and created childList above
}

bool addValueToTree(node*& pointerToNode, const double& value, bool isRoot) {
    node* p = pointerToNode;

    if (pointerToNode == nullptr)   // if node is empty
    {
        el_key* key = new el_key{ value, nullptr };
        pointerToNode = new node{ key, nullptr };                           //create node
    }
    else if (pointerToNode->pListChildren == nullptr) //add key to root node
    {
        addKey(pointerToNode->pListKeys, value);
        if (sizeOfKeyList(pointerToNode->pListKeys) >= MAX_SIZE)
        {
            if (isRoot)
                balanceRoot(pointerToNode);
            else
                return true;
        }
    }
    else { //if node have children
        el_key* tmpP = pointerToNode->pListKeys;
        el_child* tmpP2 = pointerToNode->pListChildren;
        while (tmpP && value > tmpP->key) //find key higher than value
        {
            tmpP = tmpP->pNext;
            tmpP2 = tmpP2->pNext;
        }
        bool needBalance = addValueToTree(tmpP2->pChild, value, false);
        if (needBalance) { //if unbalanced
            el_key* tmpP = tmpP2->pChild->pListKeys;
            el_key* splitKey = nullptr;
            int size = sizeOfKeyList(tmpP);
            for (int i = 1; i < size; i++) {
                if (i == floor(size / 2)) {//find split key iterating over keylist
                    splitKey = tmpP->pNext;
                    tmpP->pNext = nullptr;
                    break;
                }
                tmpP = tmpP->pNext;
            }

            int keyNumber = addKey(pointerToNode->pListKeys, splitKey->key);//add key to keyList

            tmpP2 = pointerToNode->pListChildren;
            for (int i = 1; i < keyNumber; i++)         //find proper child to add the value
            {
                tmpP2 = tmpP2->pNext;
            }

            node* newNode = new node{ splitKey->pNext , nullptr };
            el_child* newChild = new el_child{ newNode , tmpP2->pNext };
            tmpP2->pNext = newChild;
            splitKey->pNext = nullptr;

            if (sizeOfKeyList(pointerToNode->pListKeys) >= MAX_SIZE)
            {
                if (isRoot)
                    balanceRoot(pointerToNode);
                else
                    return true;
            }
        }
    }
    return false;
}

el_key* getKeyFromRightChildrens(el_child*& childP) {
    if (sizeOfKeyList(childP->pChild->pListKeys) > 1) {
        el_key* tmpP = childP->pChild->pListKeys;
        childP->pChild->pListKeys = tmpP->pNext;
        return tmpP;
    }
}


el_key* getKeyFromChildrens(el_child*& childP) {
    if (sizeOfKeyList(childP->pChild->pListKeys) > 1) { //get from left child
        el_key* tmpP = childP->pChild->pListKeys;
        el_key* prevKey = nullptr;
        while (tmpP->pNext != nullptr) //get last key from key list
        {
            prevKey = tmpP;
            tmpP = tmpP->pNext;
        }
        if (prevKey == nullptr)
            childP->pChild->pListKeys = tmpP->pNext;
        else
            prevKey->pNext = tmpP->pNext;
        return tmpP;
    }
    else if (childP->pNext != nullptr) {
        return getKeyFromRightChildrens(childP->pNext); //get from the right child
    }
    else return nullptr;
}

bool compareDoubles(double a, double b)
{
    return abs(a - b) < 0.000001;
}

void removeKey(node*& pointerToNode, double value) {
    el_key* tmpP = pointerToNode->pListKeys;
    el_key* prevKey = nullptr;
    el_child* prevChild = nullptr;
    el_child* tmpChild = nullptr;
    if (pointerToNode->pListChildren != nullptr) {
        tmpChild = pointerToNode->pListChildren;
    }
    while (tmpP->pNext != nullptr && value > tmpP->key)
    {
        if (pointerToNode->pListChildren != nullptr) {
            prevChild = tmpChild;
            tmpChild = tmpChild->pNext;
        }
        prevKey = tmpP;
        tmpP = tmpP->pNext;
    }

    if (compareDoubles(tmpP->key, value)) {
        if (pointerToNode->pListKeys == tmpP) {
            pointerToNode->pListKeys = pointerToNode->pListKeys->pNext;
            delete tmpP;
        }
        else {
            prevKey->pNext = tmpP->pNext;
            delete tmpP;
        }
        if (pointerToNode->pListChildren != nullptr) { // check if can get key from childrens
            tmpP = getKeyFromChildrens(pointerToNode->pListChildren);
            if (tmpP != nullptr) {
                if (prevKey != nullptr) {
                    tmpP->pNext = prevKey->pNext;
                    prevKey->pNext = tmpP;
                }
                else {
                    tmpP->pNext = pointerToNode->pListKeys;
                    pointerToNode->pListKeys = tmpP;
                }

            }
        }

    }
    else if (pointerToNode->pListChildren != nullptr){
        if (value > tmpP->key) {
            prevChild = tmpChild;
            tmpChild = tmpChild->pNext;
        }
        removeKey(tmpChild->pChild, value);
        if (sizeOfKeyList(tmpChild->pChild->pListKeys) == 0) { //check if there is a need to give key to child
            if (prevChild != nullptr && sizeOfKeyList(prevChild->pChild->pListKeys) > 1) { //check if can borrow key from prev child
                tmpChild->pChild->pListKeys = getKeyFromChildrens(prevChild);
            }
            else if(tmpChild->pNext != nullptr && sizeOfKeyList(tmpChild->pNext->pChild->pListKeys) > 1) {//check if can borrow key from next child
                tmpChild->pChild->pListKeys = getKeyFromRightChildrens(tmpChild->pNext);
            }
            else if(tmpChild->pChild->pListChildren == nullptr) {
                if (prevChild != nullptr) { //has left sibling
                    prevChild->pNext = tmpChild->pNext;
                    delete tmpChild;
                    //add root case
                    prevKey->pNext = tmpP->pNext;
                    el_key* lastKeyOfChild = prevChild->pChild->pListKeys;
                    while (lastKeyOfChild->pNext != nullptr)
                    {
                        lastKeyOfChild = lastKeyOfChild->pNext;
                    }
                    lastKeyOfChild->pNext = tmpP;
                    tmpP->pNext = nullptr;
                }
                else { //has right sibling and has no left sibling. move key to children on right
                    pointerToNode->pListChildren = tmpChild->pNext;
                    delete tmpChild;
                    pointerToNode->pListKeys = tmpP->pNext;
                    tmpP->pNext = pointerToNode->pListChildren->pChild->pListKeys;
                    pointerToNode->pListChildren->pChild->pListKeys = tmpP;
                }

            }

        }
    }
    else {
        std::cout << "There is no such key as: " << value << std::endl;
    }
    std::cout << "Removed value:  " << value << std::endl;

}

void deleteNode(node*& pR)
{
    if (pR) {
        if (pR->pListKeys)
        {
            deleteKeyList(pR->pListKeys);
        }
        if (pR->pListChildren) {
            deleteChildrenList(pR->pListChildren);
        }
        delete pR;
    }
}

void deleteKeyList(el_key*& key) {
    if (key) {
        if (key->pNext) {
            deleteKeyList(key->pNext);
        }
        delete key;
    }

}

void deleteChildrenList(el_child*& child) {
    if (child) {
        if (child->pNext) {
            deleteChildrenList(child->pNext);
        }
        deleteNode(child->pChild);
        delete child;
    }
}

int read_data() {

    std::ifstream file(file_name);
    std::string line;

    if (file)
    {
        while (std::getline(file, line))
        {
            std::stringstream linestream(line);
            std::string  word;
            double value;

            linestream >> word;
            if (word == "add") {
                while (linestream >> word)
                {
                    if (word == "%") {
                        break;
                    }
                    std::istringstream(word) >> value;
                    addValueToTree(root, value, true);
                }
            }
            else  if (word == "graph") {
                linestream >> word;
                std::ofstream* streamPointer = nullptr;
                std::ofstream inputStream;
                if (word == "+") {
                    linestream >> word;
                    inputStream.open(word, std::fstream::app);
                    if (inputStream)
                        streamPointer = &inputStream;
                }
                else if (word != "graph") {
                    linestream >> word;
                    inputStream.open(word, std::fstream::trunc);
                    if (inputStream)
                        streamPointer = &inputStream;
                }
                printStructure(root, 0, streamPointer);

            }
            else  if (word == "print") {
                linestream >> word;
                std::ofstream* streamPointer = nullptr;
                std::ofstream inputStream;
                if (word == "+") {
                    linestream >> word;
                    inputStream.open(word, std::fstream::app);
                    if (inputStream)
                        streamPointer = &inputStream;
                }
                else if (word != "print" && word != "%") {
                    linestream >> word;
                    inputStream.open(word, std::fstream::trunc);
                    if (inputStream)
                        streamPointer = &inputStream;
                }
                printNode(root, streamPointer);

            }
            else {
                std::cout << "Wrong command" << std::endl;
            }

            std::cout << std::endl;
        }
    }
    else {
        std::cout << "Can't open file";
        return 0;
    }
}

int main()
{
    std::ofstream* streamPointer = nullptr;

    addValueToTree(root, 2, true);
    addValueToTree(root, 8, true);
    addValueToTree(root, 2, true);
    addValueToTree(root, 18, true);
    addValueToTree(root, 4, true);
    addValueToTree(root, 64, true);
    addValueToTree(root, 6, true);
    addValueToTree(root, 34, true);
    addValueToTree(root, 12, true);
    addValueToTree(root, 52, true);
    addValueToTree(root, 5, true);
    addValueToTree(root, 32, true);

    printStructure(root, 0, streamPointer);
    printNode(root, streamPointer);


    //printStructure(root, 0, streamPointer);
    removeKey(root, 2);

    removeKey(root, 8);
    printStructure(root, 0, streamPointer);
    removeKey(root, 2);
    printStructure(root, 0, streamPointer);
    removeKey(root, 18);
    printStructure(root, 0, streamPointer);
    removeKey(root, 4);
    printStructure(root, 0, streamPointer);
    removeKey(root, 64);
    printStructure(root, 0, streamPointer);
    removeKey(root, 6);
    printStructure(root, 0, streamPointer);
    removeKey(root, 34);
    printStructure(root, 0, streamPointer);
    removeKey(root, 12);
    printStructure(root, 0, streamPointer);
    removeKey(root, 52);
    printStructure(root, 0, streamPointer);
    removeKey(root, 5);
    printStructure(root, 0, streamPointer);
    removeKey(root, 32);
    printStructure(root, 0, streamPointer);
    removeKey(root, 4);
    printStructure(root, 0, streamPointer);
    printNode(root, streamPointer);
    //read_data();

    deleteNode(root);                   // delete whole tree
}