4 #include <shogun/lib/config.h> 123 for (
int i = 0; i < v.index; i++)
124 if ( max < v[i].dist.last())
125 max = v[i].dist.last();
131 for (
int i = 0; i < s; i++)
156 unsigned int new_index = 0;
158 for (
int i = 0; i < point_set.index; i++)
160 if (point_set[i].dist.last() <= fmax)
162 point_set[new_index++] = point_set[i];
165 push(far_set,point_set[i]);
167 point_set.index=new_index;
176 unsigned int new_index = 0;
178 for(
int i = 0; i < point_set.index; i++)
181 new_d =
distance(new_point, point_set[i].p, fmax);
184 push(point_set[i].dist, new_d);
185 push(new_point_set,point_set[i]);
188 point_set[new_index++] = point_set[i];
190 point_set.index = new_index;
209 if (point_set.index == 0)
212 float max_dist =
max_set(point_set);
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);
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 float new_dist = point_set.last().dist.last();
254 push(consumed_set, point_set.last());
257 dist_split(point_set, new_point_set, new_point, max_scale);
258 dist_split(far,new_point_set,new_point,max_scale);
261 batch_insert(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;
301 assert(points.
index > 0);
305 for (
int i = 1; i < points.
index; i++) {
309 push(point_set,temp);
314 float max_dist =
max_set(point_set);
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;
409 if (cover_set.index <= 1)
411 register d_node<P> *base_ptr = cover_set.elements;
413 d_node<P> *hi = &base_ptr[cover_set.index - 1];
417 while (right_ptr > base_ptr)
419 d_node<P> *mid = base_ptr + ((hi - base_ptr) >> 1);
421 if (
compare ( mid, base_ptr) < 0.)
427 if (
compare ( mid, base_ptr) < 0.)
431 left_ptr = base_ptr + 1;
436 while (
compare (left_ptr, mid) < 0.)
439 while (
compare (mid, right_ptr) < 0.)
442 if (left_ptr < right_ptr)
447 else if (mid == right_ptr)
452 else if (left_ptr == right_ptr)
459 while (left_ptr <= right_ptr);
470 while (ret.
index < 101)
478 inline bool shell(
float parent_query_dist,
float child_parent_dist,
float upper_bound)
480 return parent_query_dist - child_parent_dist <= upper_bound;
485 void update_k(
float *k_upper_bound,
float upper_bound)
488 float *begin = k_upper_bound;
489 for (;end != begin; begin++)
491 if (upper_bound < *(begin+1))
494 *begin = upper_bound;
499 *begin = upper_bound;
503 return (
float *)malloc(
sizeof(
float) *
internal_k);
507 for(
float *end = begin+
internal_k;end != begin; begin++)
515 return (
float *)malloc(
sizeof(
float));
525 *upper_bound = new_dist;
541 new_zero_set.index = 0;
542 d_node<P> *end = zero_set.elements + zero_set.index;
543 for (
d_node<P> *ele = zero_set.elements; ele != end ; ele++)
545 float upper_dist = *new_upper_bound + query_chi->
max_dist;
548 float d =
distance(query_chi->
p, ele->n->p, upper_dist);
552 if (d < *new_upper_bound)
553 update(new_upper_bound, d);
555 push(new_zero_set,temp);
565 int current_scale,
int max_scale)
567 for (; current_scale <= max_scale; current_scale++)
569 d_node<P>* ele = cover_sets[current_scale].elements;
570 d_node<P>* end = cover_sets[current_scale].elements + cover_sets[current_scale].index;
571 for (; ele != end; ele++)
573 float upper_dist = *new_upper_bound + query_chi->
max_dist + ele->
n->max_dist;
576 float d =
distance(query_chi->
p, ele->
n->p, upper_dist);
580 if (d < *new_upper_bound)
581 update(new_upper_bound,d);
583 push(new_cover_sets[current_scale],temp);
605 int current_scale,
int max_scale)
608 for (; current_scale <= max_scale; current_scale++)
610 d_node<P> *ele = cover_sets[current_scale].elements;
611 d_node<P> *end = cover_sets[current_scale].elements + cover_sets[current_scale].index;
613 for (; ele != end; ele++)
619 d_node<P> *end = zero_set.elements + zero_set.index;
621 for (
d_node<P> *ele = zero_set.elements; ele != end ; ele++)
648 d_node<P> *end = cover_sets[current_scale].elements + cover_sets[current_scale].index;
649 for (
d_node<P> *parent = cover_sets[current_scale].elements; parent != end; parent++)
651 const node<P> *par = parent->n;
653 if (parent->dist <= upper_dist + par->
max_dist)
656 if (parent->dist <= upper_dist + chi->
max_dist)
660 if (max_scale < chi->
scale)
661 max_scale = chi->
scale;
665 else if (parent->dist <= upper_dist)
668 push(zero_set, temp);
672 for (chi++; chi != child_end; chi++)
677 float d =
distance(query->
p, chi->
p, upper_chi);
680 if (d < *upper_bound)
684 if (max_scale < chi->
scale)
685 max_scale = chi->
scale;
687 push(cover_sets[chi->scale],temp);
690 if (d <= upper_chi - chi->max_dist)
693 push(zero_set, temp);
712 brute_nearest(query_chi, zero_set, upper_bound, results, spare_zero_sets);
716 for (query_chi++;query_chi != child_end; query_chi++)
719 copy_zero_set(query_chi, new_upper_bound, zero_set, new_zero_set);
720 brute_nearest(query_chi, new_zero_set, new_upper_bound, results, spare_zero_sets);
722 free (new_upper_bound);
723 new_zero_set.
index = 0;
724 push(spare_zero_sets, new_zero_set);
729 push(temp, query->
p);
730 d_node<P> *end = zero_set.elements + zero_set.index;
731 for (
d_node<P> *ele = zero_set.elements; ele != end ; ele++)
732 if (ele->dist <= *upper_bound)
733 push(temp, ele->n->p);
749 if (current_scale > max_scale)
750 brute_nearest(query, zero_set, upper_bound, results, spare_zero_sets);
752 if (query->
scale <= current_scale && query->
scale != 100)
761 for (query_chi++; query_chi != child_end; query_chi++)
764 copy_zero_set(query_chi, new_upper_bound, zero_set, new_zero_set);
765 copy_cover_sets(query_chi, new_upper_bound, cover_sets, new_cover_sets,
766 current_scale, max_scale);
768 current_scale, max_scale, new_upper_bound,
769 results, spare_cover_sets, spare_zero_sets);
771 free (new_upper_bound);
772 new_zero_set.
index = 0;
773 push(spare_zero_sets, new_zero_set);
774 push(spare_cover_sets, new_cover_sets);
776 current_scale, max_scale, upper_bound, results,
777 spare_cover_sets, spare_zero_sets);
781 halfsort(cover_sets[current_scale]);
782 descend(query, upper_bound, current_scale, max_scale,cover_sets, zero_set);
783 cover_sets[current_scale++].index = 0;
785 current_scale, max_scale, upper_bound, results,
786 spare_cover_sets, spare_zero_sets);
801 setter(upper_bound,FLT_MAX);
803 float top_dist =
distance(query.
p, top_node.
p, FLT_MAX);
804 update(upper_bound, top_dist);
807 push(cover_sets[0], temp);
810 spare_cover_sets,spare_zero_sets);
813 push(spare_cover_sets, cover_sets);
815 for (
int i = 0; i < spare_cover_sets.
index; i++)
818 for (
int j = 0; j < cover_sets2.
index; j++)
819 free (cover_sets2[j].elements);
824 push(spare_zero_sets, zero_set);
826 for (
int i = 0; i < spare_zero_sets.
index; i++)
827 free(spare_zero_sets[i].elements);
float distance(CJLCoverTreePoint p1, CJLCoverTreePoint p2, float64_t upper_bound)
float compare(const d_node< P > *p1, const d_node< P > *p2)
void brute_nearest(const node< P > *query, v_array< d_node< P > > zero_set, float *upper_bound, v_array< v_array< P > > &results, v_array< v_array< d_node< P > > > &spare_zero_sets)
static float64_t ceil(float64_t d)
node< P > new_node(const P &p)
void unequal_nearest_neighbor(const node< P > &top_node, const node< P > &query, v_array< v_array< P > > &results)
void update_k(float *k_upper_bound, float upper_bound)
node< P > batch_create(v_array< P > points)
void scale(SGVector< T > &a, SGVector< T > &result, T alpha=1)
void internal_batch_nearest_neighbor(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, float *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)
void breadth_dist(const node< P > top_node, v_array< int > &breadths)
void split(v_array< ds_node< P > > &point_set, v_array< ds_node< P > > &far_set, int max_scale)
void copy_zero_set(node< P > *query_chi, float *new_upper_bound, v_array< d_node< P > > &zero_set, v_array< d_node< P > > &new_zero_set)
void update_unequal(float *upper_bound, float new_dist)
v_array< T > pop(v_array< v_array< T > > &stack)
bool shell(float parent_query_dist, float child_parent_dist, float upper_bound)
void add_height(int d, v_array< int > &heights)
void print_query(const node< P > *top_node)
float *(* alloc_unequal)()
void push(v_array< T > &v, const T &new_ele)
void(* setter)(float *foo, float bar)
void halfsort(v_array< d_node< P > > cover_set)
unsigned short int num_children
void print(CJLCoverTreePoint &p)
void descend(const node< P > *query, float *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 depth_dist(int top_scale, const node< P > top_node, v_array< int > &depths)
void alloc(v_array< T > &v, int length)
void batch_nearest_neighbor(const node< P > &top_node, const node< P > &query, v_array< v_array< P > > &results)
void epsilon_nearest_neighbor(const node< P > &top_node, const node< P > &query, v_array< v_array< P > > &results, float epsilon)
float dist_of_scale(int s)
void set_k(float *begin, float max)
all of classes and functions are contained in the shogun namespace
v_array< v_array< d_node< P > > > get_cover_sets(v_array< v_array< v_array< d_node< P > > > > &spare_cover_sets)
void(* update)(float *foo, float bar)
void copy_cover_sets(node< P > *query_chi, float *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)
float max_set(v_array< ds_node< P > > &v)
static void swap(T &a, T &b)
node< P > batch_insert(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)
node< P > new_leaf(const P &p)
void k_nearest_neighbor(const node< P > &top_node, const node< P > &query, v_array< v_array< P > > &results, int k)
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)
void set_epsilon(float *begin, float max)
void set_unequal(float *begin, float max)
int height_dist(const node< P > top_node, v_array< int > &heights)
T max(const Container< T > &a)
void update_epsilon(float *upper_bound, float new_dist)
static int32_t pow(bool x, int32_t n)
void dist_split(v_array< ds_node< P > > &point_set, v_array< ds_node< P > > &new_point_set, P new_point, int max_scale)