#include <iostream>
#include <chrono>
#include <utility>
#include <cassert>
#include <cstdlib>
#include <string>


template<typename D = std::chrono::microseconds>
class Benchmark {
public:
    Benchmark(bool printOnExit = false) : m_print(printOnExit) {
        start = std::chrono::high_resolution_clock::now();
    }
    typename D::rep elapsed() const {
        auto end = std::chrono::high_resolution_clock::now();
        auto result = std::chrono::duration_cast<D>(end-start);
        return result.count();
    }
    ~Benchmark() {
        auto result = elapsed();
        if (m_print)
        {
            std::cerr << "Czas: " << result << "\n";
        }
    }
private:
    std::chrono::high_resolution_clock::time_point start;
    bool m_print = true;
};

template<typename KeyType, typename ValueType>
class Node{
public:
KeyType key;
ValueType value;
Node *left, *right;

Node(KeyType key, ValueType value) {
	this->key = key;
	this->value=value;
	left=right = NULL;
}

~Node() {
	if(left!=NULL)
        delete left;
    if(right!=NULL)
        delete right;
}
};

template<typename KeyType, typename ValueType>
class TreeMap
{
  public:
    using key_type = KeyType;
    using mapped_type = ValueType;
    using value_type = std::pair<key_type, mapped_type>;
    Node<KeyType, ValueType> *root;
    int treeSize;

    TreeMap(){
        treeSize=0;
        root=NULL;
   }
    bool isEmpty()
    {
        if (this->root==NULL)
            return true;
        else
        {
            std::cout<<root->value;
            std::cout<<"\n";
        }
        return false;

    }

 // A utility function to right
// rotate subtree rooted with y
// See the diagram given above.
Node<KeyType,ValueType> *rightRotate(Node<KeyType,ValueType> *x)
{
    Node<KeyType,ValueType> *y = x->left;
    x->left = y->right;
    y->right = x;
    return y;
}

// A utility function to left
// rotate subtree rooted with x
// See the diagram given above.
Node<KeyType,ValueType> *leftRotate(Node<KeyType,ValueType> *x)
{
    Node<KeyType,ValueType> *y = x->right;
    x->right = y->left;
    y->left = x;
    return y;
}

Node<KeyType,ValueType> *splay(Node<KeyType,ValueType> *node, KeyType key){
 // Base cases: root is NULL or
    // key is present at root
    if (node == NULL || node->key == key)
        return node;

    // Key lies in left subtree
    if (node->key > key)
    {
        // Key is not in tree, we are done
        if (node->left == NULL) return node;

        // Zig-Zig (Left Left)
        if (node->left->key > key)
        {
            // First recursively bring the
            // key as root of left-left
            node->left->left = splay(node->left->left, key);

            // Do first rotation for root,
            // second rotation is done after else
            node = rightRotate(node);
        }
        else if (node->left->key < key) // Zig-Zag (Left Right)
        {
            // First recursively bring
            // the key as root of left-right
            node->left->right = splay(node->left->right, key);

            // Do first rotation for root->left
            if (node->left->right != NULL)
                node->left = leftRotate(node->left);
        }

        // Do second rotation for root
        return (node->left == NULL)? node: rightRotate(node);
    }
    else // Key lies in right subtree
    {
        // Key is not in tree, we are done
        if (node->right == NULL) return node;

        // Zig-Zag (Right Left)
        if (node->right->key > key)
        {
            // Bring the key as root of right-left
            node->right->left = splay(node->right->left, key);

            // Do first rotation for root->right
            if (node->right->left != NULL)
                node->right = rightRotate(node->right);
        }
        else if (node->right->key < key)// Zag-Zag (Right Right)
        {
            // Bring the key as root of
            // right-right and do first rotation
            node->right->right = splay(node->right->right, key);
            node = leftRotate(node);
        }

        // Do second rotation for root
        return (node->right == NULL)? node: leftRotate(node);
    }
    }


Node<KeyType,ValueType> *insert(key_type key, mapped_type value){
       this->treeSize=this->treeSize+1;
       Node<KeyType,ValueType> *newnode=new Node<KeyType,ValueType>(key,value);
    if (this->root == NULL)
    {
        this->root=newnode;
        return newnode;
    }
    this->root=splay(this->root,value);
    if(this->root->key==key) return this->root;

    // If root's key is greater, make
    // root as right child of newnode
    // and copy the left child of root to newnode
    if (this->root->key > key)
    {

        newnode->right = this->root;
        newnode->left = this->root->left;
        this->root->left = NULL;
    }
    // If root's key is smaller, make
    // root as left child of newnode
    // and copy the right child of root to newnode
    else
    {
        newnode->left = this->root;
        newnode->right = this->root->right;
        this->root->right = NULL;
    }
    this->root=newnode;
    return newnode;
    }

    /*!
     * dodaje wpis do slownika przez podanie pary klucz-wartosc
     */
    void insert(value_type key_value)
    {
        insert(key_value.first,key_value.second);
    }

    /*!
     * zwraca referencje na wartosc dla podanego klucza
     *
     * jezeli elementu nie ma w slowniku, dodaje go
     */
    /*mapped_type& operator[](const key_type& key)
    {
        if(contains(key)==true)
            return root->value;
        insert(key)
    }*/

    /*!
     * zwraca wartosc dla podanego klucza
     */

    mapped_type value(key_type key)
    {
       if (contains(key)==false)
            {
                std::cout<<"Nie ma klucza dla "<<key<<"\n";
                return 0;
            }
        splay(root,key);
        return root->value;
    }

    /*!
     * zwraca informacje, czy istnieje w slowniku podany klucz
     */
bool contains(key_type key)  {
    this->root=splay(this->root,key);
    if(root==NULL)
        return false;
    if (this->root->key==key)
        return true;
    return false;
}

    /*!
     * zwraca liczbe wpisow w slowniku
     */

int size(){
    return this->treeSize;
}

mapped_type& operator[](const key_type& key)
    {
        if(contains(key)==true)
            {
                splay(this->root,key);
                return this->root->value;
            }
        //TODO: Dodac to zeby te asserty ostatnie sie wykonywaly, tylko nie mam pomyslu jak

    }


~TreeMap() {
	delete root;
}
};


int main()
{
    TreeMap<int,int> dict;

    // slownik jest pusty
    assert(dict.isEmpty() == true);
    assert(dict.size() == 0);
    assert(dict.contains(0) == false);

    // dodanie elementu do slownika
  dict.insert(0, 1);
    assert(dict.isEmpty() == false);
    assert(dict.size() == 1);
    assert(dict.contains(0) == true);
    assert(dict.value(0) == 1);

    // dodanie elementu do slownika jako pary
    dict.insert(std::pair<int,int>(1, 2));
    assert(dict.size() == 2);
    assert(dict.contains(1) == true);
    assert(dict.value(0) == 1);
    assert(dict.value(1) == 2);


    // operator []
    assert(dict[0] == 1);
    assert(dict[1] == 2);
/*
    // operator [] tworzy nowy element
    dict[2] = 3;
    assert(dict.value(2) == 3);
    assert(dict.size() == 3);*/


     //nadpisanie wartosci dla istniejacego elementu
    dict.insert(2, 4);
    assert(dict.size() == 3);
    assert(dict.value(2) == 4);

}