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.hpp312
1 files changed, 148 insertions, 164 deletions
diff --git a/meowpp/dsa/SplayTree.hpp b/meowpp/dsa/SplayTree.hpp
index 835664f..47615db 100644
--- a/meowpp/dsa/SplayTree.hpp
+++ b/meowpp/dsa/SplayTree.hpp
@@ -12,16 +12,19 @@ namespace meow{
_rChild(NULL){ }
//
template<class Key, class Value>
- inline void SplayTree<Key, Value>::offsetAdd(Node* __node,
- Key const& __delta) const{
+ inline void
+ SplayTree<Key, Value>::offsetAdd(Node* __node, Key const& __delta) const{
__node->_key = __node->_key + __delta;
__node->_keyOffset = __node->_keyOffset + __delta;
}
template<class Key, class Value>
- inline void SplayTree<Key, Value>::sizeUpdate(Node* __node) const{
- __node->_size = 1;
- if(__node->_lChild != NULL) __node->_size += __node->_lChild->_size;
- if(__node->_rChild != NULL) __node->_size += __node->_rChild->_size;
+ 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;
+ }
}
template<class Key, class Value>
inline void
@@ -32,14 +35,14 @@ namespace meow{
}
//
template<class Key, class Value>
- inline void SplayTree<Key, Value>::connectLChild(Node* __parent,
- Node* __child) const{
+ inline void
+ SplayTree<Key, Value>::connectLChild(Node* __parent, Node* __child) const{
if(__parent != NULL) __parent->_lChild = __child;
if(__child != NULL) __child ->_parent = __parent;
}
template<class Key, class Value>
- inline void SplayTree<Key, Value>::connectRChild(Node* __parent,
- Node* __child) const{
+ inline void
+ SplayTree<Key, Value>::connectRChild(Node* __parent, Node* __child) const{
if(__parent != NULL) __parent->_rChild = __child;
if(__child != NULL) __child ->_parent = __parent;
}
@@ -55,19 +58,26 @@ namespace meow{
return NULL;
}
template<class Key, class Value>
- inline typename SplayTree<Key, Value>::Node* SplayTree<Key, Value>::dup(Node* __node){
- if(__node == NULL){
- return NULL;
- }
- Node* node = Node(__node->_key, __node->_value);
+ inline typename SplayTree<Key, Value>::Node*
+ SplayTree<Key, Value>::dup(Node* __node){
+ if(__node == NULL) return NULL;
+ offsetDown(__node);
+ Node* node = new Node(__node->_key, __node->_value);
connectLChild(node, dup(__node->_lChild));
connectRChild(node, dup(__node->_rChild));
+ sizeUpdate(node);
return node;
}
+ 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{
+ inline void
+ SplayTree<Key, Value>::rotate(Node* __parent, Node* __child) const{
if(__parent->_lChild == __child){
connectLChild(__parent, __child->_rChild);
connectRChild(__child , __parent);
@@ -79,9 +89,10 @@ namespace meow{
sizeUpdate(__child );
}
template<class Key, class Value>
- inline void SplayTree<Key, Value>::rotate(Node* __grand,
- Node* __parent,
- Node* __child) const{
+ 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);
@@ -112,10 +123,9 @@ namespace meow{
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;
- }
+ 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;
@@ -125,26 +135,23 @@ namespace meow{
}else{
Node* g_grand = grand->_parent;
rotate(grand, parent, child);
- if(g_grand == NULL){
- break;
- }
+ 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{
+ inline typename SplayTree<Key, Value>::Node*
+ SplayTree<Key, Value>::findKey(Node* __node, Key const& __key) const{
Node* ret = __node;
- for(Key offset_sum = 0; __node != NULL; offset_sum += ret->_keyOffset){
+ while(__node != NULL){
offsetDown(__node);
ret = __node;
- if(!(__key < offset_sum + __node->_key)){
- if(!(offset_sum + __node->_key< __key)){
- break;
- }
+ if(!(__key < __node->_key)){
+ if(!(__node->_key< __key)) break;
__node = __node->_rChild;
}else{
__node = __node->_lChild;
@@ -153,8 +160,8 @@ namespace meow{
return ret;
}
template<class Key, class Value>
- inline typename SplayTree<Key, Value>::Node* SplayTree<Key, Value>::findMinMax(Node* __node,
- bool minimum) const{
+ inline typename SplayTree<Key, Value>::Node*
+ SplayTree<Key, Value>::findMinMax(Node* __node, bool minimum) const{
Node* ret = __node;
while(__node != NULL){
offsetDown(__node);
@@ -164,32 +171,23 @@ namespace meow{
return ret;
}
template<class Key, class Value>
- inline typename SplayTree<Key, Value>::Node* SplayTree<Key, Value>::findOrder(Node* __node,
- size_t __order) const{
+ inline typename SplayTree<Key, Value>::Node*
+ SplayTree<Key, Value>::findOrder(Node* __node, size_t __order) const{
Node* ret = __node;
while(__node != NULL){
offsetDown(__node);
ret = __node;
size_t ord = 1 + (__node->_lChild == NULL ? 0 : __node->_lChild->_size);
- if(ord == __order){
- return ret;
- }else if(ord < __order){
- __node = __node->_rChild;
- __order -= ord;
- }else{
- __node = __node->_lChild;
- }
+ if (ord == __order) return ret;
+ else if(ord < __order){ __node = __node->_rChild; __order -= ord; }
+ else { __node = __node->_lChild; }
}
return ret;
}
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 ;
- }
+ inline void
+ SplayTree<Key, Value>::split(Node* __root, Node** __left, Node** __right){
+ if(__root == NULL){ *__left = NULL; *__right = NULL; return ; }
offsetDown(__root);
*__left = __root;
*__right = __root->_rChild;
@@ -200,7 +198,8 @@ namespace meow{
}
}
template<class Key, class Value>
- inline typename SplayTree<Key, Value>::Node* SplayTree<Key, Value>::merge(Node* __left, Node* __right){
+ inline typename SplayTree<Key, Value>::Node*
+ SplayTree<Key, Value>::merge(Node* __left, Node* __right){
if(__left == NULL) return __right;
if(__right == NULL) return __left ;
offsetDown(__left);
@@ -211,9 +210,10 @@ namespace meow{
template<class Key, class Value>
inline void SplayTree<Key, Value>::print(Node* __now, int __depth) const{
if(__now == NULL) return ;
- printf("%*s [%llX]:\tParent=%llX Left=%llX Right=%llX\n",
+ printf("%*s [%llX]:(%lu)\tParent=%llX Left=%llX Right=%llX\n",
__depth * 2, "",
(long long unsigned)__now,
+ __now->_size,
(long long unsigned)__now->_parent,
(long long unsigned)__now->_lChild,
(long long unsigned)__now->_rChild);
@@ -225,24 +225,18 @@ namespace meow{
inline void SplayTree<Key, Value>::Element::reset(Node* __node){
_node = __node;
delete _entry;
- if(__node == NULL){
- _entry = NULL;
- }else{
- _entry = new Entry(__node->_key, __node->_value);
- }
+ 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){ }
+ _entry(NULL), _node(NULL){ }
template<class Key, class Value>
inline SplayTree<Key, Value>::Element::Element(Node* __node):
- _entry(NULL),
- _node(NULL){ reset(__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); }
+ _entry(NULL), _node(NULL){ reset(__element2._node); }
template<class Key, class Value>
inline SplayTree<Key, Value>::Element::~Element(){ delete _entry; }
//
@@ -254,9 +248,11 @@ namespace meow{
}
//
template<class Key, class Value>
- inline typename SplayTree<Key, Value>::Element::Entry* SplayTree<Key, Value>::Element::operator->(){ return _entry; }
+ inline typename SplayTree<Key, Value>::Element::Entry*
+ SplayTree<Key, Value>::Element::operator->(){ return _entry; }
template<class Key, class Value>
- inline typename SplayTree<Key, Value>::Element::Entry& SplayTree<Key, Value>::Element::operator*(){ return *_entry; }
+ inline typename SplayTree<Key, Value>::Element::Entry&
+ SplayTree<Key, Value>::Element::operator*(){ return *_entry; }
//
template<class Key, class Value>
inline bool
@@ -270,117 +266,94 @@ namespace meow{
}
//
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){
- _root = dup(__tree2._root);
- }
+ _root(NULL){ setRoot(dup(__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){
+ inline SplayTree<Key, Value>&
+ SplayTree<Key, Value>::operator=(SplayTree const& __tree2){
clear(_root);
- _root = dup(__tree2._root);
+ setRoot(dup(__tree2._root));
return *this;
}
//
template<class Key, class Value>
- inline typename SplayTree<Key, Value>::Element SplayTree<Key, Value>::lowerBound(Key const& __key) const{
+ inline typename SplayTree<Key, Value>::Element
+ SplayTree<Key, Value>::lowerBound(Key const& __key) const{
SplayTree* me = (SplayTree*)this;
- me->_root = splay(findKey(me->_root, __key));
- me->_root->_parent = NULL;
- if(_root == NULL || !(_root->_key < __key)){
- return Element(_root);
- }
- if(_root->_rChild == NULL){
- return NULL;
- }
- me->_root = splay(findMinMax(me->_root->_rChild, true));
- me->_root->_parent = NULL;
+ setRoot(splay(findKey(me->_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)));
return Element(_root);
}
template<class Key, class Value>
- inline typename SplayTree<Key, Value>::Element SplayTree<Key, Value>::upperBound(Key const& __key) const{
+ inline typename SplayTree<Key, Value>::Element
+ SplayTree<Key, Value>::upperBound(Key const& __key) const{
SplayTree* me = (SplayTree*)this;
- me->_root = splay(findKey(me->_root, __key));
- me->_root->_parent = NULL;
- if(_root == NULL || __key < _root->_key){
- return Element(_root);
- }
- if(_root->_rChild == NULL){
- return NULL;
- }
- me->_root = splay(findMinMax(me->_root->_rChild, true));
- me->_root->_parent = NULL;
+ setRoot(splay(findKey(me->_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)));
return Element(_root);
}
template<class Key, class Value>
- inline typename SplayTree<Key, Value>::Element SplayTree<Key, Value>::rLowerBound(Key const& __key) const{
+ inline typename SplayTree<Key, Value>::Element
+ SplayTree<Key, Value>::rLowerBound(Key const& __key) const{
SplayTree* me = (SplayTree*)this;
- me->_root = splay(findKey(me->_root, __key));
- me->_root->_parent = NULL;
- if(_root == NULL || !(__key < _root->_key)){
- return Element(_root);
- }
+ setRoot(splay(findKey(me->_root, __key)));
+ if(_root == NULL || !(__key < _root->_key)) return Element(_root);
if(_root->_lChild == NULL){
return NULL;
}
- me->_root = splay(findMinMax(me->_root->_lChild, false));
- me->_root->_parent = NULL;
+ setRoot(splay(findMinMax(me->_root->_lChild, false)));
return Element(_root);
}
template<class Key, class Value>
- inline typename SplayTree<Key, Value>::Element SplayTree<Key, Value>::rUpperBound(Key const& __key) const{
+ inline typename SplayTree<Key, Value>::Element
+ SplayTree<Key, Value>::rUpperBound(Key const& __key) const{
SplayTree* me = (SplayTree*)this;
- me->_root = splay(findKey(me->_root, __key));
- me->_root->_parent = NULL;
- if(_root == NULL || _root->_key < __key){
- return Element(_root);
- }
- if(_root->_lChild == NULL){
- return NULL;
- }
- me->_root = splay(findMinMax(me->_root->_lChild, false));
- me->_root->_parent = NULL;
+ setRoot(splay(findKey(me->_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)));
return Element(_root);
}
template<class Key, class Value>
- inline typename SplayTree<Key, Value>::Element SplayTree<Key, Value>::find(Key const& __key) const{
+ inline typename SplayTree<Key, Value>::Element
+ SplayTree<Key, Value>::find(Key const& __key) const{
SplayTree* me = (SplayTree*)this;
- me->_root = splay(findKey(me->_root, __key));
- me->_root->_parent = NULL;
- if(_root != NULL && _root->_key == __key){
- return Element(_root);
- }
+ setRoot(splay(findKey(me->_root, __key)));
+ if(_root != NULL && _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{
+ inline typename SplayTree<Key, Value>::Element
+ SplayTree<Key, Value>::order(size_t __order) const{
SplayTree* me = (SplayTree*)this;
- me->_root = splay(findOrder(me->_root, __order + 1));
- me->_root->_parent = NULL;
+ setRoot(splay(findOrder(me->_root, __order + 1)));
return Element(_root);
}
template<class Key, class Value>
- inline typename SplayTree<Key, Value>::Element SplayTree<Key, Value>::first() const{
+ inline typename SplayTree<Key, Value>::Element
+ SplayTree<Key, Value>::first() const{
SplayTree* me = (SplayTree*)this;
- me->_root = splay(findMinMax(me->_root, true));
- me->_root->_parent = NULL;
+ setRoot(splay(findMinMax(me->_root, true)));
return Element(_root);
}
template<class Key, class Value>
- inline typename SplayTree<Key, Value>::Element SplayTree<Key, Value>::last() const{
+ inline typename SplayTree<Key, Value>::Element
+ SplayTree<Key, Value>::last() const{
SplayTree* me = (SplayTree*)this;
- me->_root = splay(findMinMax(me->_root, false));
- me->_root->_parent = NULL;
+ setRoot(splay(findMinMax(me->_root, false)));
return Element(_root);
}
template<class Key, class Value>
- inline typename SplayTree<Key, Value>::Element SplayTree<Key, Value>::end() const{ return Element(NULL); }
+ inline typename SplayTree<Key, Value>::Element
+ SplayTree<Key, Value>::end() const{ return Element(NULL); }
template<class Key, class Value>
inline size_t SplayTree<Key, Value>::size() const{
return (_root == NULL ? 0 : _root->_size);
@@ -403,87 +376,96 @@ namespace meow{
inline bool SplayTree<Key, Value>::insert(Key const& __key,
Value const& __value){
if(_root == NULL){
- _root = new Node(__key, __value);
+ 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);
}else{
- _root = splay(parent);
- _root->_parent = NULL;
+ setRoot(splay(parent));
return false;
}
- _root = splay(new_node);
- _root->_parent = NULL;
+ 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;
- }
+ if(_root == NULL) return false;
Node* body = findKey(_root, __key);
if(body->_key < __key || __key < body->_key){
+ setRoot(splay(body));
return false;
}
Node* ghost;
if(body->_rChild == NULL){
ghost = body->_lChild;
+ if(ghost != NULL) offsetDown(ghost);
}else{
ghost = findMinMax(body->_rChild, true);
connectLChild(ghost, body->_lChild);
if(ghost != body->_rChild){
- connectLChild(ghost->_parent, ghost->_lChild);
- connectLChild(ghost, body->_rChild);
+ connectLChild(ghost->_parent, ghost->_rChild);
+ connectRChild(ghost, body->_rChild);
+ for(Node* acestor = ghost->_parent;
+ acestor != ghost;
+ acestor = acestor->_parent){
+ sizeUpdate(acestor);
+ }
}
+ sizeUpdate(ghost);
}
if(body->_parent != NULL && body->_parent->_lChild == body){
connectLChild(body->_parent, ghost);
}else{
connectRChild(body->_parent, ghost);
}
- _root = splay(ghost != NULL ? ghost : body->_parent);
- _root->_parent = NULL;
+ setRoot(splay(ghost != NULL ? ghost : body->_parent));
return true;
}
template<class Key, class Value>
- inline Value& SplayTree<Key, Value>::operator[](Key const& __key){
- if(find(__key) == end()){
- insert(__key, Value());
- }
+ inline Value&
+ SplayTree<Key, Value>::operator[](Key const& __key){
+ if(find(__key) == end()) insert(__key, Value());
return find(__key)->second;
}
template<class Key, class Value>
- inline void SplayTree<Key, Value>::splitOut(Key const& __upper_bound,
- SplayTree* __right){
+ inline void
+ SplayTree<Key, Value>::splitOut(Key const& __upper_bound, SplayTree* __right){
__right->clear();
- rLowerBound(__upper_bound);
- split(_root, &_root, &(__right->_root));
+ if(rLowerBound(__upper_bound) != Element(NULL)){
+ split(_root, &_root, &(__right->_root));
+ }else{
+ __right->_root = _root;
+ _root = NULL;
+ }
}
template<class Key, class Value>
- inline bool SplayTree<Key, Value>::mergeAfter(SplayTree* __tree2){
+ inline bool
+ SplayTree<Key, Value>::mergeAfter(SplayTree* __tree2){
if(_root == NULL || __tree2->_root == NULL ||
last()->first < __tree2->first()->first){
- _root = merge(_root, __tree2->_root);
+ setRoot(merge(_root, __tree2->_root));
__tree2->_root = NULL;
return true;
}
return false;
}
template<class Key, class Value>
- inline bool SplayTree<Key, Value>::merge(SplayTree* __tree2){
+ inline bool
+ SplayTree<Key, Value>::merge(SplayTree* __tree2){
if(_root == NULL || __tree2->_root == NULL){
- _root = merge(_root, __tree2->_root);
+ setRoot(merge(_root, __tree2->_root));
}else{
if(last()->first < __tree2->first()->first){
- _root = merge(_root, __tree2->_root);
- __tree2->_root = NULL;
+ setRoot(merge(_root, __tree2->_root));
}else if(__tree2->last()->first < first()->first){
- _root = merge(__tree2->_root, _root);
+ setRoot(merge(__tree2->_root, _root));
}else{
return false;
}
@@ -492,11 +474,13 @@ namespace meow{
return true;
}
template<class Key, class Value>
- inline void SplayTree<Key, Value>::print() const{
+ inline void
+ SplayTree<Key, Value>::print() const{
print(_root, 0);
}
template<class Key, class Value>
- inline void SplayTree<Key, Value>::moveTo(SplayTree* __tree2){
+ 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-06-25 14:43:09 +0800