SHOGUN  6.0.0
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules
JLCoverTree.h
Go to the documentation of this file.
1 #ifndef JLCOVERTREE_H
2 #define JLCOVERTREE_H
3 
4 #include <shogun/lib/config.h>
5 
8 
9 #include<math.h>
10 #include<stdio.h>
11 #ifndef NDEBUG
12 #define NDEBUG
13 #endif // NDEBUG
14 #include<cassert>
15 #ifdef _WIN32
16 #undef far
17 #undef near
18 #endif
19 
20 /* First written by John Langford jl@hunch.net
21  Templatization by Dinoj Surendran dinojs@gmail.com
22  Adaptation to Shogun by Fernando José Iglesias García
23 */
24 
25 // the files below may not need to be included
26 
27 /* Whatever structure/class/type is used for P, it must have the following functions defined:
28 
29  float distance(P v1, P v2, float upper_bound);
30  : this returns the distance between two P objects
31  : the distance does not have to be calculated fully if it's more than upper_bound
32 
33  v_array<P> parse_points(char *filename);
34  : this fills up a v_array of P objects from the input file
35 
36  void print(point &P);
37  : this prints out the contents of a P object.
38 */
39 
40 using namespace shogun;
41 
45 template<class P>
46 struct node {
47 
49  P p;
50 
52  float max_dist;
53 
55  float parent_dist;
56 
59 
61  unsigned short int num_children;
62 
64  short int scale;
65 
66 };
67 
68 //template<class P>
69 //node<P> insert(P newpoint, node<P> *top_node); // not yet implemented
70 //
71 //template<class P>
72 //void remove(P byepoint, node<P> *top_node); // not yet implemented
73 //query
74 
78 template<class P>
79 struct ds_node {
80 
83 
85  P p;
86 
87 };
88 
89 static float base = 1.3;
90 
91 
92 static float il2 = 1. / log(base);
93 
94 inline float dist_of_scale (int s)
95 {
96  return CMath::pow(base, s);
97 }
98 
99 inline int get_scale(float d)
100 {
101  return (int) CMath::ceil(il2 * log(d));
102 }
103 
104 template<class P>
105 node<P> new_node(const P &p)
106 {
108  new_node.p = p;
109  return new_node;
110 }
111 
112 template<class P>
113 node<P> new_leaf(const P &p)
114 {
115  node<P> new_leaf = {p,0.,0.,NULL,0,100};
116  return new_leaf;
117 }
118 
119 template<class P>
121 {
122  float max = 0.;
123  for (int i = 0; i < v.index; i++)
124  if ( max < v[i].dist.last())
125  max = v[i].dist.last();
126  return max;
127 }
128 
129 void print_space(int s)
130 {
131  for (int i = 0; i < s; i++)
132  SG_SPRINT(" ")
133 }
134 
135 template<class P>
136 void print(int depth, node<P> &top_node)
137 {
138  print_space(depth);
139  print(top_node.p);
140  if ( top_node.num_children > 0 )
141  {
142  print_space(depth);
143  SG_SPRINT("scale = %i\n",top_node.scale)
144  print_space(depth);
145  SG_SPRINT("max_dist = %f\n",top_node.max_dist)
146  print_space(depth);
147  SG_SPRINT("num children = %i\n",top_node.num_children)
148  for (int i = 0; i < top_node.num_children;i++)
149  print(depth+1, top_node.children[i]);
150  }
151 }
152 
153 template<class P>
154 void split(v_array<ds_node<P> >& point_set, v_array<ds_node<P> >& far_set, int max_scale)
155 {
156  unsigned int new_index = 0;
157  float fmax = dist_of_scale(max_scale);
158  for (int i = 0; i < point_set.index; i++)
159  {
160  if (point_set[i].dist.last() <= fmax)
161  {
162  point_set[new_index++] = point_set[i];
163  }
164  else
165  push(far_set,point_set[i]);
166  }
167  point_set.index=new_index;
168 }
169 
170 template<class P>
171 void dist_split(v_array<ds_node<P> >& point_set,
172  v_array<ds_node<P> >& new_point_set,
173  P new_point,
174  int max_scale)
175 {
176  unsigned int new_index = 0;
177  float fmax = dist_of_scale(max_scale);
178  for(int i = 0; i < point_set.index; i++)
179  {
180  float new_d;
181  new_d = distance(new_point, point_set[i].p, fmax);
182  if (new_d <= fmax )
183  {
184  push(point_set[i].dist, new_d);
185  push(new_point_set,point_set[i]);
186  }
187  else
188  point_set[new_index++] = point_set[i];
189  }
190  point_set.index = new_index;
191 }
192 
193 
194 
195 
196 /*
197  max_scale is the maximum scale of the node we might create here.
198  point_set contains points which are 2*max_scale or less away.
199 */
200 
201 template <class P>
203  int max_scale,
204  int top_scale,
205  v_array<ds_node<P> >& point_set,
206  v_array<ds_node<P> >& consumed_set,
207  v_array<v_array<ds_node<P> > >& stack)
208 {
209  if (point_set.index == 0)
210  return new_leaf(p);
211  else {
212  float max_dist = max_set(point_set); //O(|point_set|)
213  int next_scale = CMath::min(max_scale - 1, get_scale(max_dist));
214  if (next_scale == -2147483647-1) // We have points with distance 0.
215  {
216  v_array<node<P> > children;
217  push(children,new_leaf(p));
218  while (point_set.index > 0)
219  {
220  push(children,new_leaf(point_set.last().p));
221  push(consumed_set,point_set.last());
222  point_set.decr();
223  }
224  node<P> n = new_node(p);
225  n.scale = 100; // A magic number meant to be larger than all scales.
226  n.max_dist = 0;
227  alloc(children,children.index);
228  n.num_children = children.index;
229  n.children = children.elements;
230  return n;
231  }
232  else
233  {
234  v_array<ds_node<P> > far = pop(stack);
235  split(point_set,far,max_scale); //O(|point_set|)
236 
237  node<P> child = batch_insert(p, next_scale, top_scale, point_set, consumed_set, stack);
238 
239  if (point_set.index == 0)
240  {
241  push(stack,point_set);
242  point_set=far;
243  return child;
244  }
245  else {
246  node<P> n = new_node(p);
247  v_array<node<P> > children;
248  push(children, child);
249  v_array<ds_node<P> > new_point_set = pop(stack);
250  v_array<ds_node<P> > new_consumed_set = pop(stack);
251  while (point_set.index != 0) { //O(|point_set| * num_children)
252  P new_point = point_set.last().p;
253  float new_dist = point_set.last().dist.last();
254  push(consumed_set, point_set.last());
255  point_set.decr();
256 
257  dist_split(point_set, new_point_set, new_point, max_scale); //O(|point_saet|)
258  dist_split(far,new_point_set,new_point,max_scale); //O(|far|)
259 
260  node<P> new_child =
261  batch_insert(new_point, next_scale, top_scale, new_point_set, new_consumed_set, stack);
262  new_child.parent_dist = new_dist;
263 
264  push(children, new_child);
265 
266  float fmax = dist_of_scale(max_scale);
267  for(int i = 0; i< new_point_set.index; i++) //O(|new_point_set|)
268  {
269  new_point_set[i].dist.decr();
270  if (new_point_set[i].dist.last() <= fmax)
271  push(point_set, new_point_set[i]);
272  else
273  push(far, new_point_set[i]);
274  }
275  for(int i = 0; i< new_consumed_set.index; i++) //O(|new_point_set|)
276  {
277  new_consumed_set[i].dist.decr();
278  push(consumed_set, new_consumed_set[i]);
279  }
280  new_point_set.index = 0;
281  new_consumed_set.index = 0;
282  }
283  push(stack,new_point_set);
284  push(stack,new_consumed_set);
285  push(stack,point_set);
286  point_set=far;
287  n.scale = top_scale - max_scale;
288  n.max_dist = max_set(consumed_set);
289  alloc(children,children.index);
290  n.num_children = children.index;
291  n.children = children.elements;
292  return n;
293  }
294  }
295  }
296 }
297 
298 template<class P>
300 {
301  assert(points.index > 0);
302  v_array<ds_node<P> > point_set;
303  v_array<v_array<ds_node<P> > > stack;
304 
305  for (int i = 1; i < points.index; i++) {
306  ds_node<P> temp;
307  push(temp.dist, distance(points[0], points[i], FLT_MAX));
308  temp.p = points[i];
309  push(point_set,temp);
310  }
311 
312  v_array<ds_node<P> > consumed_set;
313 
314  float max_dist = max_set(point_set);
315 
316  node<P> top = batch_insert (points[0],
317  get_scale(max_dist),
318  get_scale(max_dist),
319  point_set,
320  consumed_set,
321  stack);
322  for (int i = 0; i<consumed_set.index;i++)
323  free(consumed_set[i].dist.elements);
324  free(consumed_set.elements);
325  for (int i = 0; i<stack.index;i++)
326  free(stack[i].elements);
327  free(stack.elements);
328  free(point_set.elements);
329  return top;
330 }
331 
332 void add_height(int d, v_array<int> &heights)
333 {
334  if (heights.index <= d)
335  for(;heights.index <= d;)
336  push(heights,0);
337  heights[d] = heights[d] + 1;
338 }
339 
340 template <class P>
341 int height_dist(const node<P> top_node,v_array<int> &heights)
342 {
343  if (top_node.num_children == 0)
344  {
345  add_height(0,heights);
346  return 0;
347  }
348  else
349  {
350  int max_v=0;
351  for (int i = 0; i<top_node.num_children ;i++)
352  {
353  int d = height_dist(top_node.children[i], heights);
354  if (d > max_v)
355  max_v = d;
356  }
357  add_height(1 + max_v, heights);
358  return (1 + max_v);
359  }
360 }
361 
362 template <class P>
363 void depth_dist(int top_scale, const node<P> top_node,v_array<int> &depths)
364 {
365  if (top_node.num_children > 0)
366  for (int i = 0; i<top_node.num_children ;i++)
367  {
368  add_height(top_node.scale, depths);
369  depth_dist(top_scale, top_node.children[i], depths);
370  }
371 }
372 
373 template <class P>
374 void breadth_dist(const node<P> top_node,v_array<int> &breadths)
375 {
376  if (top_node.num_children == 0)
377  add_height(0,breadths);
378  else
379  {
380  for (int i = 0; i<top_node.num_children ;i++)
381  breadth_dist(top_node.children[i], breadths);
382  add_height(top_node.num_children, breadths);
383  }
384 }
385 
389 template <class P>
390 struct d_node {
391 
393  float dist;
394 
396  const node<P> *n;
397 };
398 
399 template <class P>
400 inline float compare(const d_node<P> *p1, const d_node<P>* p2)
401 {
402  return p1 -> dist - p2 -> dist;
403 }
404 
405 template <class P>
406 void halfsort (v_array<d_node<P> > cover_set)
407 {
408 
409  if (cover_set.index <= 1)
410  return;
411  register d_node<P> *base_ptr = cover_set.elements;
412 
413  d_node<P> *hi = &base_ptr[cover_set.index - 1];
414  d_node<P> *right_ptr = hi;
415  d_node<P> *left_ptr;
416 
417  while (right_ptr > base_ptr)
418  {
419  d_node<P> *mid = base_ptr + ((hi - base_ptr) >> 1);
420 
421  if (compare ( mid, base_ptr) < 0.)
422  CMath::swap(*mid, *base_ptr);
423  if (compare ( hi, mid) < 0.)
424  CMath::swap(*mid, *hi);
425  else
426  goto jump_over;
427  if (compare ( mid, base_ptr) < 0.)
428  CMath::swap(*mid, *base_ptr);
429  jump_over:;
430 
431  left_ptr = base_ptr + 1;
432  right_ptr = hi - 1;
433 
434  do
435  {
436  while (compare (left_ptr, mid) < 0.)
437  left_ptr ++;
438 
439  while (compare (mid, right_ptr) < 0.)
440  right_ptr --;
441 
442  if (left_ptr < right_ptr)
443  {
444  CMath::swap(*left_ptr, *right_ptr);
445  if (mid == left_ptr)
446  mid = right_ptr;
447  else if (mid == right_ptr)
448  mid = left_ptr;
449  left_ptr ++;
450  right_ptr --;
451  }
452  else if (left_ptr == right_ptr)
453  {
454  left_ptr ++;
455  right_ptr --;
456  break;
457  }
458  }
459  while (left_ptr <= right_ptr);
460 
461  hi = right_ptr;
462  }
463 }
464 
465 
466 template <class P>
468 {
469  v_array<v_array<d_node<P> > > ret = pop(spare_cover_sets);
470  while (ret.index < 101)
471  {
472  v_array<d_node<P> > temp;
473  push(ret, temp);
474  }
475  return ret;
476 }
477 
478 inline bool shell(float parent_query_dist, float child_parent_dist, float upper_bound)
479 {
480  return parent_query_dist - child_parent_dist <= upper_bound;
481  // && child_parent_dist - parent_query_dist <= upper_bound;
482 }
483 
484 int internal_k =1;
485 void update_k(float *k_upper_bound, float upper_bound)
486 {
487  float *end = k_upper_bound + internal_k-1;
488  float *begin = k_upper_bound;
489  for (;end != begin; begin++)
490  {
491  if (upper_bound < *(begin+1))
492  *begin = *(begin+1);
493  else {
494  *begin = upper_bound;
495  break;
496  }
497  }
498  if (end == begin)
499  *begin = upper_bound;
500 }
501 float *alloc_k()
502 {
503  return (float *)malloc(sizeof(float) * internal_k);
504 }
505 void set_k(float* begin, float max)
506 {
507  for(float *end = begin+internal_k;end != begin; begin++)
508  *begin = max;
509 }
510 
512 void update_epsilon(float *upper_bound, float new_dist) {}
514 {
515  return (float *)malloc(sizeof(float));
516 }
517 void set_epsilon(float* begin, float max)
518 {
519  *begin = internal_epsilon;
520 }
521 
522 void update_unequal(float *upper_bound, float new_dist)
523 {
524  if (new_dist != 0.)
525  *upper_bound = new_dist;
526 }
527 float* (*alloc_unequal)() = alloc_epsilon;
528 void set_unequal(float* begin, float max)
529 {
530  *begin = max;
531 }
532 
533 void (*update)(float *foo, float bar) = update_k;
534 void (*setter)(float *foo, float bar) = set_k;
535 float* (*alloc_upper)() = alloc_k;
536 
537 template <class P>
538 inline void copy_zero_set(node<P>* query_chi, float* new_upper_bound,
539  v_array<d_node<P> > &zero_set, v_array<d_node<P> > &new_zero_set)
540 {
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++)
544  {
545  float upper_dist = *new_upper_bound + query_chi->max_dist;
546  if (shell(ele->dist, query_chi->parent_dist, upper_dist))
547  {
548  float d = distance(query_chi->p, ele->n->p, upper_dist);
549 
550  if (d <= upper_dist)
551  {
552  if (d < *new_upper_bound)
553  update(new_upper_bound, d);
554  d_node<P> temp = {d, ele->n};
555  push(new_zero_set,temp);
556  }
557  }
558  }
559 }
560 
561 template <class P>
562 inline void copy_cover_sets(node<P>* query_chi, float* new_upper_bound,
563  v_array<v_array<d_node<P> > > &cover_sets,
564  v_array<v_array<d_node<P> > > &new_cover_sets,
565  int current_scale, int max_scale)
566 {
567  for (; current_scale <= max_scale; current_scale++)
568  {
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++)
572  {
573  float upper_dist = *new_upper_bound + query_chi->max_dist + ele->n->max_dist;
574  if (shell(ele->dist, query_chi->parent_dist, upper_dist))
575  {
576  float d = distance(query_chi->p, ele->n->p, upper_dist);
577 
578  if (d <= upper_dist)
579  {
580  if (d < *new_upper_bound)
581  update(new_upper_bound,d);
582  d_node<P> temp = {d, ele->n};
583  push(new_cover_sets[current_scale],temp);
584  }
585  }
586  }
587  }
588 }
589 
590 template <class P>
591 void print_query(const node<P> *top_node)
592 {
593  SG_SPRINT ("query = \n")
594  print(top_node->p);
595  if ( top_node->num_children > 0 ) {
596  SG_SPRINT("scale = %i\n",top_node->scale)
597  SG_SPRINT("max_dist = %f\n",top_node->max_dist)
598  SG_SPRINT("num children = %i\n",top_node->num_children)
599  }
600 }
601 
602 template <class P>
604  v_array<d_node<P> > &zero_set,
605  int current_scale, int max_scale)
606 {
607  SG_SPRINT("cover set = \n")
608  for (; current_scale <= max_scale; current_scale++)
609  {
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;
612  SG_SPRINT ("%i\n", current_scale)
613  for (; ele != end; ele++)
614  {
615  node<P> *n = (node<P> *)ele->n;
616  print(n->p);
617  }
618  }
619  d_node<P> *end = zero_set.elements + zero_set.index;
620  SG_SPRINT ("infinity\n")
621  for (d_node<P> *ele = zero_set.elements; ele != end ; ele++)
622  {
623  node<P> *n = (node<P> *)ele->n;
624  print(n->p);
625  }
626 }
627 
628 
629 /*
630  An optimization to consider:
631  Make all distance evaluations occur in descend.
632 
633  Instead of passing a cover_set, pass a stack of cover sets. The
634  last element holds d_nodes with your distance. The next lower
635  element holds a d_node with the distance to your query parent,
636  next = query grand parent, etc..
637 
638  Compute distances in the presence of the tighter upper bound.
639  */
640 
641 template <class P>
642 inline
643 void descend(const node<P>* query, float* upper_bound,
644  int current_scale,
645  int &max_scale, v_array<v_array<d_node<P> > > &cover_sets,
646  v_array<d_node<P> > &zero_set)
647 {
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++)
650  {
651  const node<P> *par = parent->n;
652  float upper_dist = *upper_bound + query->max_dist + query->max_dist;
653  if (parent->dist <= upper_dist + par->max_dist)
654  {
655  node<P> *chi = par->children;
656  if (parent->dist <= upper_dist + chi->max_dist)
657  {
658  if (chi->num_children > 0)
659  {
660  if (max_scale < chi->scale)
661  max_scale = chi->scale;
662  d_node<P> temp = {parent->dist, chi};
663  push(cover_sets[chi->scale], temp);
664  }
665  else if (parent->dist <= upper_dist)
666  {
667  d_node<P> temp = {parent->dist, chi};
668  push(zero_set, temp);
669  }
670  }
671  node<P> *child_end = par->children + par->num_children;
672  for (chi++; chi != child_end; chi++)
673  {
674  float upper_chi = *upper_bound + chi->max_dist + query->max_dist + query->max_dist;
675  if (shell(parent->dist, chi->parent_dist, upper_chi))
676  {
677  float d = distance(query->p, chi->p, upper_chi);
678  if (d <= upper_chi)
679  {
680  if (d < *upper_bound)
681  update(upper_bound, d);
682  if (chi->num_children > 0)
683  {
684  if (max_scale < chi->scale)
685  max_scale = chi->scale;
686  d_node<P> temp = {d, chi};
687  push(cover_sets[chi->scale],temp);
688  }
689  else
690  if (d <= upper_chi - chi->max_dist)
691  {
692  d_node<P> temp = {d, chi};
693  push(zero_set, temp);
694  }
695  }
696  }
697  }
698  }
699  }
700 }
701 
702 template <class P>
703 void brute_nearest(const node<P>* query,v_array<d_node<P> > zero_set,
704  float* upper_bound,
705  v_array<v_array<P> > &results,
706  v_array<v_array<d_node<P> > > &spare_zero_sets)
707 {
708  if (query->num_children > 0)
709  {
710  v_array<d_node<P> > new_zero_set = pop(spare_zero_sets);
711  node<P> * query_chi = query->children;
712  brute_nearest(query_chi, zero_set, upper_bound, results, spare_zero_sets);
713  float* new_upper_bound = alloc_upper();
714 
715  node<P> *child_end = query->children + query->num_children;
716  for (query_chi++;query_chi != child_end; query_chi++)
717  {
718  setter(new_upper_bound,*upper_bound + query_chi->parent_dist);
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);
721  }
722  free (new_upper_bound);
723  new_zero_set.index = 0;
724  push(spare_zero_sets, new_zero_set);
725  }
726  else
727  {
728  v_array<P> temp;
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);
734  push(results,temp);
735  }
736 }
737 
738 template <class P>
740  v_array<v_array<d_node<P> > > &cover_sets,
741  v_array<d_node<P> > &zero_set,
742  int current_scale,
743  int max_scale,
744  float* upper_bound,
745  v_array<v_array<P> > &results,
746  v_array<v_array<v_array<d_node<P> > > > &spare_cover_sets,
747  v_array<v_array<d_node<P> > > &spare_zero_sets)
748 {
749  if (current_scale > max_scale) // All remaining points are in the zero set.
750  brute_nearest(query, zero_set, upper_bound, results, spare_zero_sets);
751  else
752  if (query->scale <= current_scale && query->scale != 100)
753  // Our query has too much scale. Reduce.
754  {
755  node<P> *query_chi = query->children;
756  v_array<d_node<P> > new_zero_set = pop(spare_zero_sets);
757  v_array<v_array<d_node<P> > > new_cover_sets = get_cover_sets(spare_cover_sets);
758  float* new_upper_bound = alloc_upper();
759 
760  node<P> *child_end = query->children + query->num_children;
761  for (query_chi++; query_chi != child_end; query_chi++)
762  {
763  setter(new_upper_bound,*upper_bound + query_chi->parent_dist);
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);
767  internal_batch_nearest_neighbor(query_chi, new_cover_sets, new_zero_set,
768  current_scale, max_scale, new_upper_bound,
769  results, spare_cover_sets, spare_zero_sets);
770  }
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);
775  internal_batch_nearest_neighbor(query->children, cover_sets, zero_set,
776  current_scale, max_scale, upper_bound, results,
777  spare_cover_sets, spare_zero_sets);
778  }
779  else // reduce cover set scale
780  {
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;
784  internal_batch_nearest_neighbor(query, cover_sets, zero_set,
785  current_scale, max_scale, upper_bound, results,
786  spare_cover_sets, spare_zero_sets);
787  }
788 }
789 
790 template <class P>
791 void batch_nearest_neighbor(const node<P> &top_node, const node<P> &query,
792  v_array<v_array<P> > &results)
793 {
794  v_array<v_array<v_array<d_node<P> > > > spare_cover_sets;
795  v_array<v_array<d_node<P> > > spare_zero_sets;
796 
797  v_array<v_array<d_node<P> > > cover_sets = get_cover_sets(spare_cover_sets);
798  v_array<d_node<P> > zero_set = pop(spare_zero_sets);
799 
800  float* upper_bound = alloc_upper();
801  setter(upper_bound,FLT_MAX);
802 
803  float top_dist = distance(query.p, top_node.p, FLT_MAX);
804  update(upper_bound, top_dist);
805 
806  d_node<P> temp = {top_dist, &top_node};
807  push(cover_sets[0], temp);
808 
809  internal_batch_nearest_neighbor(&query,cover_sets,zero_set,0,0,upper_bound,results,
810  spare_cover_sets,spare_zero_sets);
811 
812  free(upper_bound);
813  push(spare_cover_sets, cover_sets);
814 
815  for (int i = 0; i < spare_cover_sets.index; i++)
816  {
817  v_array<v_array<d_node<P> > > cover_sets2 = spare_cover_sets[i];
818  for (int j = 0; j < cover_sets2.index; j++)
819  free (cover_sets2[j].elements);
820  free(cover_sets2.elements);
821  }
822  free(spare_cover_sets.elements);
823 
824  push(spare_zero_sets, zero_set);
825 
826  for (int i = 0; i < spare_zero_sets.index; i++)
827  free(spare_zero_sets[i].elements);
828  free(spare_zero_sets.elements);
829 }
830 
831 template <class P>
832 void k_nearest_neighbor(const node<P> &top_node, const node<P> &query,
833  v_array<v_array<P> > &results, int k)
834 {
835  internal_k = k;
836  update = update_k;
837  setter = set_k;
839 
840  batch_nearest_neighbor(top_node, query,results);
841 }
842 
843 template <class P>
844 void epsilon_nearest_neighbor(const node<P> &top_node, const node<P> &query,
845  v_array<v_array<P> > &results, float epsilon)
846 {
847  internal_epsilon = epsilon;
851 
852  batch_nearest_neighbor(top_node, query,results);
853 }
854 
855 template <class P>
856 void unequal_nearest_neighbor(const node<P> &top_node, const node<P> &query,
857  v_array<v_array<P> > &results)
858 {
862 
863  batch_nearest_neighbor(top_node, query, results);
864 }
865 
866 #endif
float distance(CJLCoverTreePoint p1, CJLCoverTreePoint p2, float64_t upper_bound)
float compare(const d_node< P > *p1, const d_node< P > *p2)
Definition: JLCoverTree.h:400
node< P > * children
Definition: JLCoverTree.h:58
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)
Definition: JLCoverTree.h:703
float *(* alloc_upper)()
Definition: JLCoverTree.h:535
float dist
Definition: JLCoverTree.h:393
const node< P > * n
Definition: JLCoverTree.h:396
static float64_t ceil(float64_t d)
Definition: Math.h:411
node< P > new_node(const P &p)
Definition: JLCoverTree.h:105
void unequal_nearest_neighbor(const node< P > &top_node, const node< P > &query, v_array< v_array< P > > &results)
Definition: JLCoverTree.h:856
void update_k(float *k_upper_bound, float upper_bound)
Definition: JLCoverTree.h:485
node< P > batch_create(v_array< P > points)
Definition: JLCoverTree.h:299
void scale(SGVector< T > &a, SGVector< T > &result, T alpha=1)
void(* update)(float *foo, float bar)
Definition: JLCoverTree.h:533
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)
Definition: JLCoverTree.h:739
void breadth_dist(const node< P > top_node, v_array< int > &breadths)
Definition: JLCoverTree.h:374
void split(v_array< ds_node< P > > &point_set, v_array< ds_node< P > > &far_set, int max_scale)
Definition: JLCoverTree.h:154
float max_dist
Definition: JLCoverTree.h:52
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)
Definition: JLCoverTree.h:538
void update_unequal(float *upper_bound, float new_dist)
Definition: JLCoverTree.h:522
float * alloc_k()
Definition: JLCoverTree.h:501
v_array< T > pop(v_array< v_array< T > > &stack)
bool shell(float parent_query_dist, float child_parent_dist, float upper_bound)
Definition: JLCoverTree.h:478
void add_height(int d, v_array< int > &heights)
Definition: JLCoverTree.h:332
void print_query(const node< P > *top_node)
Definition: JLCoverTree.h:591
int get_scale(float d)
Definition: JLCoverTree.h:99
void push(v_array< T > &v, const T &new_ele)
void(* setter)(float *foo, float bar)
Definition: JLCoverTree.h:534
short int scale
Definition: JLCoverTree.h:64
#define SG_SPRINT(...)
Definition: SGIO.h:179
void halfsort(v_array< d_node< P > > cover_set)
Definition: JLCoverTree.h:406
unsigned short int num_children
Definition: JLCoverTree.h:61
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)
Definition: JLCoverTree.h:643
float internal_epsilon
Definition: JLCoverTree.h:511
void depth_dist(int top_scale, const node< P > top_node, v_array< int > &depths)
Definition: JLCoverTree.h:363
void alloc(v_array< T > &v, int length)
float * alloc_epsilon()
Definition: JLCoverTree.h:513
void batch_nearest_neighbor(const node< P > &top_node, const node< P > &query, v_array< v_array< P > > &results)
Definition: JLCoverTree.h:791
void print_space(int s)
Definition: JLCoverTree.h:129
void epsilon_nearest_neighbor(const node< P > &top_node, const node< P > &query, v_array< v_array< P > > &results, float epsilon)
Definition: JLCoverTree.h:844
static float il2
Definition: JLCoverTree.h:92
float dist_of_scale(int s)
Definition: JLCoverTree.h:94
void set_k(float *begin, float max)
Definition: JLCoverTree.h:505
all of classes and functions are contained in the shogun namespace
Definition: class_list.h:18
float *(* alloc_unequal)()
Definition: JLCoverTree.h:527
float parent_dist
Definition: JLCoverTree.h:55
v_array< float > dist
Definition: JLCoverTree.h:82
v_array< v_array< d_node< P > > > get_cover_sets(v_array< v_array< v_array< d_node< P > > > > &spare_cover_sets)
Definition: JLCoverTree.h:467
int internal_k
Definition: JLCoverTree.h:484
static T min(T a, T b)
Definition: Math.h:153
static float base
Definition: JLCoverTree.h:89
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)
Definition: JLCoverTree.h:562
float max_set(v_array< ds_node< P > > &v)
Definition: JLCoverTree.h:120
static void swap(T &a, T &b)
Definition: Math.h:433
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)
Definition: JLCoverTree.h:202
node< P > new_leaf(const P &p)
Definition: JLCoverTree.h:113
void k_nearest_neighbor(const node< P > &top_node, const node< P > &query, v_array< v_array< P > > &results, int k)
Definition: JLCoverTree.h:832
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)
Definition: JLCoverTree.h:603
void set_epsilon(float *begin, float max)
Definition: JLCoverTree.h:517
void set_unequal(float *begin, float max)
Definition: JLCoverTree.h:528
int height_dist(const node< P > top_node, v_array< int > &heights)
Definition: JLCoverTree.h:341
T max(const Container< T > &a)
void update_epsilon(float *upper_bound, float new_dist)
Definition: JLCoverTree.h:512
static int32_t pow(bool x, int32_t n)
Definition: Math.h:530
void dist_split(v_array< ds_node< P > > &point_set, v_array< ds_node< P > > &new_point_set, P new_point, int max_scale)
Definition: JLCoverTree.h:171

SHOGUN Machine Learning Toolbox - Documentation