91 return CMath::pow(
base, s);
96 return (
int) CMath::ceil(
il2 * log(d));
118 for (
int i = 0; i < v.index; i++)
119 if ( max < v[i].dist.last())
120 max = v[i].dist.last();
126 for (
int i = 0; i < s; i++)
151 unsigned int new_index = 0;
153 for (
int i = 0; i < point_set.index; i++)
155 if (point_set[i].dist.last() <= fmax)
157 point_set[new_index++] = point_set[i];
160 push(far_set,point_set[i]);
162 point_set.index=new_index;
171 unsigned int new_index = 0;
173 for(
int i = 0; i < point_set.index; i++)
176 new_d =
distance(new_point, point_set[i].p, fmax);
179 push(point_set[i].dist, new_d);
180 push(new_point_set,point_set[i]);
183 point_set[new_index++] = point_set[i];
185 point_set.index = new_index;
204 if (point_set.index == 0)
207 float max_dist =
max_set(point_set);
208 int next_scale = CMath::min(max_scale - 1,
get_scale(max_dist));
209 if (next_scale == -2147483647-1)
213 while (point_set.index > 0)
216 push(consumed_set,point_set.last());
230 split(point_set,far,max_scale);
234 if (point_set.index == 0)
236 push(stack,point_set);
243 push(children, child);
246 while (point_set.index != 0) {
247 P new_point = point_set.last().p;
248 float new_dist = point_set.last().dist.last();
249 push(consumed_set, point_set.last());
252 dist_split(point_set, new_point_set, new_point, max_scale);
253 dist_split(far,new_point_set,new_point,max_scale);
256 batch_insert(new_point, next_scale, top_scale, new_point_set, new_consumed_set, stack);
259 push(children, new_child);
262 for(
int i = 0; i< new_point_set.
index; i++)
264 new_point_set[i].dist.
decr();
265 if (new_point_set[i].dist.
last() <= fmax)
266 push(point_set, new_point_set[i]);
268 push(far, new_point_set[i]);
270 for(
int i = 0; i< new_consumed_set.
index; i++)
272 new_consumed_set[i].dist.
decr();
273 push(consumed_set, new_consumed_set[i]);
275 new_point_set.
index = 0;
276 new_consumed_set.
index = 0;
278 push(stack,new_point_set);
279 push(stack,new_consumed_set);
280 push(stack,point_set);
282 n.
scale = top_scale - max_scale;
296 assert(points.
index > 0);
300 for (
int i = 1; i < points.
index; i++) {
304 push(point_set,temp);
309 float max_dist =
max_set(point_set);
317 for (
int i = 0; i<consumed_set.
index;i++)
318 free(consumed_set[i].dist.
elements);
320 for (
int i = 0; i<stack.
index;i++)
321 free(stack[i].elements);
329 if (heights.
index <= d)
330 for(;heights.
index <= d;)
332 heights[d] = heights[d] + 1;
397 return p1 -> dist - p2 -> dist;
404 if (cover_set.index <= 1)
406 register d_node<P> *base_ptr = cover_set.elements;
408 d_node<P> *hi = &base_ptr[cover_set.index - 1];
412 while (right_ptr > base_ptr)
414 d_node<P> *mid = base_ptr + ((hi - base_ptr) >> 1);
416 if (
compare ( mid, base_ptr) < 0.)
417 CMath::swap(*mid, *base_ptr);
419 CMath::swap(*mid, *hi);
422 if (
compare ( mid, base_ptr) < 0.)
423 CMath::swap(*mid, *base_ptr);
426 left_ptr = base_ptr + 1;
431 while (
compare (left_ptr, mid) < 0.)
434 while (
compare (mid, right_ptr) < 0.)
437 if (left_ptr < right_ptr)
439 CMath::swap(*left_ptr, *right_ptr);
442 else if (mid == right_ptr)
447 else if (left_ptr == right_ptr)
454 while (left_ptr <= right_ptr);
465 while (ret.
index < 101)
473 inline bool shell(
float parent_query_dist,
float child_parent_dist,
float upper_bound)
475 return parent_query_dist - child_parent_dist <= upper_bound;
480 void update_k(
float *k_upper_bound,
float upper_bound)
483 float *begin = k_upper_bound;
484 for (;end != begin; begin++)
486 if (upper_bound < *(begin+1))
489 *begin = upper_bound;
494 *begin = upper_bound;
498 return (
float *)malloc(
sizeof(
float) *
internal_k);
502 for(
float *end = begin+
internal_k;end != begin; begin++)
510 return (
float *)malloc(
sizeof(
float));
520 *upper_bound = new_dist;
536 new_zero_set.index = 0;
537 d_node<P> *end = zero_set.elements + zero_set.index;
538 for (
d_node<P> *ele = zero_set.elements; ele != end ; ele++)
540 float upper_dist = *new_upper_bound + query_chi->
max_dist;
543 float d =
distance(query_chi->
p, ele->n->p, upper_dist);
547 if (d < *new_upper_bound)
548 update(new_upper_bound, d);
550 push(new_zero_set,temp);
560 int current_scale,
int max_scale)
562 for (; current_scale <= max_scale; current_scale++)
564 d_node<P>* ele = cover_sets[current_scale].elements;
565 d_node<P>* end = cover_sets[current_scale].elements + cover_sets[current_scale].index;
566 for (; ele != end; ele++)
568 float upper_dist = *new_upper_bound + query_chi->
max_dist + ele->
n->max_dist;
571 float d =
distance(query_chi->
p, ele->
n->p, upper_dist);
575 if (d < *new_upper_bound)
576 update(new_upper_bound,d);
578 push(new_cover_sets[current_scale],temp);
600 int current_scale,
int max_scale)
603 for (; current_scale <= max_scale; current_scale++)
605 d_node<P> *ele = cover_sets[current_scale].elements;
606 d_node<P> *end = cover_sets[current_scale].elements + cover_sets[current_scale].index;
608 for (; ele != end; ele++)
614 d_node<P> *end = zero_set.elements + zero_set.index;
616 for (
d_node<P> *ele = zero_set.elements; ele != end ; ele++)
643 d_node<P> *end = cover_sets[current_scale].elements + cover_sets[current_scale].index;
644 for (
d_node<P> *parent = cover_sets[current_scale].elements; parent != end; parent++)
646 const node<P> *par = parent->n;
648 if (parent->dist <= upper_dist + par->
max_dist)
651 if (parent->dist <= upper_dist + chi->
max_dist)
655 if (max_scale < chi->
scale)
656 max_scale = chi->
scale;
660 else if (parent->dist <= upper_dist)
663 push(zero_set, temp);
667 for (chi++; chi != child_end; chi++)
672 float d =
distance(query->
p, chi->
p, upper_chi);
675 if (d < *upper_bound)
679 if (max_scale < chi->
scale)
680 max_scale = chi->
scale;
685 if (d <= upper_chi - chi->max_dist)
688 push(zero_set, temp);
707 brute_nearest(query_chi, zero_set, upper_bound, results, spare_zero_sets);
711 for (query_chi++;query_chi != child_end; query_chi++)
714 copy_zero_set(query_chi, new_upper_bound, zero_set, new_zero_set);
715 brute_nearest(query_chi, new_zero_set, new_upper_bound, results, spare_zero_sets);
717 free (new_upper_bound);
718 new_zero_set.
index = 0;
719 push(spare_zero_sets, new_zero_set);
724 push(temp, query->
p);
725 d_node<P> *end = zero_set.elements + zero_set.index;
726 for (
d_node<P> *ele = zero_set.elements; ele != end ; ele++)
727 if (ele->dist <= *upper_bound)
728 push(temp, ele->n->p);
744 if (current_scale > max_scale)
745 brute_nearest(query, zero_set, upper_bound, results, spare_zero_sets);
747 if (query->
scale <= current_scale && query->
scale != 100)
756 for (query_chi++; query_chi != child_end; query_chi++)
759 copy_zero_set(query_chi, new_upper_bound, zero_set, new_zero_set);
760 copy_cover_sets(query_chi, new_upper_bound, cover_sets, new_cover_sets,
761 current_scale, max_scale);
763 current_scale, max_scale, new_upper_bound,
764 results, spare_cover_sets, spare_zero_sets);
766 free (new_upper_bound);
767 new_zero_set.
index = 0;
768 push(spare_zero_sets, new_zero_set);
769 push(spare_cover_sets, new_cover_sets);
771 current_scale, max_scale, upper_bound, results,
772 spare_cover_sets, spare_zero_sets);
776 halfsort(cover_sets[current_scale]);
777 descend(query, upper_bound, current_scale, max_scale,cover_sets, zero_set);
778 cover_sets[current_scale++].index = 0;
780 current_scale, max_scale, upper_bound, results,
781 spare_cover_sets, spare_zero_sets);
796 setter(upper_bound,FLT_MAX);
798 float top_dist =
distance(query.
p, top_node.
p, FLT_MAX);
799 update(upper_bound, top_dist);
802 push(cover_sets[0], temp);
805 spare_cover_sets,spare_zero_sets);
808 push(spare_cover_sets, cover_sets);
810 for (
int i = 0; i < spare_cover_sets.
index; i++)
813 for (
int j = 0; j < cover_sets2.
index; j++)
814 free (cover_sets2[j].elements);
819 push(spare_zero_sets, zero_set);
821 for (
int i = 0; i < spare_zero_sets.
index; i++)
822 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)
void print(int depth, node< P > &top_node)
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)
static const float64_t epsilon
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 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)
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)
void dist_split(v_array< ds_node< P > > &point_set, v_array< ds_node< P > > &new_point_set, P new_point, int max_scale)