aboutsummaryrefslogtreecommitdiffstats
path: root/meowpp
diff options
context:
space:
mode:
Diffstat (limited to 'meowpp')
-rw-r--r--meowpp/Usage.h123
-rw-r--r--meowpp/dsa/DisjointSet.h71
-rw-r--r--meowpp/dsa/KD_Tree.h120
-rw-r--r--meowpp/dsa/MergeableHeap.h131
-rw-r--r--meowpp/dsa/MergeableHeap.hpp2
-rw-r--r--meowpp/dsa/SegmentTree.h100
-rw-r--r--meowpp/dsa/SplayTree.h241
-rw-r--r--meowpp/dsa/SplayTree.hpp2
-rw-r--r--meowpp/utility.h121
9 files changed, 526 insertions, 385 deletions
diff --git a/meowpp/Usage.h b/meowpp/Usage.h
index 22f7329..d2ef083 100644
--- a/meowpp/Usage.h
+++ b/meowpp/Usage.h
@@ -88,68 +88,67 @@ namespace meow{
Strings usage_end ;
Strings proc_arguments;
};
- /*******************************************************************
- @asciidoc
- === meow:: *Usage* (C++ Class)
- .Description
- `Usage` 是用來分析argc, argv和輸出usage document的class.
- argc, argv的部份, 有以下規則
-
- * `-c` 其中 `c` 可以代換成正常的一個字元的字符,
- 這種選像要嘛就是 *有設置* , 不然就是 *沒設置*
- * `-c <value>` 附加一個value, 這種選項可以是選擇性 ,即要設定與否都可以,
- 反之則一定要設定. 另外可以給定value的預設值以及哪些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-
- ******************************************************************/
+ //# === 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`
+ //#==================================
+ //#
+ //#'''
}
#include "Usage.hpp"
diff --git a/meowpp/dsa/DisjointSet.h b/meowpp/dsa/DisjointSet.h
index b33a839..b918adb 100644
--- a/meowpp/dsa/DisjointSet.h
+++ b/meowpp/dsa/DisjointSet.h
@@ -1,10 +1,18 @@
#ifndef DisjointSet_H__
#define DisjointSet_H__
+
#include <vector>
#include <cstdlib>
namespace meow{
+ //#
+ //#=== meow:: *DisjointSet* (C++ class)
+ //#==== Description
+ //# `DisjointSet` 是個*輕量級Data Dtructure*, 用來維護一堆互斥集的資訊.
+ //# 相關資料可參考
+ //# link:http://www.csie.ntnu.edu.tw/~u91029/DisjointSets.html[演算法筆記]
+ //#
class DisjointSet{
private:
size_t n;
@@ -17,39 +25,46 @@ namespace meow{
DisjointSet();
DisjointSet(size_t _n);
DisjointSet(DisjointSet const& dsj);
- //
+
+ //#==== Support Methods
+ //#
+ //#[options="header",width="100%",cols="1>m,3>s,7<,3<,3^,20<",grid="rows"]
+ //#|=====================================================================
+ //#|Const?|Name | Parameters | Return_Type| Time_Complexity| Description
+
+
+ //#|const |root |(size_t `number`) | size_t | very fast
+ //#|回傳 `number` 所在的 *集合的編號* (0~N-1)
size_t root (size_t a ) const;
+
+
+ //#|const |size |() | size_t | very fast
+ //#|回傳 *總集合大小*
size_t size ( ) const;
- //
+
+
+ //#| |reset|(size_t `N`) | void | O(N)
+ //#| 清空, 並且設定總集合大小為 `N`
void reset(size_t _n );
+
+
+ //#| |merge|(size_t `number1`,\size_t `number2`)| size_t | very fast
+ //#| 將 `number1` 所在的集合 跟 `number2` 所在的集合 *合併*,
+ //# 並回傳合併後新的集合的編號
size_t merge(size_t a, size_t b);
+
+
+ //#|=====================================================================
};
- /*********************************************************
- @asciidoc
- === meow:: *DisjointSet* (C++ class)
- .Description
- `DisjointSet` is a lighting data structure that maintain N numbers from
- *0* to *N-1* with methods below:
-
- [options="header",width="100%",cols="1>,1<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-
- *********************************************************/
+ //#
+ //#[NOTE]
+ //#========================================
+ //# * *very fast* 表示它算的真的超級快, 可以視為常數時間.
+ //# * 預設值所有 `number` 所在的集合的編號就是 `number` 本身,
+ //# 即沒有任兩個數在同一個set裡面
+ //#========================================
+ //#
+ //# '''
}
#include "DisjointSet.hpp"
diff --git a/meowpp/dsa/KD_Tree.h b/meowpp/dsa/KD_Tree.h
index 2ba81a1..035d6eb 100644
--- a/meowpp/dsa/KD_Tree.h
+++ b/meowpp/dsa/KD_Tree.h
@@ -8,6 +8,24 @@
#include <utility.h>
namespace meow{
+ //#
+ //#=== meow:: *KD_Tree<Vector, Scalar>* (C++ class)
+ //#==== Description
+ //# `KD_Tree` 全名k-dimension tree, 用來維護由 *N個K維度向量所成的集合*,
+ //# 並可於該set中查找 *前i個離給定向量最接近的向量*
+ //#
+ //#==== Template Class Operators Request
+ //#[options="header",width="70%",cols="1>m,1<,3<s,5<,3<,15<",grid="rows"]
+ //#|=====================================================================
+ //#|Const?|Typename| Operator | Parameters | Return_Type| Description
+ //#|const | Vector|operator[] |(size_t `n`) | Scalar | 取得第 `n` 維度量
+ //#|const | Vector|operator< |(Vector `v`) | bool | 權重比較
+ //#|const | Scalar|operator* |(Scalar `s`) | Scalar | 相乘
+ //#|const | Scalar|operator+ |(Scalar `s`) | Scalar | 相加
+ //#|const | Scalar|operator- |(Scalar `s`) | Scalar | 相差
+ //#|const | Scalar|operator< |(Scalar `s`) | bool | 大小比較
+ //#|=====================================================================
+ //#
template<class Vector, class Scalar>
class KD_Tree{
private:
@@ -68,68 +86,76 @@ namespace meow{
std::vector<size_t>* __orders,
int __depth);
public:
+ //#==== Custom Type Definitions
+ //# * `Vectors` <- `std::vector<Vector>`
+ //#
typedef typename std::vector<Vector> Vectors;
//
KD_Tree();
KD_Tree(size_t __dimension);
~KD_Tree();
- //
+
+ //#==== Support Methods
+ //#
+ //# * N <- `this` 中擁有的資料數
+ //# * K <- `this` 資料維度
+ //#
+ //#[options="header",width="100%",cols="1>m,3>s,7<,3<,3^,20<",grid="rows"]
+ //#|=====================================================================
+ //#|Const?|Name | Parameters | Return_Type| Time_Complexity| Description
+
+
+ //#||insert|(Vector const& `v`)|void| O(1)
+ //#|將向量 `v` 加到set中
void insert(Vector const& __vector);
+
+
+ //#||erase|(Vector const& `v`)|bool| O(N)
+ //#|將向量 `v` 從set中移除, '~TODO:可以再優化~'
bool erase (Vector const& __vector);
+
+
+ //#||build|()|void|O(KN logN) or O(1)
+ //#|檢查距上一次 `build()` 至今是否有 `insert/erase` 被呼叫,
+ //# 若有, 重新建樹, 否則不做事
void build();
+
+
+ //#||forceBuild|()|void|O(KN logN)
+ //#|重新建樹
void forceBuild();
- //
+
+
+ //#|const|query|(Vector const& `v`,\size_t `i`,\bool `cmp`)|Vectors
+ //#|O(KN ^1-1/K^ )
+ //#|於set中找尋距離 `v` 前 `i` 近的向量, 並依照由近而遠的順序排序.
+ //# 如果有兩個向量 `v1`,`v2` 距離一樣, 且 `cmp` 為 `true` , 則直接依照
+ //# `v1 < v2` 來決定誰在前面. 最後回傳一陣列包含所有解.
Vectors query(Vector const& __vector,
size_t __nearestNumber,
bool __compareWholeVector) const;
- //
+
+
+ //#||clear|()|void|O(1)
+ //#|清空所有資料
void clear();
+
+
+ //#||reset|(size_t `dimension`)|void|O(1)
+ //#|清空所有資料並且指定維度為 `dimension`
void reset(size_t __dimension);
+
+
+ //#|=====================================================================
};
- /*********************************************************
- @asciidoc
- === meow:: *KD_Tree<Vector, Scalar>* (C++ class)
- .Description
- `KD_Tree` is *K-dimension tree*, which is a multiple set contain lots of
- vector with K dimension.
-
- .Template Request
- * `Vector` should has `operator[]` to allow the KD_Tree, `operator<` to
- compare when two vector are point to the same place, `operator==`
- access the k-dimensions
- * `Scalar` should has `operator*`, `operator+`, `operator<`
-
- .Support Methods
- * N <- numbers of element in the kd-tree
- * K <- dimensions
- * `Vector` is the tyepname of the vector
- * `Vectors` is the typename of the std::vector<Vector>
- [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|(Vector const& v)|void|O(1)|Insert a vector
- ||erase |(Vector const& v)|bool|O(N*x)| Find a vector which is the same
- as `v` and remove it from the KD_Tree, `x` in the Big-O time complex
- is cost by `Vector::operator==`.
- || build|()|void|O(KN logN) if need | Build the data structure if need.
- || forceBuild|()|void|O(KN logN) | Build the data structure(the `insert()`
- method will not build the data structure immediately)
- |const|query|(Vector const& v, int k)|Vectors|O(kN ^1-1/k^ ) |
- Using Euclidean-Distance to find the 1st to k-th nearest neighbor from `v` .
- And return;
- ||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-
- *********************************************************/
+ //#
+ //#[NOTE]
+ //#========================================
+ //# * 此資料結構只有在 N >> 2 ^K^ 時才比較有優勢,
+ //# 當 K 逐漸變大時, 所花時間會跟暴搜沒兩樣
+ //#========================================
+ //#
+ //# '''
}
#include "KD_Tree.hpp"
diff --git a/meowpp/dsa/MergeableHeap.h b/meowpp/dsa/MergeableHeap.h
index 1e47afd..c1a2460 100644
--- a/meowpp/dsa/MergeableHeap.h
+++ b/meowpp/dsa/MergeableHeap.h
@@ -4,6 +4,19 @@
#include <cstdlib>
namespace meow{
+ //#
+ //#=== meow:: *MergeableHeap<Element>* (C++ class)
+ //#==== Description
+ //# 一個用 *左偏樹* 實作的 *Maximum-Heap* , 除了原本heap有的功能外,
+ //# 還支援 `merge`, `split` 等功能
+ //#
+ //#==== Template Class Operators Request
+ //#[options="header",width="70%",cols="1>m,1<,3<s,5<,3<,15<",grid="rows"]
+ //#|=====================================================================
+ //#|Const?|Typename| Operator | Parameters | Return_Type| Description
+ //#|const |Element |operator< |(Element `v`)| bool | 大小比較
+ //#|=====================================================================
+ //#
template<class Element>
class MergeableHeap{ // maximum-heap
private:
@@ -23,66 +36,70 @@ namespace meow{
public:
MergeableHeap();
MergeableHeap(MergeableHeap const& _heap2);
- //
- ~MergeableHeap();
- //
MergeableHeap& operator=(MergeableHeap const& _heap2);
- void moveTo(MergeableHeap* _heap2);
- //
- Element const& top () const;
- size_t size () const;
- size_t empty() const;
- //
- void push (Element const& _value);
- void pop ( );
- void clear( );
+ ~MergeableHeap();
+
+ //#==== Support Methods
+ //#
+ //# * N <- `this` 中擁有的資料數
+ //#
+ //#[options="header",width="100%",cols="1>m,2>s,7<,3<,3^,20<",grid="rows"]
+ //#|=====================================================================
+ //#|Const?|Name | Parameters | Return_Type| Time_Complexity| Description
+
+
+ //#||moveTo|(MergeableHeap* `h`)|void|O(M)
+ //#|將 `this` 的資料複寫到 `h` 上面, 同時清空自己,
+ //# 時間複雜度中的M是 `h` 所擁有的資料數
+ void moveTo(MergeableHeap* _heap2);
+
+
+ //#|const|top|()|Element const&|O(1)
+ //#|回傳最大的那個 `Element`
+ Element const& top() const;
+
+
+ //#|const|size|()|size_t|O(1)
+ //#|回傳 `this` 中擁有的資料數
+ size_t size() const;
+
+
+ //#|const|empty|()|bool|O(1)
+ //#|回傳 `this` 是否為空
+ bool empty() const;
+
+
+ //#||push|(Element const& `e`)|void|O(logN)
+ //#|將 `e` 加入
+ void push(Element const& _value);
+
+
+ //#||pop|()|void|O(logN)
+ //#|將最大的 `Element` 移除
+ void pop();
+
+
+ //#||clear|()|void|O(N)
+ //#|將資料清空
+ void clear();
+
+
+ //#||merge|(MergeableHeap* `heap2`)|void|O(logN+logM)
+ //#|將 `heap2` 的資料統統加到 `this` 中, 並且清空 `heap2`
+ //# 時間複雜度中的M是 `heap2` 的資料數
void merge(MergeableHeap* _heap2);
+
+ //#|==============================================
};
-
- /*********************************************************
- @asciidoc
- === meow:: *MergeableHeap<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-
- *********************************************************/
+ //# [WARNING]
+ //#==============================================
+ //# * 假設現在有兩個MergeableHeap `A` 和 `B`, 則:
+ //# ** 執行 `A.merge(&B)` 後 `B` 會變成空的
+ //# ** 執行 `B.moveTo(&A)` 後 `B` 會變成空的, `A` 原本擁有的資料也會覆蓋掉
+ //#==============================================
+ //#
+ //# '''
+ //#
}
#include "MergeableHeap.hpp"
diff --git a/meowpp/dsa/MergeableHeap.hpp b/meowpp/dsa/MergeableHeap.hpp
index be7dcea..e7f5978 100644
--- a/meowpp/dsa/MergeableHeap.hpp
+++ b/meowpp/dsa/MergeableHeap.hpp
@@ -92,7 +92,7 @@ namespace meow{
return (root == NULL ? 0 : root->weight);
}
template<class Element> // empty
- inline size_t MergeableHeap<Element>::empty() const{ return (size() == 0); }
+ inline bool MergeableHeap<Element>::empty() const{ return (size() == 0); }
//////////////////////////////////////////////////////////
// **# MergeableHeap -- update: push, pop, merge #** //
//////////////////////////////////////////////////////////
diff --git a/meowpp/dsa/SegmentTree.h b/meowpp/dsa/SegmentTree.h
index 585ea5d..89fd5d9 100644
--- a/meowpp/dsa/SegmentTree.h
+++ b/meowpp/dsa/SegmentTree.h
@@ -2,6 +2,30 @@
#define SegmentTree_H__
namespace meow{
+ //#
+ //#=== meow:: *SegmentTree<Value>* (C++ class)
+ //#==== Description
+ //# 維護一個陣列, 並且讓user可以有區間查詢, 區間修改的小東東
+ //#
+ //#==== Template Class Operators Request
+ //#[options="header",width="70%",cols="1>m,1<,3<s,5<,3<,15<",grid="rows"]
+ //#|=====================================================================
+ //#|Const?|Typename| Operator | Parameters |Return_Type| Description
+ //#|const |Value |operator+ |(Value `v`)|Value | 相加(位移)
+ //#|const |Value |operator* |(size_t `n`)|Value | 每個Value都一樣,
+ //# 長為 `n` 的區間的值
+ //#|const |Value |operator{b}|(Value `v`)|Value | 區間合併後的值
+ //#|=====================================================================
+ //#
+ //# * 若要維護區間最小值, 即每次都是詢問範圍 `[a, b]` 的最小值, 則可以定義
+ //# ** `operator+` 為 '回傳相加值'
+ //# ** `operator*` 為 '回傳*this'
+ //# ** `operator|` 為 '回傳std::min(*this, v)'
+ //# * 若要維護區間最總和, 即每次都是詢問範圍 `[a, b]` 的總和, 則可以定義
+ //# ** `operator+` 為 '回傳相加值'
+ //# ** `operator*` 為 '回傳(*this) * n'
+ //# ** `operator|` 為 '回傳相加值'
+ //#
template<class Value>
class SegmentTree{
private:
@@ -28,11 +52,38 @@ namespace meow{
SegmentTree(size_t __size);
SegmentTree(SegmentTree const& __tree2);
//
+ //#==== Support Methods
+ //#
+ //# * N <- `this` 所維護的陣列長度
+ //#
+ //#[options="header",width="100%",cols="1>m,2>s,7<,3<,3^,20<",grid="rows"]
+ //#|=====================================================================
+ //#|Const?|Name | Parameters | Return_Type| Time_Complexity| Description
+
+
+ //#||reset|(size_t `size`)|void|O(1)
+ //#|將資料清空且設定維護範圍是 `0~size - 1` 其中時間複雜度確切多少未知
+ //# 要看 `std::vector::resize()` 的效率
void reset(size_t __size);
- //
+
+
+ //#|const|query|(ssize_t `first`,\ssize_t `last`)|Value|O(logN)
+ //#|回傳區間 `[first,last]` (邊界都含) 的區間值
Value query (ssize_t __first, ssize_t __last) const;
+
+
+ //#||override|(ssize_t `first`,\ssize_t `last`,\Value const& `value`)
+ //#|void|O(logN)
+ //#|將區間 `[first,last]` 全部都設定成 `value`
void override(ssize_t __first, ssize_t __last, Value const& __value);
+
+
+ //#||offset|(ssize_t `first`,\ssize_t `last`,\Value const& `delta`)
+ //#|void|O(logN)
+ //#|將區間 `[first,last]` 全部都加上 `delta`
void offset (ssize_t __first, ssize_t __last, Value const& __delta);
+
+ //
void print(){
for(int i = 0; i < _size; i++){
query(i, i);
@@ -52,52 +103,9 @@ namespace meow{
printf("\n");
}
}
+
+ //#|==============================================
};
- /*********************************************************
- @asciidoc
- === meow:: *SegmentTree<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-
- *********************************************************/
}
#include "SegmentTree.hpp"
diff --git a/meowpp/dsa/SplayTree.h b/meowpp/dsa/SplayTree.h
index f738ded..f8cdd20 100644
--- a/meowpp/dsa/SplayTree.h
+++ b/meowpp/dsa/SplayTree.h
@@ -4,6 +4,22 @@
#include "utility.h"
namespace meow{
+ //#
+ //#=== meow:: *SplayTree<Key, Value>* (C++ class)
+ //#==== Description
+ //# `SplayTree` 是一種神乎其技的資料結構, 維護一堆 Key->Value . 並且支援
+ //# 一些 `std::map` 難以快速實踐的操作, 如 `split` , `merge` , `keyOffset`
+ //#
+ //#==== Template Class Operators Request
+ //#[options="header",width="70%",cols="1>m,1<,3<s,5<,3<,15<",grid="rows"]
+ //#|=====================================================================
+ //#|Const?|Typename| Operator| Parameters | Return_Type| Description
+ //#|const |Key |operator+|(Key `k`) | Key | 相加
+ //#|const |Key |operator<|(Key `k`) | bool | 大小比較
+ //#| |Key |'Key' |(int `n`) | | 建構子, `n` 永遠是0
+ //#| |Value | 'Value' |( ) | | 建構子
+ //#|=====================================================================
+ //#
template<class Key, class Value>
class SplayTree{
private:
@@ -44,6 +60,14 @@ namespace meow{
//
void print(Node* __now, int __depth) const;
public:
+ //#==== Custom Type Definitions
+ //#
+ //# * `Element` -> 用來當作回傳資料的媒介
+ //# ** 重定義 `operator->()` 到 `std::pair<Key const&, Value&>*`
+ //# ** 重定義 `operator*()` 到 `std::pair<Key const&, Value&>&`
+ //# ** 有 `operator==` , `operator!=`, `operator=` 可用
+ //# ** 可以直接用 `(*e).second = some_value` 來改變SplayTree中的資料
+ //#
class Element{
private:
typedef std::pair<Key const&, Value&> Entry;
@@ -69,109 +93,146 @@ namespace meow{
SplayTree();
SplayTree(SplayTree const& __tree2);
~SplayTree();
- //
SplayTree& operator=(SplayTree const& __tree2);
- void moveTo(SplayTree* __tree2);
//
+ //#==== Support Methods
+ //#
+ //# * N <- `this` 中擁有的資料數
+ //# * M <- `tree2` 中擁有的資料數
+ //#
+ //#[options="header",width="100%",cols="1>m,3>s,7<,3<,3^,20<",grid="rows"]
+ //#|=====================================================================
+ //#|Const?|Name | Parameters | Return_Type| Time_Complexity| Description
+
+
+ //#||moveTo|(SplayTree* `tree2`)|void|O(M)
+ //#|將 `this` 的資料複寫到 `tree2` 上面, 同時清空自己,
+ //# 時間複雜度中的M是 `tree2` 所擁有的資料數
+ void moveTo(SplayTree* __tree2);
+
+
+ //#|const|lowerBound|(Key const& `k`)|Element|O(logN)
+ //#|找出第一個(最小的) Element且 `k` <= 它的 Key, 並且回傳之.
+ //# 找不到的話回傳 `this->end()`
Element lowerBound(Key const& __key) const;
+
+
+ //#|const|lowerBound|(Key const& `k`)|Element|O(logN)
+ //#|找出第一個(最小的) Element且 `k` < 它的 Key, 並且回傳之.
+ //# 找不到的話回傳 `this->end()`
Element upperBound(Key const& __key) const;
+
+
+ //#|const|lowerBound|(Key const& `k`)|Element|O(logN)
+ //#|找出第一個(最小的) Element且 `k` >= 它的 Key, 並且回傳之.
+ //# 找不到的話回傳 `this->end()`
Element rLowerBound(Key const& __key) const;
+
+
+ //#|const|lowerBound|(Key const& `k`)|Element|O(logN)
+ //#|找出第一個(最小的) Element且 `k` > 它的 Key, 並且回傳之.
+ //# 找不到的話回傳 `this->end()`
Element rUpperBound(Key const& __key) const;
+
+
+ //#|const|find|(Key const& `k`)|Element|O(logN)
+ //#|找出 Key= `k` 的Elemenet 並回傳. 找不到的話回傳 `this->end()`
Element find (Key const& __key) const;
- Element order(size_t __order ) const;
- Element first( ) const;
- Element last ( ) const;
- Element end( ) const;
- //
+
+
+ //#|const|order|(size_t `ord`)|Element|O(logN)
+ //#|將Elements依照Key由小到大排序, 回傳第 `ord` 個Element (由0算起).
+ //# 其中如果 `ord` > N - 1, 則會回傳 `this->last()`
+ Element order(size_t __order) const;
+
+
+ //#|const|first|(size_t `ord`)|Element|O(logN)
+ //#|回傳Key最小的Element, 如果SplayTree為空, 則回傳 `this->end()`
+ Element first() const;
+
+
+ //#|const|last|(size_t `ord`)|Element|O(logN)
+ //#|回傳Key最大的Element, 如果SplayTree為空, 則回傳 `this->end()`
+ Element last() const;
+
+
+ //#|const|end|()|Element|O(1)
+ //#|回傳一個指向NULL的Element, 以供 `find` , `order` , `first`
+ //# , `last` 等判斷是否有找到相對應的Element
+ Element end() const;
+
+
+ //#|const|size|()|size_t|O(1)| 回傳資料數
size_t size() const;
+
+
+ //#|const|size|()|bool|O(1)| 回傳是否為空
bool empty() const;
- //
- void clear();
- void keyOffset(Key const& __delta);
- bool insert (Key const& __key, Value const& __value);
- bool erase (Key const& __key);
+
+
+ //#||clear|()|void|O(N)| 清空資料
+ void clear();
+
+
+ //#||keyOffset|(Key const& `delta`)|void|O(1)
+ //#|將所有Element的Key同加上 `delta`
+ void keyOffset(Key const& __delta);
+
+
+ //#||insert|(Key const& `key`,\Value const& `value`)|bool|O(logN)
+ //#|檢查是否已有Element的Key 為 `key`, 若有則回傳 `false` , 否則將
+ //# 一個 (Key -> Value) = (`key` -> `value`)的Element加入, 並回傳 `true`
+ //# 將所有Element的Key同加上 `delta`
+ bool insert(Key const& __key, Value const& __value);
+
+
+ //#||erase|(Key const& `key`)|bool|O(logN)
+ //#|檢查是否已有Element的Key 為 `key`, 若有則刪除之, 並回傳 `true`,
+ //# 否則則回傳 `false`
+ bool erase(Key const& __key);
+
+
+ //#||operator[]|(Key const& `key`)|Value&|O(logN)
+ //#|檢查是否已有Element的Key 為 `key`, 若有則回傳相對應的Value的Reference
+ //# 否則先執行 `insert(key, Value())` 再回傳相對應的Reference
Value& operator[](Key const& __key);
- void splitOut(Key const& __upper_bound, SplayTree* __right);
- bool mergeAfter(SplayTree* __tree2);
- bool merge (SplayTree* __tree2);
+
+
+ //#||splitOut|(Key const& `upper_bound`,\SplayTree* `tree2`)|void
+ //#|O(logN) + O(M)
+ //#|將 `tree2` 清空, 再將所有Key > `upper_bound` 的Element都丟到 `tree2`
+ void splitOut(Key const& __upper_bound, SplayTree* __right);
+
+
+ //#||mergeAfter|(SplayTree* `tree2`)|void|O(logN) + O(logM)
+ //#|檢查是否 `this` 中的 Key 都小於 `tree2` 中的Key, 是的話把 `tree2`
+ //# 中的 Element 都搬到 `this` , 同時清空 `tree2` , 回傳 `true`. 否則
+ //# 回傳 `false`
+ bool mergeAfter(SplayTree* __tree2);
+
+
+ //#||merge|(SplayTree* `tree2`)|void|O(logN) + O(logM)
+ //#|檢查是否 `this` 中的 Key 都小於 `tree2` 中的Key 或者
+ //# 是否 `this` 中的 Key 都大於 `tree2` 中的Key, 是的話把 `tree2`
+ //# 中的 Element 都搬到 `this` , 同時清空 `tree2` , 回傳 `true`. 否則
+ //# 回傳 `false`
+ bool merge(SplayTree* __tree2);
+ //
//
void print() const;
+ //#|=====================================================================
};
- /*********************************************************
- @asciidoc
- === meow:: *SplayTree<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-
- *********************************************************/
+ //#
+ //#[NOTE]
+ //#========================================
+ //# * 假設現在有兩個SplayTree `A` 和 `B`, 則:
+ //# ** 執行 `B.moveTo(&A)` 後 `B` 會變成空的, `A` 原本擁有的資料也會覆蓋掉
+ //# ** 執行 `A.merge(&B)` 或 `A.mergeAfter(&B)` 後
+ //# 如果檢查發現確實可以merge, 則之後 `B` 會變成空的
+ //#========================================
+ //#
+ //# '''
+ //#
}
#include "SplayTree.hpp"
diff --git a/meowpp/dsa/SplayTree.hpp b/meowpp/dsa/SplayTree.hpp
index 47615db..77331ef 100644
--- a/meowpp/dsa/SplayTree.hpp
+++ b/meowpp/dsa/SplayTree.hpp
@@ -31,7 +31,7 @@ namespace meow{
SplayTree<Key, Value>::offsetDown(Node* __node) const{
if(__node->_lChild != NULL) offsetAdd(__node->_lChild, __node->_keyOffset);
if(__node->_rChild != NULL) offsetAdd(__node->_rChild, __node->_keyOffset);
- __node->_keyOffset = 0;
+ __node->_keyOffset = Key(0);
}
//
template<class Key, class Value>
diff --git a/meowpp/utility.h b/meowpp/utility.h
index 4f3b36a..ec47225 100644
--- a/meowpp/utility.h
+++ b/meowpp/utility.h
@@ -40,59 +40,74 @@ namespace meow{
template<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-
- ******************************************************************/
+ //# === 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......`
+ //# ====================================
+ //#
+ //# '''
+ //#
}
#include "utility.hpp"
generated by cgit v1.2.3 (git 2.25.1) at 2024-06-29 02:46:51 +0800