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;
}
}
