diff options
Diffstat (limited to 'meowpp/dsa/SplayTree.h')
| -rw-r--r-- | meowpp/dsa/SplayTree.h | 1366 |
1 files changed, 1141 insertions, 225 deletions
diff --git a/meowpp/dsa/SplayTree.h b/meowpp/dsa/SplayTree.h index da451b0..5e9fb3c 100644 --- a/meowpp/dsa/SplayTree.h +++ b/meowpp/dsa/SplayTree.h @@ -2,234 +2,1150 @@ #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); - - - //#|===================================================================== +#include "../math/utility.h" + +namespace meow { + +/*! + * @brief + * + * 是一種神乎其技的資料結構, 維護一堆 Key->Value . 並且支援 + * 一些 \c std::map 難以快速實踐的操作, 如 \c split , \c merge , \c keyOffset + * + * Template Class Operators Request + * -------------------------------- + * + * |const?|Typename|Operator | Parameters |Return Type | Description | + * |-----:|:------:|----------:|:-------------|:----------:|:------------------| + * |const |Key |operator+ |(Key \c k) | Key |相加 | + * |const |Key |operator< |(Key \c k) | bool |大小比較 | + * | |Key |operator= |(Key \c k) | Key |copy oper | + * | |Key |Key |(int \c n) | |構子,\c n 永遠是0 | + * | |Value | Value |( ) | |建構子 | + * + * @note: + * -假設現在有兩個SplayTree `A` 和 `B`, 則: + * -執行 `B.moveTo(&A)` 後 `B` 會變成空的, `A` 原本擁有的資料也會覆蓋掉 + * -行 `A.merge(&B)` 或 `A.mergeAfter(&B)` 後 + * 如果檢查發現確實可以merge, 則之後 `B` 會變成空的 + * + * @author cat_leopard + */ +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): + key_(key), keyOffset_(0), value_(value) { + size_ = 1; + parent_ = NULL; + child_[0] = NULL; + child_[1] = NULL; + } + // + void keyOffset(Key const& delta) { + key_ = key_ + delta; + keyOffset_ = keyOffset_ + delta; + } + void syncDown() const { + for (size_t i = 0; i < 2; i++) { + if (child_[i] == NULL) continue; + child_[i]->keyOffset(keyOffset_); + } + ((Node*)this)->keyOffset_ = Key(0); + } + void syncUp() const { + ((Node*)this)->size_ = 1; + for (size_t i = 0; i < 2; i++) { + if (child_[i] == NULL) continue; + ((Node*)this)->size_ += child_[i]->size_; + } + } }; - //# - //#[NOTE] - //#======================================== - //# * 假設現在有兩個SplayTree `A` 和 `B`, 則: - //# ** 執行 `B.moveTo(&A)` 後 `B` 會變成空的, `A` 原本擁有的資料也會覆蓋掉 - //# ** 執行 `A.merge(&B)` 或 `A.mergeAfter(&B)` 後 - //# 如果檢查發現確實可以merge, 則之後 `B` 會變成空的 - //#======================================== - //# - //# ''' - //# -} -#include "SplayTree.hpp" + Node* root_; + + //! @brief 指定左子or右子, 連接parent<--->child + void connect(Node const* parent, size_t left_right, Node const* child) const { + Node* p = (Node*)parent; + Node* c = (Node*)child; + if (p != NULL) p->child_[left_right] = c; + if (c != NULL) c->parent_ = p; + } + + //! @brief 一路往上轉 + Node const* splay(Node const* node) const { + if (node != NULL && node->parent_ != NULL) { + for (const Node *g_grand, *grand, *parent, *child = node; ; ) { + g_grand = (grand = parent = child->parent_)->parent_; + size_t pc = (parent->child_[0] == child ? 0 : 1); + connect(parent, pc, child->child_[!pc]); + connect(child , !pc, parent); + if (g_grand != NULL) { + g_grand = (grand = g_grand)->parent_; + size_t gp = (grand->child_[0] == parent ? 0 : 1); + Node const* who = (pc == gp ? parent : child); + connect(grand, gp, who->child_[!gp]); + connect(who , !gp, grand); + grand->syncUp(); + } + parent->syncUp(); + child ->syncUp(); + if (g_grand == NULL) { + connect(NULL, 0, child); + break; + } + connect(g_grand, (g_grand->child_[0] == grand ? 0 : 1), child); + } + } + return (((SplayTree*)this)->root_ = (Node*)node); + } + + void clear(Node* node) { + if (node == NULL) return ; + clear(node->child_[0]); + clear(node->child_[1]); + delete node; + } + + Node* dup(Node* node2) { + if (node2 == NULL) return NULL; + node2->syncDown(); + Node* node = new Node(node2->key_, node2->value_); + connect(node, 0, dup(node2->child_[0])); + connect(node, 1, dup(node2->child_[1])); + node->syncUp(); + return node; + } + + Node const* findKey(Node const* node, Key const& key) const { + Node const* ret = node; + while (node != NULL) { + node->syncDown(); + ret = node; + if (!(key < node->key_)) { + if (!(node->key_< key)) break; + node = node->child_[1]; + } + else { + node = node->child_[0]; + } + } + return ret; + } + Node const* findMinMax(Node const* node, bool minimum) const { + Node const* ret = node; + for (int i = minimum ? 0 : 1; node != NULL; node = node->child_[i]) { + node->syncDown(); + ret = node; + } + return ret; + } + Node const* findOrder(Node const* node, size_t order) const { + Node const* ret = node; + while (node != NULL) { + node->syncDown(); + ret = node; + size_t ord = 1 + (node->child_[0] == NULL ? 0 : node->child_[0]->size_); + if (ord == order) return ret; + else if(ord < order){ node = node->child_[1]; order -= ord; } + else { node = node->child_[0]; } + } + return ret; + } + + void split(Node* root, Node** left, Node** right) { + if (root == NULL) { *left = NULL; *right = NULL; return ; } + root->syncDown(); + *left = root; + *right = root->child_[1]; + if (*right != NULL) { + (*left )->child_[1] = NULL; + (*right)->parent_ = NULL; + (*left )->syncUp(); + } + } + Node* merge(Node* left, Node* right) { + if (left == NULL) return right; + if (right == NULL) return left ; + left->syncDown(); + connect(left, 1, right); + left->syncUp(); + return left; + } +public: + /*! + * @brief 類似 \c stl 的 \c iterator ,不過這邊叫做\c Element + * + * 用來當作回傳資料的媒介 + */ + class Element{ + private: + typedef std::pair<Key const&, Value&> Entry; + Entry* entry_; + Node * node_; + // + void reset(Node* node) { + node_ = node; + delete entry_; + entry_ = (node == NULL ? NULL : new Entry(node->key_, node->value_)); + } + public: + Element(): entry_(NULL), node_(NULL) { + } + Element(Node* node): entry_(NULL), node_(NULL) { + reset(node); + } + Element(Element const& element2): entry_(NULL), node_(NULL) { + reset(element2.node_); + } + ~Element(){ + delete entry_; + } + + //! @brief 複製資料 + Element& copyFrom(Element const& e) { + reset(e.node_); + return *this; + } + + //! @brief 比對兩者是否為指向同一個Entry + bool same(Element const& e2) const { + return (node_ == e2.node_); + } + + //! @brief same as copyFrom + Element& operator=(Element const& e2) { + return copyFrom(e2); + } + + //! @brief 重導至\c std::pair<Key \c const&,\c Value&>* + Entry* operator->() { + return entry_; + } + + //! @brief 重導至\c std::pair<Key \c const&,\c Value&>& + Entry& operator*() { + return *entry_; + } + + //! @brief same as \c same(e2) + bool operator==(Element const& e2) const{ + return same(e2); + } + + //! @brief same as \c !same(e2) + bool operator!=(Element const& e2) const{ + return !same(e2); + } + }; + + //! @brief constructor + SplayTree(): root_(NULL) { + } + + //! @brief constructor, 複製資料 + SplayTree(SplayTree const& tree2): + root_(dup((Node*)(tree2.root_))) { + } + + //! @brief destructor + ~SplayTree(){ + clear(root_); + } + + /*! + * @brief 複製資料 + */ + SplayTree& copyFrom(SplayTree const& tree2) { + clear(root_); + root_ = dup((Node*)(tree2.root_)); + return *this; + } + + /*! + * @brief 將資料都丟到 \c tree2 身上, 並且清空自己 + */ + void moveTo(SplayTree* tree2) { + tree2->clear(); + tree2->root_ = root_; + root_ = NULL; + } + + /*! + * @brief 找出第一個(最小的) Element且 \c k <= 它的 Key, 並且回傳之. + * + * 找不到的話回傳 \c this->end() + */ + Element lowerBound(Key const& key) const { + splay(findKey(root_, key)); + if (root_ == NULL || !(root_->key_ < key)) return Element(root_); + if (root_->child_[1] == NULL) return Element(NULL); + splay(findMinMax(root_->child_[1], true)); + return Element(root_); + } + + /*! + * @brief 找出第一個(最小的) Element且 \c k < 它的 Key, 並且回傳之. + * + * 找不到的話回傳 \c this->end() + */ + Element upperBound(Key const& key) const { + splay(findKey(root_, key)); + if (root_ == NULL || key < root_->key_) return Element(root_); + if (root_->child_[1] == NULL) return Element(NULL); + splay(findMinMax(root_->child_[1], true)); + return Element(root_); + } + + /*! + * @brief 找出第一個(最小的) Element且 \c k >= 它的 Key, 並且回傳之. + * + * 找不到的話回傳 \c this->end() + */ + Element rLowerBound(Key const& key) const { + splay(findKey(root_, key)); + if (root_ == NULL || !(key < root_->key_)) return Element(root_); + if (root_->child_[0] == NULL) return Element(NULL); + splay(findMinMax(root_->child_[0], false)); + return Element(root_); + } + + /*! + * @brief 找出第一個(最小的) Element且 \c k > 它的 Key, 並且回傳之. + * + * 找不到的話回傳 \c this->end() + */ + Element rUpperBound(Key const& key) const { + splay(findKey(root_, key)); + if (root_ == NULL || root_->key_ < key) return Element(root_); + if (root_->child_[0] == NULL) return Element(NULL); + splay(findMinMax(root_->child_[0], false)); + return Element(root_); + } + + /*! + * @brief 找出 Key= \c k 的Elemenet 並回傳. 找不到的話回傳 \c this->end() + */ + Element find(Key const& key) const { + splay(findKey(root_, key)); + if (root_ != NULL && !(key < root_->key_) && !(root_->key_ < key)) { + return Element(root_); + } + return Element(NULL); + } + + /*! + * @brief 將Elements依照Key由小到大排序, 回傳第 \c ord 個Element (由0算起). + * + * 其中如果 \c ord>N-1, 則會回傳 \c this->last() + */ + Element order(size_t order) const { + if (root_ == NULL || order >= root_->size_) return Element(NULL); + splay(findOrder(root_, order + 1)); + return Element(root_); + } + + /*! + * @brief 回傳Key最小的Element, 如果SplayTree為空, 則回傳 \c this->end() + */ + Element first() const { + splay(findMinMax(root_, true)); + return Element(root_); + } + + /*! + * @brief 回傳Key最大的Element, 如果SplayTree為空, 則回傳 \c this->end() + */ + Element last() const { + splay(findMinMax(root_, false)); + return Element(root_); + } + + /*! + * @brief 回傳一個指向NULL的Element, + * + * 以供 \c find ,\c order ,\c first ,\c last 等判斷是否有找到相對應的Element + */ + Element end() const { + return Element(NULL); + } + + /*! + * @brief 回傳資料個數 + */ + size_t size() const { + return (root_ == NULL ? 0 : root_->size_); + } + + /*! + * @brief 回傳是否為空 + */ + bool empty() const{ + return (size() == 0); + } + + /*! + * @brief 清空 + */ + void clear() { + clear(root_); + root_ = NULL; + } + + /*! + * @brief 插入一組\c (Key ---> \c Value) + * + * 檢查是否已有Element的Key 為 \c key, 若有則回傳 \c false , 否則將 + * 一個 (Key -> Value) = (\c key -> \c value)的Element加入, 並回傳 \c true + */ + bool insert(Key const& key, Value const& value) { + if (root_ == NULL) { + root_ = new Node(key, value); + } + else { + Node* parent = (Node*)findKey(root_, key); + if (!(parent->key_ < key) && !(key < parent->key_)) { + splay(parent); + return false; + } + Node* new_node = new Node(key, value); + connect(parent, (parent->key_ < key ? 1 : 0), new_node); + parent->syncUp(); + splay(new_node); + } + return true; + } + + /*! + * @brief 刪除一組資料 + * + * 檢查是否已有Element的Key 為 \c key, 若有則刪除之, 並回傳 \c true, + * 否則則回傳 \c false + */ + bool erase(Key const& key) { + if (root_ == NULL) return false; + Node* body = (Node*)findKey(root_, key); + if (body->key_ < key || key < body->key_) { + splay(body); + return false; + } + Node* ghost; + if (body->child_[1] == NULL) { + ghost = body->child_[0]; + if (ghost != NULL) ghost->syncDown(); + } + else { + ghost = (Node*)findMinMax(body->child_[1], true); + connect(ghost, 0, body->child_[0]); + if (ghost != body->child_[1]) { + connect(ghost->parent_, 0, ghost->child_[1]); + connect(ghost, 1, body->child_[1]); + for (Node* a = ghost->parent_; a != ghost; a = a->parent_) + a->syncUp(); + } + ghost->syncUp(); + } + Node* parent = body->parent_; + connect(parent, parent != NULL && parent->child_[0] == body ? 0 : 1, ghost); + delete body; + splay(ghost != NULL ? ghost : parent); + return true; + } + + /*! + * @brief 將所有Element的Key同加上 \c delta + */ + void keyOffset(Key const& delta) { + if (root_ != NULL) { + root_->keyOffset(delta); + } + } + + /*! + * @brief 將\c tree2 清空, 再將所有Key > \c upper_bound 的Element都丟過去 + */ + void splitOut(Key const& upper_bound, SplayTree* right) { + right->clear(); + if (rLowerBound(upper_bound) != end()) { + split(root_, &root_, &(right->root_)); + } + else { + right->root_ = root_; + root_ = NULL; + } + } + + /*! + * @brief 合併 + * + * 檢查是否自己中的 Key 都小於 \c tree2 中的Key, 是的話把 \c tree2` + * 中的 Element 都搬到自己這, 同時清空 \c tree2 , 否則回傳 \c false + */ + bool mergeAfter(SplayTree* tree2) { + if (root_ == NULL || tree2->root_ == NULL || + last()->first < tree2->first()->first) { + root_ = merge(root_, tree2->root_); + tree2->root_ = NULL; + return true; + } + return false; + } + + /*! + * @brief 合併 + * + * 檢查是否自己中的 Key 都小於 \c tree2 中的Key, 或是完全相反, + * 是的話把 \c tree2`中的 Element 都搬到自己這, + * 同時清空 \c tree2 , 否則回傳 \c false + */ + bool merge(SplayTree* tree2) { + if (root_ == NULL || tree2->root_ == NULL || + last()->first < tree2->first()->first) { + root_ = merge(root_, tree2->root_); + } + else if(tree2->last()->first < first()->first) { + root_ = merge(tree2->root_, root_); + } + else { + return false; + } + tree2->root_ = NULL; + return true; + } + + /*! + * @brief 就像\c stl::map::operator[] + * + * 會先檢查是否已有Element的Key 為 \c key, 若有則回傳相對應的Value的Reference + * 否則先執行 \c insert(key,Value()) 再回傳相對應的Reference + */ + Value& operator[](Key const& key) { + if (find(key) == end()) insert(key, Value()); + return root_->value_; + } + + //! @brief same as \c copyFrom(tree2) + SplayTree& operator=(SplayTree const& tree2) { + return copyFrom(tree2); + } +}; + +/*! + * @brief + * + * 基本上跟SplayTree一樣, 不過這邊結合線段樹, 多了區間操作 + * (線段樹相關operator定義請見 \c SegmentTree ) + * + * Template Class Operators Request + * -------------------------------- + * + * |const?|Typename|Operator | Parameters |Return Type | Description | + * |-----:|:------:|----------:|:-------------|:----------:|:------------------| + * |const |Key |operator+ |(Key \c k) | Key |相加 | + * |const |Key |operator< |(Key \c k) | bool |大小比較 | + * | |Key |operator= |(Key \c k) | Key |copy oper | + * | |Key |Key |(int \c n) | |構子,\c n 永遠是0 | + * | |Value | Value |( ) | |建構子 | + * + * @note: + * -假設現在有兩個SplayTree `A` 和 `B`, 則: + * -執行 `B.moveTo(&A)` 後 `B` 會變成空的, `A` 原本擁有的資料也會覆蓋掉 + * -行 `A.merge(&B)` 或 `A.mergeAfter(&B)` 後 + * 如果檢查發現確實可以merge, 則之後 `B` 會變成空的 + * + * @author cat_leopard + */ +template<class Key, class Value> +class SplayTree_Range { +private: + struct Node { + Value valueOffset_; + Value range_; + Key key_; + Key keyOffset_; + Value value_; + bool same_; + size_t size_; + Node* parent_; + Node* child_[2]; + + Node(Key const& key, Value const& value): + valueOffset_(0), range_(value), + key_(key), keyOffset_(0), value_(value) { + same_ = false; + size_ = 1; + parent_ = NULL; + child_[0] = NULL; + child_[1] = NULL; + } + // + void keyOffset(Key const& delta) { + key_ = key_ + delta; + keyOffset_ = keyOffset_ + delta; + } + void valueUpdate(Value const& delta, bool over) { + if(over) { + value_ = delta * size_; + valueOffset_ = delta; + range_ = delta * size_; + same_ = true; + } + else { + value_ = value_ + delta * size_; + valueOffset_ = valueOffset_ + delta; + range_ = range_ + delta * size_; + } + } + void syncDown() const { + for (size_t i = 0; i < 2; i++) { + if (child_[i] == NULL) continue; + child_[i]->keyOffset(keyOffset_); + child_[i]->valueUpdate(valueOffset_, same_); + } + ((Node*)this)->keyOffset_ = Key(0); + ((Node*)this)->valueOffset_ = Value(0); + ((Node*)this)->same_ = false; + } + void syncUp() const { + ((Node*)this)->size_ = 1; + Value* v[3] = {&(((Node*)this)->value_), NULL, NULL}; + size_t vct = 1; + for (size_t i = 0; i < 2; i++) { + if (child_[i] == NULL) continue; + ((Node*)this)->size_ += child_[i]->size_; + v[vct++] = &(child_[i]->range_); + } + if (vct == 1) ((Node*)this)->range_ = (*v[0]); + else if(vct == 2) ((Node*)this)->range_ = (*v[0]) | (*v[1]); + else ((Node*)this)->range_ = (*v[0]) | (*v[1]) | (*v[2]); + } + }; + + Node* root_; + + //! @brief 指定左子or右子, 連接parent<--->child + void connect(Node const* parent, size_t left_right, Node const* child) const { + Node* p = (Node*)parent; + Node* c = (Node*)child; + if (p != NULL) p->child_[left_right] = c; + if (c != NULL) c->parent_ = p; + } + + //! @brief 一路往上轉 + Node const* splay(Node const* node) const { + if (node != NULL && node->parent_ != NULL) { + for (const Node *g_grand, *grand, *parent, *child = node; ; ) { + g_grand = (grand = parent = child->parent_)->parent_; + size_t pc = (parent->child_[0] == child ? 0 : 1); + connect(parent, pc, child->child_[!pc]); + connect(child , !pc, parent); + if (g_grand != NULL) { + g_grand = (grand = g_grand)->parent_; + size_t gp = (grand->child_[0] == parent ? 0 : 1); + Node const* who = (pc == gp ? parent : child); + connect(grand, gp, who->child_[!gp]); + connect(who , !gp, grand); + grand->syncUp(); + } + parent->syncUp(); + child ->syncUp(); + if (g_grand == NULL) { + connect(NULL, 0, child); + break; + } + connect(g_grand, (g_grand->child_[0] == grand ? 0 : 1), child); + } + } + return (((SplayTree_Range*)this)->root_ = (Node*)node); + } + + void clear(Node* node) { + if (node == NULL) return ; + clear(node->child_[0]); + clear(node->child_[1]); + delete node; + } + + Node* dup(Node* node2) { + if (node2 == NULL) return NULL; + node2->syncDown(); + Node* node = new Node(node2->key_, node2->value_); + connect(node, 0, dup(node2->child_[0])); + connect(node, 1, dup(node2->child_[1])); + node->syncUp(); + return node; + } + + Node const* findKey(Node const* node, Key const& key) const { + Node const* ret = node; + while (node != NULL) { + node->syncDown(); + ret = node; + if (!(key < node->key_)) { + if (!(node->key_< key)) break; + node = node->child_[1]; + } + else { + node = node->child_[0]; + } + } + return ret; + } + Node const* findMinMax(Node const* node, bool minimum) const { + Node const* ret = node; + for (int i = minimum ? 0 : 1; node != NULL; node = node->child_[i]) { + node->syncDown(); + ret = node; + } + return ret; + } + Node const* findOrder(Node const* node, size_t order) const { + Node const* ret = node; + while (node != NULL) { + node->syncDown(); + ret = node; + size_t ord = 1 + (node->child_[0] == NULL ? 0 : node->child_[0]->size_); + if (ord == order) return ret; + else if(ord < order){ node = node->child_[1]; order -= ord; } + else { node = node->child_[0]; } + } + return ret; + } + + void split(Node* root, Node** left, Node** right) { + if (root == NULL) { *left = NULL; *right = NULL; return ; } + root->syncDown(); + *left = root; + *right = root->child_[1]; + if (*right != NULL) { + (*left )->child_[1] = NULL; + (*right)->parent_ = NULL; + (*left )->syncUp(); + } + } + Node* merge(Node* left, Node* right) { + if (left == NULL) return right; + if (right == NULL) return left ; + left->syncDown(); + connect(left, 1, right); + left->syncUp(); + return left; + } +public: + /*! + * @brief 類似 \c stl 的 \c iterator ,不過這邊叫做\c Element + * + * 用來當作回傳資料的媒介 + */ + class Element{ + private: + typedef std::pair<Key const&, Value&> Entry; + Entry* entry_; + Node * node_; + // + void reset(Node* node) { + node_ = node; + delete entry_; + entry_ = (node == NULL ? NULL : new Entry(node->key_, node->value_)); + } + public: + Element(): entry_(NULL), node_(NULL) { + } + Element(Node* node): entry_(NULL), node_(NULL) { + reset(node); + } + Element(Element const& element2): entry_(NULL), node_(NULL) { + reset(element2.node_); + } + ~Element(){ + delete entry_; + } + + //! @brief 複製資料 + Element& copyFrom(Element const& e) { + reset(e.node_); + return *this; + } + + //! @brief 比對兩者是否為指向同一個Entry + bool same(Element const& e2) const { + return (node_ == e2.node_); + } + + //! @brief same as copyFrom + Element& operator=(Element const& e2) { + return copyFrom(e2); + } + + //! @brief 重導至\c std::pair<Key \c const&,\c Value&>* + Entry* operator->() { + return entry_; + } + + //! @brief 重導至\c std::pair<Key \c const&,\c Value&>& + Entry& operator*() { + return *entry_; + } + + //! @brief same as \c same(e2) + bool operator==(Element const& e2) const{ + return same(e2); + } + + //! @brief same as \c !same(e2) + bool operator!=(Element const& e2) const{ + return !same(e2); + } + }; + + //! @brief constructor + SplayTree_Range(): root_(NULL) { + } + + //! @brief constructor, 複製資料 + SplayTree_Range(SplayTree_Range const& tree2): + root_(dup((Node*)(tree2.root_))) { + } + + //! @brief destructor + ~SplayTree_Range() { + clear(root_); + } + + /*! + * @brief 複製資料 + */ + SplayTree_Range& copyFrom(SplayTree_Range const& tree2) { + clear(root_); + root_ = dup((Node*)(tree2.root_)); + return *this; + } + + /*! + * @brief 將資料都丟到 \c tree2 身上, 並且清空自己 + */ + void moveTo(SplayTree_Range* tree2) { + tree2->clear(); + tree2->root_ = root_; + root_ = NULL; + } + + /*! + * @brief 找出第一個(最小的) Element且 \c k <= 它的 Key, 並且回傳之. + * + * 找不到的話回傳 \c this->end() + */ + Element lowerBound(Key const& key) const { + splay(findKey(root_, key)); + if (root_ == NULL || !(root_->key_ < key)) return Element(root_); + if (root_->child_[1] == NULL) return Element(NULL); + splay(findMinMax(root_->child_[1], true)); + return Element(root_); + } + + /*! + * @brief 找出第一個(最小的) Element且 \c k < 它的 Key, 並且回傳之. + * + * 找不到的話回傳 \c this->end() + */ + Element upperBound(Key const& key) const { + splay(findKey(root_, key)); + if (root_ == NULL || key < root_->key_) return Element(root_); + if (root_->child_[1] == NULL) return Element(NULL); + splay(findMinMax(root_->child_[1], true)); + return Element(root_); + } + + /*! + * @brief 找出第一個(最小的) Element且 \c k >= 它的 Key, 並且回傳之. + * + * 找不到的話回傳 \c this->end() + */ + Element rLowerBound(Key const& key) const { + splay(findKey(root_, key)); + if (root_ == NULL || !(key < root_->key_)) return Element(root_); + if (root_->child_[0] == NULL) return Element(NULL); + splay(findMinMax(root_->child_[0], false)); + return Element(root_); + } + + /*! + * @brief 找出第一個(最小的) Element且 \c k > 它的 Key, 並且回傳之. + * + * 找不到的話回傳 \c this->end() + */ + Element rUpperBound(Key const& key) const { + splay(findKey(root_, key)); + if (root_ == NULL || root_->key_ < key) return Element(root_); + if (root_->child_[0] == NULL) return Element(NULL); + splay(findMinMax(root_->child_[0], false)); + return Element(root_); + } + + /*! + * @brief 找出 Key= \c k 的Elemenet 並回傳. 找不到的話回傳 \c this->end() + */ + Element find(Key const& key) const { + splay(findKey(root_, key)); + if (root_ != NULL && !(key < root_->key_) && !(root_->key_ < key)) { + return Element(root_); + } + return Element(NULL); + } + + /*! + * @brief 將Elements依照Key由小到大排序, 回傳第 \c ord 個Element (由0算起). + * + * 其中如果 \c ord>N-1, 則會回傳 \c this->last() + */ + Element order(size_t order) const { + if (root_ == NULL || order >= root_->size_) return Element(NULL); + splay(findOrder(root_, order + 1)); + return Element(root_); + } + + /*! + * @brief 回傳Key最小的Element, 如果SplayTree為空, 則回傳 \c this->end() + */ + Element first() const { + splay(findMinMax(root_, true)); + return Element(root_); + } + + /*! + * @brief 回傳Key最大的Element, 如果SplayTree為空, 則回傳 \c this->end() + */ + Element last() const { + splay(findMinMax(root_, false)); + return Element(root_); + } + + /*! + * @brief 回傳一個指向NULL的Element, + * + * 以供 \c find ,\c order ,\c first ,\c last 等判斷是否有找到相對應的Element + */ + Element end() const { + return Element(NULL); + } + + /*! + * @brief 回傳資料個數 + */ + size_t size() const { + return (root_ == NULL ? 0 : root_->size_); + } + + /*! + * @brief 回傳是否為空 + */ + bool empty() const{ + return (size() == 0); + } + + /*! + * @brief 查找 + * + * 詢問目前整個range的值 + */ + Value query() const { + if (root_ == NULL) return Value(0); + return root_->range_; + } + + /*! + * @brief 查找 + * + * 詢問給定range的值 + */ + Value query(Key const& first, Key const& last) const { + SplayTree_Range* self = (SplayTree_Range*)this; + Node* tmp; + rUpperBound(first); + self->split(self->root_, &tmp, &(self->root_)); + upperBound(last); + Value ret(0); + if (root_ != NULL && root_->child_[0] != NULL) { + ret = root_->child_[0]->range_; + } + self->root_ = self->merge(tmp, self->root_); + return ret; + } + + /*! + * @brief 清空 + */ + void clear() { + clear(root_); + root_ = NULL; + } + + /*! + * @brief 插入一組\c (Key ---> \c Value) + * + * 檢查是否已有Element的Key 為 \c key, 若有則回傳 \c false , 否則將 + * 一個 (Key -> Value) = (\c key -> \c value)的Element加入, 並回傳 \c true + */ + bool insert(Key const& key, Value const& value) { + if (root_ == NULL) { + root_ = new Node(key, value); + } + else { + Node* parent = (Node*)findKey(root_, key); + if (!(parent->key_ < key) && !(key < parent->key_)) { + splay(parent); + return false; + } + Node* new_node = new Node(key, value); + connect(parent, (parent->key_ < key ? 1 : 0), new_node); + parent->syncUp(); + splay(new_node); + } + return true; + } + + /*! + * @brief 刪除一組資料 + * + * 檢查是否已有Element的Key 為 \c key, 若有則刪除之, 並回傳 \c true, + * 否則則回傳 \c false + */ + bool erase(Key const& key) { + if (root_ == NULL) return false; + Node* body = (Node*)findKey(root_, key); + if (body->key_ < key || key < body->key_) { + splay(body); + return false; + } + Node* ghost; + if (body->child_[1] == NULL) { + ghost = body->child_[0]; + if (ghost != NULL) ghost->syncDown(); + } + else { + ghost = (Node*)findMinMax(body->child_[1], true); + connect(ghost, 0, body->child_[0]); + if (ghost != body->child_[1]) { + connect(ghost->parent_, 0, ghost->child_[1]); + connect(ghost, 1, body->child_[1]); + for (Node* a = ghost->parent_; a != ghost; a = a->parent_) + a->syncUp(); + } + ghost->syncUp(); + } + Node* parent = body->parent_; + connect(parent, parent != NULL && parent->child_[0] == body ? 0 : 1, ghost); + delete body; + splay(ghost != NULL ? ghost : parent); + return true; + } + + /*! + * @brief 將所有Element的Key同加上 \c delta + */ + void keyOffset(Key const& delta) { + if (root_ != NULL) { + root_->keyOffset(delta); + } + } + + /*! + * @brief 將所有Element的Value同加上 \c delta + */ + void valueOffset(Value const& delta){ + if (root_ != NULL) { + root_->valueUpdate(delta, false); + } + } + + /*! + * @brief 將所有Element的Value全部設定成\c value + */ + void valueOverride(Value const& value){ + if(root_ != NULL){ + root_->valueUpdate(value, true); + } + } + + /*! + * @brief 將\c tree2 清空, 再將所有Key > \c upper_bound 的Element都丟過去 + */ + void splitOut(Key const& upper_bound, SplayTree_Range* right) { + right->clear(); + if (rLowerBound(upper_bound) != end()) { + split(root_, &root_, &(right->root_)); + } + else { + right->root_ = root_; + root_ = NULL; + } + } + + /*! + * @brief 合併 + * + * 檢查是否自己中的 Key 都小於 \c tree2 中的Key, 是的話把 \c tree2` + * 中的 Element 都搬到自己這, 同時清空 \c tree2 , 否則回傳 \c false + */ + bool mergeAfter(SplayTree_Range* tree2) { + if (root_ == NULL || tree2->root_ == NULL || + last()->first < tree2->first()->first) { + root_ = merge(root_, tree2->root_); + tree2->root_ = NULL; + return true; + } + return false; + } + + /*! + * @brief 合併 + * + * 檢查是否自己中的 Key 都小於 \c tree2 中的Key, 或是完全相反, + * 是的話把 \c tree2`中的 Element 都搬到自己這, + * 同時清空 \c tree2 , 否則回傳 \c false + */ + bool merge(SplayTree_Range* tree2) { + if (root_ == NULL || tree2->root_ == NULL || + last()->first < tree2->first()->first) { + root_ = merge(root_, tree2->root_); + } + else if(tree2->last()->first < first()->first) { + root_ = merge(tree2->root_, root_); + } + else { + return false; + } + tree2->root_ = NULL; + return true; + } + + /*! + * @brief 就像\c stl::map::operator[] + * + * 會先檢查是否已有Element的Key 為 \c key, 若有則回傳相對應的Value的Reference + * 否則先執行 \c insert(key,Value()) 再回傳相對應的Reference + */ + Value& operator[](Key const& key) { + if (find(key) == end()) insert(key, Value()); + return root_->value_; + } + + //! @brief same as \c copyFrom(tree2) + SplayTree_Range& operator=(SplayTree_Range const& tree2){ + return copyFrom(tree2); + } +}; + +} #endif // dsa_SplayTree_h__ |