aboutsummaryrefslogtreecommitdiffstats
path: root/meowpp/dsa/SplayTree_Range.hpp
diff options
context:
space:
mode:
Diffstat (limited to 'meowpp/dsa/SplayTree_Range.hpp')
-rw-r--r--meowpp/dsa/SplayTree_Range.hpp506
1 files changed, 0 insertions, 506 deletions
diff --git a/meowpp/dsa/SplayTree_Range.hpp b/meowpp/dsa/SplayTree_Range.hpp
deleted file mode 100644
index def7ef7..0000000
--- a/meowpp/dsa/SplayTree_Range.hpp
+++ /dev/null
@@ -1,506 +0,0 @@
-#include "SplayTree_Range.h"
-
-
-#include <cstdlib>
-
-#include <utility>
-
-#include "../math/utility.h"
-
-namespace meow{
- ///////////////////////////// **# Node #** /////////////////////////
- //////////////////// **# Node -- Constructure #** //////////////////
- template<class Key, class Value>
- inline
- SplayTree_Range<Key, Value>::Node::Node(Key const& __key,
- Value const& __value):
- _key(__key), _keyOffset(0), _value(__value), _valueOffset(0), _range(__value){
- _same = false;
- _size = 1;
- _parent = NULL;
- _child[0] = NULL;
- _child[1] = NULL;
- }
- ///////////////// **# Node -- Offset / Override #** ////////////////
- template<class Key, class Value>
- inline void
- SplayTree_Range<Key, Value>::Node::keyOffset(Key const& __delta){
- _key = _key + __delta;
- _keyOffset = _keyOffset + __delta;
- }
- template<class Key, class Value>
- inline void
- SplayTree_Range<Key, Value>::Node::valueUpdate(Value const& __delta,
- bool __over){
- if(__over){
- _value = __delta * _size;
- _valueOffset = __delta;
- _range = __delta * _size;
- _same = true;
- }else{
- _value = _value + __delta * _size;
- _valueOffset = _valueOffset + __delta;
- _range = _range + __delta * _size;
- }
- }
- //////////////////////// **# Node -- sync #** //////////////////////
- template<class Key, class Value>
- inline void
- SplayTree_Range<Key, Value>::Node::syncDown() const{
- for(size_t i = 0; i < 2; i++){
- if(_child[i] == NULL) continue;
- _child[i]->keyOffset (_keyOffset);
- _child[i]->valueUpdate(_valueOffset, _same);
- }
- ((Node*)this)->_keyOffset = Key(0);
- ((Node*)this)->_valueOffset = Value(0);
- ((Node*)this)->_same = false;
- }
- template<class Key, class Value>
- inline void
- SplayTree_Range<Key, Value>::Node::syncUp() const{
- ((Node*)this)->_size = 1;
- Value* v[3] = {&(((Node*)this)->_value), NULL, NULL};
- size_t vct = 1;
- for(size_t i = 0; i < 2; i++){
- if(_child[i] == NULL) continue;
- ((Node*)this)->_size += _child[i]->_size;
- v[vct++] = &(_child[i]->_range);
- }
- if (vct == 1) ((Node*)this)->_range = (*v[0]);
- else if(vct == 2) ((Node*)this)->_range = (*v[0]) | (*v[1]);
- else ((Node*)this)->_range = (*v[0]) | (*v[1]) | (*v[2]);
- }
- ////////////////////////// **# SplayTree_Range #** ///////////////////////
- ///////////////////// **# connection, splay #** ////////////////////
- template<class Key, class Value>
- inline void
- SplayTree_Range<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_Range<Key, Value>::Node const*
- SplayTree_Range<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_Range*)this)->_root = (Node*)__node);
- }
- ///////////////////////// **# clear, dup #** ///////////////////////
- template<class Key, class Value>
- inline void
- SplayTree_Range<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_Range<Key, Value>::Node*
- SplayTree_Range<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_Range<Key, Value>::Node const*
- SplayTree_Range<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_Range<Key, Value>::Node const*
- SplayTree_Range<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_Range<Key, Value>::Node const*
- SplayTree_Range<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_Range<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_Range<Key, Value>::Node*
- SplayTree_Range<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;
- }
- ///////////////////////// **# Element ##* //////////////////////////
- template<class Key, class Value>
- inline void SplayTree_Range<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_Range<Key, Value>::Element::Element():
- _entry(NULL), _node(NULL){
- }
- template<class Key, class Value>
- inline
- SplayTree_Range<Key, Value>::Element::Element(Node* __node):
- _entry(NULL), _node(NULL){
- reset(__node);
- }
- template<class Key, class Value>
- inline
- SplayTree_Range<Key, Value>::Element::Element(Element const& __element2):
- _entry(NULL), _node(NULL){
- reset(__element2._node);
- }
- template<class Key, class Value>
- inline
- SplayTree_Range<Key, Value>::Element::~Element(){
- delete _entry;
- }
- template<class Key, class Value>
- inline typename SplayTree_Range<Key, Value>::Element&
- SplayTree_Range<Key, Value>::Element::operator=(Element const& __e2){
- reset(__e2._node);
- return *this;
- }
- //////////////////// **# Element operations #** ////////////////////
- template<class Key, class Value>
- inline typename SplayTree_Range<Key, Value>::Element::Entry*
- SplayTree_Range<Key, Value>::Element::operator->(){ return _entry; }
- template<class Key, class Value>
- inline typename SplayTree_Range<Key, Value>::Element::Entry&
- SplayTree_Range<Key, Value>::Element::operator*(){ return *_entry; }
- //
- template<class Key, class Value>
- inline bool
- SplayTree_Range<Key, Value>::Element::operator==(Element const& __e2) const{
- return (_node == __e2._node);
- }
- template<class Key, class Value>
- inline bool
- SplayTree_Range<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_Range<Key, Value>::SplayTree_Range(): _root(NULL){
- }
- template<class Key, class Value>
- inline
- SplayTree_Range<Key, Value>::SplayTree_Range(SplayTree_Range const& __tree2):
- _root(NULL){
- _root = dup((Node*)(__tree2._root));
- }
- template<class Key, class Value>
- inline
- SplayTree_Range<Key, Value>::~SplayTree_Range(){
- clear(_root);
- }
- template<class Key, class Value>
- inline SplayTree_Range<Key, Value>&
- SplayTree_Range<Key, Value>::operator=(SplayTree_Range const& __tree2){
- clear(_root);
- _root = dup((Node*)(__tree2._root));
- return *this;
- }
- template<class Key, class Value>
- inline void
- SplayTree_Range<Key, Value>::moveTo(SplayTree_Range* __tree2){
- __tree2->clear();
- __tree2->_root = _root;
- _root = NULL;
- }
- //////////////////////// **# Bounding #** //////////////////////////
- template<class Key, class Value>
- inline typename SplayTree_Range<Key, Value>::Element
- SplayTree_Range<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_Range<Key, Value>::Element
- SplayTree_Range<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_Range<Key, Value>::Element
- SplayTree_Range<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_Range<Key, Value>::Element
- SplayTree_Range<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_Range<Key, Value>::Element
- SplayTree_Range<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_Range<Key, Value>::Element
- SplayTree_Range<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_Range<Key, Value>::Element
- SplayTree_Range<Key, Value>::first() const{
- splay(findMinMax(_root, true));
- return Element(_root);
- }
- template<class Key, class Value>
- inline typename SplayTree_Range<Key, Value>::Element
- SplayTree_Range<Key, Value>::last() const{
- splay(findMinMax(_root, false));
- return Element(_root);
- }
- template<class Key, class Value>
- inline typename SplayTree_Range<Key, Value>::Element
- SplayTree_Range<Key, Value>::end() const{ return Element(NULL); }
- //////////////////// **# query, range query #** ////////////////////
- template<class Key, class Value>
- inline Value
- SplayTree_Range<Key, Value>::query() const{
- if(_root == NULL) return Value(0);
- return _root->_range;
- }
- template<class Key, class Value>
- inline Value
- SplayTree_Range<Key, Value>::query(Key const& __first,
- Key const& __last) const{
- SplayTree_Range* self = (SplayTree_Range*)this;
- Node* tmp;
- rUpperBound(__first);
- self->split(self->_root, &tmp, &(self->_root));
- upperBound(__last);
- Value ret(0);
- if(_root != NULL && _root->_child[0] != NULL){
- ret = _root->_child[0]->_range;
- }
- self->_root = self->merge(tmp, self->_root);
- return ret;
- }
- //////////////////// **# size, empty, clear #** ////////////////////
- template<class Key, class Value>
- inline size_t SplayTree_Range<Key, Value>::size() const{
- return (_root == NULL ? 0 : _root->_size);
- }
- template<class Key, class Value>
- inline bool SplayTree_Range<Key, Value>::empty() const{
- return (size() == 0);
- }
- //
- template<class Key, class Value>
- inline void SplayTree_Range<Key, Value>::clear(){
- clear(_root);
- _root = NULL;
- }
- ////////////// **# insert, erase, keyOffset, oper[] #** ////////////
- template<class Key, class Value>
- inline bool SplayTree_Range<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_Range<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_Range<Key, Value>::keyOffset(Key const& __delta){
- if(_root != NULL){
- _root->keyOffset(__delta);
- }
- }
- template<class Key, class Value>
- inline void SplayTree_Range<Key, Value>::valueOffset(Value const& __delta){
- if(_root != NULL){
- _root->valueUpdate(__delta, false);
- }
- }
- template<class Key, class Value>
- inline void SplayTree_Range<Key, Value>::valueOverride(Value const& __value){
- if(_root != NULL){
- _root->valueUpdate(__value, true);
- }
- }
- template<class Key, class Value>
- inline Value&
- SplayTree_Range<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_Range<Key, Value>::splitOut(Key const& __upper_bound, SplayTree_Range* __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_Range<Key, Value>::mergeAfter(SplayTree_Range* __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_Range<Key, Value>::merge(SplayTree_Range* __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;
- }
-}
-
generated by cgit v1.2.3 (git 2.25.1) at 2024-06-26 09:40:53 +0800