dict.c

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

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 703 "./dict.w"

return deleted_payload;
}

/*:25*//*32:*/
#line 813 "./dict.w"

void*
dict_delete_any(dict_t*d,void(*action)(void*)){
if(d->root){
dict_node_t*next,*here= NULL,*splay_this;
void*ret;
next= d->root;
ret= next->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 821 "./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 822 "./dict.w"

return ret;
}else return NULL;
}

/*:32*//*33:*/
#line 829 "./dict.w"

void*
dict_min(dict_t*d){
dict_node_t*here;
if(d->root){
for(here= d->root;here->left;here= here->left)
;
/*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 836 "./dict.w"

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

/*:33*//*34:*/
#line 843 "./dict.w"

void*
dict_max(dict_t*d)
{
dict_node_t*here;
if(d->root){
for(here= d->root;here->right;here= here->right)
;
/*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"