LCOV - code coverage report
Current view: top level - neighbors - covertree.hpp (source / functions) Hit Total Coverage
Test: clean.info Lines: 309 356 86.8 %
Date: 2013-05-24 Functions: 80 126 63.5 %
Branches: 323 746 43.3 %

           Branch data     Line data    Source code
       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 */
      14                 :            : #include <tapkee/neighbors/covertree_point.hpp>
      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                 :            : 
      31                 :            : /**
      32                 :            :  * Cover tree node TODO better doc
      33                 :            :  */
      34                 :            : template<class P>
      35                 :       1209 : struct node 
      36                 :            : {
      37                 :        551 :         node() : p(), max_dist(0.0), parent_dist(0.0), 
      38                 :        551 :                 children(NULL), num_children(0), scale(0) 
      39                 :            :         {
      40                 :        551 :         }
      41                 :            : 
      42                 :        670 :         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                 :        670 :                 num_children(_num_children), scale(_scale) 
      46                 :            :         {
      47                 :        670 :         }
      48                 :            : 
      49                 :            :         /** Point */
      50                 :            :         P p;
      51                 :            : 
      52                 :            :         /** The maximum distance to any grandchild */
      53                 :            :         ScalarType max_dist;
      54                 :            : 
      55                 :            :         /** The distance to the parent */
      56                 :            :         ScalarType parent_dist;
      57                 :            : 
      58                 :            :         /** Pointer to the list of children of this node */
      59                 :            :         node<P>* children;
      60                 :            : 
      61                 :            :         /** The number of children nodes of this node */
      62                 :            :         unsigned short int num_children;
      63                 :            : 
      64                 :            :         /** Essentially, an upper bound on the distance to any child */
      65                 :            :         short int scale;
      66                 :            : };
      67                 :            : 
      68                 :            : template<class P>
      69                 :       1221 : void free_children(const node<P>& n)
      70                 :            : {
      71 [ +  + ][ +  + ]:       2430 :         for (int i=0; i<n.num_children; i++)
      72                 :            :         {
      73                 :       1209 :                 free_children<P>(n.children[i]);
      74                 :       1209 :                 n.children[i].~node<P>();
      75                 :            :         }
      76                 :       1221 :         free(n.children);
      77                 :       1221 : }
      78                 :            : 
      79                 :            : 
      80                 :            : /**
      81                 :            :  * Cover tree node with an associated set of distances TODO better doc
      82                 :            :  */
      83                 :            : template<class P>
      84                 :            : struct ds_node {
      85                 :            : 
      86                 :        658 :         ds_node() : dist(), p() {}
      87                 :            : 
      88                 :            :         /** Vector of distances TODO better doc*/
      89                 :            :         v_array<ScalarType> dist;
      90                 :            : 
      91                 :            :         /** Point TODO better doc */
      92                 :            :         P p;
      93                 :            : };
      94                 :            : 
      95                 :            : static ScalarType base = COVERTREE_BASE;
      96                 :          4 : static ScalarType il2 = 1. / log(base);
      97                 :            : 
      98                 :       3274 : inline ScalarType dist_of_scale (int s)
      99                 :            : {
     100                 :       3274 :         return pow(base, s);
     101                 :            : }
     102                 :            : 
     103                 :       1324 : inline int get_scale(ScalarType d)
     104                 :            : {
     105                 :       1324 :         return (int)ceil(il2 * log(d));
     106                 :            : }
     107                 :            : 
     108                 :            :         template<class P>
     109                 :        551 : node<P> new_node(const P &p)
     110                 :            : {
     111                 :        551 :         node<P> new_node;
     112                 :        551 :         new_node.p = p;
     113                 :        551 :         return new_node;
     114                 :            : }
     115                 :            : 
     116                 :            :         template<class P>
     117                 :        670 : node<P> new_leaf(const P &p)
     118                 :            : {
     119                 :        670 :         node<P> new_leaf(p,0.,0.,NULL,0,100);
     120                 :        670 :         return new_leaf;
     121                 :            : }
     122                 :            : 
     123                 :            :         template<class P>
     124                 :       1863 : ScalarType max_set(v_array<ds_node<P> > &v)
     125                 :            : {
     126                 :       1863 :         ScalarType max = 0.;
     127 [ +  + ][ +  + ]:      13582 :         for (int i = 0; i < v.index; i++)
     128 [ +  + ][ +  + ]:      11719 :                 if ( max < v[i].dist.last()) 
     129                 :       5859 :                         max = v[i].dist.last();
     130                 :       1863 :         return max;
     131                 :            : }
     132                 :            : 
     133                 :          0 : void print_space(int s)
     134                 :            : {
     135         [ #  # ]:          0 :         for (int i = 0; i < s; i++)
     136                 :          0 :                 printf(" ");
     137                 :          0 : }
     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                 :       1300 : void split(v_array<ds_node<P> >& point_set, v_array<ds_node<P> >& far_set, int max_scale)
     159                 :            : {
     160                 :       1300 :         IndexType new_index = 0;
     161                 :       1300 :         ScalarType fmax = dist_of_scale(max_scale);
     162 [ +  + ][ +  + ]:       8754 :         for (int i = 0; i < point_set.index; i++)
     163                 :            :         {
     164 [ +  + ][ +  + ]:       7454 :                 if (point_set[i].dist.last() <= fmax) 
     165                 :            :                 {
     166                 :       5918 :                         point_set[new_index++] = point_set[i];
     167                 :            :                 }
     168                 :            :                 else
     169                 :       1536 :                         push(far_set,point_set[i]);
     170                 :            :         }
     171                 :       1300 :         point_set.index=new_index;  
     172                 :       1300 : }
     173                 :            : 
     174                 :            : template<class P, class DistanceCallback>
     175                 :       1316 : 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                 :       1316 :         IndexType new_index = 0;
     181                 :       1316 :         ScalarType fmax = dist_of_scale(max_scale);
     182 [ +  + ][ +  + ]:       2593 :         for(int i = 0; i < point_set.index; i++) 
         [ +  + ][ #  # ]
         [ #  # ][ #  # ]
                 [ #  # ]
     183                 :            :         {
     184                 :            :                 ScalarType new_d;
     185                 :       1277 :                 new_d = distance(dcb, new_point, point_set[i].p, fmax);
     186   [ +  +  +  +  :       1277 :                 if (new_d <= fmax ) 
          +  +  #  #  #  
             #  #  #  #  
                      # ]
     187                 :            :                 {
     188                 :        878 :                         push(point_set[i].dist, new_d);
     189                 :        878 :                         push(new_point_set,point_set[i]);
     190                 :            :                 }
     191                 :            :                 else
     192                 :        399 :                         point_set[new_index++] = point_set[i];
     193                 :            :         }
     194                 :       1316 :         point_set.index = new_index;
     195                 :       1316 : }
     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                 :       1970 : 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 [ +  + ][ +  + ]:       1970 :         if (point_set.index == 0) 
         [ +  + ][ #  # ]
         [ #  # ][ #  # ]
                 [ #  # ]
     210                 :        670 :                 return new_leaf(p);
     211                 :            :         else {
     212                 :       1300 :                 ScalarType max_dist = max_set(point_set); //O(|point_set|)
     213                 :       1300 :                 int next_scale = std::min(max_scale - 1, get_scale(max_dist));
     214   [ -  +  -  +  :       1300 :                 if (next_scale == -2147483647-1) // We have points with distance 0.
          -  +  #  #  #  
             #  #  #  #  
                      # ]
     215                 :            :                 {
     216                 :          0 :                         v_array<node<P> > children;
     217                 :          0 :                         push(children,new_leaf(p));
     218 [ #  # ][ #  # ]:          0 :                         while (point_set.index > 0)
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
                 [ #  # ]
     219                 :            :                         {
     220                 :          0 :                                 push(children,new_leaf(point_set.last().p));
     221                 :          0 :                                 push(consumed_set,point_set.last());
     222                 :          0 :                                 point_set.decr();
     223                 :            :                         }
     224                 :          0 :                         node<P> n = new_node(p);
     225                 :          0 :                         n.scale = 100; // A magic number meant to be larger than all scales.  
     226                 :          0 :                         n.max_dist = 0;
     227                 :          0 :                         alloc(children,children.index);
     228                 :          0 :                         n.num_children = children.index;
     229                 :          0 :                         n.children = children.elements;
     230                 :          0 :                         return n;
     231                 :            :                 }
     232                 :            :                 else
     233                 :            :                 {
     234                 :       1300 :                         v_array<ds_node<P> > far = pop(stack);
     235                 :       1300 :                         split(point_set,far,max_scale); //O(|point_set|)
     236                 :            : 
     237                 :       1300 :                         node<P> child = batch_insert(dcb, p, next_scale, top_scale, point_set, consumed_set, stack);
     238                 :            : 
     239   [ +  +  +  +  :       1300 :                         if (point_set.index == 0)
          +  +  #  #  #  
             #  #  #  #  
                      # ]
     240                 :            :                         {
     241                 :        749 :                                 push(stack,point_set);
     242                 :        749 :                                 point_set=far;
     243                 :        749 :                                 return child;
     244                 :            :                         }
     245                 :            :                         else {
     246                 :        551 :                                 node<P> n = new_node(p);
     247                 :        551 :                                 v_array<node<P> > children;
     248                 :        551 :                                 push(children, child);
     249                 :        551 :                                 v_array<ds_node<P> > new_point_set = pop(stack);
     250                 :        551 :                                 v_array<ds_node<P> > new_consumed_set = pop(stack);
     251 [ +  + ][ +  + ]:       1209 :                                 while (point_set.index != 0) { //O(|point_set| * num_children)
         [ +  + ][ #  # ]
         [ #  # ][ #  # ]
                 [ #  # ]
     252                 :        658 :                                         P new_point = point_set.last().p;
     253                 :        658 :                                         ScalarType new_dist = point_set.last().dist.last();
     254                 :        658 :                                         push(consumed_set, point_set.last());
     255                 :        658 :                                         point_set.decr();
     256                 :            : 
     257                 :        658 :                                         dist_split(dcb,point_set,new_point_set,new_point,max_scale); //O(|point_saet|)
     258                 :        658 :                                         dist_split(dcb,far,new_point_set,new_point,max_scale); //O(|far|)
     259                 :            : 
     260                 :            :                                         node<P> new_child = 
     261                 :        658 :                                                 batch_insert(dcb, new_point, next_scale, top_scale, new_point_set, new_consumed_set, stack);
     262                 :        658 :                                         new_child.parent_dist = new_dist;
     263                 :            : 
     264                 :        658 :                                         push(children, new_child);
     265                 :            : 
     266                 :        658 :                                         ScalarType fmax = dist_of_scale(max_scale);
     267 [ +  + ][ +  + ]:        718 :                                         for(int i = 0; i< new_point_set.index; i++) //O(|new_point_set|)
         [ -  + ][ #  # ]
         [ #  # ][ #  # ]
                 [ #  # ]
     268                 :            :                                         {
     269                 :         60 :                                                 new_point_set[i].dist.decr();
     270   [ +  +  +  +  :         60 :                                                 if (new_point_set[i].dist.last() <= fmax)
          #  #  #  #  #  
             #  #  #  #  
                      # ]
     271                 :         19 :                                                         push(point_set, new_point_set[i]);
     272                 :            :                                                 else
     273                 :         41 :                                                         push(far, new_point_set[i]);
     274                 :            :                                         }
     275 [ +  + ][ +  + ]:       1476 :                                         for(int i = 0; i< new_consumed_set.index; i++) //O(|new_point_set|)
         [ +  + ][ #  # ]
         [ #  # ][ #  # ]
                 [ #  # ]
     276                 :            :                                         {
     277                 :        818 :                                                 new_consumed_set[i].dist.decr();
     278                 :        818 :                                                 push(consumed_set, new_consumed_set[i]);
     279                 :            :                                         }
     280                 :        658 :                                         new_point_set.index = 0;
     281                 :        658 :                                         new_consumed_set.index = 0;
     282                 :            :                                 }
     283                 :        551 :                                 push(stack,new_point_set);
     284                 :        551 :                                 push(stack,new_consumed_set);
     285                 :        551 :                                 push(stack,point_set);
     286                 :        551 :                                 point_set=far;
     287                 :        551 :                                 n.scale = top_scale - max_scale;
     288                 :        551 :                                 n.max_dist = max_set(consumed_set);
     289                 :        551 :                                 alloc(children,children.index);
     290                 :        551 :                                 n.num_children = children.index;
     291                 :        551 :                                 n.children = children.elements;
     292                 :       1970 :                                 return n;
     293                 :            :                         }
     294                 :            :                 }
     295                 :            :         }
     296                 :            : }
     297                 :            : 
     298                 :            : template<class P, class DistanceCallback>
     299                 :         12 : node<P> batch_create(DistanceCallback& dcb, v_array<P> points)
     300                 :            : {
     301 [ -  + ][ -  + ]:         12 :         assert(points.index > 0);
         [ -  + ][ #  # ]
         [ #  # ][ #  # ]
                 [ #  # ]
     302                 :         12 :         v_array<ds_node<P> > point_set;
     303                 :         12 :         v_array<v_array<ds_node<P> > > stack;
     304                 :            : 
     305 [ +  + ][ +  + ]:        670 :         for (int i = 1; i < points.index; i++) {
         [ +  + ][ #  # ]
         [ #  # ][ #  # ]
                 [ #  # ]
     306                 :        658 :                 ds_node<P> temp;
     307                 :        658 :                 push(temp.dist, distance(dcb, points[0], points[i], std::numeric_limits<ScalarType>::max()));
     308                 :        658 :                 temp.p = points[i];
     309                 :        658 :                 push(point_set,temp);
     310                 :            :         }
     311                 :            : 
     312                 :         12 :         v_array<ds_node<P> > consumed_set;
     313                 :            : 
     314                 :         12 :         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                 :         12 :                         stack);
     322 [ +  + ][ +  + ]:        670 :         for (int i = 0; i<consumed_set.index;i++)
         [ +  + ][ #  # ]
         [ #  # ][ #  # ]
                 [ #  # ]
     323                 :        658 :                 free(consumed_set[i].dist.elements);
     324                 :         12 :         free(consumed_set.elements);
     325 [ +  + ][ +  + ]:        261 :         for (int i = 0; i<stack.index;i++)
         [ +  + ][ #  # ]
         [ #  # ][ #  # ]
                 [ #  # ]
     326                 :        249 :                 free(stack[i].elements);
     327                 :         12 :         free(stack.elements);
     328                 :         12 :         free(point_set.elements);
     329                 :         12 :         return top;
     330                 :            : }
     331                 :            : 
     332                 :          0 : void add_height(int d, v_array<int> &heights)
     333                 :            : {
     334         [ #  # ]:          0 :         if (heights.index <= d)
     335         [ #  # ]:          0 :                 for(;heights.index <= d;)
     336                 :          0 :                         push(heights,0);
     337                 :          0 :         heights[d] = heights[d] + 1;
     338                 :          0 : }
     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                 :            : 
     386                 :            : /**
     387                 :            :  * List of cover tree nodes associated to a distance TODO better doc
     388                 :            :  */
     389                 :            : template <class P>
     390                 :            : struct d_node 
     391                 :            : {
     392                 :            :         /** Distance TODO better doc*/
     393                 :            :         ScalarType dist;
     394                 :            : 
     395                 :            :         /** List of nodes TODO better doc*/
     396                 :            :         const node<P> *n;
     397                 :            : };
     398                 :            : 
     399                 :            : template <class P>
     400                 :      19588 : inline ScalarType compare(const d_node<P> *p1, const d_node<P>* p2)
     401                 :            : {
     402                 :      19588 :         return p1 -> dist - p2 -> dist;
     403                 :            : }
     404                 :            : 
     405                 :            : template <class P>
     406                 :       4596 : void halfsort (v_array<d_node<P> > cover_set)
     407                 :            : {
     408 [ +  + ][ +  + ]:       4596 :         if (cover_set.index <= 1)
     409                 :       4596 :                 return;
     410                 :       2205 :         register d_node<P> *base_ptr =  cover_set.elements;
     411                 :            : 
     412                 :       2205 :         d_node<P> *hi = &base_ptr[cover_set.index - 1];
     413                 :       2205 :         d_node<P> *right_ptr = hi;
     414                 :            :         d_node<P> *left_ptr;
     415                 :            : 
     416 [ +  + ][ +  + ]:       5715 :         while (right_ptr > base_ptr)
     417                 :            :         {
     418                 :       3510 :                 d_node<P> *mid = base_ptr + ((hi - base_ptr) >> 1);
     419                 :            : 
     420 [ +  + ][ +  + ]:       3510 :                 if (compare ( mid,  base_ptr) < 0.)
     421                 :       1275 :                         std::swap(*mid, *base_ptr);
     422 [ +  + ][ +  + ]:       3510 :                 if (compare ( hi,  mid) < 0.)
     423                 :       1760 :                         std::swap(*mid, *hi);
     424                 :            :                 else
     425                 :       1750 :                         goto jump_over;
     426   [ +  +  +  + ]:       1760 :                 if (compare ( mid,  base_ptr) < 0.)
     427                 :        534 :                         std::swap(*mid, *base_ptr);
     428                 :            : jump_over:;
     429                 :            : 
     430                 :       3510 :                 left_ptr  = base_ptr + 1;
     431                 :       3510 :                 right_ptr = hi - 1;
     432                 :            : 
     433 [ +  + ][ -  + ]:       2950 :                 do
     434                 :            :                 {
     435 [ +  + ][ -  + ]:       5353 :                         while (compare (left_ptr, mid) < 0.)
     436                 :       1112 :                                 left_ptr++;
     437                 :            : 
     438 [ +  + ][ +  + ]:       5455 :                         while (compare (mid, right_ptr) < 0.)
     439                 :       1214 :                                 right_ptr--;
     440                 :            : 
     441 [ +  + ][ +  + ]:       4241 :                         if (left_ptr < right_ptr)
     442                 :            :                         {
     443                 :       1469 :                                 std::swap(*left_ptr, *right_ptr);
     444   [ +  +  +  - ]:       1469 :                                 if (mid == left_ptr)
     445                 :        767 :                                         mid = right_ptr;
     446 [ +  + ][ #  # ]:        702 :                                 else if (mid == right_ptr)
     447                 :        279 :                                         mid = left_ptr;
     448                 :       1469 :                                 left_ptr++;
     449                 :       1469 :                                 right_ptr--;
     450                 :            :                         }
     451 [ +  + ][ +  + ]:       2772 :                         else if (left_ptr == right_ptr)
     452                 :            :                         {
     453                 :       1291 :                                 left_ptr ++;
     454                 :       1291 :                                 right_ptr --;
     455                 :       1291 :                                 break;
     456                 :            :                         }
     457                 :            :                 }
     458                 :            :                 while (left_ptr <= right_ptr);
     459                 :       3510 :                 hi = right_ptr;
     460                 :            :         }
     461                 :            : }
     462                 :            : 
     463                 :            : template <class P>
     464                 :        563 : v_array<v_array<d_node<P> > > get_cover_sets(v_array<v_array<v_array<d_node<P> > > > &spare_cover_sets)
     465                 :            : {
     466                 :        563 :         v_array<v_array<d_node<P> > > ret = pop(spare_cover_sets);
     467 [ +  + ][ +  + ]:       6623 :         while (ret.index < 101)
     468                 :            :         {
     469                 :       6060 :                 v_array<d_node<P> > temp;
     470                 :       6060 :                 push(ret, temp);
     471                 :            :         }
     472                 :        563 :         return ret;
     473                 :            : }
     474                 :            : 
     475                 :      19012 : inline bool shell(ScalarType parent_query_dist, ScalarType child_parent_dist, ScalarType upper_bound)
     476                 :            : {
     477                 :      19012 :         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                 :      13994 : void update_k(ScalarType *k_upper_bound, ScalarType upper_bound)
     483                 :            : {
     484                 :      13994 :         ScalarType *end = k_upper_bound + internal_k-1;
     485                 :      13994 :         ScalarType *begin = k_upper_bound;
     486         [ +  + ]:     101208 :         for (;end != begin; begin++)
     487                 :            :         {
     488         [ +  + ]:      98573 :                 if (upper_bound < *(begin+1))
     489                 :      87214 :                         *begin = *(begin+1);
     490                 :            :                 else {
     491                 :      11359 :                         *begin = upper_bound;
     492                 :      11359 :                         break;
     493                 :            :                 }
     494                 :            :         }
     495         [ +  + ]:      13994 :         if (end == begin)
     496                 :       2635 :                 *begin = upper_bound;
     497                 :      13994 : }
     498                 :        563 : ScalarType *alloc_k()
     499                 :            : {
     500                 :        563 :         return (ScalarType*)malloc(sizeof(ScalarType) * internal_k);
     501                 :            : }
     502                 :        670 : void set_k(ScalarType* begin, ScalarType max)
     503                 :            : {
     504         [ +  + ]:       7940 :         for(ScalarType *end = begin+internal_k;end != begin; begin++)
     505                 :       7270 :                 *begin = max;
     506                 :        670 : }
     507                 :            : 
     508                 :            : ScalarType internal_epsilon =0.;
     509                 :            : //void update_epsilon(ScalarType *upper_bound, ScalarType new_dist) {}
     510                 :          0 : ScalarType *alloc_epsilon()
     511                 :            : {
     512                 :          0 :         return (ScalarType *)malloc(sizeof(ScalarType));
     513                 :            : }
     514                 :          0 : void set_epsilon(ScalarType* begin)
     515                 :            : {
     516                 :          0 :         *begin = internal_epsilon;
     517                 :          0 : }
     518                 :            : 
     519                 :          0 : void update_unequal(ScalarType *upper_bound, ScalarType new_dist) 
     520                 :            : {
     521         [ #  # ]:          0 :         if (new_dist != 0.)
     522                 :          0 :                 *upper_bound = new_dist;
     523                 :          0 : }
     524                 :            : ScalarType* (*alloc_unequal)() = alloc_epsilon;
     525                 :          0 : void set_unequal(ScalarType* begin, ScalarType max)
     526                 :            : {
     527                 :          0 :         *begin = max;
     528                 :          0 : }
     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                 :        658 : 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                 :        658 :         new_zero_set.index = 0;
     540                 :        658 :         d_node<P> *end = zero_set.elements + zero_set.index;
     541 [ +  + ][ +  + ]:       5192 :         for (d_node<P> *ele = zero_set.elements; ele != end ; ele++)
         [ +  + ][ #  # ]
         [ #  # ][ #  # ]
                 [ #  # ]
     542                 :            :         {
     543                 :       4534 :                 ScalarType upper_dist = *new_upper_bound + query_chi->max_dist;
     544 [ +  + ][ +  + ]:       4534 :                 if (shell(ele->dist, query_chi->parent_dist, upper_dist))
         [ +  + ][ #  # ]
         [ #  # ][ #  # ]
                 [ #  # ]
     545                 :            :                 {
     546                 :       3506 :                         ScalarType d = distance(dcb, query_chi->p, ele->n->p, upper_dist);
     547                 :            : 
     548   [ +  +  +  +  :       3506 :                         if (d <= upper_dist)
          +  +  #  #  #  
             #  #  #  #  
                      # ]
     549                 :            :                         {
     550 [ +  + ][ +  + ]:       3044 :                                 if (d < *new_upper_bound) 
         [ +  + ][ #  # ]
         [ #  # ][ #  # ]
                 [ #  # ]
     551                 :       2932 :                                         update(new_upper_bound, d);
     552                 :       3044 :                                 d_node<P> temp = {d, ele->n};
     553                 :       3044 :                                 push(new_zero_set,temp);
     554                 :            :                         }
     555                 :            :                 }
     556                 :            :         }
     557                 :        658 : }
     558                 :            : 
     559                 :            : template <class P, class DistanceCallback>
     560                 :        658 : 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 [ +  + ][ +  + ]:       3430 :         for (; current_scale <= max_scale; current_scale++)
         [ +  + ][ #  # ]
         [ #  # ][ #  # ]
                 [ #  # ]
     567                 :            :         {
     568                 :       2772 :                 d_node<P>* ele = cover_sets[current_scale].elements;
     569                 :       2772 :                 d_node<P>* end = cover_sets[current_scale].elements + cover_sets[current_scale].index;
     570 [ +  + ][ +  + ]:       8277 :                 for (; ele != end; ele++)
         [ +  + ][ #  # ]
         [ #  # ][ #  # ]
                 [ #  # ]
     571                 :            :                 { 
     572                 :       5505 :                         ScalarType upper_dist = *new_upper_bound + query_chi->max_dist + ele->n->max_dist;
     573 [ +  + ][ +  + ]:       5505 :                         if (shell(ele->dist, query_chi->parent_dist, upper_dist))
         [ +  + ][ #  # ]
         [ #  # ][ #  # ]
                 [ #  # ]
     574                 :            :                         {
     575                 :       4712 :                                 ScalarType d = distance(dcb, query_chi->p, ele->n->p, upper_dist);
     576                 :            : 
     577   [ +  +  +  +  :       4712 :                                 if (d <= upper_dist)
          +  +  #  #  #  
             #  #  #  #  
                      # ]
     578                 :            :                                 {
     579 [ +  + ][ +  + ]:       4378 :                                         if (d < *new_upper_bound)
         [ +  + ][ #  # ]
         [ #  # ][ #  # ]
                 [ #  # ]
     580                 :       3995 :                                                 update(new_upper_bound,d);
     581                 :       4378 :                                         d_node<P> temp = {d, ele->n};
     582                 :       4378 :                                         push(new_cover_sets[current_scale],temp);
     583                 :            :                                 }
     584                 :            :                         }
     585                 :            :                 }
     586                 :            :         }
     587                 :        658 : }
     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>
     602                 :            : void print_cover_sets(v_array<v_array<d_node<P> > > &cover_sets,
     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                 :       4596 : 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                 :       4596 :         d_node<P> *end = cover_sets[current_scale].elements + cover_sets[current_scale].index;
     645 [ +  + ][ +  + ]:      15288 :         for (d_node<P> *parent = cover_sets[current_scale].elements; parent != end; parent++)
         [ +  + ][ #  # ]
         [ #  # ][ #  # ]
                 [ #  # ]
     646                 :            :         {
     647                 :      10692 :                 const node<P> *par = parent->n;
     648                 :      10692 :                 ScalarType upper_dist = *upper_bound + query->max_dist + query->max_dist;
     649 [ +  + ][ +  + ]:      10692 :                 if (parent->dist <= upper_dist + par->max_dist)
         [ +  + ][ #  # ]
         [ #  # ][ #  # ]
                 [ #  # ]
     650                 :            :                 {
     651                 :       7445 :                         node<P> *chi = par->children;
     652 [ +  + ][ +  + ]:       7445 :                         if (parent->dist <= upper_dist + chi->max_dist)
         [ +  + ][ #  # ]
         [ #  # ][ #  # ]
                 [ #  # ]
     653                 :            :                         {
     654 [ +  + ][ +  + ]:       6837 :                                 if (chi->num_children > 0)
         [ +  + ][ #  # ]
         [ #  # ][ #  # ]
                 [ #  # ]
     655                 :            :                                 {
     656 [ +  + ][ +  + ]:       3727 :                                         if (max_scale < chi->scale)
         [ +  + ][ #  # ]
         [ #  # ][ #  # ]
                 [ #  # ]
     657                 :        242 :                                                 max_scale = chi->scale;
     658                 :       3727 :                                         d_node<P> temp = {parent->dist, chi};
     659                 :       3727 :                                         push(cover_sets[chi->scale], temp);
     660                 :            :                                 }
     661 [ +  - ][ +  - ]:       3110 :                                 else if (parent->dist <= upper_dist)
         [ +  - ][ #  # ]
         [ #  # ][ #  # ]
                 [ #  # ]
     662                 :            :                                 {
     663                 :       3110 :                                         d_node<P> temp = {parent->dist, chi};
     664                 :       3110 :                                         push(zero_set, temp);
     665                 :            :                                 }
     666                 :            :                         }
     667                 :       7445 :                         node<P> *child_end = par->children + par->num_children;
     668 [ +  + ][ +  + ]:      16418 :                         for (chi++; chi != child_end; chi++)
         [ +  + ][ #  # ]
         [ #  # ][ #  # ]
                 [ #  # ]
     669                 :            :                         {
     670                 :       8973 :                                 ScalarType upper_chi = *upper_bound + chi->max_dist + query->max_dist + query->max_dist;
     671 [ +  + ][ +  + ]:       8973 :                                 if (shell(parent->dist, chi->parent_dist, upper_chi))
         [ +  - ][ #  # ]
         [ #  # ][ #  # ]
                 [ #  # ]
     672                 :            :                                 {
     673                 :       8961 :                                         ScalarType d = distance(dcb, query->p, chi->p, upper_chi);
     674   [ +  +  +  +  :       8961 :                                         if (d <= upper_chi) 
          +  +  #  #  #  
             #  #  #  #  
                      # ]
     675                 :            :                                         {
     676 [ +  + ][ +  + ]:       7795 :                                                 if (d < *upper_bound)
         [ +  + ][ #  # ]
         [ #  # ][ #  # ]
                 [ #  # ]
     677                 :       7055 :                                                         update(upper_bound, d);
     678 [ +  + ][ +  + ]:       7795 :                                                 if (chi->num_children > 0)
         [ +  + ][ #  # ]
         [ #  # ][ #  # ]
                 [ #  # ]
     679                 :            :                                                 {
     680 [ +  + ][ +  + ]:       2575 :                                                         if (max_scale < chi->scale)
         [ +  + ][ #  # ]
         [ #  # ][ #  # ]
                 [ #  # ]
     681                 :        432 :                                                                 max_scale = chi->scale;
     682                 :       2575 :                                                         d_node<P> temp = {d, chi};
     683                 :       2575 :                                                         push(cover_sets[chi->scale],temp);
     684                 :            :                                                 }
     685                 :            :                                                 else 
     686 [ +  - ][ +  - ]:       5220 :                                                         if (d <= upper_chi - chi->max_dist)
         [ +  - ][ #  # ]
         [ #  # ][ #  # ]
                 [ #  # ]
     687                 :            :                                                         {
     688                 :       5220 :                                                                 d_node<P> temp = {d, chi};
     689                 :       5220 :                                                                 push(zero_set, temp);
     690                 :            :                                                         }
     691                 :            :                                         }
     692                 :            :                                 }
     693                 :            :                         }
     694                 :            :                 }
     695                 :            :         }
     696                 :       4596 : }
     697                 :            : 
     698                 :            : template <class P, class DistanceCallback>
     699                 :        670 : 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 [ -  + ][ -  + ]:        670 :         if (query->num_children > 0)
         [ -  + ][ #  # ]
         [ #  # ][ #  # ]
                 [ #  # ]
     705                 :            :         {
     706                 :          0 :                 v_array<d_node<P> > new_zero_set = pop(spare_zero_sets);
     707                 :          0 :                 node<P> * query_chi = query->children; 
     708                 :          0 :                 brute_nearest(dcb, query_chi, zero_set, upper_bound, results, spare_zero_sets);
     709                 :          0 :                 ScalarType* new_upper_bound = alloc_upper();
     710                 :            : 
     711                 :          0 :                 node<P> *child_end = query->children + query->num_children;
     712 [ #  # ][ #  # ]:          0 :                 for (query_chi++;query_chi != child_end; query_chi++)
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
                 [ #  # ]
     713                 :            :                 {
     714                 :          0 :                         setter(new_upper_bound,*upper_bound + query_chi->parent_dist);
     715                 :          0 :                         copy_zero_set(dcb, query_chi, new_upper_bound, zero_set, new_zero_set);
     716                 :          0 :                         brute_nearest(dcb, query_chi, new_zero_set, new_upper_bound, results, spare_zero_sets);
     717                 :            :                 }
     718                 :          0 :                 free (new_upper_bound);
     719                 :          0 :                 new_zero_set.index = 0;
     720                 :          0 :                 push(spare_zero_sets, new_zero_set);
     721                 :            :         }
     722                 :            :         else 
     723                 :            :         {
     724                 :        670 :                 v_array<P> temp;
     725                 :        670 :                 push(temp, query->p);
     726                 :        670 :                 d_node<P> *end = zero_set.elements + zero_set.index;
     727 [ +  + ][ +  + ]:      12044 :                 for (d_node<P> *ele = zero_set.elements; ele != end ; ele++)
         [ +  + ][ #  # ]
         [ #  # ][ #  # ]
                 [ #  # ]
     728 [ +  + ][ +  + ]:      11374 :                         if (ele->dist <= *upper_bound) 
         [ +  + ][ #  # ]
         [ #  # ][ #  # ]
                 [ #  # ]
     729                 :       7284 :                                 push(temp, ele->n->p);
     730                 :        670 :                 push(results,temp);
     731                 :            :         }
     732                 :        670 : }
     733                 :            : 
     734                 :            : template <class P, class DistanceCallback>
     735                 :       5817 : 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 [ +  + ][ +  + ]:       5817 :         if (current_scale > max_scale) // All remaining points are in the zero set. 
         [ +  + ][ #  # ]
         [ #  # ][ #  # ]
                 [ #  # ]
     746                 :        670 :                 brute_nearest(dcb, query, zero_set, upper_bound, results, spare_zero_sets);
     747                 :            :         else
     748 [ +  + ][ +  - ]:       5147 :                 if (query->scale <= current_scale && query->scale != 100) 
         [ +  + ][ +  - ]
         [ +  + ][ +  - ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
     749                 :            :                         // Our query has too much scale.  Reduce.
     750                 :            :                 { 
     751                 :        551 :                         node<P> *query_chi = query->children;
     752                 :        551 :                         v_array<d_node<P> > new_zero_set = pop(spare_zero_sets);
     753                 :        551 :                         v_array<v_array<d_node<P> > > new_cover_sets = get_cover_sets(spare_cover_sets);
     754                 :        551 :                         ScalarType* new_upper_bound = alloc_upper();
     755                 :            : 
     756                 :        551 :                         node<P> *child_end = query->children + query->num_children;
     757 [ +  + ][ +  + ]:       1209 :                         for (query_chi++; query_chi != child_end; query_chi++)
         [ +  + ][ #  # ]
         [ #  # ][ #  # ]
                 [ #  # ]
     758                 :            :                         {
     759                 :        658 :                                 setter(new_upper_bound,*upper_bound + query_chi->parent_dist);
     760                 :        658 :                                 copy_zero_set(dcb, query_chi, new_upper_bound, zero_set, new_zero_set);
     761                 :        658 :                                 copy_cover_sets(dcb, query_chi, new_upper_bound, cover_sets, new_cover_sets,
     762                 :            :                                                 current_scale, max_scale);
     763                 :        658 :                                 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                 :        551 :                         free (new_upper_bound);
     768                 :        551 :                         new_zero_set.index = 0;
     769                 :        551 :                         push(spare_zero_sets, new_zero_set);
     770                 :        551 :                         push(spare_cover_sets, new_cover_sets);
     771                 :        551 :                         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                 :       4596 :                         halfsort(cover_sets[current_scale]);
     778                 :       4596 :                         descend(dcb, query, upper_bound, current_scale, max_scale,cover_sets, zero_set);
     779                 :       4596 :                         cover_sets[current_scale++].index = 0;
     780                 :       4596 :                         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                 :       5817 : }
     785                 :            : 
     786                 :            : template <class P, class DistanceCallback>
     787                 :         12 : void batch_nearest_neighbor(DistanceCallback &dcb, const node<P> &top_node,
     788                 :            :                 const node<P> &query, v_array<v_array<P> > &results)
     789                 :            : {
     790                 :         12 :         v_array<v_array<v_array<d_node<P> > > > spare_cover_sets;
     791                 :         12 :         v_array<v_array<d_node<P> > > spare_zero_sets;
     792                 :            : 
     793                 :         12 :         v_array<v_array<d_node<P> > > cover_sets = get_cover_sets(spare_cover_sets);
     794                 :         12 :         v_array<d_node<P> > zero_set = pop(spare_zero_sets);
     795                 :            : 
     796                 :         12 :         ScalarType* upper_bound = alloc_upper();
     797                 :         12 :         setter(upper_bound, std::numeric_limits<ScalarType>::max());
     798                 :            : 
     799                 :         12 :         ScalarType top_dist = distance(dcb, query.p, top_node.p, std::numeric_limits<ScalarType>::max());
     800                 :         12 :         update(upper_bound, top_dist);
     801                 :            : 
     802                 :         12 :         d_node<P> temp = {top_dist, &top_node};
     803                 :         12 :         push(cover_sets[0], temp);
     804                 :            : 
     805                 :         12 :         internal_batch_nearest_neighbor(dcb, &query,cover_sets,zero_set,0,0,upper_bound,results,
     806                 :            :                         spare_cover_sets,spare_zero_sets);
     807                 :            : 
     808                 :         12 :         free(upper_bound);
     809                 :         12 :         push(spare_cover_sets, cover_sets);
     810                 :            : 
     811 [ +  + ][ +  + ]:         72 :         for (int i = 0; i < spare_cover_sets.index; i++)
         [ +  + ][ #  # ]
         [ #  # ][ #  # ]
                 [ #  # ]
     812                 :            :         {
     813                 :         60 :                 v_array<v_array<d_node<P> > > cover_sets2 = spare_cover_sets[i];
     814 [ +  + ][ +  + ]:       6120 :                 for (int j = 0; j < cover_sets2.index; j++)
         [ +  + ][ #  # ]
         [ #  # ][ #  # ]
                 [ #  # ]
     815                 :       6060 :                         free (cover_sets2[j].elements);
     816                 :         60 :                 free(cover_sets2.elements);
     817                 :            :         }
     818                 :         12 :         free(spare_cover_sets.elements);
     819                 :            : 
     820                 :         12 :         push(spare_zero_sets, zero_set);
     821                 :            : 
     822 [ +  + ][ +  + ]:         72 :         for (int i = 0; i < spare_zero_sets.index; i++)
         [ +  + ][ #  # ]
         [ #  # ][ #  # ]
                 [ #  # ]
     823                 :         60 :                 free(spare_zero_sets[i].elements);
     824                 :         12 :         free(spare_zero_sets.elements);
     825                 :         12 : }
     826                 :            : 
     827                 :            : template <class P, class DistanceCallback>
     828                 :         12 : 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                 :         12 :         internal_k = k;
     832                 :         12 :         update = update_k;
     833                 :         12 :         setter = set_k;
     834                 :         12 :         alloc_upper = alloc_k;
     835                 :            : 
     836                 :         12 :         batch_nearest_neighbor(dcb, top_node, query, results);
     837                 :         12 : }
     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

Generated by: LCOV version 1.9