if(pi!=E2_nn_seed){/*80:*/#line 1811 "./kdtree.w"{const doublediff_x= E2_nn_seed_x-coord[pi].x[0],diff_y= E2_nn_seed_y-coord[pi].x[1];/*113:*/#line 2434 "./kdtree.w"#if KD_ALLOW_VERBOSEif(verbose>=1500){printf(" pi=%d qmask=%d x0=%.0f y0=%.0f x1=%.0f y1=%.0f dx=%.0f dy=%.0f q=%d mask=%d\n",pi,quadrant_mask,E2_nn_seed_x,E2_nn_seed_y,coord[pi].x[0],coord[pi].x[1],diff_x,diff_y,E2_quadrant(diff_x,diff_y),E2_quadrant_mask(diff_x,diff_y));}#endif/*:113*/#line 1816 "./kdtree.w"if(quadrant_mask&E2_quadrant_mask(diff_x,diff_y)){const double dist_sq= diff_x*diff_x+diff_y*diff_y;/*110:*/#line 2397 "./kdtree.w"#if 1 if(verbose>=2000){printf("  city %5d (%7.0f,%7.0f) is dist %10.3f\n",pi,coord[pi].x[0],coord[pi].x[1],sqrt(dist_sq));}#endif/*:110*/#line 1820 "./kdtree.w"if(dist_sq<E2_nn_dist_sq){/*111:*/#line 2407 "./kdtree.w"#if KD_ALLOW_VERBOSEif(verbose>=1000){printf("    new champion\n");}#endif/*:111*/#line 1822 "./kdtree.w"/*83:*/#line 1860 "./kdtree.w"if(E2_nn_fill_bin){kd_bin_t*pi_particulars;if(pq_size(E2_nn_bin)==E2_nn_bin_want_size){pi_particulars= pq_delete_min(E2_nn_bin);}else{pi_particulars= E2_nn_bin_work+pq_size(E2_nn_bin);}pi_particulars->cost_squared= dist_sq;pi_particulars->city= pi;pq_insert(E2_nn_bin,pi_particulars);if(pq_size(E2_nn_bin)==E2_nn_bin_want_size){E2_nn_dist_sq= ((kd_bin_t*)pq_min(E2_nn_bin))->cost_squared;E2_nn_dist= sqrt(E2_nn_dist_sq);}}else{E2_nn_dist= sqrt(dist_sq);E2_nn_dist_sq= dist_sq;E2_nn_incumbent= pi;}/*:83*/#line 1823 "./kdtree.w"}}}/*:80*/#line 2167 "./kdtree.w"}}}/*:97*/#line 2091 "./kdtree.w"do{/*98:*/#line 2185 "./kdtree.w"{E2_box_t*b= node->bbox;if(b&&(b->xmin<=E2_nn_seed_x-E2_nn_dist)&&(b->xmax>=E2_nn_seed_x+E2_nn_dist)&&(b->ymin<=E2_nn_seed_y-E2_nn_dist)&&(b->ymax>=E2_nn_seed_y+E2_nn_dist)){/*112:*/#line 2415 "./kdtree.w"#if KD_ALLOW_VERBOSEif(verbose>=500){printf("     rnn break: seed=(%0.0f,%0.0f) dist=%f\n",E2_nn_seed_x,E2_nn_seed_y,E2_nn_dist);printf("     seedbb=(%0.0f,%0.0f,%0.0f,%0.0f) bb=(%0.0f,%0.0f,%0.0f,%0.0f)\n",E2_nn_seed_x-E2_nn_dist,E2_nn_seed_y-E2_nn_dist,E2_nn_seed_x+E2_nn_dist,E2_nn_seed_y+E2_nn_dist,b->xmin,b->ymin,b->xmax,b->ymax);}#endif/*:112*/#line 2192 "./kdtree.w"break;}}/*:98*/#line 2093 "./kdtree.w"/*99:*/#line 2205 "./kdtree.w"#if !defined(KD_NO_HIDDEN_BIT)#define recurse_if_not_last_or_hidden(P) ((P)==last||(E2_rnn(P),42))#else#define recurse_if_not_last_or_hidden(P) ((P)==last||(P)->hidden||(E2_rnn(P),42))#endif{E2_node_t*last;for(last= node,node= node->parent;node;last= node,node= node->parent){E2_node_t*l= node->f.i.lo_child,*e= node->f.i.eq_child,*h= node->f.i.hi_child;if((node->f.i.cutdimen==0&&E2_nn_seed_x<node->f.i.cutvalue)||(node->f.i.cutdimen==1&&E2_nn_seed_y<node->f.i.cutvalue)){recurse_if_not_last_or_hidden(l);recurse_if_not_last_or_hidden(e);recurse_if_not_last_or_hidden(h);}else{recurse_if_not_last_or_hidden(h);recurse_if_not_last_or_hidden(e);recurse_if_not_last_or_hidden(l);}/*98:*/#line 2185 "./kdtree.w"{E2_box_t*b= node->bbox;if(b&&(b->xmin<=E2_nn_seed_x-E2_nn_dist)&&(b->xmax>=E2_nn_seed_x+E2_nn_dist)&&(b->ymin<=E2_nn_seed_y-E2_nn_dist)&&(b->ymax>=E2_nn_seed_y+E2_nn_dist)){/*112:*/#line 2415 "./kdtree.w"#if KD_ALLOW_VERBOSEif(verbose>=500){printf("     rnn break: seed=(%0.0f,%0.0f) dist=%f\n",E2_nn_seed_x,E2_nn_seed_y,E2_nn_dist);printf("     seedbb=(%0.0f,%0.0f,%0.0f,%0.0f) bb=(%0.0f,%0.0f,%0.0f,%0.0f)\n",E2_nn_seed_x-E2_nn_dist,E2_nn_seed_y-E2_nn_dist,E2_nn_seed_x+E2_nn_dist,E2_nn_seed_y+E2_nn_dist,b->xmin,b->ymin,b->xmax,b->ymax);}#endif/*:112*/#line 2192 "./kdtree.w"break;}}/*:98*/#line 2226 "./kdtree.w"}}/*:99*/#line 2094 "./kdtree.w"}while(0);/*:92*/#line 2061 "./kdtree.w"return E2_nn_incumbent;}/*:89*//*93:*/#line 2107 "./kdtree.w"intE2_nn_bulk_func(int c,int num_wanted,kd_bin_t*buffer){return E2_nn_quadrant_bulk(c,num_wanted,buffer,0x1f);}intE2_nn_quadrant_bulk(int c,int num_wanted,kd_bin_t*buffer,const int mask){int num_found;E2_node_t*node= E2_point_to_bucket[c];/*91:*/#line 2077 "./kdtree.w"quadrant_mask= mask;E2_nn_seed= c;E2_nn_seed_x= coord[c].x[0];E2_nn_seed_y= coord[c].x[1];E2_nn_incumbent= -1;if(mask&(~1)){E2_nn_dist= E2_nn_dist_sq= E2_strict_upper_bound;}else{E2_nn_dist= E2_nn_dist_sq= 1e-5;}/*:91*/#line 2118 "./kdtree.w"E2_nn_fill_bin= 1;E2_nn_bin_want_size= num_wanted;E2_nn_bin_work= buffer;/*92:*/#line 2090 "./kdtree.w"/*97:*/#line 2161 "./kdtree.w"{int i,hi= node->f.e.hi;for(i= node->f.e.lo;i<hi;i++){int pi= perm[i];if(pi!=E2_nn_seed){/*80:*/#line 1811 "./kdtree.w"{const doublediff_x= E2_nn_seed_x-coord[pi].x[0],diff_y= E2_nn_seed_y-coord[pi].x[1];/*113:*/#line 2434 "./kdtree.w"#if KD_ALLOW_VERBOSEif(verbose>=1500){printf(" pi=%d qmask=%d x0=%.0f y0=%.0f x1=%.0f y1=%.0f dx=%.0f dy=%.0f q=%d mask=%d\n",pi,quadrant_mask,E2_nn_seed_x,E2_nn_seed_y,coord[pi].x[0],coord[pi].x[1],diff_x,diff_y,E2_quadrant(diff_x,diff_y),E2_quadrant_mask(diff_x,diff_y));}#endif/*:113*/#line 1816 "./kdtree.w"if(quadrant_mask&E2_quadrant_mask(diff_x,diff_y)){const double dist_sq= diff_x*diff_x+diff_y*diff_y;/*110:*/#line 2397 "./kdtree.w"#if 1 if(verbose>=2000){printf("  city %5d (%7.0f,%7.0f) is dist %10.3f\n",pi,coord[pi].x[0],coord[pi].x[1],sqrt(dist_sq));}#endif/*:110*/#line 1820 "./kdtree.w"if(dist_sq<E2_nn_dist_sq){/*111:*/#line 2407 "./kdtree.w"#if KD_ALLOW_VERBOSEif(verbose>=1000){printf("    new champion\n");}#endif/*:111*/#line 1822 "./kdtree.w"/*83:*/#line 1860 "./kdtree.w"if(E2_nn_fill_bin){kd_bin_t*pi_particulars;if(pq_size(E2_nn_bin)==E2_nn_bin_want_size){pi_particulars= pq_delete_min(E2_nn_bin);}else{pi_particulars= E2_nn_bin_work+pq_size(E2_nn_bin);}pi_particulars->cost_squared= dist_sq;pi_particulars->city= pi;pq_insert(E2_nn_bin,pi_particulars);if(pq_size(E2_nn_bin)==E2_nn_bin_want_size){E2_nn_dist_sq= ((kd_bin_t*)pq_min(E2_nn_bin))->cost_squared;E2_nn_dist= sqrt(E2_nn_dist_sq);}}else{E2_nn_dist= sqrt(dist_sq);E2_nn_dist_sq= dist_sq;E2_nn_incumbent= pi;}/*:83*/#line 1823 "./kdtree.w"}}}/*:80*/#line 2167 "./kdtree.w"}}}/*:97*/#line 2091 "./kdtree.w"do{/*98:*/#line 2185 "./kdtree.w"{E2_box_t*b= node->bbox;if(b&&(b->xmin<=E2_nn_seed_x-E2_nn_dist)&&(b->xmax>=E2_nn_seed_x+E2_nn_dist)&&(b->ymin<=E2_nn_seed_y-E2_nn_dist)&&(b->ymax>=E2_nn_seed_y+E2_nn_dist)){/*112:*/#line 2415 "./kdtree.w"#if KD_ALLOW_VERBOSEif(verbose>=500){printf("     rnn break: seed=(%0.0f,%0.0f) dist=%f\n",E2_nn_seed_x,E2_nn_seed_y,E2_nn_dist);printf("     seedbb=(%0.0f,%0.0f,%0.0f,%0.0f) bb=(%0.0f,%0.0f,%0.0f,%0.0f)\n",E2_nn_seed_x-E2_nn_dist,E2_nn_seed_y-E2_nn_dist,E2_nn_seed_x+E2_nn_dist,E2_nn_seed_y+E2_nn_dist,b->xmin,b->ymin,b->xmax,b->ymax);}#endif/*:112*/#line 2192 "./kdtree.w"break;}}/*:98*/#line 2093 "./kdtree.w"/*99:*/#line 2205 "./kdtree.w"#if !defined(KD_NO_HIDDEN_BIT)#define recurse_if_not_last_or_hidden(P) ((P)==last||(E2_rnn(P),42))#else#define recurse_if_not_last_or_hidden(P) ((P)==last||(P)->hidden||(E2_rnn(P),42))#endif{E2_node_t*last;for(last= node,node= node->parent;node;last= node,node= node->parent){E2_node_t*l= node->f.i.lo_child,*e= node->f.i.eq_child,*h= node->f.i.hi_child;if((node->f.i.cutdimen==0&&E2_nn_seed_x<node->f.i.cutvalue)||(node->f.i.cutdimen==1&&E2_nn_seed_y<node->f.i.cutvalue)){recurse_if_not_last_or_hidden(l);recurse_if_not_last_or_hidden(e);recurse_if_not_last_or_hidden(h);}else{recurse_if_not_last_or_hidden(h);recurse_if_not_last_or_hidden(e);recurse_if_not_last_or_hidden(l);}/*98:*/#line 2185 "./kdtree.w"{E2_box_t*b= node->bbox;if(b&&(b->xmin<=E2_nn_seed_x-E2_nn_dist)&&(b->xmax>=E2_nn_seed_x+E2_nn_dist)&&(b->ymin<=E2_nn_seed_y-E2_nn_dist)&&(b->ymax>=E2_nn_seed_y+E2_nn_dist)){/*112:*/#line 2415 "./kdtree.w"#if KD_ALLOW_VERBOSEif(verbose>=500){printf("     rnn break: seed=(%0.0f,%0.0f) dist=%f\n",E2_nn_seed_x,E2_nn_seed_y,E2_nn_dist);printf("     seedbb=(%0.0f,%0.0f,%0.0f,%0.0f) bb=(%0.0f,%0.0f,%0.0f,%0.0f)\n",E2_nn_seed_x-E2_nn_dist,E2_nn_seed_y-E2_nn_dist,E2_nn_seed_x+E2_nn_dist,E2_nn_seed_y+E2_nn_dist,b->xmin,b->ymin,b->xmax,b->ymax);}#endif/*:112*/#line 2192 "./kdtree.w"break;}}/*:98*/#line 2226 "./kdtree.w"}}/*:99*/#line 2094 "./kdtree.w"}while(0);/*:92*/#line 2122 "./kdtree.w"num_found= pq_size(E2_nn_bin);pq_make_empty(E2_nn_bin);return num_found;}/*:93*//*102:*/#line 2259 "./kdtree.w"voidE2_frnn(int c,double rad,void(*proc)(int j)){errorif(1,"Fixed radius nearest neighbour not implemented");}void E2_set_radius(int i,double r){errorif(1,"Ball searching not implemented");}void E2_ball_search(int i,void(*proc)(int j)){errorif(1,"Ball searching not implemented");}/*:102*//*105:*/#line 2307 "./kdtree.w"extern tsp_instance_t*tsp_instance;static voidE2_postscript_show_helper(FILE*ps_out,int level,E2_node_t*node,double xmin,double xmax,double ymin,double ymax){if(!node->is_bucket){double cv= node->f.i.cutvalue;fprintf(ps_out,"%%cutdimen == %d\n",node->f.i.cutdimen);switch(node->f.i.cutdimen){case 0:fprintf(ps_out,"newpath %f x %f y moveto %f x %f y lineto stroke\n",cv,ymin,cv,ymax);/*107:*/#line 2367 "./kdtree.w"verb(1000){int i;for(i= 0;i<level;i++)printf(" ");}/*:107*/#line 2320 "./kdtree.w"verb(1000)printf("= in x = %f\n",cv);E2_postscript_show_helper(ps_out,level+1,node->f.i.eq_child,cv,cv,ymin,ymax);/*107:*/#line 2367 "./kdtree.w"verb(1000){int i;for(i= 0;i<level;i++)printf(" ");}/*:107*/#line 2322 "./kdtree.w"verb(1000)printf("< in x < %f\n",cv);E2_postscript_show_helper(ps_out,level+1,node->f.i.lo_child,xmin,cv,ymin,ymax);/*107:*/#line 2367 "./kdtree.w"verb(1000){int i;for(i= 0;i<level;i++)printf(" ");}/*:107*/#line 2324 "./kdtree.w"verb(1000)printf("> in x > %f\n",cv);E2_postscript_show_helper(ps_out,level+1,node->f.i.hi_child,cv,xmax,ymin,ymax);break;case 1:fprintf(ps_out,"newpath %f x %f y moveto %f x %f y lineto stroke\n",xmin,cv,xmax,cv);/*107:*/#line 2367 "./kdtree.w"verb(1000){int i;for(i= 0;i<level;i++)printf(" ");}/*:107*/#line 2330 "./kdtree.w"verb(1000)printf("= in y = %f\n",cv);E2_postscript_show_helper(ps_out,level+1,node->f.i.eq_child,xmin,xmax,cv,cv);/*107:*/#line 2367 "./kdtree.w"verb(1000){int i;for(i= 0;i<level;i++)printf(" ");}/*:107*/#line 2332 "./kdtree.w"verb(1000)printf("< in y < %f\n",cv);E2_postscript_show_helper(ps_out,level+1,node->f.i.lo_child,xmin,xmax,ymin,cv);/*107:*/#line 2367 "./kdtree.w"verb(1000){int i;for(i= 0;i<level;i++)printf(" ");}/*:107*/#line 2334 "./kdtree.w"verb(1000)printf("> in y > %f\n",cv);E2_postscript_show_helper(ps_out,level+1,node->f.i.hi_child,xmin,xmax,cv,ymax);break;}}else{int i;/*107:*/#line 2367 "./kdtree.w"verb(1000){int i;for(i= 0;i<level;i++)printf(" ");}/*:107*/#line 2340 "./kdtree.w"for(i= node->f.e.lo;i<node->f.e.hi_all;i++){verb(1000)printf("%d ",perm[i]);}verb(1000)printf("\n");}}voidE2_postscript_show(FILE*ps_out){#if defined(KD_SHOW_KDTREE)fprintf(ps_out,"gsave 0 setlinewidth\n");E2_postscript_show_helper(ps_out,0,E2_root,tsp_instance->xmin,tsp_instance->xmax,tsp_instance->ymin,tsp_instance->ymax);fprintf(ps_out,"grestore\n");fflush(ps_out);fprintf(stderr,"Printed stuff to ps_out\n");#elsereturn;#endif}/*:105*/#line 364 "./kdtree.w"const char*kdtree_rcs_id= "$Id: kdtree.w,v 1.165 1998/10/10 19:25:16 neto Exp neto $";/*:1*/