diff options
Diffstat (limited to 'meowpp/dsa/SplayTree.hpp')
| -rw-r--r-- | meowpp/dsa/SplayTree.hpp | 505 |
1 files changed, 505 insertions, 0 deletions
diff --git a/meowpp/dsa/SplayTree.hpp b/meowpp/dsa/SplayTree.hpp new file mode 100644 index 0000000..835664f --- /dev/null +++ b/meowpp/dsa/SplayTree.hpp @@ -0,0 +1,505 @@ + +namespace meow{ + 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){ } + // + 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; + } + 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; + } + 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 = 0; + } + // + 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; + } + 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; + } + // + template<class Key, class Value> + inline typename SplayTree<Key, Value>::Node* + SplayTree<Key, Value>::clear(Node* __node){ + if(__node != NULL){ + clear(__node->_lChild); + clear(__node->_rChild); + delete __node; + } + 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); + connectLChild(node, dup(__node->_lChild)); + connectRChild(node, dup(__node->_rChild)); + return node; + } + // + 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); + } + } + 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; + for(Key offset_sum = 0; __node != NULL; offset_sum += ret->_keyOffset){ + offsetDown(__node); + ret = __node; + if(!(__key < offset_sum + __node->_key)){ + if(!(offset_sum + __node->_key< __key)){ + break; + } + __node = __node->_rChild; + }else{ + __node = __node->_lChild; + } + } + 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); + 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; + 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; + } + } + 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 ; + } + offsetDown(__root); + *__left = __root; + *__right = __root->_rChild; + if(*__right != NULL){ + (*__left )->_rChild = NULL; + (*__right)->_parent = NULL; + sizeUpdate(*__left); + } + } + template<class Key, class Value> + 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); + connectRChild(__left, __right); + sizeUpdate(__left); + return __left; + } + 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", + __depth * 2, "", + (long long unsigned)__now, + (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); + } + // + template<class Key, class Value> + 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); + } + } + template<class Key, class Value> + 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); } + template<class Key, class Value> + 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; } + // + template<class Key, class Value> + inline typename SplayTree<Key, Value>::Element& + SplayTree<Key, Value>::Element::operator=(Element const& __e2){ + reset(__e2._node); + return *this; + } + // + template<class Key, class Value> + 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; } + // + template<class Key, class Value> + inline bool + SplayTree<Key, Value>::Element::operator==(Element const& __e2) const{ + return (_node == __e2._node); + } + template<class Key, class Value> + inline bool + SplayTree<Key, Value>::Element::operator!=(Element const& __e2) const{ + return (_node != __e2._node); + } + // + template<class Key, class Value> + 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); + } + template<class Key, class Value> + 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); + _root = dup(__tree2._root); + return *this; + } + // + template<class Key, class Value> + 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; + 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; + 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; + 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; + me->_root = splay(findKey(me->_root, __key)); + me->_root->_parent = NULL; + 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; + 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; + 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; + return Element(_root); + } + template<class Key, class Value> + 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); + } + 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; + me->_root = splay(findOrder(me->_root, __order + 1)); + me->_root->_parent = NULL; + return Element(_root); + } + template<class Key, class Value> + 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; + return Element(_root); + } + template<class Key, class Value> + 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; + return Element(_root); + } + template<class Key, class Value> + 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); + } + template<class Key, class Value> + 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); + } + } + template<class Key, class Value> + inline bool SplayTree<Key, Value>::insert(Key const& __key, + Value const& __value){ + if(_root == NULL){ + _root = 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)); + }else if(__key < parent->_key){ + connectLChild(parent, new_node = new Node(__key, __value)); + }else{ + _root = splay(parent); + _root->_parent = NULL; + return false; + } + _root = splay(new_node); + _root->_parent = NULL; + 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); + if(body->_key < __key || __key < body->_key){ + return false; + } + Node* ghost; + if(body->_rChild == NULL){ + ghost = body->_lChild; + }else{ + ghost = findMinMax(body->_rChild, true); + connectLChild(ghost, body->_lChild); + if(ghost != body->_rChild){ + connectLChild(ghost->_parent, ghost->_lChild); + connectLChild(ghost, body->_rChild); + } + } + 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; + return true; + } + 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; + } + template<class Key, class Value> + inline void SplayTree<Key, Value>::splitOut(Key const& __upper_bound, + SplayTree* __right){ + __right->clear(); + rLowerBound(__upper_bound); + split(_root, &_root, &(__right->_root)); + } + template<class Key, class Value> + inline bool SplayTree<Key, Value>::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; + } + template<class Key, class Value> + inline bool SplayTree<Key, Value>::merge(SplayTree* __tree2){ + if(_root == NULL || __tree2->_root == NULL){ + _root = merge(_root, __tree2->_root); + }else{ + if(last()->first < __tree2->first()->first){ + _root = merge(_root, __tree2->_root); + __tree2->_root = NULL; + }else if(__tree2->last()->first < first()->first){ + _root = merge(__tree2->_root, _root); + }else{ + return false; + } + } + __tree2->_root = NULL; + return true; + } + template<class Key, class Value> + inline void 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; + } +} + |