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

SHOGUN Machine Learning Toolbox - Documentation