1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
|
#ifndef KD_Tree_H__
#define KD_Tree_H__
#include <list>
#include <vector>
#include <cstdlib>
#include <queue>
#include <utility.h>
namespace meow{
//#
//#=== meow:: *KD_Tree<Vector, Scalar>* (C++ class)
//#==== Description
//# `KD_Tree` 全名k-dimension tree, 用來維護由 *N個K維度向量所成的集合*,
//# 並可於該set中查找 *前i個離給定向量最接近的向量*
//#
//#==== Template Class Operators Request
//#[options="header",width="70%",cols="1>m,1<,3<s,5<,3<,15<",grid="rows"]
//#|=====================================================================
//#|Const?|Typename| Operator | Parameters | Return_Type| Description
//#|const | Vector|operator[] |(size_t `n`) | Scalar | 取得第 `n` 維度量
//#|const | Vector|operator< |(Vector `v`) | bool | 權重比較
//#|const | Scalar|operator* |(Scalar `s`) | Scalar | 相乘
//#|const | Scalar|operator+ |(Scalar `s`) | Scalar | 相加
//#|const | Scalar|operator- |(Scalar `s`) | Scalar | 相差
//#|const | Scalar|operator< |(Scalar `s`) | bool | 大小比較
//#|=====================================================================
//#
template<class Vector, class Scalar>
class KD_Tree{
private:
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,
size_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();
//#||forceBuild|()|void|O(KN logN)
//#|重新建樹
void forceBuild();
//#|const|query|(Vector const& `v`,\size_t `i`,\bool `cmp`)|Vectors
//#|O(KN ^1-1/K^ )
//#|於set中找尋距離 `v` 前 `i` 近的向量, 並依照由近而遠的順序排序.
//# 如果有兩個向量 `v1`,`v2` 距離一樣, 且 `cmp` 為 `true` , 則直接依照
//# `v1 < v2` 來決定誰在前面. 最後回傳一陣列包含所有解.
Vectors query(Vector const& __vector,
size_t __nearestNumber,
bool __compareWholeVector) const;
//#||clear|()|void|O(1)
//#|清空所有資料
void clear();
//#||reset|(size_t `dimension`)|void|O(1)
//#|清空所有資料並且指定維度為 `dimension`
void reset(size_t __dimension);
//#|=====================================================================
};
//#
//#[NOTE]
//#========================================
//# * 此資料結構只有在 N >> 2 ^K^ 時才比較有優勢,
//# 當 K 逐漸變大時, 所花時間會跟暴搜沒兩樣
//#========================================
//#
//# '''
}
#include "KD_Tree.hpp"
#endif // KD_Tree_H__
|
