#define new_box() ((E2_box_t*) pool_alloc(box_pool) ) #define free_box(P) pool_free(box_pool,(P) )  \ \#define new_node() ((E2_node_t*) (pool_alloc(node_pool) ) ) #define free_node(P) pool_free(node_pool,(P) )  \#define val(a) (coord[perm[(a) ]].x[cutdimen]) #define valx(a) (coord[perm[(a) ]].x[0]) #define valy(a) (coord[perm[(a) ]].x[1]) #define med3(a,b,c) (val(a) <val(b) ?(val(b) <val(c) ?b:val(a) <val(c) ?(c) :(a) )  \:(val(b) >val(c) ?b:val(a) >val(c) ?(c) :(a) ) )  \#define swapint(J,K) {int t= J;J= K;K= t;} \ \#define min(x,y) ((x) <(y) ?(x) :(y) ) #define max(x,y) ((x) >(y) ?(x) :(y) ) #define verb(a) if(verbose>=(a) ) /*1:*/#line 352 "./kdtree.w"#include <config.h>#include "lkconfig.h"/*30:*/#line 919 "./kdtree.w"#include <stddef.h>#include <stdio.h>#include <stdlib.h>#include "fixincludes.h"/*:30*//*59:*/#line 1453 "./kdtree.w"#include <stdio.h>/*:59*//*82:*/#line 1838 "./kdtree.w"#include <math.h>/*:82*/#line 355 "./kdtree.w"/*7:*/#line 524 "./kdtree.w"#include "length.h"#include "read.h"/*:7*/#line 356 "./kdtree.w"/*3:*/#line 382 "./kdtree.w"#include "kdtree.h"/*:3*//*17:*/#line 737 "./kdtree.w"#include "pool.h"/*:17*//*28:*/#line 897 "./kdtree.w"#include "error.h"#include "memory.h"/*:28*//*72:*/#line 1704 "./kdtree.w"#include "pq.h"/*:72*//*104:*/#line 2300 "./kdtree.w"#include "error.h"#include "memory.h"/*:104*/#line 357 "./kdtree.w"/*15:*/#line 718 "./kdtree.w"typedef struct{double xmin,xmax,ymin,ymax;}E2_box_t;/*:15*/#line 359 "./kdtree.w"/*8:*/#line 555 "./kdtree.w"typedef struct E2_node_s{/*12:*/#line 651 "./kdtree.w"struct E2_node_s*parent;/*:12*//*14:*/#line 714 "./kdtree.w"E2_box_t*bbox;/*:14*/#line 557 "./kdtree.w"union{struct{int cutdimen;double cutvalue;struct E2_node_s*lo_child,*hi_child;/*21:*/#line 816 "./kdtree.w"struct E2_node_s*eq_child;/*:21*/#line 563 "./kdtree.w"}i;struct{int lo,hi;/*54:*/#line 1376 "./kdtree.w"int hi_all;/*:54*/#line 567 "./kdtree.w"}e;}f;char is_bucket;/*13:*/#line 660 "./kdtree.w"#if !defined(KD_NO_HIDDEN_BIT)char hidden;#endif/*:13*/#line 571 "./kdtree.w"}E2_node_t;/*:8*/#line 360 "./kdtree.w"/*25:*/#line 877 "./kdtree.w"static pool_t*node_pool,*box_pool;/*:25*//*27:*/#line 893 "./kdtree.w"static int n;/*:27*//*32:*/#line 962 "./kdtree.w"static E2_node_t*E2_root;static coord_2d*coord;/*:32*//*36:*/#line 1046 "./kdtree.w"static E2_node_t**E2_point_to_bucket;/*:36*//*70:*/#line 1661 "./kdtree.w"static int quadrant_mask;/*:70*//*71:*/#line 1697 "./kdtree.w"static int E2_nn_seed,E2_nn_incumbent,E2_nn_bin_want_size;static double E2_nn_dist,E2_nn_dist_sq,E2_nn_seed_x,E2_nn_seed_y;static pq_t*E2_nn_bin;static kd_bin_t*E2_nn_bin_work= NULL;/*:71*//*84:*/#line 1882 "./kdtree.w"static int E2_nn_fill_bin= 0;/*:84*//*96:*/#line 2155 "./kdtree.w"static double E2_strict_upper_bound;/*:96*//*109:*/#line 2393 "./kdtree.w"extern int verbose;/*:109*/#line 361 "./kdtree.w"/*9:*/#line 589 "./kdtree.w"int*perm;/*:9*//*10:*/#line 613 "./kdtree.w"int kd_bucket_cutoff= 10;/*:10*//*18:*/#line 747 "./kdtree.w"int kd_bbox_skip= 3;/*:18*/#line 362 "./kdtree.w"/*33:*/#line 986 "./kdtree.w"static E2_node_t*E2_build_helper(E2_node_t*parent,int flat_dimens,int level,int lo,int hi,double xmin,double xmax,double ymin,double ymax){E2_node_t*node= new_node();node->parent= parent;#if !defined(KD_NO_HIDDEN_BIT)node->hidden= lo>=hi;#endifif((++level%kd_bbox_skip)==0){node->bbox= new_box();node->bbox->xmin= xmin;node->bbox->xmax= xmax;node->bbox->ymin= ymin;node->bbox->ymax= ymax;/*108:*/#line 2371 "./kdtree.w"#ifdef KD_CHECK_BBOXverb(1000)printf("lo %d hi %d\n",lo,hi);if(lo<hi){double xl,xh,yl,yh;int i;xl= xmax;xh= xmin;yl= ymax;yh= ymin;for(i= lo;i<hi;i++){verb(1000)printf("xl %f i %d perm[i] %d %f %f xl\n",xl,i,perm[i],coord[perm[i]].x[0],coord[perm[i]].x[1]);xl= min(xl,valx(i));yl= min(yl,valy(i));xh= max(xh,valx(i));yh= max(yh,valy(i));}errorif(xl!=xmin,"xl %f!= xmin %f",xl,xmin);errorif(yl!=ymin,"yl %f!= ymin %f",yl,ymin);errorif(xh!=xmax,"xh %f!= xmax %f",xh,xmax);errorif(yh!=ymax,"yh %f!= ymax %f",yh,ymax);}#endif/*:108*/#line 1002 "./kdtree.w"}else{node->bbox= NULL;}if(hi-lo<=kd_bucket_cutoff||flat_dimens==0x03){node->is_bucket= 1;node->f.e.lo= lo;node->f.e.hi= hi;/*55:*/#line 1380 "./kdtree.w"node->f.e.hi_all= hi;/*:55*/#line 1010 "./kdtree.w"/*35:*/#line 1040 "./kdtree.w"{int i;for(i= lo;i<hi;i++)E2_point_to_bucket[perm[i]]= node;}/*:35*/#line 1011 "./kdtree.w"}else{node->is_bucket= 0;/*39:*/#line 1069 "./kdtree.w"{int cutdimen= 0;switch(flat_dimens){case 0:if(xmax-xmin>ymax-ymin)cutdimen= 0;else cutdimen= 1;break;case 1:cutdimen= 1;break;case 2:cutdimen= 0;break;case 3:default:errorif(1,"Invalid flat_dimens: %d",flat_dimens);}/*40:*/#line 1092 "./kdtree.w"{int p;int a,b,c,d;double exl,exh,lxl,lxh,gxl,gxh;double eyl,eyh,lyl,lyh,gyl,gyh;/*41:*/#line 1140 "./kdtree.w"p= (lo+hi)/2;if(hi-lo>7){int p1= lo,pn= hi-1;if(hi-lo>40){int s= (hi-lo)/8;p1= med3(p1,p1+s,p1+s+s);p= med3(p-s,p,p+s);pn= med3(pn-s-s,pn-s,pn);}p= med3(p1,p,pn);}/*:41*/#line 1097 "./kdtree.w"/*42:*/#line 1172 "./kdtree.w"/*43:*/#line 1210 "./kdtree.w"exl= lxl= gxl= xmax;exh= lxh= gxh= xmin;eyl= lyl= gyl= ymax;eyh= lyh= gyh= ymin;/*:43*/#line 1173 "./kdtree.w"a= b= lo;c= d= hi-1;{double v= val(p),diff;node->f.i.cutdimen= cutdimen;node->f.i.cutvalue= v;for(;;){while(b<=c&&(diff= val(b)-v)<=0.0){if(diff==0.0){/*44:*/#line 1219 "./kdtree.w"exl= min(exl,valx(b));exh= max(exh,valx(b));eyl= min(eyl,valy(b));eyh= max(eyh,valy(b));/*:44*/#line 1181 "./kdtree.w"swapint(perm[a],perm[b]);a++;}else{/*45:*/#line 1226 "./kdtree.w"lxl= min(lxl,valx(b));lxh= max(lxh,valx(b));lyl= min(lyl,valy(b));lyh= max(lyh,valy(b));/*:45*/#line 1185 "./kdtree.w"}b++;}while(c>=b&&(diff= val(c)-v)>=0.0){if(diff==0.0){/*46:*/#line 1233 "./kdtree.w"exl= min(exl,valx(c));exh= max(exh,valx(c));eyl= min(eyl,valy(c));eyh= max(eyh,valy(c));/*:46*/#line 1191 "./kdtree.w"swapint(perm[d],perm[c]);d--;}else{/*47:*/#line 1240 "./kdtree.w"gxl= min(gxl,valx(c));gxh= max(gxh,valx(c));gyl= min(gyl,valy(c));gyh= max(gyh,valy(c));/*:47*/#line 1195 "./kdtree.w"}c--;}if(b>c)break;swapint(perm[b],perm[c]);/*45:*/#line 1226 "./kdtree.w"lxl= min(lxl,valx(b));lxh= max(lxh,valx(b));lyl= min(lyl,valy(b));lyh= max(lyh,valy(b));/*:45*/#line 1201 "./kdtree.w"/*47:*/#line 1240 "./kdtree.w"gxl= min(gxl,valx(c));gxh= max(gxh,valx(c));gyl= min(gyl,valy(c));gyh= max(gyh,valy(c));/*:47*/#line 1202 "./kdtree.w"b++;c--;}/*48:*/#line 1247 "./kdtree.w"{int s,l,h;s= min(a-lo,b-a);for(l= lo,h= b-s;s;s--){swapint(perm[l],perm[h]);l++;h++;}s= min(d-c,hi-1-d);for(l= b,h= hi-s;s;s--){swapint(perm[l],perm[h]);l++;h++;}}/*:48*/#line 1205 "./kdtree.w"}/*103:*/#line 2276 "./kdtree.w"#ifdef KD_CHECK_PARTITIONING{int i;double v= node->f.i.cutvalue;verb(1000)printf("\nDimension %d\n",cutdimen);for(i= lo;i<hi;i++){if(i==lo)verb(1000)printf("Checking lesser: %d %d\n",lo,lo+b-a);if(i==lo+b-a)verb(1000)printf("Checking equal: %d %d\n",lo+b-a,hi-(d-c));if(i==hi-(d-c))verb(1000)printf("Checking greater: %d %d\n",hi-(d-c),hi);verb(1000)printf("%d (%.0f,%.0f)\t %.0f %.0f\n",i,valx(i),valy(i),val(i),v);fflush(stdout);}for(i= lo;i<lo+b-a;i++){errorif(val(i)>=v,"Not lesser at %d",i);}for(i= lo+b-a;i<hi-(d-c);i++){errorif(val(i)!=v,"Not equal at %d",i);}for(i= hi-(d-c);i<hi;i++){errorif(val(i)<=v,"Not greater at %d",i);}}#endif/*:103*/#line 1207 "./kdtree.w"/*:42*/#line 1098 "./kdtree.w"/*49:*/#line 1316 "./kdtree.w"#if defined(KD_BUILD_SMALLEST_SEGMENT_FIRST){int l= b-a,m= hi-(d-c)-lo+b-a,h= d-c;if(l<=m){if(m<=h){/*50:*/#line 1343 "./kdtree.w"node->f.i.lo_child= E2_build_helper(node,flat_dimens,level,lo,lo+b-a,lxl,lxh,lyl,lyh);/*:50*/#line 1320 "./kdtree.w"/*52:*/#line 1357 "./kdtree.w"node->f.i.eq_child= E2_build_helper(node,flat_dimens|(cutdimen+1),level,lo+b-a,hi-(d-c),exl,exh,eyl,eyh);/*:52*/#line 1320 "./kdtree.w"/*51:*/#line 1347 "./kdtree.w"node->f.i.hi_child= E2_build_helper(node,flat_dimens,level,hi-(d-c),hi,gxl,gxh,gyl,gyh);/*:51*/#line 1321 "./kdtree.w"}else if(l<=h){/*50:*/#line 1343 "./kdtree.w"node->f.i.lo_child= E2_build_helper(node,flat_dimens,level,lo,lo+b-a,lxl,lxh,lyl,lyh);/*:50*/#line 1322 "./kdtree.w"/*51:*/#line 1347 "./kdtree.w"node->f.i.hi_child= E2_build_helper(node,flat_dimens,level,hi-(d-c),hi,gxl,gxh,gyl,gyh);/*:51*/#line 1322 "./kdtree.w"/*52:*/#line 1357 "./kdtree.w"node->f.i.eq_child= E2_build_helper(node,flat_dimens|(cutdimen+1),level,lo+b-a,hi-(d-c),exl,exh,eyl,eyh);/*:52*/#line 1322 "./kdtree.w"}else{/*51:*/#line 1347 "./kdtree.w"node->f.i.hi_child= E2_build_helper(node,flat_dimens,level,hi-(d-c),hi,gxl,gxh,gyl,gyh);/*:51*/#line 1323 "./kdtree.w"/*50:*/#line 1343 "./kdtree.w"node->f.i.lo_child= E2_build_helper(node,flat_dimens,level,lo,lo+b-a,lxl,lxh,lyl,lyh);/*:50*/#line 1323 "./kdtree.w"/*52:*/#line 1357 "./kdtree.w"node->f.i.eq_child= E2_build_helper(node,flat_dimens|(cutdimen+1),level,lo+b-a,hi-(d-c),exl,exh,eyl,eyh);/*:52*/#line 1323 "./kdtree.w"}}else{if(l<=h){/*52:*/#line 1357 "./kdtree.w"node->f.i.eq_child= E2_build_helper(node,flat_dimens|(cutdimen+1),level,lo+b-a,hi-(d-c),exl,exh,eyl,eyh);/*:52*/#line 1325 "./kdtree.w"/*50:*/#line 1343 "./kdtree.w"