From c3ddd993afbdfe37e85df4a54738469dcbc0a37c Mon Sep 17 00:00:00 2001 From: cathook Date: Sat, 19 Apr 2014 23:39:29 +0800 Subject: Add description --- README.asciidoc | 357 +++++++- README.html | 1845 ++++++++++++++++++++++++++++++++++++++ description.asciidoc | 38 +- meowpp/Usage.h | 63 +- meowpp/dsa/DisjointSet.h | 26 + meowpp/dsa/Heaps.h | 84 +- meowpp/dsa/KD_Tree.h | 42 + meowpp/dsa/MergeableHeap.hpp | 3 - meowpp/dsa/SegmentTree.h | 92 ++ meowpp/dsa/SegmentTree.hpp | 172 ++++ meowpp/dsa/SplayTree.h | 75 ++ meowpp/oo/Register_Implement.h | 20 + meowpp/oo/Register_Implement.hpp | 5 +- meowpp/utility.h | 55 +- readme_generate.py | 6 +- 15 files changed, 2827 insertions(+), 56 deletions(-) create mode 100644 README.html create mode 100644 meowpp/dsa/SegmentTree.h create mode 100644 meowpp/dsa/SegmentTree.hpp diff --git a/README.asciidoc b/README.asciidoc index 8058527..3b3c9d7 100644 --- a/README.asciidoc +++ b/README.asciidoc @@ -1,14 +1,202 @@ -==== hi!! += meow -=== MergeableHeap + +== 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 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......` + +''' + +=== 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` + +''' + +=== meow:: *ImplementInterface/RegisterInterface* (C++ Class) .Description -MergeableHeap is a kind of maximum-heap with an extra method `merge`, -which will merge another MergeableHeap into itself. +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` , and call the constructure with giving +`identify` (type `T` ) . +* Create an object, type `RegisterInterface` , 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* (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* (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>,1v) +|| 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|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* (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)` + +''' + +=== 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 + + + + +meow + + + + + +
+
+

Description

+
+

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

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

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 +

    +
      +
    • +

      +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

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

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

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

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

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

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

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

+
+
+
+
+
+
+ + + diff --git a/description.asciidoc b/description.asciidoc index 09b6ef9..f768289 100644 --- a/description.asciidoc +++ b/description.asciidoc @@ -1 +1,37 @@ -== hi! += 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 + diff --git a/meowpp/Usage.h b/meowpp/Usage.h index b98a7ac..22f7329 100644 --- a/meowpp/Usage.h +++ b/meowpp/Usage.h @@ -52,7 +52,6 @@ namespace meow{ }; typedef std::map Options; typedef Options::const_iterator OptionsIterator; - //typedef std::map::const_iterator OptionsIterator; public: Usage(); Usage(String const& _name); @@ -89,6 +88,68 @@ 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- + ******************************************************************/ } #include "Usage.hpp" diff --git a/meowpp/dsa/DisjointSet.h b/meowpp/dsa/DisjointSet.h index 1ea6d97..b33a839 100644 --- a/meowpp/dsa/DisjointSet.h +++ b/meowpp/dsa/DisjointSet.h @@ -24,6 +24,32 @@ namespace meow{ void reset(size_t _n ); 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{ - /********************************************************* - @asciidoc - === MergeableHeap - .Description - MergeableHeap is a kind of maximum-heap with an extra method `merge`, - which will merge another MergeableHeap into itself. - - .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- - *********************************************************/ template class MergeableHeap{ // maximum-heap private: @@ -77,6 +38,51 @@ you call `A.moveTo(&B)` void clear( ); 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- + *********************************************************/ } #include "MergeableHeap.hpp" diff --git a/meowpp/dsa/KD_Tree.h b/meowpp/dsa/KD_Tree.h index 0abc358..2e55d12 100644 --- a/meowpp/dsa/KD_Tree.h +++ b/meowpp/dsa/KD_Tree.h @@ -68,6 +68,48 @@ namespace meow{ void clear(); void reset(size_t _dimension); }; + /********************************************************* + @asciidoc + === meow:: *KD_Tree* (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>,1v) + || 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|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 + +''' +@asciidoc- + *********************************************************/ } #include "KD_Tree.hpp" diff --git a/meowpp/dsa/MergeableHeap.hpp b/meowpp/dsa/MergeableHeap.hpp index de3aea9..6e49a1c 100644 --- a/meowpp/dsa/MergeableHeap.hpp +++ b/meowpp/dsa/MergeableHeap.hpp @@ -1,6 +1,3 @@ -// @class name : MergeableHeap -// @implement : Leftist Tree - #include namespace meow{ diff --git a/meowpp/dsa/SegmentTree.h b/meowpp/dsa/SegmentTree.h new file mode 100644 index 0000000..1aa396d --- /dev/null +++ b/meowpp/dsa/SegmentTree.h @@ -0,0 +1,92 @@ +#ifndef SegmentTree_H__ +#define SegmentTree_H__ + +namespace meow{ + template + class SegmentTree{ + private: + struct Node{ + Value _value; + Value _offset; + bool _sameFlag; + // + Node(); + }; + // + size_t _size; + std::vector _nodes; + size_t const _root; + // + size_t leftChild(size_t __parent) const; + size_t rightChild(size_t __parent) const; + // + void downUpdate(size_t __L, size_t __R, size_t __index); + void override(size_t __l, size_t __r, + size_t __L, size_t __R, + size_t __index, Value const& __value); + void offset(size_t __l, size_t __r, + size_t __L, size_t __R, + size_t __index, Value const& __delta); + Value query(size_t __l, size_t __r, + size_t __L, size_t __R, + size_t __index); + bool rangeCorrect(ssize_t* __first, ssize_t* __last) const; + public: + SegmentTree(); + SegmentTree(size_t __size); + SegmentTree(SegmentTree const& __tree2); + // + void reset(size_t __size); + // + Value query (ssize_t __first, ssize_t __last) const; + void override(ssize_t __first, ssize_t __last, Value const& __value); + void offset (ssize_t __first, ssize_t __last, Value const& __delta); + }; + /********************************************************* + @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 + inline SegmentTree::Node::Node(){ } + + template + inline size_t + SegmentTree::leftChild(size_t __parent) const { + return __parent * 2 + 1; + } + template + inline size_t + SegmentTree::rightChild(size_t __parent) const { + return __parent * 2 + 2; + } + + template + inline void + SegmentTree::downUpdate(size_t __L, size_t __R, size_t __index){ + size_t mid = (__L + __R) / 2; + Value& val = _nodes[__index]._value; + Value& off = _nodes[__index]._offset; + if(_nodes[__index]._sameFlag){ + if(__L < __R){ + override(__L , mid, __L , mid, leftChild(__index), val); + override(mid + 1, __R, mid + 1, __R, rightChild(__index), val); + } + _nodes[__index]._sameFlag = false; + _nodes[__index]._offset = 0; + }else if(!(_nodes[__index]._offset == Value(0))){ + if(__L < __R){ + offset(__L , mid, __L , mid, leftChild(__index), off); + offset(mid + 1, __R, mid + 1, __R, rightChild(__index), off); + } + _nodes[__index]._offset = 0; + } + } + template + inline void + SegmentTree::override(size_t __l, size_t __r, + size_t __L, size_t __R, + size_t __index, Value const& __value){ + if(__l == __L && __r == __R){ + _nodes[__index]._value = __value * (__R - __L + 1); + _nodes[__index]._offset = 0; + _nodes[__index]._sameFlag = true; + return ; + } + downUpdate(__L, __R, __index); + size_t mid = (__L + __R) / 2; + if(__r <= mid){ + override(__l, __r, __L , mid, leftChild(__index), __value); + }else if(mid + 1 <= __l){ + override(__l, __r, mid + 1, __R, rightChild(__index), __value); + }else{ + override(__l , mid, __L , mid, leftChild(__index), __value); + override(mid + 1, __r, mid + 1, __R, rightChild(__index), __value); + } + _nodes[__index]._value = ( _nodes[ leftChild(__index)]._value + | _nodes[rightChild(__index)]._value); + } + template + inline void + SegmentTree::offset(size_t __l, size_t __r, + size_t __L, size_t __R, + size_t __index, Value const& __delta){ + if(__l == __L && __r == __R){ + _nodes[__index]._value = _nodes[__index]._value + __delta*(__R-__L+1); + if(!_nodes[__index]._sameFlag){ + _nodes[__index]._offset = _nodes[__index]._offset + __delta; + } + return ; + } + downUpdate(__L, __R, __index); + size_t mid = (__L + __R) / 2; + if(__r <= mid){ + offset(__l, __r, __L , mid, leftChild(__index), __delta); + }else if(mid + 1 <= __l){ + offset(__l, __r, mid + 1, __R, rightChild(__index), __delta); + }else{ + offset(__l , mid, __L , mid, leftChild(__index), __delta); + offset(mid + 1, __r, mid + 1, __R, rightChild(__index), __delta); + } + _nodes[__index]._value = ( _nodes[ leftChild(__index)]._value + | _nodes[rightChild(__index)]._value); + } + template + inline Value + SegmentTree::query(size_t __l, size_t __r, + size_t __L, size_t __R, + size_t __index){ + if((__l == __L && __r == __R) || _nodes[__index]._sameFlag){ + return _nodes[__index]._value; + } + size_t mid = (__L + __R) / 2; + Value& off = _nodes[__index]._offset; + if(__r <= mid){ + return query(__l, __r, __L , mid, leftChild(__index)) + off; + }else if(mid + 1 <= __l){ + return query(__l, __r, mid + 1, __R, rightChild(__index)) + off; + }else{ + return ( query(__l , mid, __L , mid, leftChild(__index)) + | query(mid + 1, __r, mid + 1, __R, rightChild(__index))) + off; + } + } + template + inline bool + SegmentTree::rangeCorrect(ssize_t* __first, ssize_t* __last) const{ + if(*__last < *__first){ + return false; + } + if(*__last < 0 || _size - 1 < *__first){ + return false; + } + *__first = inRange((ssize_t)0, (ssize_t)_size - 1, *__first); + *__last = inRange((ssize_t)0, (ssize_t)_size - 1, *__last ); + return true; + } + + template + inline + SegmentTree::SegmentTree(): _size(0), _root(0) { + } + template + inline + SegmentTree::SegmentTree(size_t __size): _size(0), _root(0){ + reset(__size); + } + template + inline + SegmentTree::SegmentTree(SegmentTree const& __tree2): + _size(__tree2._size), _nodes(__tree2._nodes), _root(0){ } + // + template + inline void + SegmentTree::reset(size_t __size){ + _size = __size; + _nodes.resize(__size * 4); + _nodes[_root]._sameFlag = true; + _nodes[_root]._value = Value(0); + } + template + inline Value + SegmentTree::query(ssize_t __first, ssize_t __last) const{ + if(rangeCorrect(&__first, &__last) == false){ + return Value(); + } + return ((SegmentTree*)this)->query(__first, __last, 0, _size - 1, _root); + } + template + inline void + SegmentTree::override(ssize_t __first, ssize_t __last, + Value const& __value){ + if(rangeCorrect(&__first, &__last) == false){ + return ; + } + override(__first, __last, 0, _size - 1, _root, __value); + } + template + inline void + SegmentTree::offset(ssize_t __first, ssize_t __last, + Value const& __delta){ + if(rangeCorrect(&__first, &__last) == false){ + return ; + } + offset(__first, __last, 0, _size - 1, _root, __delta); + } +} + +#endif diff --git a/meowpp/dsa/SplayTree.h b/meowpp/dsa/SplayTree.h index 78b54f6..3d2d2e3 100644 --- a/meowpp/dsa/SplayTree.h +++ b/meowpp/dsa/SplayTree.h @@ -96,6 +96,81 @@ namespace meow{ // void print() const; }; + /********************************************************* + @asciidoc + === meow:: *SplayTree* (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- + *********************************************************/ } #include "SplayTree.hpp" diff --git a/meowpp/oo/Register_Implement.h b/meowpp/oo/Register_Implement.h index e46f86c..dd496fa 100644 --- a/meowpp/oo/Register_Implement.h +++ b/meowpp/oo/Register_Implement.h @@ -26,6 +26,26 @@ namespace meow{ virtual ImplementInterface* getImplement(T const& identify); virtual ~RegisterInterface(){ } }; + /******************************************************************* + @asciidoc + === 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` , and call the constructure with giving + `identify` (type `T` ) . + * Create an object, type `RegisterInterface` , 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. + + ''' + @asciidoc- + ******************************************************************/ } #include "Register_Implement.hpp" diff --git a/meowpp/oo/Register_Implement.hpp b/meowpp/oo/Register_Implement.hpp index 523f266..34d9129 100644 --- a/meowpp/oo/Register_Implement.hpp +++ b/meowpp/oo/Register_Implement.hpp @@ -13,9 +13,8 @@ namespace meow{ return true; } template - inline ImplementInterface* RegisterInterface::getImplement( - T const& identify - ){ + inline ImplementInterface* + RegisterInterface::getImplement(T const& identify){ if(implements.find(identify) == implements.end()){ return NULL; } diff --git a/meowpp/utility.h b/meowpp/utility.h index 156971a..4f3b36a 100644 --- a/meowpp/utility.h +++ b/meowpp/utility.h @@ -6,7 +6,6 @@ #include namespace meow{ - inline std::string stringPrintf(char const * fmt, ...); inline std::string stringReplace(std::string str, std::string const& from, @@ -40,6 +39,60 @@ namespace meow{ inline double average(T const& beg, T const& end, double sigs); 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- + ******************************************************************/ } #include "utility.hpp" diff --git a/readme_generate.py b/readme_generate.py index 781e2d3..7eb6782 100755 --- a/readme_generate.py +++ b/readme_generate.py @@ -76,11 +76,15 @@ readme_f = open(readme, 'w'); for (root, sub_folders, files) in os.walk('./'): for reader in readers: + deleted = [] for filename in files: path = os.path.join(root, filename); if path == './' + readme: continue; if reader.checkOk(filename): + print 'Get asciidoc from ' + path; readme_f.write(reader.read(path)); - files.remove(filename); + deleted.append(filename); + for filename in deleted: + files.remove(filename); readme_f.close(); -- cgit v1.2.3