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
|
#ifndef KD_Tree_H__
#define KD_Tree_H__
#include <list>
#include <vector>
#include <cstdlib>
namespace meow{
template<class Keys, class Key, class Value>
class KD_Tree{
private:
struct Node{
Keys key;
Value value;
ssize_t lChild;
ssize_t rChild;
Node(Keys _key, Value _value, ssize_t _l_child, ssize_t _r_child);
};
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;
};
typedef std::vector<Value> Values;
struct Answer{
Node const& node;
Key dist2;
Answer(Node const& _node, Key _dist2);
bool operator<(Answer const& b) const;
};
typedef typename std::list<Answer> AnswerList;
typedef typename AnswerList::iterator AnswerListIterator;
//
const ssize_t NIL;
//
Nodes nodes;
size_t root;
bool needRebuild;
size_t dimension;
//
Key distance2(Keys const& k1, Keys const& k2) const;
size_t query(Keys const& key,
size_t k,
size_t index,
int depth,
std::vector<Key>& dist2_v,
Key dist2_s,
AnswerList* ret) const;
ssize_t build(ssize_t beg,
ssize_t end,
std::vector<size_t>* orders,
int depth);
public:
KD_Tree();
KD_Tree(size_t _dimension);
~KD_Tree();
//
void insert(Keys const& key, Value value);
void build();
//
Value query (Keys const& point, int k) const;
Values rangeQuery(Keys const& point, int k) const;
//
void clear();
void reset(size_t _dimension);
};
/*********************************************************
@asciidoc
=== meow:: *KD_Tree<Keys, Key, Value>* (C++ class)
.Description
`KD_Tree` is *K-dimension tree*, which is a dictionary(key->value).
Where the type if key is a *K-dimension vector* .
.Template Request
* `Keys` should has `operator[]` to allow the KD_Tree access the k-dimensions
* `Key` should has `operator*`, `operator+`
.Support Methods
* N <- numbers of element in the kd-tree
* K <- dimensions
* `Keys` is the tyepname of the vector
* `Key` is the typename of the element in the vector
* `Value` is the typename of value
[options="header",width="100%",cols="1>,1<s,5<,1<,2<,10<",grid="rows"]
|=======================================================================
|Const?|Name| Parameters| Return Type| Time Complexity| Description
|const|root|(size_t number)|size_t|very fast|
||insert|(Key const& k, Value v)|void|O(1)|Insert a pair (k->v)
|| build|()|void|O(KN logN) | Build the data structure(the `insert()`
method will not build the data structure immediately)
|const|query|(Keys const& point, int k)|Value|O(kN ^1-1/k^ ) |
Using Euclidean-Distance to find the k-nearest neighbor from `point` .
And return the corrosponding value
|const|query|(Keys const& point, int k)|std::vector<Value>|O(kN ^1-1/k^ ) |
Using Euclidean-Distance to find all the x-nearest neighbor from `point` ,
where x <= k. And return an array of all the corrosponding value.
||clear|()|O(1)|Clear all data
||reset|(size_t dimension)|O(1)|Clear all data and then
set the this->dimension be `dimension`
|=======================================================================
NOTE: O(kN ^1-1/k^ ) is reference from wiki. +
`query()` and `rangeQuery()` will run `build()` first if you called `insert()`
before call them. And `build()` is very slow, so you should not use this class
as a dynamic tree
'''
@asciidoc-
*********************************************************/
}
#include "KD_Tree.hpp"
#endif // KD_Tree_H__
|
