aboutsummaryrefslogtreecommitdiffstats
path: root/meowpp/dsa/SplayTree.h
diff options
context:
space:
mode:
authorcathook <b01902109@csie.ntu.edu.tw>2014-09-24 13:37:42 +0800
committercathook <b01902109@csie.ntu.edu.tw>2014-09-29 16:55:57 +0800
commit8b76fbb408f8eedab24195655c45c891af01eaab (patch)
tree414d7fc87885cb77e181a3ab99e334b837621036 /meowpp/dsa/SplayTree.h
parentef9af0d577c3a6b5d11fdeed7a9149d09973171b (diff)
downloadmeow-8b76fbb408f8eedab24195655c45c891af01eaab.tar.gz
meow-8b76fbb408f8eedab24195655c45c891af01eaab.tar.zst
meow-8b76fbb408f8eedab24195655c45c891af01eaab.zip
Big change, detail see README.
Diffstat (limited to 'meowpp/dsa/SplayTree.h')
-rw-r--r--meowpp/dsa/SplayTree.h1151
1 files changed, 0 insertions, 1151 deletions
diff --git a/meowpp/dsa/SplayTree.h b/meowpp/dsa/SplayTree.h
deleted file mode 100644
index 483b965..0000000
--- a/meowpp/dsa/SplayTree.h
+++ /dev/null
@@ -1,1151 +0,0 @@
-#ifndef dsa_SplayTree_h__
-#define dsa_SplayTree_h__
-
-#include <cstdlib>
-#include <utility>
-
-#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_;
- }
- }
- };
-
- 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);
- }
-};
-
-} // meow
-
-#endif // dsa_SplayTree_h__
generated by cgit (git 2.34.1) at 2025-06-16 12:32:20 +0800