#define max(A,B) ((A) >(B) ?(A) :(B) )  \/*5:*/#line 214 "./nn.w"#include <config.h>#include "lkconfig.h"/*6:*/#line 230 "./nn.w"#include <stdio.h>#include <stdlib.h>#include <stddef.h>/*:6*/#line 217 "./nn.w"/*12:*/#line 277 "./nn.w"#include "length.h"/*:12*//*24:*/#line 407 "./nn.w"#include "read.h"#include "lk.h"/*:24*//*36:*/#line 531 "./nn.w"#include "kdtree.h"/*:36*/#line 218 "./nn.w"/*8:*/#line 245 "./nn.w"#include "nn.h"/*:8*//*17:*/#line 324 "./nn.w"#include "error.h"#include "memory.h"/*:17*//*40:*/#line 573 "./nn.w"#include "dsort.h"/*:40*/#line 219 "./nn.w"/*9:*/#line 249 "./nn.w"int nn_max_bound;/*:9*/#line 221 "./nn.w"/*11:*/#line 268 "./nn.w"typedef struct{length_t len;int city;}nn_entry_t;/*:11*/#line 222 "./nn.w"/*15:*/#line 311 "./nn.w"static int*list,*begin,n;/*:15*//*28:*/#line 442 "./nn.w"static int list_size;/*:28*/#line 223 "./nn.w"/*13:*/#line 295 "./nn.w"int*nn_list(int city,int*list_len){*list_len= begin[city+1]-begin[city];return list+begin[city];}/*:13*//*18:*/#line 329 "./nn.w"voidnn_cleanup(void){/*19:*/#line 336 "./nn.w"if(begin){free_mem(begin);mem_deduct(sizeof(int)*(n+1));}/*:19*//*27:*/#line 436 "./nn.w"if(list){free_mem(begin);mem_deduct(sizeof(int)*list_size);}/*:27*/#line 332 "./nn.w"}/*:18*//*21:*/#line 361 "./nn.w"voidnn_build(int num_pure,int num_quadrant,int num_delauney){/*31:*/#line 458 "./nn.w"kd_bin_t*work;/*:31*/#line 365 "./nn.w"int i;n= tsp_instance->n;/*23:*/#line 393 "./nn.w"/*50:*/#line 687 "./nn.w"if(verbose>=500){printf("nn: build nn %d nq %d del %d\n",num_pure,num_quadrant,num_delauney);fflush(stdout);}/*:50*/#line 394 "./nn.w"errorif(num_pure<0,"Need positive number of nearest neighbours; %d specified",num_pure);errorif(num_quadrant<0,"Need positive number of quadrant neighbours; %d specified",num_quadrant);errorif(num_delauney<0,"Need positive Delauney depth; %d specified",num_delauney);errorif(num_pure<=0&&num_quadrant<=0&&num_delauney<=0,"Must specify some candidates");errorif(num_pure>=n,"%d nearest neighbours specified, but there are only %d cities",num_pure,n);/*:23*//*41:*/#line 583 "./nn.w"errorif(num_quadrant>0&&!E2_supports(tsp_instance),"Quadrant lists supported only when 2-d trees supported",num_pure);/*:41*//*47:*/#line 671 "./nn.w"errorif(num_delauney,"Delauney neighbours not supported (yet)");/*:47*/#line 368 "./nn.w"/*16:*/#line 317 "./nn.w"begin= new_arr_of(int,n+1);begin[0]= 0;/*:16*//*26:*/#line 428 "./nn.w"{int guess_avg;/*25:*/#line 417 "./nn.w"if(num_pure)guess_avg= num_pure+num_quadrant+num_delauney;else if(num_quadrant)guess_avg= 4*num_quadrant+num_delauney;elseguess_avg= 3*num_delauney*num_delauney;/*:25*/#line 430 "./nn.w"list_size= guess_avg*n;list= new_arr_of(int,list_size);}/*:26*//*29:*/#line 449 "./nn.w"work= new_arr_of(kd_bin_t,3*n);/*:29*/#line 370 "./nn.w"nn_max_bound= 0;for(i= 0;i<n;i++){/*33:*/#line 486 "./nn.w"int work_next= 0;/*:33*/#line 373 "./nn.w"/*52:*/#line 702 "./nn.w"if(verbose>=1250){printf("nn: about to build for %d; work_next=%d list_size=%d\n",i,work_next,list_size);fflush(stdout);}/*:52*/#line 374 "./nn.w"/*35:*/#line 519 "./nn.w"if(num_pure){int start_work= work_next;if(E2_supports(tsp_instance)){/*37:*/#line 540 "./nn.w"work_next+= E2_nn_bulk(i,num_pure,work+work_next);/*:37*/#line 523 "./nn.w"}else{/*38:*/#line 546 "./nn.w"{int j;for(j= 0;j<i;j++){kd_bin_city(&work[start_work+j])= j;kd_bin_monotonic_len(&work[start_work+j])= cost(i,j);}for(j= i+1;j<n;j++){kd_bin_city(&work[start_work+j-1])= j;kd_bin_monotonic_len(&work[start_work+j-1])= cost(i,j);}}/*:38*/#line 525 "./nn.w"/*39:*/#line 567 "./nn.w"select_range((void*)work,(size_t)n-1,sizeof(kd_bin_t),kd_bin_cmp_increasing,0,num_pure,0);work_next+= num_pure;/*:39*/#line 526 "./nn.w"}}/*:35*/#line 375 "./nn.w"/*42:*/#line 604 "./nn.w"if(num_quadrant){int quadrant;int q_count[5]= {0,0,0,0,0};/*43:*/#line 632 "./nn.w"{int j;coord_2d*coord= tsp_instance->coord;for(j= 0;j<work_next;j++){const double diff_x= coord[i].x[0]-coord[j].x[0];const double diff_y= coord[i].x[1]-coord[j].x[1];q_count[E2_quadrant(diff_x,diff_y)]++;}}/*:43*/#line 608 "./nn.w"if(0==q_count[1]+q_count[2]+q_count[3]+q_count[4]){/*45:*/#line 659 "./nn.w"{const int num_quadrant= n-1,quadrant= 0;/*44:*/#line 649 "./nn.w"work_next+= E2_nn_quadrant_bulk(i,num_quadrant,work+work_next,1<<quadrant);/*:44*/#line 661 "./nn.w"}/*:45*/#line 610 "./nn.w"}for(quadrant= 1;quadrant<=4;quadrant++){if(q_count[quadrant]<num_quadrant){/*44:*/#line 649 "./nn.w"work_next+= E2_nn_quadrant_bulk(i,num_quadrant,work+work_next,1<<quadrant);/*:44*/#line 614 "./nn.w"}}}/*:42*/#line 376 "./nn.w"/*48:*/#line 675 "./nn.w"/*:48*/#line 377 "./nn.w"/*32:*/#line 471 "./nn.w"errorif(work_next<1,"Must have nonempty candidate list");{int r,w,last_city;sort(work,(size_t)work_next,sizeof(kd_bin_t),kd_bin_cmp_increasing);for(r= w= 0,last_city= kd_bin_city(&work[r])-1;r<work_next;r++){if(kd_bin_city(&work[r])!=last_city)last_city= kd_bin_city(&work[w++])= kd_bin_city(&work[r]);}/*34:*/#line 499 "./nn.w"if(begin[i]+w>list_size){int new_size= list_size;while(begin[i]+w>new_size)new_size*= 2;/*49:*/#line 679 "./nn.w"if(verbose>=750){printf("nn: Resize list from %d elements to %d elements; begin[i]=%d, w=%d\n",list_size,new_size,begin[i],w);fflush(stdout);}/*:49*/#line 503 "./nn.w"list= mem_realloc(list,sizeof(int)*new_size);mem_deduct(sizeof(int)*list_size);list_size= new_size;}/*:34*/#line 480 "./nn.w"for(r= 0;r<w;r++)list[begin[i]+r]= kd_bin_city(&work[r]);begin[i+1]= begin[i]+w;}/*:32*/#line 378 "./nn.w"nn_max_bound= max(nn_max_bound,begin[i+1]-begin[i]);}/*30:*/#line 454 "./nn.w"free_mem(work);mem_deduct(sizeof(kd_bin_t)*3*n);/*:30*/#line 381 "./nn.w"/*51:*/#line 694 "./nn.w"if(verbose>=75){printf("nn: build nn %d nq %d del %d got %d total neighbours\n",num_pure,num_quadrant,num_delauney,begin[n]);fflush(stdout);}/*:51*/#line 382 "./nn.w"}/*:21*/#line 224 "./nn.w"const char*nn_rcs_id= "$Id: nn.w,v 1.134 1998/10/10 19:27:39 neto Exp neto $";/*:5*/