node->f.i.lo_child= E2_build_helper(node,flat_dimens,level,lo,lo+b-a,lxl,lxh,lyl,lyh);/*:50*/#line 1325 "./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 1325 "./kdtree.w"}else if(m<=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 1326 "./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 1326 "./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 1326 "./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 1327 "./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 1327 "./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 1327 "./kdtree.w"}}}#else/*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 1331 "./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 1332 "./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 1333 "./kdtree.w"#endif/*:49*/#line 1099 "./kdtree.w"}/*:40*/#line 1086 "./kdtree.w"}/*:39*/#line 1014 "./kdtree.w"}return node;}/*:33*//*66:*/#line 1569 "./kdtree.w"static voidE2_hide_all_helper(E2_node_t*p){#if !defined(KD_NO_HIDDEN_BIT)p->hidden= 1;#endifif(p->is_bucket)p->f.e.hi= p->f.e.lo;else{#if !defined(KD_NO_HIDDEN_BIT)if(!p->f.i.lo_child->hidden)E2_hide_all_helper(p->f.i.lo_child);if(!p->f.i.eq_child->hidden)E2_hide_all_helper(p->f.i.eq_child);if(!p->f.i.hi_child->hidden)E2_hide_all_helper(p->f.i.hi_child);#elseE2_hide_all_helper(p->f.i.lo_child);E2_hide_all_helper(p->f.i.eq_child);E2_hide_all_helper(p->f.i.hi_child);#endif}}/*:66*//*68:*/#line 1604 "./kdtree.w"static voidE2_unhide_all_helper(E2_node_t*p){if(p->is_bucket){p->f.e.hi= p->f.e.hi_all;#if !defined(KD_NO_HIDDEN_BIT)p->hidden= p->f.e.lo>=p->f.e.hi;#endif}else{#if !defined(KD_NO_HIDDEN_BIT)p->hidden= 0;#endifE2_unhide_all_helper(p->f.i.lo_child);E2_unhide_all_helper(p->f.i.eq_child);E2_unhide_all_helper(p->f.i.hi_child);}}/*:68*//*78:*/#line 1760 "./kdtree.w"static voidE2_rnn(E2_node_t*p){if(p->is_bucket){/*79:*/#line 1774 "./kdtree.w"{int i,hi= p->f.e.hi;for(i= p->f.e.lo;i<hi;i++){int pi= perm[i];/*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 1778 "./kdtree.w"}}/*:79*/#line 1765 "./kdtree.w"}else{/*88:*/#line 1995 "./kdtree.w"#if !defined(KD_NO_HIDDEN_BIT) && !defined(KD_NO_HIDDEN_RNN_TEST)#define recurse_if_not_hidden(P) ((P)->hidden || (E2_rnn(P),42))#else#define recurse_if_not_hidden(P) (E2_rnn(P),42)#endif{const int cutdimen= p->f.i.cutdimen;const double seed_coord= cutdimen==0?E2_nn_seed_x:E2_nn_seed_y,diff= seed_coord-p->f.i.cutvalue;if(diff<0){recurse_if_not_hidden(p->f.i.lo_child);if(E2_nn_dist>=-diff&&((cutdimen?0x12:0x06)&quadrant_mask)){recurse_if_not_hidden(p->f.i.eq_child);recurse_if_not_hidden(p->f.i.hi_child);}}else if(diff>0){recurse_if_not_hidden(p->f.i.hi_child);if(E2_nn_dist>=diff&&((cutdimen?0x0c:0x18)&quadrant_mask)){recurse_if_not_hidden(p->f.i.eq_child);recurse_if_not_hidden(p->f.i.lo_child);}}else{recurse_if_not_hidden(p->f.i.eq_child);recurse_if_not_hidden(p->f.i.lo_child);recurse_if_not_hidden(p->f.i.hi_child);}}/*:88*/#line 1767 "./kdtree.w"}}/*:78*/#line 363 "./kdtree.w"/*6:*/#line 507 "./kdtree.w"intE2_supports(tsp_instance_t*tsp){switch(tsp->edge_weight_type){case EUC_2D:case CEIL_2D:case ATT:return 1;default:return 0;}}/*:6*//*23:*/#line 847 "./kdtree.w"voidE2_create(tsp_instance_t*tsp){errorif(!E2_supports(tsp),"2-d trees may not be used for this instance");/*24:*/#line 872 "./kdtree.w"node_pool= pool_create(sizeof(E2_node_t),500);box_pool= pool_create(sizeof(E2_box_t),500);/*:24*//*26:*/#line 887 "./kdtree.w"n= tsp->n;perm= new_arr_of(int,n);{int i;for(i= 0;i<n;i++)perm[i]= i;}/*:26*//*37:*/#line 1050 "./kdtree.w"E2_point_to_bucket= new_arr_of(E2_node_t*,n);/*:37*//*75:*/#line 1723 "./kdtree.w"E2_nn_bin= pq_create(kd_bin_cmp_decreasing);/*:75*/#line 852 "./kdtree.w"/*31:*/#line 953 "./kdtree.w"coord= tsp->coord;errorif(n<=0,"Need at least one point; instance has %d points",n);E2_root= E2_build_helper(NULL,0,0,0,n,tsp->xmin,tsp->xmax,tsp->ymin,tsp->ymax);/*:31*//*95:*/#line 2149 "./kdtree.w"{double xrange= tsp->xmax-tsp->xmin,yrange= tsp->ymax-tsp->ymin;E2_strict_upper_bound= 2.0*(xrange*xrange+yrange*yrange)+1.0;}/*:95*/#line 853 "./kdtree.w"}/*:23*//*29:*/#line 904 "./kdtree.w"voidE2_destroy(void){pool_destroy(node_pool);pool_destroy(box_pool);box_pool= node_pool= NULL;free_mem(perm);/*38:*/#line 1054 "./kdtree.w"free_mem(E2_point_to_bucket);/*:38*//*77:*/#line 1754 "./kdtree.w"pq_destroy(E2_nn_bin);/*:77*/#line 911 "./kdtree.w"}/*:29*//*56:*/#line 1386 "./kdtree.w"voidE2_hide(int c){int ci;E2_node_t*node;errorif(c<0||c>=n,"Invalid city %d to hide",c);node= E2_point_to_bucket[c];/*57:*/#line 1421 "./kdtree.w"{int hi_all= node->f.e.hi_all;for(ci= node->f.e.lo;ci<hi_all;ci++){if(perm[ci]==c)break;}errorif(ci==hi_all,"Point %d not found in its bucket",c);}/*:57*/#line 1393 "./kdtree.w"/*58:*/#line 1441 "./kdtree.w"{int t,hi= node->f.e.hi;if(ci<hi){hi= --node->f.e.hi;t= perm[ci];perm[ci]= perm[hi];perm[hi]= t;}else{fprintf(stderr,"Hiding hidden city %d at perm[%d]\n",c,ci);}}/*:58*/#line 1394 "./kdtree.w"/*60:*/#line 1470 "./kdtree.w"#if !defined(KD_NO_HIDDEN_BIT)if(node->f.e.lo==node->f.e.hi&&!node->hidden){do{node->hidden= 1;node= node->parent;}while(node&&!node->hidden&&node->f.i.lo_child->hidden&&node->f.i.eq_child->hidden&&node->f.i.hi_child->hidden);}#endif/*:60*/#line 1395 "./kdtree.w"}/*:56*//*61:*/#line 1491 "./kdtree.w"voidE2_unhide(int c){int ci;E2_node_t*node= E2_point_to_bucket[c];/*57:*/#line 1421 "./kdtree.w"{int hi_all= node->f.e.hi_all;for(ci= node->f.e.lo;ci<hi_all;ci++){if(perm[ci]==c)break;}errorif(ci==hi_all,"Point %d not found in its bucket",c);}/*:57*/#line 1496 "./kdtree.w"/*62:*/#line 1507 "./kdtree.w"{int t,hi= node->f.e.hi;if(ci>=hi){t= perm[ci];perm[ci]= perm[hi];perm[hi]= t;node->f.e.hi++;}else{fprintf(stderr,"Unhiding unhidden city %d at perm[%d]\n",c,ci);}}/*:62*/#line 1497 "./kdtree.w"/*63:*/#line 1525 "./kdtree.w"#if !defined(KD_NO_HIDDEN_BIT)while(node&&node->hidden){node->hidden= 0;node= node->parent;}#endif/*:63*/#line 1498 "./kdtree.w"}/*:61*//*65:*/#line 1542 "./kdtree.w"voidE2_hide_all(void){#if !defined(KD_NO_HIDDEN_BIT)if(E2_root&&!E2_root->hidden)E2_hide_all_helper(E2_root);#elseif(E2_root)E2_hide_all_helper(E2_root);#endif}/*:65*//*67:*/#line 1594 "./kdtree.w"voidE2_unhide_all(void){if(E2_root)E2_unhide_all_helper(E2_root);}/*:67*//*76:*/#line 1730 "./kdtree.w"intkd_bin_cmp_increasing(const void*a,const void*b){double da= ((const kd_bin_t*)a)->cost_squared;double db= ((const kd_bin_t*)b)->cost_squared;if(da>db)return 1;if(da<db)return-1;return((const kd_bin_t*)a)->city-((const kd_bin_t*)b)->city;}intkd_bin_cmp_decreasing(const void*a,const void*b){double da= ((const kd_bin_t*)a)->cost_squared;double db= ((const kd_bin_t*)b)->cost_squared;if(da<db)return 1;if(da>db)return-1;return((const kd_bin_t*)a)->city-((const kd_bin_t*)b)->city;}/*:76*//*89:*/#line 2052 "./kdtree.w"int E2_nn_func(int c){return E2_nn_quadrant(c,0x1f);}intE2_nn_quadrant(int c,const int mask){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 2059 "./kdtree.w"E2_nn_fill_bin= 0;/*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];