diff options
author | cathook <b01902109@csie.ntu.edu.tw> | 2014-04-25 01:53:47 +0800 |
---|---|---|
committer | cathook <b01902109@csie.ntu.edu.tw> | 2014-04-25 01:53:47 +0800 |
commit | 04e55aa4560f597373ca58c29f57fe6c98d11a50 (patch) | |
tree | d9782d703266e0962d6c34de0c1faf043474be1b /meowpp | |
parent | 77038a76911ecbb32931a51e2ac8eb9d32cc13da (diff) | |
download | meow-04e55aa4560f597373ca58c29f57fe6c98d11a50.tar meow-04e55aa4560f597373ca58c29f57fe6c98d11a50.tar.gz meow-04e55aa4560f597373ca58c29f57fe6c98d11a50.tar.bz2 meow-04e55aa4560f597373ca58c29f57fe6c98d11a50.tar.lz meow-04e55aa4560f597373ca58c29f57fe6c98d11a50.tar.xz meow-04e55aa4560f597373ca58c29f57fe6c98d11a50.tar.zst meow-04e55aa4560f597373ca58c29f57fe6c98d11a50.zip |
add BIT
Diffstat (limited to 'meowpp')
-rw-r--r-- | meowpp/dsa/BinaryIndexTree.h | 69 | ||||
-rw-r--r-- | meowpp/dsa/BinaryIndexTree.hpp | 44 | ||||
-rw-r--r-- | meowpp/dsa/SplayTree.h | 52 | ||||
-rw-r--r-- | meowpp/dsa/SplayTree.hpp | 467 |
4 files changed, 351 insertions, 281 deletions
diff --git a/meowpp/dsa/BinaryIndexTree.h b/meowpp/dsa/BinaryIndexTree.h new file mode 100644 index 0000000..4b1b23a --- /dev/null +++ b/meowpp/dsa/BinaryIndexTree.h @@ -0,0 +1,69 @@ +#ifndef __BinaryIndexTree_H__ +#define __BinaryIndexTree_H__ + +namespace meow{ + //# + //#=== meow:: *BinaryIndexTree<Value>* (C++ class) + //#==== Description + //# 極度簡化版的 `SegmentTree` 已無法區間操作, 區間詢問的區間開頭也一定要 + //# 在 `index=0` 的地方 + //# + //#==== 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 | Value | operator+ |(Value `n`) | Value | 合併用(類似 + //# `SegmentTree` 的 + //# operator{b} ) + //#|===================================================================== + //# + template<class Value> + class BinaryIndexTree{ + private: + std::vector<Value> _array; + public: + BinaryIndexTree(); + BinaryIndexTree(size_t __size, Value const& __value); + BinaryIndexTree(BinaryIndexTree const& __tree2); + + //#==== Support Methods + //# + //# * N <- `this` 中擁有的資料數 + //# + //#[options="header",width="100%",cols="1>m,3>s,7<,3<,3^,20<",grid="rows"] + //#|===================================================================== + //#|Const?|Name | Parameters | Return_Type| Time_Complexity| Description + + + //#||reset|(size_t `size`, Value const& `value`)|void|O(`size`) + //#|將資料長度刷成 `N = size` 且每一個元素都是 `value` + void reset(size_t __size, Value const& __value); + + + //#||update|(size_t `index`, Value const& `value`)|void|O(logN) + //#|將第 `index` (從零開始算) 多加上 `value` + void update( size_t __index, Value const& __value); + + + //#|const|query|(size_t `index`)|void|O(logN) + //#|詢問 `0~index` 的區間值 + Value query (ssize_t __index) const; + + + //#|===================================================================== + }; + //# + //#[NOTE] + //#======================================== + //# * 一般來說只能用在維護區間總和, 維護區間最大值只有在特殊情況才可以, 即 + //# '針對每個元素, 每次 update() 的值一定會大於等於原本的值' + //# * 若要用區間最大值 , 則 `Value` 的 `operator+` 要寫成 `std::max(...)` + //#======================================== + //# + //# ''' +} + +#include "BinaryIndexTree.hpp" + +#endif // BinaryIndexTree_H__ + diff --git a/meowpp/dsa/BinaryIndexTree.hpp b/meowpp/dsa/BinaryIndexTree.hpp new file mode 100644 index 0000000..e7e146a --- /dev/null +++ b/meowpp/dsa/BinaryIndexTree.hpp @@ -0,0 +1,44 @@ + +namespace meow{ + template<class Value> + inline + BinaryIndexTree<Value>::BinaryIndexTree(): + _array(0){ + } + template<class Value> + inline + BinaryIndexTree<Value>::BinaryIndexTree(size_t __size, Value const& __value): + _array(__size, __value){ + } + template<class Value> + inline + BinaryIndexTree<Value>::BinaryIndexTree(BinaryIndexTree const& __tree2): + _array(__tree2._array){ + } + // + template<class Value> + inline void + BinaryIndexTree<Value>::reset(size_t __size, Value const& __init){ + _array.clear(); + _array.resize(__size, __init); + } + // + template<class Value> + inline void + BinaryIndexTree<Value>::update(size_t __index, Value const& __value){ + __index++; + for( ; __index <= _array.size(); __index += (__index & -__index)){ + _array[__index - 1] = _array[__index - 1] + __value; + } + } + template<class Value> + inline Value + BinaryIndexTree<Value>::query(ssize_t __index) const{ + __index = std::min(__index + 1, (ssize_t)_array.size()); + Value ret(0); + for( ; 0 < __index; __index -= (__index & -__index)){ + ret = ret + _array[__index - 1]; + } + return ret; + } +} diff --git a/meowpp/dsa/SplayTree.h b/meowpp/dsa/SplayTree.h index 69b204e..38cbe7f 100644 --- a/meowpp/dsa/SplayTree.h +++ b/meowpp/dsa/SplayTree.h @@ -29,31 +29,27 @@ namespace meow{ Value _value; size_t _size; Node* _parent; - Node* _lChild; - Node* _rChild; + Node* _child[2]; // Node(Key const& __key, Value const& __value); + // + void keyOffset(Key const& __delta); + void syncDown() const; + void syncUp () const; }; // 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 connect(Node const* __parent, size_t __left_right, + Node const* __child) const; + Node const* splay (Node const* __node) const; // - void rotate( Node* __parent, Node* __child) const; - void rotate(Node* __grand, Node* __parent, Node* __child) const; - Node* splay(Node* __node) const; + void clear(Node* __node); + Node* dup(Node* __node); // - Node* findKey (Node* __node, Key const& __key) const; - Node* findMinMax(Node* __node, bool minimum ) const; - Node* findOrder (Node* __node, size_t __order ) const; + 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); @@ -114,13 +110,13 @@ namespace meow{ //#|const|lowerBound|(Key const& `k`)|Element|O(logN) //#|找出第一個(最小的) Element且 `k` <= 它的 Key, 並且回傳之. //# 找不到的話回傳 `this->end()` - Element lowerBound(Key const& __key) const; + 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; + Element upperBound(Key const& __key) const; //#|const|lowerBound|(Key const& `k`)|Element|O(logN) @@ -163,22 +159,17 @@ namespace meow{ //#|const|size|()|size_t|O(1)| 回傳資料數 - size_t size() const; + size_t size() const; //#|const|size|()|bool|O(1)| 回傳是否為空 - bool empty() const; + 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` @@ -192,6 +183,11 @@ namespace meow{ 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 @@ -217,8 +213,8 @@ namespace meow{ //# 中的 Element 都搬到 `this` , 同時清空 `tree2` , 回傳 `true`. 否則 //# 回傳 `false` bool merge(SplayTree* __tree2); - // - // + + void print() const; //#|===================================================================== }; diff --git a/meowpp/dsa/SplayTree.hpp b/meowpp/dsa/SplayTree.hpp index 77331ef..de08f63 100644 --- a/meowpp/dsa/SplayTree.hpp +++ b/meowpp/dsa/SplayTree.hpp @@ -1,200 +1,154 @@ namespace meow{ + ///////////////////////////// **# Node #** ///////////////////////// + //////////////////// **# Node -- Constructure #** ////////////////// template<class Key, class Value> - inline SplayTree<Key, Value>::Node::Node(Key const& __key, - Value const& __value): - _key(__key), - _keyOffset(0), - _value(__value), - _size(1), - _parent(NULL), - _lChild(NULL), - _rChild(NULL){ } - // + inline + SplayTree<Key, Value>::Node::Node(Key const& __key, Value const& __value): + _key(__key), _keyOffset(0), _value(__value){ + _size = 1; + _parent = NULL; + _child[0] = NULL; + _child[1] = NULL; + } + //////////////////////// **# Node -- Offset #** //////////////////// template<class Key, class Value> inline void - SplayTree<Key, Value>::offsetAdd(Node* __node, Key const& __delta) const{ - __node->_key = __node->_key + __delta; - __node->_keyOffset = __node->_keyOffset + __delta; + SplayTree<Key, Value>::Node::keyOffset(Key const& __delta){ + _key = _key + __delta; + _keyOffset = _keyOffset + __delta; } + //////////////////////// **# Node -- sync #** ////////////////////// template<class Key, class Value> inline void - SplayTree<Key, Value>::sizeUpdate(Node* __node) const{ - if(__node != NULL){ - __node->_size = 1; - if(__node->_lChild != NULL) __node->_size += __node->_lChild->_size; - if(__node->_rChild != NULL) __node->_size += __node->_rChild->_size; + SplayTree<Key, Value>::Node::syncDown() const{ + for(size_t i = 0; i < 2; i++){ + if(_child[i] == NULL) continue; + _child[i]->keyOffset(_keyOffset); } + ((Node*)this)->_keyOffset = Key(0); } template<class Key, class Value> inline void - SplayTree<Key, Value>::offsetDown(Node* __node) const{ - if(__node->_lChild != NULL) offsetAdd(__node->_lChild, __node->_keyOffset); - if(__node->_rChild != NULL) offsetAdd(__node->_rChild, __node->_keyOffset); - __node->_keyOffset = Key(0); + SplayTree<Key, Value>::Node::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; + } } - // + ////////////////////////// **# SplayTree #** /////////////////////// + ///////////////////// **# connection, splay #** //////////////////// template<class Key, class Value> inline void - SplayTree<Key, Value>::connectLChild(Node* __parent, Node* __child) const{ - if(__parent != NULL) __parent->_lChild = __child; - if(__child != NULL) __child ->_parent = __parent; + SplayTree<Key, Value>::connect(Node const* __parent, size_t __left_right, + Node const* __child) const{ + Node* parent = (Node*)__parent; + Node* child = (Node*)__child; + if(parent != NULL) parent->_child[__left_right] = child; + if(child != NULL) child ->_parent = parent; } template<class Key, class Value> - inline void - SplayTree<Key, Value>::connectRChild(Node* __parent, Node* __child) const{ - if(__parent != NULL) __parent->_rChild = __child; - if(__child != NULL) __child ->_parent = __parent; + inline typename SplayTree<Key, Value>::Node const* + SplayTree<Key, Value>::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); } - // + ///////////////////////// **# clear, dup #** /////////////////////// template<class Key, class Value> - inline typename SplayTree<Key, Value>::Node* + inline void SplayTree<Key, Value>::clear(Node* __node){ - if(__node != NULL){ - clear(__node->_lChild); - clear(__node->_rChild); - delete __node; - } - return NULL; + if(__node == NULL) return ; + clear(__node->_child[0]); + clear(__node->_child[1]); + delete __node; } template<class Key, class Value> inline typename SplayTree<Key, Value>::Node* SplayTree<Key, Value>::dup(Node* __node){ if(__node == NULL) return NULL; - offsetDown(__node); + __node->syncDown(); Node* node = new Node(__node->_key, __node->_value); - connectLChild(node, dup(__node->_lChild)); - connectRChild(node, dup(__node->_rChild)); - sizeUpdate(node); + connect(node, 0, dup(__node->_child[0])); + connect(node, 1, dup(__node->_child[1])); + node->syncUp(); return node; } + /////////////////////////// **# find #** /////////////////////////// template<class Key, class Value> inline typename SplayTree<Key, Value>::Node const* - SplayTree<Key, Value>::setRoot(Node* __node) const{ - connectLChild(NULL, (((SplayTree*)this)->_root = __node)); - return _root; - } - // - template<class Key, class Value> - inline void - SplayTree<Key, Value>::rotate(Node* __parent, Node* __child) const{ - if(__parent->_lChild == __child){ - connectLChild(__parent, __child->_rChild); - connectRChild(__child , __parent); - }else{ - connectRChild(__parent, __child->_lChild); - connectLChild(__child , __parent); - } - sizeUpdate(__parent); - sizeUpdate(__child ); - } - template<class Key, class Value> - inline void - SplayTree<Key, Value>::rotate(Node* __grand, - Node* __parent, - Node* __child) const{ - if(__grand->_lChild == __parent){ - if(__parent->_lChild == __child){ - connectLChild(__grand , __parent->_rChild); - connectLChild(__parent, __child ->_rChild); - connectRChild(__child , __parent); - connectRChild(__parent, __grand ); - }else{ - connectRChild(__parent, __child->_lChild); - connectLChild(__grand , __child->_rChild); - connectLChild(__child, __parent); - connectRChild(__child, __grand ); - } - }else if(__grand->_rChild == __parent){ - if(__parent->_rChild == __child){ - connectRChild(__grand , __parent->_lChild); - connectRChild(__parent, __child ->_lChild); - connectLChild(__child , __parent); - connectLChild(__parent, __grand ); - }else{ - connectRChild(__grand , __child->_lChild); - connectLChild(__parent, __child->_rChild); - connectLChild(__child, __grand ); - connectRChild(__child, __parent); - } - } - sizeUpdate(__grand ); - sizeUpdate(__parent); - sizeUpdate(__child ); - } - template<class Key, class Value> - inline typename SplayTree<Key, Value>::Node* - SplayTree<Key, Value>::splay(Node* __node) const{ - if(__node == NULL) return NULL; - for(Node *parent, *grand, *child = __node; child->_parent != NULL; ){ - parent = child ->_parent; - grand = parent->_parent; - if(grand == NULL){ - rotate(parent, child); - break; - }else{ - Node* g_grand = grand->_parent; - rotate(grand, parent, child); - if(g_grand == NULL) break; - if(g_grand->_lChild == grand) connectLChild(g_grand, child); - else connectRChild(g_grand, child); - } - } - sizeUpdate(__node); - return __node; - } - template<class Key, class Value> - inline typename SplayTree<Key, Value>::Node* - SplayTree<Key, Value>::findKey(Node* __node, Key const& __key) const{ - Node* ret = __node; + SplayTree<Key, Value>::findKey(Node const* __node, Key const& __key) const{ + Node const* ret = __node; while(__node != NULL){ - offsetDown(__node); + __node->syncDown(); ret = __node; if(!(__key < __node->_key)){ if(!(__node->_key< __key)) break; - __node = __node->_rChild; + __node = __node->_child[1]; }else{ - __node = __node->_lChild; + __node = __node->_child[0]; } } return ret; } template<class Key, class Value> - inline typename SplayTree<Key, Value>::Node* - SplayTree<Key, Value>::findMinMax(Node* __node, bool minimum) const{ - Node* ret = __node; - while(__node != NULL){ - offsetDown(__node); + inline typename SplayTree<Key, Value>::Node const* + SplayTree<Key, Value>::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; - __node = (minimum ? __node->_lChild : __node->_rChild); } return ret; } template<class Key, class Value> - inline typename SplayTree<Key, Value>::Node* - SplayTree<Key, Value>::findOrder(Node* __node, size_t __order) const{ - Node* ret = __node; + inline typename SplayTree<Key, Value>::Node const* + SplayTree<Key, Value>::findOrder(Node const* __node, size_t __order) const{ + Node const* ret = __node; while(__node != NULL){ - offsetDown(__node); + __node->syncDown(); ret = __node; - size_t ord = 1 + (__node->_lChild == NULL ? 0 : __node->_lChild->_size); + size_t ord = 1 + (__node->_child[0]==NULL ? 0:__node->_child[0]->_size); if (ord == __order) return ret; - else if(ord < __order){ __node = __node->_rChild; __order -= ord; } - else { __node = __node->_lChild; } + else if(ord < __order){ __node = __node->_child[1]; __order -= ord; } + else { __node = __node->_child[0]; } } return ret; } + /////////////////////// **# split, merge #** /////////////////////// template<class Key, class Value> inline void SplayTree<Key, Value>::split(Node* __root, Node** __left, Node** __right){ if(__root == NULL){ *__left = NULL; *__right = NULL; return ; } - offsetDown(__root); + __root->syncDown(); *__left = __root; - *__right = __root->_rChild; + *__right = __root->_child[1]; if(*__right != NULL){ - (*__left )->_rChild = NULL; - (*__right)->_parent = NULL; - sizeUpdate(*__left); + (*__left )->_child[1] = NULL; + (*__right)->_parent = NULL; + (*__left )->syncUp(); } } template<class Key, class Value> @@ -202,11 +156,12 @@ namespace meow{ SplayTree<Key, Value>::merge(Node* __left, Node* __right){ if(__left == NULL) return __right; if(__right == NULL) return __left ; - offsetDown(__left); - connectRChild(__left, __right); - sizeUpdate(__left); + __left->syncDown(); + connect(__left, 1, __right); + __left->syncUp(); return __left; } + // template<class Key, class Value> inline void SplayTree<Key, Value>::print(Node* __now, int __depth) const{ if(__now == NULL) return ; @@ -215,12 +170,12 @@ namespace meow{ (long long unsigned)__now, __now->_size, (long long unsigned)__now->_parent, - (long long unsigned)__now->_lChild, - (long long unsigned)__now->_rChild); - print(__now->_lChild, __depth + 1); - print(__now->_rChild, __depth + 1); + (long long unsigned)__now->_child[0], + (long long unsigned)__now->_child[1]); + print(__now->_child[0], __depth + 1); + print(__now->_child[1], __depth + 1); } - // + ///////////////////////// **# Element ##* ////////////////////////// template<class Key, class Value> inline void SplayTree<Key, Value>::Element::reset(Node* __node){ _node = __node; @@ -228,25 +183,36 @@ namespace meow{ if(__node == NULL) _entry = NULL; else _entry = new Entry(__node->_key, __node->_value); } + // template<class Key, class Value> - inline SplayTree<Key, Value>::Element::Element(): - _entry(NULL), _node(NULL){ } + inline + SplayTree<Key, Value>::Element::Element(): + _entry(NULL), _node(NULL){ + } template<class Key, class Value> - inline SplayTree<Key, Value>::Element::Element(Node* __node): - _entry(NULL), _node(NULL){ reset(__node); } + inline + SplayTree<Key, Value>::Element::Element(Node* __node): + _entry(NULL), _node(NULL){ + reset(__node); + } template<class Key, class Value> - inline SplayTree<Key, Value>::Element::Element(Element const& __element2): - _entry(NULL), _node(NULL){ reset(__element2._node); } + inline + SplayTree<Key, Value>::Element::Element(Element const& __element2): + _entry(NULL), _node(NULL){ + reset(__element2._node); + } template<class Key, class Value> - inline SplayTree<Key, Value>::Element::~Element(){ delete _entry; } - // + inline + SplayTree<Key, Value>::Element::~Element(){ + delete _entry; + } template<class Key, class Value> inline typename SplayTree<Key, Value>::Element& SplayTree<Key, Value>::Element::operator=(Element const& __e2){ reset(__e2._node); return *this; } - // + //////////////////// **# Element operations #** //////////////////// template<class Key, class Value> inline typename SplayTree<Key, Value>::Element::Entry* SplayTree<Key, Value>::Element::operator->(){ return _entry; } @@ -264,181 +230,186 @@ namespace meow{ SplayTree<Key, Value>::Element::operator!=(Element const& __e2) const{ return (_node != __e2._node); } - // + /////// **# Splay tree constructure/destructure/copy oper #** ////// template<class Key, class Value> - inline SplayTree<Key, Value>::SplayTree(): _root(NULL){ } + inline + SplayTree<Key, Value>::SplayTree(): _root(NULL){ + } template<class Key, class Value> - inline SplayTree<Key, Value>::SplayTree(SplayTree const& __tree2): - _root(NULL){ setRoot(dup(__tree2._root)); } + inline + SplayTree<Key, Value>::SplayTree(SplayTree const& __tree2): _root(NULL){ + _root = dup((Node*)(__tree2._root)); + } template<class Key, class Value> - inline SplayTree<Key, Value>::~SplayTree(){ clear(_root); } + inline + SplayTree<Key, Value>::~SplayTree(){ + clear(_root); + } template<class Key, class Value> inline SplayTree<Key, Value>& SplayTree<Key, Value>::operator=(SplayTree const& __tree2){ clear(_root); - setRoot(dup(__tree2._root)); + _root = dup((Node*)(__tree2._root)); return *this; } - // + template<class Key, class Value> + inline void + SplayTree<Key, Value>::moveTo(SplayTree* __tree2){ + __tree2->clear(); + __tree2->_root = _root; + _root = NULL; + } + //////////////////////// **# Bounding #** ////////////////////////// template<class Key, class Value> inline typename SplayTree<Key, Value>::Element SplayTree<Key, Value>::lowerBound(Key const& __key) const{ - SplayTree* me = (SplayTree*)this; - setRoot(splay(findKey(me->_root, __key))); + splay(findKey(_root, __key)); if(_root == NULL || !(_root->_key < __key)) return Element(_root); - if(_root->_rChild == NULL) return Element(NULL); - setRoot(splay(findMinMax(me->_root->_rChild, true))); + if(_root->_child[1] == NULL) return Element(NULL); + splay(findMinMax(_root->_child[1], true)); return Element(_root); } template<class Key, class Value> inline typename SplayTree<Key, Value>::Element SplayTree<Key, Value>::upperBound(Key const& __key) const{ - SplayTree* me = (SplayTree*)this; - setRoot(splay(findKey(me->_root, __key))); + splay(findKey(_root, __key)); if(_root == NULL || __key < _root->_key) return Element(_root); - if(_root->_rChild == NULL) return Element(NULL); - setRoot(splay(findMinMax(me->_root->_rChild, true))); + if(_root->_child[1] == NULL) return Element(NULL); + splay(findMinMax(_root->_child[1], true)); return Element(_root); } template<class Key, class Value> inline typename SplayTree<Key, Value>::Element SplayTree<Key, Value>::rLowerBound(Key const& __key) const{ - SplayTree* me = (SplayTree*)this; - setRoot(splay(findKey(me->_root, __key))); + splay(findKey(_root, __key)); if(_root == NULL || !(__key < _root->_key)) return Element(_root); - if(_root->_lChild == NULL){ - return NULL; - } - setRoot(splay(findMinMax(me->_root->_lChild, false))); + if(_root->_child[0] == NULL) return Element(NULL); + splay(findMinMax(_root->_child[0], false)); return Element(_root); } template<class Key, class Value> inline typename SplayTree<Key, Value>::Element SplayTree<Key, Value>::rUpperBound(Key const& __key) const{ - SplayTree* me = (SplayTree*)this; - setRoot(splay(findKey(me->_root, __key))); + splay(findKey(_root, __key)); if(_root == NULL || _root->_key < __key) return Element(_root); - if(_root->_lChild == NULL) return Element(NULL); - setRoot(splay(findMinMax(me->_root->_lChild, false))); + if(_root->_child[0] == NULL) return Element(NULL); + splay(findMinMax(_root->_child[0], false)); return Element(_root); } + ////////////// **# find / order / first / last / end #** //////////// template<class Key, class Value> inline typename SplayTree<Key, Value>::Element SplayTree<Key, Value>::find(Key const& __key) const{ - SplayTree* me = (SplayTree*)this; - setRoot(splay(findKey(me->_root, __key))); - if(_root != NULL && _root->_key == __key) return Element(_root); + splay(findKey(_root, __key)); + if(_root != NULL && !(__key < _root->_key) && !(_root->_key < __key)){ + return Element(_root); + } return Element(NULL); } template<class Key, class Value> inline typename SplayTree<Key, Value>::Element SplayTree<Key, Value>::order(size_t __order) const{ - SplayTree* me = (SplayTree*)this; - setRoot(splay(findOrder(me->_root, __order + 1))); + if(_root == NULL || __order >= _root->_size) return Element(NULL); + splay(findOrder(_root, __order + 1)); return Element(_root); } template<class Key, class Value> inline typename SplayTree<Key, Value>::Element SplayTree<Key, Value>::first() const{ - SplayTree* me = (SplayTree*)this; - setRoot(splay(findMinMax(me->_root, true))); + splay(findMinMax(_root, true)); return Element(_root); } template<class Key, class Value> inline typename SplayTree<Key, Value>::Element SplayTree<Key, Value>::last() const{ - SplayTree* me = (SplayTree*)this; - setRoot(splay(findMinMax(me->_root, false))); + splay(findMinMax(_root, false)); return Element(_root); } template<class Key, class Value> inline typename SplayTree<Key, Value>::Element SplayTree<Key, Value>::end() const{ return Element(NULL); } + //////////////////// **# size, empty, clear #** //////////////////// template<class Key, class Value> inline size_t SplayTree<Key, Value>::size() const{ return (_root == NULL ? 0 : _root->_size); } template<class Key, class Value> - inline bool SplayTree<Key, Value>::empty() const{ return (size() == 0); } + inline bool SplayTree<Key, Value>::empty() const{ + return (size() == 0); + } // template<class Key, class Value> inline void SplayTree<Key, Value>::clear(){ clear(_root); _root = NULL; } - template<class Key, class Value> - inline void SplayTree<Key, Value>::keyOffset(Key const& __delta){ - if(_root != NULL){ - offsetAdd(_root, __delta); - } - } + ////////////// **# insert, erase, keyOffset, oper[] #** //////////// template<class Key, class Value> inline bool SplayTree<Key, Value>::insert(Key const& __key, Value const& __value){ if(_root == NULL){ - setRoot(new Node(__key, __value)); - return true; - } - Node* parent = findKey(_root, __key); - Node* new_node; - if(parent->_key < __key){ - connectRChild(parent, new_node = new Node(__key, __value)); - sizeUpdate(parent); - }else if(__key < parent->_key){ - connectLChild(parent, new_node = new Node(__key, __value)); - sizeUpdate(parent); + _root = new Node(__key, __value); }else{ - setRoot(splay(parent)); - return false; + 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); } - setRoot(splay(new_node)); return true; } template<class Key, class Value> inline bool SplayTree<Key, Value>::erase(Key const& __key){ if(_root == NULL) return false; - Node* body = findKey(_root, __key); + Node* body = (Node*)findKey(_root, __key); if(body->_key < __key || __key < body->_key){ - setRoot(splay(body)); + splay(body); return false; } Node* ghost; - if(body->_rChild == NULL){ - ghost = body->_lChild; - if(ghost != NULL) offsetDown(ghost); + if(body->_child[1] == NULL){ + ghost = body->_child[0]; + if(ghost != NULL) ghost->syncDown(); }else{ - ghost = findMinMax(body->_rChild, true); - connectLChild(ghost, body->_lChild); - if(ghost != body->_rChild){ - connectLChild(ghost->_parent, ghost->_rChild); - connectRChild(ghost, body->_rChild); - for(Node* acestor = ghost->_parent; - acestor != ghost; - acestor = acestor->_parent){ - sizeUpdate(acestor); - } + 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(); } - sizeUpdate(ghost); - } - if(body->_parent != NULL && body->_parent->_lChild == body){ - connectLChild(body->_parent, ghost); - }else{ - connectRChild(body->_parent, ghost); + ghost->syncUp(); } - setRoot(splay(ghost != NULL ? ghost : body->_parent)); + Node* parent = body->_parent; + connect(parent, parent != NULL && parent->_child[0] == body ? 0 : 1, + ghost); + delete body; + splay(ghost != NULL ? ghost : parent); return true; } template<class Key, class Value> + inline void SplayTree<Key, Value>::keyOffset(Key const& __delta){ + if(_root != NULL){ + _root->keyOffset(__delta); + } + } + template<class Key, class Value> inline Value& SplayTree<Key, Value>::operator[](Key const& __key){ if(find(__key) == end()) insert(__key, Value()); - return find(__key)->second; + return _root->_value; } + /////////////////////// **# split, merge #** /////////////////////// template<class Key, class Value> inline void SplayTree<Key, Value>::splitOut(Key const& __upper_bound, SplayTree* __right){ __right->clear(); - if(rLowerBound(__upper_bound) != Element(NULL)){ + if(rLowerBound(__upper_bound) != end()){ split(_root, &_root, &(__right->_root)); }else{ __right->_root = _root; @@ -450,7 +421,7 @@ namespace meow{ SplayTree<Key, Value>::mergeAfter(SplayTree* __tree2){ if(_root == NULL || __tree2->_root == NULL || last()->first < __tree2->first()->first){ - setRoot(merge(_root, __tree2->_root)); + _root = merge(_root, __tree2->_root); __tree2->_root = NULL; return true; } @@ -459,16 +430,13 @@ namespace meow{ template<class Key, class Value> inline bool SplayTree<Key, Value>::merge(SplayTree* __tree2){ - if(_root == NULL || __tree2->_root == NULL){ - setRoot(merge(_root, __tree2->_root)); + 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{ - if(last()->first < __tree2->first()->first){ - setRoot(merge(_root, __tree2->_root)); - }else if(__tree2->last()->first < first()->first){ - setRoot(merge(__tree2->_root, _root)); - }else{ - return false; - } + return false; } __tree2->_root = NULL; return true; @@ -478,12 +446,5 @@ namespace meow{ SplayTree<Key, Value>::print() const{ print(_root, 0); } - template<class Key, class Value> - inline void - SplayTree<Key, Value>::moveTo(SplayTree* __tree2){ - __tree2->clear(); - __tree2->_root = _root; - _root = NULL; - } } |