/*
  Copyright 2012 Marek "p2004a" Rusinowski
  Splay tree
*/
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <set>

#define left s[0]
#define right s[1]

template <class T> class Splay {
  class node;
  node *root;

 public:
  Splay() : root(NULL) {}
  
  ~Splay() {
    if (root) delete root;
  }
  
  void insert(const T &value) {
    root = root ? root->insert(value) : new node(value, NULL);
  }
  
  void erase(const T &value) {
    if (root) {
      root = root->find(value);
      if (root->elem == value) {
        node *tmp = root;
        if (root->left == NULL) {
          root = root->right;
        } else if (root->right == NULL) {
          root = root->left;  
        } else {
          root = root->left;
          while (root->right != NULL) { 
            root = root->right->rotate();
          }
          root->right = tmp->right;
          root->right->parent = root;
        }
        root->parent = NULL;
        tmp->left = tmp->right = NULL;
        delete tmp;
      }
    }
  }
  
  bool find(const T &value) {
    if (root) {
      root = root->find(value);
      if (root->elem == value) return true;
    }
    return false;
  }
};

template <class T> class Splay<T>::node {
  node *s[2];
  node *parent;
  T elem;
  
  /* return true if i'm right son or false if i'm left son */
  bool direction() const {
    return this->parent->right == this ? true : false;
  }

 public:
  node(T value, node *par) : parent(par) {
    this->elem = value;
    this->right = this->left = NULL;
  }
  
  ~node() {
    if (this->left) delete this->left;
    if (this->right) delete this->right;
  }

  /* my parent become my son, and my son became my grandson */
  node *rotate() {
    bool dir = this->direction();
    node *q = this->s[!dir];
    node *p = this->parent;
    // setting my parent as my parent parent
    this->parent = p->parent;
    // if i'm not root, change my new parent son from my old parent to me
    if (this->parent != NULL) {
      this->parent->s[p->direction()] = this;
    }
    // setting me as my parent and my parent as my son
    this->s[!dir] = p;
    p->parent = this;
    // setting my old son as my old parent son
    p->s[dir] = q;
    // if my old son exist, set his parent to my old parent (now my son)
    if (q != NULL) {
      q->parent = p;
    }
    return this;
  }
  
  node *splay() {
    while (this->parent != NULL) {
      if (this->parent->parent == NULL) { // my parent is a root - Zig
        this->rotate();
      } else if (this->direction() == this->parent->direction()) { // Zig-Zig
        this->parent->rotate();
        this->rotate();
      } else { // Zig-Zag
        this->rotate();
        this->rotate();
      }
    }
    return this;
  }
  
  node *insert(const T &value) {
    if (value == this->elem) {
      return this->splay();
    } else {
      bool dir = value > this->elem;
      if (this->s[dir]) {
        return this->s[dir]->insert(value);
      } else {
        this->s[dir] = new node(value, this);
        return this->s[dir]->splay();
      }
    }
  }
  
  node *find(const T &value) {
    if (value < this->elem && this->left) {
      return this->left->find(value);
    } else if (value > this->elem && this->right) {
      return this->right->find(value);
    } else {
      return this->splay();
    }
  }

  friend class Splay<T>;
};

inline int los(int a, int b) {
  return rand() % (b - a + 1) + a;
}

int main() {
  srand(time(NULL));
  Splay<int> tree1;
  std::set<int> tree2;
  for (int i = 0; i < 1000000; ++i) {
    int losowa = los(1, 1000);
    switch(los(1, 3)) {
      case 1: {
        tree1.insert(losowa);
        tree2.insert(losowa);
        break;
      }
      case 2: {
        tree1.erase(losowa);
        tree2.erase(losowa);
        break;
      }
      case 3: {
        if (tree1.find(losowa) != (tree2.find(losowa) != tree2.end())) {
          printf("something went wrong...\n");
          return 1;
        }
        break;
      }
    }
  }
  return 0;
}