119 for (
int i = 0; i < v.index; i++)
120 if ( max < v[i].dist.last())
121 max = v[i].dist.last();
127 for (
int i = 0; i < s; i++)
152 unsigned int new_index = 0;
154 for (
int i = 0; i < point_set.index; i++)
156 if (point_set[i].dist.last() <= fmax)
158 point_set[new_index++] = point_set[i];
161 push(far_set,point_set[i]);
163 point_set.index=new_index;
172 unsigned int new_index = 0;
174 for(
int i = 0; i < point_set.index; i++)
177 new_d =
distance(new_point, point_set[i].p, fmax);
180 push(point_set[i].dist, new_d);
181 push(new_point_set,point_set[i]);
184 point_set[new_index++] = point_set[i];
186 point_set.index = new_index;
205 if (point_set.index == 0)
208 float max_dist =
max_set(point_set);
210 if (next_scale == -2147483647-1)
214 while (point_set.index > 0)
217 push(consumed_set,point_set.last());
231 split(point_set,far,max_scale);
235 if (point_set.index == 0)
237 push(stack,point_set);
244 push(children, child);
247 while (point_set.index != 0) {
248 P new_point = point_set.last().p;
249 float new_dist = point_set.last().dist.last();
250 push(consumed_set, point_set.last());
253 dist_split(point_set, new_point_set, new_point, max_scale);
254 dist_split(far,new_point_set,new_point,max_scale);
257 batch_insert(new_point, next_scale, top_scale, new_point_set, new_consumed_set, stack);
260 push(children, new_child);
263 for(
int i = 0; i< new_point_set.
index; i++)
265 new_point_set[i].dist.
decr();
266 if (new_point_set[i].dist.
last() <= fmax)
267 push(point_set, new_point_set[i]);
269 push(far, new_point_set[i]);
271 for(
int i = 0; i< new_consumed_set.
index; i++)
273 new_consumed_set[i].dist.
decr();
274 push(consumed_set, new_consumed_set[i]);
276 new_point_set.
index = 0;
277 new_consumed_set.
index = 0;
279 push(stack,new_point_set);
280 push(stack,new_consumed_set);
281 push(stack,point_set);
283 n.
scale = top_scale - max_scale;
297 assert(points.
index > 0);
301 for (
int i = 1; i < points.
index; i++) {
305 push(point_set,temp);
310 float max_dist =
max_set(point_set);
318 for (
int i = 0; i<consumed_set.
index;i++)
319 free(consumed_set[i].dist.
elements);
321 for (
int i = 0; i<stack.
index;i++)
322 free(stack[i].elements);
330 if (heights.
index <= d)
331 for(;heights.
index <= d;)
333 heights[d] = heights[d] + 1;
398 return p1 -> dist - p2 -> dist;
405 if (cover_set.index <= 1)
407 register d_node<P> *base_ptr = cover_set.elements;
409 d_node<P> *hi = &base_ptr[cover_set.index - 1];
413 while (right_ptr > base_ptr)
415 d_node<P> *mid = base_ptr + ((hi - base_ptr) >> 1);
417 if (
compare ( mid, base_ptr) < 0.)
423 if (
compare ( mid, base_ptr) < 0.)
427 left_ptr = base_ptr + 1;
432 while (
compare (left_ptr, mid) < 0.)
435 while (
compare (mid, right_ptr) < 0.)
438 if (left_ptr < right_ptr)
443 else if (mid == right_ptr)
448 else if (left_ptr == right_ptr)
455 while (left_ptr <= right_ptr);
466 while (ret.
index < 101)
474 inline bool shell(
float parent_query_dist,
float child_parent_dist,
float upper_bound)
476 return parent_query_dist - child_parent_dist <= upper_bound;
481 void update_k(
float *k_upper_bound,
float upper_bound)
484 float *begin = k_upper_bound;
485 for (;end != begin; begin++)
487 if (upper_bound < *(begin+1))
490 *begin = upper_bound;
495 *begin = upper_bound;
499 return (
float *)malloc(
sizeof(
float) *
internal_k);
503 for(
float *end = begin+
internal_k;end != begin; begin++)
511 return (
float *)malloc(
sizeof(
float));
521 *upper_bound = new_dist;
537 new_zero_set.index = 0;
538 d_node<P> *end = zero_set.elements + zero_set.index;
539 for (
d_node<P> *ele = zero_set.elements; ele != end ; ele++)
541 float upper_dist = *new_upper_bound + query_chi->
max_dist;
544 float d =
distance(query_chi->
p, ele->n->p, upper_dist);
548 if (d < *new_upper_bound)
549 update(new_upper_bound, d);
551 push(new_zero_set,temp);
561 int current_scale,
int max_scale)
563 for (; current_scale <= max_scale; current_scale++)
565 d_node<P>* ele = cover_sets[current_scale].elements;
566 d_node<P>* end = cover_sets[current_scale].elements + cover_sets[current_scale].index;
567 for (; ele != end; ele++)
569 float upper_dist = *new_upper_bound + query_chi->
max_dist + ele->
n->max_dist;
572 float d =
distance(query_chi->
p, ele->
n->p, upper_dist);
576 if (d < *new_upper_bound)
577 update(new_upper_bound,d);
579 push(new_cover_sets[current_scale],temp);
601 int current_scale,
int max_scale)
604 for (; current_scale <= max_scale; current_scale++)
606 d_node<P> *ele = cover_sets[current_scale].elements;
607 d_node<P> *end = cover_sets[current_scale].elements + cover_sets[current_scale].index;
609 for (; ele != end; ele++)
615 d_node<P> *end = zero_set.elements + zero_set.index;
617 for (
d_node<P> *ele = zero_set.elements; ele != end ; ele++)
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++)
673 float d =
distance(query->
p, chi->
p, upper_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);
708 brute_nearest(query_chi, zero_set, upper_bound, results, spare_zero_sets);
712 for (query_chi++;query_chi != child_end; query_chi++)
715 copy_zero_set(query_chi, new_upper_bound, zero_set, new_zero_set);
716 brute_nearest(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);
745 if (current_scale > max_scale)
746 brute_nearest(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(query_chi, new_upper_bound, zero_set, new_zero_set);
761 copy_cover_sets(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(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);
797 setter(upper_bound,FLT_MAX);
799 float top_dist =
distance(query.
p, top_node.
p, FLT_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);
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(* update)(float *foo, float bar)
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)
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
float *(* alloc_unequal)()
v_array< v_array< d_node< P > > > get_cover_sets(v_array< v_array< v_array< d_node< P > > > > &spare_cover_sets)
void scale(Matrix A, Matrix B, typename Matrix::Scalar alpha)
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)
Matrix::Scalar max(Matrix m)
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)
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)