aboutsummaryrefslogtreecommitdiffstats
path: root/meowpp/dsa/SplayTree.hpp
diff options
context:
space:
mode:
Diffstat (limited to 'meowpp/dsa/SplayTree.hpp')
-rw-r--r--meowpp/dsa/SplayTree.hpp467
1 files changed, 214 insertions, 253 deletions
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;
- }
}
generated by cgit v1.2.3 (git 2.25.1) at 2024-09-27 18:44:12 +0800