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;
_child[0] = NULL;
_child[1] = NULL;
}
//////////////////////// **# Node -- Offset #** ////////////////////
template<class Key, class Value>
inline void
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>::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>::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>::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 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 void
SplayTree<Key, Value>::clear(Node* __node){
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;
__node->syncDown();
Node* node = new Node(__node->_key, __node->_value);
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>::findKey(Node const* __node, Key const& __key) const{
Node const* ret = __node;
while(__node != NULL){
__node->syncDown();
ret = __node;
if(!(__key < __node->_key)){
if(!(__node->_key< __key)) break;
__node = __node->_child[1];
}else{
__node = __node->_child[0];
}
}
return ret;
}
template<class Key, class Value>
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;
}
return ret;
}
template<class Key, class Value>
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){
__node->syncDown();
ret = __node;
size_t ord = 1 + (__node->_child[0]==NULL ? 0:__node->_child[0]->_size);
if (ord == __order) return ret;
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 ; }
__root->syncDown();
*__left = __root;
*__right = __root->_child[1];
if(*__right != NULL){
(*__left )->_child[1] = NULL;
(*__right)->_parent = NULL;
(*__left )->syncUp();
}
}
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 ;
__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 ;
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->_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;
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;
}
//////////////////// **# Element operations #** ////////////////////
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);
}
/////// **# Splay tree constructure/destructure/copy oper #** //////
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((Node*)(__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((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{
splay(findKey(_root, __key));
if(_root == NULL || !(_root->_key < __key)) return Element(_root);
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{
splay(findKey(_root, __key));
if(_root == NULL || __key < _root->_key) return Element(_root);
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{
splay(findKey(_root, __key));
if(_root == NULL || !(__key < _root->_key)) return Element(_root);
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{
splay(findKey(_root, __key));
if(_root == NULL || _root->_key < __key) return Element(_root);
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{
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{
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{
splay(findMinMax(_root, true));
return Element(_root);
}
template<class Key, class Value>
inline typename SplayTree<Key, Value>::Element
SplayTree<Key, Value>::last() const{
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);
}
//
template<class Key, class Value>
inline void SplayTree<Key, Value>::clear(){
clear(_root);
_root = NULL;
}
////////////// **# insert, erase, keyOffset, oper[] #** ////////////
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);
}else{
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);
}
return true;
}
template<class Key, class Value>
inline bool SplayTree<Key, Value>::erase(Key const& __key){
if(_root == NULL) return false;
Node* body = (Node*)findKey(_root, __key);
if(body->_key < __key || __key < body->_key){
splay(body);
return false;
}
Node* ghost;
if(body->_child[1] == NULL){
ghost = body->_child[0];
if(ghost != NULL) ghost->syncDown();
}else{
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();
}
ghost->syncUp();
}
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 _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) != end()){
split(_root, &_root, &(__right->_root));
}else{
__right->_root = _root;
_root = NULL;
}
}
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 ||
last()->first < __tree2->first()->first){
_root = merge(_root, __tree2->_root);
}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);
}
}
