//
// Created by Dmytrii Ivanov on 07/02/2021.
//

#include "BinTree.h"
#include <iostream>
#include <queue>

BinTree::BinTree() {
    root = nullptr;
    sz = 0;
}

BinTree::~BinTree() {

}

int BinTree::size() const {
    return sz;
}
//BinTree::Node *BinTree::findValue(const char &val) const{
//    return find(val, root);
//}
BinTree::Node* pnt = nullptr;
int res = 0;
char BinTree::find(char val, Node* leaf) const {
//    Node* p = nullptr;
//    if(leaf == nullptr)
//        return nullptr;

res++;
//res = val;
    if (leaf->value == val) {
//        pnt = leaf;

        return val;
    }
    else if (leaf->value > val)
        find(val, leaf->left);
    else // (leaf->value < val)
        find(val, leaf->right);
}

BinTree::Node *BinTree::insert(const char &val, Node* n) {
    if (n == nullptr){
        n = new Node(val, n);
    }
    else if(n->value < val){
        n->right = insert(val, n->right);
        n->right->pre = n;
    }
    else if (n->value > val){
        n->left = insert(val, n->left);
        n->left->pre = n;
    }
    else n->count +=1;
    return n;
}

BinTree::Node *BinTree::getRoot() const {
    return root;
}

unsigned int BinTree::countNode(Node* n) const {
    unsigned int counter =1;
    if(!n) return counter;
    if(n->left != nullptr)
        counter += countNode(n->left);
    if(n->right != nullptr)
        counter += countNode(n->right);
    return counter;
}

void BinTree::inOrder(Node *n) {
    if(n == nullptr)
        return ;
    inOrder(n->left);
    std::cout << n->value << " " ;
    inOrder(n->right);
}

void BinTree::nodeInsert(const char &val) {
    root = insert(val, root);
    sz++;
}

void BinTree::levelOder(BinTree::Node *n) {
    std::queue <Node* > q;
    q.push(n);
    while(!q.empty()) {
        n = q.front();
        q.pop();
        std::cout << n->value << " ";
        if(n->left != nullptr)
            q.push(n->left);
        if(n->right != nullptr)
            q.push(n->right);
    }
}

BinTree::Node::Node(char ch, Node *t) {
    value = ch;
    pre = t ;
    left = nullptr;
    right = nullptr;
    count = 1;
}

BinTree::Node* BinTree::rotateLeft(Node* n)
{
    if (n->pre->pre == nullptr) {
        n->pre->right = n->left;
        if (n->left != nullptr) n->left->pre = n->pre;
        n->left = n->pre;
        n->pre = nullptr;
        root->pre = n;
        root = n;
    }

    else{
        Node* tmp{ n->pre->pre };

        n->pre->right = n->left;
        if (n->left != nullptr)n->left->pre = n->pre;
        n->left = n->pre;
        n->pre->pre = n;
        n->pre = tmp;
        tmp = nullptr;

        if (n->pre->left == n->left){
            n->pre->left = n;
        }
        else if (n->pre->right == n->left){
            n->pre->right = n;
        }
    }
    return n;
}

//BinTree::Node *BinTree::rotateRight(BinTree::Node *n) {
//
//}