#include <iostream>
#include "splay.h"

int main(){
  auto i = { 7, 8, 19, 10, 15, 9, 14, 12, 11, 23};

  splay<int>* spl = new splay<int>;
  for (auto const& e : i)
    spl->insert(e);

  std::cout<<"Splay Treen"<<spl->print()<<std::endl;
  auto number = 10;
  if (spl->find(number))
    number = 14;
  else
    std::cout<<"not foundn";

  std::cout<<"removing "<<number<<std::endl;
  spl->remove(number);
  std::cout<<spl->print()<<std::endl;

return 0;
}

#ifndef SPLAY_H
#define SPLAY_H
#include <memory>

template <class K, class V>
class node{
  public:
    node(K const& key,V const& value):
         key_ (key), value_ (value)
        { left = right =  nullptr; }
    std::shared_ptr< node<K,V> > left, right;
    std::weak_ptr< node<K,V> > parent;
    V value()
        {return value_;}
    K key()
        {return key_;}
    void key(const K& key)
        {key_ =key;}
  private:
    K  key_;
    V value_;
};


template <class T>
class splay
{
  public:
    typedef node<int,T> node;
    splay()
        { null_=nullptr; };

    void insert (const T& value)
        { insertNode_ (head_, null_, value); };
    void remove (const T& value)
        { markNode_ (head_, value); };
    bool find (const T& value)
        { return searchNode_ (head_, value); };
    std::string print ()
        { return print_inOrder_ (head_, ""); };

  private:
    std::shared_ptr<node> head_;
    std::shared_ptr<node> null_;

    void insertNode_ (std::shared_ptr<node>& current,  //recursive insert
        const std::shared_ptr<node>& parent,const T& value)
    {
      if (current == nullptr){
        current = std::make_shared<node> (0, value);
        current->parent = parent;
        if (current->parent.lock()!= null_)
      if (current != head_)
         splayNode(current);
      }
      else if (current->value() < value)
        insertNode_ (current->right, current, value);
      else if (current->value() > value)
        insertNode_ (current->left , current, value);
    }

    void markNode_ (const std::shared_ptr<node>& current,const T& value)
    {//recursively finds the  value, calls markRemove to remove the node
      if (current != nullptr) {
        if (current->value() < value)
          markNode_ (current->right, value);
        else if (current->value() > value)
          markNode_ (current->left , value);
        else
          removeNode_ (current);
      }
    }

    void removeNode_ (std::shared_ptr<node> current) //deletes node
    {
      if (current->right == nullptr) {
        if (current->left != nullptr)
          current->left->parent = current->parent;
        current = current->left;
      }
      else if (current->left == nullptr)  {
        current->left->parent = current->parent;
        current = current->right;
      }
      else  {                                       //worst case scenario
        std::shared_ptr<node> temp = current->right;
        while (temp->left != nullptr)
          temp = temp->left;
        temp->left = current->left;
        if (current->left != nullptr) {
          temp->left = current->left;
          temp->left->parent = temp;
          if (temp->right != nullptr)
            temp->right->parent= temp->parent;
          temp->parent.lock()->left = temp->right;
          temp->right=current->right;
          temp->right->parent=temp;
          if (current->parent.lock() == null_)
            head_ = temp;
          else if (current == current->parent.lock()->left)
            current->parent.lock()->left = temp;
          else
            current->parent.lock()->right= temp;
          current= std::move(temp);
        }
      }
    }

    bool searchNode_ (const std::shared_ptr<node>& current, const T& value)
    { //searches for node.
      if (current != nullptr) {
        if (current->value() < value)
          return searchNode_ (current->right, value);
        else if (current->value() > value)
          return searchNode_ (current->left , value);
        else  {
          splayNode(current);
          return true;
        }
      }
      return false;
    }

    void splayNode (const std::shared_ptr<node> current) {
      while (current != head_){
        if (head_ == current->parent.lock())  {
          if (head_->left == current)
            RR(current);
          else
            LR(current);
        }
        else  {
          if (current->parent.lock()->parent.lock()->left ==
              current->parent.lock())  {
            if (current->parent.lock()->left == current)  {
              RR(current->parent.lock());
              RR(current);
            }
            else  {
              LR(current);
              RR(current);
            }
          }
          else  {
            if (current->parent.lock()->right == current)  {
              LR(current->parent.lock());
              LR(current);
            }
            else  {
              RR(current);
              LR(current);
            }
          }
        }
      }
    }

    void LR(const std::shared_ptr<node> current)
    {
      current->parent.lock()->right = current->left;
      if (current->parent.lock()->right != nullptr)
        current->parent.lock()->right->parent = current->parent.lock();
      current->left = current->parent.lock();
      current->parent = current->left->parent;
      if (current->left->parent.lock() == null_)
        head_ = current;
      else if (current->left == current->left->parent.lock()->left)
        current->left->parent.lock()->left = current;
      else
        current->left->parent.lock()->right= current;
      current->left->parent = current;
    };

    void RR(const std::shared_ptr<node> current)
    {
      current->parent.lock()->left = current->right;
      if (current->parent.lock()->left != nullptr)
        current->parent.lock()->left->parent = current->parent.lock();
      current->right = current->parent.lock();
      current->parent = current->right->parent;
      if (current->right->parent.lock() == null_)
        head_ = current;
      else if (current->right == current->right->parent.lock()->left)
        current->right->parent.lock()->left = current;
      else
        current->right->parent.lock()->right= current;
      current->right->parent = current;
    };

    std::string print_inOrder_ (const std::shared_ptr<node>& current,
        std::string print)
    {
      if (current != nullptr) {
        print+= "["+ std::to_string(current->value())+ "]";
        print = print_inOrder_ (current->left, print);
        print = print_inOrder_ (current->right, print);
      }
      return print;
    }
};

#endif