//Splay tree implementation in C++
#include <bits/stdc++.h>
using namespace std;

class Node {
    public:
        int data;
        Node* parent;
        Node* left;
        Node* right;

    Node(int d) {
        data = d;
        parent=NULL;
        left=NULL;
        right=NULL;

    }



};

class SplayTree {
    public:
        Node* root=NULL;

        void LR(Node* x) {
            //Left rotate the node

            Node* y = x->right;
            y->parent = x->parent;

           if(x->parent!=NULL && x->parent->right==x) { x->parent->right=y;}
            if(x->parent!=NULL && x->parent->left==x) { x->parent->left = y; }
            x->right = y->left;
           if(y->left!=NULL) { y->left->parent=x; }

            y->left=x;

           x->parent=y;

           if(y->parent==NULL) { root=y; }
                 //cout<<"i cri";
        }

        void RR(Node* x) {
            Node* y = x->left;
            y->parent = x->parent;
            if(x->parent!=NULL && x->parent->right==x) { x->parent->right=y;}
            if(x->parent!=NULL && x->parent->left==x) { x->parent->left=y;}
            x->left = y->right;
            if(y->right!=NULL) { y->right->parent=x; }
            y->right = x;
            x->parent = y;

             if(y->parent==NULL) { root=y; }
        }
        void Splay(Node* node) {
           cout<<"in";
           if(node->parent==NULL) { return; }
           cout<<"Ok";
            while(node->parent!=NULL) {


                if(node->parent==root) {
                   cout<<"into this alive "<<endl;
                    if(node->parent->right==node) {
                        //Perform left rotation on root
                      //  cout<<"hello i cri";
                        LR(root);
                       // cout<<"god please help me";

                    } else if(node->parent->left==node) {
                        //Perform right rotation on root
                        RR(root);
                    }
                } else {
                    //At least at height = 2

                    if(node->parent->right == node && node->parent->parent->right ==node->parent) {

                        //Perform left rotation on node's parent parent first then on node-sp parent
                        LR(node->parent->parent);
                      //cout<<"new root is: "<<root->data<<"and "<<node->parent->data<<endl;
                        LR(node->parent);
                    }
                    else if(node->parent->left!=NULL && node->parent->left==node && node->parent->parent->left==node->parent) {
                        //perform right rotation on node's grandparent then note's parent
                        RR(node->parent->parent);
                        RR(node->parent);

                    }

                    else if(node->parent->left ==node && node->parent->parent->right == node->parent) {
                        //perform right rotation on node's parent followed by left rotation on node's grandparent
                      Node *grandparent = node->parent->parent;
                        RR(node->parent);
                       // cout<<node->parent->parent->data;
                        LR(grandparent);

                    }

                    else if(node->parent->right==node && node->parent->parent->left==node->parent) {
                        //left rotation on node's parent followed by right rotation on node's grandparent
                         Node *grandparent = node->parent->parent;
                        LR(node->parent);

                        RR(grandparent);
                    }
                }
            }
            //Inorder(root);

        }

        void Inorder(Node* root) {
            if(root==NULL) { return; }
            Inorder(root->left);
            cout<<root->data<<" ";
            Inorder(root->right);
        }
        void Insert(int value) {
            Node* temp = root;
            if(temp!=NULL) { cout<<"root is : "<<temp->data<<endl; }
            Node* temp_parent = NULL;

            while(temp!=NULL) {
                temp_parent = temp;
              //  cout<<"temp is :"<<temp->data<<endl;
                int data = temp->data;
                if((data)<value) {temp = temp->right; }
                if((data)>value) { temp = temp->left; }
                //cout<<"ok"<<endl;
                //cout<<"new temp is "<<temp<<endl;
                if(temp==NULL) {break; }

            }


            if(temp_parent==NULL) { root = new Node(value); return; }

            if(temp_parent!=NULL) {
                Node *x = new Node(value);
                int data = temp_parent->data;
                if(value<data) {x->parent=temp_parent; temp_parent->left=x;  }
                if(value>data) {x->parent=temp_parent; temp_parent->right=x;  }

                Splay(x);

            }

        }
    Node* FindSuccessor(Node* node) {
        //cout<<"called"<<node->data<<endl;
        while(node->left!=NULL) { node=node->left;}
        return node;
    }
    void Delete(int value) {
        Node *temp = root;
        Node* temp_node = NULL;
        if(value==20) {
            //15 17 10 7 13
            cout<<root->right->parent->data;
            cout<<root->data<<" "<<root->right->data<<" "<<root->left->data<<" "<<root->left->left->data<<" "<<root->left->right->data<<endl;
        }
        //To implement delete function
        while(1) {
            temp_node = temp;

          cout<<temp_node->data<<endl;
        //  cout<<"temp ebfore"<<temp->data<<endl;
            if(temp->data<value) { temp = temp->right;}
            else if(temp->data>value) { temp = temp->left; }
           // cout<<temp<<endl;
             //cout<<"temp after "<<temp->data<<endl;
            if(temp==NULL) { break; }
            if(temp->data==value) { break; }


        }
        cout<<"finally"<<temp_node->data<<endl;
        if(temp==NULL) { cout<<"yes";Splay(temp_node); return; }

        //CASE 1: Node has no child
        if(temp->left==NULL and temp->right==NULL) {
            //if its root node;
            if(temp->parent==NULL) {
                delete temp;
                root = NULL;

            } else if(temp->parent!=NULL) {
                //Leaf node
                cout<<"17 is a leaf node"<<endl;
                Node *tempnode = temp;
                Node *temp_parent = temp->parent;
                 cout<<tempnode->parent->data<<endl;
                if(temp->parent->right==temp) { temp->parent->right=NULL;}
                if(temp->parent->left==temp) { temp->parent->left=NULL; }
                delete temp;
                //Splay the parent
                cout<<temp_parent->data<<endl;
                Splay(temp_parent);
            }
        //CASE 2: LEFT CHILD BUT NO RIGHT CHILD
        } else if(temp->left!=NULL && temp->right==NULL) {
                Node *tempnode = temp;
                if(temp->parent->left==temp) { temp->parent->left = temp->left; temp->left->parent=temp->parent;}
                else if(temp->parent->right==temp) { temp->parent->right = temp->left;temp->left->parent=temp->parent; }

                Splay(tempnode->parent);
        //CASE 3: RIGHT CHILD BUT NO LEFT CHILD
        } else if(temp->right!=NULL && temp->left==NULL) {
                Node *tempnode = temp;
                if(temp->parent->right==temp) { temp->parent->right = temp->right;temp->right->parent = temp->parent;}
                else if(temp->parent->left==temp) { temp->parent->left = temp->right;temp->right->parent = temp->parent; }
                Splay(tempnode->parent);
        //CASE 4: BOTH CHILD
        } else if(temp->right!=NULL && temp->left!=NULL) {
            cout<<"both child"<<endl;
            Node* parent = temp->parent;

            Node* tempnode = FindSuccessor(temp->right);//Find successor
            cout<<tempnode->data<<endl;
            cout<<tempnode->parent<<endl;
            temp->data = tempnode->data;

            if(tempnode->parent->right==tempnode) { cout<<"right";tempnode->parent->right = NULL;}
            if(tempnode->parent->left==tempnode) { tempnode->parent->left = NULL; }
            Node* tempnode_parent = tempnode->parent;
            delete tempnode;

            if(parent!=NULL) { Splay(parent);}
            cout<<"ok"<<endl;
        }

        }



};



int main() {
    SplayTree tree;
    int n;
    /**cout<<"Enter number of nodes: ";
    cin>>n;
    while(n--) {
        cout<<"\n Enter node: ";
        int x;
        cin>>x;
        tree.Insert(x);
        cout<<"\n Inorder: ";
        tree.Inorder(tree.root);
        cout<<"new root is : "<<tree.root->data<<endl;
        cout<<endl;

    }**/
    tree.root = new Node(14);
    tree.root->left = new Node(13);
    tree.root->left->parent = tree.root;
    tree.root->left->left = new Node(7);
    tree.root->left->left->parent = tree.root->left;
    tree.root->left->left->right = new Node(10);
    tree.root->left->left->right->right = new Node(12);
    tree.root->left->left->right->right->parent = tree.root->left->left->right;
    tree.root->left->left->right->parent = tree.root->left->left;
    tree.root->right = new Node(16);
    tree.root->right->parent = tree.root;
    tree.root->right->right = new Node(17);
    tree.root->right->right->parent = tree.root->right;
    tree.root->right->left = new Node(15);
    tree.root->right->left->parent = tree.root->right;


   cout<<"Enter number of nodes to delete: ";
    cin>>n;
    while(n--) {
        cout<<"\n Enter node: ";
        int x;
        cin>>x;
        tree.Delete(x);
        cout<<"\n Inorder: ";
        tree.Inorder(tree.root);
        cout<<"new root is : "<<tree.root->data<<endl;
        cout<<endl;

    }
//    cout<<tree.root->data<<" "<<tree.root->right->data<<" "<<tree.root->right->left->data<<" "<<tree.root->right->left->right->data<<" ";

    //tree.Insert(10);
    //tree.Insert(17);
    //tree.Insert(7);
    //tree.Insert(13);
    //tree.Insert(16);
}