diff options
Diffstat (limited to 'meowpp/dsa')
| -rw-r--r-- | meowpp/dsa/!readme.asciidoc | 57 | ||||
| -rw-r--r-- | meowpp/dsa/BinaryIndexTree.h | 155 | ||||
| -rw-r--r-- | meowpp/dsa/DisjointSet.h | 192 | ||||
| -rw-r--r-- | meowpp/dsa/HashTable.h | 217 | ||||
| -rw-r--r-- | meowpp/dsa/KD_Tree.h | 425 | ||||
| -rw-r--r-- | meowpp/dsa/MergeableHeap.h | 260 | ||||
| -rw-r--r-- | meowpp/dsa/SegmentTree.h | 274 | ||||
| -rw-r--r-- | meowpp/dsa/SplayTree.h | 1366 | ||||
| -rw-r--r-- | meowpp/dsa/VP_Tree.h | 461 |
9 files changed, 2575 insertions, 832 deletions
diff --git a/meowpp/dsa/!readme.asciidoc b/meowpp/dsa/!readme.asciidoc new file mode 100644 index 0000000..d6eb3d7 --- /dev/null +++ b/meowpp/dsa/!readme.asciidoc @@ -0,0 +1,57 @@ + + +包含一些資料結構 + +===== BinaryIndexTree.h + +極度簡化的 *SegmentTree* 已無區間更新的操作. + +.Classes +* `meow::BinaryIndexTree<Value>` + +===== DisjointSet.h + +用來維護一堆互斥集的資訊. + +.Classes +* `meow::DisjointSet` + +===== HashTable.h + +就是傳說中的HashTable + +.Classes +* `meow::HashTableList<Data, HashFunc>` + +===== KD_Tree.h + +查詢第k近鄰居用的 + +.Classes +* `meow::KD_Tree<Vector>` + +===== MergeableHeap.h + +可合併Heap + +.Classes +* `meow::MergeableHeap<Element>` + +===== SegmentTree.h + +線段樹 +.Classes +* `meow::SegmentTree<Value>` + +===== SplayTree.h + +伸展樹, 比一般平衡樹稍強的東東 +* `meow::SplayTree<Key, Value>` +* `meow::SplayTree_Range<Key, Value>` + +===== VP_Tree.h + +查詢第k近鄰居用的 + +.Classes +* `meow::VP_Tree<Vector>` diff --git a/meowpp/dsa/BinaryIndexTree.h b/meowpp/dsa/BinaryIndexTree.h index 36f24d7..5525c62 100644 --- a/meowpp/dsa/BinaryIndexTree.h +++ b/meowpp/dsa/BinaryIndexTree.h @@ -4,70 +4,99 @@ #include <cstdlib> #include <vector> +#include <algorithm> -namespace meow{ - //# - //#=== meow:: *BinaryIndexTree<Value>* (C++ class) - //#==== Description - //# 極度簡化版的 `SegmentTree` 已無法區間操作, 區間詢問的區間開頭也一定要 - //# 在 `index=0` 的地方 - //# - //#==== 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 `n`) | Value | 合併用(類似 - //# `SegmentTree` 的 - //# operator{b} ) - //#|===================================================================== - //# - template<class Value> - class BinaryIndexTree{ - private: - std::vector<Value> _array; - public: - BinaryIndexTree(); - BinaryIndexTree(size_t __size, Value const& __value); - BinaryIndexTree(BinaryIndexTree const& __tree2); - - //#==== Support Methods - //# - //# * N <- `this` 中擁有的資料數 - //# - //#[options="header",width="100%",cols="1>m,3>s,7<,3<,3^,20<",grid="rows"] - //#|===================================================================== - //#|Const?|Name | Parameters | Return_Type| Time_Complexity| Description - - - //#||reset|(size_t `size`, Value const& `value`)|void|O(`size`) - //#|將資料長度刷成 `N = size` 且每一個元素都是 `value` - void reset(size_t __size, Value const& __value); - - - //#||update|(size_t `index`, Value const& `value`)|void|O(logN) - //#|將第 `index` (從零開始算) 多加上 `value` - void update( size_t __index, Value const& __value); - - - //#|const|query|(size_t `index`)|void|O(logN) - //#|詢問 `0~index` 的區間值 - Value query (ssize_t __index) const; - - - //#|===================================================================== - }; - //# - //#[NOTE] - //#======================================== - //# * 一般來說只能用在維護區間總和, 維護區間最大值只有在特殊情況才可以, 即 - //# '針對每個元素, 每次 update() 的值一定會大於等於原本的值' - //# * 若要用區間最大值 , 則 `Value` 的 `operator+` 要寫成 `std::max(...)` - //#======================================== - //# - //# ''' -} +namespace meow { -#include "BinaryIndexTree.hpp" +template<class Value> +/*! + * @brief 極度簡化的 \c SegmentTree 已無區間更新的操作 + * + * 一般來說只能用在維護區間總和, 維護區間最大值只有在特殊情況才可以, 即 + * \b 針對每個元素, \b 每次update() \b 的值一定會大於等於原本的值 . + * 若要用區間最大值 , 則 \a Value 的 \c operator+ 要寫成 \c std::max(...) + * + * @author cat_leopard + */ +class BinaryIndexTree { +private: + std::vector<Value> array_; +public: + /*! + * @brief constructor + */ + BinaryIndexTree() { + } -#endif // dsa_BinaryIndexTree_H__ + /*! + * @brief constructor + * + * @param [in] size 要維護的區間大小 \b [0,size) + * @param [in] value 預設值 + */ + BinaryIndexTree(size_t size, Value const& value): + array_(size, value) { + } + + /*! + * @brief constructor + * + * 將另一個 \c BinaryIndexTree 原封不動的複製過來 + * @param [in] tree2 另外一個 \c BinaryIndexTree + */ + BinaryIndexTree(BinaryIndexTree const& tree2): + array_(tree2.array_) { + } + + /*! + * @brief 將資料洗掉, 重設 + * + * 時間複雜度\b O(N) + * + * @param [in] size 要維護的區間大小 \b [0,size) + * @param [in] init 預設值 + * @return 無 + */ + void reset(size_t size, Value const& init) { + array_.clear(); + array_.resize(size, init); + } + + /*! + * @brief 將array中第 \a index (從零算起)個element多加上指定的值 + * + * 時間複雜度\b O(logN) + * + * @param [in] index 指定的index + * @param [in] value 指定的值 + * @return 無 + */ + void update(size_t index, Value const& value) { + index++; + for ( ; index <= array_.size(); index += (index & -index)) { + array_[index - 1] = array_[index - 1] + value; + } + } + + /*! + * @brief 詢問 \a 0~index 的區間值 + * + * 時間複雜度\b O(logN) + * + * @param [in] index 指定的index + * @return 區間值 + */ + Value query(ssize_t index) const { + index = std::min(index + 1, (ssize_t)array_.size()); + Value ret(0); + for ( ; 0 < index; index -= (index & -index)) { + ret = ret + array_[index - 1]; + } + return ret; + } +}; + +} + +#endif // dsa_BinaryIndexTree_H__ diff --git a/meowpp/dsa/DisjointSet.h b/meowpp/dsa/DisjointSet.h index bb777e1..4575835 100644 --- a/meowpp/dsa/DisjointSet.h +++ b/meowpp/dsa/DisjointSet.h @@ -1,73 +1,135 @@ #ifndef dsa_DisjointSet_H__ #define dsa_DisjointSet_H__ -#include <cstdlib> - #include <vector> +#include <cstdlib> +#include <cstdio> + +namespace meow { +/*! + * @brief 用來維護一堆互斥集的資訊 + * + * DisjointSet 是個 \b 輕量級Data \b Dtructure, 用來維護一堆互斥集的資訊. \n + * 相關資料可參考 + * <a href="http://www.csie.ntnu.edu.tw/~u91029/DisjointSets.html"> + * 演算法筆記 + * </a> + * + * @note + * - 時間複雜度 \b 非常快 表示它真的算的超級快, 可以視為常數時間 + * - 預設值所有 \a number 所在的集合的編號就是 \a number 本身, + * 即沒有任兩個數在同一個set裡面 + * + * @author cat_leopard + */ +class DisjointSet { +private: + size_t n_; + std::vector<size_t> father_; + std::vector<size_t> depth_; + // + size_t root_(size_t now) { + if (father_[now] == now) return now; + return (father_[now] = root_(father_[now])); + } + + size_t merge_(size_t a, size_t b) { + a = root_(a); + b = root_(b); + if (a == b) return a; + if (depth_[a] > depth_[b]) { + father_[b] = a; + return a; + } + else { + father_[a] = b; + if (depth_[a] == depth_[b]) depth_[b]++; + return b; + } + } +public: + /*! + *@brief constructor + */ + DisjointSet(): n_(0) { + } + + /*! + *@brief constructor + * + *@param [in] n elements數 + */ + DisjointSet(size_t n) { + reset(n); + } + + /*! + *@brief constructor + * + *將另一個 \c DisjointSet 原封不動的複製過來 + * + *@param [in] dsj 另一個 \c DisjointSet + */ + DisjointSet(DisjointSet const& dsj): + n_(dsj.n_), father_(dsj.father_), depth_(dsj.depth_) { + } + + /*! + *@brief 回傳指定的number所在的 \b 集合的編號 + * + *時間複雜度 \b 超級快 + * + *@param [in] a 指定的number + *@return 集合的編號 + */ + size_t root(size_t a) const { + return ((DisjointSet*)this)->root_(a); + } + + + /*! + *@brief 回傳總element數 + * + *@return 總element數 + */ + size_t size() const { + return n_; + } + + /*! + *@brief 重設 + * + *清空, 並且設定總集合大小為 \a n + * + *@param [in] n 重新設定的集合大小 \a n + *@return 無 + */ + void reset(size_t n) { + n_ = n; + father_.resize(n); + depth_ .resize(n); + for (size_t i = 0; i < n; i++) { + father_[i] = i; + depth_ [i] = 1; + } + } + + /*! + * @brief 合併 + * + * 將 \a number1 所在的集合 跟 \b number2 所在的集合 \b 合併, + * 並回傳合併後新的集合的編號. \n + * 時間複雜度\b 非常快 + * + * @param [in] a 即上述\a number1 + * @param [in] b 即上述\a number2 + * @return 新的編號 + */ + size_t merge(size_t a, size_t b) { + return merge_(a, b); + } +}; -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; - std::vector<size_t> father; - std::vector<size_t> depth; - // - size_t _root(size_t now); - size_t _merge(size_t a, size_t b); - public: - 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); - - - //#|===================================================================== - }; - //# - //#[NOTE] - //#======================================== - //# * *very fast* 表示它算的真的超級快, 可以視為常數時間. - //# * 預設值所有 `number` 所在的集合的編號就是 `number` 本身, - //# 即沒有任兩個數在同一個set裡面 - //#======================================== - //# - //# ''' } -#include "DisjointSet.hpp" - - #endif // dsa_DisjointSet_H__ diff --git a/meowpp/dsa/HashTable.h b/meowpp/dsa/HashTable.h new file mode 100644 index 0000000..9171c72 --- /dev/null +++ b/meowpp/dsa/HashTable.h @@ -0,0 +1,217 @@ +#ifndef dsa_HashTable_H__ +#define dsa_HashTable_H__ + +#include <vector> +#include <list> + +namespace meow { + +/*! + * @brief 一個當key相撞時會用list解決的hash_table + * + * @author cat_leopard + */ +template<class Data, class HashFunc> +class HashTableList { +private: + std::vector<std::list<Data> > table_; + HashFunc func_; +public: + /*! + * @brief constructor + */ + HashTableList() { + } + + /*! + * @brief constructor + * + * 設定table size, hash function + */ + HashTableList(size_t size, HashFunc const& func): table_(size), func_(func) { + } + + /*! + * @brief destructor + */ + ~HashTableList() { + } + + /*! + * @brief copy + */ + HashTableList& copyFrom(HashTableList const& b) { + table_ = b.table_; + func_ = b.func_; + return *this; + } + + /*! + * @brief 清除資料 + */ + void clear() { + for (size_t i = 0, I = table_.size(); i < I; i++) { + table_[i].clear(); + } + } + + /*! + * @brief 清除資料, 指定新的size與hash function + */ + void reset(size_t size, HashFunc const& func) { + table_.clear(); + table_.resize(std::max(size, 1u)); + func_ = func; + } + + /*! + * @brief 回傳table size + */ + size_t tableSize() const { + return table_.size(); + } + + /*! + * @brief 回傳目前有多少element在其中 + */ + size_t size() const { + size_t ret = 0; + for (size_t i = 0, I = table_.size(); i < I; i++) { + ret += table_[i].size(); + } + return ret; + } + + /*! + * @brief 回傳hash function + */ + HashFunc const& func() const { + return func_; + } + + /*! + * @brief 加入新的element + */ + bool add(Data const& e) { + size_t index = func_(e) % size(); + table_[index].push_back(e); + return true; + } + + /*! + * @brief 把給定的HashTableList中所有的element全加進來 + */ + bool add(HashTableList const& h) { + for (size_t i = 0, I = h.table_.size(); i < I; i++) { + for (std::list<Data>::const_iterator + it = h.table_[index].begin(); it != h.table_[index].end(); ++it) { + insert(*it); + } + } + return true; + } + + /*! + * @brief 刪除element + */ + bool del(Data const& e) { + size_t index = func_(e) % size(); + for (std::list<Data>::const_iterator + it = table_[index].begin(); it != table_[index].end(); ++it) { + if ((*it) == e) { + table_[index].erase(i); + return true; + } + } + return false; + } + + /*! + * @brief 刪除有出現在給定的的HashTableList中的element + */ + bool del(HashTableList const& h) { + if (size() > h.size()) { + for (size_t i = 0, I = h.table_.size(); i < I; i++) { + for (std::list<Data>::const_iterator + it = h.table_[index].begin(); it != h.table_[index].end(); ++it) { + erase(*it); + } + } + } + else { + for (size_t i = 0, I = table_.size(); i < I; i++) { + for (std::list<Data>::const_iterator + it = table_[index].begin(); it != table_[index].end(); ) { + if (h.exist(*it)) { + table_[index].erase(it); + } + else { + ++it; + } + } + } + } + return true; + } + + /*! + * @brief 查看某element是否已經擁有 + */ + bool exist(Data const& e) const { + size_t index = func_(e) % size(); + for (std::list<Data>::const_iterator + it = table_[index].begin(); it != table_[index].end(); ++it) { + if ((*it) == e) + return true; + } + return false; + } + + /*! + * @brief 回傳所有存下來的資料 + */ + std::vector<Data> all() const { + std::vector<Data> ret; + for (size_t i = 0, I = table_.size(); i < I; i++) { + for (std::list<Data>::const_iterator + it = table_[i].begin(); it != table_[i].end(); ++it) { + ret.push_back(*it); + } + } + return ret; + } + + /*! + * @brief 回傳所有存下來且key為index的資料 + */ + std::vector<Data> all(size_t index) const { + index %= table_.size(); + std::vector<Data> ret; + for (std::list<Data>::const_iterator + it = table_[index].begin(); it != table_[index].end(); ++it) { + ret.push_back(*it); + } + 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); + return *this; + } +}; + +} + +#endif // dsa_HashTable_H__ diff --git a/meowpp/dsa/KD_Tree.h b/meowpp/dsa/KD_Tree.h index dcb60a7..05f9b1b 100644 --- a/meowpp/dsa/KD_Tree.h +++ b/meowpp/dsa/KD_Tree.h @@ -1,162 +1,303 @@ #ifndef dsa_KD_Tree_H__ #define dsa_KD_Tree_H__ +#include "../utility.h" +#include "../math/utility.h" + #include <cstdlib> #include <vector> +#include <algorithm> #include <queue> -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: - struct Node{ - Vector _vector; - ssize_t _lChild; - ssize_t _rChild; - // - Node(Vector __vector, ssize_t __lChild, ssize_t __rChild); - }; - typedef std::vector<Node> Nodes; - // - class Sorter{ - private: - Nodes const* _nodes; - size_t _cmp; - public: - Sorter(Nodes const* __nodes, size_t __cmp); - bool operator()(size_t const& __a, size_t const& __b) const; - }; - struct Answer{ - ssize_t _index; - Scalar _dist2; - // - Answer(ssize_t __index, Scalar __dist2); - Answer(Answer const& __answer2); - }; - class AnswerCompare{ - private: - Nodes const* _nodes; - bool _cmpValue; - public: - AnswerCompare(Nodes const* __nodes, bool __cmpValue); - bool operator()(Answer const& __a, Answer const& __b) const; - }; - typedef std::vector<Answer> AnswerV; - typedef std::priority_queue<Answer, AnswerV, AnswerCompare> Answers; - // - const ssize_t _NIL; - // - Nodes _nodes; - size_t _root; - bool _needRebuild; - size_t _dimension; - // - Scalar distance2(Vector const& __v1, Vector const& __v2) const; - // - void query(Vector const& __vector, - size_t __nearestNumber, - AnswerCompare const& __answerCompare, - ssize_t __index, - int __depth, - std::vector<Scalar>& __dist2Vector, - Scalar __dist2Minimum, - Answers *__out) const; - ssize_t build(ssize_t __beg, - ssize_t __end, - 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(); +namespace meow { +/*! + * @brief \c k-dimension tree + * + * 全名k-dimension tree, 用來維護由\b N個K維度向量所成的集合, + * 並可於該set中查找 \b 前i個離給定向量最接近的向量 + * + * Template Class Operators Request + * -------------------------------- + * + * |const?|Typename|Operator | Parameters |Return Type | Description | + * |-----:|:------:|----------:|:-------------|:----------:|:------------------| + * |const |Vector |operator[] |(size_t \c n) |Scalar | 取得第 `n` 維度量 | + * |const |Vector |operator< |(Vector \c v) |bool | 權重比較 | + * |const |Scalar |operator* |(Scalar \c s) |Scalar | 相乘 | + * |const |Scalar |operator+ |(Scalar \c s) |Scalar | 相加 | + * |const |Scalar |operator- |(Scalar \c s) |Scalar | 相差 | + * |const |Scalar |operator< |(Scalar \c s) |bool | 大小比較 | + * + * @note: + * 此資料結構只有在 N >> 2 <sup>K</sup> 時才比較有優勢, + * 當 K 逐漸變大時, 所花時間會跟暴搜沒兩樣 + * + * @author cat_leopard + */ +template<class Vector, class Scalar> +class KD_Tree { +private: + struct Node { + 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_; + size_t cmp_; + public: + Sorter(Nodes const* nodes, size_t cmp): + nodes_(nodes), cmp_(cmp){ + } + bool operator()(size_t const& a, size_t const& b) const{ + if ((*nodes_)[a].vector_[cmp_] != (*nodes_)[b].vector_[cmp_]) { + return ((*nodes_)[a].vector_[cmp_] < (*nodes_)[b].vector_[cmp_]); + } + return ((*nodes_)[a].vector_ < (*nodes_)[b].vector_); + } + }; + struct Answer { + ssize_t index_; + Scalar dist2_; + // + Answer(ssize_t index, Scalar dist2): + index_(index), dist2_(dist2) { + } + Answer(Answer const& answer2): + index_(answer2.index_), dist2_(answer2.dist2_) { + } + }; + class AnswerCompare { + private: + Nodes const* nodes_; + bool cmpValue_; + public: + AnswerCompare(Nodes const* nodes, bool cmpValue): + nodes_(nodes), cmpValue_(cmpValue) { + } + bool operator()(Answer const& a, Answer const& b) const { + if (cmpValue_ == true && a.dist2_ == b.dist2_) { + return ((*nodes_)[a.index_].vector_ < (*nodes_)[b.index_].vector_); + } + return (a.dist2_ < b.dist2_); + } + }; + typedef std::vector<Answer> AnswerV; + typedef std::priority_queue<Answer, AnswerV, AnswerCompare> Answers; + // + const ssize_t kNIL_; + // + Nodes nodes_; + size_t root_; + bool needRebuild_; + size_t dimension_; + // + 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]); + } + return ret; + } + // + void query(Vector const& v, + size_t nearestNumber, + AnswerCompare const& answerCompare, + ssize_t index, + int depth, + std::vector<Scalar>& dist2Vector, + Scalar dist2Minimum, + Answers *out) const { + if (index == kNIL_) return ; + size_t cmp = depth % dimension_; + ssize_t this_side, that_side; + if (!(nodes_[index].vector_[cmp] < v[cmp])) { + this_side = nodes_[index].lChild_; + that_side = nodes_[index].rChild_; + }else{ + this_side = nodes_[index].rChild_; + that_side = nodes_[index].lChild_; + } + query(v, nearestNumber, answerCompare, + this_side, depth + 1, + dist2Vector, dist2Minimum, + out); + Answer my_ans(index, distance2(nodes_[index].vector_, v)); + if (out->size() < nearestNumber || answerCompare(my_ans, out->top())) { + out->push(my_ans); + if (out->size() > nearestNumber) out->pop(); + } + Scalar dist2_old(dist2Vector[cmp]); + dist2Vector[cmp] = squ(nodes_[index].vector_[cmp] - v[cmp]); + Scalar dist2Minimum2(dist2Minimum + dist2Vector[cmp] - dist2_old); + if (out->size() < nearestNumber || !(out->top().dist2_ < dist2Minimum)) { + query(v, nearestNumber, answerCompare, + that_side, depth + 1, + dist2Vector, dist2Minimum2, + out); + } + dist2Vector[cmp] = dist2_old; + } + ssize_t build(ssize_t beg, + ssize_t end, + std::vector<size_t>* orders, + int depth) { + if (beg > end) return kNIL_; + size_t tmp_order = dimension_; + size_t which_side = dimension_ + 1; + ssize_t mid = (beg + end) / 2; + size_t cmp = depth % dimension_; + for (ssize_t i = beg; i <= mid; i++) { + orders[which_side][orders[cmp][i]] = 0; + } + for (ssize_t i = mid + 1; i <= end; i++) { + orders[which_side][orders[cmp][i]] = 1; + } + for (size_t i = 0; i < dimension_; i++) { + if (i == cmp) continue; + size_t left = beg, right = mid + 1; + for (int j = beg; j <= end; j++) { + size_t ask = orders[i][j]; + if(ask == orders[cmp][mid]) { + orders[tmp_order][mid] = ask; + } + else if(orders[which_side][ask] == 1) { + orders[tmp_order][right++] = ask; + } + else { + orders[tmp_order][left++] = ask; + } + } + for (int j = beg; j <= end; j++) { + orders[i][j] = orders[tmp_order][j]; + } + } + nodes_[orders[cmp][mid]].lChild_ = build(beg, mid - 1, orders, depth + 1); + nodes_[orders[cmp][mid]].rChild_ = build(mid + 1, end, orders, depth + 1); + return orders[cmp][mid]; + } +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() { + } - //#||forceBuild|()|void|O(KN logN) - //#|重新建樹 - void forceBuild(); - + /*! + * @brief 將給定的Vector加到set中 + */ + void insert(Vector const& v) { + nodes_.push_back(Node(v, kNIL_, kNIL_)); + needRebuild_ = true; + } - //#|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; + /*! + * @brief 將給定的Vector從set移除 + */ + bool erase(Vector const& v) { + for (size_t i = 0, I = nodes_.size(); i < I; i++) { + if (nodes_[i] == v) { + if (i != I - 1) { + std::swap(nodes_[i], nodes_[I - 1]); + } + needRebuild_ = true; + return true; + } + } + return false; + } + /*! + * @brief 檢查至今是否有 insert/erase 被呼叫來決定是否 \c rebuild() + */ + void build(){ + if (needRebuild_) { + forceBuild(); + } + } - //#||clear|()|void|O(1) - //#|清空所有資料 - void clear(); + /*! + * @brief 重新建樹 + */ + void forceBuild() { + std::vector<size_t> *orders = new std::vector<size_t>[dimension_ + 2]; + for (size_t j = 0; j < dimension_ + 2; j++) { + orders[j].resize(nodes_.size()); + } + for (size_t j = 0; j < dimension_; j++) { + for (size_t i = 0, I = nodes_.size(); i < I; i++) { + orders[j][i] = i; + } + std::sort(orders[j].begin(), orders[j].end(), Sorter(&nodes_, j)); + } + root_ = build(0, (ssize_t)nodes_.size() - 1, orders, 0); + delete [] orders; + needRebuild_ = false; + } + /*! + * @brief 查找 + * + * 於set中找尋距離指定向量前 \c i 近的向量, 並依照由近而遠的順序排序. + * 如果有兩個向量\c v1,v2 距離一樣, 且 \c cmp 為\c true , 則直接依照 + * \c v1<v2 來決定誰在前面. 最後回傳一陣列包含所有解. + */ + Vectors query(Vector const& v, + size_t nearestNumber, + bool compareWholeVector) const { + ((KD_Tree*)this)->build(); + AnswerCompare answer_compare(&nodes_, compareWholeVector); + Answers answer_set(answer_compare); + std::vector<Scalar> tmp(dimension_, 0); + query(v, nearestNumber, + answer_compare, + root_, 0, + tmp, Scalar(0), + &answer_set); + Vectors ret(answer_set.size()); + for (int i = (ssize_t)answer_set.size() - 1; i >= 0; i--) { + ret[i] = nodes_[answer_set.top().index_].vector_; + answer_set.pop(); + } + return ret; + } - //#||reset|(size_t `dimension`)|void|O(1) - //#|清空所有資料並且指定維度為 `dimension` - void reset(size_t __dimension); + /*! + * @brief 清空所有資料 + */ + void clear() { + root_ = kNIL_; + nodes_.clear(); + needRebuild_ = false; + } + /*! + * @brief 清空所有資料並重新給定維度 + */ + void reset(size_t dimension) { + clear(); + dimension_ = dimension; + } +}; - //#|===================================================================== - }; - //# - //#[NOTE] - //#======================================== - //# * 此資料結構只有在 N >> 2 ^K^ 時才比較有優勢, - //# 當 K 逐漸變大時, 所花時間會跟暴搜沒兩樣 - //#======================================== - //# - //# ''' } -#include "KD_Tree.hpp" - #endif // dsa_KD_Tree_H__ diff --git a/meowpp/dsa/MergeableHeap.h b/meowpp/dsa/MergeableHeap.h index 0ddb100..af7ad75 100644 --- a/meowpp/dsa/MergeableHeap.h +++ b/meowpp/dsa/MergeableHeap.h @@ -2,107 +2,167 @@ #define dsa_MergeableHeap_H__ #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: - struct Node{ - Element value; - Node* l_child; - Node* r_child; - size_t weight; - Node(Element const& _value); - }; - // - Node* root; - // - void clear(Node* _node ); - Node* dup (Node* _node2 ); - Node* merge(Node* _left, Node* _right); - public: - MergeableHeap(); - MergeableHeap(MergeableHeap const& _heap2); - MergeableHeap& operator=(MergeableHeap const& _heap2); - ~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); - - //#|===================================================================== +#include <algorithm> + +namespace meow { + +/*! + * @brief + * + * 一個用 \b 左偏樹 實作的 \c Maximum-Heap , 除了原本heap有的功能外, + * 還支援 \c merge 功能 + * + * Template Class Operators Request + * -------------------------------- + * + * |const?|Typename|Operator | Parameters |Return Type | Description | + * |-----:|:------:|----------:|:-------------|:----------:|:------------------| + * |const |Element |operator< |(Element \c b)|bool | 大小比較 | + * + * @note: + * 假設現在有兩個MergeableHeap \c A 和 \c B, 則: + * - 執行 \c A.merge(&B) 後 \c B 會變成空的 + * - 執行 \c B.moveTo(&A) 後 \c B 會變成空的, \c A 原本擁有的資料也會覆蓋掉 + * + * @author cat_leopard + */ +template<class Element> +class MergeableHeap { // maximum-heap +private: + struct Node { + Element value_; + Node* lChild_; + Node* rChild_; + size_t weight_; + Node(Element const& value): + value_(value), lChild_(NULL), rChild_(NULL), weight_(1){ + } }; - //# - //# [WARNING] - //#============================================== - //# * 假設現在有兩個MergeableHeap `A` 和 `B`, 則: - //# ** 執行 `A.merge(&B)` 後 `B` 會變成空的 - //# ** 執行 `B.moveTo(&A)` 後 `B` 會變成空的, `A` 原本擁有的資料也會覆蓋掉 - //#============================================== - //# - //# ''' - //# -} -#include "MergeableHeap.hpp" + Node* root_; + + void clear(Node* node) { + if (node != NULL) { + clear(node->lChild_); + clear(node->rChild_); + delete node; + } + } + Node* dup(Node* node) { + if (node == NULL) return NULL; + Node* ret = new Node(node->value_); + ret->lChild_ = dup(node->lChild_); + ret->rChild_ = dup(node->rChild_); + ret->weight_ = 1; + ret->weight_ += (ret->lChild_ == NULL ? 0 : ret->lChild_->weight_); + ret->weight_ += (ret->rChild_ == NULL ? 0 : ret->rChild_->weight_); + return ret; + } + Node* merge(Node* left, Node* right) { + if (left == NULL) return right; + if (right == NULL) return left; + if (left->value_ < right->value_) { + std::swap(left, right); + } + left->rChild_ = merge(left->rChild_, right); + size_t lw = (left->lChild_ == NULL ? 0 : left->lChild_->weight_); + size_t rw = (left->rChild_ == NULL ? 0 : left->rChild_->weight_); + if (lw < rw) { + std::swap(left->lChild_, left->rChild_); + } + left->weight_ = 1 + lw + rw; + return left; + } +public: + //! @brief constructor + MergeableHeap(): root_(NULL){ + } + + //! @brief constructor, 並且複製資料 + MergeableHeap(MergeableHeap const& heap2): root_(dup(heap2.root_)) { + } + + //! @brief destructor + ~MergeableHeap(){ + clear(root_); + } + + //! @brief 複製資料 + MergeableHeap& copyFrom(MergeableHeap const& heap2) { + delete root_; + root_ = dup(heap2.root_); + return *this; + } + + /*! + * @brief 將自己的資料丟給指定的heap, 從此自己一身空 + */ + void moveTo(MergeableHeap* heap2){ + heap2->clear(); + heap2->root_ = root_; + root_ = NULL; + } + + /*! + * @brief 回傳最大的那個 Element + */ + Element const& top() const { + return root_->value_; + } + + /*! + * @brief 回傳資料個數 + */ + size_t size() const { + return (root_ == NULL ? 0 : root_->weight_); + } + + /*! + * @brief 回傳是否為空 + */ + bool empty() const { + return (size() == 0); + } + + /*! + * @brief 加入element + */ + void push(Element const& value) { + root_ = merge(root_, new Node(value)); + } + + /*! + * @brief 將最大的element移除 + */ + void pop() { + Node* l = root_->lChild_; + Node* r = root_->rChild_; + delete root_; + root_ = merge(l, r); + } + + /*! + * 將資料清空 + */ + void clear() { + clear(root_); + root_ = NULL; + } + + /*! + * 將給定的MergeableHeap的資料統統加到自己身上並且清空該heap + */ + void merge(MergeableHeap* heap2) { + root_ = merge(root_, heap2->root_); + heap2->root_ = NULL; + } + + //! @brief same as \c copyFrom(heap2) + MergeableHeap& operator=(MergeableHeap const& heap2) { + return copyFrom(heap2); + } +}; + +} #endif // dsa_MergeableHeap_H__ diff --git a/meowpp/dsa/SegmentTree.h b/meowpp/dsa/SegmentTree.h index 52d5a6f..b2fa749 100644 --- a/meowpp/dsa/SegmentTree.h +++ b/meowpp/dsa/SegmentTree.h @@ -1,100 +1,194 @@ #ifndef dsa_SegmentTree_H__ #define dsa_SegmentTree_H__ -#include <cstdlib> +#include "../math/utility.h" #include <vector> +#include <algorithm> + +#include <cstdlib> -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: - struct Node{ - Value _value; - Value _offset; - bool _sameFlag; - }; - // - size_t _size; - std::vector<Node> _nodes; - // - void update(size_t __index, size_t __size, Value const& __value, - bool __override); - void update(size_t __l, size_t __r, size_t __L, size_t __R, - size_t __index, Value const& __value, - bool __override); - 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); - // - //#==== 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); - - - //#|===================================================================== +namespace meow { +/*! + * @brief 中文名 \c 線段樹 + * + * 維護一個陣列, 並且讓user可以有區間查詢, 區間修改的小東東 + * + * Template Class Operators Request + * -------------------------------- + * + * |const?|Typename|Operator | Parameters |Return Type | Description | + * |-----:|:------:|----------:|:-------------|:----------:|:------------------| + * |const |Vector |operator[] |(size_t \c n) |Scalar | 取得第 `n` 維度量 | + * |const |Vector |operator< |(Vector \c v) |bool | 權重比較 | + * |const |Scalar |operator* |(Scalar \c s) |Scalar | 相乘 | + * |const |Scalar |operator+ |(Scalar \c s) |Scalar | 相加 | + * |const |Scalar |operator- |(Scalar \c s) |Scalar | 相差 | + * |const |Scalar |operator< |(Scalar \c s) |bool | 大小比較 | + * |const |Value |operator+ |(Value \c v) |Value | 相加(位移) | + * |const |Value |operator* |(size_t \c n) |Value | 每個Value都一樣, + * 長為 `n` 的區間的值| + * |const |Value |operator{b}|(Value \c v) |Value | 區間合併後的值 | + * + * - 若要維護區間最小值, 即每次都是詢問範圍 `[a, b]` 的最小值, 則可以定義 + * - \c operator+ 為 '回傳相加值' + * - \c operator* 為 '回傳*this' + * - \c operator| 為 '回傳std::min(*this, v)' + * - 若要維護區間最總和, 即每次都是詢問範圍 `[a, b]` 的總和, 則可以定義 + * - \c operator+ 為 '回傳相加值' + * - \c operator* 為 '回傳(*this) * n' + * - \c operator| 為 '回傳相加值' + * + * @author cat_leopard + */ +template<class Value> +class SegmentTree { +private: + struct Node { + Value value_; + Value offset_; + bool sameFlage_; }; - //# - //# ''' - //# -} + // + size_t size_; + std::vector<Node> nodes_; + // + void update(size_t index, size_t size, Value const& value, bool override) { + if (override) { + nodes_[index].value_ = value * size; + nodes_[index].offset_ = value; + nodes_[index].sameFlage_ = true; + } + else { + nodes_[index].value_ = nodes_[index].value_ + value * size; + nodes_[index].offset_ = nodes_[index].offset_ + value; + } + } + void update(size_t l, size_t r, size_t L, size_t R, + size_t index, Value const& value, + bool override) { + if (l == L && r == R) { + update(index, R - L + 1, value, override); + return ; + } + size_t mid = (L + R) / 2; + if (L < R) { + update(index * 2 + 1, mid - L + 1, + nodes_[index].offset_, nodes_[index].sameFlage_); + update(index * 2 + 2, R - mid, + nodes_[index].offset_, nodes_[index].sameFlage_); + nodes_[index].offset_ = Value(0); + nodes_[index].sameFlage_ = false; + } + if (r <= mid) { + update(l, r, L ,mid, index * 2 + 1, value, override); + } + else if (mid + 1 <= l) { + update(l, r, mid + 1,R, index*2 + 2, value, override); + } + else { + update(l, mid , L, mid , index * 2 + 1, value, override); + update( mid + 1, r, mid + 1, R, index * 2 + 2, value, override); + } + nodes_[index].value_ = ( + (nodes_[index * 2 + 1].value_ | nodes_[index * 2 + 2].value_) + + nodes_[index].offset_ + ); + } + Value query(size_t l, size_t r, size_t L, size_t R, size_t index) { + if (l == L && r == R) return nodes_[index].value_; + Value off = nodes_[index].offset_ * (r - l + 1); + if (nodes_[index].sameFlage_) return off; + size_t mid = (L + R) / 2; + if (r <= mid) return query(l, r, L , mid, index * 2 + 1) + off; + else if(mid + 1 <= l) return query(l, r, mid + 1, R, index * 2 + 2) + off; + else{ + return ( query(l, mid , L, mid , index * 2 + 1) + | query( mid + 1, r, mid + 1, R, index * 2 + 2) + ) + off; + } + } + // + bool rangeCorrect(ssize_t* first, ssize_t* last) const { + if (*last < *first || *last < 0 || (ssize_t)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; + } +public: + //! @brief constructor + SegmentTree() { + reset(1); + } + + //! @brief constructor, with \c size gived + SegmentTree(size_t size) { + reset(size); + } + + //! @brief constructor, 並且複製資料 + SegmentTree(SegmentTree const& tree2): + size_(tree2.size_), nodes_(tree2.nodes_) { + } -#include "SegmentTree.hpp" + /*! + * @brief 複製 + */ + SegmentTree copyFrom(SegmentTree const& b) { + size_ = b.size_; + nodes_ = b.nodes_; + return *this; + } + + /*! + * @brief 回傳size + */ + size_t size() const { + return size_; + } + + /*! + * @brief 將資料清空且設定維護範圍是 \c 0~size-1 + */ + void reset(size_t size){ + size_ = std::max(size, (size_t)1); + nodes_.resize(size * 4); + nodes_[0].sameFlage_ = true; + nodes_[0].value_ = Value(0); + nodes_[0].offset_ = Value(0); + } + + /*! + * @brief 回傳區間 \c [first,last] (邊界都含) 的區間值 + */ + 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, 0); + } + + /*! + * @brief 將區間 \c [first,last] 全部都設定成 \c value + */ + void override(ssize_t first, ssize_t last, Value const& value) { + if (rangeCorrect(&first, &last) == false) return ; + update(first, last, 0, size_ - 1, 0, value, true); + } + + /*! + * @brief 將區間 \c [first,last] 全部都加上 \c delta + */ + void offset(ssize_t first, ssize_t last, Value const& delta) { + 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); + } +}; + +} #endif // dsa_SegmentTree_H__ diff --git a/meowpp/dsa/SplayTree.h b/meowpp/dsa/SplayTree.h index da451b0..5e9fb3c 100644 --- a/meowpp/dsa/SplayTree.h +++ b/meowpp/dsa/SplayTree.h @@ -2,234 +2,1150 @@ #define dsa_SplayTree_h__ #include <cstdlib> - #include <utility> -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: - struct Node{ - Key _key; - Key _keyOffset; - Value _value; - size_t _size; - Node* _parent; - Node* _child[2]; - // - Node(Key const& __key, Value const& __value); - // - void keyOffset(Key const& __delta); - void syncDown() const; - void syncUp () const; - }; - // - Node* _root; - // - void connect(Node const* __parent, size_t __left_right, - Node const* __child) const; - Node const* splay (Node const* __node) const; - // - void clear(Node* __node); - Node* dup(Node* __node); - // - Node const* findKey (Node const* __node, Key const& __key ) const; - Node const* findMinMax(Node const* __node, bool __minimum) const; - Node const* findOrder (Node const* __node, size_t __order ) const; - // - void split(Node* __root, Node** __left, Node** __right); - Node* merge( Node* __left, Node* __right); - 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; - Entry* _entry; - Node * _node; - // - void reset(Node* __node); - public: - Element(); - Element(Node* __node); - Element(Element const& __iterator2); - ~Element(); - // - Element& operator=(Element const& __e2); - // - Entry* operator->(); - Entry& operator *(); - // - bool operator==(Element const& __e2) const; - bool operator!=(Element const& __e2) const; - }; - // - SplayTree(); - SplayTree(SplayTree const& __tree2); - ~SplayTree(); - SplayTree& operator=(SplayTree const& __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; - - - //#|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; - - - //#||clear|()|void|O(N)| 清空資料 - void clear(); - - - //#||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); - - - //#||keyOffset|(Key const& `delta`)|void|O(1) - //#|將所有Element的Key同加上 `delta` - void keyOffset(Key const& __delta); - - - //#||operator[]|(Key const& `key`)|Value&|O(logN) - //#|檢查是否已有Element的Key 為 `key`, 若有則回傳相對應的Value的Reference - //# 否則先執行 `insert(key, Value())` 再回傳相對應的Reference - Value& operator[](Key const& __key); - - - //#||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); - - - //#|===================================================================== +#include "../math/utility.h" + +namespace meow { + +/*! + * @brief + * + * 是一種神乎其技的資料結構, 維護一堆 Key->Value . 並且支援 + * 一些 \c std::map 難以快速實踐的操作, 如 \c split , \c merge , \c keyOffset + * + * Template Class Operators Request + * -------------------------------- + * + * |const?|Typename|Operator | Parameters |Return Type | Description | + * |-----:|:------:|----------:|:-------------|:----------:|:------------------| + * |const |Key |operator+ |(Key \c k) | Key |相加 | + * |const |Key |operator< |(Key \c k) | bool |大小比較 | + * | |Key |operator= |(Key \c k) | Key |copy oper | + * | |Key |Key |(int \c n) | |構子,\c n 永遠是0 | + * | |Value | Value |( ) | |建構子 | + * + * @note: + * -假設現在有兩個SplayTree `A` 和 `B`, 則: + * -執行 `B.moveTo(&A)` 後 `B` 會變成空的, `A` 原本擁有的資料也會覆蓋掉 + * -行 `A.merge(&B)` 或 `A.mergeAfter(&B)` 後 + * 如果檢查發現確實可以merge, 則之後 `B` 會變成空的 + * + * @author cat_leopard + */ +template<class Key, class Value> +class SplayTree { +private: + struct Node { + Key key_; + Key keyOffset_; + Value value_; + size_t size_; + Node* parent_; + Node* child_[2]; + + Node(Key const& key, Value const& value): + key_(key), keyOffset_(0), value_(value) { + size_ = 1; + parent_ = NULL; + child_[0] = NULL; + child_[1] = NULL; + } + // + void keyOffset(Key const& delta) { + key_ = key_ + delta; + keyOffset_ = keyOffset_ + delta; + } + void syncDown() const { + for (size_t i = 0; i < 2; i++) { + if (child_[i] == NULL) continue; + child_[i]->keyOffset(keyOffset_); + } + ((Node*)this)->keyOffset_ = Key(0); + } + void syncUp() const { + ((Node*)this)->size_ = 1; + for (size_t i = 0; i < 2; i++) { + if (child_[i] == NULL) continue; + ((Node*)this)->size_ += child_[i]->size_; + } + } }; - //# - //#[NOTE] - //#======================================== - //# * 假設現在有兩個SplayTree `A` 和 `B`, 則: - //# ** 執行 `B.moveTo(&A)` 後 `B` 會變成空的, `A` 原本擁有的資料也會覆蓋掉 - //# ** 執行 `A.merge(&B)` 或 `A.mergeAfter(&B)` 後 - //# 如果檢查發現確實可以merge, 則之後 `B` 會變成空的 - //#======================================== - //# - //# ''' - //# -} -#include "SplayTree.hpp" + Node* root_; + + //! @brief 指定左子or右子, 連接parent<--->child + void connect(Node const* parent, size_t left_right, Node const* child) const { + Node* p = (Node*)parent; + Node* c = (Node*)child; + if (p != NULL) p->child_[left_right] = c; + if (c != NULL) c->parent_ = p; + } + + //! @brief 一路往上轉 + Node const* splay(Node const* node) const { + if (node != NULL && node->parent_ != NULL) { + for (const Node *g_grand, *grand, *parent, *child = node; ; ) { + g_grand = (grand = parent = child->parent_)->parent_; + size_t pc = (parent->child_[0] == child ? 0 : 1); + connect(parent, pc, child->child_[!pc]); + connect(child , !pc, parent); + if (g_grand != NULL) { + g_grand = (grand = g_grand)->parent_; + size_t gp = (grand->child_[0] == parent ? 0 : 1); + Node const* who = (pc == gp ? parent : child); + connect(grand, gp, who->child_[!gp]); + connect(who , !gp, grand); + grand->syncUp(); + } + parent->syncUp(); + child ->syncUp(); + if (g_grand == NULL) { + connect(NULL, 0, child); + break; + } + connect(g_grand, (g_grand->child_[0] == grand ? 0 : 1), child); + } + } + return (((SplayTree*)this)->root_ = (Node*)node); + } + + void clear(Node* node) { + if (node == NULL) return ; + clear(node->child_[0]); + clear(node->child_[1]); + delete node; + } + + Node* dup(Node* node2) { + if (node2 == NULL) return NULL; + node2->syncDown(); + Node* node = new Node(node2->key_, node2->value_); + connect(node, 0, dup(node2->child_[0])); + connect(node, 1, dup(node2->child_[1])); + node->syncUp(); + return node; + } + + Node const* findKey(Node const* node, Key const& key) const { + Node const* ret = node; + while (node != NULL) { + node->syncDown(); + ret = node; + if (!(key < node->key_)) { + if (!(node->key_< key)) break; + node = node->child_[1]; + } + else { + node = node->child_[0]; + } + } + return ret; + } + Node const* findMinMax(Node const* node, bool minimum) const { + Node const* ret = node; + for (int i = minimum ? 0 : 1; node != NULL; node = node->child_[i]) { + node->syncDown(); + ret = node; + } + return ret; + } + Node const* findOrder(Node const* node, size_t order) const { + Node const* ret = node; + while (node != NULL) { + node->syncDown(); + ret = node; + size_t ord = 1 + (node->child_[0] == NULL ? 0 : node->child_[0]->size_); + if (ord == order) return ret; + else if(ord < order){ node = node->child_[1]; order -= ord; } + else { node = node->child_[0]; } + } + return ret; + } + + void split(Node* root, Node** left, Node** right) { + if (root == NULL) { *left = NULL; *right = NULL; return ; } + root->syncDown(); + *left = root; + *right = root->child_[1]; + if (*right != NULL) { + (*left )->child_[1] = NULL; + (*right)->parent_ = NULL; + (*left )->syncUp(); + } + } + Node* merge(Node* left, Node* right) { + if (left == NULL) return right; + if (right == NULL) return left ; + left->syncDown(); + connect(left, 1, right); + left->syncUp(); + return left; + } +public: + /*! + * @brief 類似 \c stl 的 \c iterator ,不過這邊叫做\c Element + * + * 用來當作回傳資料的媒介 + */ + class Element{ + private: + typedef std::pair<Key const&, Value&> Entry; + Entry* entry_; + Node * node_; + // + void reset(Node* node) { + node_ = node; + delete entry_; + entry_ = (node == NULL ? NULL : new Entry(node->key_, node->value_)); + } + public: + Element(): entry_(NULL), node_(NULL) { + } + Element(Node* node): entry_(NULL), node_(NULL) { + reset(node); + } + Element(Element const& element2): entry_(NULL), node_(NULL) { + reset(element2.node_); + } + ~Element(){ + delete entry_; + } + + //! @brief 複製資料 + Element& copyFrom(Element const& e) { + reset(e.node_); + return *this; + } + + //! @brief 比對兩者是否為指向同一個Entry + bool same(Element const& e2) const { + return (node_ == e2.node_); + } + + //! @brief same as copyFrom + Element& operator=(Element const& e2) { + return copyFrom(e2); + } + + //! @brief 重導至\c std::pair<Key \c const&,\c Value&>* + Entry* operator->() { + return entry_; + } + + //! @brief 重導至\c std::pair<Key \c const&,\c Value&>& + Entry& operator*() { + return *entry_; + } + + //! @brief same as \c same(e2) + bool operator==(Element const& e2) const{ + return same(e2); + } + + //! @brief same as \c !same(e2) + bool operator!=(Element const& e2) const{ + return !same(e2); + } + }; + + //! @brief constructor + SplayTree(): root_(NULL) { + } + + //! @brief constructor, 複製資料 + SplayTree(SplayTree const& tree2): + root_(dup((Node*)(tree2.root_))) { + } + + //! @brief destructor + ~SplayTree(){ + clear(root_); + } + + /*! + * @brief 複製資料 + */ + SplayTree& copyFrom(SplayTree const& tree2) { + clear(root_); + root_ = dup((Node*)(tree2.root_)); + return *this; + } + + /*! + * @brief 將資料都丟到 \c tree2 身上, 並且清空自己 + */ + void moveTo(SplayTree* tree2) { + tree2->clear(); + tree2->root_ = root_; + root_ = NULL; + } + + /*! + * @brief 找出第一個(最小的) Element且 \c k <= 它的 Key, 並且回傳之. + * + * 找不到的話回傳 \c this->end() + */ + Element lowerBound(Key const& key) const { + splay(findKey(root_, key)); + if (root_ == NULL || !(root_->key_ < key)) return Element(root_); + if (root_->child_[1] == NULL) return Element(NULL); + splay(findMinMax(root_->child_[1], true)); + return Element(root_); + } + + /*! + * @brief 找出第一個(最小的) Element且 \c k < 它的 Key, 並且回傳之. + * + * 找不到的話回傳 \c this->end() + */ + Element upperBound(Key const& key) const { + splay(findKey(root_, key)); + if (root_ == NULL || key < root_->key_) return Element(root_); + if (root_->child_[1] == NULL) return Element(NULL); + splay(findMinMax(root_->child_[1], true)); + return Element(root_); + } + + /*! + * @brief 找出第一個(最小的) Element且 \c k >= 它的 Key, 並且回傳之. + * + * 找不到的話回傳 \c this->end() + */ + Element rLowerBound(Key const& key) const { + splay(findKey(root_, key)); + if (root_ == NULL || !(key < root_->key_)) return Element(root_); + if (root_->child_[0] == NULL) return Element(NULL); + splay(findMinMax(root_->child_[0], false)); + return Element(root_); + } + + /*! + * @brief 找出第一個(最小的) Element且 \c k > 它的 Key, 並且回傳之. + * + * 找不到的話回傳 \c this->end() + */ + Element rUpperBound(Key const& key) const { + splay(findKey(root_, key)); + if (root_ == NULL || root_->key_ < key) return Element(root_); + if (root_->child_[0] == NULL) return Element(NULL); + splay(findMinMax(root_->child_[0], false)); + return Element(root_); + } + + /*! + * @brief 找出 Key= \c k 的Elemenet 並回傳. 找不到的話回傳 \c this->end() + */ + Element find(Key const& key) const { + splay(findKey(root_, key)); + if (root_ != NULL && !(key < root_->key_) && !(root_->key_ < key)) { + return Element(root_); + } + return Element(NULL); + } + + /*! + * @brief 將Elements依照Key由小到大排序, 回傳第 \c ord 個Element (由0算起). + * + * 其中如果 \c ord>N-1, 則會回傳 \c this->last() + */ + Element order(size_t order) const { + if (root_ == NULL || order >= root_->size_) return Element(NULL); + splay(findOrder(root_, order + 1)); + return Element(root_); + } + + /*! + * @brief 回傳Key最小的Element, 如果SplayTree為空, 則回傳 \c this->end() + */ + Element first() const { + splay(findMinMax(root_, true)); + return Element(root_); + } + + /*! + * @brief 回傳Key最大的Element, 如果SplayTree為空, 則回傳 \c this->end() + */ + Element last() const { + splay(findMinMax(root_, false)); + return Element(root_); + } + + /*! + * @brief 回傳一個指向NULL的Element, + * + * 以供 \c find ,\c order ,\c first ,\c last 等判斷是否有找到相對應的Element + */ + Element end() const { + return Element(NULL); + } + + /*! + * @brief 回傳資料個數 + */ + size_t size() const { + return (root_ == NULL ? 0 : root_->size_); + } + + /*! + * @brief 回傳是否為空 + */ + bool empty() const{ + return (size() == 0); + } + + /*! + * @brief 清空 + */ + void clear() { + clear(root_); + root_ = NULL; + } + + /*! + * @brief 插入一組\c (Key ---> \c Value) + * + * 檢查是否已有Element的Key 為 \c key, 若有則回傳 \c false , 否則將 + * 一個 (Key -> Value) = (\c key -> \c value)的Element加入, 並回傳 \c true + */ + bool insert(Key const& key, Value const& value) { + if (root_ == NULL) { + root_ = new Node(key, value); + } + else { + Node* parent = (Node*)findKey(root_, key); + if (!(parent->key_ < key) && !(key < parent->key_)) { + splay(parent); + return false; + } + Node* new_node = new Node(key, value); + connect(parent, (parent->key_ < key ? 1 : 0), new_node); + parent->syncUp(); + splay(new_node); + } + return true; + } + + /*! + * @brief 刪除一組資料 + * + * 檢查是否已有Element的Key 為 \c key, 若有則刪除之, 並回傳 \c true, + * 否則則回傳 \c false + */ + bool erase(Key const& key) { + if (root_ == NULL) return false; + Node* body = (Node*)findKey(root_, key); + if (body->key_ < key || key < body->key_) { + splay(body); + return false; + } + Node* ghost; + if (body->child_[1] == NULL) { + ghost = body->child_[0]; + if (ghost != NULL) ghost->syncDown(); + } + else { + ghost = (Node*)findMinMax(body->child_[1], true); + connect(ghost, 0, body->child_[0]); + if (ghost != body->child_[1]) { + connect(ghost->parent_, 0, ghost->child_[1]); + connect(ghost, 1, body->child_[1]); + for (Node* a = ghost->parent_; a != ghost; a = a->parent_) + a->syncUp(); + } + ghost->syncUp(); + } + Node* parent = body->parent_; + connect(parent, parent != NULL && parent->child_[0] == body ? 0 : 1, ghost); + delete body; + splay(ghost != NULL ? ghost : parent); + return true; + } + + /*! + * @brief 將所有Element的Key同加上 \c delta + */ + void keyOffset(Key const& delta) { + if (root_ != NULL) { + root_->keyOffset(delta); + } + } + + /*! + * @brief 將\c tree2 清空, 再將所有Key > \c upper_bound 的Element都丟過去 + */ + void splitOut(Key const& upper_bound, SplayTree* right) { + right->clear(); + if (rLowerBound(upper_bound) != end()) { + split(root_, &root_, &(right->root_)); + } + else { + right->root_ = root_; + root_ = NULL; + } + } + + /*! + * @brief 合併 + * + * 檢查是否自己中的 Key 都小於 \c tree2 中的Key, 是的話把 \c tree2` + * 中的 Element 都搬到自己這, 同時清空 \c tree2 , 否則回傳 \c false + */ + bool mergeAfter(SplayTree* tree2) { + if (root_ == NULL || tree2->root_ == NULL || + last()->first < tree2->first()->first) { + root_ = merge(root_, tree2->root_); + tree2->root_ = NULL; + return true; + } + return false; + } + + /*! + * @brief 合併 + * + * 檢查是否自己中的 Key 都小於 \c tree2 中的Key, 或是完全相反, + * 是的話把 \c tree2`中的 Element 都搬到自己這, + * 同時清空 \c tree2 , 否則回傳 \c false + */ + bool merge(SplayTree* tree2) { + if (root_ == NULL || tree2->root_ == NULL || + last()->first < tree2->first()->first) { + root_ = merge(root_, tree2->root_); + } + else if(tree2->last()->first < first()->first) { + root_ = merge(tree2->root_, root_); + } + else { + return false; + } + tree2->root_ = NULL; + return true; + } + + /*! + * @brief 就像\c stl::map::operator[] + * + * 會先檢查是否已有Element的Key 為 \c key, 若有則回傳相對應的Value的Reference + * 否則先執行 \c insert(key,Value()) 再回傳相對應的Reference + */ + Value& operator[](Key const& key) { + if (find(key) == end()) insert(key, Value()); + return root_->value_; + } + + //! @brief same as \c copyFrom(tree2) + SplayTree& operator=(SplayTree const& tree2) { + return copyFrom(tree2); + } +}; + +/*! + * @brief + * + * 基本上跟SplayTree一樣, 不過這邊結合線段樹, 多了區間操作 + * (線段樹相關operator定義請見 \c SegmentTree ) + * + * Template Class Operators Request + * -------------------------------- + * + * |const?|Typename|Operator | Parameters |Return Type | Description | + * |-----:|:------:|----------:|:-------------|:----------:|:------------------| + * |const |Key |operator+ |(Key \c k) | Key |相加 | + * |const |Key |operator< |(Key \c k) | bool |大小比較 | + * | |Key |operator= |(Key \c k) | Key |copy oper | + * | |Key |Key |(int \c n) | |構子,\c n 永遠是0 | + * | |Value | Value |( ) | |建構子 | + * + * @note: + * -假設現在有兩個SplayTree `A` 和 `B`, 則: + * -執行 `B.moveTo(&A)` 後 `B` 會變成空的, `A` 原本擁有的資料也會覆蓋掉 + * -行 `A.merge(&B)` 或 `A.mergeAfter(&B)` 後 + * 如果檢查發現確實可以merge, 則之後 `B` 會變成空的 + * + * @author cat_leopard + */ +template<class Key, class Value> +class SplayTree_Range { +private: + struct Node { + Value valueOffset_; + Value range_; + Key key_; + Key keyOffset_; + Value value_; + bool same_; + 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) { + same_ = false; + size_ = 1; + parent_ = NULL; + child_[0] = NULL; + child_[1] = NULL; + } + // + void keyOffset(Key const& delta) { + key_ = key_ + delta; + keyOffset_ = keyOffset_ + delta; + } + void valueUpdate(Value const& delta, bool over) { + if(over) { + value_ = delta * size_; + valueOffset_ = delta; + range_ = delta * size_; + same_ = true; + } + else { + value_ = value_ + delta * size_; + valueOffset_ = valueOffset_ + delta; + range_ = range_ + delta * size_; + } + } + void syncDown() const { + for (size_t i = 0; i < 2; i++) { + if (child_[i] == NULL) continue; + child_[i]->keyOffset(keyOffset_); + child_[i]->valueUpdate(valueOffset_, same_); + } + ((Node*)this)->keyOffset_ = Key(0); + ((Node*)this)->valueOffset_ = Value(0); + ((Node*)this)->same_ = false; + } + void syncUp() const { + ((Node*)this)->size_ = 1; + Value* v[3] = {&(((Node*)this)->value_), NULL, NULL}; + size_t vct = 1; + for (size_t i = 0; i < 2; i++) { + if (child_[i] == NULL) continue; + ((Node*)this)->size_ += child_[i]->size_; + v[vct++] = &(child_[i]->range_); + } + if (vct == 1) ((Node*)this)->range_ = (*v[0]); + else if(vct == 2) ((Node*)this)->range_ = (*v[0]) | (*v[1]); + else ((Node*)this)->range_ = (*v[0]) | (*v[1]) | (*v[2]); + } + }; + + Node* root_; + + //! @brief 指定左子or右子, 連接parent<--->child + void connect(Node const* parent, size_t left_right, Node const* child) const { + Node* p = (Node*)parent; + Node* c = (Node*)child; + if (p != NULL) p->child_[left_right] = c; + if (c != NULL) c->parent_ = p; + } + + //! @brief 一路往上轉 + Node const* splay(Node const* node) const { + if (node != NULL && node->parent_ != NULL) { + for (const Node *g_grand, *grand, *parent, *child = node; ; ) { + g_grand = (grand = parent = child->parent_)->parent_; + size_t pc = (parent->child_[0] == child ? 0 : 1); + connect(parent, pc, child->child_[!pc]); + connect(child , !pc, parent); + if (g_grand != NULL) { + g_grand = (grand = g_grand)->parent_; + size_t gp = (grand->child_[0] == parent ? 0 : 1); + Node const* who = (pc == gp ? parent : child); + connect(grand, gp, who->child_[!gp]); + connect(who , !gp, grand); + grand->syncUp(); + } + parent->syncUp(); + child ->syncUp(); + if (g_grand == NULL) { + connect(NULL, 0, child); + break; + } + connect(g_grand, (g_grand->child_[0] == grand ? 0 : 1), child); + } + } + return (((SplayTree_Range*)this)->root_ = (Node*)node); + } + + void clear(Node* node) { + if (node == NULL) return ; + clear(node->child_[0]); + clear(node->child_[1]); + delete node; + } + + Node* dup(Node* node2) { + if (node2 == NULL) return NULL; + node2->syncDown(); + Node* node = new Node(node2->key_, node2->value_); + connect(node, 0, dup(node2->child_[0])); + connect(node, 1, dup(node2->child_[1])); + node->syncUp(); + return node; + } + + Node const* findKey(Node const* node, Key const& key) const { + Node const* ret = node; + while (node != NULL) { + node->syncDown(); + ret = node; + if (!(key < node->key_)) { + if (!(node->key_< key)) break; + node = node->child_[1]; + } + else { + node = node->child_[0]; + } + } + return ret; + } + Node const* findMinMax(Node const* node, bool minimum) const { + Node const* ret = node; + for (int i = minimum ? 0 : 1; node != NULL; node = node->child_[i]) { + node->syncDown(); + ret = node; + } + return ret; + } + Node const* findOrder(Node const* node, size_t order) const { + Node const* ret = node; + while (node != NULL) { + node->syncDown(); + ret = node; + size_t ord = 1 + (node->child_[0] == NULL ? 0 : node->child_[0]->size_); + if (ord == order) return ret; + else if(ord < order){ node = node->child_[1]; order -= ord; } + else { node = node->child_[0]; } + } + return ret; + } + + void split(Node* root, Node** left, Node** right) { + if (root == NULL) { *left = NULL; *right = NULL; return ; } + root->syncDown(); + *left = root; + *right = root->child_[1]; + if (*right != NULL) { + (*left )->child_[1] = NULL; + (*right)->parent_ = NULL; + (*left )->syncUp(); + } + } + Node* merge(Node* left, Node* right) { + if (left == NULL) return right; + if (right == NULL) return left ; + left->syncDown(); + connect(left, 1, right); + left->syncUp(); + return left; + } +public: + /*! + * @brief 類似 \c stl 的 \c iterator ,不過這邊叫做\c Element + * + * 用來當作回傳資料的媒介 + */ + class Element{ + private: + typedef std::pair<Key const&, Value&> Entry; + Entry* entry_; + Node * node_; + // + void reset(Node* node) { + node_ = node; + delete entry_; + entry_ = (node == NULL ? NULL : new Entry(node->key_, node->value_)); + } + public: + Element(): entry_(NULL), node_(NULL) { + } + Element(Node* node): entry_(NULL), node_(NULL) { + reset(node); + } + Element(Element const& element2): entry_(NULL), node_(NULL) { + reset(element2.node_); + } + ~Element(){ + delete entry_; + } + + //! @brief 複製資料 + Element& copyFrom(Element const& e) { + reset(e.node_); + return *this; + } + + //! @brief 比對兩者是否為指向同一個Entry + bool same(Element const& e2) const { + return (node_ == e2.node_); + } + + //! @brief same as copyFrom + Element& operator=(Element const& e2) { + return copyFrom(e2); + } + + //! @brief 重導至\c std::pair<Key \c const&,\c Value&>* + Entry* operator->() { + return entry_; + } + + //! @brief 重導至\c std::pair<Key \c const&,\c Value&>& + Entry& operator*() { + return *entry_; + } + + //! @brief same as \c same(e2) + bool operator==(Element const& e2) const{ + return same(e2); + } + + //! @brief same as \c !same(e2) + bool operator!=(Element const& e2) const{ + return !same(e2); + } + }; + + //! @brief constructor + SplayTree_Range(): root_(NULL) { + } + + //! @brief constructor, 複製資料 + SplayTree_Range(SplayTree_Range const& tree2): + root_(dup((Node*)(tree2.root_))) { + } + + //! @brief destructor + ~SplayTree_Range() { + clear(root_); + } + + /*! + * @brief 複製資料 + */ + SplayTree_Range& copyFrom(SplayTree_Range const& tree2) { + clear(root_); + root_ = dup((Node*)(tree2.root_)); + return *this; + } + + /*! + * @brief 將資料都丟到 \c tree2 身上, 並且清空自己 + */ + void moveTo(SplayTree_Range* tree2) { + tree2->clear(); + tree2->root_ = root_; + root_ = NULL; + } + + /*! + * @brief 找出第一個(最小的) Element且 \c k <= 它的 Key, 並且回傳之. + * + * 找不到的話回傳 \c this->end() + */ + Element lowerBound(Key const& key) const { + splay(findKey(root_, key)); + if (root_ == NULL || !(root_->key_ < key)) return Element(root_); + if (root_->child_[1] == NULL) return Element(NULL); + splay(findMinMax(root_->child_[1], true)); + return Element(root_); + } + + /*! + * @brief 找出第一個(最小的) Element且 \c k < 它的 Key, 並且回傳之. + * + * 找不到的話回傳 \c this->end() + */ + Element upperBound(Key const& key) const { + splay(findKey(root_, key)); + if (root_ == NULL || key < root_->key_) return Element(root_); + if (root_->child_[1] == NULL) return Element(NULL); + splay(findMinMax(root_->child_[1], true)); + return Element(root_); + } + + /*! + * @brief 找出第一個(最小的) Element且 \c k >= 它的 Key, 並且回傳之. + * + * 找不到的話回傳 \c this->end() + */ + Element rLowerBound(Key const& key) const { + splay(findKey(root_, key)); + if (root_ == NULL || !(key < root_->key_)) return Element(root_); + if (root_->child_[0] == NULL) return Element(NULL); + splay(findMinMax(root_->child_[0], false)); + return Element(root_); + } + + /*! + * @brief 找出第一個(最小的) Element且 \c k > 它的 Key, 並且回傳之. + * + * 找不到的話回傳 \c this->end() + */ + Element rUpperBound(Key const& key) const { + splay(findKey(root_, key)); + if (root_ == NULL || root_->key_ < key) return Element(root_); + if (root_->child_[0] == NULL) return Element(NULL); + splay(findMinMax(root_->child_[0], false)); + return Element(root_); + } + + /*! + * @brief 找出 Key= \c k 的Elemenet 並回傳. 找不到的話回傳 \c this->end() + */ + Element find(Key const& key) const { + splay(findKey(root_, key)); + if (root_ != NULL && !(key < root_->key_) && !(root_->key_ < key)) { + return Element(root_); + } + return Element(NULL); + } + + /*! + * @brief 將Elements依照Key由小到大排序, 回傳第 \c ord 個Element (由0算起). + * + * 其中如果 \c ord>N-1, 則會回傳 \c this->last() + */ + Element order(size_t order) const { + if (root_ == NULL || order >= root_->size_) return Element(NULL); + splay(findOrder(root_, order + 1)); + return Element(root_); + } + + /*! + * @brief 回傳Key最小的Element, 如果SplayTree為空, 則回傳 \c this->end() + */ + Element first() const { + splay(findMinMax(root_, true)); + return Element(root_); + } + + /*! + * @brief 回傳Key最大的Element, 如果SplayTree為空, 則回傳 \c this->end() + */ + Element last() const { + splay(findMinMax(root_, false)); + return Element(root_); + } + + /*! + * @brief 回傳一個指向NULL的Element, + * + * 以供 \c find ,\c order ,\c first ,\c last 等判斷是否有找到相對應的Element + */ + Element end() const { + return Element(NULL); + } + + /*! + * @brief 回傳資料個數 + */ + size_t size() const { + return (root_ == NULL ? 0 : root_->size_); + } + + /*! + * @brief 回傳是否為空 + */ + bool empty() const{ + return (size() == 0); + } + + /*! + * @brief 查找 + * + * 詢問目前整個range的值 + */ + Value query() const { + if (root_ == NULL) return Value(0); + return root_->range_; + } + + /*! + * @brief 查找 + * + * 詢問給定range的值 + */ + Value query(Key const& first, Key const& last) const { + SplayTree_Range* self = (SplayTree_Range*)this; + Node* tmp; + rUpperBound(first); + self->split(self->root_, &tmp, &(self->root_)); + upperBound(last); + Value ret(0); + if (root_ != NULL && root_->child_[0] != NULL) { + ret = root_->child_[0]->range_; + } + self->root_ = self->merge(tmp, self->root_); + return ret; + } + + /*! + * @brief 清空 + */ + void clear() { + clear(root_); + root_ = NULL; + } + + /*! + * @brief 插入一組\c (Key ---> \c Value) + * + * 檢查是否已有Element的Key 為 \c key, 若有則回傳 \c false , 否則將 + * 一個 (Key -> Value) = (\c key -> \c value)的Element加入, 並回傳 \c true + */ + bool insert(Key const& key, Value const& value) { + if (root_ == NULL) { + root_ = new Node(key, value); + } + else { + Node* parent = (Node*)findKey(root_, key); + if (!(parent->key_ < key) && !(key < parent->key_)) { + splay(parent); + return false; + } + Node* new_node = new Node(key, value); + connect(parent, (parent->key_ < key ? 1 : 0), new_node); + parent->syncUp(); + splay(new_node); + } + return true; + } + + /*! + * @brief 刪除一組資料 + * + * 檢查是否已有Element的Key 為 \c key, 若有則刪除之, 並回傳 \c true, + * 否則則回傳 \c false + */ + bool erase(Key const& key) { + if (root_ == NULL) return false; + Node* body = (Node*)findKey(root_, key); + if (body->key_ < key || key < body->key_) { + splay(body); + return false; + } + Node* ghost; + if (body->child_[1] == NULL) { + ghost = body->child_[0]; + if (ghost != NULL) ghost->syncDown(); + } + else { + ghost = (Node*)findMinMax(body->child_[1], true); + connect(ghost, 0, body->child_[0]); + if (ghost != body->child_[1]) { + connect(ghost->parent_, 0, ghost->child_[1]); + connect(ghost, 1, body->child_[1]); + for (Node* a = ghost->parent_; a != ghost; a = a->parent_) + a->syncUp(); + } + ghost->syncUp(); + } + Node* parent = body->parent_; + connect(parent, parent != NULL && parent->child_[0] == body ? 0 : 1, ghost); + delete body; + splay(ghost != NULL ? ghost : parent); + return true; + } + + /*! + * @brief 將所有Element的Key同加上 \c delta + */ + void keyOffset(Key const& delta) { + if (root_ != NULL) { + root_->keyOffset(delta); + } + } + + /*! + * @brief 將所有Element的Value同加上 \c delta + */ + void valueOffset(Value const& delta){ + if (root_ != NULL) { + root_->valueUpdate(delta, false); + } + } + + /*! + * @brief 將所有Element的Value全部設定成\c value + */ + void valueOverride(Value const& value){ + if(root_ != NULL){ + root_->valueUpdate(value, true); + } + } + + /*! + * @brief 將\c tree2 清空, 再將所有Key > \c upper_bound 的Element都丟過去 + */ + void splitOut(Key const& upper_bound, SplayTree_Range* right) { + right->clear(); + if (rLowerBound(upper_bound) != end()) { + split(root_, &root_, &(right->root_)); + } + else { + right->root_ = root_; + root_ = NULL; + } + } + + /*! + * @brief 合併 + * + * 檢查是否自己中的 Key 都小於 \c tree2 中的Key, 是的話把 \c tree2` + * 中的 Element 都搬到自己這, 同時清空 \c tree2 , 否則回傳 \c false + */ + bool mergeAfter(SplayTree_Range* tree2) { + if (root_ == NULL || tree2->root_ == NULL || + last()->first < tree2->first()->first) { + root_ = merge(root_, tree2->root_); + tree2->root_ = NULL; + return true; + } + return false; + } + + /*! + * @brief 合併 + * + * 檢查是否自己中的 Key 都小於 \c tree2 中的Key, 或是完全相反, + * 是的話把 \c tree2`中的 Element 都搬到自己這, + * 同時清空 \c tree2 , 否則回傳 \c false + */ + bool merge(SplayTree_Range* tree2) { + if (root_ == NULL || tree2->root_ == NULL || + last()->first < tree2->first()->first) { + root_ = merge(root_, tree2->root_); + } + else if(tree2->last()->first < first()->first) { + root_ = merge(tree2->root_, root_); + } + else { + return false; + } + tree2->root_ = NULL; + return true; + } + + /*! + * @brief 就像\c stl::map::operator[] + * + * 會先檢查是否已有Element的Key 為 \c key, 若有則回傳相對應的Value的Reference + * 否則先執行 \c insert(key,Value()) 再回傳相對應的Reference + */ + Value& operator[](Key const& key) { + if (find(key) == end()) insert(key, Value()); + return root_->value_; + } + + //! @brief same as \c copyFrom(tree2) + SplayTree_Range& operator=(SplayTree_Range const& tree2){ + return copyFrom(tree2); + } +}; + +} #endif // dsa_SplayTree_h__ diff --git a/meowpp/dsa/VP_Tree.h b/meowpp/dsa/VP_Tree.h index e2daa28..75186e6 100644 --- a/meowpp/dsa/VP_Tree.h +++ b/meowpp/dsa/VP_Tree.h @@ -7,164 +7,331 @@ #include <list> #include <vector> +#include <stack> #include <queue> -namespace meow{ - //# - //#=== meow:: *VP_Tree<Vector, Scalar>* (C++ class) - //#==== Description - //# `VP_Tree` 用來維護由 *N個K維度向量所成的集合*, - //# 並可於該set中查找 *前i個離給定向量最接近的向量*. + - //# 不像 `KD_Tree` 二分樹每次都選擇一個維度去分, 分成小的跟大的, - //# `VP_Tree` 每次選一個點, 將資料分成 離這個點近的, 跟離這個點遠的. - //# 至於怎麼選呢...., 嘛還沒研究, 先random - //# - //# .參考資料連結: - //# * http://stevehanov.ca/blog/index.php?id=130[link] - //# * http://pnylab.com/pny/papers/vptree/vptree[link] - //# - //#==== 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`) | Vector& | copy operator - //#|const | Vector|operator< |(Vector `v`) | bool | 權重比較 - //#|const | Scalar| 'Scalar' |(int `n`) | Scalar | 建構子, - //# 其中一定`n=0 or 4` - //#|const | Scalar|operator* |(Scalar `s`) | Scalar | 相乘 - //#|const | Scalar|operator+ |(Scalar `s`) | Scalar | 相加 - //#|const | Scalar|operator- |(Scalar `s`) | Scalar | 相差 - //#|const | Scalar|operator- |( ) | Scalar | 取負號 - //#|const | Scalar|operator< |(Scalar `s`) | bool | 大小比較 - //#|===================================================================== - //# - template<class Vector, class Scalar> - class VP_Tree{ - public: - //#==== Custom Type Definitions - //# * `Vectors` <- `std::vector<Vector>` - //# - typedef typename std::vector<Vector> Vectors; - private: - // - struct Node{ - size_t _index; - Scalar _threshold; - Node* _nearChild; - Node* _farChild; - Node(size_t __index); - }; - struct Answer{ - size_t _index; - Scalar _dist2; - // - Answer(size_t __index, Scalar const& __dist2); - Answer(Answer const& __answer2); - }; - class AnswerCompare{ - private: - Vectors const* _vectors; - bool _cmpValue; - public: - AnswerCompare(Vectors const* __vectors, bool __cmpValue); - bool operator()(Answer const& __a, Answer const& __b) const; - }; - 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; - int distanceCompare(Scalar const& __a2, Scalar const& __b2, - Scalar const& __c2) const; - Scalar split(ssize_t __first, ssize_t __last, size_t __order, - Vector const& __center); - // - Node* build(ssize_t __first, ssize_t __last); - void query(Vector const& __vector, - size_t __k, - AnswerCompare const& __cmp, - Node const* __node, - Answers* __out) const; - void clear(Node* __root); - Node* dup(Node* __root); - public: - VP_Tree(); - VP_Tree(VP_Tree const& __tree2); - VP_Tree(size_t __dimension); - ~VP_Tree(); - VP_Tree& operator=(VP_Tree const& __tree2); +namespace meow { - //#==== Support Methods - //# - //# * N <- `this` 中擁有的資料數 - //# * D <- `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(); +/*! + * @brief 跟KD_Tree很像歐 + * + * \c VP_Tree 用來維護由 \b N個K維度向量所成的集合 , + * 並可於該set中查找 \b 前i個離給定向量最接近的向量* . + * 不像 \c KD_Tree 二分樹每次都選擇一個維度去分, 分成小的跟大的, + * \c VP_Tree 每次選一個點, 將資料分成 離這個點近的, 跟離這個點遠的. + * 至於怎麼選呢...., 嘛還沒研究, 先random + * + * 參考資料連結: + * - http://stevehanov.ca/blog/index.php?id=130 + * - http://pnylab.com/pny/papers/vptree/vptree + * + * Template Class Operators Request + * -------------------------------- + * + * |const?|Typename|Operator | Parameters |Return Type | Description | + * |-----:|:------:|----------:|:-------------|:----------:|:------------------| + * |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 | 建構子, + * 其中一定\c n=0or4 | + * |const | Scalar|operator* |(Scalar \c s) | Scalar | 相乘 | + * |const | Scalar|operator+ |(Scalar \c s) | Scalar | 相加 | + * |const | Scalar|operator- |(Scalar \c s) | Scalar | 相差 | + * |const | Scalar|operator- |( ) | Scalar | 取負號 | + * |const | Scalar|operator< |(Scalar \c s) | bool | 大小比較 | + * + * @note: + * -實測結果發覺, 維度小的時候, 比起中規中矩的 \c KD_Tree, \c VP_Tree 有 + * \b random 於其中, 因此時間複雜度只是期望值 \c O(logN) 但是測資大到 + * 一定程度, \c KD_Tree 效率會一整個大幅掉下, 但 \c VP_Tree 幾乎不受影響 + * -TODO \c insert(), \c erase() 算是未完成功能 + */ +template<class Vector, class Scalar> +class VP_Tree { +public: + typedef std::vector<Vector> Vectors; +private: + struct Node { + size_t index_; + Scalar threshold_; + Node* nearChild_; + Node* farChild_; + // + Node(size_t index): index_(index), nearChild_(NULL), farChild_(NULL){ + } + }; + struct Answer { + size_t index_; + Scalar dist2_; + // + Answer(size_t index, Scalar const& dist2): index_(index), dist2_(dist2){ + } + Answer(Answer const& answer2): + index_(answer2.index_), dist2_(answer2.dist2_){ + } + }; + class AnswerCompare { + private: + Vectors const* vectors_; + bool cmpValue_; + public: + AnswerCompare(Vectors const* vectors, bool cmpValue): + vectors_(vectors), cmpValue_(cmpValue){ + } + bool operator()(Answer const& a, Answer const& b) const { + if (a.dist2_ < b.dist2_) return true; + if (b.dist2_ < a.dist2_) return false; + return (cmpValue_ && ((*vectors_)[a.index_] < (*vectors_)[b.index_])); + } + }; + 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]); + return ret; + } + int distanceCompare(Scalar const& a2, Scalar const& b2, + Scalar const& c2) const { + if (b2 < 0) { + return -distanceCompare(c2, -b2, a2); + } + Scalar cab(c2 - a2 - b2); + if (cab < Scalar(0)) return 1; + Scalar ab2(Scalar(4) * a2 * b2), cab2(squ(cab)); + if ( ab2 < cab2) return -1; + else if (cab2 < ab2) return 1; + else return 0; + } + Scalar split(ssize_t first, ssize_t last, size_t order, + Vector const& center) { + ssize_t first0 = first; + std::vector<Scalar> dist2(last - first + 1); + for (ssize_t i = first; i <= last; i++) { + dist2[i - first0] = distance2(vectors_[i], center); + } + while (first < last) { + size_t thresholdindex_ = first + rand() % (last - first + 1); + Scalar threshold(dist2[thresholdindex_ - first0]); + size_t large_first = last + 1; + for( ssize_t i=first; first<=(ssize_t)large_first-1; large_first--) { + if (threshold < dist2[large_first - 1 - first0]) continue; + while (i < (ssize_t)large_first-1&&!(threshold < dist2[i-first0])) i++; + if (i < (ssize_t)large_first - 1){ + std::swap(dist2 [large_first - 1 - first0], dist2 [i - first0]); + std::swap(vectors_[large_first - 1 ], vectors_[i ]); + i++; + } + else { + break; + } + } + if (large_first == (size_t)last + 1) { + std::swap(dist2 [thresholdindex_-first0], dist2 [last-first0]); + std::swap(vectors_[thresholdindex_ ], vectors_[last ]); + if ((ssize_t)order == last - first) { + first = last; + break; + } + last--; + } + else { + if (order < large_first - first) { + last = large_first - 1; + } + else { + order -= large_first - first; + first = large_first; + } + } + } + return dist2[first - first0]; + } + // + Node* build(ssize_t first, ssize_t last) { + if (first > last) return NULL; + Node* ret = new Node(first); + if (first < last) { + std::swap(vectors_[first], + vectors_[first + rand() % (last - first + 1)]); + ssize_t mid = (first + 1 + last + 1) / 2; + ret->threshold_ = split(first + 1, last, mid - (first + 1), + vectors_[first]); + ret->nearChild_ = build(first + 1, mid - 1 ); + ret->farChild_ = build( mid , last); + } + return ret; + } + void query(Vector const& vector, + size_t k, + AnswerCompare const& cmp, + Node const* node, + Answers* out) const { + if (node == NULL) return ; + Scalar dist2 = distance2(vector, vectors_[node->index_]); + Answer my_ans(node->index_, dist2); + if (out->size() < k || cmp(my_ans, out->top())) { + out->push(my_ans); + if (out->size() > k) { + out->pop(); + } + } + if (node->nearChild_ == NULL && node->farChild_ == NULL) return ; + if (out->size() < k || distanceCompare(dist2, -out->top().dist2_, + node->threshold_) <= 0) { + query(vector, k, cmp, node->nearChild_, out); + } + if (out->size() < k || distanceCompare(dist2, out->top().dist2_, + node->threshold_) >= 0) { + query(vector, k, cmp, node->farChild_, out); + } + } + void clear(Node* root) { + if(root == NULL) return ; + clear(root->nearChild_); + clear(root->farChild_); + delete root; + } + Node* dup(Node* root) { + if(root == NULL) return ; + Node* ret = new Node(root->index_); + ret->threshold_ = root->threshold_; + ret->nearChild_ = dup(root->nearChild_); + ret->farChild_ = dup(root->farChild_ ); + return ret; + } +public: + //! @brief constructor, with dimension = 1 + VP_Tree(): root_(NULL), vectors_(0), dimension_(1), needRebuild_(false){ + reset(0); + } + + //! @brief constructor, 複製資料 + VP_Tree(VP_Tree const& tree2): + vectors_(tree2.vectors_), + root_(dup(tree2.root_)), + dimension_(tree2.dimension_), + needRebuild_(tree2.needRebuild_) { + } + + //! @brief constructor, 給定dimension + VP_Tree(size_t dimension): + vectors_(0), + root_(NULL), + dimension_(0), + needRebuild_(false) { + reset(dimension); + } + + //! @brief destructor + ~VP_Tree() { + clear(root_); + } + + /*! + * @brief 複製資料 + */ + VP_Tree& copyFrom(VP_Tree const& tree2) { + reset(tree2.dimension_); + vectors_ = tree2.vectors_; + root_ = dup(tree2.root_); + needRebuild_ = tree2.needRebuild_; + return *this; + } + /*! + * @brief 將給定的Vector加到set中 + */ + void insert(Vector const& vector) { + vectors_.push_back(vector); + needRebuild_ = true; + } - //#|const|query|(Vector const& `v`,\size_t `i`,\bool `cmp`)|Vectors - //#|O(logN) ~Expected~ - //#|於set中找尋距離 `v` 前 `i` 近的向量, 並依照由近而遠的順序排序. - //# 如果有兩個向量 `v1`,`v2` 距離一樣, 且 `cmp` 為 `true` , 則直接依照 - //# `v1 < v2` 來決定誰在前面. 最後回傳一陣列包含所有解. - Vectors query(Vector const& __vector, - size_t __nearestNumber, - bool __compareWholeVector) const; + /*! + * @brief 將給定的Vector從set移除 + */ + bool erase (Vector const& vector) { + for (ssize_t i = 0, I = vectors_.size(); i < I; i++) { + if (vectors_[i] == vector) { + if (i != I - 1) std::swap(vectors_[i], vectors_[I - 1]); + needRebuild_ = true; + vectors_.pop_back(); + return true; + } + } + return false; + } + /*! + * @brief 檢查至今是否有 insert/erase 被呼叫來決定是否 \c rebuild() + */ + void build() { + if (needRebuild_) { + forceBuild(); + } + } - //#||clear|()|void|O(1) - //#|清空所有資料 - void clear(); + /*! + * @brief 重新建樹 + */ + void forceBuild() { + root_ = build(0, (size_t)vectors_.size() - 1); + needRebuild_ = false; + } + /*! + * @brief 查找 + * + * 於set中找尋距離指定向量前 \c i 近的向量, 並依照由近而遠的順序排序. + * 如果有兩個向量\c v1,v2 距離一樣, 且 \c cmp 為\c true , 則直接依照 + * \c v1<v2 來決定誰在前面. 最後回傳一陣列包含所有解. + */ + Vectors query(Vector const& vector, + size_t nearestNumber, + bool compareWholeVector) const { + ((VP_Tree*)this)->build(); + AnswerCompare cmp(&vectors_, compareWholeVector); + Answers answers(cmp); + query(vector, nearestNumber, cmp, root_, &answers); + std::stack<Answer> rev; + for ( ; !answers.empty(); answers.pop()) rev.push(answers.top()); + Vectors ret; + for ( ; !rev.empty(); rev.pop()) ret.push_back(vectors_[rev.top().index_]); + return ret; + } - //#||reset|(size_t `dimension`)|size_t|O(1) - //#|清空所有資料並且指定維度為 `max(1, dimension)` 並且回傳指定後的維度 - size_t reset(size_t __dimension); + /*! + * @brief 清空所有資料 + */ + void clear() { + clear(root_); + vectors_.clear(); + root_ = NULL; + needRebuild_ = false; + } + /*! + * @brief 清空所有資料並重新給定維度 + */ + size_t reset(size_t dimension) { + clear(); + 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); + } +}; - //#|===================================================================== - }; - //# - //#[NOTE] - //#======================================== - //# * 實測結果發覺, 維度小的時候, 比起中規中矩的 `KD_Tree`, `VP_Tree` 有 - //# 'randomp' 於其中, 因此時間複雜度只是期望值 'O(logN)' 但是測資大到 - //# 一定程度, `KD_Tree` 效率會一整個大幅掉下, 但 `VP_Tree` 幾乎不受影響 - //# * 'TODO' `insert()`, `erase()` 算是未完成功能 - //# - //#======================================== - //# - //# ''' } -#include "VP_Tree.hpp" - #endif // dsa_VP_Tree_H__ |