diff options
Diffstat (limited to 'meowpp/dsa/SplayTree.h')
| -rw-r--r-- | meowpp/dsa/SplayTree.h | 75 |
1 files changed, 75 insertions, 0 deletions
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" |