t[two_i+2]= e_entry->t2ip2;swap_mates(t[1],t[two_i],t[two_i+1],t[two_i+2]);two_i+= 2;/*74:*/#line 1398 "./match.w"#if MATCH_REPORT_DEPTHSif(two_i> probe_depth_less_2)probe_depth_less_2= two_i;#endif/*:74*/#line 1268 "./match.w"/*98:*/#line 1697 "./match.w"#if MATCH_MAX_VERBOSE >= 125if(verbose> 125){int i;printf("\n");for(i= 0;i<two_i;i++)putchar(' ');printf("+");fflush(stdout);}#endif/*:98*/#line 1269 "./match.w"/*101:*/#line 1731 "./match.w"#if MATCH_MAX_VERBOSE >= 150if(verbose>=150){int i;printf("t:");for(i= 1;i<=two_i;i++)printf(" %d",t[i]);printf("\n");fflush(stdout);}#endif/*:101*/#line 1270 "./match.w"/*:68*/#line 1038 "./match.w"}else if(best_two_i){keep_going= 0;}else{/*69:*/#line 1276 "./match.w"if(two_i> 2){if(two_i<=2*backtracking_levels){ei[two_i]= -2;en[two_i]= -1;}two_i-= 2;/*97:*/#line 1685 "./match.w"#if MATCH_MAX_VERBOSE >= 125if(verbose> 125){int i;printf("\n");for(i= 0;i<two_i;i++)putchar(' ');printf("-");fflush(stdout);}#endif/*:97*/#line 1283 "./match.w"swap_mates(t[1],t[two_i+2],t[two_i+1],t[two_i]);/*101:*/#line 1731 "./match.w"#if MATCH_MAX_VERBOSE >= 150if(verbose>=150){int i;printf("t:");for(i= 1;i<=two_i;i++)printf(" %d",t[i]);printf("\n");fflush(stdout);}#endif/*:101*/#line 1285 "./match.w"}else keep_going= 0;/*:69*/#line 1040 "./match.w"}}else{/*112:*/#line 1848 "./match.w"#if MATCH_MAX_VERBOSE >= 109if(verbose>=109){printf("G");}#endif/*:112*/#line 1042 "./match.w"/*70:*/#line 1300 "./match.w"{int none_eligible= 1;if(two_i<=max_two_i){/*72:*/#line 1328 "./match.w"{eligible_t best_move;int j,num_candidates,*candidates= nn_list(t[two_i],&num_candidates);for(j= 0;j<num_candidates;j++){const int t2ip1= candidates[j],t2ip2= mate[t2ip1];eligible_t trial_move,*e_entry= &trial_move;/*61:*/#line 1122 "./match.w"{int j,tabu= 0;if(t2ip2==t[two_i]){/*104:*/#line 1772 "./match.w"#if MATCH_MAX_VERBOSE >= 500if(verbose>=500){printf("X");fflush(stdout);}#endif/*:104*/#line 1125 "./match.w"continue;}for(j= 2;j<two_i;j+= 2){if((t2ip1==t[j]&&t2ip2==t[j+1])||(t2ip1==t[j+1]&&t2ip2==t[j])){tabu= 1;break;}}if(tabu){/*104:*/#line 1772 "./match.w"#if MATCH_MAX_VERBOSE >= 500if(verbose>=500){printf("X");fflush(stdout);}#endif/*:104*/#line 1130 "./match.w"continue;}}/*:61*/#line 1335 "./match.w"/*62:*/#line 1138 "./match.w"{const length_t this_neg= cost(t[two_i],t2ip1),this_pos= cost(t2ip1,t2ip2),this_net= this_pos-this_neg;e_entry->t2ip1= t2ip1;e_entry->t2ip2= t2ip2;#if SPLIT_GAIN_VARe_entry->gain_1_neg= cum_gain_neg+this_neg;e_entry->gain_1_pos= cum_gain_pos;e_entry->gain_neg= cum_gain_neg+this_neg;e_entry->gain_pos= cum_gain_pos+this_pos;#elsee_entry->gain_1= cum_gain-this_neg;e_entry->gain= cum_gain+this_net;#endif#if USE_DECLUSTERe_entry->cluster_distance= decluster_d(t[1],t2ip2);e_entry->gain_for_comparison= this_net-e_entry->cluster_distance;#elsee_entry->gain_for_comparison= this_net;#endife_entry->two_i= two_i;}/*:62*/#line 1336 "./match.w"/*64:*/#line 1172 "./match.w"{const length_t cluster_dist= (USE_DECLUSTER?e_entry->cluster_distance:0);if(CAREFUL_OP(e_entry->gain,<=,cluster_dist+best_gain)||CAREFUL_OP(e_entry->gain_1,<=,best_gain)){/*105:*/#line 1781 "./match.w"#if MATCH_MAX_VERBOSE >= 500if(verbose>=500){printf("<");fflush(stdout);}#endif/*:105*/#line 1177 "./match.w"continue;}}/*:64*/#line 1337 "./match.w"/*65:*/#line 1195 "./match.w"{#if SPLIT_GAIN_VARconst length_t possible_best_gain_pos= e_entry->gain_pos,possible_best_gain_neg= e_entry->gain_neg+cost(t[1],e_entry->t2ip2);#elseconst length_t possible_best_gain= e_entry->gain-cost(t[1],e_entry->t2ip2);#endifif(CAREFUL_OP(possible_best_gain,> ,best_gain)){best_two_i= two_i;best_exit_a= t2ip1;best_exit_b= t2ip2;#if SPLIT_GAIN_VARbest_gain= possible_best_gain_pos-possible_best_gain_neg;#elsebest_gain= possible_best_gain;#endif#if !LENGTH_TYPE_IS_EXACTbest_gain_with_slop= best_gain+instance_epsilon;#endif/*99:*/#line 1710 "./match.w"#if MATCH_MAX_VERBOSE >= 125if(verbose>=125){printf(" verbose %d ===two_i %d best_two_i %d best_exit_a %d best_exit_b %d\n",verbose,two_i,best_two_i,best_exit_a,best_exit_b);fflush(stdout);}#endif/*:99*/#line 1216 "./match.w"}}/*:65*/#line 1338 "./match.w"/*106:*/#line 1790 "./match.w"#if MATCH_MAX_VERBOSE >= 500show_entry_with_string_at_verbose(e_entry,"accept",500);#endif/*:106*/#line 1339 "./match.w"if(none_eligible||best_move.gain_for_comparison<trial_move.gain_for_comparison){none_eligible= 0;best_move= trial_move;/*107:*/#line 1796 "./match.w"#if MATCH_MAX_VERBOSE >= 500show_entry_with_string_at_verbose(e_entry,"best move",500);#endif/*:107*/#line 1343 "./match.w"}}if(!none_eligible){eligible_t*e_entry= &best_move;/*68:*/#line 1252 "./match.w"/*108:*/#line 1803 "./match.w"#if MATCH_MAX_VERBOSE >= 500show_entry_with_string_at_verbose(e_entry,"doing move",500);#endif/*:108*/#line 1253 "./match.w"#if SPLIT_GAIN_VARcum_gain_pos= e_entry->gain_pos;cum_gain_neg= e_entry->gain_neg;#elsecum_gain= e_entry->gain;#endif#if defined(MATCH_DEBUG)if(e_entry->two_i!=two_i)dump_core(96);#endift[two_i+1]= e_entry->t2ip1;t[two_i+2]= e_entry->t2ip2;swap_mates(t[1],t[two_i],t[two_i+1],t[two_i+2]);two_i+= 2;/*74:*/#line 1398 "./match.w"#if MATCH_REPORT_DEPTHSif(two_i> probe_depth_less_2)probe_depth_less_2= two_i;#endif/*:74*/#line 1268 "./match.w"/*98:*/#line 1697 "./match.w"#if MATCH_MAX_VERBOSE >= 125if(verbose> 125){int i;printf("\n");for(i= 0;i<two_i;i++)putchar(' ');printf("+");fflush(stdout);}#endif/*:98*/#line 1269 "./match.w"/*101:*/#line 1731 "./match.w"#if MATCH_MAX_VERBOSE >= 150if(verbose>=150){int i;printf("t:");for(i= 1;i<=two_i;i++)printf(" %d",t[i]);printf("\n");fflush(stdout);}#endif/*:101*/#line 1270 "./match.w"/*:68*/#line 1347 "./match.w"}}/*:72*/#line 1303 "./match.w"}if(none_eligible){if(best_two_i==0)while(two_i> 2*backtracking_levels){/*69:*/#line 1276 "./match.w"if(two_i> 2){if(two_i<=2*backtracking_levels){ei[two_i]= -2;en[two_i]= -1;}two_i-= 2;/*97:*/#line 1685 "./match.w"#if MATCH_MAX_VERBOSE >= 125if(verbose> 125){int i;printf("\n");for(i= 0;i<two_i;i++)putchar(' ');printf("-");fflush(stdout);}#endif/*:97*/#line 1283 "./match.w"swap_mates(t[1],t[two_i+2],t[two_i+1],t[two_i]);/*101:*/#line 1731 "./match.w"#if MATCH_MAX_VERBOSE >= 150if(verbose>=150){int i;printf("t:");for(i= 1;i<=two_i;i++)printf(" %d",t[i]);printf("\n");fflush(stdout);}#endif/*:101*/#line 1285 "./match.w"}else keep_going= 0;/*:69*/#line 1307 "./match.w"}else{keep_going= 0;}}}/*:70*/#line 1043 "./match.w"}}}/*:57*/#line 957 "./match.w"if(best_two_i){/*73:*/#line 1365 "./match.w"/*75:*/#line 1405 "./match.w"#if MATCH_REPORT_DEPTHSmove_depth= best_two_i+2;#endif/*:75*/#line 1366 "./match.w"while(best_two_i<two_i){/*69:*/#line 1276 "./match.w"if(two_i> 2){if(two_i<=2*backtracking_levels){ei[two_i]= -2;en[two_i]= -1;}two_i-= 2;/*97:*/#line 1685 "./match.w"#if MATCH_MAX_VERBOSE >= 125if(verbose> 125){int i;printf("\n");for(i= 0;i<two_i;i++)putchar(' ');printf("-");fflush(stdout);}#endif/*:97*/#line 1283 "./match.w"swap_mates(t[1],t[two_i+2],t[two_i+1],t[two_i]);/*101:*/#line 1731 "./match.w"#if MATCH_MAX_VERBOSE >= 150if(verbose>=150){int i;printf("t:");for(i= 1;i<=two_i;i++)printf(" %d",t[i]);printf("\n");fflush(stdout);}#endif/*:101*/#line 1285 "./match.w"}else keep_going= 0;/*:69*/#line 1367 "./match.w"}/*103:*/#line 1757 "./match.w"#if MATCH_MAX_VERBOSE >= 110if(verbose>=110){int i,m= (two_i<best_two_i?two_i:best_two_i);printf("two_i %d best_two_i %d best_exit_a %d best_exit_b %d\n",two_i,best_two_i,best_exit_a,best_exit_b);printf("B:");for(i= 1;i<=m;i++)printf(" %d",t[i]);printf("\n");fflush(stdout);}#endif/*:103*/#line 1368 "./match.w"swap_mates(t[1],t[best_two_i],best_exit_a,best_exit_b);/*82:*/#line 1495 "./match.w"if(iteration> 0){const int more_log= 3+best_two_i;/*83:*/#line 1512 "./match.w"{const int need_size= more_log+change_log_next;if(need_size>=change_log_max_alloc){do{change_log_max_alloc*= 2;}while(need_size>=change_log_max_alloc);change_log= (int*)mem_realloc(change_log,sizeof(int)*change_log_max_alloc);}}/*:83*/#line 1498 "./match.w"{int j;for(j= 1;j<=best_two_i;j++){write_log(t[j]);}}write_log(best_exit_a);write_log(best_exit_b);write_log(2+best_two_i);}/*:82*/#line 1370 "./match.w"/*55:*/#line 999 "./match.w"{int i;for(i= 1;i<=best_two_i;i++){mark_dirty(t[i]);}mark_dirty(best_exit_a);mark_dirty(best_exit_b);}/*:55*/#line 1371 "./match.w"/*102:*/#line 1743 "./match.w"#if MATCH_MAX_VERBOSE >= 110if(verbose>=110){int i;printf("T:");for(i= 1;i<=best_two_i;i++)printf(" %d",t[i]);printf(" %d",best_exit_a);printf(" %d",best_exit_b);printf("\n");fflush(stdout);}#endif/*:102*/#line 1372 "./match.w"incumbent_len-= best_gain;/*100:*/#line 1721 "./match.w"#if MATCH_MAX_VERBOSE >= 100if(verbose>=100){printf("=== improve by "length_t_spec" to "length_t_spec"\n",length_t_pcast(best_gain),length_t_pcast(incumbent_len));fflush(stdout);}#endif/*:100*/#line 1374 "./match.w"/*95:*/#line 1672 "./match.w"milestone_check(&ms_lower_bound,incumbent_len);milestone_check(&ms_upper_bound,incumbent_len);/*:95*/#line 1375 "./match.w"/*39:*/#line 769 "./match.w"#if !LENGTH_TYPE_IS_EXACTinstance_epsilon= incumbent_len*LENGTH_MACHINE_EPSILON;#endif/*:39*/#line 1376 "./match.w"/*:73*/#line 958 "./match.w"}/*79:*/#line 1442 "./match.w"#if MATCH_REPORT_DEPTHSm_depths[move_depth/2]+= 1;p_depths[probe_depth_less_2/2+1]+= 1;#endif/*:79*/#line 959 "./match.w"}/*114:*/#line 1864 "./match.w"#if MATCH_MAX_VERBOSE >= 40if(verbose>=40){char end_iter_message[100];printf("End of LK step %d, incumbent_len = "length_t_spec"\n",iteration+1,length_t_pcast(incumbent_len));sprintf(end_iter_message,"End of LK step %d",iteration+1);milestone_show_request(&ms_lower_bound,end_iter_message,incumbent_len);milestone_show_request(&ms_upper_bound,end_iter_message,incumbent_len);}#endif/*:114*/#line 961 "./match.w"/*87:*/#line 1547 "./match.w"if(iteration> 0&&change_log_next> 0&&previous_incumbent_len<incumbent_len){/*113:*/#line 1856 "./match.w"#if MATCH_MAX_VERBOSE >= 57if(verbose>=57){printf("Reverting to previous\n");}#endif/*:113*/#line 1549 "./match.w"while(change_log_next> 0){/*89:*/#line 1577 "./match.w"{const int t1_pos= change_log_next-change_log[change_log_next-1]-1;int j;for(j= change_log_next-3;j>=t1_pos;j-= 2){const int a= change_log[j],b= change_log[j+1];make_mates(a,b);}errorif(j!=t1_pos-2,"Fencepost Bug!");}/*:89*/#line 1551 "./match.w"change_log_next-= change_log[change_log_next-1]+1;}errorif(change_log_next!=0,"Bug!");incumbent_len= previous_incumbent_len;}change_log_next= 0;/*:87*/#line 962 "./match.w"/*90:*/#line 1601 "./match.w"if(iteration+1<iterations){int m[8],i;/*91:*/#line 1627 "./match.w"{int count= 0,still_clashing;do{int j;errorif(count++>=10000,"Ummm, 4-change matching mutation didn't terminate after 10000 tries!\n");for(j= 0;j<8;j+= 2){m[j]= prng_unif_int(random_stream,n);m[j+1]= mate[m[j]];}still_clashing= 0;for(j= 0;j<8;j+= 2){int k;for(k= j+2;k<8;k++){if(m[j]==m[k]){still_clashing= 1;break;}}}}while(still_clashing);}/*:91*/#line 1605 "./match.w"make_mates(m[0],m[7]);make_mates(m[1],m[2]);make_mates(m[3],m[4]);make_mates(m[5],m[6]);for(i= 0;i<8;i++)write_log(m[i]);write_log(8);previous_incumbent_len= incumbent_len;incumbent_len+= cost(m[1],m[2])+cost(m[3],m[4])+cost(m[5],m[6])+cost(m[7],m[0])-cost(m[0],m[1])-cost(m[2],m[3])-cost(m[4],m[5])-cost(m[6],m[7]);for(i= 0;i<8;i++)mark_dirty(m[i]);}/*:90*/#line 963 "./match.w"}/*115:*/#line 1878 "./match.w"#if MATCH_MAX_VERBOSE >= 20if(verbose>=20){const double lk_time= resource_user_tick();const double ds_time= resource_user_tick_from(begin_data_structures_mark);printf("LK phase ended with incumbent_len == "length_t_spec" after %.3f sec for LK and %.3f sec for ds+LK\n",length_t_pcast(incumbent_len),lk_time,ds_time);fflush(stdout);}#endif/*:115*/#line 965 "./match.w"/*96:*/#line 1677 "./match.w"milestone_show_final(&ms_lower_bound,incumbent_len);milestone_show_final(&ms_upper_bound,incumbent_len);/*:96*/#line 966 "./match.w"/*81:*/#line 1460 "./match.w"#if MATCH_REPORT_DEPTHS{int i,j;for(i= DEPTHS_BOUND-1;p_depths[i]==0&&i> 0;i--);for(j= 0;j<=i;j++){printf("p %d citydeep %d\n",j*2,p_depths[j]);}for(i= DEPTHS_BOUND-1;m_depths[i]==0&&i> 0;i--);for(j= 0;j<=i;j++){printf("m %d citydeep %d\n",j*2,m_depths[j]);}}#endif/*:81*/#line 967 "./match.w"/*48:*/#line 916 "./match.w"{int l;for(l= 2;l<=2*backtracking_levels;l+= 2){free_mem(e[l]);mem_deduct(sizeof(eligible_t)*nn_max_bound);}free_mem(e);mem_deduct(sizeof(eligible_t*)*(1+2*backtracking_levels));free_mem(en);mem_deduct(sizeof(int)*(1+2*backtracking_levels));free_mem(ei);mem_deduct(sizeof(int)*(1+2*backtracking_levels));}/*:48*//*80:*/#line 1450 "./match.w"#if MATCH_REPORT_DEPTHSfree_mem(m_depths);mem_deduct(sizeof(int)*DEPTHS_BOUND);free_mem(p_depths);mem_deduct(sizeof(int)*DEPTHS_BOUND);#endif/*:80*//*85:*/#line 1529 "./match.w"free_mem(change_log);mem_deduct(sizeof(int)*change_log_max_alloc);/*:85*/#line 968 "./match.w"}/*:49*/#line 239 "./match.w"const char*match_rcs_id= "$Id: match.w,v 1.25 2000/09/17 03:10:18 neto Exp neto $";/*:4*/