aboutsummaryrefslogtreecommitdiffstats
path: root/meowpp/dsa
diff options
context:
space:
mode:
Diffstat (limited to 'meowpp/dsa')
-rw-r--r--meowpp/dsa/DisjointSet.h6
-rw-r--r--meowpp/dsa/HashTable.h8
-rw-r--r--meowpp/dsa/KD_Tree.h12
-rw-r--r--meowpp/dsa/MergeableHeap.h2
-rw-r--r--meowpp/dsa/SegmentTree.h6
-rw-r--r--meowpp/dsa/SplayTree.h22
-rw-r--r--meowpp/dsa/VP_Tree.h24
7 files changed, 40 insertions, 40 deletions
diff --git a/meowpp/dsa/DisjointSet.h b/meowpp/dsa/DisjointSet.h
index 4575835..9be9c35 100644
--- a/meowpp/dsa/DisjointSet.h
+++ b/meowpp/dsa/DisjointSet.h
@@ -13,11 +13,11 @@ namespace meow {
* 相關資料可參考
* <a href="http://www.csie.ntnu.edu.tw/~u91029/DisjointSets.html">
* 演算法筆記
- * </a>
+ * </a>
*
* @note
* - 時間複雜度 \b 非常快 表示它真的算的超級快, 可以視為常數時間
- * - 預設值所有 \a number 所在的集合的編號就是 \a number 本身,
+ * - 預設值所有 \a number 所在的集合的編號就是 \a number 本身,
* 即沒有任兩個數在同一個set裡面
*
* @author cat_leopard
@@ -119,7 +119,7 @@ public:
*
* 將 \a number1 所在的集合 跟 \b number2 所在的集合 \b 合併,
* 並回傳合併後新的集合的編號. \n
- * 時間複雜度\b 非常快
+ * 時間複雜度\b 非常快
*
* @param [in] a 即上述\a number1
* @param [in] b 即上述\a number2
diff --git a/meowpp/dsa/HashTable.h b/meowpp/dsa/HashTable.h
index 9171c72..5f343f5 100644
--- a/meowpp/dsa/HashTable.h
+++ b/meowpp/dsa/HashTable.h
@@ -25,7 +25,7 @@ public:
/*!
* @brief constructor
- *
+ *
* 設定table size, hash function
*/
HashTableList(size_t size, HashFunc const& func): table_(size), func_(func) {
@@ -193,18 +193,18 @@ public:
}
return ret;
}
-
+
//! @brief same as \c copyFrom(h)
HashTableList& operator=(HashTableList const& h) {
return copyFrom(h);
}
-
+
//! @brief same as \c add(h)
HashTableList& operator+=(HashTableList const& h) {
add(h);
return *this;
}
-
+
//! @brief same as \c del(h)
HashTableList& operator-=(HashTableList const& h) {
del(h);
diff --git a/meowpp/dsa/KD_Tree.h b/meowpp/dsa/KD_Tree.h
index 05f9b1b..e3bd73b 100644
--- a/meowpp/dsa/KD_Tree.h
+++ b/meowpp/dsa/KD_Tree.h
@@ -43,12 +43,12 @@ private:
Vector vector_;
ssize_t lChild_;
ssize_t rChild_;
-
+
Node(Vector v, ssize_t l, ssize_t r): vector_(v), lChild_(l), rChild_(r){
}
};
typedef std::vector<Node> Nodes;
-
+
class Sorter {
private:
Nodes const* nodes_;
@@ -187,16 +187,16 @@ private:
public:
//! Custom Type: Vectors is \c std::vector<Vector>
typedef typename std::vector<Vector> Vectors;
-
+
//! @brief constructor, with dimension = 1
KD_Tree(): kNIL_(-1), root_(kNIL_), needRebuild_(false), dimension_(1) {
}
-
+
//! @brief constructor, given dimension
KD_Tree(size_t dimension):
kNIL_(-1), root_(kNIL_), needRebuild_(false), dimension_(dimension) {
}
-
+
//! @brief destructor
~KD_Tree() {
}
@@ -254,7 +254,7 @@ public:
}
/*!
- * @brief 查找
+ * @brief 查找
*
* 於set中找尋距離指定向量前 \c i 近的向量, 並依照由近而遠的順序排序.
* 如果有兩個向量\c v1,v2 距離一樣, 且 \c cmp 為\c true , 則直接依照
diff --git a/meowpp/dsa/MergeableHeap.h b/meowpp/dsa/MergeableHeap.h
index af7ad75..0967edd 100644
--- a/meowpp/dsa/MergeableHeap.h
+++ b/meowpp/dsa/MergeableHeap.h
@@ -7,7 +7,7 @@
namespace meow {
/*!
- * @brief
+ * @brief
*
* 一個用 \b 左偏樹 實作的 \c Maximum-Heap , 除了原本heap有的功能外,
* 還支援 \c merge 功能
diff --git a/meowpp/dsa/SegmentTree.h b/meowpp/dsa/SegmentTree.h
index b2fa749..64eab4c 100644
--- a/meowpp/dsa/SegmentTree.h
+++ b/meowpp/dsa/SegmentTree.h
@@ -37,7 +37,7 @@ namespace meow {
* - 若要維護區間最總和, 即每次都是詢問範圍 `[a, b]` 的總和, 則可以定義
* - \c operator+ 為 '回傳相加值'
* - \c operator* 為 '回傳(*this) * n'
- * - \c operator| 為 '回傳相加值'
+ * - \c operator| 為 '回傳相加值'
*
* @author cat_leopard
*/
@@ -140,7 +140,7 @@ public:
nodes_ = b.nodes_;
return *this;
}
-
+
/*!
* @brief 回傳size
*/
@@ -182,7 +182,7 @@ public:
if (rangeCorrect(&first, &last) == false) return ;
update(first, last, 0, size_ - 1, 0, delta, false);
}
-
+
//! @brief same as copyFrom(b)
SegmentTree& operator=(SegmentTree const& b) {
return copyFrom(b);
diff --git a/meowpp/dsa/SplayTree.h b/meowpp/dsa/SplayTree.h
index 5e9fb3c..40a2a0b 100644
--- a/meowpp/dsa/SplayTree.h
+++ b/meowpp/dsa/SplayTree.h
@@ -43,7 +43,7 @@ private:
size_t size_;
Node* parent_;
Node* child_[2];
-
+
Node(Key const& key, Value const& value):
key_(key), keyOffset_(0), value_(value) {
size_ = 1;
@@ -373,7 +373,7 @@ public:
/*!
* @brief 回傳一個指向NULL的Element,
- *
+ *
* 以供 \c find ,\c order ,\c first ,\c last 等判斷是否有找到相對應的Element
*/
Element end() const {
@@ -404,7 +404,7 @@ public:
/*!
* @brief 插入一組\c (Key ---> \c Value)
- *
+ *
* 檢查是否已有Element的Key 為 \c key, 若有則回傳 \c false , 否則將
* 一個 (Key -> Value) = (\c key -> \c value)的Element加入, 並回傳 \c true
*/
@@ -504,7 +504,7 @@ public:
/*!
* @brief 合併
*
- * 檢查是否自己中的 Key 都小於 \c tree2 中的Key, 或是完全相反,
+ * 檢查是否自己中的 Key 都小於 \c tree2 中的Key, 或是完全相反,
* 是的話把 \c tree2`中的 Element 都搬到自己這,
* 同時清空 \c tree2 , 否則回傳 \c false
*/
@@ -522,7 +522,7 @@ public:
tree2->root_ = NULL;
return true;
}
-
+
/*!
* @brief 就像\c stl::map::operator[]
*
@@ -578,7 +578,7 @@ private:
size_t size_;
Node* parent_;
Node* child_[2];
-
+
Node(Key const& key, Value const& value):
valueOffset_(0), range_(value),
key_(key), keyOffset_(0), value_(value) {
@@ -932,7 +932,7 @@ public:
/*!
* @brief 回傳一個指向NULL的Element,
- *
+ *
* 以供 \c find ,\c order ,\c first ,\c last 等判斷是否有找到相對應的Element
*/
Element end() const {
@@ -952,7 +952,7 @@ public:
bool empty() const{
return (size() == 0);
}
-
+
/*!
* @brief 查找
*
@@ -992,7 +992,7 @@ public:
/*!
* @brief 插入一組\c (Key ---> \c Value)
- *
+ *
* 檢查是否已有Element的Key 為 \c key, 若有則回傳 \c false , 否則將
* 一個 (Key -> Value) = (\c key -> \c value)的Element加入, 並回傳 \c true
*/
@@ -1110,7 +1110,7 @@ public:
/*!
* @brief 合併
*
- * 檢查是否自己中的 Key 都小於 \c tree2 中的Key, 或是完全相反,
+ * 檢查是否自己中的 Key 都小於 \c tree2 中的Key, 或是完全相反,
* 是的話把 \c tree2`中的 Element 都搬到自己這,
* 同時清空 \c tree2 , 否則回傳 \c false
*/
@@ -1128,7 +1128,7 @@ public:
tree2->root_ = NULL;
return true;
}
-
+
/*!
* @brief 就像\c stl::map::operator[]
*
diff --git a/meowpp/dsa/VP_Tree.h b/meowpp/dsa/VP_Tree.h
index 75186e6..9c85930 100644
--- a/meowpp/dsa/VP_Tree.h
+++ b/meowpp/dsa/VP_Tree.h
@@ -15,13 +15,13 @@ namespace meow {
/*!
* @brief 跟KD_Tree很像歐
*
- * \c VP_Tree 用來維護由 \b N個K維度向量所成的集合 ,
+ * \c VP_Tree 用來維護由 \b N個K維度向量所成的集合 ,
* 並可於該set中查找 \b 前i個離給定向量最接近的向量* .
- * 不像 \c KD_Tree 二分樹每次都選擇一個維度去分, 分成小的跟大的,
+ * 不像 \c KD_Tree 二分樹每次都選擇一個維度去分, 分成小的跟大的,
* \c VP_Tree 每次選一個點, 將資料分成 離這個點近的, 跟離這個點遠的.
* 至於怎麼選呢...., 嘛還沒研究, 先random
*
- * 參考資料連結:
+ * 參考資料連結:
* - http://stevehanov.ca/blog/index.php?id=130
* - http://pnylab.com/pny/papers/vptree/vptree
*
@@ -33,7 +33,7 @@ namespace meow {
* |const | Vector|operator[] |(size_t \c n) | Scalar | 取得第\c n 維度量 |
* |const | Vector|operator= |(Vector \c v) | Vector& | copy operator |
* |const | Vector|operator< |(Vector \c v) | bool | 權重比較 |
- * |const | Scalar| 'Scalar' |(int \c n) | Scalar | 建構子,
+ * |const | Scalar| 'Scalar' |(int \c n) | Scalar | 建構子,
* 其中一定\c n=0or4 |
* |const | Scalar|operator* |(Scalar \c s) | Scalar | 相乘 |
* |const | Scalar|operator+ |(Scalar \c s) | Scalar | 相加 |
@@ -87,12 +87,12 @@ private:
};
typedef std::vector<Answer> AnswerV;
typedef std::priority_queue<Answer, AnswerV, AnswerCompare> Answers;
-
+
Vectors vectors_;
Node* root_;
size_t dimension_;
bool needRebuild_;
-
+
Scalar distance2(Vector const& v1, Vector const& v2) const {
Scalar ret(0);
for (size_t i = 0; i < dimension_; i++) ret += squ(v1[i] - v2[i]);
@@ -212,7 +212,7 @@ public:
VP_Tree(): root_(NULL), vectors_(0), dimension_(1), needRebuild_(false){
reset(0);
}
-
+
//! @brief constructor, 複製資料
VP_Tree(VP_Tree const& tree2):
vectors_(tree2.vectors_),
@@ -220,7 +220,7 @@ public:
dimension_(tree2.dimension_),
needRebuild_(tree2.needRebuild_) {
}
-
+
//! @brief constructor, 給定dimension
VP_Tree(size_t dimension):
vectors_(0),
@@ -229,12 +229,12 @@ public:
needRebuild_(false) {
reset(dimension);
}
-
+
//! @brief destructor
~VP_Tree() {
clear(root_);
}
-
+
/*!
* @brief 複製資料
*/
@@ -287,7 +287,7 @@ public:
}
/*!
- * @brief 查找
+ * @brief 查找
*
* 於set中找尋距離指定向量前 \c i 近的向量, 並依照由近而遠的順序排序.
* 如果有兩個向量\c v1,v2 距離一樣, 且 \c cmp 為\c true , 則直接依照
@@ -325,7 +325,7 @@ public:
dimension_ = std::max((size_t)1, dimension);
return dimension_;
}
-
+
//! @brief same as \c copyFrom(tree2)
VP_Tree& operator=(VP_Tree const& tree2) {
return copyFrom(tree2);
generated by cgit v1.2.3 (git 2.25.1) at 2025-08-28 05:02:47 +0800