dict.c

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

}while(1);
}

/*:19*/
#line 851 "./dict.w"

return here->payload;
}else return NULL;
}

/*:34*//*35:*/
#line 859 "./dict.w"


void*
dict_delete_min(dict_t*d)
{
if(d->root){
dict_node_t*m,*next,*here= NULL,*splay_this;
void(*action)(void*)= NULL,*payload;
for(m= d->root;m->left;m= m->left)
;
next= m;
payload= m->payload;
/*26:*/
#line 709 "./dict.w"

{
dict_node_t*e_node,*ep;
int l;
e_node= next;
if(e_node){
if(e_node->left==NULL&&e_node->right==NULL){
/*27:*/
#line 735 "./dict.w"

/*28:*/
#line 750 "./dict.w"

ep= e_node->parent;
l= NILLINK;
if(ep){
if(ep->left==e_node)l= LEFT;
else if(ep->right==e_node)l= RIGHT;
else{errorif(1,"Bug");}
}

/*:28*/
#line 736 "./dict.w"

if(ep){ep->link[l]= NULL;}
else{d->root= NULL;}



/*:27*/
#line 716 "./dict.w"

splay_this= e_node->parent;
}else if(e_node->left==NULL){
/*29:*/
#line 762 "./dict.w"

/*28:*/
#line 750 "./dict.w"

ep= e_node->parent;
l= NILLINK;
if(ep){
if(ep->left==e_node)l= LEFT;
else if(ep->right==e_node)l= RIGHT;
else{errorif(1,"Bug");}
}

/*:28*/
#line 763 "./dict.w"

if(ep){SETLINK(ep,l,e_node->right);}
else{e_node->right->parent= NULL;d->root= e_node->right;}

/*:29*/
#line 719 "./dict.w"

splay_this= e_node->right;
}else if(e_node->right==NULL){
/*30:*/
#line 768 "./dict.w"

/*28:*/
#line 750 "./dict.w"

ep= e_node->parent;
l= NILLINK;
if(ep){
if(ep->left==e_node)l= LEFT;
else if(ep->right==e_node)l= RIGHT;
else{errorif(1,"Bug");}
}

/*:28*/
#line 769 "./dict.w"

if(ep){SETLINK(ep,l,e_node->left);}
else{e_node->left->parent= NULL;d->root= e_node->left;}

/*:30*/
#line 722 "./dict.w"

splay_this= e_node->left;
}else{
/*31:*/
#line 785 "./dict.w"

{dict_node_t*erL,*save_e_node= e_node;

for(erL= e_node->right;erL->left;erL= erL->left)
;
if(erL->right){
splay_this= erL->right;
}else{
if(erL->parent!=e_node)splay_this= erL->parent;
else splay_this= erL;
}
e_node= erL;
/*29:*/
#line 762 "./dict.w"

/*28:*/
#line 750 "./dict.w"

ep= e_node->parent;
l= NILLINK;
if(ep){
if(ep->left==e_node)l= LEFT;
else if(ep->right==e_node)l= RIGHT;
else{errorif(1,"Bug");}
}

/*:28*/
#line 763 "./dict.w"

if(ep){SETLINK(ep,l,e_node->right);}
else{e_node->right->parent= NULL;d->root= e_node->right;}

/*:29*/
#line 797 "./dict.w"

e_node= save_e_node;


SETLINK(erL,LEFT,e_node->left);
if(e_node->right!=erL){SETLINK(erL,RIGHT,e_node->right);}


/*28:*/
#line 750 "./dict.w"

ep= e_node->parent;
l= NILLINK;
if(ep){
if(ep->left==e_node)l= LEFT;
else if(ep->right==e_node)l= RIGHT;
else{errorif(1,"Bug");}
}

/*:28*/
#line 805 "./dict.w"

if(ep){SETLINK(ep,l,erL);}
else{erL->parent= NULL;d->root= erL;}
}

/*:31*/
#line 725 "./dict.w"

}
if(action)action(e_node->payload);
pool_free(d->pool,e_node);
d->size--;
here= splay_this;
}
}

/*:26*/
#line 871 "./dict.w"

/*19:*/
#line 510 "./dict.w"

if(here){
dict_node_t*p,*gp,*ggp= NULL;
int pl,gpl;
int ggpl= NILLINK;

dict_node_t*subtree[2];
do{
errorif(here==NULL,"|here| must not be NULL");
/*20:*/
#line 527 "./dict.w"

gpl= pl= SELF;
p= here->parent;
if(p){
if(p->left==here)pl= LEFT;
else if(p->right==here)pl= RIGHT;
else{dict_doall(d,d->prn);errorif(1,"Bug");}
gp= p->parent;
if(gp){
if(gp->left==p)gpl= LEFT;
else if(gp->right==p)gpl= RIGHT;
else{dict_doall(d,d->prn);errorif(1,"Bug");}
ggp= gp->parent;
if(ggp){
if(ggp->left==gp)ggpl= LEFT;
else if(ggp->right==gp)ggpl= RIGHT;
else{dict_doall(d,d->prn);errorif(1,"Bug");}
}
}
}else{
break;
}


/*:20*/
#line 519 "./dict.w"

/*21:*/
#line 558 "./dict.w"

if(gp){
/*22:*/
#line 584 "./dict.w"

switch(gpl){
case LEFT:
switch(pl){
case LEFT:
subtree[0]= here->right;
subtree[1]= p->right;
SETLINK(here,RIGHT,p);
SETLINK(p,RIGHT,gp);
SETLINK(p,LEFT,subtree[0]);
SETLINK(gp,LEFT,subtree[1]);
break;
case RIGHT:
subtree[0]= here->left;
subtree[1]= here->right;
SETLINK(here,LEFT,p);
SETLINK(here,RIGHT,gp);
SETLINK(p,RIGHT,subtree[0]);
SETLINK(gp,LEFT,subtree[1]);
break;
}
break;
case RIGHT:
switch(pl){
case LEFT:
subtree[0]= here->left;
subtree[1]= here->right;
SETLINK(here,LEFT,gp);
SETLINK(here,RIGHT,p);
SETLINK(gp,RIGHT,subtree[0]);
SETLINK(p,LEFT,subtree[1]);
break;
case RIGHT:
subtree[0]= p->left;
subtree[1]= here->left;
SETLINK(here,LEFT,p);
SETLINK(p,LEFT,gp);
SETLINK(gp,RIGHT,subtree[0]);
SETLINK(p,RIGHT,subtree[1]);
break;
}
break;
}
if(ggp){
if(ggpl!=NILLINK){
SETLINK(ggp,ggpl,here);
}else{
errorif(1,"Uninitialized great grandparent link.");
}
}else{here->parent= NULL;d->root= here;}


/*:22*/
#line 560 "./dict.w"

}else{
/*23:*/
#line 642 "./dict.w"

switch(pl){
case LEFT:
subtree[0]= here->right;
SETLINK(here,RIGHT,p);
SETLINK(p,LEFT,subtree[0]);
break;
case RIGHT:
subtree[0]= here->left;
SETLINK(here,LEFT,p);
SETLINK(p,RIGHT,subtree[0]);
break;
}
here->parent= NULL;
d->root= here;

/*:23*/
#line 562 "./dict.w"

}

/*:21*/
#line 520 "./dict.w"

}while(1);
}

/*:19*/
#line 872 "./dict.w"

return payload;
}else return NULL;
}

void*
dict_delete_max(dict_t*d)
{
if(d->root){
dict_node_t*m,*next,*here= NULL,*splay_this;
void(*action)(void*)= NULL,*payload;
for(m= d->root;m->right;m= m->right)
;
next= m;
payload= m->payload;
/*26:*/
#line 709 "./dict.w"

{
dict_node_t*e_node,*ep;
int l;
e_node= next;
if(e_node){
if(e_node->left==NULL&&e_node->right==NULL){
/*27:*/
#line 735 "./dict.w"

/*28:*/
#line 750 "./dict.w"

ep= e_node->parent;
l= NILLINK;
if(ep){
if(ep->left==e_node)l= LEFT;
else if(ep->right==e_node)l= RIGHT;
else{errorif(1,"Bug");}
}

/*:28*/
#line 736 "./dict.w"

if(ep){ep->link[l]= NULL;}
else{d->root= NULL;}



/*:27*/
#line 716 "./dict.w"

splay_this= e_node->parent;
}else if(e_node->left==NULL){
/*29:*/
#line 762 "./dict.w"

/*28:*/
#line 750 "./dict.w"

ep= e_node->parent;
l= NILLINK;
if(ep){
if(ep->left==e_node)l= LEFT;
else if(ep->right==e_node)l= RIGHT;
else{errorif(1,"Bug");}
}

/*:28*/
#line 763 "./dict.w"

if(ep){SETLINK(ep,l,e_node->right);}
else{e_node->right->parent= NULL;d->root= e_node->right;}

/*:29*/
#line 719 "./dict.w"

splay_this= e_node->right;
}else if(e_node->right==NULL){
/*30:*/
#line 768 "./dict.w"

/*28:*/
#line 750 "./dict.w"

ep= e_node->parent;
l= NILLINK;
if(ep){
if(ep->left==e_node)l= LEFT;
else if(ep->right==e_node)l= RIGHT;
else{errorif(1,"Bug");}
}

/*:28*/
#line 769 "./dict.w"

if(ep){SETLINK(ep,l,e_node->left);}
else{e_node->left->parent= NULL;d->root= e_node->left;}

/*:30*/
#line 722 "./dict.w"

splay_this= e_node->left;
}else{
/*31:*/
#line 785 "./dict.w"

{dict_node_t*erL,*save_e_node= e_node;

for(erL= e_node->right;erL->left;erL= erL->left)
;
if(erL->right){
splay_this= erL->right;
}else{
if(erL->parent!=e_node)splay_this= erL->parent;
else splay_this= erL;
}
e_node= erL;
/*29:*/
#line 762 "./dict.w"

/*28:*/
#line 750 "./dict.w"

ep= e_node->parent;
l= NILLINK;
if(ep){
if(ep->left==e_node)l= LEFT;
else if(ep->right==e_node)l= RIGHT;
else{errorif(1,"Bug");}
}

/*:28*/
#line 763 "./dict.w"

if(ep){SETLINK(ep,l,e_node->right);}
else{e_node->right->parent= NULL;d->root= e_node->right;}

/*:29*/
#line 797 "./dict.w"

e_node= save_e_node;


SETLINK(erL,LEFT,e_node->left);
if(e_node->right!=erL){SETLINK(erL,RIGHT,e_node->right);}


/*28:*/
#line 750 "./dict.w"

ep= e_node->parent;
l= NILLINK;
if(ep){
if(ep->left==e_node)l= LEFT;
else if(ep->right==e_node)l= RIGHT;
else{errorif(1,"Bug");}
}

/*:28*/
#line 805 "./dict.w"

if(ep){SETLINK(ep,l,erL);}
else{erL->parent= NULL;d->root= erL;}
}

/*:31*/
#line 725 "./dict.w"

}
if(action)action(e_node->payload);
pool_free(d->pool,e_node);
d->size--;
here= splay_this;
}
}

/*:26*/
#line 887 "./dict.w"

/*19:*/
#line 510 "./dict.w"

if(here){
dict_node_t*p,*gp,*ggp= NULL;
int pl,gpl;
int ggpl= NILLINK;

dict_node_t*subtree[2];
do{
errorif(here==NULL,"|here| must not be NULL");
/*20:*/
#line 527 "./dict.w"

gpl= pl= SELF;
p= here->parent;
if(p){
if(p->left==here)pl= LEFT;
else if(p->right==here)pl= RIGHT;
else{dict_doall(d,d->prn);errorif(1,"Bug");}
gp= p->parent;
if(gp){
if(gp->left==p)gpl= LEFT;
else if(gp->right==p)gpl= RIGHT;
else{dict_doall(d,d->prn);errorif(1,"Bug");}
ggp= gp->parent;
if(ggp){
if(ggp->left==gp)ggpl= LEFT;
else if(ggp->right==gp)ggpl= RIGHT;
else{dict_doall(d,d->prn);errorif(1,"Bug");}
}
}
}else{
break;
}


/*:20*/
#line 519 "./dict.w"

/*21:*/
#line 558 "./dict.w"

if(gp){
/*22:*/
#line 584 "./dict.w"

switch(gpl){
case LEFT:
switch(pl){
case LEFT:
subtree[0]= here->right;
subtree[1]= p->right;
SETLINK(here,RIGHT,p);
SETLINK(p,RIGHT,gp);
SETLINK(p,LEFT,subtree[0]);
SETLINK(gp,LEFT,subtree[1]);
break;
case RIGHT:
subtree[0]= here->left;
subtree[1]= here->right;
SETLINK(here,LEFT,p);
SETLINK(here,RIGHT,gp);
SETLINK(p,RIGHT,subtree[0]);
SETLINK(gp,LEFT,subtree[1]);
break;
}
break;
case RIGHT:
switch(pl){
case LEFT:
subtree[0]= here->left;
subtree[1]= here->right;
SETLINK(here,LEFT,gp);
SETLINK(here,RIGHT,p);
SETLINK(gp,RIGHT,subtree[0]);
SETLINK(p,LEFT,subtree[1]);
break;
case RIGHT:
subtree[0]= p->left;
subtree[1]= here->left;
SETLINK(here,LEFT,p);
SETLINK(p,LEFT,gp);
SETLINK(gp,RIGHT,subtree[0]);
SETLINK(p,RIGHT,subtree[1]);
break;
}
break;
}
if(ggp){
if(ggpl!=NILLINK){
SETLINK(ggp,ggpl,here);
}else{
errorif(1,"Uninitialized great grandparent link.");
}
}else{here->parent= NULL;d->root= here;}


/*:22*/
#line 560 "./dict.w"

}else{
/*23:*/
#line 642 "./dict.w"

switch(pl){
case LEFT:
subtree[0]= here->right;
SETLINK(here,RIGHT,p);
SETLINK(p,LEFT,subtree[0]);
break;
case RIGHT:
subtree[0]= here->left;
SETLINK(here,LEFT,p);
SETLINK(p,RIGHT,subtree[0]);
break;
}
here->parent= NULL;
d->root= here;

/*:23*/
#line 562 "./dict.w"

}

/*:21*/
#line 520 "./dict.w"

}while(1);
}

/*:19*/
#line 888 "./dict.w"

return payload;
}else return NULL;
}

/*:35*//*36:*/
#line 897 "./dict.w"

void
dict_update_all(dict_t*d,void(*proc)(void*env2,void**payload_p),void*env1)
{
dict_node_t*here,*prev;
here= d->root;
prev= NULL;
while(here!=NULL){
if(here->left!=NULL&&prev==here->parent){
prev= here;
here= here->left;
}else if(here->right!=NULL&&prev!=here->right){
prev= here;
here= here->right;
}else{
proc(env1,&(here->payload));
prev= here;
here= here->parent;
}
}
}

/*:36*//*37:*/
#line 922 "./dict.w"

size_t
dict_size(dict_t*d)
{
return d->size;
}

/*:37*//*38:*/
#line 930 "./dict.w"


void visit(dict_node_t*n,void(*action)(void*));
void visit(dict_node_t*n,void(*action)(void*)){
if(n){
printf("(");
visit(n->left,action);
errorif(n->left!=NULL&&n->left->parent!=n,"Bug");
if(action)action(n->payload);
visit(n->right,action);
errorif(n->right!=NULL&&n->right->parent!=n,"Bug");
printf(")");
}
}

void
dict_doall(dict_t*d,void(*action)(void*)){
visit(d->root,action);
errorif(d->root!=NULL&&d->root->parent!=NULL,"Bug");
}

void
dict_show_node(dict_t*d,dict_node_t*h){
printf("%lx",(unsigned long)h);
if(h){
printf("={\"");
d->prn(h->payload);
printf("\" p=%lx l=%lx r=%lx}",
(unsigned long)h->parent,
(unsigned long)h->left,
(unsigned long)h->right);
}
}

/*:38*/
#line 158 "./dict.w"

const char*dict_rcs_id= "$Id: dict.w,v 1.128 1998/10/16 20:43:58 neto Exp neto $";

/*:2*/