From 1817d739e89b1d4c1c09d5f553ce5068fab0e4d7 Mon Sep 17 00:00:00 2001 From: cathook Date: Mon, 21 Apr 2014 14:13:53 +0800 Subject: =?UTF-8?q?=E5=A3=93=E5=8A=9B=E6=B8=AC=E8=A9=A6=E5=AE=8C=E6=88=90~?= =?UTF-8?q?~~~~~~~~~?= MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit --- meowpp/dsa/KD_Tree.h | 146 +++++++++------- meowpp/dsa/KD_Tree.hpp | 390 +++++++++++++++++++++++++------------------ meowpp/dsa/MergeableHeap.hpp | 56 ++----- meowpp/dsa/SegmentTree.h | 49 ++++-- meowpp/dsa/SegmentTree.hpp | 179 +++++++------------- meowpp/dsa/SplayTree.h | 5 +- meowpp/dsa/SplayTree.hpp | 312 ++++++++++++++++------------------ 7 files changed, 572 insertions(+), 565 deletions(-) (limited to 'meowpp/dsa') diff --git a/meowpp/dsa/KD_Tree.h b/meowpp/dsa/KD_Tree.h index 2e55d12..2ba81a1 100644 --- a/meowpp/dsa/KD_Tree.h +++ b/meowpp/dsa/KD_Tree.h @@ -4,100 +4,120 @@ #include #include #include +#include +#include namespace meow{ - template + template class KD_Tree{ private: struct Node{ - Keys key; - Value value; - ssize_t lChild; - ssize_t rChild; - Node(Keys _key, Value _value, ssize_t _l_child, ssize_t _r_child); + Vector _vector; + ssize_t _lChild; + ssize_t _rChild; + // + Node(Vector __vector, ssize_t __lChild, ssize_t __rChild); }; typedef std::vector Nodes; + // class Sorter{ private: - Nodes const& nodes; - size_t cmp; + Nodes const* _nodes; + size_t _cmp; public: - Sorter(Nodes const& _nodes, size_t _cmp); - bool operator()(size_t const& a, size_t const& b) const; + Sorter(Nodes const* __nodes, size_t __cmp); + bool operator()(size_t const& __a, size_t const& __b) const; }; - typedef std::vector Values; struct Answer{ - Node const& node; - Key dist2; - Answer(Node const& _node, Key _dist2); - bool operator<(Answer const& b) const; + ssize_t _index; + Scalar _dist2; + // + Answer(ssize_t __index, Scalar __dist2); + Answer(Answer const& __answer2); + }; + class AnswerCompare{ + private: + Nodes const* _nodes; + bool _cmpValue; + public: + AnswerCompare(Nodes const* __nodes, bool __cmpValue); + bool operator()(Answer const& __a, Answer const& __b) const; }; - typedef typename std::list AnswerList; - typedef typename AnswerList::iterator AnswerListIterator; + typedef std::vector AnswerV; + typedef std::priority_queue Answers; // - const ssize_t NIL; + const ssize_t _NIL; // - Nodes nodes; - size_t root; - bool needRebuild; - size_t dimension; + Nodes _nodes; + size_t _root; + bool _needRebuild; + size_t _dimension; // - Key distance2(Keys const& k1, Keys const& k2) const; - size_t query(Keys const& key, - size_t k, - size_t index, - int depth, - std::vector& dist2_v, - Key dist2_s, - AnswerList* ret) const; - ssize_t build(ssize_t beg, - ssize_t end, - std::vector* orders, - int depth); + Scalar distance2(Vector const& __v1, Vector const& __v2) const; + // + void query(Vector const& __vector, + size_t __nearestNumber, + AnswerCompare const& __answerCompare, + size_t __index, + int __depth, + std::vector& __dist2Vector, + Scalar __dist2Minimum, + Answers *__out) const; + ssize_t build(ssize_t __beg, + ssize_t __end, + std::vector* __orders, + int __depth); public: + typedef typename std::vector Vectors; + // KD_Tree(); - KD_Tree(size_t _dimension); + KD_Tree(size_t __dimension); ~KD_Tree(); // - void insert(Keys const& key, Value value); - void build(); + void insert(Vector const& __vector); + bool erase (Vector const& __vector); + void build(); + void forceBuild(); // - Value query (Keys const& point, int k) const; - Values rangeQuery(Keys const& point, int k) const; + Vectors query(Vector const& __vector, + size_t __nearestNumber, + bool __compareWholeVector) const; // - void clear(); - void reset(size_t _dimension); + void clear(); + void reset(size_t __dimension); }; /********************************************************* @asciidoc - === meow:: *KD_Tree* (C++ class) + === meow:: *KD_Tree* (C++ class) .Description - `KD_Tree` is *K-dimension tree*, which is a dictionary(key->value). - Where the type if key is a *K-dimension vector* . - - .Template Request - * `Keys` should has `operator[]` to allow the KD_Tree access the k-dimensions - * `Key` should has `operator*`, `operator+` - - .Support Methods - * N <- numbers of element in the kd-tree - * K <- dimensions - * `Keys` is the tyepname of the vector - * `Key` is the typename of the element in the vector - * `Value` is the typename of value + `KD_Tree` is *K-dimension tree*, which is a multiple set contain lots of + vector with K dimension. + + .Template Request + * `Vector` should has `operator[]` to allow the KD_Tree, `operator<` to + compare when two vector are point to the same place, `operator==` + access the k-dimensions + * `Scalar` should has `operator*`, `operator+`, `operator<` + + .Support Methods + * N <- numbers of element in the kd-tree + * K <- dimensions + * `Vector` is the tyepname of the vector + * `Vectors` is the typename of the std::vector [options="header",width="100%",cols="1>,1v) - || build|()|void|O(KN logN) | Build the data structure(the `insert()` + ||insert|(Vector const& v)|void|O(1)|Insert a vector + ||erase |(Vector const& v)|bool|O(N*x)| Find a vector which is the same + as `v` and remove it from the KD_Tree, `x` in the Big-O time complex + is cost by `Vector::operator==`. + || build|()|void|O(KN logN) if need | Build the data structure if need. + || forceBuild|()|void|O(KN logN) | Build the data structure(the `insert()` method will not build the data structure immediately) - |const|query|(Keys const& point, int k)|Value|O(kN ^1-1/k^ ) | - Using Euclidean-Distance to find the k-nearest neighbor from `point` . - And return the corrosponding value - |const|query|(Keys const& point, int k)|std::vector|O(kN ^1-1/k^ ) | - Using Euclidean-Distance to find all the x-nearest neighbor from `point` , - where x <= k. And return an array of all the corrosponding value. + |const|query|(Vector const& v, int k)|Vectors|O(kN ^1-1/k^ ) | + Using Euclidean-Distance to find the 1st to k-th nearest neighbor from `v` . + And return; ||clear|()|O(1)|Clear all data ||reset|(size_t dimension)|O(1)|Clear all data and then set the this->dimension be `dimension` diff --git a/meowpp/dsa/KD_Tree.hpp b/meowpp/dsa/KD_Tree.hpp index ac9f868..f0e97a9 100644 --- a/meowpp/dsa/KD_Tree.hpp +++ b/meowpp/dsa/KD_Tree.hpp @@ -2,196 +2,266 @@ #include #include #include -#include -#include "utility.h" +#include +#include "../utility.h" namespace meow{ - template - inline KD_Tree::Node::Node(Keys _key, - Value _value, - ssize_t _l_child, - ssize_t _r_child): - key(_key), value(_value), lChild(_l_child), rChild(_r_child){ } - // - template - inline KD_Tree::Sorter::Sorter(KD_Tree::Nodes const& _nodes, - size_t _cmp): - nodes(_nodes), cmp(_cmp){ } - template + //////////////////////////////////////////////////////////////////// + // **# Node #** // + //////////////////////////////////////////////////////////////////// + template + inline + KD_Tree::Node::Node(Vector __vector, + ssize_t __lChild, ssize_t __rChild): + _vector(__vector), _lChild(__lChild), _rChild(__rChild){ + } + //////////////////////////////////////////////////////////////////// + // **# Sorter #** // + //////////////////////////////////////////////////////////////////// + template + inline + KD_Tree::Sorter::Sorter(Nodes const* __nodes, size_t __cmp): + _nodes(__nodes), _cmp(__cmp){ + } + template inline bool - KD_Tree::Sorter::operator()(size_t const& a, - size_t const& b) const{ - if(nodes[a].key[cmp] != nodes[b].key[cmp]){ - return (nodes[a].key[cmp] < nodes[b].key[cmp]); + KD_Tree::Sorter::operator()(size_t const& __a, + size_t const& __b) const{ + if((*_nodes)[__a]._vector[_cmp] != (*_nodes)[__b]._vector[_cmp]){ + return ((*_nodes)[__a]._vector[_cmp] < (*_nodes)[__b]._vector[_cmp]); } - return (nodes[a].value < nodes[b].value); + return ((*_nodes)[__a]._vector < (*_nodes)[__b]._vector); + } + //////////////////////////////////////////////////////////////////// + // **# Answer / Answer's Compare class #** // + //////////////////////////////////////////////////////////////////// + template + inline + KD_Tree::Answer::Answer(ssize_t __index, Scalar __dist2): + _index(__index), _dist2(__dist2){ + } + template + inline + KD_Tree::Answer::Answer(Answer const& __answer2): + _index(__answer2._index), _dist2(__answer2._dist2){ } // - template - inline KD_Tree::Answer::Answer(Node const& _node, - Key _dist2): - node(_node), dist2(_dist2){ } - template + template + inline + KD_Tree::AnswerCompare::AnswerCompare(Nodes const* __nodes, + bool __cmpValue): + _nodes(__nodes), _cmpValue(__cmpValue){ + } + template inline bool - KD_Tree::Answer::operator<(Answer const& b) const{ - if(dist2 != b.dist2) return (dist2 < b.dist2); - return (node.value < b.node.value); + KD_Tree::AnswerCompare::operator()(Answer const& __a, + Answer const& __b) const{ + if(_cmpValue == true && __a._dist2 == __b._dist2){ + return ((*_nodes)[__a._index]._vector < (*_nodes)[__b._index]._vector); + } + return (__a._dist2 < __b._dist2); } - // - template - inline Key KD_Tree::distance2(Keys const& k1, - Keys const& k2) const{ - Key ret(0); - for(size_t i = 0; i < dimension; i++) - ret += squ(k1[i] - k2[i]); + //////////////////////////////////////////////////////////////////// + // **# distance2() #** // + //////////////////////////////////////////////////////////////////// + template + inline Scalar + KD_Tree::distance2(Vector const& __v1, + Vector const& __v2) const{ + Scalar ret(0); + for(size_t i = 0; i < _dimension; i++){ + ret += squ(__v1[i] - __v2[i]); + } return ret; } - template - inline size_t KD_Tree::query(Keys const& key, - size_t k, - size_t index, - int depth, - std::vector& dist2_v, - Key dist2_s, - KD_Tree::AnswerList* ret) const{ - if(index == NIL){ - return 0; - } - size_t cmp = depth % dimension; - ssize_t right_side, opposite, size; - ssize_t sz, other; - if(key[cmp] <= nodes[index].key[cmp]){ - right_side = nodes[index].lChild; - opposite = nodes[index].rChild; + //////////////////////////////////////////////////////////////////// + // **# query() #** // + //////////////////////////////////////////////////////////////////// + template + inline void + KD_Tree::query(Vector const& __vector, + size_t __nearestNumber, + AnswerCompare const& __answerCompare, + size_t __index, + int __depth, + std::vector& __dist2Vector, + Scalar __dist2Minimum, + Answers *__out) const{ + if(__index == _NIL) return ; + size_t cmp = __depth % _dimension; + ssize_t this_side, that_side; + if(!(_nodes[__index]._vector[cmp] < __vector[cmp])){ + this_side = _nodes[__index]._lChild; + that_side = _nodes[__index]._rChild; }else{ - right_side = nodes[index].rChild; - opposite = nodes[index].lChild; + this_side = _nodes[__index]._rChild; + that_side = _nodes[__index]._lChild; } - size = query(key, k, right_side, depth + 1, dist2_v, dist2_s, ret); - Answer my_ans(nodes[index], distance2(nodes[index].key, key)); - if(size < k || my_ans < *(ret->rbegin())){ - KD_Tree::AnswerListIterator it = ret->begin(); - while(it != ret->end() && !(my_ans < *it)) it++; - ret->insert(it, my_ans); - size++; + query(__vector, __nearestNumber, __answerCompare, + this_side, __depth + 1, + __dist2Vector, __dist2Minimum, + __out); + Answer my_ans(__index, distance2(_nodes[__index]._vector, __vector)); + if(__out->size() < __nearestNumber || + __answerCompare(my_ans, __out->top())){ + __out->push(my_ans); + if(__out->size() > __nearestNumber) __out->pop(); } - Key dist2_old = dist2_v[cmp]; - dist2_v[cmp] = squ(nodes[index].key[cmp] - key[cmp]); - dist2_s += dist2_v[cmp] - dist2_old; - if(size < k || (*(ret->rbegin())).dist2 >= dist2_s){ - KD_Tree::AnswerList ret2; - size += query(key, k, opposite, depth + 1, dist2_v, dist2_s, &ret2); - KD_Tree::AnswerListIterator it1, it2; - for(it1 = ret->begin(), it2 = ret2.begin(); it2 != ret2.end(); it2++){ - while(it1 != ret->end() && *it1 < *it2) it1++; - it1 = ++(ret->insert(it1, *it2)); - } + Scalar dist2_old = __dist2Vector[cmp]; + __dist2Vector[cmp] = squ(_nodes[__index]._vector[cmp] - __vector[cmp]); + Scalar dist2Minimum = __dist2Minimum + __dist2Vector[cmp] - dist2_old; + if(__out->size() < __nearestNumber || + !(__out->top()._dist2 < dist2Minimum)){ + query(__vector, __nearestNumber, __answerCompare, + that_side, __depth + 1, + __dist2Vector, dist2Minimum, + __out); } - if(size > k){ - for(int i = size - k; i--; ){ - ret->pop_back(); - } - size = k; - } - dist2_v[cmp] = dist2_old; - return size; - } - template - inline ssize_t KD_Tree::build(ssize_t beg, - ssize_t end, - std::vector* orders, - int depth){ - if(beg > end){ - return NIL; + __dist2Vector[cmp] = dist2_old; + } + //////////////////////////////////////////////////////////////////// + // **# build() #** // + //////////////////////////////////////////////////////////////////// + template + inline ssize_t + KD_Tree::build(ssize_t __beg, + ssize_t __end, + std::vector* __orders, + int __depth){ + if(__beg > __end) return _NIL; + size_t tmp_order = _dimension; + size_t which_side = _dimension + 1; + ssize_t mid = (__beg + __end) / 2; + size_t cmp = __depth % _dimension; + for(ssize_t i = __beg; i <= mid; i++){ + __orders[which_side][__orders[cmp][i]] = 0; } - ssize_t mid = (beg + end) / 2; - size_t cmp = depth % 2; - std::set right; - for(ssize_t i = mid + 1; i <= end; i++){ - right.insert(orders[cmp][i]); + for(ssize_t i = mid + 1; i <= __end; i++){ + __orders[which_side][__orders[cmp][i]] = 1; } - for(int i = 0; i < dimension; i++){ + for(int i = 0; i < _dimension; i++){ if(i == cmp) continue; - size_t aa = beg, bb = mid + 1; - for(int j = beg; j <= end; j++){ - if(orders[i][j] == orders[cmp][mid]){ - orders[dimension][mid] = orders[i][j]; - }else if(right.find(orders[i][j]) != right.end()){ - orders[dimension][bb++] = orders[i][j]; + size_t left = __beg, right = mid + 1; + for(int j = __beg; j <= __end; j++){ + size_t ask = __orders[i][j]; + if(ask == __orders[cmp][mid]){ + __orders[tmp_order][mid] = ask; + }else if(__orders[which_side][ask] == 1){ + __orders[tmp_order][right++] = ask; }else{ - orders[dimension][aa++] = orders[i][j]; + __orders[tmp_order][left++] = ask; } } - for(int j = beg; j <= end; j++){ - orders[i][j] = orders[dimension][j]; + for(int j = __beg; j <= __end; j++){ + __orders[i][j] = __orders[tmp_order][j]; } } - nodes[orders[cmp][mid]].lChild = build(beg, mid - 1, orders, depth + 1); - nodes[orders[cmp][mid]].rChild = build(mid + 1, end, orders, depth + 1); - return orders[cmp][mid]; - } - template - inline KD_Tree::KD_Tree(): - NIL(-1), root(NIL), needRebuild(false), dimension(1){ } - template - inline KD_Tree::KD_Tree(size_t _dimension): - NIL(-1), root(NIL), needRebuild(false), dimension(_dimension){ } - template - inline KD_Tree::~KD_Tree(){ } - template - inline void KD_Tree::insert(Keys const& key, Value value){ - nodes.push_back(Node(key, value, NIL, NIL)); - needRebuild = true; - } - template - inline void KD_Tree::build(){ - if(needRebuild){ - std::vector *orders = new std::vector[dimension + 1]; - for(int j = 0; j < dimension + 1; j++){ - orders[j].resize(nodes.size()); - } - for(int j = 0; j < dimension; j++){ - for(size_t i = 0, I = nodes.size(); i < I; i++){ - orders[j][i] = i; + _nodes[__orders[cmp][mid]]._lChild=build(__beg,mid-1,__orders,__depth+1); + _nodes[__orders[cmp][mid]]._rChild=build(mid+1,__end,__orders,__depth+1); + return __orders[cmp][mid]; + } + //////////////////////////////////////////////////////////////////// + // **# constructures/destructures #** // + //////////////////////////////////////////////////////////////////// + template + inline + KD_Tree::KD_Tree(): + _NIL(-1), _root(_NIL), _needRebuild(false), _dimension(1){ + } + template + inline + KD_Tree::KD_Tree(size_t __dimension): + _NIL(-1), _root(_NIL), _needRebuild(false), _dimension(__dimension){ + } + template + inline + KD_Tree::~KD_Tree(){ + } + //////////////////////////////////////////////////////////////////// + // **# insert, build #** // + //////////////////////////////////////////////////////////////////// + template + inline void + KD_Tree::insert(Vector const& __vector){ + _nodes.push_back(Node(__vector, _NIL, _NIL)); + _needRebuild = true; + } + template + inline bool + KD_Tree::erase(Vector const& __vector){ + for(size_t i = 0, I = _nodes.size(); i < I; i++){ + if(_nodes[i] == __vector){ + if(i != I - 1){ + std::swap(_nodes[i], _nodes[I - 1]); } - std::sort(orders[j].begin(), orders[j].end(), Sorter(nodes, j)); + _needRebuild = true; + return true; } - root = build(0, (ssize_t)nodes.size() - 1, orders, 0); - needRebuild = false; - delete [] orders; } + return false; } - template - inline Value KD_Tree::query(Keys const& point, int k) const{ - ((KD_Tree*)this)->build(); - KD_Tree::AnswerList ret; - std::vector tmp(dimension, Key(0)); - query(point, k, root, 0, tmp, Key(0), &ret); - return (*(ret.rbegin())).node.value; - } - template - inline typename KD_Tree::Values - KD_Tree::rangeQuery(Keys const& point, int k) const{ + template + inline void + KD_Tree::build(){ + if(_needRebuild){ + forceBuild(); + } + } + template + inline void + KD_Tree::forceBuild(){ + std::vector *orders = new std::vector[_dimension + 2]; + for(int j = 0; j < _dimension + 2; j++){ + orders[j].resize(_nodes.size()); + } + for(int j = 0; j < _dimension; j++){ + for(size_t i = 0, I = _nodes.size(); i < I; i++){ + orders[j][i] = i; + } + std::sort(orders[j].begin(), orders[j].end(), Sorter(&_nodes, j)); + } + _root = build(0, (ssize_t)_nodes.size() - 1, orders, 0); + delete [] orders; + _needRebuild = false; + } + //////////////////////////////////////////////////////////////////// + // **# query #** // + //////////////////////////////////////////////////////////////////// + template + inline typename KD_Tree::Vectors + KD_Tree::query(Vector const& __vector, + size_t __nearestNumber, + bool __compareWholeVector) const{ ((KD_Tree*)this)->build(); - KD_Tree::AnswerList ret; - std::vector tmp(dimension, Key(0)); - query(point, k, root, 0, tmp, Key(0), &ret); - KD_Tree::Values ret_val(ret.size()); - int i = 0; - for(KD_Tree::AnswerListIterator it = ret.begin(); it != ret.end(); it++){ - ret_val[i++] = (*it).node.value; + AnswerCompare answer_compare(&_nodes, __compareWholeVector); + Answers answer_set(answer_compare); + std::vector tmp(_dimension, 0); + query(__vector, __nearestNumber, + answer_compare, + _root, 0, + tmp, Scalar(0), + &answer_set); + Vectors ret(answer_set.size()); + for(int i = (ssize_t)answer_set.size() - 1; i >= 0; i--){ + ret[i] = _nodes[answer_set.top()._index]._vector; + answer_set.pop(); } - return ret_val; + return ret; } - template - inline void KD_Tree::clear(){ - root = NIL; - nodes.clear(); - needRebuild = false; + //////////////////////////////////////////////////////////////////// + // **# clear, reset #** // + //////////////////////////////////////////////////////////////////// + template + inline void + KD_Tree::clear(){ + _root = _NIL; + _nodes.clear(); + _needRebuild = false; } - template - inline void KD_Tree::reset(size_t _dimension){ + template + inline void + KD_Tree::reset(size_t __dimension){ clear(); - dimension = _dimension; + _dimension = __dimension; } } diff --git a/meowpp/dsa/MergeableHeap.hpp b/meowpp/dsa/MergeableHeap.hpp index 6e49a1c..be7dcea 100644 --- a/meowpp/dsa/MergeableHeap.hpp +++ b/meowpp/dsa/MergeableHeap.hpp @@ -5,16 +5,14 @@ namespace meow{ // **# MergeableHeap--Node-- constructor #** // ////////////////////////////////////////////////////////// template - inline - MergeableHeap::Node::Node(Element const& _value): // Node + inline MergeableHeap::Node::Node(Element const& _value): // Node value(_value), l_child(NULL), r_child(NULL), weight(1){ } ////////////////////////////////////////////////////////// // **# MergeableHeap -- clear, duplicate #** // ////////////////////////////////////////////////////////// template - inline void - MergeableHeap::clear(Node* _node){ //clear + inline void MergeableHeap::clear(Node* _node){ //clear if(_node != NULL){ clear(_node->l_child); clear(_node->r_child); @@ -59,18 +57,13 @@ namespace meow{ // **# MergeableHeap -- constrctors/destructors #** // ////////////////////////////////////////////////////////// template - inline - MergeableHeap::MergeableHeap(): //MergeableHeap + inline MergeableHeap::MergeableHeap(): //MergeableHeap root(NULL){ } template - inline - MergeableHeap::MergeableHeap(MergeableHeap const& _heap2): - root(NULL){ - root = dup(_heap2.root); - } + inline MergeableHeap::MergeableHeap(MergeableHeap const& _heap2): + root(NULL){ root = dup(_heap2.root); } template - inline - MergeableHeap::~MergeableHeap(){ //~MergeableHeap + inline MergeableHeap::~MergeableHeap(){ //~MergeableHeap clear(root); } @@ -84,8 +77,7 @@ namespace meow{ return *this; } template - inline void - MergeableHeap::moveTo(MergeableHeap* _heap2){ // moveTo + inline void MergeableHeap::moveTo(MergeableHeap* _heap2){ // moveTo _heap2->clear(); _heap2->root = root; root = NULL; @@ -93,41 +85,30 @@ namespace meow{ ////////////////////////////////////////////////////////// // **# MergeableHeap -- access: top, size, emtpy #** // ////////////////////////////////////////////////////////// - template - inline Element const& - MergeableHeap::top() const{ // top - return root->value; - } - template - inline size_t - MergeableHeap::size() const{ // size + template // top + inline Element const& MergeableHeap::top()const{return root->value;} + template // size + inline size_t MergeableHeap::size() const{ return (root == NULL ? 0 : root->weight); } - template - inline size_t - MergeableHeap::empty() const{ // empty - return (size() == 0); - } + template // empty + inline size_t MergeableHeap::empty() const{ return (size() == 0); } ////////////////////////////////////////////////////////// // **# MergeableHeap -- update: push, pop, merge #** // ////////////////////////////////////////////////////////// template - inline void - MergeableHeap::push(Element const& _value){ // push - Node* new_node = new Node(_value); - root = merge(root, new_node); + inline void MergeableHeap::push(Element const& _value){ // push + root = merge(root, new Node(_value)); } template - inline void - MergeableHeap::pop(){ // pop + inline void MergeableHeap::pop(){ // pop Node* l = root->l_child; Node* r = root->r_child; delete root; root = merge(l, r); } template - inline void - MergeableHeap::merge(MergeableHeap* _heap2){ // merge + inline void MergeableHeap::merge(MergeableHeap* _heap2){ // merge root = merge(root, _heap2->root); _heap2->root = NULL; } @@ -135,8 +116,7 @@ namespace meow{ // **# MergeableHeap -- refresh: clear #** // ////////////////////////////////////////////////////////// template - inline void - MergeableHeap::clear(){ // clear + inline void MergeableHeap::clear(){ // clear clear(root); root = NULL; } diff --git a/meowpp/dsa/SegmentTree.h b/meowpp/dsa/SegmentTree.h index 1aa396d..585ea5d 100644 --- a/meowpp/dsa/SegmentTree.h +++ b/meowpp/dsa/SegmentTree.h @@ -9,27 +9,19 @@ namespace meow{ Value _value; Value _offset; bool _sameFlag; - // - Node(); }; // size_t _size; std::vector _nodes; - size_t const _root; // - size_t leftChild(size_t __parent) const; - size_t rightChild(size_t __parent) const; - // - void downUpdate(size_t __L, size_t __R, size_t __index); - void override(size_t __l, size_t __r, - size_t __L, size_t __R, - size_t __index, Value const& __value); - void offset(size_t __l, size_t __r, - size_t __L, size_t __R, - size_t __index, Value const& __delta); - Value query(size_t __l, size_t __r, - size_t __L, size_t __R, + void update(size_t __index, size_t __size, Value const& __value, + bool __override); + void update(size_t __l, size_t __r, size_t __L, size_t __R, + size_t __index, Value const& __value, + bool __override); + Value query(size_t __l, size_t __r, size_t __L, size_t __R, size_t __index); + // bool rangeCorrect(ssize_t* __first, ssize_t* __last) const; public: SegmentTree(); @@ -38,9 +30,28 @@ namespace meow{ // void reset(size_t __size); // - Value query (ssize_t __first, ssize_t __last) const; - void override(ssize_t __first, ssize_t __last, Value const& __value); - void offset (ssize_t __first, ssize_t __last, Value const& __delta); + Value query (ssize_t __first, ssize_t __last) const; + void override(ssize_t __first, ssize_t __last, Value const& __value); + void offset (ssize_t __first, ssize_t __last, Value const& __delta); + void print(){ + for(int i = 0; i < _size; i++){ + query(i, i); + } + printf("\n"); + for(int depth = 0, count = 1, size = _size, id = 0; + size > 0; + depth++, count *= 2, size /= 2){ + for(int j = 0; j < count; j++, id++){ + printf("[%3d%c%3d%*s]", + _nodes[id]._value.value, + _nodes[id]._sameFlag ? 's' : ' ', + _nodes[id]._offset.value, + size * 9 - 9, + ""); + } + printf("\n"); + } + } }; /********************************************************* @asciidoc @@ -89,4 +100,6 @@ namespace meow{ *********************************************************/ } +#include "SegmentTree.hpp" + #endif diff --git a/meowpp/dsa/SegmentTree.hpp b/meowpp/dsa/SegmentTree.hpp index 24efcdd..a2b74e8 100644 --- a/meowpp/dsa/SegmentTree.hpp +++ b/meowpp/dsa/SegmentTree.hpp @@ -1,172 +1,111 @@ -#ifndef SegmentTree_H__ -#define SegmentTree_H__ +#include "../utility.h" -namespace meow{ - template - inline SegmentTree::Node::Node(){ } +#include - template - inline size_t - SegmentTree::leftChild(size_t __parent) const { - return __parent * 2 + 1; - } - template - inline size_t - SegmentTree::rightChild(size_t __parent) const { - return __parent * 2 + 2; - } - - template - inline void - SegmentTree::downUpdate(size_t __L, size_t __R, size_t __index){ - size_t mid = (__L + __R) / 2; - Value& val = _nodes[__index]._value; - Value& off = _nodes[__index]._offset; - if(_nodes[__index]._sameFlag){ - if(__L < __R){ - override(__L , mid, __L , mid, leftChild(__index), val); - override(mid + 1, __R, mid + 1, __R, rightChild(__index), val); - } - _nodes[__index]._sameFlag = false; - _nodes[__index]._offset = 0; - }else if(!(_nodes[__index]._offset == Value(0))){ - if(__L < __R){ - offset(__L , mid, __L , mid, leftChild(__index), off); - offset(mid + 1, __R, mid + 1, __R, rightChild(__index), off); - } - _nodes[__index]._offset = 0; - } - } +namespace meow{ + template inline void - SegmentTree::override(size_t __l, size_t __r, - size_t __L, size_t __R, - size_t __index, Value const& __value){ - if(__l == __L && __r == __R){ - _nodes[__index]._value = __value * (__R - __L + 1); - _nodes[__index]._offset = 0; - _nodes[__index]._sameFlag = true; - return ; - } - downUpdate(__L, __R, __index); - size_t mid = (__L + __R) / 2; - if(__r <= mid){ - override(__l, __r, __L , mid, leftChild(__index), __value); - }else if(mid + 1 <= __l){ - override(__l, __r, mid + 1, __R, rightChild(__index), __value); + SegmentTree::update(size_t __i, size_t __size, Value const& __value, + bool __over){ + if(__over){ + _nodes[__i]._value = __value * __size; + _nodes[__i]._offset = __value; + _nodes[__i]._sameFlag = true; }else{ - override(__l , mid, __L , mid, leftChild(__index), __value); - override(mid + 1, __r, mid + 1, __R, rightChild(__index), __value); + _nodes[__i]._value = _nodes[__i]._value + __value * __size; + _nodes[__i]._offset = _nodes[__i]._offset + __value; } - _nodes[__index]._value = ( _nodes[ leftChild(__index)]._value - | _nodes[rightChild(__index)]._value); } template inline void - SegmentTree::offset(size_t __l, size_t __r, - size_t __L, size_t __R, - size_t __index, Value const& __delta){ + SegmentTree::update(size_t __l, size_t __r, size_t __L, size_t __R, + size_t __i, Value const& __value, + bool __over){ if(__l == __L && __r == __R){ - _nodes[__index]._value = _nodes[__index]._value + __delta*(__R-__L+1); - if(!_nodes[__index]._sameFlag){ - _nodes[__index]._offset = _nodes[__index]._offset + __delta; - } + update(__i, __R - __L + 1, __value, __over); return ; } - downUpdate(__L, __R, __index); size_t mid = (__L + __R) / 2; - if(__r <= mid){ - offset(__l, __r, __L , mid, leftChild(__index), __delta); - }else if(mid + 1 <= __l){ - offset(__l, __r, mid + 1, __R, rightChild(__index), __delta); - }else{ - offset(__l , mid, __L , mid, leftChild(__index), __delta); - offset(mid + 1, __r, mid + 1, __R, rightChild(__index), __delta); + if(__L < __R){ + update(__i*2+1, mid-__L+1, _nodes[__i]._offset, _nodes[__i]._sameFlag); + update(__i*2+2, __R - mid, _nodes[__i]._offset, _nodes[__i]._sameFlag); + _nodes[__i]._offset = Value(0); + _nodes[__i]._sameFlag = false; + } + if (__r <= mid) update(__l,__r, __L ,mid, __i*2+1, __value, __over); + else if(mid+1 <= __l) update(__l,__r, mid+1,__R, __i*2+2, __value, __over); + else{ + update(__l,mid , __L,mid , __i*2+1, __value, __over); + update( mid+1, __r, mid+1, __R, __i*2+2, __value, __over); } - _nodes[__index]._value = ( _nodes[ leftChild(__index)]._value - | _nodes[rightChild(__index)]._value); + _nodes[__i]._value = ( + (_nodes[__i * 2 + 1]._value | _nodes[__i * 2 + 2]._value) + + _nodes[__i]._offset + ); } template inline Value - SegmentTree::query(size_t __l, size_t __r, - size_t __L, size_t __R, - size_t __index){ - if((__l == __L && __r == __R) || _nodes[__index]._sameFlag){ - return _nodes[__index]._value; - } + SegmentTree::query(size_t __l, size_t __r, size_t __L, size_t __R, + size_t __i){ + if(__l == __L && __r == __R) return _nodes[__i]._value; + Value off = _nodes[__i]._offset * (__r - __l + 1); + if(_nodes[__i]._sameFlag) return off; size_t mid = (__L + __R) / 2; - Value& off = _nodes[__index]._offset; - if(__r <= mid){ - return query(__l, __r, __L , mid, leftChild(__index)) + off; - }else if(mid + 1 <= __l){ - return query(__l, __r, mid + 1, __R, rightChild(__index)) + off; - }else{ - return ( query(__l , mid, __L , mid, leftChild(__index)) - | query(mid + 1, __r, mid + 1, __R, rightChild(__index))) + off; + if (__r <= mid) return query(__l,__r, __L , mid, __i*2+1) + off; + else if(mid+1 <= __l) return query(__l,__r, mid+1, __R, __i*2+2) + off; + else{ + return ( query(__l, mid , __L, mid, __i*2+1) + | query( mid+1, __r, mid+1, __R, __i*2+2) + ) + off; } } + // template inline bool SegmentTree::rangeCorrect(ssize_t* __first, ssize_t* __last) const{ - if(*__last < *__first){ - return false; - } - if(*__last < 0 || _size - 1 < *__first){ - return false; - } + if(*__last<*__first || *__last<0 || _size-1<*__first) return false; *__first = inRange((ssize_t)0, (ssize_t)_size - 1, *__first); *__last = inRange((ssize_t)0, (ssize_t)_size - 1, *__last ); return true; } - + // template - inline - SegmentTree::SegmentTree(): _size(0), _root(0) { - } + inline SegmentTree::SegmentTree(){ reset(1); } template - inline - SegmentTree::SegmentTree(size_t __size): _size(0), _root(0){ - reset(__size); - } + inline SegmentTree::SegmentTree(size_t __size){ reset(__size); } template - inline - SegmentTree::SegmentTree(SegmentTree const& __tree2): - _size(__tree2._size), _nodes(__tree2._nodes), _root(0){ } + inline SegmentTree::SegmentTree(SegmentTree const& __tree2): + _size(__tree2._size), _nodes(__tree2._nodes){ } // template inline void SegmentTree::reset(size_t __size){ - _size = __size; + _size = std::max(__size, (size_t)1); _nodes.resize(__size * 4); - _nodes[_root]._sameFlag = true; - _nodes[_root]._value = Value(0); + _nodes[0]._sameFlag = true; + _nodes[0]._value = Value(0); + _nodes[0]._offset = Value(0); } template inline Value SegmentTree::query(ssize_t __first, ssize_t __last) const{ - if(rangeCorrect(&__first, &__last) == false){ - return Value(); - } - return ((SegmentTree*)this)->query(__first, __last, 0, _size - 1, _root); + if(rangeCorrect(&__first, &__last) == false) return Value(); + return ((SegmentTree*)this)->query(__first, __last, 0, _size - 1, 0); } template inline void SegmentTree::override(ssize_t __first, ssize_t __last, Value const& __value){ - if(rangeCorrect(&__first, &__last) == false){ - return ; - } - override(__first, __last, 0, _size - 1, _root, __value); + if(rangeCorrect(&__first, &__last) == false) return ; + update(__first, __last, 0, _size - 1, 0, __value, true); } template inline void SegmentTree::offset(ssize_t __first, ssize_t __last, Value const& __delta){ - if(rangeCorrect(&__first, &__last) == false){ - return ; - } - offset(__first, __last, 0, _size - 1, _root, __delta); + if(rangeCorrect(&__first, &__last) == false) return ; + update(__first, __last, 0, _size - 1, 0, __delta, false); } } -#endif diff --git a/meowpp/dsa/SplayTree.h b/meowpp/dsa/SplayTree.h index 3d2d2e3..f738ded 100644 --- a/meowpp/dsa/SplayTree.h +++ b/meowpp/dsa/SplayTree.h @@ -26,9 +26,10 @@ namespace meow{ void sizeUpdate (Node* __node ) const; void connectLChild(Node* __parent, Node* __child ) const; void connectRChild(Node* __parent, Node* __child ) const; + Node const* setRoot(Node* __node) const; // - Node* clear(Node* __node); - Node* dup (Node* __node); + Node* clear (Node* __node); + Node* dup (Node* __node); // void rotate( Node* __parent, Node* __child) const; void rotate(Node* __grand, Node* __parent, Node* __child) const; 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 - inline void SplayTree::offsetAdd(Node* __node, - Key const& __delta) const{ + inline void + SplayTree::offsetAdd(Node* __node, Key const& __delta) const{ __node->_key = __node->_key + __delta; __node->_keyOffset = __node->_keyOffset + __delta; } template - inline void SplayTree::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::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 inline void @@ -32,14 +35,14 @@ namespace meow{ } // template - inline void SplayTree::connectLChild(Node* __parent, - Node* __child) const{ + inline void + SplayTree::connectLChild(Node* __parent, Node* __child) const{ if(__parent != NULL) __parent->_lChild = __child; if(__child != NULL) __child ->_parent = __parent; } template - inline void SplayTree::connectRChild(Node* __parent, - Node* __child) const{ + inline void + SplayTree::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 - inline typename SplayTree::Node* SplayTree::dup(Node* __node){ - if(__node == NULL){ - return NULL; - } - Node* node = Node(__node->_key, __node->_value); + inline typename SplayTree::Node* + SplayTree::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 + inline typename SplayTree::Node const* + SplayTree::setRoot(Node* __node) const{ + connectLChild(NULL, (((SplayTree*)this)->_root = __node)); + return _root; + } // template - inline void SplayTree::rotate(Node* __parent, - Node* __child) const{ + inline void + SplayTree::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 - inline void SplayTree::rotate(Node* __grand, - Node* __parent, - Node* __child) const{ + inline void + SplayTree::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 - inline typename SplayTree::Node* SplayTree::splay(Node* __node) const{ - if(__node == NULL){ - return NULL; - } + inline typename SplayTree::Node* + SplayTree::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 - inline typename SplayTree::Node* SplayTree::findKey(Node* __node, - Key const& __key) const{ + inline typename SplayTree::Node* + SplayTree::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 - inline typename SplayTree::Node* SplayTree::findMinMax(Node* __node, - bool minimum) const{ + inline typename SplayTree::Node* + SplayTree::findMinMax(Node* __node, bool minimum) const{ Node* ret = __node; while(__node != NULL){ offsetDown(__node); @@ -164,32 +171,23 @@ namespace meow{ return ret; } template - inline typename SplayTree::Node* SplayTree::findOrder(Node* __node, - size_t __order) const{ + inline typename SplayTree::Node* + SplayTree::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 - inline void SplayTree::split(Node* __root, - Node** __left, Node** __right){ - if(__root == NULL){ - *__left = NULL; - *__right = NULL; - return ; - } + inline void + SplayTree::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 - inline typename SplayTree::Node* SplayTree::merge(Node* __left, Node* __right){ + inline typename SplayTree::Node* + SplayTree::merge(Node* __left, Node* __right){ if(__left == NULL) return __right; if(__right == NULL) return __left ; offsetDown(__left); @@ -211,9 +210,10 @@ namespace meow{ template inline void SplayTree::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::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 inline SplayTree::Element::Element(): - _entry(NULL), - _node(NULL){ } + _entry(NULL), _node(NULL){ } template inline SplayTree::Element::Element(Node* __node): - _entry(NULL), - _node(NULL){ reset(__node); } + _entry(NULL), _node(NULL){ reset(__node); } template inline SplayTree::Element::Element(Element const& __element2): - _entry(NULL), - _node(NULL){ reset(__element2._node); } + _entry(NULL), _node(NULL){ reset(__element2._node); } template inline SplayTree::Element::~Element(){ delete _entry; } // @@ -254,9 +248,11 @@ namespace meow{ } // template - inline typename SplayTree::Element::Entry* SplayTree::Element::operator->(){ return _entry; } + inline typename SplayTree::Element::Entry* + SplayTree::Element::operator->(){ return _entry; } template - inline typename SplayTree::Element::Entry& SplayTree::Element::operator*(){ return *_entry; } + inline typename SplayTree::Element::Entry& + SplayTree::Element::operator*(){ return *_entry; } // template inline bool @@ -270,117 +266,94 @@ namespace meow{ } // template - inline SplayTree::SplayTree(): - _root(NULL){ } + inline SplayTree::SplayTree(): _root(NULL){ } template inline SplayTree::SplayTree(SplayTree const& __tree2): - _root(NULL){ - _root = dup(__tree2._root); - } + _root(NULL){ setRoot(dup(__tree2._root)); } template - inline SplayTree::~SplayTree(){ - clear(_root); - } + inline SplayTree::~SplayTree(){ clear(_root); } template - inline SplayTree& SplayTree::operator=(SplayTree const& __tree2){ + inline SplayTree& + SplayTree::operator=(SplayTree const& __tree2){ clear(_root); - _root = dup(__tree2._root); + setRoot(dup(__tree2._root)); return *this; } // template - inline typename SplayTree::Element SplayTree::lowerBound(Key const& __key) const{ + inline typename SplayTree::Element + SplayTree::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 - inline typename SplayTree::Element SplayTree::upperBound(Key const& __key) const{ + inline typename SplayTree::Element + SplayTree::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 - inline typename SplayTree::Element SplayTree::rLowerBound(Key const& __key) const{ + inline typename SplayTree::Element + SplayTree::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 - inline typename SplayTree::Element SplayTree::rUpperBound(Key const& __key) const{ + inline typename SplayTree::Element + SplayTree::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 - inline typename SplayTree::Element SplayTree::find(Key const& __key) const{ + inline typename SplayTree::Element + SplayTree::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 - inline typename SplayTree::Element SplayTree::order(size_t __order) const{ + inline typename SplayTree::Element + SplayTree::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 - inline typename SplayTree::Element SplayTree::first() const{ + inline typename SplayTree::Element + SplayTree::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 - inline typename SplayTree::Element SplayTree::last() const{ + inline typename SplayTree::Element + SplayTree::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 - inline typename SplayTree::Element SplayTree::end() const{ return Element(NULL); } + inline typename SplayTree::Element + SplayTree::end() const{ return Element(NULL); } template inline size_t SplayTree::size() const{ return (_root == NULL ? 0 : _root->_size); @@ -403,87 +376,96 @@ namespace meow{ inline bool SplayTree::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 inline bool SplayTree::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 - inline Value& SplayTree::operator[](Key const& __key){ - if(find(__key) == end()){ - insert(__key, Value()); - } + inline Value& + SplayTree::operator[](Key const& __key){ + if(find(__key) == end()) insert(__key, Value()); return find(__key)->second; } template - inline void SplayTree::splitOut(Key const& __upper_bound, - SplayTree* __right){ + inline void + SplayTree::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 - inline bool SplayTree::mergeAfter(SplayTree* __tree2){ + inline bool + SplayTree::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 - inline bool SplayTree::merge(SplayTree* __tree2){ + inline bool + SplayTree::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 - inline void SplayTree::print() const{ + inline void + SplayTree::print() const{ print(_root, 0); } template - inline void SplayTree::moveTo(SplayTree* __tree2){ + inline void + SplayTree::moveTo(SplayTree* __tree2){ __tree2->clear(); __tree2->_root = _root; _root = NULL; -- cgit v1.2.3