33 using namespace shogun;
89 return CMath::pow(
base, s);
94 return (
int) CMath::ceil(
il2 * log(d));
116 for (
int i = 0; i < v.index; i++)
117 if ( max < v[i].dist.last())
118 max = v[i].dist.last();
124 for (
int i = 0; i < s; i++)
149 unsigned int new_index = 0;
151 for (
int i = 0; i < point_set.index; i++)
153 if (point_set[i].dist.last() <= fmax)
155 point_set[new_index++] = point_set[i];
158 push(far_set,point_set[i]);
160 point_set.index=new_index;
169 unsigned int new_index = 0;
171 for(
int i = 0; i < point_set.index; i++)
174 new_d =
distance(new_point, point_set[i].p, fmax);
177 push(point_set[i].dist, new_d);
178 push(new_point_set,point_set[i]);
181 point_set[new_index++] = point_set[i];
183 point_set.index = new_index;
202 if (point_set.index == 0)
205 float max_dist =
max_set(point_set);
206 int next_scale = CMath::min(max_scale - 1,
get_scale(max_dist));
207 if (next_scale == -2147483647-1)
211 while (point_set.index > 0)
214 push(consumed_set,point_set.last());
228 split(point_set,far,max_scale);
232 if (point_set.index == 0)
234 push(stack,point_set);
241 push(children, child);
244 while (point_set.index != 0) {
245 P new_point = point_set.last().p;
246 float new_dist = point_set.last().dist.last();
247 push(consumed_set, point_set.last());
250 dist_split(point_set, new_point_set, new_point, max_scale);
251 dist_split(far,new_point_set,new_point,max_scale);
254 batch_insert(new_point, next_scale, top_scale, new_point_set, new_consumed_set, stack);
257 push(children, new_child);
260 for(
int i = 0; i< new_point_set.
index; i++)
262 new_point_set[i].dist.
decr();
263 if (new_point_set[i].dist.
last() <= fmax)
264 push(point_set, new_point_set[i]);
266 push(far, new_point_set[i]);
268 for(
int i = 0; i< new_consumed_set.
index; i++)
270 new_consumed_set[i].dist.
decr();
271 push(consumed_set, new_consumed_set[i]);
273 new_point_set.
index = 0;
274 new_consumed_set.
index = 0;
276 push(stack,new_point_set);
277 push(stack,new_consumed_set);
278 push(stack,point_set);
280 n.
scale = top_scale - max_scale;
294 assert(points.
index > 0);
298 for (
int i = 1; i < points.
index; i++) {
302 push(point_set,temp);
307 float max_dist =
max_set(point_set);
315 for (
int i = 0; i<consumed_set.
index;i++)
316 free(consumed_set[i].dist.
elements);
318 for (
int i = 0; i<stack.
index;i++)
319 free(stack[i].elements);
327 if (heights.
index <= d)
328 for(;heights.
index <= d;)
330 heights[d] = heights[d] + 1;
395 return p1 -> dist - p2 -> dist;
402 if (cover_set.index <= 1)
404 register d_node<P> *base_ptr = cover_set.elements;
406 d_node<P> *hi = &base_ptr[cover_set.index - 1];
410 while (right_ptr > base_ptr)
412 d_node<P> *mid = base_ptr + ((hi - base_ptr) >> 1);
414 if (
compare ( mid, base_ptr) < 0.)
415 CMath::swap(*mid, *base_ptr);
417 CMath::swap(*mid, *hi);
420 if (
compare ( mid, base_ptr) < 0.)
421 CMath::swap(*mid, *base_ptr);
424 left_ptr = base_ptr + 1;
429 while (
compare (left_ptr, mid) < 0.)
432 while (
compare (mid, right_ptr) < 0.)
435 if (left_ptr < right_ptr)
437 CMath::swap(*left_ptr, *right_ptr);
440 else if (mid == right_ptr)
445 else if (left_ptr == right_ptr)
452 while (left_ptr <= right_ptr);
463 while (ret.
index < 101)
471 inline bool shell(
float parent_query_dist,
float child_parent_dist,
float upper_bound)
473 return parent_query_dist - child_parent_dist <= upper_bound;
478 void update_k(
float *k_upper_bound,
float upper_bound)
481 float *begin = k_upper_bound;
482 for (;end != begin; begin++)
484 if (upper_bound < *(begin+1))
487 *begin = upper_bound;
492 *begin = upper_bound;
496 return (
float *)malloc(
sizeof(
float) *
internal_k);
500 for(
float *end = begin+
internal_k;end != begin; begin++)
508 return (
float *)malloc(
sizeof(
float));
518 *upper_bound = new_dist;
534 new_zero_set.index = 0;
535 d_node<P> *end = zero_set.elements + zero_set.index;
536 for (
d_node<P> *ele = zero_set.elements; ele != end ; ele++)
538 float upper_dist = *new_upper_bound + query_chi->
max_dist;
541 float d =
distance(query_chi->
p, ele->n->p, upper_dist);
545 if (d < *new_upper_bound)
546 update(new_upper_bound, d);
548 push(new_zero_set,temp);
558 int current_scale,
int max_scale)
560 for (; current_scale <= max_scale; current_scale++)
562 d_node<P>* ele = cover_sets[current_scale].elements;
563 d_node<P>* end = cover_sets[current_scale].elements + cover_sets[current_scale].index;
564 for (; ele != end; ele++)
566 float upper_dist = *new_upper_bound + query_chi->
max_dist + ele->
n->max_dist;
569 float d =
distance(query_chi->
p, ele->
n->p, upper_dist);
573 if (d < *new_upper_bound)
574 update(new_upper_bound,d);
576 push(new_cover_sets[current_scale],temp);
598 int current_scale,
int max_scale)
601 for (; current_scale <= max_scale; current_scale++)
603 d_node<P> *ele = cover_sets[current_scale].elements;
604 d_node<P> *end = cover_sets[current_scale].elements + cover_sets[current_scale].index;
606 for (; ele != end; ele++)
612 d_node<P> *end = zero_set.elements + zero_set.index;
614 for (
d_node<P> *ele = zero_set.elements; ele != end ; ele++)
641 d_node<P> *end = cover_sets[current_scale].elements + cover_sets[current_scale].index;
642 for (
d_node<P> *parent = cover_sets[current_scale].elements; parent != end; parent++)
644 const node<P> *par = parent->n;
646 if (parent->dist <= upper_dist + par->
max_dist)
649 if (parent->dist <= upper_dist + chi->
max_dist)
653 if (max_scale < chi->scale)
654 max_scale = chi->
scale;
658 else if (parent->dist <= upper_dist)
661 push(zero_set, temp);
665 for (chi++; chi != child_end; chi++)
670 float d =
distance(query->
p, chi->
p, upper_chi);
673 if (d < *upper_bound)
677 if (max_scale < chi->scale)
678 max_scale = chi->
scale;
683 if (d <= upper_chi - chi->max_dist)
686 push(zero_set, temp);
705 brute_nearest(query_chi, zero_set, upper_bound, results, spare_zero_sets);
709 for (query_chi++;query_chi != child_end; query_chi++)
712 copy_zero_set(query_chi, new_upper_bound, zero_set, new_zero_set);
713 brute_nearest(query_chi, new_zero_set, new_upper_bound, results, spare_zero_sets);
715 free (new_upper_bound);
716 new_zero_set.
index = 0;
717 push(spare_zero_sets, new_zero_set);
722 push(temp, query->
p);
723 d_node<P> *end = zero_set.elements + zero_set.index;
724 for (
d_node<P> *ele = zero_set.elements; ele != end ; ele++)
725 if (ele->dist <= *upper_bound)
726 push(temp, ele->n->p);
742 if (current_scale > max_scale)
743 brute_nearest(query, zero_set, upper_bound, results, spare_zero_sets);
745 if (query->
scale <= current_scale && query->
scale != 100)
754 for (query_chi++; query_chi != child_end; query_chi++)
757 copy_zero_set(query_chi, new_upper_bound, zero_set, new_zero_set);
758 copy_cover_sets(query_chi, new_upper_bound, cover_sets, new_cover_sets,
759 current_scale, max_scale);
761 current_scale, max_scale, new_upper_bound,
762 results, spare_cover_sets, spare_zero_sets);
764 free (new_upper_bound);
765 new_zero_set.
index = 0;
766 push(spare_zero_sets, new_zero_set);
767 push(spare_cover_sets, new_cover_sets);
769 current_scale, max_scale, upper_bound, results,
770 spare_cover_sets, spare_zero_sets);
774 halfsort(cover_sets[current_scale]);
775 descend(query, upper_bound, current_scale, max_scale,cover_sets, zero_set);
776 cover_sets[current_scale++].index = 0;
778 current_scale, max_scale, upper_bound, results,
779 spare_cover_sets, spare_zero_sets);
794 setter(upper_bound,FLT_MAX);
796 float top_dist =
distance(query.
p, top_node.
p, FLT_MAX);
797 update(upper_bound, top_dist);
800 push(cover_sets[0], temp);
803 spare_cover_sets,spare_zero_sets);
806 push(spare_cover_sets, cover_sets);
808 for (
int i = 0; i < spare_cover_sets.
index; i++)
811 for (
int j = 0; j < cover_sets2.
index; j++)
812 free (cover_sets2[j].elements);
817 push(spare_zero_sets, zero_set);
819 for (
int i = 0; i < spare_zero_sets.
index; i++)
820 free(spare_zero_sets[i].elements);