path: root/README.asciidoc

= meow


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

.Links
* https://github.com/cathook/meow[GitHub]
* http://www.csie.ntu.edu.tw/~b01902109/readme/template_meow/README.html[README.html]
* https://github.com/cathook/meow/archive/master.zip[Download]

== File Tree
=== *meowpp/* C++ templates

* *utility.h* some useful functions,
              `stringPringf()` , `stringReplace()` , `cstringEndWith()` ,
              `debugPrintf()` , `messagePrintf()` , `constant PI` ,
              `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()`
* *dsa/* Data Structures and Algorithms
** *BinaryIndexTree.h* `class BinaryIndexTree<Vector, Scalar>`
** *DisjointSet.h* `class DisjointSet`
** *Heaps.h* `class MergeableHeap<Element>`
** *KD_Tree.h* `class KD_Tree<Vector, Scalar>`
** *SegemenTree.h* `class SegmentTree<Value>`
** *SplayTree.h* `class SplayTree<Key, Value>`
** *SplayTree_Range.h* `class SplayTree_Range<Key, Value>`
** *VP_Tree.h* `class VP_Tree<Vector, Scalar>`
* *oo/*
** *Register_Implement.h* `class RegisterInterface` ,
                            `class ImplementInterface` 

== 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
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>     |(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` 來加權平均
|==============================================================

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

'''


=== meow:: *Usage* (C++ Class)
==== Description
`Usage` 是用來分析argc, argv和輸出usage document的class.
argc, argv的部份, 有以下規則

* `-c` 其中 `c` 可以代換成正常的一個字元的字符,
這種選像要嘛就是 *有設置* , 不然就是 *沒設置*
* `-c <value>` 附加一個value, 這種選項可以是選擇性 ,即要設定與否都可以,
反之則一定要設定. 另外可以給定value的預設值以及哪些value是可接受的
* `<value>` 其他, 一律視為process arguments

==== Methods
* `Usage(String const& _name)` +
建構子, 所有說明文字中 *<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)` +
新增一個有額外選項的參數, 並附上說明文字, 額外選項的型別跟預設值.
說明文字中所有的" *<types>* "將會被取代指定的型別, 其中 `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`
==================================

'''


=== meow:: *ImplementInterface/RegisterInterface* (C++ Class)
==== Description
Assume there is a problem which can be solved by different algorithms.
Then you can write multiple classes to approach this problem. +
Now if you want to decide which algorithm to use in runtime, you can just
approach this case by a simple way:

* Let all the problem-solving classes inherit from
`class ImplementInterface<T>` , and call the constructure with giving
`identify` (type `T` ) .
* Create an class inherit from `RegisterInterface<T>` ,
and register all your implement class to it by call
`regImplement(pointer to the class)`.
* Select which implement class you want by call
`getImplement(identify)` , which will return the pointer
to the corresponding class.

'''


=== meow:: *DisjointSet* (C++ class)
==== 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<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:: *VP_Tree<Vector, Scalar>* (C++ class)
==== Description
`VP_Tree` 用來維護由 *N個K維度向量所成的集合*, 
並可於該set中查找 *前i個離給定向量最接近的向量*. +
不像 `KD_Tree` 二分樹每次都選擇一個維度去分, 分成小的跟大的, 
`VP_Tree` 每次選一個點, 將資料分成 離這個點近的, 跟離這個點遠的.
至於怎麼選呢...., 嘛還沒研究, 先random

.參考資料連結: 
* http://stevehanov.ca/blog/index.php?id=130[link]
* http://pnylab.com/pny/papers/vptree/vptree[link]

==== 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`) | Vector&    | copy operator
|const |  Vector|operator<  |(Vector `v`) | bool       | 權重比較
|const |  Scalar| 'Scalar'  |(int    `n`) | Scalar     | 建構子,
其中一定`n=0 or 4`
|const |  Scalar|operator*  |(Scalar `s`) | Scalar     | 相乘
|const |  Scalar|operator+  |(Scalar `s`) | Scalar     | 相加
|const |  Scalar|operator-  |(Scalar `s`) | Scalar     | 相差
|const |  Scalar|operator-  |(          ) | Scalar     | 取負號
|const |  Scalar|operator<  |(Scalar `s`) | bool       | 大小比較
|=====================================================================

==== Custom Type Definitions
* `Vectors` <- `std::vector<Vector>`

==== Support Methods

* N <- `this` 中擁有的資料數
* D <- `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(logN) ~Expected~
|於set中找尋距離 `v` 前 `i` 近的向量, 並依照由近而遠的順序排序.
如果有兩個向量 `v1`,`v2` 距離一樣, 且 `cmp` 為 `true` , 則直接依照
`v1 < v2` 來決定誰在前面. 最後回傳一陣列包含所有解.
||clear|()|void|O(1)
|清空所有資料
||reset|(size_t `dimension`)|size_t|O(1)
|清空所有資料並且指定維度為 `max(1, dimension)` 並且回傳指定後的維度
|=====================================================================

[NOTE]
========================================
* 實測結果發覺, 維度小的時候, 比起中規中矩的 `KD_Tree`, `VP_Tree` 有
'randomp' 於其中, 因此時間複雜度只是期望值 'O(logN)' 但是測資大到
一定程度, `KD_Tree` 效率會一整個大幅掉下, 但 `VP_Tree` 幾乎不受影響
* 'TODO' `insert()`, `erase()` 算是未完成功能

========================================

'''

=== meow:: *KD_Tree<Vector, Scalar>* (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<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
`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)| 清空資料
||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`
||keyOffset|(Key const& `delta`)|void|O(1)
|將所有Element的Key同加上 `delta`
||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
維護一個陣列, 並且讓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`
|=====================================================================

'''


=== meow:: *SplayTree_Range<Key, Value>* (C++ class)
==== Description
`SplayTree_Range` 是一種神乎其技的資料結構, 維護一堆 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_Range中的資料

==== 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_Range* `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|query|()|Value|O(1)
|回傳整棵樹的區間Value
|const|query|(Key const& `first` , +
Key const& `last`)|Value|O(logN)
|找出key介於 `first`  +
~ `last` 的區間Value
|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_Range為空, 則回傳 `this->end()`
|const|last|(size_t `ord`)|Element|O(logN)
|回傳Key最大的Element, 如果SplayTree_Range為空, 則回傳 `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)| 清空資料
||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`
||keyOffset|(Key const& `delta`)|void|O(1)
|將所有Element的Key同加上 `delta`
||valueOffset|(Value const& `delta`)|void|O(1)
|將所有Element的value同加上 `delta`
||valueOverride|(Value const& `vaule`)|void|O(1)
|將所有Element的value同變成 `value`
||operator[]|(Key const& `key`)|Value&|O(logN)
|檢查是否已有Element的Key 為 `key`, 若有則回傳相對應的Value的Reference
否則先執行 `insert(key, Value())` 再回傳相對應的Reference
||splitOut|(Key const& `upper_bound`, +
SplayTree_Range* `tree2`)|void
|O(logN) + O(M)
|將 `tree2` 清空, 再將所有Key > `upper_bound` 的Element都丟到 `tree2`
||mergeAfter|(SplayTree_Range* `tree2`)|void|O(logN) + O(logM)
|檢查是否 `this` 中的 Key 都小於 `tree2` 中的Key, 是的話把 `tree2` 
中的 Element 都搬到 `this` , 同時清空 `tree2` , 回傳 `true`. 否則
回傳 `false`
||merge|(SplayTree_Range* `tree2`)|void|O(logN) + O(logM)
|檢查是否 `this` 中的 Key 都小於 `tree2` 中的Key 或者
是否 `this` 中的 Key 都大於 `tree2` 中的Key, 是的話把 `tree2` 
中的 Element 都搬到 `this` , 同時清空 `tree2` , 回傳 `true`. 否則
回傳 `false`
|=====================================================================

[NOTE]
========================================
* 假設現在有兩個SplayTree_Range `A` 和 `B`,  則:
** 執行 `B.moveTo(&A)` 後 `B` 會變成空的, `A` 原本擁有的資料也會覆蓋掉
** 執行 `A.merge(&B)` 或 `A.mergeAfter(&B)` 後
如果檢查發現確實可以merge, 則之後 `B` 會變成空的
========================================

'''


=== meow:: *BinaryIndexTree<Value>* (C++ class)
==== Description
極度簡化版的 `SegmentTree` 已無法區間操作, 區間詢問的區間開頭也一定要
在 `index=0` 的地方

==== 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  `n`) | Value      | 合併用(類似
`SegmentTree` 的
operator{b} )
|=====================================================================

==== Support Methods

* N <- `this` 中擁有的資料數

[options="header",width="100%",cols="1>m,3>s,7<,3<,3^,20<",grid="rows"]
|=====================================================================
|Const?|Name | Parameters   | Return_Type| Time_Complexity| Description
||reset|(size_t `size`, Value const& `value`)|void|O(`size`)
|將資料長度刷成 `N = size` 且每一個元素都是 `value`
||update|(size_t `index`, Value const& `value`)|void|O(logN)
|將第 `index` (從零開始算) 多加上 `value`
|const|query|(size_t `index`)|void|O(logN)
|詢問 `0~index` 的區間值
|=====================================================================

[NOTE]
========================================
* 一般來說只能用在維護區間總和, 維護區間最大值只有在特殊情況才可以, 即
'針對每個元素, 每次 update() 的值一定會大於等於原本的值' 
* 若要用區間最大值 , 則 `Value` 的 `operator+` 要寫成 `std::max(...)`
========================================

'''

== Test
=== ACM 相關題目
[options="header",width="70%",cols="3<s,3<,4^,1^,1<,2^m",grid="rows"]
|=======================================================================
| Name          | Problem               | Link  | Status | Time | source
| KD_Tree       | 'Retrenchment' |
http://acm.csie.org/ntujudge/problem.php?id=1971[NTU-OJ]
https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4052[ACM-ICPC Live]
| Accept | 0.083/0.083 | http://codepad.org/U85ruse5[codepad]


| VP_Tree       | 'Retrenchment' |
http://acm.csie.org/ntujudge/problem.php?id=1971[NTU-OJ]
https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4052[ACM-ICPC Live]
| Accept | 0.516/0.516 | http://codepad.org/03dW6ZHV[codepad]


| SplayTree + SegmentTree | 'Shuffling_cards' |
http://acm.csie.org/ntujudge/problem.php?id=1353[NTU-OJ]
http://www.spoj.com/problems/SHUFFLEK/[SPOJ]
| Accept/TLE | 6.910/--- | http://codepad.org/yUeiVZc0[codepad]

| SplayTree + BinaryIndexTree | 'Shuffling_cards' |
http://acm.csie.org/ntujudge/problem.php?id=1353[NTU-OJ]
http://www.spoj.com/problems/SHUFFLEK/[SPOJ]
|Accept/Accept|5.480/44.35| http://codepad.org/GAWjEtmq[codepad]



|=======================================================================




== Bug Report / Contact
  * E-Mail: cat.hook31894 \~在~ gmail.com