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
|
#ifndef HERA_BT_DNN_LOCAL_KD_TREE_H
#define HERA_BT_DNN_LOCAL_KD_TREE_H
#include "../utils.h"
#include "search-functors.h"
#include <unordered_map>
#include <stack>
#include <boost/tuple/tuple.hpp>
#include <boost/shared_ptr.hpp>
#include <boost/range/value_type.hpp>
#include <boost/static_assert.hpp>
#include <boost/type_traits.hpp>
namespace hera {
namespace bt {
namespace dnn
{
// Weighted KDTree
// Traits_ provides Coordinate, DistanceType, PointType, dimension(), distance(p1,p2), coordinate(p,i)
template< class Traits_ >
class KDTree
{
public:
typedef Traits_ Traits;
typedef hera::bt::dnn::HandleDistance<KDTree> HandleDistance;
typedef typename Traits::PointType Point;
typedef typename Traits::PointHandle PointHandle;
typedef typename Traits::Coordinate Coordinate;
typedef typename Traits::DistanceType DistanceType;
typedef std::vector<PointHandle> HandleContainer;
typedef std::vector<HandleDistance> HDContainer; // TODO: use tbb::scalable_allocator
typedef HDContainer Result;
typedef std::vector<DistanceType> DistanceContainer;
typedef std::unordered_map<PointHandle, size_t> HandleMap;
//private:
typedef typename HandleContainer::iterator HCIterator;
typedef std::tuple<HCIterator, HCIterator, size_t, ssize_t> KDTreeNode;
typedef std::tuple<HCIterator, HCIterator> KDTreeNodeNoCut;
//BOOST_STATIC_ASSERT_MSG(has_coordinates<Traits, PointHandle, int>::value, "KDTree requires coordinates");
public:
KDTree(const Traits& traits):
traits_(traits) {}
KDTree(const Traits& traits, HandleContainer&& handles);
template<class Range>
KDTree(const Traits& traits, const Range& range);
template<class Range>
void init(const Range& range);
HandleDistance find(PointHandle q) const;
Result findR(PointHandle q, DistanceType r) const; // all neighbors within r
Result findFirstR(PointHandle q, DistanceType r) const; // first neighbor within r
Result findK(PointHandle q, size_t k) const; // k nearest neighbors
HandleDistance find(const Point& q) const { return find(traits().handle(q)); }
Result findR(const Point& q, DistanceType r) const { return findR(traits().handle(q), r); }
Result findFirstR(const Point& q, DistanceType r) const { return findFirstR(traits().handle(q), r); }
Result findK(const Point& q, size_t k) const { return findK(traits().handle(q), k); }
template<class ResultsFunctor>
void search(PointHandle q, ResultsFunctor& rf) const;
const Traits& traits() const { return traits_; }
void get_path_to_root(const size_t idx, std::stack<KDTreeNodeNoCut>& s);
// to support deletion
void init_n_elems();
void delete_point(const size_t idx);
void delete_point(PointHandle p);
void update_n_elems(const ssize_t idx, const int delta);
void increase_n_elems(const ssize_t idx);
void decrease_n_elems(const ssize_t idx);
size_t get_num_points() const { return num_points_; }
//private:
void init();
struct CoordinateComparison;
struct OrderTree;
//private:
Traits traits_;
HandleContainer tree_;
std::vector<char> delete_flags_;
std::vector<int> subtree_n_elems;
HandleMap indices_;
std::vector<ssize_t> parents_;
size_t num_points_;
};
} // dnn
} // bt
} // hera
#include "kd-tree.hpp"
#endif
|
