28 namespace tapkee_internal
43 unsigned short int _num_children,
short int _scale) :
p(_p),
105 return (
int)ceil(
il2 * log(d));
127 for (
int i = 0; i < v.index; i++)
128 if ( max < v[i].dist.last())
129 max = v[i].dist.last();
135 for (
int i = 0; i < s; i++)
147 printf(
"scale = %i\n",top_node.
scale);
149 printf(
"max_dist = %f\n",top_node.
max_dist);
162 for (
int i = 0; i < point_set.index; i++)
164 if (point_set[i].dist.last() <= fmax)
166 point_set[new_index++] = point_set[i];
169 push(far_set,point_set[i]);
171 point_set.index=new_index;
174 template<
class P,
class DistanceCallback>
182 for(
int i = 0; i < point_set.index; i++)
185 new_d =
distance(dcb, new_point, point_set[i].p, fmax);
188 push(point_set[i].dist, new_d);
189 push(new_point_set,point_set[i]);
192 point_set[new_index++] = point_set[i];
194 point_set.index = new_index;
201 template <
class P,
class DistanceCallback>
209 if (point_set.index == 0)
213 int next_scale = std::min(max_scale - 1,
get_scale(max_dist));
214 if (next_scale == -2147483647-1)
218 while (point_set.index > 0)
221 push(consumed_set,point_set.last());
235 split(point_set,far,max_scale);
237 node<P> child =
batch_insert(dcb, p, next_scale, top_scale, point_set, consumed_set, stack);
239 if (point_set.index == 0)
241 push(stack,point_set);
248 push(children, child);
251 while (point_set.index != 0) {
252 P new_point = point_set.last().p;
253 ScalarType new_dist = point_set.last().dist.last();
254 push(consumed_set, point_set.last());
257 dist_split(dcb,point_set,new_point_set,new_point,max_scale);
258 dist_split(dcb,far,new_point_set,new_point,max_scale);
261 batch_insert(dcb, new_point, next_scale, top_scale, new_point_set, new_consumed_set, stack);
264 push(children, new_child);
267 for(
int i = 0; i< new_point_set.
index; i++)
269 new_point_set[i].dist.
decr();
270 if (new_point_set[i].dist.
last() <= fmax)
271 push(point_set, new_point_set[i]);
273 push(far, new_point_set[i]);
275 for(
int i = 0; i< new_consumed_set.
index; i++)
277 new_consumed_set[i].dist.
decr();
278 push(consumed_set, new_consumed_set[i]);
280 new_point_set.
index = 0;
281 new_consumed_set.
index = 0;
283 push(stack,new_point_set);
284 push(stack,new_consumed_set);
285 push(stack,point_set);
287 n.
scale = top_scale - max_scale;
298 template<
class P,
class DistanceCallback>
301 assert(points.
index > 0);
305 for (
int i = 1; i < points.
index; i++) {
307 push(temp.
dist,
distance(dcb, points[0], points[i], std::numeric_limits<ScalarType>::max()));
309 push(point_set,temp);
322 for (
int i = 0; i<consumed_set.
index;i++)
323 free(consumed_set[i].dist.
elements);
325 for (
int i = 0; i<stack.
index;i++)
326 free(stack[i].elements);
334 if (heights.
index <= d)
335 for(;heights.
index <= d;)
337 heights[d] = heights[d] + 1;
402 return p1 -> dist - p2 -> dist;
408 if (cover_set.index <= 1)
410 register d_node<P> *base_ptr = cover_set.elements;
412 d_node<P> *hi = &base_ptr[cover_set.index - 1];
416 while (right_ptr > base_ptr)
418 d_node<P> *mid = base_ptr + ((hi - base_ptr) >> 1);
420 if (
compare ( mid, base_ptr) < 0.)
421 std::swap(*mid, *base_ptr);
423 std::swap(*mid, *hi);
426 if (
compare ( mid, base_ptr) < 0.)
427 std::swap(*mid, *base_ptr);
430 left_ptr = base_ptr + 1;
435 while (
compare (left_ptr, mid) < 0.)
438 while (
compare (mid, right_ptr) < 0.)
441 if (left_ptr < right_ptr)
443 std::swap(*left_ptr, *right_ptr);
446 else if (mid == right_ptr)
451 else if (left_ptr == right_ptr)
458 while (left_ptr <= right_ptr);
467 while (ret.
index < 101)
477 return parent_query_dist - child_parent_dist <= upper_bound;
486 for (;end != begin; begin++)
488 if (upper_bound < *(begin+1))
491 *begin = upper_bound;
496 *begin = upper_bound;
522 *upper_bound = new_dist;
534 template <
class P,
class DistanceCallback>
539 new_zero_set.index = 0;
540 d_node<P> *end = zero_set.elements + zero_set.index;
541 for (
d_node<P> *ele = zero_set.elements; ele != end ; ele++)
550 if (d < *new_upper_bound)
551 update(new_upper_bound, d);
553 push(new_zero_set,temp);
559 template <
class P,
class DistanceCallback>
564 int current_scale,
int max_scale)
566 for (; current_scale <= max_scale; current_scale++)
568 d_node<P>* ele = cover_sets[current_scale].elements;
569 d_node<P>* end = cover_sets[current_scale].elements + cover_sets[current_scale].index;
570 for (; ele != end; ele++)
579 if (d < *new_upper_bound)
580 update(new_upper_bound,d);
582 push(new_cover_sets[current_scale],temp);
592 printf(
"query = \n");
595 printf(
"scale = %i\n",top_node->
scale);
596 printf(
"max_dist = %f\n",top_node->
max_dist);
604 int current_scale,
int max_scale)
606 printf(
"cover set = \n");
607 for (; current_scale <= max_scale; current_scale++)
609 d_node<P> *ele = cover_sets[current_scale].elements;
610 d_node<P> *end = cover_sets[current_scale].elements + cover_sets[current_scale].index;
611 printf(
"%i\n", current_scale);
612 for (; ele != end; ele++)
618 d_node<P> *end = zero_set.elements + zero_set.index;
619 printf(
"infinity\n");
620 for (
d_node<P> *ele = zero_set.elements; ele != end ; ele++)
638 template <
class P,
class DistanceCallback>
644 d_node<P> *end = cover_sets[current_scale].elements + cover_sets[current_scale].index;
645 for (
d_node<P> *parent = cover_sets[current_scale].elements; parent != end; parent++)
647 const node<P> *par = parent->n;
649 if (parent->dist <= upper_dist + par->
max_dist)
652 if (parent->dist <= upper_dist + chi->
max_dist)
656 if (max_scale < chi->scale)
657 max_scale = chi->
scale;
661 else if (parent->dist <= upper_dist)
664 push(zero_set, temp);
668 for (chi++; chi != child_end; chi++)
676 if (d < *upper_bound)
680 if (max_scale < chi->scale)
681 max_scale = chi->
scale;
686 if (d <= upper_chi - chi->max_dist)
689 push(zero_set, temp);
698 template <
class P,
class DistanceCallback>
708 brute_nearest(dcb, query_chi, zero_set, upper_bound, results, spare_zero_sets);
712 for (query_chi++;query_chi != child_end; query_chi++)
715 copy_zero_set(dcb, query_chi, new_upper_bound, zero_set, new_zero_set);
716 brute_nearest(dcb, query_chi, new_zero_set, new_upper_bound, results, spare_zero_sets);
718 free (new_upper_bound);
719 new_zero_set.
index = 0;
720 push(spare_zero_sets, new_zero_set);
725 push(temp, query->
p);
726 d_node<P> *end = zero_set.elements + zero_set.index;
727 for (
d_node<P> *ele = zero_set.elements; ele != end ; ele++)
728 if (ele->dist <= *upper_bound)
729 push(temp, ele->n->p);
734 template <
class P,
class DistanceCallback>
745 if (current_scale > max_scale)
746 brute_nearest(dcb, query, zero_set, upper_bound, results, spare_zero_sets);
748 if (query->
scale <= current_scale && query->
scale != 100)
757 for (query_chi++; query_chi != child_end; query_chi++)
760 copy_zero_set(dcb, query_chi, new_upper_bound, zero_set, new_zero_set);
761 copy_cover_sets(dcb, query_chi, new_upper_bound, cover_sets, new_cover_sets,
762 current_scale, max_scale);
764 current_scale, max_scale, new_upper_bound,
765 results, spare_cover_sets, spare_zero_sets);
767 free (new_upper_bound);
768 new_zero_set.
index = 0;
769 push(spare_zero_sets, new_zero_set);
770 push(spare_cover_sets, new_cover_sets);
772 current_scale, max_scale, upper_bound, results,
773 spare_cover_sets, spare_zero_sets);
777 halfsort(cover_sets[current_scale]);
778 descend(dcb, query, upper_bound, current_scale, max_scale,cover_sets, zero_set);
779 cover_sets[current_scale++].index = 0;
781 current_scale, max_scale, upper_bound, results,
782 spare_cover_sets, spare_zero_sets);
786 template <
class P,
class DistanceCallback>
797 setter(upper_bound, std::numeric_limits<ScalarType>::max());
799 ScalarType top_dist =
distance(dcb, query.
p, top_node.
p, std::numeric_limits<ScalarType>::max());
800 update(upper_bound, top_dist);
803 push(cover_sets[0], temp);
806 spare_cover_sets,spare_zero_sets);
809 push(spare_cover_sets, cover_sets);
811 for (
int i = 0; i < spare_cover_sets.
index; i++)
814 for (
int j = 0; j < cover_sets2.
index; j++)
815 free (cover_sets2[j].elements);
820 push(spare_zero_sets, zero_set);
822 for (
int i = 0; i < spare_zero_sets.
index; i++)
823 free(spare_zero_sets[i].elements);
827 template <
class P,
class DistanceCallback>
ScalarType dist_of_scale(int s)
ScalarType distance(Callback &cb, const CoverTreePoint< RandomAccessIterator > &l, const CoverTreePoint< RandomAccessIterator > &r, ScalarType upper_bound)
void k_nearest_neighbor(DistanceCallback &dcb, const node< P > &top_node, const node< P > &query, v_array< v_array< P > > &results, int k)
void copy_cover_sets(DistanceCallback &dcb, node< P > *query_chi, ScalarType *new_upper_bound, v_array< v_array< d_node< P > > > &cover_sets, v_array< v_array< d_node< P > > > &new_cover_sets, int current_scale, int max_scale)
void depth_dist(int top_scale, const node< P > top_node, v_array< int > &depths)
bool shell(ScalarType parent_query_dist, ScalarType child_parent_dist, ScalarType upper_bound)
void add_height(int d, v_array< int > &heights)
node< P > batch_create(DistanceCallback &dcb, v_array< P > points)
ScalarType max_set(v_array< ds_node< P > > &v)
void update_k(ScalarType *k_upper_bound, ScalarType upper_bound)
void dist_split(DistanceCallback &dcb, v_array< ds_node< P > > &point_set, v_array< ds_node< P > > &new_point_set, P new_point, int max_scale)
void set_unequal(ScalarType *begin, ScalarType max)
double ScalarType
default scalar value (can be overrided with TAPKEE_CUSTOM_INTERNAL_NUMTYPE define) ...
v_array< v_array< d_node< P > > > get_cover_sets(v_array< v_array< v_array< d_node< P > > > > &spare_cover_sets)
void descend(DistanceCallback &dcb, const node< P > *query, ScalarType *upper_bound, int current_scale, int &max_scale, v_array< v_array< d_node< P > > > &cover_sets, v_array< d_node< P > > &zero_set)
void alloc(v_array< T > &v, int length)
void split(v_array< ds_node< P > > &point_set, v_array< ds_node< P > > &far_set, int max_scale)
void free_children(const node< P > &n)
int height_dist(const node< P > top_node, v_array< int > &heights)
int IndexType
indexing type (non-overridable) set to int for compatibility with OpenMP 2.0
void print(int depth, node< P > &top_node)
node< P > new_node(const P &p)
node< P > new_leaf(const P &p)
void push(v_array< T > &v, const T &new_ele)
int get_scale(ScalarType d)
ScalarType internal_epsilon
void batch_nearest_neighbor(DistanceCallback &dcb, const node< P > &top_node, const node< P > &query, v_array< v_array< P > > &results)
void internal_batch_nearest_neighbor(DistanceCallback &dcb, const node< P > *query, v_array< v_array< d_node< P > > > &cover_sets, v_array< d_node< P > > &zero_set, int current_scale, int max_scale, ScalarType *upper_bound, v_array< v_array< P > > &results, v_array< v_array< v_array< d_node< P > > > > &spare_cover_sets, v_array< v_array< d_node< P > > > &spare_zero_sets)
v_array< ScalarType > dist
void print_query(const node< P > *top_node)
void(* setter)(ScalarType *foo, ScalarType bar)
void breadth_dist(const node< P > top_node, v_array< int > &breadths)
node< P > batch_insert(DistanceCallback &dcb, const P &p, int max_scale, int top_scale, v_array< ds_node< P > > &point_set, v_array< ds_node< P > > &consumed_set, v_array< v_array< ds_node< P > > > &stack)
void update_unequal(ScalarType *upper_bound, ScalarType new_dist)
ScalarType compare(const d_node< P > *p1, const d_node< P > *p2)
ScalarType * alloc_epsilon()
void set_epsilon(ScalarType *begin)
ScalarType *(* alloc_upper)()
void brute_nearest(DistanceCallback &dcb, const node< P > *query, v_array< d_node< P > > zero_set, ScalarType *upper_bound, v_array< v_array< P > > &results, v_array< v_array< d_node< P > > > &spare_zero_sets)
void copy_zero_set(DistanceCallback &dcb, node< P > *query_chi, ScalarType *new_upper_bound, v_array< d_node< P > > &zero_set, v_array< d_node< P > > &new_zero_set)
#define COVERTREE_BASE
Base of covertree. Could be overrided if TAPKEE_CUSTOM_PROPERTIES file is defined.
v_array< T > pop(v_array< v_array< T > > &stack)
unsigned short int num_children
void halfsort(v_array< d_node< P > > cover_set)
node(P _p, ScalarType _max_dist, ScalarType _parent_dist, node< P > *_children, unsigned short int _num_children, short int _scale)
void set_k(ScalarType *begin, ScalarType max)
void(* update)(ScalarType *foo, ScalarType bar)
void print_cover_sets(v_array< v_array< d_node< P > > > &cover_sets, v_array< d_node< P > > &zero_set, int current_scale, int max_scale)