Treap

/* Laborator 10 SD - Treapuri
  * Autor: Andrei Parvu - andrei.parvu@cti.pub.ro
  * Echipa SD, 2014
  *
  * Modificari: Mihai Neacsu - mihai.mneacsu@gmail.com
  * Echipa SD, 2015
  *
  * Modificari: Gabriel Bercaru, 2018
 */

using namespace std;

template <typename T> struct Treap {
    T key;
    int priority;
    Treap<T> *left, *right;
    bool nil;

    // Pentru a rezolva problema 3 trebuie ca fiecare nod sa retina numarul de
    // noduri din subarborle sau
    int nr_nodes;

    // Creaza un nod nil
    Treap() : priority(-1), left(NULL), right(NULL), nil(true), nr_nodes(0) {}

    // Adaugam date, transformand un nod nil intr-un nod obisnuit
    void addData(T key, int priority) {
        this->nil = false;
        this->key = key;
        this->priority = priority;
        this->nr_nodes = 1;
        this->left = new Treap();
        this->right = new Treap();
    }

    // Stergem un nod obisnuit, transformandu-l intr-unul nil
    void delData() {
        this->key = 0;
        this->nil = true;
        this->priority = -1;
        delete this->left;
        delete this->right;
        this->nr_nodes = 0;
        delete this;
    }

    bool isNil() {
        return this->nil;
    }

    bool find(T key) {
        if (this->isNil()) {
            return false;
        }
        // TODO 1.1: Completati functia de cautare
        Treap<T> *current = this;
        while (current != NULL && current->key != key) {
            if (current->key > key) {
                current = current->left;
            } else {
                current = current->right;
            }
        }
        if (current != NULL) {
            return true;
        }
        return false;
    }

    /* Atat insert cat si erase au nevoie de o referinta catre un fatherPointer,
       adica de pointerul left sau right din parinte care pointeaza catre obiectul
       curent. De ce?
       Sa presupunem ca avem urmatoarea configuratie:
                     a
                    / \
                   b   c
                      / \
                     d   e

       si facem o rotatie dreapta in nodul c. Configuratia care rezulta este:
                     a
                    / \
                   b   d
                        \
                         c
                          \
                           e

       Dupa cum se poat vedea pointerul right a lui a trebuie sa pointeze in urma
       rotirii catre d. De aceea, o referinta a acelui pointer trebuie pasata catre
       fiul care reprezinta acel pointer, pentru ca nodul a sa vada eventualele
       inlocuiri ce pot aparea in urma unor rotiri.
       Atentie! - desi s-ar putea sa spunem ca putem folosi pointerul this pentru
       a rezolva problema de mai sus, acest lucru este gresit, deoarece this este un
       pointer constant, asupra caruia nu se pot face asignari de forma this = ...
     */

    void rotateRight(Treap<T> *&fatherPointer) {
        // TODO 1.2: Completati rotirea dreapta

        // TODO 1.2: Recalculati dimensiunea subarborilor
        Treap<T> *son = fatherPointer->left;
        Treap<T> *rson = son->right;
        if (rson != NULL) {
            fatherPointer->left = rson;
        }
        son->right = fatherPointer;
        fatherPointer = son;
    }

    void rotateLeft(Treap<T> *&fatherPointer) {
        // TODO 1.2: Completati rotirea stanga

        // TODO 1.2: Recalculati dimensiunea subarborilor
        Treap<T> *son = fatherPointer->right;
        Treap<T> *lson = son->left;
        if (lson != NULL) {
            fatherPointer->right = lson;
        }
        son->left = fatherPointer;
        fatherPointer = son;
    }

    void insert(Treap<T> *&fatherPointer, T key, int priority) {
        if (fatherPointer->isNil()) {
            fatherPointer->addData(key, priority);

            return ;
        }

        Treap<T> *nonConstThis = this;
        // TODO 1.3: Inserati recursiv in arbore
        if (key < fatherPointer->key) {
            insert(fatherPointer->left, key, priority);
        } else {
            insert(fatherPointer->right, key, priority);
        }
        nr_nodes++;

        // TODO 1.3: Faceti rotatiile corespunzatoare
        if (fatherPointer->left->priority > fatherPointer->priority) {
            rotateRight(fatherPointer);
        } else if (fatherPointer->right->priority > fatherPointer->priority) {
            rotateLeft(fatherPointer);
        }
    }

    void erase(Treap<T> *&fatherPointer, T key) {
        if (fatherPointer->isNil()) {
            return ;
        }

        Treap<T> *nonConstThis = this;
        nr_nodes--;

        // TODO 2: Stergti recursiv in arbore (pe subarborele corespunzator)
        if (key < fatherPointer->key) {
            erase(fatherPointer->left, key);
        } else if (key > fatherPointer->key) {
            erase(fatherPointer->right, key);
        } else if (fatherPointer->left->isNil() && fatherPointer->right->isNil()) {
            fatherPointer->delData();
        } else {
            // TODO 2: Rotiti si stergeti recursiv pentru a aduce nodul la baza arborelui
            if (fatherPointer->left->priority > fatherPointer->right->priority) {
                rotateRight(fatherPointer);
                erase(fatherPointer->right, key);
            } else {
                rotateLeft(fatherPointer);
                erase(fatherPointer->left, key);
            }
        }
    }
    void recInOrder(Treap<T> *current) {
        if (!current->left->isNil()) {
            recInOrder(current->left);
        }
        std::cout << current->key << ' ';
        if (!current->right->isNil()) {
            recInOrder(current->right);
        }
    }
    void inOrder() {
        if (this->isNil()) {
            return;
        }
        // TODO 3: Afisati parcurgerea inordine a cheilor
        recInOrder(this);
        std::cout << '\n';
    }
    void recPreOrder(Treap<T> *current) {
        std::cout << current->key << ' ';
        if (!current->left->isNil()) {
            recPreOrder(current->left);
        }
        if (!current->right->isNil()) {
            recPreOrder(current->right);
        }
    }
    void preOrder(int level = 0) {
        if (this->isNil()) {
            return ;
        }

        for (int i = 0; i < level; i++) {
            cout << ' ';
        }

        // TODO 3: Afisati parcurgerea preordine a prioritatilor
        recPreOrder(this);
    }
    T getKey(Treap<T> *current, int &k, bool &flag) {
        if (!current->left->isNil() && flag == false) {
            getKey(current->left, k, flag);
        }
        --k;
        if (k == 0 && flag == false) {
            flag = true;
            return current->key;
        }
        if (!current->right->isNil() && flag == false) {
            return getKey(current->right, k, flag);
        }
    }
    T findK(int k) {
        // TODO 3: Pe baza nr_nodes determinati cea de-a k cheie in ordinea sortarii
        bool flag = false;
        T key = getKey(this, k, flag);
        return key;
    }
};