#ifndef   SplayTree_h__
#define   SplayTree_h__

#include "utility.h"

namespace meow{
  template<class Key, class Value>
  class SplayTree{
    private:
      struct Node{
        Key    _key;
        Key    _keyOffset;
        Value  _value;
        size_t _size;
        Node*  _parent;
        Node*  _lChild;
        Node*  _rChild;
        //
        Node(Key const& __key, Value const& __value);
      };
      //
      Node* _root;
      //
      void offsetAdd    (Node* __node, Key const& __delta) const;
      void offsetDown   (Node* __node                    ) const;
      void sizeUpdate   (Node* __node                    ) const;
      void connectLChild(Node* __parent, Node* __child   ) const;
      void connectRChild(Node* __parent, Node* __child   ) const;
      Node const* setRoot(Node* __node) const;
      //
      Node* clear  (Node* __node);
      Node* dup    (Node* __node);
      //
      void rotate(               Node* __parent, Node* __child) const;
      void rotate(Node* __grand, Node* __parent, Node* __child) const;
      Node* splay(Node* __node) const;
      //
      Node* findKey   (Node* __node, Key const& __key) const;
      Node* findMinMax(Node* __node, bool minimum    ) const;
      Node* findOrder (Node* __node, size_t __order  ) const;
      //
      void  split(Node* __root, Node** __left, Node** __right);
      Node* merge(              Node*  __left, Node*  __right);
      //
      void print(Node* __now, int __depth) const;
    public:
      class Element{
        private:
          typedef std::pair<Key const&, Value&> Entry;
          Entry* _entry;
          Node * _node;
          //
          void reset(Node* __node);
        public:
          Element();
          Element(Node* __node);
          Element(Element const& __iterator2);
          ~Element();
          //
          Element& operator=(Element const& __e2);
          //
          Entry* operator->();
          Entry& operator *();
          //
          bool operator==(Element const& __e2) const;
          bool operator!=(Element const& __e2) const;
      };
      //
      SplayTree();
      SplayTree(SplayTree const& __tree2);
      ~SplayTree();
      //
      SplayTree& operator=(SplayTree const& __tree2);
      void moveTo(SplayTree* __tree2);
      //
      Element  lowerBound(Key const& __key) const;
      Element  upperBound(Key const& __key) const;
      Element rLowerBound(Key const& __key) const;
      Element rUpperBound(Key const& __key) const;
      Element find (Key const& __key) const;
      Element order(size_t __order  ) const;
      Element first(                ) const;
      Element last (                ) const;
      Element   end(                ) const;
      //
      size_t  size() const;
      bool   empty() const;
      //
      void   clear();
      void   keyOffset(Key const& __delta);
      bool   insert      (Key const& __key, Value const& __value);
      bool   erase       (Key const& __key);
      Value& operator[](Key const& __key);
      void   splitOut(Key const& __upper_bound, SplayTree* __right);
      bool   mergeAfter(SplayTree* __tree2);
      bool   merge     (SplayTree* __tree2);
      //
      void print() const;
  };
  /*********************************************************
    @asciidoc
    === meow:: *SplayTree<Key, Value>* (C++ class)
    .Description
    Like `std::map`, `SplayTree` is an dictionary(key->value). But it has
    some extra method, such as `split()`, `merge()`, `keyOffset()`.

    .Data Type
   * `Key` is the tyepname of the key
   * `Value` is the typename of value
   * `SplayTree<Key, Value>:: *Element* ` is a typename which contain
   (key->value). It has some methods below:
   ** `->first ` a constant reference to `Key`
   ** `->second` a reference to `Value`
   ** `operator==, operator!=` compare function, check if the two `Element`
   is pointer to the same (key->value)
   
   .Template Request
   * `Key` should has `operator<`, `operator+`

   .Support Methods
   * N <- numbers of element in the SplayTree
   * M <- numbers of element in another SplayTree
   [options="header",width="100%",cols="1>,1<s,5<,1<,3^,10<",grid="rows"]
   |=======================================================================
   |Const?|Name| Parameters| Return Type| Time Complexity| Description
   ||operator=|(SplayTree const&)| *this | O(N) | copy operator
   ||moveTo|(SplayTree* t)|void|O(M)| Transform the data in this to `t`
   |const|lowerBound|(Key k)|Element|O(logN)| Find the smallest (key->value) 
   which `k <= key` and return
   |const|upperBound|(Key k)|Element|O(logN)| Find the smallest (key->value) 
   which `k < key` and return
   |const|rLowerBound|(Key k)|Element|O(logN)| Find the largest (key->value) 
   which `key <= k` and return
   |const|rUpperBound|(Key k)|Element|O(logN)| Find the largest (key->value) 
   which `key < k` and return
   |const| find|(Key k)|Element|O(logN)| Find the element (key->value) which
   `key == k` and return
   |const|order|(size_t k)|Element|O(logN)| Find the `k`-th small element.
   note that `k` start from zero like a normal C/C++ array.
   |const|first|()|Element|O(logN)| Return the smallest element
   |const|last|()|Element|O(logN)| Return the largest element
   |const|end|()|Element|O(1)|Return an empty element(it can be use to 
   check if `find()` is successful)
   |const|size|()|size_t|O(1)| Return number of elements in the tree
   |const|empty|()|bool|O(1)|Return whether the tree is empty
   ||clear|()|void|O(N)|Clear
   ||keyOffset|(Key offset)|void|O(1)| Let all the keys in the tree
   plus offset
   ||insert|(Key k, Value v)|bool | O(logN)| Insert an element.
   If the tree already has an element with same key, return `false`.
   ||erase|(Key k)|bool | O(logN)|Erase an element from the tree with
   given key. Return `false` if the element not found.
   ||operator[]|(Key k)|Value|O(logN)|Like `find()` , but it will insert an element
   automatic if the corrosponding element not found
   ||splitOut|(Key const& upper_bound, +
   SplayTree* out)|void | O(log N) | Split out all the elements with key
   larger than `upper_bound` and store then into `out`
   ||mergeAfter|(SplayTree* t)|bool|O(logN + logM)|If not all of the elements in this
   are smaller than elements in `t`, return `false` , else merge `t` into
   itself and return `true`.
   ||merge|(SplayTree* t)|bool|O(logN + logM)|If all of the elements in this
   are smaller than elements in `t` or all of the elements in this larger than 
   elements in `t` , merge `t` into itself and return `true`.
   Else return `false`
   |=======================================================================
WARNING: Consider there are two SplayTree `A` and `B`. +
`B` will become empty after you call `A.mergeAfter(&B)`
or `A.merge(&B)` successful. +
The data in `B` will override by data in `A` and `A` will become empty after
you call `A.moveTo(&B)`

'''
@asciidoc-
   *********************************************************/
}

#include "SplayTree.hpp"

#endif // SplayTree_h__