diff options
Diffstat (limited to 'meowpp/dsa')
| -rw-r--r-- | meowpp/dsa/DisjointSet.h | 26 | ||||
| -rw-r--r-- | meowpp/dsa/Heaps.h | 84 | ||||
| -rw-r--r-- | meowpp/dsa/KD_Tree.h | 42 | ||||
| -rw-r--r-- | meowpp/dsa/MergeableHeap.hpp | 3 | ||||
| -rw-r--r-- | meowpp/dsa/SegmentTree.h | 92 | ||||
| -rw-r--r-- | meowpp/dsa/SegmentTree.hpp | 172 | ||||
| -rw-r--r-- | meowpp/dsa/SplayTree.h | 75 |
7 files changed, 452 insertions, 42 deletions
diff --git a/meowpp/dsa/DisjointSet.h b/meowpp/dsa/DisjointSet.h index 1ea6d97..b33a839 100644 --- a/meowpp/dsa/DisjointSet.h +++ b/meowpp/dsa/DisjointSet.h @@ -24,6 +24,32 @@ namespace meow{ void reset(size_t _n ); size_t merge(size_t a, size_t b); }; + /********************************************************* + @asciidoc + === meow:: *DisjointSet* (C++ class) + .Description + `DisjointSet` is a lighting data structure that maintain N numbers from + *0* to *N-1* with methods below: + + [options="header",width="100%",cols="1>,1<s,5<,1<,1<,10<",grid="rows"] + |======================================================================= + |Const?|Name| Parameters| Return Type| Time Complexity| Description + |const|root|(size_t number)|size_t|very fast| + Return the *group id* of the number given + |const|size|()|size_t|very fast| + Return *N* + ||reset|(size_t N)|void|very fast| + Clean and initalize + ||merge|(size_t number1, + + size_t number2)|size_t|very fast| + *Union* the group contains number1 and the group contains number2. + Return the merged group id + |======================================================================= +NOTE: *very fast* means that you can consider it as constant time. + +''' +@asciidoc- + *********************************************************/ } #include "DisjointSet.hpp" diff --git a/meowpp/dsa/Heaps.h b/meowpp/dsa/Heaps.h index cac3e01..1e47afd 100644 --- a/meowpp/dsa/Heaps.h +++ b/meowpp/dsa/Heaps.h @@ -4,45 +4,6 @@ #include <cstdlib> namespace meow{ - /********************************************************* - @asciidoc - === MergeableHeap<Key, Value> - .Description - MergeableHeap is a kind of maximum-heap with an extra method `merge`, - which will merge another MergeableHeap into itself. - - .Support methods - * N <- number of elements in the heap - * M <- number of elements in the other heap if need - [options="header",width="100%",cols="1>,1<s,5<,1<,1<,10<",grid="rows"] - |======================================================================= - |Const?|Name| Parameters| Return Type| Time Complexity| Description - ||operator= | (MergeableHeap const&)| *this | O(N) - | Copy operator. - ||moveTo | (MergeableHeap*) | void | O(M) - | Transform the this->data to the heap specified in parameters - |const|top | () | Element | O(1) - | Return the maximum element in the heap. - |const|size | () | size_t | O(1) - | Return the number of elements in the heap. - |const|empty| () | bool | O(1) - | Return whether the heap is empty or not. - ||push |(Element) |void | O(log N) - | Add a element into the heap - ||pop |() |void | O(log N) - | Delete the maximum element from the heap - ||merge |(MergeableHeap*) |void | O(log M) - | Merge the specified MergeableHeap(with size=M) into itself - ||clear |() |void | O(N) - | Delete all elements from the heap - |======================================================================= - -WARNING: Consider there are two MergeableHeap `A` and `B`. -`B` will become empty after you call `A.merge(&B)`. -The data in `B` will override by data in `A` and `A` will become empty after -you call `A.moveTo(&B)` - @asciidoc- - *********************************************************/ template<class Element> class MergeableHeap{ // maximum-heap private: @@ -77,6 +38,51 @@ you call `A.moveTo(&B)` void clear( ); void merge(MergeableHeap* _heap2); }; + + /********************************************************* + @asciidoc + === meow:: *MergeableHeap<Key, Value>* (C++ class) + .Description + MergeableHeap is a kind of maximum-heap with a special method `merge`, + which will merge another MergeableHeap into itself in O(logN) time. + + .Template Request + * `Key` should has `operator<` + + .Support methods + * N <- number of elements in the heap + * M <- number of elements in the other heap if need + [options="header",width="100%",cols="1>,1<s,3<,1<,1<,10<",grid="rows"] + |======================================================================= + |Const?|Name| Parameters| Return Type| Time Complexity| Description + ||operator= | (MergeableHeap const&)| *this | O(N) + | Copy operator. + ||moveTo | (MergeableHeap*) | void | O(M) + | Transform the this->data to the heap specified in parameters + |const|top | () | Element | O(1) + | Return the maximum element in the heap. + |const|size | () | size_t | O(1) + | Return the number of elements in the heap. + |const|empty| () | bool | O(1) + | Return whether the heap is empty or not. + ||push |(Element) |void | O(log N) + | Add a element into the heap + ||pop |() |void | O(log N) + | Delete the maximum element from the heap + ||merge |(MergeableHeap*) |void | O(log M) + | Merge the specified MergeableHeap(with size=M) into itself + ||clear |() |void | O(N) + | Delete all elements from the heap + |======================================================================= + +WARNING: Consider there are two MergeableHeap `A` and `B`. + +`B` will become empty after you call `A.merge(&B)`. + +The data in `B` will override by data in `A` and `A` will become empty after +you call `A.moveTo(&B)` + +''' +@asciidoc- + *********************************************************/ } #include "MergeableHeap.hpp" diff --git a/meowpp/dsa/KD_Tree.h b/meowpp/dsa/KD_Tree.h index 0abc358..2e55d12 100644 --- a/meowpp/dsa/KD_Tree.h +++ b/meowpp/dsa/KD_Tree.h @@ -68,6 +68,48 @@ namespace meow{ void clear(); void reset(size_t _dimension); }; + /********************************************************* + @asciidoc + === meow:: *KD_Tree<Keys, Key, Value>* (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 + [options="header",width="100%",cols="1>,1<s,5<,1<,2<,10<",grid="rows"] + |======================================================================= + |Const?|Name| Parameters| Return Type| Time Complexity| Description + |const|root|(size_t number)|size_t|very fast| + ||insert|(Key const& k, Value v)|void|O(1)|Insert a pair (k->v) + || build|()|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<Value>|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. + ||clear|()|O(1)|Clear all data + ||reset|(size_t dimension)|O(1)|Clear all data and then + set the this->dimension be `dimension` + |======================================================================= +NOTE: O(kN ^1-1/k^ ) is reference from wiki. + +`query()` and `rangeQuery()` will run `build()` first if you called `insert()` +before call them. And `build()` is very slow, so you should not use this class +as a dynamic tree + +''' +@asciidoc- + *********************************************************/ } #include "KD_Tree.hpp" diff --git a/meowpp/dsa/MergeableHeap.hpp b/meowpp/dsa/MergeableHeap.hpp index de3aea9..6e49a1c 100644 --- a/meowpp/dsa/MergeableHeap.hpp +++ b/meowpp/dsa/MergeableHeap.hpp @@ -1,6 +1,3 @@ -// @class name : MergeableHeap -// @implement : Leftist Tree - #include <cstdlib> namespace meow{ diff --git a/meowpp/dsa/SegmentTree.h b/meowpp/dsa/SegmentTree.h new file mode 100644 index 0000000..1aa396d --- /dev/null +++ b/meowpp/dsa/SegmentTree.h @@ -0,0 +1,92 @@ +#ifndef SegmentTree_H__ +#define SegmentTree_H__ + +namespace meow{ + template<class Value> + class SegmentTree{ + private: + struct Node{ + Value _value; + Value _offset; + bool _sameFlag; + // + Node(); + }; + // + size_t _size; + std::vector<Node> _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, + size_t __index); + bool rangeCorrect(ssize_t* __first, ssize_t* __last) const; + public: + SegmentTree(); + SegmentTree(size_t __size); + SegmentTree(SegmentTree const& __tree2); + // + 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); + }; + /********************************************************* + @asciidoc + === meow:: *SegmentTree<Value>* (C++ class) + .Description + `SegmentTree` is a data structure that can maintain an array, and + support *range update* , *range query* + + .Template Request + * `Value` should has + ** `operator+(Value)` offset + ** `operator|(Value)` merge two nodes + ** `operator*(size_t)` ?? + + For example, if you want to maintain *range minimum* + + * `Value::operator+(Value v2)` will be `this->realValue + v2.realValue` + * `Value::operator|(Value v2)` will be `std::min(this->realValue, v2.realValue)` + * `Value::operator*(size_t n)` will be `this->realValue` + + If you want to maintain *range sum* + + * `Value::operator+(Value v2)` will be `this->realValue + v2.realValue` + * `Value::operator|(Value v2)` will be `this->realValue + v2.realValue)` + * `Value::operator*(size_t n)` will be `this->realValue * n` + + .Support methods + * N <- array size + [options="header",width="100%",cols="1>,1<s,3<,1<,1<,10<",grid="rows"] + |======================================================================= + |Const?|Name| Parameters| Return Type| Time Complexity| Description + ||reset|(size_t N)|void|O(1)| + Clear and reset the array size to N (from `0` to `N - 1`) + |const|query|(ssize_t __first, ssize_t __last)|Value|O(logN)| + Range query + ||override|(ssize_t __first, ssize_t __last, Value const& __value)|void| + O(logN)| Let the element in the array index from `__first` to `__last` + be `__value` + ||offset|(ssize_t __first, ssize_t __last, Value const& __value)|void| + O(logN)| Let the element in the array index from `__first` to `__last` + plus `__value` + |======================================================================= + +''' +@asciidoc- + *********************************************************/ +} + +#endif diff --git a/meowpp/dsa/SegmentTree.hpp b/meowpp/dsa/SegmentTree.hpp new file mode 100644 index 0000000..24efcdd --- /dev/null +++ b/meowpp/dsa/SegmentTree.hpp @@ -0,0 +1,172 @@ +#ifndef SegmentTree_H__ +#define SegmentTree_H__ + +namespace meow{ + template<class Value> + inline SegmentTree<Value>::Node::Node(){ } + + template<class Value> + inline size_t + SegmentTree<Value>::leftChild(size_t __parent) const { + return __parent * 2 + 1; + } + template<class Value> + inline size_t + SegmentTree<Value>::rightChild(size_t __parent) const { + return __parent * 2 + 2; + } + + template<class Value> + inline void + SegmentTree<Value>::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; + } + } + template<class Value> + inline void + SegmentTree<Value>::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); + }else{ + override(__l , mid, __L , mid, leftChild(__index), __value); + override(mid + 1, __r, mid + 1, __R, rightChild(__index), __value); + } + _nodes[__index]._value = ( _nodes[ leftChild(__index)]._value + | _nodes[rightChild(__index)]._value); + } + template<class Value> + inline void + SegmentTree<Value>::offset(size_t __l, size_t __r, + size_t __L, size_t __R, + size_t __index, Value const& __delta){ + 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; + } + 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); + } + _nodes[__index]._value = ( _nodes[ leftChild(__index)]._value + | _nodes[rightChild(__index)]._value); + } + template<class Value> + inline Value + SegmentTree<Value>::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; + } + 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; + } + } + template<class Value> + inline bool + SegmentTree<Value>::rangeCorrect(ssize_t* __first, ssize_t* __last) const{ + if(*__last < *__first){ + return false; + } + if(*__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<class Value> + inline + SegmentTree<Value>::SegmentTree(): _size(0), _root(0) { + } + template<class Value> + inline + SegmentTree<Value>::SegmentTree(size_t __size): _size(0), _root(0){ + reset(__size); + } + template<class Value> + inline + SegmentTree<Value>::SegmentTree(SegmentTree const& __tree2): + _size(__tree2._size), _nodes(__tree2._nodes), _root(0){ } + // + template<class Value> + inline void + SegmentTree<Value>::reset(size_t __size){ + _size = __size; + _nodes.resize(__size * 4); + _nodes[_root]._sameFlag = true; + _nodes[_root]._value = Value(0); + } + template<class Value> + inline Value + SegmentTree<Value>::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); + } + template<class Value> + inline void + SegmentTree<Value>::override(ssize_t __first, ssize_t __last, + Value const& __value){ + if(rangeCorrect(&__first, &__last) == false){ + return ; + } + override(__first, __last, 0, _size - 1, _root, __value); + } + template<class Value> + inline void + SegmentTree<Value>::offset(ssize_t __first, ssize_t __last, + Value const& __delta){ + if(rangeCorrect(&__first, &__last) == false){ + return ; + } + offset(__first, __last, 0, _size - 1, _root, __delta); + } +} + +#endif diff --git a/meowpp/dsa/SplayTree.h b/meowpp/dsa/SplayTree.h index 78b54f6..3d2d2e3 100644 --- a/meowpp/dsa/SplayTree.h +++ b/meowpp/dsa/SplayTree.h @@ -96,6 +96,81 @@ namespace meow{ // void print() const; }; + /********************************************************* + @asciidoc + === meow:: *SplayTree<Key, Value>* (C++ class) + .Description + Like `std::map`, `SplayTree` is an dictionary(key->value). But it has + some extra method, such as `split()`, `merge()`, `keyOffset()`. + + .Data Type + * `Key` is the tyepname of the key + * `Value` is the typename of value + * `SplayTree<Key, Value>:: *Element* ` is a typename which contain + (key->value). It has some methods below: + ** `->first ` a constant reference to `Key` + ** `->second` a reference to `Value` + ** `operator==, operator!=` compare function, check if the two `Element` + is pointer to the same (key->value) + + .Template Request + * `Key` should has `operator<`, `operator+` + + .Support Methods + * N <- numbers of element in the SplayTree + * M <- numbers of element in another SplayTree + [options="header",width="100%",cols="1>,1<s,5<,1<,3^,10<",grid="rows"] + |======================================================================= + |Const?|Name| Parameters| Return Type| Time Complexity| Description + ||operator=|(SplayTree const&)| *this | O(N) | copy operator + ||moveTo|(SplayTree* t)|void|O(M)| Transform the data in this to `t` + |const|lowerBound|(Key k)|Element|O(logN)| Find the smallest (key->value) + which `k <= key` and return + |const|upperBound|(Key k)|Element|O(logN)| Find the smallest (key->value) + which `k < key` and return + |const|rLowerBound|(Key k)|Element|O(logN)| Find the largest (key->value) + which `key <= k` and return + |const|rUpperBound|(Key k)|Element|O(logN)| Find the largest (key->value) + which `key < k` and return + |const| find|(Key k)|Element|O(logN)| Find the element (key->value) which + `key == k` and return + |const|order|(size_t k)|Element|O(logN)| Find the `k`-th small element. + note that `k` start from zero like a normal C/C++ array. + |const|first|()|Element|O(logN)| Return the smallest element + |const|last|()|Element|O(logN)| Return the largest element + |const|end|()|Element|O(1)|Return an empty element(it can be use to + check if `find()` is successful) + |const|size|()|size_t|O(1)| Return number of elements in the tree + |const|empty|()|bool|O(1)|Return whether the tree is empty + ||clear|()|void|O(N)|Clear + ||keyOffset|(Key offset)|void|O(1)| Let all the keys in the tree + plus offset + ||insert|(Key k, Value v)|bool | O(logN)| Insert an element. + If the tree already has an element with same key, return `false`. + ||erase|(Key k)|bool | O(logN)|Erase an element from the tree with + given key. Return `false` if the element not found. + ||operator[]|(Key k)|Value|O(logN)|Like `find()` , but it will insert an element + automatic if the corrosponding element not found + ||splitOut|(Key const& upper_bound, + + SplayTree* out)|void | O(log N) | Split out all the elements with key + larger than `upper_bound` and store then into `out` + ||mergeAfter|(SplayTree* t)|bool|O(logN + logM)|If not all of the elements in this + are smaller than elements in `t`, return `false` , else merge `t` into + itself and return `true`. + ||merge|(SplayTree* t)|bool|O(logN + logM)|If all of the elements in this + are smaller than elements in `t` or all of the elements in this larger than + elements in `t` , merge `t` into itself and return `true`. + Else return `false` + |======================================================================= +WARNING: Consider there are two SplayTree `A` and `B`. + +`B` will become empty after you call `A.mergeAfter(&B)` +or `A.merge(&B)` successful. + +The data in `B` will override by data in `A` and `A` will become empty after +you call `A.moveTo(&B)` + +''' +@asciidoc- + *********************************************************/ } #include "SplayTree.hpp" |