#include "lib.cpp"

#include "lib.h"
#include <iostream>
#include <string>
#include <cstdlib>
#include <fstream>
#include <string>

using namespace std;

struct BST_P{
    int value;
    BST_P *left = nullptr;
    BST_P *right = nullptr;
    BST_P *parent = nullptr;
};

void inorder(BST_P *root);
void preorder(BST_P *root);
void postorder(BST_P * root);
BST_P* find(BST_P *root);
BST_P* max(BST_P *root);
BST_P* min(BST_P *root);
BST_P* next(BST_P *root);
BST_P* prev(BST_P *root);
BST_P* insert_BST (BST_P* root, BST_P *x);
void remove_BST (BST_P* root, BST_P *x);

struct node
{
    BST_P * wsk;
    node *next;
};



struct Stack
{
    node *top;
    Stack()
     {   
         top = nullptr;
     }
     
     
    void push(BST_P *wezel)
     {
        node * ptr = new node;
        ptr ->wsk = wezel;
        ptr ->next = top;
        top =ptr;

     }
     BST_P * pop()
     {
         if(!top) return nullptr;
         node *ptr = top;
         BST_P *x = top->wsk;
         top = top->next;
         delete(ptr);
         return x;
     }
    
};



void inorder(BST_P *root)
{   
    if(!root) return;
    if(root->left)
        inorder(root->left);
    cout << root->value << " ";
    if(root->right)
        inorder(root->right);
}
void postorder(BST_P *root)
{
    if(!root) return;
    if(root ->left)
        postorder(root->left);
    if(root ->right)
        postorder(root -> right);
    cout << root->value;
}
void preorder(BST_P *root)
{
    if(!root) return;
    cout << root ->value;
    if(root ->left)
        preorder(root -> left);
    if(root ->right)
        preorder(root->right);

}
BST_P* find(BST_P *root,int x)
{
    if(!root) return nullptr;
    if(root->value==x) return root;
    if(root->value > x) return find(root->left,x);
    else return find(root->right,x);
}
BST_P* min(BST_P *root)
{
    if(!root) return nullptr;
    while(root->left)
    {
        root=root->left;
    }
    return root;
}
BST_P* max(BST_P *root)
{
    if(!root) return nullptr;
    while(root->right)
        root=root->right;
    return root;
}
BST_P* next(BST_P *root)
{
    if(root->right) return min(root->right);
    BST_P* y = root->parent;
    while(y && root->parent)
    {
        root=y;
        y=y->parent;
    }
    return y;
}
BST_P* prev(BST_P *root)
{
    if(root->left) return max(root->left);
    BST_P* y = root->parent;
    while(y&& root->parent)
    {
        root=y;
        y=y->parent;
    }
    return y;
}
BST_P* insert_BST (BST_P* root, BST_P *x)
{
    if(!root){
        root = x;
        return root;
    }
    BST_P *par = nullptr;
    BST_P *son = root;
    while(son)
    {
        par=son;
        if(par->value > x-> value) son = par->left;
        else son = par->right;
    }
    x->parent = par;
    if(par->value > x->value) par->left=x;
    else par->right =x;
    return root;    
}

void remove_BST (BST_P* root, BST_P *z)
{
    BST_P* y;
    if(z->left && z->right) y=next(z);
    else y=z;
    BST_P *x;
    if(y->left) x=y->left;
    else x=y->right;
    if(x) x->parent = y->parent;
    if(y->parent)
    {
        if(y=y->parent->left)
        y->parent->left=x;
        else y->parent->right=x;
    }
    else root = x;
    if(z!=y)
    z->value=y->value;
    delete y;

}

Stack getDataFromFile(Stack s) {
    string token;
    fstream plik;
    int i=0;

    plik.open("listaliczb.txt", ios::in);
    if (plik) {
        while (!plik.eof()) {
           getline(plik, token,' ');
           BST_P* t = new BST_P;
           t->value=stoi(token);
            s.push(t);
            cout << s.top->wsk->value << " " ;

            
        }
        plik.close();
        return s;
    }
    
    else 
    {
        cout << "Nie udalo sie otworzyc pliku OwO" << endl;
    }
}




int main()
{
    Stack s;
    s=getDataFromFile(s);
    node* temp = s.top;

    
    cout << endl;
    BST_P *root = nullptr;
    while(s.top)
    {
        insert_BST(root,s.pop());
        
    }
    inorder(root);

    return 0;
}