From a18df7f42f62932001cbb1c61c458abaf5d8bace Mon Sep 17 00:00:00 2001 From: cathook Date: Tue, 22 Apr 2014 02:22:21 +0800 Subject: 重寫readme MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit --- README.asciidoc | 600 ++++++++++++--------- README.html | 1192 ++++++++++++++++++++++++++---------------- description.asciidoc | 34 +- meowpp/Usage.h | 123 +++-- meowpp/dsa/DisjointSet.h | 71 ++- meowpp/dsa/KD_Tree.h | 120 +++-- meowpp/dsa/MergeableHeap.h | 131 +++-- meowpp/dsa/MergeableHeap.hpp | 2 +- meowpp/dsa/SegmentTree.h | 100 ++-- meowpp/dsa/SplayTree.h | 241 +++++---- meowpp/dsa/SplayTree.hpp | 2 +- meowpp/utility.h | 121 +++-- readme_generate.py | 52 +- 13 files changed, 1670 insertions(+), 1119 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` +** *KD_Tree.h* `class KD_Tree` +** *SegemenTree.h* `class SegmentTree` +** *SplayTree.h* `class SplayTree` * *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 const& mn, T const& mx, + -T const& v) | T | -std::max(mn, std::min(mx, v)) -|squ |(T const& x) | T| -x * x -|average|(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 const& `mn`, T const& `mx`, + + T const& `v`) | T | +`std::max(mn, std::min(mx, v))` +|squ |(T const& `x`) | T| `x * x` +|average|(T const& `beg`, T const& `end`, + + double `sigs`)| T| 只將 `sigs` 個標準差以內的數據拿來取平均 -|average|(T const& beg, T const& end, + -T const& p, double sigs)| T| -同上, 不過這次用 `p` 來加權平均 +|average|(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是可接受的 * `` 其他, 一律視為process arguments -.Methods +==== Methods * `Usage(String const& _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* (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>,1data 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* (C++ class) +==== Description +一個用 *左偏樹* 實作的 *Maximum-Heap* , 除了原本heap有的功能外, +還支援 `merge`, `split` 等功能 + +==== Template Class Operators Request +[options="header",width="70%",cols="1>m,1<,3* (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 -[options="header",width="100%",cols="1>,1dimension 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` + +==== 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* (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:: *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>,1value) -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 用來當作回傳資料的媒介 +** 重定義 `operator->()` 到 `std::pair*` +** 重定義 `operator*()` 到 `std::pair&` +** 有 `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* (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* (C++ class) +==== Description +維護一個陣列, 並且讓user可以有區間查詢, 區間修改的小東東 + +==== Template Class Operators Request +[options="header",width="70%",cols="1>m,1<,3 ul > li { list-style-type: square; @@ -685,15 +685,19 @@ asciidoc.install(2);

Description

-

一個不需要, 也不建議先compile成obj files的templates.

-
- - - -
-
Tip
-		README.html is more beautiful.
-
+

一個不需要, 也不應該先compile成obj files的templates.

+
Links
@@ -705,10 +709,10 @@ asciidoc.install(2);

  • 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()

  • @@ -728,20 +732,20 @@ asciidoc.install(2);

  • -YUV.h class YUVi , class YUVf , RGB_to_YUV() , YUV_to_RGB +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 +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 +HSV.h class HSVf , RGB_to_HSV() , HSV_to_RGB() , + YUV_to_HSV() , HSV_to_YUV() , + HSL_to_HSV() , HSV_to_HSL()

    • @@ -758,17 +762,22 @@ asciidoc.install(2);

  • -Heaps.h class MergeableHeap +Heaps.h class MergeableHeap<Element> +

    +
    • +
  • +

    +KD_Tree.h class KD_Tree<Vector, Scalar>

  • -KD_Tree.h class KD_Tree +SegemenTree.h class SegmentTree<Value>

  • -SplayTree.h class SplayTree +SplayTree.h class SplayTree<Key, Value>

    • @@ -805,99 +814,104 @@ width:100%; -Name - Parameters - Return Type +Name + Parameters + Return_Type Description

    stringPrintf

    -

    (char const * fmt, …)

    +

    (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 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, …)

    +

    (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, …)

    +

    (char const* fmt, …)

    void

    Print debug message (file name, line number, …etc) when DEBUG is defined

    messagePrintf

    -

    (int level_change, char const* fmt, …)

    +

    (int level_change,
    +char const* fmt, …)

    void

    階層式的訊息輸出

    noEPS

    -

    (double value, double eps = 1e-9)

    +

    (double value, double eps = 1e-9)

    double

    如果abs(輸入的數值) < eps, 則回傳0, 否則回傳輸入的數值

    normalize

    -

    (double lower, double upper,
    -double value)

    +

    (double lower, double upper,
    + double value)

    double

    -

    (value - lower) / (upper - lower)

    +

    (value - lower) / (upper - lower)

    denormalize

    -

    (double lower, double upper,
    -double ratio)

    +

    (double lower, double upper, +
    + double ratio)

    double

    -

    lower + (upper - lower) * ratio

    +

    lower + (upper - lower) * ratio

    ratioMapping

    -

    (double l1, double u1,
    -double m1, double l2,
    -double u2)

    +

    (double l1, double u1, +
    +double m1, double l2,
    +double u2)

    double

    -

    denormalize(l2, u2, normalize(l1, u1, m1))

    +

    denormalize(l2, u2, normalize(l1, u1, m1))

    inRange<T>

    -

    (T const& mn, T const& mx,
    -T const& v)

    +

    (T const& mn, T const& mx,
    + T const& v)

    T

    -

    std::max(mn, std::min(mx, v))

    +

    std::max(mn, std::min(mx, v))

    squ<T>

    -

    (T const& x)

    +

    (T const& x)

    T

    -

    x * x

    +

    x * x

    average<T>

    -

    (T const& beg, T const& end,
    -double sigs)

    +

    (T const& beg, T const& end,
    + double sigs)

    T

    只將 sigs 個標準差以內的數據拿來取平均

    average<T>

    -

    (T const& beg, T const& end,
    -T const& p, double sigs)

    +

    (T const& beg, T const& end, +
    + T const& p, double sigs)

    T

    同上, 不過這次用 p 來加權平均

    @@ -908,15 +922,29 @@ T const& p, double sigs)

    Note
    -stringReplace() 不是用什麼好方法寫的因此執行效率很低請別虐待它.
    -額外附贈一個 const double PI = 3.141592653589...... + +
      +
    • +

      +stringReplace() 不是用什麼好方法寫的因此執行效率很低請別虐待它. +

      +
      • +
    • +

      +額外附贈一個 const double PI = 3.141592653589...... +

      +
      • +
    +

    meow:: Usage (C++ Class)

    -
    Description

    Usage 是用來分析argc, argv和輸出usage document的class. +

    +

    Description

    +

    Usage 是用來分析argc, argv和輸出usage document的class. argc, argv的部份, 有以下規則

    • @@ -937,7 +965,10 @@ argc, argv的部份, 有以下規則

    -
    Methods
      +
    +
    +

    Methods

    +

    • Usage(String const& _name)
      @@ -981,8 +1012,8 @@ String const& value_type, String const& value_default, bool must)

      addOptionValueAccept(unsigned char option, String const& value, String const& description)
      -針對某個option, 新增一個可接受的額外選項 (如果某個option從頭到尾都沒有 -新增可接受的選項, 則視為不限制), 回傳成功與否 (bool) +針對某個option, 新增一個可接受的額外選項 (如果某個option從頭到尾都 +沒有新增可接受的選項, 則視為不限制), 回傳成功與否 (bool)

    • @@ -1052,13 +1083,30 @@ String const& value, String const& description)
      Note
      -String 是 std::string .
      -Strings 是 std::vector< std::string> >.
      -如果沒有寫回傳什麼, 就是回傳 void + +
        +
      • +

        +String 是 std::string . +

        +
        • +
      • +

        +Strings 是 std::vector< std::string> >. +

        +
        • +
      • +

        +如果沒有寫回傳什麼, 就是回傳 void +

        +
        • +
      +
    +

    meow:: ImplementInterface/RegisterInterface (C++ Class)

    Description

    Assume there is a problem which can be solved by different algorithms. @@ -1090,62 +1138,68 @@ 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:

    +
    +

    Description

    +

    DisjointSet 是個輕量級Data Dtructure, 用來維護一堆互斥集的資訊. +相關資料可參考 +演算法筆記

    +
    +
    +

    Support Methods

    ------++++++ - - - - + + + + - - - + + + - - + + - - + + - - + + - - - + + + - - + + - - - + + + - - + +
    Const?Name Parameters Return Type Time ComplexityName Parameters Return_Type Time_Complexity Description

    const

    root

    (size_t number)

    const

    root

    (size_t number)

    size_t

    very fast

    Return the group id of the number given

    very fast

    回傳 number 所在的 集合的編號 (0~N-1)

    const

    size

    const

    size

    ()

    size_t

    very fast

    Return N

    very fast

    回傳 總集合大小

    reset

    (size_t N)

    reset

    (size_t N)

    void

    very fast

    Clean and initalize

    O(N)

    清空, 並且設定總集合大小為 N

    merge

    (size_t number1,
    -size_t number2)

    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

    very fast

    將 number1 所在的集合 跟 number2 所在的集合 合併, +並回傳合併後新的集合的編號
    @@ -1154,31 +1208,73 @@ Return the merged group id

    Note
    -very fast means that you can consider it as constant time. - -
    -
    -
    -
    -

    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< +very fast 表示它算的真的超級快, 可以視為常數時間.

        • -
      -
      Support methods

      • -N ← number of elements in the heap +預設值所有 number 所在的集合的編號就是 number 本身, +即沒有任兩個數在同一個set裡面

        • +
      + + +
    +
    +
    +
    +
    +

    meow:: MergeableHeap<Element> (C++ class)

    +
    +

    Description

    +

    一個用 左偏樹 實作的 Maximum-Heap , 除了原本heap有的功能外, +還支援 merge, split 等功能

    +
    +
    +

    Template Class Operators Request

    + +++++++ + + + + + + + + + + + + + + + + + + + +
    Const?Typename Operator Parameters Return_Type Description

    const

    Element

    operator<

    (Element v)

    bool

    大小比較

    +
    +
    +

    Support Methods

    +

    • -M ← number of elements in the other heap if need +N ← this 中擁有的資料數

    @@ -1186,94 +1282,88 @@ M ← number of elements in the other heap if need style=" width:100%; "> + - - - - - + + + + Const? -Name - Parameters - Return Type - Time Complexity +Name + Parameters + Return_Type + Time_Complexity Description -

    -

    operator=

    -

    (MergeableHeap const&)

    -

    *this

    -

    O(N)

    -

    Copy operator.

    - - -

    -

    moveTo

    -

    (MergeableHeap*)

    +

    +

    moveTo

    +

    (MergeableHeap* h)

    void

    -

    O(M)

    -

    Transform the this→data to the heap specified in parameters

    +

    O(M)

    +

    將 this 的資料複寫到 h 上面, 同時清空自己, +時間複雜度中的M是 h 所擁有的資料數

    -

    const

    -

    top

    +

    const

    +

    top

    ()

    -

    Element

    -

    O(1)

    -

    Return the maximum element in the heap.

    +

    Element const&

    +

    O(1)

    +

    回傳最大的那個 Element

    -

    const

    -

    size

    +

    const

    +

    size

    ()

    size_t

    -

    O(1)

    -

    Return the number of elements in the heap.

    +

    O(1)

    +

    回傳 this 中擁有的資料數

    -

    const

    -

    empty

    +

    const

    +

    empty

    ()

    bool

    -

    O(1)

    -

    Return whether the heap is empty or not.

    +

    O(1)

    +

    回傳 this 是否為空

    -

    -

    push

    -

    (Element)

    +

    +

    push

    +

    (Element const& e)

    void

    -

    O(log N)

    -

    Add a element into the heap

    +

    O(logN)

    +

    將 e 加入

    -

    -

    pop

    +

    +

    pop

    ()

    void

    -

    O(log N)

    -

    Delete the maximum element from the heap

    +

    O(logN)

    +

    將最大的 Element 移除

    -

    -

    merge

    -

    (MergeableHeap*)

    +

    +

    clear

    +

    ()

    void

    -

    O(log M)

    -

    Merge the specified MergeableHeap(with size=M) into itself

    +

    O(N)

    +

    將資料清空

    -

    -

    clear

    -

    ()

    +

    +

    merge

    +

    (MergeableHeap* heap2)

    void

    -

    O(N)

    -

    Delete all elements from the heap

    +

    O(logN+logM)

    +

    將 heap2 的資料統統加到 this 中, 並且清空 heap2 +時間複雜度中的M是 heap2 的資料數

    @@ -1282,51 +1372,134 @@ width:100%;
    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:: 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 +假設現在有兩個MergeableHeap A 和 B, 則:

        -
        • +

        • -Scalar should has operator*, operator+, operator< +執行 A.merge(&B) 後 B 會變成空的

          • -
        -
        Support Methods

        • -N ← numbers of element in the kd-tree +執行 B.moveTo(&A) 後 B 會變成空的, A 原本擁有的資料也會覆蓋掉

          • +
        + +
      + + +
    +
    +
    +
    +
    +

    meow:: KD_Tree<Vector, Scalar> (C++ class)

    +
    +

    Description

    +

    KD_Tree 全名k-dimension tree, 用來維護由 N個K維度向量所成的集合, +並可於該set中查找 前i個離給定向量最接近的向量

    +
    +
    +

    Template Class Operators Request

    + +++++++ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
    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

    +

    • -K ← dimensions +Vectors ← std::vector<Vector>

      • +
    +
    +
    +

    Support Methods

    +

    • -Vector is the tyepname of the vector +N ← this 中擁有的資料數

    • -Vectors is the typename of the std::vector<Vector> +K ← this 資料維度

    @@ -1334,82 +1507,83 @@ K ← dimensions style=" width:100%; "> - - - - - - + + + + + + Const? -Name - Parameters - Return Type - Time Complexity +Name + Parameters + Return_Type + Time_Complexity Description -

    const

    -

    root

    -

    (size_t number)

    -

    size_t

    -

    very fast

    -

    - - -

    -

    insert

    -

    (Vector const& v)

    +

    +

    insert

    +

    (Vector const& v)

    void

    -

    O(1)

    -

    Insert a vector

    +

    O(1)

    +

    將向量 v 加到set中

    -

    -

    erase

    -

    (Vector const& v)

    +

    +

    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==.

    +

    O(N)

    +

    將向量 v 從set中移除, TODO:可以再優化

    -

    -

    build

    +

    +

    build

    ()

    void

    -

    O(KN logN) if need

    -

    Build the data structure if need.

    +

    O(KN logN) or O(1)

    +

    檢查距上一次 build() 至今是否有 insert/erase 被呼叫, +若有, 重新建樹, 否則不做事

    -

    -

    forceBuild

    +

    +

    forceBuild

    ()

    void

    -

    O(KN logN)

    -

    Build the data structure(the insert() -method will not build the data structure immediately)

    +

    O(KN logN)

    +

    重新建樹

    -

    const

    -

    query

    -

    (Vector const& v, int k)

    +

    const

    +

    query

    +

    (Vector const& v,
    +size_t i,
    +bool cmp)

    Vectors

    -

    O(kN 1-1/k )

    -

    Using Euclidean-Distance to find the 1st to k-th nearest neighbor from v . -And return;

    +

    O(KN 1-1/K )

    +

    於set中找尋距離 v 前 i 近的向量, 並依照由近而遠的順序排序. +如果有兩個向量 v1,v2 距離一樣, 且 cmp 為 true , 則直接依照 +v1 < v2 來決定誰在前面. 最後回傳一陣列包含所有解.

    -

    -

    clear

    +

    +

    clear

    ()

    -

    O(1)

    -

    Clear all data

    -

    +

    void

    +

    O(1)

    +

    清空所有資料

    + + +

    +

    reset

    +

    (size_t dimension)

    +

    void

    +

    O(1)

    +

    清空所有資料並且指定維度為 dimension

    @@ -1418,70 +1592,129 @@ And return;

    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 + +
      +
    • +

      +此資料結構只有在 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
      +
      +

      Description

      +

      SplayTree 是一種神乎其技的資料結構, 維護一堆 Key→Value . 並且支援 +一些 std::map 難以快速實踐的操作, 如 split , merge , keyOffset

      +
      +
      +

      Template Class Operators Request

      + +++++++ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
      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

      +

      • -Key is the tyepname of the key +Element → 用來當作回傳資料的媒介

        -
        • +

        • -Value is the typename of value +重定義 operator->() 到 std::pair<Key const&, Value&>*

        • -`SplayTree<Key, Value>:: Element ` is a typename which contain -(key→value). It has some methods below: -

          -
            -
          • -

            -->first ` a constant reference to `Key +重定義 operator*() 到 std::pair<Key const&, Value&>&

          • -->second a reference to Value +有 operator== , operator!=, operator= 可用

          • -operator==, operator!= compare function, check if the two Element -is pointer to the same (key→value) +可以直接用 (*e).second = some_value 來改變SplayTree中的資料

        -
        Template Request
          -
        • -

          -Key should has operator<, operator+ -

          -
          • -
        -
        Support Methods
          +
        +
        +

        Support Methods

        +

        • -N ← numbers of element in the SplayTree +N ← this 中擁有的資料數

        • -M ← numbers of element in another SplayTree +M ← tree2 中擁有的資料數

        @@ -1489,293 +1722,344 @@ M ← numbers of element in another SplayTree style=" width:100%; "> - - - - - - + + + + + + Const? -Name - Parameters - Return Type - Time Complexity +Name + Parameters + Return_Type + Time_Complexity Description -

        -

        operator=

        -

        (SplayTree const&)

        -

        *this

        -

        O(N)

        -

        copy operator

        - - -

        -

        moveTo

        -

        (SplayTree* t)

        +

        +

        moveTo

        +

        (SplayTree* tree2)

        void

        O(M)

        -

        Transform the data in this to t

        +

        將 this 的資料複寫到 tree2 上面, 同時清空自己, +時間複雜度中的M是 tree2 所擁有的資料數

        -

        const

        -

        lowerBound

        -

        (Key k)

        +

        const

        +

        lowerBound

        +

        (Key const& k)

        Element

        O(logN)

        -

        Find the smallest (key→value) -which k <= key and return

        +

        找出第一個(最小的) Element且 k ⇐ 它的 Key, 並且回傳之. +找不到的話回傳 this->end()

        -

        const

        -

        upperBound

        -

        (Key k)

        +

        const

        +

        lowerBound

        +

        (Key const& k)

        Element

        O(logN)

        -

        Find the smallest (key→value) -which k < key and return

        +

        找出第一個(最小的) Element且 k < 它的 Key, 並且回傳之. +找不到的話回傳 this->end()

        -

        const

        -

        rLowerBound

        -

        (Key k)

        +

        const

        +

        lowerBound

        +

        (Key const& k)

        Element

        O(logN)

        -

        Find the largest (key→value) -which key <= k and return

        +

        找出第一個(最小的) Element且 k >= 它的 Key, 並且回傳之. +找不到的話回傳 this->end()

        -

        const

        -

        rUpperBound

        -

        (Key k)

        +

        const

        +

        lowerBound

        +

        (Key const& k)

        Element

        O(logN)

        -

        Find the largest (key→value) -which key < k and return

        +

        找出第一個(最小的) Element且 k > 它的 Key, 並且回傳之. +找不到的話回傳 this->end()

        -

        const

        -

        find

        -

        (Key k)

        +

        const

        +

        find

        +

        (Key const& k)

        Element

        O(logN)

        -

        Find the element (key→value) which -key == k and return

        +

        找出 Key= k 的Elemenet 並回傳. 找不到的話回傳 this->end()

        -

        const

        -

        order

        -

        (size_t k)

        +

        const

        +

        order

        +

        (size_t ord)

        Element

        O(logN)

        -

        Find the k-th small element. -note that k start from zero like a normal C/C++ array.

        +

        將Elements依照Key由小到大排序, 回傳第 ord 個Element (由0算起). +其中如果 ord > N - 1, 則會回傳 this->last()

        -

        const

        -

        first

        -

        ()

        +

        const

        +

        first

        +

        (size_t ord)

        Element

        O(logN)

        -

        Return the smallest element

        +

        回傳Key最小的Element, 如果SplayTree為空, 則回傳 this->end()

        -

        const

        -

        last

        -

        ()

        +

        const

        +

        last

        +

        (size_t ord)

        Element

        O(logN)

        -

        Return the largest element

        +

        回傳Key最大的Element, 如果SplayTree為空, 則回傳 this->end()

        -

        const

        -

        end

        +

        const

        +

        end

        ()

        Element

        O(1)

        -

        Return an empty element(it can be use to -check if find() is successful)

        +

        回傳一個指向NULL的Element, 以供 find , order , first +, last 等判斷是否有找到相對應的Element

        -

        const

        -

        size

        +

        const

        +

        size

        ()

        size_t

        O(1)

        -

        Return number of elements in the tree

        +

        回傳資料數

        -

        const

        -

        empty

        +

        const

        +

        size

        ()

        bool

        O(1)

        -

        Return whether the tree is empty

        +

        回傳是否為空

        -

        -

        clear

        +

        +

        clear

        ()

        void

        O(N)

        -

        Clear

        +

        清空資料

        -

        -

        keyOffset

        -

        (Key offset)

        +

        +

        keyOffset

        +

        (Key const& delta)

        void

        O(1)

        -

        Let all the keys in the tree -plus offset

        +

        將所有Element的Key同加上 delta

        -

        -

        insert

        -

        (Key k, Value v)

        +

        +

        insert

        +

        (Key const& key,
        +Value const& value)

        bool

        O(logN)

        -

        Insert an element. -If the tree already has an element with same key, return false.

        +

        檢查是否已有Element的Key 為 key, 若有則回傳 false , 否則將 +一個 (Key → Value) = (key → value)的Element加入, 並回傳 true +將所有Element的Key同加上 delta

        -

        -

        erase

        -

        (Key k)

        +

        +

        erase

        +

        (Key const& key)

        bool

        O(logN)

        -

        Erase an element from the tree with -given key. Return false if the element not found.

        +

        檢查是否已有Element的Key 為 key, 若有則刪除之, 並回傳 true, +否則則回傳 false

        -

        -

        operator[]

        -

        (Key k)

        -

        Value

        +

        +

        operator[]

        +

        (Key const& key)

        +

        Value&

        O(logN)

        -

        Like find() , but it will insert an element -automatic if the corrosponding element not found

        +

        檢查是否已有Element的Key 為 key, 若有則回傳相對應的Value的Reference +否則先執行 insert(key, Value()) 再回傳相對應的Reference

        -

        -

        splitOut

        -

        (Key const& upper_bound,
        -SplayTree* out)

        +

        +

        splitOut

        +

        (Key const& upper_bound,
        +SplayTree* tree2)

        void

        -

        O(log N)

        -

        Split out all the elements with key -larger than upper_bound and store then into out

        +

        O(logN) + O(M)

        +

        將 tree2 清空, 再將所有Key > upper_bound 的Element都丟到 tree2

        -

        -

        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.

        +

        +

        mergeAfter

        +

        (SplayTree* tree2)

        +

        void

        +

        O(logN) + O(logM)

        +

        檢查是否 this 中的 Key 都小於 tree2 中的Key, 是的話把 tree2 +中的 Element 都搬到 this , 同時清空 tree2 , 回傳 true. 否則 +回傳 false

        -

        -

        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

        +

        +

        merge

        +

        (SplayTree* tree2)

        +

        void

        +

        O(logN) + O(logM)

        +

        檢查是否 this 中的 Key 都小於 tree2 中的Key 或者 +是否 this 中的 Key 都大於 tree2 中的Key, 是的話把 tree2 +中的 Element 都搬到 this , 同時清空 tree2 , 回傳 true. 否則 +回傳 false

        - -
        -
        Warning
        +
        Note
        		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)
        -
        -
        -
        -
        -

        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 +假設現在有兩個SplayTree A 和 B, 則:

            -
            • +

            • -operator|(Value) merge two nodes +執行 B.moveTo(&A) 後 B 會變成空的, A 原本擁有的資料也會覆蓋掉

            • -operator*(size_t) ?? +執行 A.merge(&B) 或 A.mergeAfter(&B) 後 +如果檢查發現確實可以merge, 則之後 B 會變成空的

          -

          For example, if you want to maintain range minimum

          + + +
        +
        +
        +
      +
      +

      meow:: SegmentTree<Value> (C++ class)

      +
      +

      Description

      +

      維護一個陣列, 並且讓user可以有區間查詢, 區間修改的小東東

      +
      +
      +

      Template Class Operators Request

      + +++++++ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
      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|

      (Value v)

      Value

      區間合併後的值

      +
        +
      • +

        +若要維護區間最小值, 即每次都是詢問範圍 [a, b] 的最小值, 則可以定義 +

        • -Value::operator+(Value v2) will be this->realValue + v2.realValue +operator+ 為 回傳相加值

        • -Value::operator|(Value v2) will be std::min(this->realValue, v2.realValue) +operator* 為 回傳*this

        • -Value::operator*(size_t n) will be this->realValue +operator| 為 回傳std::min(*this, v)

        -

        If you want to maintain range sum

        +
        • +
      • +

        +若要維護區間最總和, 即每次都是詢問範圍 [a, b] 的總和, 則可以定義 +

        • -Value::operator+(Value v2) will be this->realValue + v2.realValue +operator+ 為 回傳相加值

        • -Value::operator|(Value v2) will be this->realValue + v2.realValue) +operator* 為 回傳(*this) * n

        • -Value::operator*(size_t n) will be this->realValue * n +operator| 為 回傳相加值

        -
        Support methods
          + +
        +
      +
      +

      Support Methods

      +

      • -N ← array size +N ← this 所維護的陣列長度

      @@ -1783,60 +2067,64 @@ N ← array size style=" width:100%; "> + - - - - - + + + + Const? -Name - Parameters - Return Type - Time Complexity +Name + Parameters + Return_Type + Time_Complexity Description -

      -

      reset

      -

      (size_t N)

      +

      +

      reset

      +

      (size_t size)

      void

      -

      O(1)

      -

      Clear and reset the array size to N (from 0 to N - 1)

      +

      O(1)

      +

      將資料清空且設定維護範圍是 0~size - 1 其中時間複雜度確切多少未知 +要看 std::vector::resize() 的效率

      -

      const

      -

      query

      -

      (ssize_t first, ssize_t last)

      +

      const

      +

      query

      +

      (ssize_t first,
      +ssize_t last)

      Value

      -

      O(logN)

      -

      Range query

      +

      O(logN)

      +

      回傳區間 [first,last] (邊界都含) 的區間值

      -

      -

      override

      -

      (ssize_t first, ssize_t last, Value const& __value)

      +

      +

      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

      +

      O(logN)

      +

      將區間 [first,last] 全部都設定成 value

      -

      -

      offset

      -

      (ssize_t first, ssize_t last, Value const& __value)

      +

      +

      offset

      +

      (ssize_t first,
      +ssize_t last,
      +Value const& delta)

      void

      -

      O(logN)

      -

      Let the element in the array index from __first to __last -plus __value

      +

      O(logN)

      +

      將區間 [first,last] 全部都加上 delta

      -
      +
      @@ -1844,7 +2132,7 @@ plus __value

      diff --git a/description.asciidoc b/description.asciidoc index f768289..f55fdad 100644 --- a/description.asciidoc +++ b/description.asciidoc @@ -2,36 +2,40 @@ == 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` +** *KD_Tree.h* `class KD_Tree` +** *SegemenTree.h* `class SegmentTree` +** *SplayTree.h* `class SplayTree` * *oo/* ** *Register_Implement.h* `class RegisterInterface` , `class ImplementInterface` == Structures/Classes/Functions + +:b: | diff --git a/meowpp/Usage.h b/meowpp/Usage.h index 22f7329..d2ef083 100644 --- a/meowpp/Usage.h +++ b/meowpp/Usage.h @@ -88,68 +88,67 @@ namespace meow{ Strings usage_end ; Strings proc_arguments; }; - /******************************************************************* - @asciidoc - === meow:: *Usage* (C++ Class) - .Description - `Usage` 是用來分析argc, argv和輸出usage document的class. - argc, argv的部份, 有以下規則 - - * `-c` 其中 `c` 可以代換成正常的一個字元的字符, - 這種選像要嘛就是 *有設置* , 不然就是 *沒設置* - * `-c ` 附加一個value, 這種選項可以是選擇性 ,即要設定與否都可以, - 反之則一定要設定. 另外可以給定value的預設值以及哪些value是可接受的 - * `` 其他, 一律視為process arguments - - .Methods - * `Usage(String const& _name)` + - 建構子, 所有說明文字中 ** 都會被代換成 `_name` - * `Usage()` + - 建構子, `_name` 自動取為 " *nobody* " - * `import(Usage const& usage)` + - 將另一個usage的設定匯入, 回傳成功與否 *(bool)* - * `update(Usage const& usage)` + - 將另一個usage分析argc,argv出來的資料拿來用, 回傳成功與否 *(bool)* - * `addOption(unsigned char option, String const& description)` + - 新增一個不接額外選項的參數, 並附上說明文字, 回傳成功與否 *(bool)* - * `addOption(unsigned char option, String const& description, - String const& value_type, String const& value_default, bool must)` + - 新增一個有額外選項的參數, 並附上說明文字, 額外選項的型別跟預設值. - 說明文字中所有的" ** "將會被取代指定的型別, 其中 `must` 代表 - " *是否一定要設定此參數* " , 回傳表成功與否 *(bool)* - * `addOptionValueAccept(unsigned char option, - String const& value, String const& description)` + - 針對某個option, 新增一個可接受的額外選項 (如果某個option從頭到尾都沒有 - 新增可接受的選項, 則視為不限制), 回傳成功與否 *(bool)* - * `hasOptionSetup(unsigned char option)` + - 回傳是否有此選項 *(bool)* - * `getOptionValuesCount(unsigned char option)` + - 回傳此參數被設置了幾次 *(size_t)* , 只對有接額外參數的有效 - * `getOptionValue(unsigned char option, size_t index)` + - 回傳第`index`個額外選項 *(String)* - * `getProcArgsCount()` + - 回傳有多少個Process Arguments *(size_t)* - * `getProcArg(size_t index)` + - 取得第`index`個Process Argument *(String)* - * `getProcArgs()` + - 回傳一個陣列, 包含所有Process Arguments *(Strings)* - * `addUsageBegin(String const& des)` + - 新增一段usage document於每個選項逐條說明之前 - * `addUsageEnd (String const& des)` + - 新增一段usage document於每個選項逐條說明之後 - * `String getUsage()` + - 回傳usage document *(String)* - * `setArguments(int argc, char** argv, String* errmsg)` + - 輸入argv, argc, 回傳是否沒有錯誤發生 *(bool)* , 其中如果有錯誤發生, - 且 `errmsg != NULL` 則會將錯誤訊息寫入之 - -NOTE: `String` 是 `std::string` . + -`Strings` 是 `std::vector< std::string> >`. + -如果沒有寫回傳什麼, 就是回傳 `void` - -''' -@asciidoc- - ******************************************************************/ + //# === meow:: *Usage* (C++ Class) + //# ==== Description + //# `Usage` 是用來分析argc, argv和輸出usage document的class. + //# argc, argv的部份, 有以下規則 + //# + //# * `-c` 其中 `c` 可以代換成正常的一個字元的字符, + //# 這種選像要嘛就是 *有設置* , 不然就是 *沒設置* + //# * `-c ` 附加一個value, 這種選項可以是選擇性 ,即要設定與否都可以, + //# 反之則一定要設定. 另外可以給定value的預設值以及哪些value是可接受的 + //# * `` 其他, 一律視為process arguments + //# + //# ==== Methods + //# * `Usage(String const& _name)` + + //# 建構子, 所有說明文字中 ** 都會被代換成 `_name` + //# * `Usage()` + + //# 建構子, `_name` 自動取為 " *nobody* " + //# * `import(Usage const& usage)` + + //# 將另一個usage的設定匯入, 回傳成功與否 *(bool)* + //# * `update(Usage const& usage)` + + //# 將另一個usage分析argc,argv出來的資料拿來用, 回傳成功與否 *(bool)* + //# * `addOption(unsigned char option, String const& description)` + + //# 新增一個不接額外選項的參數, 並附上說明文字, 回傳成功與否 *(bool)* + //# * `addOption(unsigned char option, String const& description, + //# String const& value_type, String const& value_default, bool must)` + + //# 新增一個有額外選項的參數, 並附上說明文字, 額外選項的型別跟預設值. + //# 說明文字中所有的" ** "將會被取代指定的型別, 其中 `must` 代表 + //# " *是否一定要設定此參數* " , 回傳表成功與否 *(bool)* + //# * `addOptionValueAccept(unsigned char option, + //# String const& value, String const& description)` + + //# 針對某個option, 新增一個可接受的額外選項 (如果某個option從頭到尾都 + //# 沒有新增可接受的選項, 則視為不限制), 回傳成功與否 *(bool)* + //# * `hasOptionSetup(unsigned char option)` + + //# 回傳是否有此選項 *(bool)* + //# * `getOptionValuesCount(unsigned char option)` + + //# 回傳此參數被設置了幾次 *(size_t)* , 只對有接額外參數的有效 + //# * `getOptionValue(unsigned char option, size_t index)` + + //# 回傳第`index`個額外選項 *(String)* + //# * `getProcArgsCount()` + + //# 回傳有多少個Process Arguments *(size_t)* + //# * `getProcArg(size_t index)` + + //# 取得第`index`個Process Argument *(String)* + //# * `getProcArgs()` + + //# 回傳一個陣列, 包含所有Process Arguments *(Strings)* + //# * `addUsageBegin(String const& des)` + + //# 新增一段usage document於每個選項逐條說明之前 + //# * `addUsageEnd (String const& des)` + + //# 新增一段usage document於每個選項逐條說明之後 + //# * `String getUsage()` + + //# 回傳usage document *(String)* + //# * `setArguments(int argc, char** argv, String* errmsg)` + + //# 輸入argv, argc, 回傳是否沒有錯誤發生 *(bool)* , 其中如果有錯誤發生, + //# 且 `errmsg != NULL` 則會將錯誤訊息寫入之 + //# + //#[NOTE] + //#================================== + //# * `String` 是 `std::string` . + //# * `Strings` 是 `std::vector< std::string> >`. + //# * 如果沒有寫回傳什麼, 就是回傳 `void` + //#================================== + //# + //#''' } #include "Usage.hpp" diff --git a/meowpp/dsa/DisjointSet.h b/meowpp/dsa/DisjointSet.h index b33a839..b918adb 100644 --- a/meowpp/dsa/DisjointSet.h +++ b/meowpp/dsa/DisjointSet.h @@ -1,10 +1,18 @@ #ifndef DisjointSet_H__ #define DisjointSet_H__ + #include #include namespace meow{ + //# + //#=== meow:: *DisjointSet* (C++ class) + //#==== Description + //# `DisjointSet` 是個*輕量級Data Dtructure*, 用來維護一堆互斥集的資訊. + //# 相關資料可參考 + //# link:http://www.csie.ntnu.edu.tw/~u91029/DisjointSets.html[演算法筆記] + //# class DisjointSet{ private: size_t n; @@ -17,39 +25,46 @@ namespace meow{ DisjointSet(); DisjointSet(size_t _n); DisjointSet(DisjointSet const& dsj); - // + + //#==== 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) size_t root (size_t a ) const; + + + //#|const |size |() | size_t | very fast + //#|回傳 *總集合大小* size_t size ( ) const; - // + + + //#| |reset|(size_t `N`) | void | O(N) + //#| 清空, 並且設定總集合大小為 `N` void reset(size_t _n ); + + + //#| |merge|(size_t `number1`,\size_t `number2`)| size_t | very fast + //#| 將 `number1` 所在的集合 跟 `number2` 所在的集合 *合併*, + //# 並回傳合併後新的集合的編號 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 namespace meow{ + //# + //#=== meow:: *KD_Tree* (C++ class) + //#==== Description + //# `KD_Tree` 全名k-dimension tree, 用來維護由 *N個K維度向量所成的集合*, + //# 並可於該set中查找 *前i個離給定向量最接近的向量* + //# + //#==== Template Class Operators Request + //#[options="header",width="70%",cols="1>m,1<,3 class KD_Tree{ private: @@ -68,68 +86,76 @@ namespace meow{ std::vector* __orders, int __depth); public: + //#==== Custom Type Definitions + //# * `Vectors` <- `std::vector` + //# typedef typename std::vector Vectors; // KD_Tree(); KD_Tree(size_t __dimension); ~KD_Tree(); - // + + //#==== 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中 void insert(Vector const& __vector); + + + //#||erase|(Vector const& `v`)|bool| O(N) + //#|將向量 `v` 從set中移除, '~TODO:可以再優化~' bool erase (Vector const& __vector); + + + //#||build|()|void|O(KN logN) or O(1) + //#|檢查距上一次 `build()` 至今是否有 `insert/erase` 被呼叫, + //# 若有, 重新建樹, 否則不做事 void build(); + + + //#||forceBuild|()|void|O(KN logN) + //#|重新建樹 void forceBuild(); - // + + + //#|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` 來決定誰在前面. 最後回傳一陣列包含所有解. Vectors query(Vector const& __vector, size_t __nearestNumber, bool __compareWholeVector) const; - // + + + //#||clear|()|void|O(1) + //#|清空所有資料 void clear(); + + + //#||reset|(size_t `dimension`)|void|O(1) + //#|清空所有資料並且指定維度為 `dimension` void reset(size_t __dimension); + + + //#|===================================================================== }; - /********************************************************* - @asciidoc - === meow:: *KD_Tree* (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 - [options="header",width="100%",cols="1>,1dimension 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- - *********************************************************/ + //# + //#[NOTE] + //#======================================== + //# * 此資料結構只有在 N >> 2 ^K^ 時才比較有優勢, + //# 當 K 逐漸變大時, 所花時間會跟暴搜沒兩樣 + //#======================================== + //# + //# ''' } #include "KD_Tree.hpp" diff --git a/meowpp/dsa/MergeableHeap.h b/meowpp/dsa/MergeableHeap.h index 1e47afd..c1a2460 100644 --- a/meowpp/dsa/MergeableHeap.h +++ b/meowpp/dsa/MergeableHeap.h @@ -4,6 +4,19 @@ #include namespace meow{ + //# + //#=== meow:: *MergeableHeap* (C++ class) + //#==== Description + //# 一個用 *左偏樹* 實作的 *Maximum-Heap* , 除了原本heap有的功能外, + //# 還支援 `merge`, `split` 等功能 + //# + //#==== Template Class Operators Request + //#[options="header",width="70%",cols="1>m,1<,3 class MergeableHeap{ // maximum-heap private: @@ -23,66 +36,70 @@ namespace meow{ public: MergeableHeap(); MergeableHeap(MergeableHeap const& _heap2); - // - ~MergeableHeap(); - // MergeableHeap& operator=(MergeableHeap const& _heap2); - void moveTo(MergeableHeap* _heap2); - // - Element const& top () const; - size_t size () const; - size_t empty() const; - // - void push (Element const& _value); - void pop ( ); - void clear( ); + ~MergeableHeap(); + + //#==== 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` 所擁有的資料數 + void moveTo(MergeableHeap* _heap2); + + + //#|const|top|()|Element const&|O(1) + //#|回傳最大的那個 `Element` + Element const& top() const; + + + //#|const|size|()|size_t|O(1) + //#|回傳 `this` 中擁有的資料數 + size_t size() const; + + + //#|const|empty|()|bool|O(1) + //#|回傳 `this` 是否為空 + bool empty() const; + + + //#||push|(Element const& `e`)|void|O(logN) + //#|將 `e` 加入 + void push(Element const& _value); + + + //#||pop|()|void|O(logN) + //#|將最大的 `Element` 移除 + void pop(); + + + //#||clear|()|void|O(N) + //#|將資料清空 + void clear(); + + + //#||merge|(MergeableHeap* `heap2`)|void|O(logN+logM) + //#|將 `heap2` 的資料統統加到 `this` 中, 並且清空 `heap2` + //# 時間複雜度中的M是 `heap2` 的資料數 void merge(MergeableHeap* _heap2); + + //#|============================================== }; - - /********************************************************* - @asciidoc - === meow:: *MergeableHeap* (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>,1data 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- - *********************************************************/ + //# [WARNING] + //#============================================== + //# * 假設現在有兩個MergeableHeap `A` 和 `B`, 則: + //# ** 執行 `A.merge(&B)` 後 `B` 會變成空的 + //# ** 執行 `B.moveTo(&A)` 後 `B` 會變成空的, `A` 原本擁有的資料也會覆蓋掉 + //#============================================== + //# + //# ''' + //# } #include "MergeableHeap.hpp" diff --git a/meowpp/dsa/MergeableHeap.hpp b/meowpp/dsa/MergeableHeap.hpp index be7dcea..e7f5978 100644 --- a/meowpp/dsa/MergeableHeap.hpp +++ b/meowpp/dsa/MergeableHeap.hpp @@ -92,7 +92,7 @@ namespace meow{ return (root == NULL ? 0 : root->weight); } template // empty - inline size_t MergeableHeap::empty() const{ return (size() == 0); } + inline bool MergeableHeap::empty() const{ return (size() == 0); } ////////////////////////////////////////////////////////// // **# MergeableHeap -- update: push, pop, merge #** // ////////////////////////////////////////////////////////// diff --git a/meowpp/dsa/SegmentTree.h b/meowpp/dsa/SegmentTree.h index 585ea5d..89fd5d9 100644 --- a/meowpp/dsa/SegmentTree.h +++ b/meowpp/dsa/SegmentTree.h @@ -2,6 +2,30 @@ #define SegmentTree_H__ namespace meow{ + //# + //#=== meow:: *SegmentTree* (C++ class) + //#==== Description + //# 維護一個陣列, 並且讓user可以有區間查詢, 區間修改的小東東 + //# + //#==== Template Class Operators Request + //#[options="header",width="70%",cols="1>m,1<,3 class SegmentTree{ private: @@ -28,11 +52,38 @@ namespace meow{ SegmentTree(size_t __size); SegmentTree(SegmentTree const& __tree2); // + //#==== 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()` 的效率 void reset(size_t __size); - // + + + //#|const|query|(ssize_t `first`,\ssize_t `last`)|Value|O(logN) + //#|回傳區間 `[first,last]` (邊界都含) 的區間值 Value query (ssize_t __first, ssize_t __last) const; + + + //#||override|(ssize_t `first`,\ssize_t `last`,\Value const& `value`) + //#|void|O(logN) + //#|將區間 `[first,last]` 全部都設定成 `value` void override(ssize_t __first, ssize_t __last, Value const& __value); + + + //#||offset|(ssize_t `first`,\ssize_t `last`,\Value const& `delta`) + //#|void|O(logN) + //#|將區間 `[first,last]` 全部都加上 `delta` void offset (ssize_t __first, ssize_t __last, Value const& __delta); + + // void print(){ for(int i = 0; i < _size; i++){ query(i, i); @@ -52,52 +103,9 @@ namespace meow{ printf("\n"); } } + + //#|============================================== }; - /********************************************************* - @asciidoc - === meow:: *SegmentTree* (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* (C++ class) + //#==== Description + //# `SplayTree` 是一種神乎其技的資料結構, 維護一堆 Key->Value . 並且支援 + //# 一些 `std::map` 難以快速實踐的操作, 如 `split` , `merge` , `keyOffset` + //# + //#==== Template Class Operators Request + //#[options="header",width="70%",cols="1>m,1<,3 class SplayTree{ private: @@ -44,6 +60,14 @@ namespace meow{ // void print(Node* __now, int __depth) const; public: + //#==== Custom Type Definitions + //# + //# * `Element` -> 用來當作回傳資料的媒介 + //# ** 重定義 `operator->()` 到 `std::pair*` + //# ** 重定義 `operator*()` 到 `std::pair&` + //# ** 有 `operator==` , `operator!=`, `operator=` 可用 + //# ** 可以直接用 `(*e).second = some_value` 來改變SplayTree中的資料 + //# class Element{ private: typedef std::pair Entry; @@ -69,109 +93,146 @@ namespace meow{ SplayTree(); SplayTree(SplayTree const& __tree2); ~SplayTree(); - // SplayTree& operator=(SplayTree const& __tree2); - void moveTo(SplayTree* __tree2); // + //#==== 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` 所擁有的資料數 + void moveTo(SplayTree* __tree2); + + + //#|const|lowerBound|(Key const& `k`)|Element|O(logN) + //#|找出第一個(最小的) Element且 `k` <= 它的 Key, 並且回傳之. + //# 找不到的話回傳 `this->end()` Element lowerBound(Key const& __key) const; + + + //#|const|lowerBound|(Key const& `k`)|Element|O(logN) + //#|找出第一個(最小的) Element且 `k` < 它的 Key, 並且回傳之. + //# 找不到的話回傳 `this->end()` Element upperBound(Key const& __key) const; + + + //#|const|lowerBound|(Key const& `k`)|Element|O(logN) + //#|找出第一個(最小的) Element且 `k` >= 它的 Key, 並且回傳之. + //# 找不到的話回傳 `this->end()` Element rLowerBound(Key const& __key) const; + + + //#|const|lowerBound|(Key const& `k`)|Element|O(logN) + //#|找出第一個(最小的) Element且 `k` > 它的 Key, 並且回傳之. + //# 找不到的話回傳 `this->end()` Element rUpperBound(Key const& __key) const; + + + //#|const|find|(Key const& `k`)|Element|O(logN) + //#|找出 Key= `k` 的Elemenet 並回傳. 找不到的話回傳 `this->end()` Element find (Key const& __key) const; - Element order(size_t __order ) const; - Element first( ) const; - Element last ( ) const; - Element end( ) const; - // + + + //#|const|order|(size_t `ord`)|Element|O(logN) + //#|將Elements依照Key由小到大排序, 回傳第 `ord` 個Element (由0算起). + //# 其中如果 `ord` > N - 1, 則會回傳 `this->last()` + Element order(size_t __order) const; + + + //#|const|first|(size_t `ord`)|Element|O(logN) + //#|回傳Key最小的Element, 如果SplayTree為空, 則回傳 `this->end()` + Element first() const; + + + //#|const|last|(size_t `ord`)|Element|O(logN) + //#|回傳Key最大的Element, 如果SplayTree為空, 則回傳 `this->end()` + Element last() const; + + + //#|const|end|()|Element|O(1) + //#|回傳一個指向NULL的Element, 以供 `find` , `order` , `first` + //# , `last` 等判斷是否有找到相對應的Element + Element end() const; + + + //#|const|size|()|size_t|O(1)| 回傳資料數 size_t size() const; + + + //#|const|size|()|bool|O(1)| 回傳是否為空 bool empty() const; - // - void clear(); - void keyOffset(Key const& __delta); - bool insert (Key const& __key, Value const& __value); - bool erase (Key const& __key); + + + //#||clear|()|void|O(N)| 清空資料 + void clear(); + + + //#||keyOffset|(Key const& `delta`)|void|O(1) + //#|將所有Element的Key同加上 `delta` + void keyOffset(Key const& __delta); + + + //#||insert|(Key const& `key`,\Value const& `value`)|bool|O(logN) + //#|檢查是否已有Element的Key 為 `key`, 若有則回傳 `false` , 否則將 + //# 一個 (Key -> Value) = (`key` -> `value`)的Element加入, 並回傳 `true` + //# 將所有Element的Key同加上 `delta` + bool insert(Key const& __key, Value const& __value); + + + //#||erase|(Key const& `key`)|bool|O(logN) + //#|檢查是否已有Element的Key 為 `key`, 若有則刪除之, 並回傳 `true`, + //# 否則則回傳 `false` + bool erase(Key const& __key); + + + //#||operator[]|(Key const& `key`)|Value&|O(logN) + //#|檢查是否已有Element的Key 為 `key`, 若有則回傳相對應的Value的Reference + //# 否則先執行 `insert(key, Value())` 再回傳相對應的Reference Value& operator[](Key const& __key); - void splitOut(Key const& __upper_bound, SplayTree* __right); - bool mergeAfter(SplayTree* __tree2); - bool merge (SplayTree* __tree2); + + + //#||splitOut|(Key const& `upper_bound`,\SplayTree* `tree2`)|void + //#|O(logN) + O(M) + //#|將 `tree2` 清空, 再將所有Key > `upper_bound` 的Element都丟到 `tree2` + void splitOut(Key const& __upper_bound, SplayTree* __right); + + + //#||mergeAfter|(SplayTree* `tree2`)|void|O(logN) + O(logM) + //#|檢查是否 `this` 中的 Key 都小於 `tree2` 中的Key, 是的話把 `tree2` + //# 中的 Element 都搬到 `this` , 同時清空 `tree2` , 回傳 `true`. 否則 + //# 回傳 `false` + bool mergeAfter(SplayTree* __tree2); + + + //#||merge|(SplayTree* `tree2`)|void|O(logN) + O(logM) + //#|檢查是否 `this` 中的 Key 都小於 `tree2` 中的Key 或者 + //# 是否 `this` 中的 Key 都大於 `tree2` 中的Key, 是的話把 `tree2` + //# 中的 Element 都搬到 `this` , 同時清空 `tree2` , 回傳 `true`. 否則 + //# 回傳 `false` + bool merge(SplayTree* __tree2); + // // void print() const; + //#|===================================================================== }; - /********************************************************* - @asciidoc - === meow:: *SplayTree* (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:: *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>,1value) - 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- - *********************************************************/ + //# + //#[NOTE] + //#======================================== + //# * 假設現在有兩個SplayTree `A` 和 `B`, 則: + //# ** 執行 `B.moveTo(&A)` 後 `B` 會變成空的, `A` 原本擁有的資料也會覆蓋掉 + //# ** 執行 `A.merge(&B)` 或 `A.mergeAfter(&B)` 後 + //# 如果檢查發現確實可以merge, 則之後 `B` 會變成空的 + //#======================================== + //# + //# ''' + //# } #include "SplayTree.hpp" diff --git a/meowpp/dsa/SplayTree.hpp b/meowpp/dsa/SplayTree.hpp index 47615db..77331ef 100644 --- a/meowpp/dsa/SplayTree.hpp +++ b/meowpp/dsa/SplayTree.hpp @@ -31,7 +31,7 @@ namespace meow{ SplayTree::offsetDown(Node* __node) const{ if(__node->_lChild != NULL) offsetAdd(__node->_lChild, __node->_keyOffset); if(__node->_rChild != NULL) offsetAdd(__node->_rChild, __node->_keyOffset); - __node->_keyOffset = 0; + __node->_keyOffset = Key(0); } // template diff --git a/meowpp/utility.h b/meowpp/utility.h index 4f3b36a..ec47225 100644 --- a/meowpp/utility.h +++ b/meowpp/utility.h @@ -40,59 +40,74 @@ namespace meow{ template inline double average(T const& beg, T const& end, T const& p, double sigs); - /******************************************************************* - @asciidoc - === 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 - the parameters or not - |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 | - 如果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 const& mn, T const& mx, + - T const& v) | T | - std::max(mn, std::min(mx, v)) - |squ |(T const& x) | T| - x * x - |average|(T const& beg, T const& end, + - double sigs)| T| - 只將 `sigs` 個標準差以內的數據拿來取平均 - |average|(T const& beg, T const& end, + - T const& p, double sigs)| T| - 同上, 不過這次用 `p` 來加權平均 - |============================================================== - - [NOTE] - `stringReplace()` 不是用什麼好方法寫的因此執行效率很低請別虐待它. + - 額外附贈一個 `const double PI = 3.141592653589......` - -''' -@asciidoc- - ******************************************************************/ + //# === 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 + //# the parameters or not + + + //# |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 | + //# 如果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 const& `mn`, T const& `mx`, \ T const& `v`) | T | + //# `std::max(mn, std::min(mx, v))` + + + //# |squ |(T const& `x`) | T| `x * x` + + + //# |average|(T const& `beg`, T const& `end`, \ double `sigs`)| T| + //# 只將 `sigs` 個標準差以內的數據拿來取平均 + + + //# |average|(T const& `beg`, T const& `end`, + //# \ T const& `p`, double `sigs`)| T| 同上, 不過這次用 `p` 來加權平均 + //# |============================================================== + //# + //# [NOTE] + //# ==================================== + //# * `stringReplace()` 不是用什麼好方法寫的因此執行效率很低請別虐待它. + //# * 額外附贈一個 `const double PI = 3.141592653589......` + //# ==================================== + //# + //# ''' + //# } #include "utility.hpp" diff --git a/readme_generate.py b/readme_generate.py index b7da90c..2ee5cc4 100755 --- a/readme_generate.py +++ b/readme_generate.py @@ -4,8 +4,9 @@ import sys; import os; class Reader(): - def __init__(self, suffix): + def __init__(self, suffix, stp): self.suffix = suffix; + self._stop = stp; # def checkOk(self, pathname): for suffix in self.suffix: @@ -19,19 +20,22 @@ class Reader(): return self.getOutputString(input_string); def getOutputString(self, input_string): return '' + def stop(self): + return self._stop; # class AsciidocReader(Reader): def __init__(self): Reader.__init__(self, ['.asciidoc', '.adoc', '.ascii', - ]); + ], + True); def getOutputString(self, input_string): return input_string; # class InReader(Reader): def __init__(self, suffix, start_string, end_string): - Reader.__init__(self, suffix); + Reader.__init__(self, suffix, False); self.start_string = start_string; self. end_string = end_string; def getOutputString(self, input_string): @@ -58,15 +62,48 @@ class InReader(Reader): index += 1; return ret; # +class InLineReader(Reader): + def __init__(self, suffix, prefix): + Reader.__init__(self, suffix, False); + self.prefix = prefix; + def getOutputString(self, input_string): + ret = ''; + line_begin = 0; + while line_begin < len(input_string): + line_end = line_begin; + for line_end in range(line_begin, len(input_string) + 1): + if input_string[line_end] == "\n": + break; + ok = False; + for i in range(line_begin, line_end - len(self.prefix) + 1): + if input_string[i : i + len(self.prefix)] == self.prefix: + ok = True; + break; + if ok: + start = i + len(self.prefix); + while start < line_end: + if input_string[start]!=' ' and input_string[start]!="\t": + break; + start += 1; + ret += input_string[start: line_end].replace('\\', " +\n")+"\n"; + line_begin = line_end + 1; + return ret; +# class CppReader(InReader): def __init__(self): InReader.__init__(self, ['.c', '.cpp', '.h', '.hpp'], '@asciidoc', '@asciidoc-'); +class CppLineReader(InLineReader): + def __init__(self): + InLineReader.__init__(self, + ['.c', '.cpp', '.h', '.hpp'], + '//#'); # readers = [AsciidocReader(), CppReader(), + CppLineReader(), ]; if len(sys.argv) <= 1: readme = 'README.asciidoc'; @@ -82,9 +119,12 @@ for (root, sub_folders, files) in os.walk('./'): if path == './' + readme: continue; if reader.checkOk(filename): - print 'Get asciidoc from ' + path; - readme_f.write(reader.read(path)); - deleted.append(filename); + s = reader.read(path); + if len(s) > 0: + print 'Get asciidoc from ' + path; + readme_f.write(s); + if reader.stop(): + deleted.append(filename); for filename in deleted: files.remove(filename); readme_f.close(); -- cgit