dirty.c

Lin-Kernighan heuristic for the TSP and minimum weight perfect matching

#define VIRTUAL_BASE ((char*) 42)  \

/*2:*/
#line 124 "./dirty.w"

#include <config.h> 
#include "lkconfig.h"
/*3:*/
#line 140 "./dirty.w"

#include <stdio.h> 
#include <stdlib.h> 
#include <stddef.h> 

/*:3*/
#line 127 "./dirty.w"

#include "error.h"
#include "memory.h"
#include "dirty.h"

/*32:*/
#line 547 "./dirty.w"

#if DIRTY_SET == DIRTY_SET_FIFO
static dirty_queue_node_t sentinel;
#endif


/*:32*//*38:*/
#line 634 "./dirty.w"

#if DIRTY_SET == DIRTY_SET_FIFO
static int num_queues= 0;
#endif

/*:38*/
#line 132 "./dirty.w"

/*18:*/
#line 390 "./dirty.w"

#if DIRTY_SET == DIRTY_SET_SPLAY_ROOT
static int cmp_virtual_char(const void*a,const void*b);
static int
cmp_virtual_char(const void*a,const void*b)
{
return(const char*)a-(const char*)b;
}

static void prn_virtual_char(void*a);
static void
prn_virtual_char(void*a)
{
printf("%d",(const char*)a-VIRTUAL_BASE);
}
#endif

/*:18*//*31:*/
#line 526 "./dirty.w"

#if DIRTY_SET == DIRTY_SET_FIFO && DIRTY_DEBUG
void show_FIFO(dirty_set_t*ds);
void show_FIFO(dirty_set_t*ds)
{
if(0> 5000){
dirty_queue_node_t*p= ds->head;
while(p&&p!=&sentinel){
printf(" %d",p-ds->queue);
p= p->next;
}
printf(".\n");
}
fflush(stdout);
}
#endif

/*:31*/
#line 133 "./dirty.w"

/*7:*/
#line 227 "./dirty.w"

dirty_set_t*
dirty_create(int n,int full,int seed,const char*file,int line)
{
dirty_set_t*ds= new_of(dirty_set_t);
errorif(n<0,"Dirty set must be over non-empty range: n=%d",n);
ds->n= n;
ds->num_used= -1;
ds->file= file;
ds->line= line;
#if DIRTY_SET==DIRTY_SET_SPLAY_ROOT
/*17:*/
#line 366 "./dirty.w"

ds->dict= dict_create(cmp_virtual_char,prn_virtual_char);


/*:17*/
#line 238 "./dirty.w"

#else
/*27:*/
#line 492 "./dirty.w"

ds->queue= new_arr_of(dirty_queue_node_t,n);

/*:27*//*37:*/
#line 626 "./dirty.w"

ds->prng= prng_new(PRNG_DEFAULT,seed^21264^num_queues++);

/*:37*/
#line 240 "./dirty.w"

#endif
if(full){dirty_make_full(ds,seed);}
else{dirty_make_empty(ds);}
#if DIRTY_DEBUG

printf("dirty.w:%d:dirty_create(%d,%d,%d,%s,%d) = %8p\n",
__LINE__,n,full,seed,file,line,ds);
#endif
return ds;
}


/*:7*//*8:*/
#line 254 "./dirty.w"

void
dirty_destroy(dirty_set_t*ds)
{
if(ds){
#if DIRTY_SET == DIRTY_SET_SPLAY_ROOT
/*19:*/
#line 408 "./dirty.w"

if(ds->dict)dict_destroy(ds->dict,NULL);


/*:19*/
#line 260 "./dirty.w"

#else
/*28:*/
#line 496 "./dirty.w"

free_mem(ds->queue);mem_deduct(ds->n*sizeof(dirty_queue_node_t));
ds->head= NULL;
ds->tail= NULL;

/*:28*//*39:*/
#line 640 "./dirty.w"

prng_free(ds->prng);

/*:39*/
#line 262 "./dirty.w"

#endif
ds->n= -1;
free_mem(ds);mem_deduct(sizeof(dirty_set_t));
}
}


/*:8*//*9:*/
#line 271 "./dirty.w"

void
dirty_add(dirty_set_t*ds,const int v)
{
#if DIRTY_DEBUG
errorif(v<0||v>=ds->n,"arg v=%d not in range 0..%d",v,ds->n-1);
#endif
#if DIRTY_SET == DIRTY_SET_SPLAY_ROOT
/*22:*/
#line 432 "./dirty.w"

if(!dict_insert(ds->dict,VIRTUAL_BASE+v))ds->num_used++;

/*:22*/
#line 279 "./dirty.w"

#else
/*30:*/
#line 507 "./dirty.w"

{dirty_queue_node_t*dq= ds->queue;
#if DIRTY_DEBUG
if(verbose>=1000){printf("Before adding  : ");show_FIFO(ds);}
#endif
if(dq[v].next==NULL){
dq[v].next= &sentinel;
if(ds->tail)ds->tail->next= dq+v;
else ds->head= dq+v;
ds->tail= dq+v;
ds->num_used++;
}
#if DIRTY_DEBUG
if(verbose>=1000){printf("After adding   : ");show_FIFO(ds);}
#endif
}


/*:30*/
#line 281 "./dirty.w"

#endif
}

/*:9*//*10:*/
#line 286 "./dirty.w"

int
dirty_includes(dirty_set_t*ds,const int v)
{
#if DIRTY_SET == DIRTY_SET_SPLAY_ROOT
/*23:*/
#line 440 "./dirty.w"

return dict_find(ds->dict,VIRTUAL_BASE+v)!=NULL;

/*:23*/
#line 291 "./dirty.w"

#else
/*29:*/
#line 502 "./dirty.w"

return ds->queue[v].next!=NULL;

/*:29*/
#line 293 "./dirty.w"

#endif
}


/*:10*//*11:*/
#line 301 "./dirty.w"

int
dirty_remove(dirty_set_t*ds)
{
int return_value= -1;
#if DIRTY_SET == DIRTY_SET_SPLAY_ROOT
/*24:*/
#line 447 "./dirty.w"

{void*vp= dict_delete_any(ds->dict,NULL);
if(vp){ds->num_used--;return((char*)vp)-VIRTUAL_BASE;}
}


/*:24*/
#line 307 "./dirty.w"

#else
/*33:*/
#line 557 "./dirty.w"

#if DIRTY_DEBUG
if(verbose>=1000){printf("Before removing: ");show_FIFO(ds);}
#endif
if(ds->head){
dirty_queue_node_t*old_head= ds->head;
return_value= old_head-ds->queue;
if(old_head==ds->tail)ds->tail= ds->head= NULL;

else ds->head= old_head->next;
old_head->next= NULL;
ds->num_used--;
}
#if DIRTY_DEBUG
if(verbose>=1000){printf("After  removing: ");show_FIFO(ds);}
#endif

/*:33*/
#line 309 "./dirty.w"

#endif
return return_value;
}


/*:11*//*12:*/
#line 316 "./dirty.w"

void
dirty_make_full(dirty_set_t*ds,int seed)
{
#if DIRTY_SET == DIRTY_SET_SPLAY_ROOT
/*20:*/
#line 415 "./dirty.w"

{
int i,n= ds->n;
dict_t*d= ds->dict;
for(i= 0;i<n;i++){
dict_insert(d,VIRTUAL_BASE+i);
}
}

/*:20*/
#line 321 "./dirty.w"

#else
/*40:*/
#line 646 "./dirty.w"

{
const int n= ds->n;
prng_t*prng= ds->prng;
int i,*work= new_arr_of(int,n);

/*41:*/
#line 660 "./dirty.w"

for(i= 0;i<n;i++)work[i]= i;
for(i= 0;i<n;i++){
const int next= prng_unif_int(prng,n-i);
const int t= work[next];
work[next]= work[n-1-i];
work[n-1-i]= t;
}

/*:41*/
#line 652 "./dirty.w"

/*42:*/
#line 670 "./dirty.w"

{
dirty_queue_node_t*q= ds->queue;
ds->head= q+work[0];
ds->tail= q+work[n-1];
for(i= 0;i<n-1;i++){
q[work[i]].next= q+work[i+1];
}
q[work[n-1]].next= &sentinel;
}



/*:42*/
#line 653 "./dirty.w"


free_mem(work);mem_deduct(n*sizeof(int));
}


/*:40*/
#line 323 "./dirty.w"

#endif
ds->num_used= ds->n;
}

/*:12*//*13:*/
#line 329 "./dirty.w"

void
dirty_make_empty(dirty_set_t*ds)
{
#if DIRTY_SET == DIRTY_SET_SPLAY_ROOT
/*21:*/
#line 426 "./dirty.w"

dict_delete_all(ds->dict,NULL);

/*:21*/
#line 334 "./dirty.w"

#else
/*34:*/
#line 592 "./dirty.w"

if(ds->num_used<0||ds->num_used>=ds->n/2){
ds->head= ds->tail= NULL;
{int i;
const int n= ds->n;
dirty_queue_node_t*dq= ds->queue;
for(i= 0;i<n;i++)dq[i].next= NULL;
}
}else{
int return_value;
while(ds->head){/*33:*/
#line 557 "./dirty.w"

#if DIRTY_DEBUG
if(verbose>=1000){printf("Before removing: ");show_FIFO(ds);}
#endif
if(ds->head){
dirty_queue_node_t*old_head= ds->head;
return_value= old_head-ds->queue;
if(old_head==ds->tail)ds->tail= ds->head= NULL;

else ds->head= old_head->next;
old_head->next= NULL;
ds->num_used--;
}
#if DIRTY_DEBUG
if(verbose>=1000){printf("After  removing: ");show_FIFO(ds);}
#endif

/*:33*/
#line 602 "./dirty.w"
}
}

/*:34*/
#line 336 "./dirty.w"

#endif
ds->num_used= 0;
}


/*:13*//*14:*/
#line 343 "./dirty.w"

int
dirty_has_elements(dirty_set_t*ds)
{
return ds->num_used> 0;
}



/*:14*/
#line 134 "./dirty.w"

const char*dirty_rcs_id= "$Id: dirty.w,v 1.14 2000/09/17 03:08:33 neto Exp neto $";

/*:2*/