Tapkee
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
covertree.hpp
Go to the documentation of this file.
1 /*
2  * This program is free software; you can redistribute it and/or modify
3  * it under the terms of the GNU General Public License as published by
4  * the Free Software Foundation; either version 3 of the License, or
5  * (at your option) any later version.
6  *
7  * Copyright (c) 2009-2013 John Langford, Dinoj Surendran, Fernando José Iglesias García
8  */
9 
10 #ifndef COVERTREE_H_
11 #define COVERTREE_H_
12 
13 /* Tapkee includes */
15 /* End of Tapkee includes */
16 
17 #include <cmath>
18 #include <limits>
19 #include <stdio.h>
20 #include <assert.h>
21 
22 /* First written by John Langford jl@hunch.net
23  Templatization by Dinoj Surendran dinojs@gmail.com
24  Adaptation to Shogun by Fernando José Iglesias García
25  */
26 namespace tapkee
27 {
28 namespace tapkee_internal
29 {
30 
34 template<class P>
35 struct node
36 {
37  node() : p(), max_dist(0.0), parent_dist(0.0),
38  children(NULL), num_children(0), scale(0)
39  {
40  }
41 
42  node(P _p, ScalarType _max_dist, ScalarType _parent_dist, node<P>* _children,
43  unsigned short int _num_children, short int _scale) : p(_p),
44  max_dist(_max_dist), parent_dist(_parent_dist), children(_children),
45  num_children(_num_children), scale(_scale)
46  {
47  }
48 
50  P p;
51 
54 
57 
60 
62  unsigned short int num_children;
63 
65  short int scale;
66 };
67 
68 template<class P>
69 void free_children(const node<P>& n)
70 {
71  for (int i=0; i<n.num_children; i++)
72  {
73  free_children<P>(n.children[i]);
74  n.children[i].~node<P>();
75  }
76  free(n.children);
77 }
78 
79 
83 template<class P>
84 struct ds_node {
85 
86  ds_node() : dist(), p() {}
87 
90 
92  P p;
93 };
94 
96 static ScalarType il2 = 1. / log(base);
97 
98 inline ScalarType dist_of_scale (int s)
99 {
100  return pow(base, s);
101 }
102 
103 inline int get_scale(ScalarType d)
104 {
105  return (int)ceil(il2 * log(d));
106 }
107 
108  template<class P>
109 node<P> new_node(const P &p)
110 {
112  new_node.p = p;
113  return new_node;
114 }
115 
116  template<class P>
117 node<P> new_leaf(const P &p)
118 {
119  node<P> new_leaf(p,0.,0.,NULL,0,100);
120  return new_leaf;
121 }
122 
123  template<class P>
125 {
126  ScalarType max = 0.;
127  for (int i = 0; i < v.index; i++)
128  if ( max < v[i].dist.last())
129  max = v[i].dist.last();
130  return max;
131 }
132 
133 void print_space(int s)
134 {
135  for (int i = 0; i < s; i++)
136  printf(" ");
137 }
138 
139 template<class P>
140 void print(int depth, node<P> &top_node)
141 {
142  print_space(depth);
143  print(top_node.p);
144  if ( top_node.num_children > 0 )
145  {
146  print_space(depth);
147  printf("scale = %i\n",top_node.scale);
148  print_space(depth);
149  printf("max_dist = %f\n",top_node.max_dist);
150  print_space(depth);
151  printf("num children = %i\n",top_node.num_children);
152  for (int i = 0; i < top_node.num_children;i++)
153  print(depth+1, top_node.children[i]);
154  }
155 }
156 
157 template<class P>
158 void split(v_array<ds_node<P> >& point_set, v_array<ds_node<P> >& far_set, int max_scale)
159 {
160  IndexType new_index = 0;
161  ScalarType fmax = dist_of_scale(max_scale);
162  for (int i = 0; i < point_set.index; i++)
163  {
164  if (point_set[i].dist.last() <= fmax)
165  {
166  point_set[new_index++] = point_set[i];
167  }
168  else
169  push(far_set,point_set[i]);
170  }
171  point_set.index=new_index;
172 }
173 
174 template<class P, class DistanceCallback>
175 void dist_split(DistanceCallback& dcb, v_array<ds_node<P> >& point_set,
176  v_array<ds_node<P> >& new_point_set,
177  P new_point,
178  int max_scale)
179 {
180  IndexType new_index = 0;
181  ScalarType fmax = dist_of_scale(max_scale);
182  for(int i = 0; i < point_set.index; i++)
183  {
184  ScalarType new_d;
185  new_d = distance(dcb, new_point, point_set[i].p, fmax);
186  if (new_d <= fmax )
187  {
188  push(point_set[i].dist, new_d);
189  push(new_point_set,point_set[i]);
190  }
191  else
192  point_set[new_index++] = point_set[i];
193  }
194  point_set.index = new_index;
195 }
196 
197 /*
198  max_scale is the maximum scale of the node we might create here.
199  point_set contains points which are 2*max_scale or less away.
200  */
201 template <class P, class DistanceCallback>
202 node<P> batch_insert(DistanceCallback& dcb, const P& 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  ScalarType max_dist = max_set(point_set); //O(|point_set|)
213  int next_scale = std::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(dcb, 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  ScalarType new_dist = point_set.last().dist.last();
254  push(consumed_set, point_set.last());
255  point_set.decr();
256 
257  dist_split(dcb,point_set,new_point_set,new_point,max_scale); //O(|point_saet|)
258  dist_split(dcb,far,new_point_set,new_point,max_scale); //O(|far|)
259 
260  node<P> new_child =
261  batch_insert(dcb, 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  ScalarType 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, class DistanceCallback>
299 node<P> batch_create(DistanceCallback& dcb, v_array<P> points)
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(dcb, points[0], points[i], std::numeric_limits<ScalarType>::max()));
308  temp.p = points[i];
309  push(point_set,temp);
310  }
311 
312  v_array<ds_node<P> > consumed_set;
313 
314  ScalarType max_dist = max_set(point_set);
315 
316  node<P> top = batch_insert (dcb, 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 {
394 
396  const node<P> *n;
397 };
398 
399 template <class P>
400 inline ScalarType 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  if (cover_set.index <= 1)
409  return;
410  register d_node<P> *base_ptr = cover_set.elements;
411 
412  d_node<P> *hi = &base_ptr[cover_set.index - 1];
413  d_node<P> *right_ptr = hi;
414  d_node<P> *left_ptr;
415 
416  while (right_ptr > base_ptr)
417  {
418  d_node<P> *mid = base_ptr + ((hi - base_ptr) >> 1);
419 
420  if (compare ( mid, base_ptr) < 0.)
421  std::swap(*mid, *base_ptr);
422  if (compare ( hi, mid) < 0.)
423  std::swap(*mid, *hi);
424  else
425  goto jump_over;
426  if (compare ( mid, base_ptr) < 0.)
427  std::swap(*mid, *base_ptr);
428 jump_over:;
429 
430  left_ptr = base_ptr + 1;
431  right_ptr = hi - 1;
432 
433  do
434  {
435  while (compare (left_ptr, mid) < 0.)
436  left_ptr++;
437 
438  while (compare (mid, right_ptr) < 0.)
439  right_ptr--;
440 
441  if (left_ptr < right_ptr)
442  {
443  std::swap(*left_ptr, *right_ptr);
444  if (mid == left_ptr)
445  mid = right_ptr;
446  else if (mid == right_ptr)
447  mid = left_ptr;
448  left_ptr++;
449  right_ptr--;
450  }
451  else if (left_ptr == right_ptr)
452  {
453  left_ptr ++;
454  right_ptr --;
455  break;
456  }
457  }
458  while (left_ptr <= right_ptr);
459  hi = right_ptr;
460  }
461 }
462 
463 template <class P>
465 {
466  v_array<v_array<d_node<P> > > ret = pop(spare_cover_sets);
467  while (ret.index < 101)
468  {
469  v_array<d_node<P> > temp;
470  push(ret, temp);
471  }
472  return ret;
473 }
474 
475 inline bool shell(ScalarType parent_query_dist, ScalarType child_parent_dist, ScalarType upper_bound)
476 {
477  return parent_query_dist - child_parent_dist <= upper_bound;
478  // && child_parent_dist - parent_query_dist <= upper_bound;
479 }
480 
481 int internal_k =1;
482 void update_k(ScalarType *k_upper_bound, ScalarType upper_bound)
483 {
484  ScalarType *end = k_upper_bound + internal_k-1;
485  ScalarType *begin = k_upper_bound;
486  for (;end != begin; begin++)
487  {
488  if (upper_bound < *(begin+1))
489  *begin = *(begin+1);
490  else {
491  *begin = upper_bound;
492  break;
493  }
494  }
495  if (end == begin)
496  *begin = upper_bound;
497 }
499 {
500  return (ScalarType*)malloc(sizeof(ScalarType) * internal_k);
501 }
502 void set_k(ScalarType* begin, ScalarType max)
503 {
504  for(ScalarType *end = begin+internal_k;end != begin; begin++)
505  *begin = max;
506 }
507 
509 //void update_epsilon(ScalarType *upper_bound, ScalarType new_dist) {}
511 {
512  return (ScalarType *)malloc(sizeof(ScalarType));
513 }
515 {
516  *begin = internal_epsilon;
517 }
518 
519 void update_unequal(ScalarType *upper_bound, ScalarType new_dist)
520 {
521  if (new_dist != 0.)
522  *upper_bound = new_dist;
523 }
524 ScalarType* (*alloc_unequal)() = alloc_epsilon;
526 {
527  *begin = max;
528 }
529 
530 void (*update)(ScalarType *foo, ScalarType bar) = update_k;
531 void (*setter)(ScalarType *foo, ScalarType bar) = set_k;
532 ScalarType* (*alloc_upper)() = alloc_k;
533 
534 template <class P, class DistanceCallback>
535 inline void copy_zero_set(DistanceCallback& dcb, node<P>* query_chi,
536  ScalarType* new_upper_bound, v_array<d_node<P> > &zero_set,
537  v_array<d_node<P> > &new_zero_set)
538 {
539  new_zero_set.index = 0;
540  d_node<P> *end = zero_set.elements + zero_set.index;
541  for (d_node<P> *ele = zero_set.elements; ele != end ; ele++)
542  {
543  ScalarType upper_dist = *new_upper_bound + query_chi->max_dist;
544  if (shell(ele->dist, query_chi->parent_dist, upper_dist))
545  {
546  ScalarType d = distance(dcb, query_chi->p, ele->n->p, upper_dist);
547 
548  if (d <= upper_dist)
549  {
550  if (d < *new_upper_bound)
551  update(new_upper_bound, d);
552  d_node<P> temp = {d, ele->n};
553  push(new_zero_set,temp);
554  }
555  }
556  }
557 }
558 
559 template <class P, class DistanceCallback>
560 inline void copy_cover_sets(DistanceCallback& dcb, node<P>* query_chi,
561  ScalarType* new_upper_bound,
562  v_array<v_array<d_node<P> > > &cover_sets,
563  v_array<v_array<d_node<P> > > &new_cover_sets,
564  int current_scale, int max_scale)
565 {
566  for (; current_scale <= max_scale; current_scale++)
567  {
568  d_node<P>* ele = cover_sets[current_scale].elements;
569  d_node<P>* end = cover_sets[current_scale].elements + cover_sets[current_scale].index;
570  for (; ele != end; ele++)
571  {
572  ScalarType upper_dist = *new_upper_bound + query_chi->max_dist + ele->n->max_dist;
573  if (shell(ele->dist, query_chi->parent_dist, upper_dist))
574  {
575  ScalarType d = distance(dcb, query_chi->p, ele->n->p, upper_dist);
576 
577  if (d <= upper_dist)
578  {
579  if (d < *new_upper_bound)
580  update(new_upper_bound,d);
581  d_node<P> temp = {d, ele->n};
582  push(new_cover_sets[current_scale],temp);
583  }
584  }
585  }
586  }
587 }
588 
589 template <class P>
590 void print_query(const node<P> *top_node)
591 {
592  printf("query = \n");
593  print(top_node->p);
594  if ( top_node->num_children > 0 ) {
595  printf("scale = %i\n",top_node->scale);
596  printf("max_dist = %f\n",top_node->max_dist);
597  printf("num children = %i\n",top_node->num_children);
598  }
599 }
600 
601 template <class P>
603  v_array<d_node<P> > &zero_set,
604  int current_scale, int max_scale)
605 {
606  printf("cover set = \n");
607  for (; current_scale <= max_scale; current_scale++)
608  {
609  d_node<P> *ele = cover_sets[current_scale].elements;
610  d_node<P> *end = cover_sets[current_scale].elements + cover_sets[current_scale].index;
611  printf("%i\n", current_scale);
612  for (; ele != end; ele++)
613  {
614  node<P> *n = (node<P> *)ele->n;
615  print(n->p);
616  }
617  }
618  d_node<P> *end = zero_set.elements + zero_set.index;
619  printf("infinity\n");
620  for (d_node<P> *ele = zero_set.elements; ele != end ; ele++)
621  {
622  node<P> *n = (node<P> *)ele->n;
623  print(n->p);
624  }
625 }
626 
627 /*
628  An optimization to consider:
629  Make all distance evaluations occur in descend.
630 
631  Instead of passing a cover_set, pass a stack of cover sets. The
632  last element holds d_nodes with your distance. The next lower
633  element holds a d_node with the distance to your query parent,
634  next = query grand parent, etc..
635 
636  Compute distances in the presence of the tighter upper bound.
637  */
638 template <class P, class DistanceCallback>
639 inline
640 void descend(DistanceCallback& dcb, const node<P>* query, ScalarType* upper_bound,
641  int current_scale,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  ScalarType 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  ScalarType 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  ScalarType d = distance(dcb, 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, class DistanceCallback>
699 void brute_nearest(DistanceCallback& dcb, const node<P>* query,
700  v_array<d_node<P> > zero_set, ScalarType* 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(dcb, query_chi, zero_set, upper_bound, results, spare_zero_sets);
709  ScalarType* 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(dcb, query_chi, new_upper_bound, zero_set, new_zero_set);
716  brute_nearest(dcb, 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, class DistanceCallback>
735 void internal_batch_nearest_neighbor(DistanceCallback& dcb, const node<P> *query,
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  ScalarType* 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(dcb, 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  ScalarType* 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(dcb, query_chi, new_upper_bound, zero_set, new_zero_set);
761  copy_cover_sets(dcb, query_chi, new_upper_bound, cover_sets, new_cover_sets,
762  current_scale, max_scale);
763  internal_batch_nearest_neighbor(dcb, 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(dcb, 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(dcb, query, upper_bound, current_scale, max_scale,cover_sets, zero_set);
779  cover_sets[current_scale++].index = 0;
780  internal_batch_nearest_neighbor(dcb, 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, class DistanceCallback>
787 void batch_nearest_neighbor(DistanceCallback &dcb, const node<P> &top_node,
788  const node<P> &query, 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  ScalarType* upper_bound = alloc_upper();
797  setter(upper_bound, std::numeric_limits<ScalarType>::max());
798 
799  ScalarType top_dist = distance(dcb, query.p, top_node.p, std::numeric_limits<ScalarType>::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(dcb, &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, class DistanceCallback>
828 void k_nearest_neighbor(DistanceCallback &dcb, const node<P> &top_node,
829  const node<P> &query, 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(dcb, top_node, query, results);
837 }
838 /*
839 template <class P, class DistanceCallback>
840 void epsilon_nearest_neighbor(DistanceCallback &dcb, const node<P> &top_node,
841  const node<P> &query, v_array<v_array<P> > &results,
842  ScalarType epsilon)
843 {
844  internal_epsilon = epsilon;
845  // update = update_epsilon;
846  setter = set_epsilon;
847  alloc_upper = alloc_epsilon;
848 
849  batch_nearest_neighbor(dcb, top_node, query, results);
850 }
851 
852 template <class P, class DistanceCallback>
853 void unequal_nearest_neighbor(DistanceCallback &dcb, const node<P> &top_node,
854  const node<P> &query, v_array<v_array<P> > &results)
855 {
856  update = update_unequal;
857  setter = set_unequal;
858  alloc_upper = alloc_unequal;
859 
860  batch_nearest_neighbor(dcb, top_node, query, results);
861 }
862 */
863 
864 }
865 }
866 #endif
ScalarType dist_of_scale(int s)
Definition: covertree.hpp:98
ScalarType distance(Callback &cb, const CoverTreePoint< RandomAccessIterator > &l, const CoverTreePoint< RandomAccessIterator > &r, ScalarType upper_bound)
void k_nearest_neighbor(DistanceCallback &dcb, const node< P > &top_node, const node< P > &query, v_array< v_array< P > > &results, int k)
Definition: covertree.hpp:828
void copy_cover_sets(DistanceCallback &dcb, node< P > *query_chi, ScalarType *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: covertree.hpp:560
void depth_dist(int top_scale, const node< P > top_node, v_array< int > &depths)
Definition: covertree.hpp:363
bool shell(ScalarType parent_query_dist, ScalarType child_parent_dist, ScalarType upper_bound)
Definition: covertree.hpp:475
void add_height(int d, v_array< int > &heights)
Definition: covertree.hpp:332
node< P > batch_create(DistanceCallback &dcb, v_array< P > points)
Definition: covertree.hpp:299
ScalarType max_set(v_array< ds_node< P > > &v)
Definition: covertree.hpp:124
void update_k(ScalarType *k_upper_bound, ScalarType upper_bound)
Definition: covertree.hpp:482
void dist_split(DistanceCallback &dcb, v_array< ds_node< P > > &point_set, v_array< ds_node< P > > &new_point_set, P new_point, int max_scale)
Definition: covertree.hpp:175
void set_unequal(ScalarType *begin, ScalarType max)
Definition: covertree.hpp:525
double ScalarType
default scalar value (can be overrided with TAPKEE_CUSTOM_INTERNAL_NUMTYPE define) ...
Definition: types.hpp:15
static ScalarType il2
Definition: covertree.hpp:96
v_array< v_array< d_node< P > > > get_cover_sets(v_array< v_array< v_array< d_node< P > > > > &spare_cover_sets)
Definition: covertree.hpp:464
void descend(DistanceCallback &dcb, const node< P > *query, ScalarType *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: covertree.hpp:640
void alloc(v_array< T > &v, int length)
void split(v_array< ds_node< P > > &point_set, v_array< ds_node< P > > &far_set, int max_scale)
Definition: covertree.hpp:158
void free_children(const node< P > &n)
Definition: covertree.hpp:69
int height_dist(const node< P > top_node, v_array< int > &heights)
Definition: covertree.hpp:341
int IndexType
indexing type (non-overridable) set to int for compatibility with OpenMP 2.0
Definition: types.hpp:19
void print(int depth, node< P > &top_node)
Definition: covertree.hpp:140
node< P > new_node(const P &p)
Definition: covertree.hpp:109
node< P > new_leaf(const P &p)
Definition: covertree.hpp:117
void push(v_array< T > &v, const T &new_ele)
int get_scale(ScalarType d)
Definition: covertree.hpp:103
ScalarType internal_epsilon
Definition: covertree.hpp:508
void batch_nearest_neighbor(DistanceCallback &dcb, const node< P > &top_node, const node< P > &query, v_array< v_array< P > > &results)
Definition: covertree.hpp:787
void internal_batch_nearest_neighbor(DistanceCallback &dcb, 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, ScalarType *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: covertree.hpp:735
v_array< ScalarType > dist
Definition: covertree.hpp:89
static ScalarType base
Definition: covertree.hpp:95
void print_query(const node< P > *top_node)
Definition: covertree.hpp:590
void(* setter)(ScalarType *foo, ScalarType bar)
Definition: covertree.hpp:531
void breadth_dist(const node< P > top_node, v_array< int > &breadths)
Definition: covertree.hpp:374
node< P > batch_insert(DistanceCallback &dcb, 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: covertree.hpp:202
void update_unequal(ScalarType *upper_bound, ScalarType new_dist)
Definition: covertree.hpp:519
ScalarType compare(const d_node< P > *p1, const d_node< P > *p2)
Definition: covertree.hpp:400
ScalarType * alloc_epsilon()
Definition: covertree.hpp:510
void set_epsilon(ScalarType *begin)
Definition: covertree.hpp:514
ScalarType *(* alloc_upper)()
Definition: covertree.hpp:532
void brute_nearest(DistanceCallback &dcb, const node< P > *query, v_array< d_node< P > > zero_set, ScalarType *upper_bound, v_array< v_array< P > > &results, v_array< v_array< d_node< P > > > &spare_zero_sets)
Definition: covertree.hpp:699
void copy_zero_set(DistanceCallback &dcb, node< P > *query_chi, ScalarType *new_upper_bound, v_array< d_node< P > > &zero_set, v_array< d_node< P > > &new_zero_set)
Definition: covertree.hpp:535
#define COVERTREE_BASE
Base of covertree. Could be overrided if TAPKEE_CUSTOM_PROPERTIES file is defined.
Definition: defines.hpp:37
v_array< T > pop(v_array< v_array< T > > &stack)
unsigned short int num_children
Definition: covertree.hpp:62
void halfsort(v_array< d_node< P > > cover_set)
Definition: covertree.hpp:406
node(P _p, ScalarType _max_dist, ScalarType _parent_dist, node< P > *_children, unsigned short int _num_children, short int _scale)
Definition: covertree.hpp:42
void set_k(ScalarType *begin, ScalarType max)
Definition: covertree.hpp:502
void(* update)(ScalarType *foo, ScalarType bar)
Definition: covertree.hpp:530
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: covertree.hpp:602
ScalarType * alloc_k()
Definition: covertree.hpp:498