path: root/README.asciidoc

= meow


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

TIP: *README.html* is more beautiful.

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

[width="90%"]
* *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
** *DisjointSet.h* `class DisjointSet`
** *Heaps.h* `class MergeableHeap`
** *KD_Tree.h* `class KD_Tree`
** *SplayTree.h* `class SplayTree`
* *oo/*
** *Register_Implement.h* `class RegisterInterface` ,
                            `class ImplementInterface` 

== Structures/Classes/Functions


=== 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 object, type `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` is a lighting data structure that maintain N numbers from
*0* to *N-1* with methods below:

[options="header",width="100%",cols="1>,1<s,5<,1<,1<,10<",grid="rows"]
|=======================================================================
|Const?|Name| Parameters| Return Type| Time Complexity| Description
|const|root|(size_t number)|size_t|very fast|
Return the *group id* of the number given
|const|size|()|size_t|very fast|
Return *N*
||reset|(size_t N)|void|very fast|
Clean and initalize
||merge|(size_t number1, +
size_t number2)|size_t|very fast|
*Union* the group contains number1 and the group contains number2.
Return the merged group id
|=======================================================================
NOTE: *very fast* means that you can consider it as constant time.

'''

=== meow:: *MergeableHeap<Key, Value>* (C++ class)
.Description
MergeableHeap is a kind of maximum-heap with a special method `merge`,
which will merge another MergeableHeap into itself in O(logN) time.

.Template Request
* `Key` should has `operator<`

.Support methods
* N <- number of elements in the heap
* M <- number of elements in the other heap if need
[options="header",width="100%",cols="1>,1<s,3<,1<,1<,10<",grid="rows"]
|=======================================================================
|Const?|Name| Parameters| Return Type| Time Complexity| Description
||operator= | (MergeableHeap const&)| *this  | O(N)
|    Copy operator.
||moveTo    | (MergeableHeap*)      | void   | O(M)
|    Transform the this->data to the heap specified in parameters
|const|top  | ()    | Element   | O(1)
|    Return the maximum element in the heap.
|const|size | ()    | size_t    | O(1)
|    Return the number of elements in the heap.
|const|empty| ()    | bool      | O(1)
|     Return whether the heap is empty or not.
||push    |(Element)  |void   | O(log N) 
|    Add a element into the heap
||pop     |()         |void   | O(log N) 
|    Delete the maximum element from the heap
||merge   |(MergeableHeap*)   |void   | O(log M)
|    Merge the specified MergeableHeap(with size=M) into itself
||clear   |()         |void   | O(N)
|    Delete all elements from the heap
|=======================================================================

WARNING: Consider there are two MergeableHeap `A` and `B`. +
`B` will become empty after you call `A.merge(&B)`. +
The data in `B` will override by data in `A` and `A` will become empty after
you call `A.moveTo(&B)`

'''

=== meow:: *KD_Tree<Keys, Key, Value>* (C++ class)
.Description
`KD_Tree` is *K-dimension tree*, which is a dictionary(key->value).
Where the type if key is a *K-dimension vector* .

.Template Request
* `Keys` should has `operator[]` to allow the KD_Tree access the k-dimensions
* `Key` should has `operator*`, `operator+`

.Support Methods
* N <- numbers of element in the kd-tree
* K <- dimensions
* `Keys` is the tyepname of the vector
* `Key` is the typename of the element in the vector
* `Value` is the typename of value
[options="header",width="100%",cols="1>,1<s,5<,1<,2<,10<",grid="rows"]
|=======================================================================
|Const?|Name| Parameters| Return Type| Time Complexity| Description
|const|root|(size_t number)|size_t|very fast|
||insert|(Key const& k, Value v)|void|O(1)|Insert a pair (k->v)
|| build|()|void|O(KN logN) | Build the data structure(the `insert()` 
method will not build the data structure immediately)
|const|query|(Keys const& point, int k)|Value|O(kN ^1-1/k^ ) |
Using Euclidean-Distance to find the k-nearest neighbor from `point` .
And return the corrosponding value
|const|query|(Keys const& point, int k)|std::vector<Value>|O(kN ^1-1/k^ ) |
Using Euclidean-Distance to find all the x-nearest neighbor from `point` ,
where x <= k. And return an array of all the corrosponding value.
||clear|()|O(1)|Clear all data
||reset|(size_t dimension)|O(1)|Clear all data and then
set the this->dimension be `dimension`
|=======================================================================
NOTE: O(kN ^1-1/k^ ) is reference from wiki. +
`query()` and `rangeQuery()` will run `build()` first if you called `insert()`
before call them. And `build()` is very slow, so you should not use this class
as a dynamic tree

'''

=== meow:: *SplayTree<Key, Value>* (C++ class)
.Description
Like `std::map`, `SplayTree` is an dictionary(key->value). But it has
some extra method, such as `split()`, `merge()`, `keyOffset()`.

.Data Type
* `Key` is the tyepname of the key
* `Value` is the typename of value
* `SplayTree<Key, Value>:: *Element* ` is a typename which contain
(key->value). It has some methods below:
** `->first ` a constant reference to `Key`
** `->second` a reference to `Value`
** `operator==, operator!=` compare function, check if the two `Element`
is pointer to the same (key->value)

.Template Request
* `Key` should has `operator<`, `operator+`

.Support Methods
* N <- numbers of element in the SplayTree
* M <- numbers of element in another SplayTree
[options="header",width="100%",cols="1>,1<s,5<,1<,3^,10<",grid="rows"]
|=======================================================================
|Const?|Name| Parameters| Return Type| Time Complexity| Description
||operator=|(SplayTree const&)| *this | O(N) | copy operator
||moveTo|(SplayTree* t)|void|O(M)| Transform the data in this to `t`
|const|lowerBound|(Key k)|Element|O(logN)| Find the smallest (key->value) 
which `k <= key` and return
|const|upperBound|(Key k)|Element|O(logN)| Find the smallest (key->value) 
which `k < key` and return
|const|rLowerBound|(Key k)|Element|O(logN)| Find the largest (key->value) 
which `key <= k` and return
|const|rUpperBound|(Key k)|Element|O(logN)| Find the largest (key->value) 
which `key < k` and return
|const| find|(Key k)|Element|O(logN)| Find the element (key->value) which
`key == k` and return
|const|order|(size_t k)|Element|O(logN)| Find the `k`-th small element.
note that `k` start from zero like a normal C/C++ array.
|const|first|()|Element|O(logN)| Return the smallest element
|const|last|()|Element|O(logN)| Return the largest element
|const|end|()|Element|O(1)|Return an empty element(it can be use to 
check if `find()` is successful)
|const|size|()|size_t|O(1)| Return number of elements in the tree
|const|empty|()|bool|O(1)|Return whether the tree is empty
||clear|()|void|O(N)|Clear
||keyOffset|(Key offset)|void|O(1)| Let all the keys in the tree
plus offset
||insert|(Key k, Value v)|bool | O(logN)| Insert an element.
If the tree already has an element with same key, return `false`.
||erase|(Key k)|bool | O(logN)|Erase an element from the tree with
given key. Return `false` if the element not found.
||operator[]|(Key k)|Value|O(logN)|Like `find()` , but it will insert an element
automatic if the corrosponding element not found
||splitOut|(Key const& upper_bound, +
SplayTree* out)|void | O(log N) | Split out all the elements with key
larger than `upper_bound` and store then into `out`
||mergeAfter|(SplayTree* t)|bool|O(logN + logM)|If not all of the elements in this
are smaller than elements in `t`, return `false` , else merge `t` into
itself and return `true`.
||merge|(SplayTree* t)|bool|O(logN + logM)|If all of the elements in this
are smaller than elements in `t` or all of the elements in this larger than 
elements in `t` , merge `t` into itself and return `true`.
Else return `false`
|=======================================================================
WARNING: Consider there are two SplayTree `A` and `B`. +
`B` will become empty after you call `A.mergeAfter(&B)`
or `A.merge(&B)` successful. +
The data in `B` will override by data in `A` and `A` will become empty after
you call `A.moveTo(&B)`

'''

=== meow:: *SegmentTree<Value>* (C++ class)
.Description
`SegmentTree` is a data structure that can maintain an array, and
support *range update* , *range query*

.Template Request
* `Value` should has
** `operator+(Value)` offset
** `operator|(Value)` merge two nodes
** `operator*(size_t)` ??

For example, if you want to maintain *range minimum*

* `Value::operator+(Value v2)` will be `this->realValue + v2.realValue`
* `Value::operator|(Value v2)` will be `std::min(this->realValue, v2.realValue)`
* `Value::operator*(size_t n)` will be `this->realValue`

If you want to maintain *range sum*

* `Value::operator+(Value v2)` will be `this->realValue + v2.realValue`
* `Value::operator|(Value v2)` will be `this->realValue + v2.realValue)`
* `Value::operator*(size_t n)` will be `this->realValue * n`

.Support methods
* N <- array size
[options="header",width="100%",cols="1>,1<s,3<,1<,1<,10<",grid="rows"]
|=======================================================================
|Const?|Name| Parameters| Return Type| Time Complexity| Description
||reset|(size_t N)|void|O(1)|
Clear and reset the array size to N (from `0` to `N - 1`)
|const|query|(ssize_t __first, ssize_t __last)|Value|O(logN)|
Range query
||override|(ssize_t __first, ssize_t __last, Value const& __value)|void|
O(logN)| Let the element in the array index from `__first` to `__last`
be `__value`
||offset|(ssize_t __first, ssize_t __last, Value const& __value)|void|
O(logN)| Let the element in the array index from `__first` to `__last`
plus `__value`
|=======================================================================

'''