#include "stdio.h"
#include "malloc.h"
#include "stdlib.h"
#include "string.h"
using namespace std;
struct HeapItem
{
    char* profession;
    float salary;
};

struct BST
{
    HeapItem* info;
    BST* left;
    BST* right;
    int GE;
};

BST* createNode(HeapItem*);
void insertNode(BST*&, BST*); //radacina, nod nou
HeapItem* createElement(char*, float);
void printSRD(BST*);
void printRSD(BST*);
void printSDR(BST*);
void AfisareStructura(BST*, int);
void AfisareDescendenti(BST*);
void deleteNode(BST**, float);
void stergereLogica(BST**, BST*&);
void main()
{
    FILE* pFile = fopen("Date.txt", "r");
    BST* root = NULL;
    BST* treeFromHeapRoot = NULL;
    if (pFile)
    {
        char buffer[100]; float salary;
        fscanf(pFile, "%s", buffer);
        while (!feof(pFile))
        {
            fscanf(pFile, "%f", &salary);

            //1. create an element of type List*
            HeapItem* newElement = createElement(buffer, salary);
            //2. insert the newly created element
            //enqueue(heap, newElement);

            BST* item = createNode(newElement);
            insertNode(root, item);

            fscanf(pFile, "%s", buffer);
        }
        fclose(pFile);
    }
    printf("----------AfisareStructura-------------\n");
    AfisareStructura(root, 0);

    printf("----------Inordine-------------\n");
    printSRD(root);
    printf("----------Preordine-------------\n");
    printRSD(root);
    printf("----------Postordine-------------\n");
    printSDR(root);
    printf("----------Afisare noduri doar cu descendent in dreapta-------------\n");
    AfisareDescendenti(root);

    //stergere frunza
    deleteNode(&root, 1230);

    printf("----------AfisareStructura-------------\n");
    AfisareStructura(root, 0);

    char buf[] = "Profesie";
    HeapItem* newElement = createElement(buf, 2700);
    BST* item = createNode(newElement);
    insertNode(root, item);

    printf("----------AfisareStructura-------------\n");
    AfisareStructura(root, 0);

}

void stergereLogica(BST** root, BST*& descLeft)
{
    if (descLeft->right != NULL)
        stergereLogica(&(*root), descLeft->right);
    else
    {
        HeapItem* tmp = (*root)->info;
        (*root)->info = descLeft->info;
        BST* nodTmp = descLeft;
        descLeft = descLeft->left;
        free(tmp->profession);
        free(tmp);
        free(nodTmp);
    }
}

void deleteNode(BST** root, float cheie)
{
    if ((*root) != NULL)
    {
        //apel recursiv (descendent stang/drept)
        if ((*root)->info->salary > cheie)
            deleteNode(&(*root)->left, cheie);
        else if ((*root)->info->salary < cheie)
            deleteNode(&(*root)->right, cheie);
        else
        {
            //stergere nod identificat dupa cheie
            //stergere nod frunza
            if ((*root)->left == NULL && (*root)->right == NULL)
            {
                BST* tmp = (*root);
                *root = NULL;
                free(tmp->info->profession);
                free(tmp->info);
                free(tmp);
            }
            //stergere nod cu 1 descendent stang
            else if ((*root)->left != NULL && (*root)->right == NULL)
            {
                BST* tmp = (*root);
                *root = (*root)->left;
                free(tmp->info->profession);
                free(tmp->info);
                free(tmp);
            }
            //stergere nod cu 1 descendent drept
            else if ((*root)->left == NULL && (*root)->right != NULL)
            {
                BST* tmp = (*root);
                *root = (*root)->right;
                free(tmp->info->profession);
                free(tmp->info);
                free(tmp);
            }
            //stergere nod cu 2 descendenti
            else
            {
                stergereLogica(&(*root), (*root)->left);
            }
        }
    }
}
void AfisareDescendenti(BST* root) //inordine
{
    if (root != NULL)
    {
        //left
        AfisareDescendenti(root->left);
        //root
        if (root->left == NULL && root->right != NULL)
            printf("Salary: %f\n", root->info->salary);
        //right
        AfisareDescendenti(root->right);
    }
}


void printSRD(BST* root) //inordine
{
    if (root != NULL)
    {
        //left
        printSRD(root->left);
        //root
        printf("Salary: %f\n", root->info->salary);
        //right
        printSRD(root->right);
    }
}
void printRSD(BST* root) //preordine
{
    if (root != NULL)
    {
        //root
        printf("Salary: %f\n", root->info->salary);
        //left
        printRSD(root->left);
        //right
        printRSD(root->right);
    }
}
void AfisareStructura(BST* root, int nivel)
{
    if (root != NULL)
    {
        for (int i = 0; i < nivel; i++)
            printf("\t");
        printf("%f\n", root->info->salary);
        AfisareStructura(root->left, nivel + 1);
        AfisareStructura(root->right, nivel + 1);
    }
    else
    {
        for (int i = 0; i < nivel; i++)
            printf("\t");
        printf("NULL\n");
    }
}
void printSDR(BST* root) //postordine
{
    if (root != NULL)
    {
        //left
        printSDR(root->left);
        //right
        printSDR(root->right);
        //root
        printf("Salary: %f\n", root->info->salary);
    }
}
int max(int a, int b)
{
    return a > b ? a : b;
}
int calculInaltime(BST* root)
{
    if (root != NULL)
    {
        return 1 + max(calculInaltime(root->left), calculInaltime(root->right));
    }
    else
        return 0;
}
int calculGE(BST* root)
{
    int hsleft = 0, hsright = 0;
    if (root->right != NULL)
        hsright = calculInaltime(root->right);
    if (root->left != NULL)
        hsleft = calculInaltime(root->left);
    return hsright - hsleft;
}

BST* RotireDreapta(BST* pivot)
{
    BST* desc = pivot->left;
    pivot->left = desc->right;
    desc->right = pivot;
    pivot = desc;
    return pivot;
}

BST* RotireStanga(BST* pivot)
{
    BST* desc = pivot->right;
    pivot->right = desc->left;
    desc->left = pivot;
    pivot = desc;
    return pivot;
}

BST* reechilibrare(BST* root)
{
    root->GE = calculGE(root);
    if (root->GE == -2)
    {
        BST* desc = root->left;
        if (desc->GE == -1)
        {
            //rotire la dreapta in pivot
            root = RotireDreapta(root);
        }
        else
        {
            //rotire la stanga in desc
            root->left = RotireStanga(desc);
            //rotire la dreapta in pivot
            root = RotireDreapta(root);
        }
    }
    else if (root->GE == 2)
    {
        BST* desc = root->right;
        if (desc->GE == 1)
        {
            //simpla rotire la stanga in pivot
            root = RotireStanga(root);
        }
        else
        {
            //simpla rotire la dreapta in desc
            root->right = RotireDreapta(desc);
            //simpla rotire la stanga in pivot
            root = RotireStanga(root);
        }
    }
    return root;
}

void insertNode(BST*& root, BST* node)
{
    //iteratia n
    if (root == NULL)
    {
        root = node;
    }
    //iteratia n-1
    else
    {
        if (root->info->salary > node->info->salary)
            insertNode(root->left, node);
        else if (root->info->salary < node->info->salary)
            insertNode(root->right, node);
    }
    root = reechilibrare(root);
}
BST* createNode(HeapItem* info)
{
    BST* node = (BST*)malloc(sizeof(BST));
    node->info = info;
    node->GE = 0;
    node->left = node->right = NULL;
    return node;
}

HeapItem* createElement(char* buffer, float salary)
{
    //1.allocate memory for the new element
    HeapItem* newElement = (HeapItem*)malloc(sizeof(HeapItem));
    //2.initialize it with the params
    //(the connection attributes should remain NULL)
    newElement->salary = salary;
    newElement->profession = (char*)malloc(strlen(buffer) + 1);
    strcpy(newElement->profession, buffer);
    //3.return the new element
    return newElement;
}