diff options
Diffstat (limited to 'README.asciidoc')
| -rw-r--r-- | README.asciidoc | 600 |
1 files changed, 339 insertions, 261 deletions
diff --git a/README.asciidoc b/README.asciidoc index d64ab13..9998a00 100644 --- a/README.asciidoc +++ b/README.asciidoc @@ -2,33 +2,35 @@ == Description -一個不需要, 也不建議先compile成obj files的templates. +一個不需要, 也不應該先compile成obj files的templates. -TIP: *README.html* is more beautiful. +.Links +* https://github.com/cathook/meow[GitHub] +* http://www.csie.ntu.edu.tw/~b01902109/readme/template_meow/README.html[README.html] == File Tree === *meowpp/* C++ templates -[width="90%"] * *utility.h* some useful functions, - `stringPringf()` , `stringReplace` , `cstringEndWith` , + `stringPringf()` , `stringReplace()` , `cstringEndWith()` , `debugPrintf()` , `messagePrintf()` , `constant PI` , - `noEPS()` , `normalize()` , `denormalize` , - `ratioMapping` , `inRange()` , `squ()` , `average()` + `noEPS()` , `normalize()` , `denormalize()` , + `ratioMapping()` , `inRange()` , `squ()` , `average()` * *Usage.h* `class Usage` * *colors/* Color splces and transformer ** *RGB.h* `class RGBi` , `class RGBf` -** *YUV.h* `class YUVi` , `class YUVf` , `RGB_to_YUV()` , `YUV_to_RGB` -** *HSL.h* `class HSLf` , `RGB_to_HSL()` , `HSL_to_RGB` , - `YUV_to_HSL()` , `HSL_to_YUV` -** *HSV.h* `class HSVf` , `RGB_to_HSV()` , `HSV_to_RGB` , - `YUV_to_HSV()` , `HSV_to_YUV` , - `HSL_to_HSV()` , `HSV_to_HSL` +** *YUV.h* `class YUVi` , `class YUVf` , `RGB_to_YUV()` , `YUV_to_RGB()` +** *HSL.h* `class HSLf` , `RGB_to_HSL()` , `HSL_to_RGB()` , + `YUV_to_HSL()` , `HSL_to_YUV()` +** *HSV.h* `class HSVf` , `RGB_to_HSV()` , `HSV_to_RGB()` , + `YUV_to_HSV()` , `HSV_to_YUV()` , + `HSL_to_HSV()` , `HSV_to_HSL()` * *dsa/* Data Structures and Algorithms ** *DisjointSet.h* `class DisjointSet` -** *Heaps.h* `class MergeableHeap` -** *KD_Tree.h* `class KD_Tree` -** *SplayTree.h* `class SplayTree` +** *Heaps.h* `class MergeableHeap<Element>` +** *KD_Tree.h* `class KD_Tree<Vector, Scalar>` +** *SegemenTree.h* `class SegmentTree<Value>` +** *SplayTree.h* `class SplayTree<Key, Value>` * *oo/* ** *Register_Implement.h* `class RegisterInterface` , `class ImplementInterface` @@ -36,58 +38,64 @@ TIP: *README.html* is more beautiful. == Structures/Classes/Functions +:b: | === meow:: *Functios* in utility.h [options="header",width="100%",cols="1>s,5<,1<,10<",grid="rows"] |============================================================== -|Name | Parameters | Return Type | Description -|stringPrintf |(char const * fmt, ...)|std::string | -Format print to C++ string and return it -|stringReplace |(std::string str, + -std::string const& from, + -std::string const& to) | std::string | -Return a string like `str`, but all `from` be replaced by `to` -|cstringEndWith |(char const* str, int n, ...) | bool | -Return whether `str` is end with one of the c-string you specify in +|Name | Parameters | Return_Type | Description +|stringPrintf |(char const * `fmt`, ...) | std::string +|Format print to C++ string and return it +|stringReplace |(std::string `str`, + + +std::string const& `from`, + + +std::string const& `to`) | std::string +|Return a string like `str`, but all `from` be replaced by `to` +|cstringEndWith |(char const* `str`, + +int `n`, ...) | bool +|Return whether `str` is end with one of the c-string you specify in the parameters or not -|debugPrintf |(char const* fmt, ...) | void| -Print debug message (file name, line number, ...etc) when `DEBUG` is +|debugPrintf |(char const* `fmt`, ...) | void +|Print debug message (file name, line number, ...etc) when `DEBUG` is defined -|messagePrintf |(int level_change, char const* fmt, ...) | void| -階層式的訊息輸出 -|noEPS |(double value, double eps = 1e-9) | double | +|messagePrintf |(int `level_change`, + +char const* `fmt`, ...) | void +|階層式的訊息輸出 +|noEPS |(double `value`, double `eps` = 1e-9) | double | 如果abs(輸入的數值) < eps, 則回傳0, 否則回傳輸入的數值 -|normalize |(double lower, double upper, + -double value) | double | -(value - lower) / (upper - lower) -|denormalize |(double lower, double upper, + -double ratio) | double | -lower + (upper - lower) * ratio -|ratioMapping |(double l1, double u1, + -double m1, double l2, + -double u2) -| double | -denormalize(l2, u2, normalize(l1, u1, m1)) -|inRange<T> |(T const& mn, T const& mx, + -T const& v) | T | -std::max(mn, std::min(mx, v)) -|squ<T> |(T const& x) | T| -x * x -|average<T>|(T const& beg, T const& end, + -double sigs)| T| +|normalize |(double `lower`, double `upper`, + + double value) +| double | `(value - lower) / (upper - lower)` +|denormalize |(double `lower`, double `upper`, + + + double `ratio`) | double | `lower + (upper - lower) * ratio` +|ratioMapping |(double `l1`, double `u1`, + + +double `m1`, double `l2`, + +double `u2`) +| double | `denormalize(l2, u2, normalize(l1, u1, m1))` +|inRange<T> |(T const& `mn`, T const& `mx`, + + T const& `v`) | T | +`std::max(mn, std::min(mx, v))` +|squ<T> |(T const& `x`) | T| `x * x` +|average<T>|(T const& `beg`, T const& `end`, + + double `sigs`)| T| 只將 `sigs` 個標準差以內的數據拿來取平均 -|average<T>|(T const& beg, T const& end, + -T const& p, double sigs)| T| -同上, 不過這次用 `p` 來加權平均 +|average<T>|(T const& `beg`, T const& `end`, + + + T const& `p`, double `sigs`)| T| 同上, 不過這次用 `p` 來加權平均 |============================================================== [NOTE] -`stringReplace()` 不是用什麼好方法寫的因此執行效率很低請別虐待它. + -額外附贈一個 `const double PI = 3.141592653589......` +==================================== +* `stringReplace()` 不是用什麼好方法寫的因此執行效率很低請別虐待它. +* 額外附贈一個 `const double PI = 3.141592653589......` +==================================== ''' === meow:: *Usage* (C++ Class) -.Description +==== Description `Usage` 是用來分析argc, argv和輸出usage document的class. argc, argv的部份, 有以下規則 @@ -97,7 +105,7 @@ argc, argv的部份, 有以下規則 反之則一定要設定. 另外可以給定value的預設值以及哪些value是可接受的 * `<value>` 其他, 一律視為process arguments -.Methods +==== Methods * `Usage(String const& _name)` + 建構子, 所有說明文字中 *<name>* 都會被代換成 `_name` * `Usage()` + @@ -115,8 +123,8 @@ String const& value_type, String const& value_default, bool must)` + " *是否一定要設定此參數* " , 回傳表成功與否 *(bool)* * `addOptionValueAccept(unsigned char option, String const& value, String const& description)` + -針對某個option, 新增一個可接受的額外選項 (如果某個option從頭到尾都沒有 -新增可接受的選項, 則視為不限制), 回傳成功與否 *(bool)* +針對某個option, 新增一個可接受的額外選項 (如果某個option從頭到尾都 +沒有新增可接受的選項, 則視為不限制), 回傳成功與否 *(bool)* * `hasOptionSetup(unsigned char option)` + 回傳是否有此選項 *(bool)* * `getOptionValuesCount(unsigned char option)` + @@ -139,9 +147,12 @@ String const& value, String const& description)` + 輸入argv, argc, 回傳是否沒有錯誤發生 *(bool)* , 其中如果有錯誤發生, 且 `errmsg != NULL` 則會將錯誤訊息寫入之 -NOTE: `String` 是 `std::string` . + -`Strings` 是 `std::vector< std::string> >`. + -如果沒有寫回傳什麼, 就是回傳 `void` +[NOTE] +================================== +* `String` 是 `std::string` . +* `Strings` 是 `std::vector< std::string> >`. +* 如果沒有寫回傳什麼, 就是回傳 `void` +================================== ''' @@ -163,220 +174,287 @@ which will return the pointer to the corresponding class. ''' === 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. +==== Description +`DisjointSet` 是個*輕量級Data Dtructure*, 用來維護一堆互斥集的資訊. +相關資料可參考 +link:http://www.csie.ntnu.edu.tw/~u91029/DisjointSets.html[演算法筆記] + +==== Support Methods + +[options="header",width="100%",cols="1>m,3>s,7<,3<,3^,20<",grid="rows"] +|===================================================================== +|Const?|Name | Parameters | Return_Type| Time_Complexity| Description +|const |root |(size_t `number`) | size_t | very fast +|回傳 `number` 所在的 *集合的編號* (0~N-1) +|const |size |() | size_t | very fast +|回傳 *總集合大小* +| |reset|(size_t `N`) | void | O(N) +| 清空, 並且設定總集合大小為 `N` +| |merge|(size_t `number1`, + +size_t `number2`)| size_t | very fast +| 將 `number1` 所在的集合 跟 `number2` 所在的集合 *合併*, +並回傳合併後新的集合的編號 +|===================================================================== + +[NOTE] +======================================== +* *very fast* 表示它算的真的超級快, 可以視為常數時間. +* 預設值所有 `number` 所在的集合的編號就是 `number` 本身, +即沒有任兩個數在同一個set裡面 +======================================== ''' -=== 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)` +=== meow:: *MergeableHeap<Element>* (C++ class) +==== Description +一個用 *左偏樹* 實作的 *Maximum-Heap* , 除了原本heap有的功能外, +還支援 `merge`, `split` 等功能 + +==== Template Class Operators Request +[options="header",width="70%",cols="1>m,1<,3<s,5<,3<,15<",grid="rows"] +|===================================================================== +|Const?|Typename| Operator | Parameters | Return_Type| Description +|const |Element |operator< |(Element `v`)| bool | 大小比較 +|===================================================================== + +==== Support Methods + +* N <- `this` 中擁有的資料數 + +[options="header",width="100%",cols="1>m,2>s,7<,3<,3^,20<",grid="rows"] +|===================================================================== +|Const?|Name | Parameters | Return_Type| Time_Complexity| Description +||moveTo|(MergeableHeap* `h`)|void|O(M) +|將 `this` 的資料複寫到 `h` 上面, 同時清空自己, +時間複雜度中的M是 `h` 所擁有的資料數 +|const|top|()|Element const&|O(1) +|回傳最大的那個 `Element` +|const|size|()|size_t|O(1) +|回傳 `this` 中擁有的資料數 +|const|empty|()|bool|O(1) +|回傳 `this` 是否為空 +||push|(Element const& `e`)|void|O(logN) +|將 `e` 加入 +||pop|()|void|O(logN) +|將最大的 `Element` 移除 +||clear|()|void|O(N) +|將資料清空 +||merge|(MergeableHeap* `heap2`)|void|O(logN+logM) +|將 `heap2` 的資料統統加到 `this` 中, 並且清空 `heap2` +時間複雜度中的M是 `heap2` 的資料數 +|============================================== +[WARNING] +============================================== +* 假設現在有兩個MergeableHeap `A` 和 `B`, 則: +** 執行 `A.merge(&B)` 後 `B` 會變成空的 +** 執行 `B.moveTo(&A)` 後 `B` 會變成空的, `A` 原本擁有的資料也會覆蓋掉 +============================================== ''' + === meow:: *KD_Tree<Vector, Scalar>* (C++ class) -.Description -`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<Vector> -[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|(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|(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` -|======================================================================= -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 +==== Description +`KD_Tree` 全名k-dimension tree, 用來維護由 *N個K維度向量所成的集合*, +並可於該set中查找 *前i個離給定向量最接近的向量* + +==== Template Class Operators Request +[options="header",width="70%",cols="1>m,1<,3<s,5<,3<,15<",grid="rows"] +|===================================================================== +|Const?|Typename| Operator | Parameters | Return_Type| Description +|const | Vector|operator[] |(size_t `n`) | Scalar | 取得第 `n` 維度量 +|const | Vector|operator< |(Vector `v`) | bool | 權重比較 +|const | Scalar|operator* |(Scalar `s`) | Scalar | 相乘 +|const | Scalar|operator+ |(Scalar `s`) | Scalar | 相加 +|const | Scalar|operator- |(Scalar `s`) | Scalar | 相差 +|const | Scalar|operator< |(Scalar `s`) | bool | 大小比較 +|===================================================================== + +==== Custom Type Definitions +* `Vectors` <- `std::vector<Vector>` + +==== Support Methods + +* N <- `this` 中擁有的資料數 +* K <- `this` 資料維度 + +[options="header",width="100%",cols="1>m,3>s,7<,3<,3^,20<",grid="rows"] +|===================================================================== +|Const?|Name | Parameters | Return_Type| Time_Complexity| Description +||insert|(Vector const& `v`)|void| O(1) +|將向量 `v` 加到set中 +||erase|(Vector const& `v`)|bool| O(N) +|將向量 `v` 從set中移除, '~TODO:可以再優化~' +||build|()|void|O(KN logN) or O(1) +|檢查距上一次 `build()` 至今是否有 `insert/erase` 被呼叫, +若有, 重新建樹, 否則不做事 +||forceBuild|()|void|O(KN logN) +|重新建樹 +|const|query|(Vector const& `v`, + +size_t `i`, + +bool `cmp`)|Vectors +|O(KN ^1-1/K^ ) +|於set中找尋距離 `v` 前 `i` 近的向量, 並依照由近而遠的順序排序. +如果有兩個向量 `v1`,`v2` 距離一樣, 且 `cmp` 為 `true` , 則直接依照 +`v1 < v2` 來決定誰在前面. 最後回傳一陣列包含所有解. +||clear|()|void|O(1) +|清空所有資料 +||reset|(size_t `dimension`)|void|O(1) +|清空所有資料並且指定維度為 `dimension` +|===================================================================== + +[NOTE] +======================================== +* 此資料結構只有在 N >> 2 ^K^ 時才比較有優勢, +當 K 逐漸變大時, 所花時間會跟暴搜沒兩樣 +======================================== ''' === 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)` +==== Description +`SplayTree` 是一種神乎其技的資料結構, 維護一堆 Key->Value . 並且支援 +一些 `std::map` 難以快速實踐的操作, 如 `split` , `merge` , `keyOffset` + +==== Template Class Operators Request +[options="header",width="70%",cols="1>m,1<,3<s,5<,3<,15<",grid="rows"] +|===================================================================== +|Const?|Typename| Operator| Parameters | Return_Type| Description +|const |Key |operator+|(Key `k`) | Key | 相加 +|const |Key |operator<|(Key `k`) | bool | 大小比較 +| |Key |'Key' |(int `n`) | | 建構子, `n` 永遠是0 +| |Value | 'Value' |( ) | | 建構子 +|===================================================================== + +==== Custom Type Definitions + +* `Element` -> 用來當作回傳資料的媒介 +** 重定義 `operator->()` 到 `std::pair<Key const&, Value&>*` +** 重定義 `operator*()` 到 `std::pair<Key const&, Value&>&` +** 有 `operator==` , `operator!=`, `operator=` 可用 +** 可以直接用 `(*e).second = some_value` 來改變SplayTree中的資料 + +==== Support Methods + +* N <- `this` 中擁有的資料數 +* M <- `tree2` 中擁有的資料數 + +[options="header",width="100%",cols="1>m,3>s,7<,3<,3^,20<",grid="rows"] +|===================================================================== +|Const?|Name | Parameters | Return_Type| Time_Complexity| Description +||moveTo|(SplayTree* `tree2`)|void|O(M) +|將 `this` 的資料複寫到 `tree2` 上面, 同時清空自己, +時間複雜度中的M是 `tree2` 所擁有的資料數 +|const|lowerBound|(Key const& `k`)|Element|O(logN) +|找出第一個(最小的) Element且 `k` <= 它的 Key, 並且回傳之. +找不到的話回傳 `this->end()` +|const|lowerBound|(Key const& `k`)|Element|O(logN) +|找出第一個(最小的) Element且 `k` < 它的 Key, 並且回傳之. +找不到的話回傳 `this->end()` +|const|lowerBound|(Key const& `k`)|Element|O(logN) +|找出第一個(最小的) Element且 `k` >= 它的 Key, 並且回傳之. +找不到的話回傳 `this->end()` +|const|lowerBound|(Key const& `k`)|Element|O(logN) +|找出第一個(最小的) Element且 `k` > 它的 Key, 並且回傳之. +找不到的話回傳 `this->end()` +|const|find|(Key const& `k`)|Element|O(logN) +|找出 Key= `k` 的Elemenet 並回傳. 找不到的話回傳 `this->end()` +|const|order|(size_t `ord`)|Element|O(logN) +|將Elements依照Key由小到大排序, 回傳第 `ord` 個Element (由0算起). +其中如果 `ord` > N - 1, 則會回傳 `this->last()` +|const|first|(size_t `ord`)|Element|O(logN) +|回傳Key最小的Element, 如果SplayTree為空, 則回傳 `this->end()` +|const|last|(size_t `ord`)|Element|O(logN) +|回傳Key最大的Element, 如果SplayTree為空, 則回傳 `this->end()` +|const|end|()|Element|O(1) +|回傳一個指向NULL的Element, 以供 `find` , `order` , `first` +, `last` 等判斷是否有找到相對應的Element +|const|size|()|size_t|O(1)| 回傳資料數 +|const|size|()|bool|O(1)| 回傳是否為空 +||clear|()|void|O(N)| 清空資料 +||keyOffset|(Key const& `delta`)|void|O(1) +|將所有Element的Key同加上 `delta` +||insert|(Key const& `key`, + +Value const& `value`)|bool|O(logN) +|檢查是否已有Element的Key 為 `key`, 若有則回傳 `false` , 否則將 +一個 (Key -> Value) = (`key` -> `value`)的Element加入, 並回傳 `true` +將所有Element的Key同加上 `delta` +||erase|(Key const& `key`)|bool|O(logN) +|檢查是否已有Element的Key 為 `key`, 若有則刪除之, 並回傳 `true`, +否則則回傳 `false` +||operator[]|(Key const& `key`)|Value&|O(logN) +|檢查是否已有Element的Key 為 `key`, 若有則回傳相對應的Value的Reference +否則先執行 `insert(key, Value())` 再回傳相對應的Reference +||splitOut|(Key const& `upper_bound`, + +SplayTree* `tree2`)|void +|O(logN) + O(M) +|將 `tree2` 清空, 再將所有Key > `upper_bound` 的Element都丟到 `tree2` +||mergeAfter|(SplayTree* `tree2`)|void|O(logN) + O(logM) +|檢查是否 `this` 中的 Key 都小於 `tree2` 中的Key, 是的話把 `tree2` +中的 Element 都搬到 `this` , 同時清空 `tree2` , 回傳 `true`. 否則 +回傳 `false` +||merge|(SplayTree* `tree2`)|void|O(logN) + O(logM) +|檢查是否 `this` 中的 Key 都小於 `tree2` 中的Key 或者 +是否 `this` 中的 Key 都大於 `tree2` 中的Key, 是的話把 `tree2` +中的 Element 都搬到 `this` , 同時清空 `tree2` , 回傳 `true`. 否則 +回傳 `false` +|===================================================================== + +[NOTE] +======================================== +* 假設現在有兩個SplayTree `A` 和 `B`, 則: +** 執行 `B.moveTo(&A)` 後 `B` 會變成空的, `A` 原本擁有的資料也會覆蓋掉 +** 執行 `A.merge(&B)` 或 `A.mergeAfter(&B)` 後 +如果檢查發現確實可以merge, 則之後 `B` 會變成空的 +======================================== ''' -=== 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` -|======================================================================= -''' +=== meow:: *SegmentTree<Value>* (C++ class) +==== Description +維護一個陣列, 並且讓user可以有區間查詢, 區間修改的小東東 + +==== Template Class Operators Request +[options="header",width="70%",cols="1>m,1<,3<s,5<,3<,15<",grid="rows"] +|===================================================================== +|Const?|Typename| Operator | Parameters |Return_Type| Description +|const |Value |operator+ |(Value `v`)|Value | 相加(位移) +|const |Value |operator* |(size_t `n`)|Value | 每個Value都一樣, +長為 `n` 的區間的值 +|const |Value |operator{b}|(Value `v`)|Value | 區間合併後的值 +|===================================================================== + +* 若要維護區間最小值, 即每次都是詢問範圍 `[a, b]` 的最小值, 則可以定義 +** `operator+` 為 '回傳相加值' +** `operator*` 為 '回傳*this' +** `operator|` 為 '回傳std::min(*this, v)' +* 若要維護區間最總和, 即每次都是詢問範圍 `[a, b]` 的總和, 則可以定義 +** `operator+` 為 '回傳相加值' +** `operator*` 為 '回傳(*this) * n' +** `operator|` 為 '回傳相加值' + +==== Support Methods + +* N <- `this` 所維護的陣列長度 + +[options="header",width="100%",cols="1>m,2>s,7<,3<,3^,20<",grid="rows"] +|===================================================================== +|Const?|Name | Parameters | Return_Type| Time_Complexity| Description +||reset|(size_t `size`)|void|O(1) +|將資料清空且設定維護範圍是 `0~size - 1` 其中時間複雜度確切多少未知 +要看 `std::vector::resize()` 的效率 +|const|query|(ssize_t `first`, + +ssize_t `last`)|Value|O(logN) +|回傳區間 `[first,last]` (邊界都含) 的區間值 +||override|(ssize_t `first`, + +ssize_t `last`, + +Value const& `value`) +|void|O(logN) +|將區間 `[first,last]` 全部都設定成 `value` +||offset|(ssize_t `first`, + +ssize_t `last`, + +Value const& `delta`) +|void|O(logN) +|將區間 `[first,last]` 全部都加上 `delta` +|============================================== |