#ifndef   dsa_SplayTree_h__
#define   dsa_SplayTree_h__

#include <cstdlib>

#include <utility>

namespace meow{
  //#
  //#=== meow:: *SplayTree<Key, Value>* (C++ class)
  //#==== Description
  //#  `SplayTree` 是一種神乎其技的資料結構, 維護一堆 Key->Value . 並且支援
  //#  一些 `std::map` 難以快速實踐的操作, 如 `split` , `merge` , `keyOffset`
  //#
  //#==== Template Class Operators Request
  //#[options="header",width="70%",cols="1>m,1<,3<s,5<,3<,15<",grid="rows"]
  //#|=====================================================================
  //#|Const?|Typename| Operator| Parameters  | Return_Type| Description
  //#|const |Key     |operator+|(Key    `k`) | Key        | 相加
  //#|const |Key     |operator<|(Key    `k`) | bool       | 大小比較
  //#|      |Key     |'Key'    |(int    `n`) |            | 建構子, `n` 永遠是0
  //#|      |Value   | 'Value' |(          ) |            | 建構子
  //#|=====================================================================
  //#
  template<class Key, class Value>
  class SplayTree{
    private:
      struct Node{
        Key    _key;
        Key    _keyOffset;
        Value  _value;
        size_t _size;
        Node*  _parent;
        Node*  _child[2];
        //
        Node(Key const& __key, Value const& __value);
        //
        void keyOffset(Key const& __delta);
        void syncDown() const;
        void syncUp  () const;
      };
      //
      Node* _root;
      //
      void        connect(Node const* __parent, size_t __left_right,
                          Node const* __child) const;
      Node const* splay  (Node const* __node) const;
      //
      void  clear(Node* __node);
      Node*   dup(Node* __node);
      //
      Node const* findKey   (Node const* __node, Key const& __key    ) const;
      Node const* findMinMax(Node const* __node, bool       __minimum) const;
      Node const* findOrder (Node const* __node, size_t     __order  ) const;
      //
      void  split(Node* __root, Node** __left, Node** __right);
      Node* merge(              Node*  __left, Node*  __right);
    public:
      //#==== Custom Type Definitions
      //#
      //# * `Element` -> 用來當作回傳資料的媒介
      //# ** 重定義 `operator->()` 到 `std::pair<Key const&, Value&>*` 
      //# ** 重定義 `operator*()` 到 `std::pair<Key const&, Value&>&` 
      //# ** 有 `operator==` , `operator!=`, `operator=` 可用
      //# ** 可以直接用 `(*e).second = some_value` 來改變SplayTree中的資料
      //#
      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);
      //
      //#==== Support Methods
      //#
      //# * N <- `this` 中擁有的資料數
      //# * M <- `tree2` 中擁有的資料數
      //#
      //#[options="header",width="100%",cols="1>m,3>s,7<,3<,3^,20<",grid="rows"]
      //#|=====================================================================
      //#|Const?|Name | Parameters   | Return_Type| Time_Complexity| Description
      
      
      //#||moveTo|(SplayTree* `tree2`)|void|O(M)
      //#|將 `this` 的資料複寫到 `tree2` 上面, 同時清空自己, 
      //# 時間複雜度中的M是 `tree2` 所擁有的資料數
      void moveTo(SplayTree* __tree2);
      
      
      //#|const|lowerBound|(Key const& `k`)|Element|O(logN)
      //#|找出第一個(最小的) Element且 `k` <= 它的 Key, 並且回傳之.
      //# 找不到的話回傳 `this->end()`
      Element lowerBound(Key const& __key) const;
      
      
      //#|const|lowerBound|(Key const& `k`)|Element|O(logN)
      //#|找出第一個(最小的) Element且 `k` < 它的 Key, 並且回傳之.
      //# 找不到的話回傳 `this->end()`
      Element upperBound(Key const& __key) const;
      
      
      //#|const|lowerBound|(Key const& `k`)|Element|O(logN)
      //#|找出第一個(最小的) Element且 `k` >= 它的 Key, 並且回傳之.
      //# 找不到的話回傳 `this->end()`
      Element rLowerBound(Key const& __key) const;
      
      
      //#|const|lowerBound|(Key const& `k`)|Element|O(logN)
      //#|找出第一個(最小的) Element且 `k` > 它的 Key, 並且回傳之.
      //# 找不到的話回傳 `this->end()`
      Element rUpperBound(Key const& __key) const;
      
      
      //#|const|find|(Key const& `k`)|Element|O(logN)
      //#|找出 Key= `k` 的Elemenet 並回傳. 找不到的話回傳 `this->end()`
      Element find (Key const& __key) const;
      
      
      //#|const|order|(size_t `ord`)|Element|O(logN)
      //#|將Elements依照Key由小到大排序, 回傳第 `ord` 個Element (由0算起).
      //# 其中如果 `ord` > N - 1, 則會回傳 `this->last()`
      Element order(size_t __order) const;
      
      
      //#|const|first|(size_t `ord`)|Element|O(logN)
      //#|回傳Key最小的Element, 如果SplayTree為空, 則回傳 `this->end()`
      Element first() const;
      
      
      //#|const|last|(size_t `ord`)|Element|O(logN)
      //#|回傳Key最大的Element, 如果SplayTree為空, 則回傳 `this->end()`
      Element last() const;
      
      
      //#|const|end|()|Element|O(1)
      //#|回傳一個指向NULL的Element, 以供 `find` , `order` , `first`
      //# , `last` 等判斷是否有找到相對應的Element
      Element end() const;
      
      
      //#|const|size|()|size_t|O(1)| 回傳資料數
      size_t size() const;
      
      
      //#|const|size|()|bool|O(1)| 回傳是否為空
      bool empty() const;
      
      
      //#||clear|()|void|O(N)| 清空資料
      void clear();
      
      
      //#||insert|(Key const& `key`,\Value const& `value`)|bool|O(logN)
      //#|檢查是否已有Element的Key 為 `key`, 若有則回傳 `false` , 否則將
      //# 一個 (Key -> Value) = (`key` -> `value`)的Element加入, 並回傳 `true`
      //# 將所有Element的Key同加上 `delta`
      bool insert(Key const& __key, Value const& __value);
      
      
      //#||erase|(Key const& `key`)|bool|O(logN)
      //#|檢查是否已有Element的Key 為 `key`, 若有則刪除之, 並回傳 `true`,
      //# 否則則回傳 `false`
      bool erase(Key const& __key);
      
      
      //#||keyOffset|(Key const& `delta`)|void|O(1)
      //#|將所有Element的Key同加上 `delta`
      void keyOffset(Key const& __delta);
      
      
      //#||operator[]|(Key const& `key`)|Value&|O(logN)
      //#|檢查是否已有Element的Key 為 `key`, 若有則回傳相對應的Value的Reference
      //# 否則先執行 `insert(key, Value())` 再回傳相對應的Reference
      Value& operator[](Key const& __key);
      
      
      //#||splitOut|(Key const& `upper_bound`,\SplayTree* `tree2`)|void
      //#|O(logN) + O(M)
      //#|將 `tree2` 清空, 再將所有Key > `upper_bound` 的Element都丟到 `tree2`
      void splitOut(Key const& __upper_bound, SplayTree* __right);
      
      
      //#||mergeAfter|(SplayTree* `tree2`)|void|O(logN) + O(logM)
      //#|檢查是否 `this` 中的 Key 都小於 `tree2` 中的Key, 是的話把 `tree2` 
      //# 中的 Element 都搬到 `this` , 同時清空 `tree2` , 回傳 `true`. 否則
      //# 回傳 `false`
      bool mergeAfter(SplayTree* __tree2);
      
      
      //#||merge|(SplayTree* `tree2`)|void|O(logN) + O(logM)
      //#|檢查是否 `this` 中的 Key 都小於 `tree2` 中的Key 或者
      //# 是否 `this` 中的 Key 都大於 `tree2` 中的Key, 是的話把 `tree2` 
      //# 中的 Element 都搬到 `this` , 同時清空 `tree2` , 回傳 `true`. 否則
      //# 回傳 `false`
      bool merge(SplayTree* __tree2);
      
      
      //#|=====================================================================
  };
  //#
  //#[NOTE]
  //#========================================
  //# * 假設現在有兩個SplayTree `A` 和 `B`,  則:
  //# ** 執行 `B.moveTo(&A)` 後 `B` 會變成空的, `A` 原本擁有的資料也會覆蓋掉
  //# ** 執行 `A.merge(&B)` 或 `A.mergeAfter(&B)` 後
  //#    如果檢查發現確實可以merge, 則之後 `B` 會變成空的
  //#========================================
  //#
  //# '''
  //#
}

#include "SplayTree.hpp"

#endif // dsa_SplayTree_h__