pq.c

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

#define SWAP(x,y) {void*t= x;x= y;y= t;} \

/*2:*/
#line 98 "./pq.w"


#include <stdio.h>
#include <stdlib.h>
#include <stddef.h>
#include "pq.h"
#include "error.h"

/*7:*/
#line 155 "./pq.w"

pq_t*
pq_create(pq_cmp_func_t cmp)
{
return pq_create_size(cmp,1023);
}

pq_t*
pq_create_size(pq_cmp_func_t cmp,int n)
{
pq_t*pq= malloc(sizeof(pq_t));
if(pq){
pq->cmp= cmp;
pq->last_elem_i= 0;
pq->A_size= 1+((n<63)?63:n);
pq->A= malloc(sizeof(void*)*pq->A_size);
errorif(pq->A==NULL,"Couldn't allocate a heap array of %d bytes",sizeof(void*)*pq->A_size);
}
return pq;
}

/*:7*//*8:*/
#line 177 "./pq.w"

void
pq_make_empty(pq_t*pq)
{
pq->last_elem_i= 0;
}

/*:8*//*9:*/
#line 185 "./pq.w"

void
pq_destroy(pq_t*pq)
{
if(pq){
if(pq->A){free(pq->A);pq->A= NULL;}
pq->last_elem_i= 0;
pq->A_size= 0;
free(pq);
}
}

/*:9*//*10:*/
#line 198 "./pq.w"

int
pq_empty_func(pq_t*pq)
{
return pq->last_elem_i==0;
}


/*:10*//*11:*/
#line 207 "./pq.w"

int
pq_size_func(pq_t*pq)
{
return pq->last_elem_i;
}

/*:11*//*12:*/
#line 221 "./pq.w"

void
pq_insert(pq_t*pq,void*payload)
{
pq_cmp_func_t cmp= pq->cmp;
int i= pq->last_elem_i+1;
void**A;
if(i>=pq->A_size){
pq->A_size*= 2;
pq->A= realloc(pq->A,sizeof(void*)*pq->A_size);
errorif(pq->A==NULL,"pq_insert: realloc failed: couldn't grow array");
}
A= pq->A;
A[i]= payload;
while(i>1&&cmp(A[i/2],A[i])>0){
SWAP(A[i],A[i/2]);
i/= 2;
}
pq->last_elem_i++;
/*13:*/
#line 244 "./pq.w"

#if PQ_DEBUGGING_CHARS
{int i;
for(i= 1;i<=pq->last_elem_i;i++){
putchar(*(char*)pq->A[i]);
}
putchar('\n');
}
#endif

/*:13*/
#line 240 "./pq.w"

}

/*:12*//*14:*/
#line 255 "./pq.w"

void*
pq_min(pq_t*pq)
{
return pq->last_elem_i?pq->A[1]:NULL;
}

/*:14*//*15:*/
#line 263 "./pq.w"

void*
pq_delete_min(pq_t*pq)
{
if(pq->last_elem_i){
void**A= pq->A;
void*the_min= A[1];
A[1]= A[pq->last_elem_i--];
/*16:*/
#line 281 "./pq.w"

{
const int last_elem_i= pq->last_elem_i;
pq_cmp_func_t cmp= pq->cmp;
int i,next_i;
for(i= 1,next_i= 0;i;i= next_i,next_i= 0){
const int child1= i*2,child2= child1+1;
if(child2<=last_elem_i){
const int least_child= cmp(A[child1],A[child2])<0?child1:child2;
if(cmp(A[i],A[least_child])>0){
SWAP(A[i],A[least_child]);
next_i= least_child;
}
}else if(child1<=last_elem_i&&cmp(A[i],A[child1])>0){
SWAP(A[i],A[child1]);
next_i= child1;
}
}
}

/*:16*/
#line 271 "./pq.w"

/*13:*/
#line 244 "./pq.w"

#if PQ_DEBUGGING_CHARS
{int i;
for(i= 1;i<=pq->last_elem_i;i++){
putchar(*(char*)pq->A[i]);
}
putchar('\n');
}
#endif

/*:13*/
#line 272 "./pq.w"

return the_min;
}else{return NULL;}
}


/*:15*//*17:*/
#line 304 "./pq.w"

void
pq_set_print_func(pq_t*pq,void(*print_func)(FILE*,void*))
{
pq->print_func= print_func;
}

/*:17*//*18:*/
#line 313 "./pq.w"

void
pq_print(pq_t*pq,FILE*out)
{
int i,row_count= 0,row_size= 1;
if(pq==NULL||pq->print_func==NULL)return;
for(i= 1;i<pq->last_elem_i;i++){
fprintf(out," %d->",i);
pq->print_func(out,pq->A[i]);
if(++row_count==row_size){
fputc('\n',out);
row_size*= 2;
row_count= 0;
}
}
if(row_count){fputc('\n',out);}
}

/*:18*/
#line 106 "./pq.w"

const char*pq_rcs_id= "$Id: pq.w,v 1.7 1998/10/09 16:47:34 neto Exp neto $";

/*:2*/