diff options
Diffstat (limited to 'meowpp')
| -rw-r--r-- | meowpp/Usage.h | 63 | ||||
| -rw-r--r-- | meowpp/dsa/DisjointSet.h | 26 | ||||
| -rw-r--r-- | meowpp/dsa/Heaps.h | 84 | ||||
| -rw-r--r-- | meowpp/dsa/KD_Tree.h | 42 | ||||
| -rw-r--r-- | meowpp/dsa/MergeableHeap.hpp | 3 | ||||
| -rw-r--r-- | meowpp/dsa/SegmentTree.h | 92 | ||||
| -rw-r--r-- | meowpp/dsa/SegmentTree.hpp | 172 | ||||
| -rw-r--r-- | meowpp/dsa/SplayTree.h | 75 | ||||
| -rw-r--r-- | meowpp/oo/Register_Implement.h | 20 | ||||
| -rw-r--r-- | meowpp/oo/Register_Implement.hpp | 5 | ||||
| -rw-r--r-- | meowpp/utility.h | 55 |
11 files changed, 590 insertions, 47 deletions
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<unsigned char, Option> Options; typedef Options::const_iterator OptionsIterator; - //typedef std::map<unsigned char, Option>::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的預設值以及哪些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` + +''' +@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<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. + +''' +@asciidoc- + *********************************************************/ } #include "DisjointSet.hpp" diff --git a/meowpp/dsa/Heaps.h b/meowpp/dsa/Heaps.h index cac3e01..1e47afd 100644 --- a/meowpp/dsa/Heaps.h +++ b/meowpp/dsa/Heaps.h @@ -4,45 +4,6 @@ #include <cstdlib> namespace meow{ - /********************************************************* - @asciidoc - === MergeableHeap<Key, Value> - .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>,1<s,5<,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)` - @asciidoc- - *********************************************************/ template<class Element> class MergeableHeap{ // maximum-heap private: @@ -77,6 +38,51 @@ you call `A.moveTo(&B)` void clear( ); void merge(MergeableHeap* _heap2); }; + + /********************************************************* + @asciidoc + === 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)` + +''' +@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<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 + +''' +@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 <cstdlib> 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 Value> + class SegmentTree{ + private: + struct Node{ + Value _value; + Value _offset; + bool _sameFlag; + // + Node(); + }; + // + size_t _size; + std::vector<Node> _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<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` + |======================================================================= + +''' +@asciidoc- + *********************************************************/ +} + +#endif diff --git a/meowpp/dsa/SegmentTree.hpp b/meowpp/dsa/SegmentTree.hpp new file mode 100644 index 0000000..24efcdd --- /dev/null +++ b/meowpp/dsa/SegmentTree.hpp @@ -0,0 +1,172 @@ +#ifndef SegmentTree_H__ +#define SegmentTree_H__ + +namespace meow{ + template<class Value> + inline SegmentTree<Value>::Node::Node(){ } + + template<class Value> + inline size_t + SegmentTree<Value>::leftChild(size_t __parent) const { + return __parent * 2 + 1; + } + template<class Value> + inline size_t + SegmentTree<Value>::rightChild(size_t __parent) const { + return __parent * 2 + 2; + } + + template<class Value> + inline void + SegmentTree<Value>::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<class Value> + inline void + SegmentTree<Value>::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<class Value> + inline void + SegmentTree<Value>::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<class Value> + inline Value + SegmentTree<Value>::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<class Value> + inline bool + SegmentTree<Value>::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<class Value> + inline + SegmentTree<Value>::SegmentTree(): _size(0), _root(0) { + } + template<class Value> + inline + SegmentTree<Value>::SegmentTree(size_t __size): _size(0), _root(0){ + reset(__size); + } + template<class Value> + inline + SegmentTree<Value>::SegmentTree(SegmentTree const& __tree2): + _size(__tree2._size), _nodes(__tree2._nodes), _root(0){ } + // + template<class Value> + inline void + SegmentTree<Value>::reset(size_t __size){ + _size = __size; + _nodes.resize(__size * 4); + _nodes[_root]._sameFlag = true; + _nodes[_root]._value = Value(0); + } + template<class Value> + inline Value + SegmentTree<Value>::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<class Value> + inline void + SegmentTree<Value>::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<class Value> + inline void + SegmentTree<Value>::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<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)` + +''' +@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<T>* 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<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. + + ''' + @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<class T> - inline ImplementInterface<T>* RegisterInterface<T>::getImplement( - T const& identify - ){ + inline ImplementInterface<T>* + RegisterInterface<T>::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 <cctype> 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<class T> 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> |(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......` + +''' +@asciidoc- + ******************************************************************/ } #include "utility.hpp" |