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
|
#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);
};
}
#include "KD_Tree.hpp"
#endif // KD_Tree_H__
|
