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>
46 return callback.kernel(*l,*r);
50 return sqrt(callback.kernel(*l,*l) - 2*callback.kernel(*l,*r) + callback.kernel(*r,*r));
60 template <
class RandomAccessIterator,
class Callback>
66 return callback.distance(*l,*r);
70 return callback.distance(*l,*r);
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)
ScalarType distance(const RandomAccessIterator &l, const RandomAccessIterator &r)
bool operator()(const DistanceRecord &l, const DistanceRecord &r) const
Neighbors find_neighbors(NeighborsMethod method, const RandomAccessIterator &begin, const RandomAccessIterator &end, const Callback &callback, IndexType k, bool check_connectivity)
void k_nearest_neighbor(DistanceCallback &dcb, const node< P > &top_node, const node< P > &query, v_array< v_array< P > > &results, int k)
ScalarType operator()(const RandomAccessIterator &l, const RandomAccessIterator &r)
node< P > batch_create(DistanceCallback &dcb, v_array< P > points)
ScalarType distance(const RandomAccessIterator &l, const RandomAccessIterator &r)
Class v_array taken directly from JL's implementation.
Neighbors find_neighbors_covertree_impl(RandomAccessIterator begin, RandomAccessIterator end, Callback callback, IndexType k)
double ScalarType
default scalar value (can be overrided with TAPKEE_CUSTOM_INTERNAL_NUMTYPE define) ...
std::string get_neighbors_method_name(NeighborsMethod m)
void free_children(const node< P > &n)
TAPKEE_INTERNAL_VECTOR< tapkee::IndexType > LocalNeighbors
int IndexType
indexing type (non-overridable) set to int for compatibility with OpenMP 2.0
ScalarType operator()(const RandomAccessIterator &l, const RandomAccessIterator &r)
void push(v_array< T > &v, const T &new_ele)
PlainDistance(const Callback &cb)
void message_info(const std::string &msg)
Covertree-based method with approximate time complexity. Recommended to be used as a default method...
TAPKEE_INTERNAL_VECTOR< tapkee::tapkee_internal::LocalNeighbors > Neighbors
Neighbors find_neighbors_vptree_impl(const RandomAccessIterator &begin, const RandomAccessIterator &end, Callback callback, IndexType k)
bool is_connected(RandomAccessIterator begin, RandomAccessIterator end, const Neighbors &neighbors)
void message_warning(const std::string &msg)
static LoggingSingleton & instance()
std::vector< IndexType > search(const RandomAccessIterator &target, int k)
Class Point to use with John Langford's CoverTree. This class must have some associated functions def...
Brute force method with not least than time complexity. Recommended to be used only in debug purpose...
NeighborsMethod
Neighbors computation methods.
KernelDistance(const Callback &cb)
Neighbors find_neighbors_bruteforce_impl(const RandomAccessIterator &begin, const RandomAccessIterator &end, Callback callback, IndexType k)