6 #ifndef TAPKEE_NEIGHBORS_H_
7 #define TAPKEE_NEIGHBORS_H_
11 #ifdef TAPKEE_USE_LGPL_COVERTREE
24 namespace tapkee_internal
27 template <
class DistanceRecord>
30 inline bool operator()(
const DistanceRecord& l,
const DistanceRecord& r)
const
32 return (l.second < r.second);
40 template <
class RandomAccessIterator,
class Callback>
60 template <
class RandomAccessIterator,
class Callback>
76 #ifdef TAPKEE_USE_LGPL_COVERTREE
77 template <
class RandomAccessIterator,
class Callback>
85 for (RandomAccessIterator iter=begin; iter!=end; ++iter)
86 push(points, TreePoint(iter, callback(iter,iter)));
95 neighbors.resize(end-begin);
96 assert(end-begin==res.
index);
97 for (
int i=0; i<res.
index; ++i)
100 local_neighbors.reserve(k);
105 if (res[i][j].iter_-begin==res[i][0].iter_-begin)
107 local_neighbors.push_back(res[i][j].iter_-begin);
109 neighbors[res[i][0].iter_-begin] = local_neighbors;
110 free(res[i].elements);
119 template <
class RandomAccessIterator,
class Callback>
123 timed_context context(
"Distance sorting based neighbors search");
124 typedef std::pair<RandomAccessIterator, ScalarType> DistanceRecord;
125 typedef std::vector<DistanceRecord> Distances;
128 neighbors.reserve(end-begin);
129 for (RandomAccessIterator iter=begin; iter!=end; ++iter)
132 for (RandomAccessIterator around_iter=begin; around_iter!=end; ++around_iter)
133 distances.push_back(std::make_pair(around_iter, callback.distance(iter,around_iter)));
135 std::nth_element(distances.begin(),distances.begin()+k+1,distances.end(),
139 local_neighbors.reserve(k);
140 for (
typename Distances::const_iterator neighbors_iter=distances.begin();
141 neighbors_iter!=distances.begin()+k+1; ++neighbors_iter)
143 if (neighbors_iter->first != iter)
144 local_neighbors.push_back(neighbors_iter->first - begin);
146 neighbors.push_back(local_neighbors);
151 template <
class RandomAccessIterator,
class Callback>
158 neighbors.reserve(end-begin);
162 for (RandomAccessIterator i=begin; i!=end; ++i)
165 std::remove(local_neighbors.begin(),local_neighbors.end(),i-begin);
166 neighbors.push_back(local_neighbors);
172 template <
class RandomAccessIterator,
class Callback>
174 const RandomAccessIterator& end,
const Callback& callback,
177 if (k > static_cast<IndexType>(end-begin-1))
180 "Using greatest possible number of neighbors.");
189 #ifdef TAPKEE_USE_LGPL_COVERTREE
195 if (check_connectivity)