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

SHOGUN Machine Learning Toolbox - Documentation