diff options
Diffstat (limited to 'meowpp/dsa/VP_Tree.h')
| -rw-r--r-- | meowpp/dsa/VP_Tree.h | 164 |
1 files changed, 164 insertions, 0 deletions
diff --git a/meowpp/dsa/VP_Tree.h b/meowpp/dsa/VP_Tree.h new file mode 100644 index 0000000..f8ab393 --- /dev/null +++ b/meowpp/dsa/VP_Tree.h @@ -0,0 +1,164 @@ +#ifndef VP_Tree_H__ +#define VP_Tree_H__ + +#include <list> +#include <vector> +#include <cstdlib> +#include <queue> +#include "../utility.h" + +namespace meow{ + //# + //#=== meow:: *VP_Tree<Vector, Scalar>* (C++ class) + //#==== Description + //# `VP_Tree` 用來維護由 *N個K維度向量所成的集合*, + //# 並可於該set中查找 *前i個離給定向量最接近的向量*. + + //# 不像 `KD_Tree` 二分樹每次都選擇一個維度去分, 分成小的跟大的, + //# `VP_Tree` 每次選一個點, 將資料分成 離這個點近的, 跟離這個點遠的. + //# 至於怎麼選呢...., 嘛還沒研究, 先random + //# + //#==== 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); + // + void print(Node* __node, int depth = 1, + Node* __parent = NULL, bool __near = true) const; + public: + VP_Tree(); + VP_Tree(VP_Tree const& __tree2); + VP_Tree(size_t __dimension); + ~VP_Tree(); + VP_Tree& operator=(VP_Tree const& __tree2); + + //#==== 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(); + + + //#|const|query|(Vector const& `v`,\size_t `i`,\bool `cmp`)|Vectors + //#|O(KN ^1-1/K^ ) + //#|於set中找尋距離 `v` 前 `i` 近的向量, 並依照由近而遠的順序排序. + //# 如果有兩個向量 `v1`,`v2` 距離一樣, 且 `cmp` 為 `true` , 則直接依照 + //# `v1 < v2` 來決定誰在前面. 最後回傳一陣列包含所有解. + Vectors query(Vector const& __vector, + size_t __nearestNumber, + bool __compareWholeVector) const; + + + //#||clear|()|void|O(1) + //#|清空所有資料 + void clear(); + + + //#||reset|(size_t `dimension`)|size_t|O(1) + //#|清空所有資料並且指定維度為 `max(1, dimension)` 並且回傳指定後的維度 + size_t reset(size_t __dimension); + + + //#|===================================================================== + + void print() const; + }; + //# + //#[NOTE] + //#======================================== + //#======================================== + //# + //# ''' +} + +#include "VP_Tree.hpp" + +#endif // VP_Tree_H__ |