#include <iostream>
#include <string>
#include <sstream>
#include <functional>
#include <cmath>
#include <time.h>
#include <cstdlib>

using namespace std;

class Person {
public:
    string name;
    int age;

    Person() {}

    Person(int age, string name) {
        this->name = name;
        this->age = age;
    }
};

int nodeCounter = 1;

template<class T>
class Node {
public:
    T value;
    Node<T> *parent = NULL;
    Node<T> *leftKid = NULL;
    Node<T> *rightKid = NULL;
    bool isRed = true;
    int id;

    Node(T value) {
        this->value = value;
        this->id = nodeCounter;
        nodeCounter++;
    }
};


// globalna zmienna do toStringa
//ostringstream toStringResult;


template<class T>
class BlackRedTree {
    int elementCounter = 0;
    Node<T> *root = NULL;
public:

    ~BlackRedTree() {
        clear();
    }

    T *find(T data, function<bool(T, T)> compareElement, function<int(T, T)> compare) {
        Node<T> *tmp = root;
        while ((tmp != NULL) && !(compareElement(tmp->value, data))) {
            if (compare(tmp->value, data) == -1) {
                tmp = tmp->leftKid;
            } else {
                tmp = tmp->rightKid;
            }
        }
        if (tmp == NULL) {
            return NULL;
        }
        return &tmp->value;
    }

    void preOrder(function<void(Node<T> *)> f) {
        preOrderRecursion(root, f);
    }

    void inOrder(function<void(Node<T> *)> f) {
        inOrderRecursion(root, f);
    }

    void postOrder(function<void(Node<T> *)> f) {
        postOrderRecursion(root, f);
    }

    void clear() {
        postOrder(clearElement);
    }

    int height() {
        return heightRecursion(root);
    }

    void addElement(T data, function<int(T, T)> compare) {
        balancing(addElementSimple(data, compare));
    }

    string toString(function<string(T)> f) {
        // czyszczenie ostringstreama
//        toStringResult.str("");
//        preOrder(BlackRedTree::nodeToString);
//        return toStringResult.str();

        ostringstream result;

        result << "Size: " << elementCounter << endl;
        preOrder(
                // WYRAZENIE LAMBDA
                [&result, &f](Node<T> *node) -> void {
                    int parentId = node->parent == NULL ? 0 : node->parent->id;
                    string color = (node->isRed == true) ? "red" : "black";
                    int leftId = node->leftKid == NULL ? 0 : node->leftKid->id;
                    int rightId = node->rightKid == NULL ? 0 : node->rightKid->id;
                    result << " ID: " << node->id <<
                           " color: " << color <<
                           " parent id: " << parentId <<
                           " left id: " << leftId <<
                           " right id: " << rightId <<
                           " | " << f(node->value) << endl;

                }
        );
        return result.str();
    }

//    static void nodeToString(Node<T> *node) {
//        toStringResult << node->isRed << endl;
//    }

private:
//dodawanie bez rotacji i bez kolorow
    Node<T> *addElementSimple(T data, function<int(T, T)> compare) {
        Node<T> *node = new Node<T>(data);
        if (elementCounter == 0) {
            root = node;
            elementCounter++;
            return node;
        }
        Node<T> *tmp = root;
        while (true) {
            int x = compare(data, tmp->value);
            if (x == 0 || x == -1) {
                if (tmp->leftKid == NULL) {
                    tmp->leftKid = node;
                    node->parent = tmp;
                    elementCounter++;
                    return node;
                } else {
                    tmp = tmp->leftKid;
                }
            } else if (tmp->rightKid == NULL) {
                tmp->rightKid = node;
                node->parent = tmp;
                elementCounter++;
                return node;
            } else {
                tmp = tmp->rightKid;
            }
        }
    }

    void coloringCase1Left(Node<T> *node, Node<T> *father, Node<T> *grandfather, Node<T> *leftUncle) {
        father->isRed = false;
        leftUncle->isRed = false;
        grandfather->isRed = true;
    }

    void coloringCase1Right(Node<T> *node, Node<T> *father, Node<T> *grandfather, Node<T> *rightUncle) {
        father->isRed = false;
        rightUncle->isRed = false;
        grandfather->isRed = true;
    }

    void coloringCase3(Node<T> *father, Node<T> *grandfather) {
        father->isRed = !father->isRed;
        grandfather->isRed = !grandfather->isRed;

    }

    void balancing(Node<T> *node) {
        Node<T> *father = NULL;
        Node<T> *grandfather = NULL;
        Node<T> *leftUncle = NULL;
        Node<T> *rightUncle = NULL;

        while (true) {
            father = node->parent;
            if (node == root) {
                node->isRed = false;
                return;
            }
            if (!father->isRed) {
                return;
            }
            grandfather = father->parent;
            leftUncle = grandfather->leftKid;
            rightUncle = grandfather->rightKid;

            if (isLeftUncleRed(father, leftUncle, rightUncle)) {
                coloringCase1Left(node, father, grandfather, leftUncle);
                node = grandfather;
                continue;
            }
            if (isRightUncleRed(father, leftUncle, rightUncle)) {
                coloringCase1Right(node, father, grandfather, rightUncle);
                node = grandfather;
                continue;
            }
            break;
        }
        if (isRightUncleBlack(father, leftUncle, rightUncle) && father->rightKid == node) {
            rotationLeft(father);
            node = father;
            rotationRight(grandfather);
            father = node->parent;
            Node<T> *brother = father->rightKid;
            coloringCase3(father, brother);
            return;
        }
        if (isLeftUncleBlack(father, leftUncle, rightUncle) && father->leftKid == node) {
            rotationRight(father);
            node = father;
            rotationLeft(grandfather);
            father = node->parent;
            Node<T> *brother = father->leftKid;
            coloringCase3(father, brother);
            return;
        }

        if (isRightUncleBlack(father, leftUncle, rightUncle) && father->leftKid == node) {
            rotationRight(grandfather);
            coloringCase3(father, grandfather);
        }

        if (isLeftUncleBlack(father, leftUncle, rightUncle) && father->rightKid == node) {
            rotationLeft(grandfather);
            coloringCase3(father, grandfather);
        }

    }

    bool isLeftUncleRed(Node<T> *father, Node<T> *leftUncle, Node<T> *rightUncle) {
        if (leftUncle == NULL) {
            return false;
        }
        return (father == rightUncle && leftUncle->isRed);
    }

    bool isRightUncleRed(Node<T> *father, Node<T> *leftUncle, Node<T> *rightUncle) {
        if (rightUncle == NULL) {
            return false;
        }
        return (father == leftUncle && rightUncle->isRed);
    }

    bool isRightUncleBlack(Node<T> *father, Node<T> *leftUncle, Node<T> *rightUncle) {
        if (rightUncle == NULL) {
            return true;
        }
        return (father == leftUncle && !rightUncle->isRed);
    }

    bool isLeftUncleBlack(Node<T> *father, Node<T> *leftUncle, Node<T> *rightUncle) {
        if (leftUncle == NULL) {
            return true;
        }
        return (father == rightUncle && !leftUncle->isRed);
    }

    void rotationRight(Node<T> *start) {
        Node<T> *startLeftChild = start->leftKid;
        Node<T> *startRightGrandChild = startLeftChild->rightKid;
        Node<T> **startPointer = getStartPointer(start);

        start->leftKid = startRightGrandChild;
        startLeftChild->rightKid = start;
        startLeftChild->parent = start->parent;
        start->parent = startLeftChild;
        *startPointer = startLeftChild;
        if (
                startRightGrandChild) {
            startRightGrandChild->parent = start;
        }
    }

    void rotationLeft(Node<T> *start) {
        Node<T> *startRightChild = start->rightKid;
        Node<T> *startLeftGrandChild = startRightChild->leftKid;
        Node<T> **startPointer = getStartPointer(start);

        start->rightKid = startLeftGrandChild;
        startRightChild->leftKid = start;
        startRightChild->parent = start->parent;
        start->parent = startRightChild;
        *startPointer = startRightChild;
        if (startLeftGrandChild) {
            startLeftGrandChild->parent = start;
        }
    }

/**
 * zwraca wskaznik na wskaznik na "punkt startowy rotacji"
 * "**" zeby mozna bylo zmienic np. roota
 */
    Node<T> **getStartPointer(Node<T> *start) {
        if (start == root) {
            return &root;
        } else if (start->parent->leftKid == start) {
            return &start->parent->leftKid;
        } else {
            return &start->parent->rightKid;
        }
    }

    void preOrderRecursion(Node<T> *node, function<void(Node<T> *)> f) {
        f(node);
        if (node->leftKid != NULL) {
            preOrderRecursion(node->leftKid, f);
        }
        if (node->rightKid != NULL) {
            preOrderRecursion(node->rightKid, f);
        }
    }

    void inOrderRecursion(Node<T> *node, function<void(Node<T> *)> f) {
        if (node->leftKid != NULL) {
            inOrderRecursion(node->leftKid, f);
        }
        f(node);
        if (node->rightKid != NULL) {
            inOrderRecursion(node->rightKid, f);
        }
    }

    void postOrderRecursion(Node<T> *node, function<void(Node<T> *)> f) {
        if (node->leftKid != NULL) {
            postOrderRecursion(node->leftKid, f);
        }
        if (node->rightKid != NULL) {
            postOrderRecursion(node->rightKid, f);
        }
        f(node);
    }

    static void clearElement(Node<T> *node) {
        delete node;
    }

    int heightRecursion(Node<T> *node) {
        int height = 0;
        if (node == NULL) {
            return height;
        }
        int leftHeight = heightRecursion(node->leftKid);
        int rightHeight = heightRecursion(node->rightKid);

        if (leftHeight >= rightHeight) {
            leftHeight++;
            return leftHeight;
        } else {
            rightHeight++;
            return rightHeight;
        }
    }

};

bool compareElement(Person person, Person pattern) {
    if (person.age == pattern.age) {
        return true;
    } else {
        return false;
    }
}

int compare(Person newPerson, Person elem) {
    if (newPerson.age == elem.age) {
        return 0;
    } else if (newPerson.age < elem.age) {
        return -1;
    } else {
        return 1;
    }
}

bool compareElementInt(int number, int pattern) {
    return number == pattern;
}

int compareInt(int number, int pattern) {
    if (number == pattern) {
        return 0;
    } else if (number < pattern) {
        return -1;
    } else {
        return 1;
    }
}

string intToString(int n) {
    ostringstream ss;
    ss << n;
    return ss.str();
}

void print(Node<int> *x) {
    cout << x->value << endl;
}

string personToString(Person p) {
    ostringstream result; //zamiana inta na stringa
    result << "age: " << p.age << ", " << "imie: " << p.name;
    return result.str();
}

void treeTest(int n) {
    BlackRedTree<Person> brt;
    Person *persons = new Person[n];

    clock_t t1 = clock();
    for (int i = 0; i < n; ++i) {
//     cout << i << "/" << n << endl;
        persons[i].age = i + 1;
        persons[i].name = "xyz";
        brt.addElement(persons[i], compare);
    }
    clock_t t2 = clock();
    double addTime = (t2 - t1) / (double) CLOCKS_PER_SEC;
    cout << "czas dodawania: " << addTime << endl;
    cout << "czas sredni dodawania: " << addTime / n << endl;
    cout << "wysokosc drzewa: " << brt.height() << endl;


    const int m = pow(10, 4);
    int hits = 0;
    t1 = clock();
    for (int i = 0; i < m; i++) {
        int age = (rand() % n) + 1;
        //int age = (rand()<<15) + rand();
        Person person(age, "xyz");
        Person *result = brt.find(person, compareElement, compare);
        if (result != NULL)
            hits++;
    }
    t2 = clock();
    double findTime = (t2 - t1) / (double) CLOCKS_PER_SEC;
    cout << "czas wyszukiwania: " << findTime << endl;
    cout << "czas sredni wyszukiwania: " << findTime / m << endl;
    cout << "liczba trafien: " << hits << endl;

    //cout << brt.toString(personToString);

    delete[] persons;
}


int main() {
    srand(time(NULL));

    const int MAX_ORDER = 7;

    for (int o = 1; o <= MAX_ORDER; o++) {
        int n = pow(10, o);
        cout << n;
        treeTest(n);
        cout << " - " << endl;
    }


//    BlackRedTree<int> brt;
//    for (int i = 0; i < 8; ++i) {
//        brt.addElement(i + 1, compareInt);
//
//    }
//    cout << brt.toString(intToString) << endl;

//    brt.find(3, compareElementInt, compareInt);
//    brt.postOrder(print);
//    cout << endl;
//
//    cout << brt.height() << endl << endl;
//
//    cout << brt.toString(intToString) << endl;


    return 0;
}