#ifndef SplayTree_h__
#define SplayTree_h__
#include "utility.h"
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* _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:
//#==== 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();
//#||keyOffset|(Key const& `delta`)|void|O(1)
//#|將所有Element的Key同加上 `delta`
void keyOffset(Key const& __delta);
//#||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);
//#||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);
//
//
void print() const;
//#|=====================================================================
};
//#
//#[NOTE]
//#========================================
//# * 假設現在有兩個SplayTree `A` 和 `B`, 則:
//# ** 執行 `B.moveTo(&A)` 後 `B` 會變成空的, `A` 原本擁有的資料也會覆蓋掉
//# ** 執行 `A.merge(&B)` 或 `A.mergeAfter(&B)` 後
//# 如果檢查發現確實可以merge, 則之後 `B` 會變成空的
//#========================================
//#
//# '''
//#
}
#include "SplayTree.hpp"
#endif // SplayTree_h__
