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)
ScalarType distance(const RandomAccessIterator &l, const RandomAccessIterator &r)
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)
bool operator()(const DistanceRecord &l, const DistanceRecord &r) const
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)