dict.w,v

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

		next = here->link[l=LEFT];
	} else if ( compared_as > 0 ) {
		next = here->link[l=RIGHT];
	} else if ( compared_as == 0 ) {
		l = SELF;
		break;
	}
}


@@ We need to allocate a node for |e|, and set the pointers properly.

@@<Add |e|, and make |here| to point its node@@>=
{
	dict_node_t *node = (dict_node_t*)pool_alloc(d->pool);
	node->payload = e;
	node->left = node->right = NULL;
	node->parent = here;
	if ( here == NULL ) d->root = node;
	else here->link[l] = node;
	here = node;
}

@@ Splaying a node to the root is the only feature of splay trees over ordinary
binary trees.  It was described and analysed by Sleator and Tarjan (insert
reference!!!).

For now, all you have to know about splaying a node to the root is that it
is a sequence of splay operations.  Each splay operation moves the current
node up two levels (or only one if the current node is at depth 1 in the
tree) while maintaining the left-to right (or in-order traversal order) 
order of the nodes.   


@@<Splay |here| to the root@@>=
if (here) {
	dict_node_t *p, *gp, *ggp=NULL; /* Parent, grandparent, and great-grandparent */
	int pl, gpl; /* Parent and grandparent links down to |here|. */
	int ggpl=NILLINK;	/* Great grandparent link.   Initialized to nonsense
		value to satisfy GCC's data flow analysis. */
	dict_node_t *subtree[2];	/* Subtrees that are moved */
	do {
		errorif(here==NULL,"|here| must not be NULL");
		@@<Name the links, |break| if done@@>@@;
		@@<Splay |here| up once@@>@@;
	} while (1);
}

@@ Here we initialize all the pointers to parents, grandparents,
and determine which pointers came from where.

@@<Name the links, |break| if done@@>=
gpl = pl = SELF;	/* Something that isn't LEFT or RIGHT */
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;
}


@@ There are six cases in splaying a node up: two when |here| is at depth 1
in the tree, and four when |here| is deeper.

The SETLINK macro will be very handy.

@@d SETLINK(N,L,C) { (N)->link[L] = (C); if (C) (C)->parent = (N); }

@@<Splay |here| up once@@>=
if ( gp ) {
	@@<Splay |here| up two levels@@>@@;
} else {
	@@<Splay |here| up one level to the root@@>@@;
}

@@ The two level case is the common case.  


The description so far isn't quite enough to derive
all the details of the splay operation.  There are still at least two choices 
in how to rearrange the tree.  The following rewrite rules define
the ``right'' way to do it, \ie, the way that makes the amortized analysis
work out.  (In each case, the capitalized-letter node is the one that
is being splayed.)

\def\becomes{\rightarrow}
$$(((1A2)b3)c4) \becomes (1A(2b(3c4)))$$
$$((1a(2B3))c4) \becomes ((1a2)B(3c4))$$
$$(1a((2B3)c4)) \becomes ((1a2)B(3c4))$$
$$(1a(2b(3C4))) \becomes (((1a2)b3)C4)$$

In coding this transformation, we must be careful in case
the splayed node becomes the new root.

@@<Splay |here| up two levels@@>=
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; }


@@ Splaying up one level is simpler.  It is a simple rotation.

Here are its rewrite rules:
$$((1A2)b3) \becomes (1A(2b3))$$
$$(1a(2B3)) \becomes ((1a2)B3)$$

@@<Splay |here| up one level to the root@@>=
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;

@@ Procedure |dict_find| is much the same as |dict_insert|, except we
skip the insertion.

@@<Subroutines@@>=
void *
dict_find(dict_t *d,void *e) {
	dict_node_t *here, *next;
	int l;	/* The link where |e| goes. */
	void *found = NULL;

	next = d->root;
	@@<Find |e| in the subtree rooted at |next|@@>@@;
	if ( next != NULL ) {
		found = next->payload;
	}
	@@<Splay |here| to the root@@>@@;
	return found;
}

@@ Now we can get to the deletion routine.

This works much like the |dict_find| routine, except that we remove the
item if it is present.  We must take care to keep the subtrees that were
its children.  

In more detail, there are three cases:

If we delete a leaf, then splay its parent.

If we delete a node with one child, then replace the deleted node by its
child and splay that child.

If we delete a node with two children, then move the smallest node in the right
subtree in place of the deleted node.  Then splay the old parent of that
leaf we promoted.

@@<Subroutines@@>=
void *
dict_delete(dict_t *d, void *e, void (*action)(void *)) {
	dict_node_t *next, *here, *splay_this; void *deleted_payload=NULL;
	int l;
	next = d->root;
	@@<Find |e| in the subtree rooted at |next|@@>@@;
	if ( next ) deleted_payload = next->payload;
	@@<If |next| isn't |NULL|, delete it@@>@@;
	@@<Splay |here| to the root@@>@@;
	return deleted_payload;
}

@@ This is the first level of the nitty gritty of deleting
the node.
@@<If |next| isn't |NULL|, delete it@@>=
{ 
dict_node_t *e_node, *ep;
int l;
e_node = next;
if ( e_node ) {
	if ( e_node->left == NULL && e_node->right == NULL ) {
		@@<Remove the leaf |e_node|@@>@@;
		splay_this = e_node->parent;
	} else if ( e_node->left == NULL ) {
		@@<Promote |e_node->right|@@>@@;
		splay_this = e_node->right;
	} else if ( e_node->right == NULL ) {
		@@<Promote |e_node->left|@@>@@;
		splay_this = e_node->left;
	} else {
		@@<Replace |e_node| by a merge of its two children@@>@@;
	}
	if ( action ) action(e_node->payload);
	pool_free(d->pool,e_node);
	d->size--;
	here = splay_this;
}
}

@@ This is simple surgery.  It is tricky only because |e_node| may be the root.
@@<Remove the leaf |e_node|@@>=
@@<Name the parent and its link@@>@@;
if ( ep ) { ep->link[l]=NULL; }
else { d->root = NULL; }



@@ Here we do a shallower version of what was needed in the splaying routine.

After this section is executed, 
the value of |l| is used only if |ep!=NULL|, \ie, |e_node| is the root node.
Unfortunately, GCC's dataflow analysis isn't smart enough to detect this.
So we eliminate the dataflow analysis warning by assigning a garbage
value |NILLINK| to |l| right away.

@@<Name the parent and its link@@>=
ep = e_node->parent;
l=NILLINK; /* Satisfy GCC's dataflow analysis. */
if ( ep ) {
	if ( ep->left == e_node ) l = LEFT;
	else if ( ep->right == e_node ) l = RIGHT;
	else { errorif(1,"Bug"); }
}

@@ Promoting |e_node|'s right child is only tricky because we need to take
care of the case when |e_node| is the root.

@@<Promote |e_node->right|@@>=
@@<Name the parent and its link@@>@@;
if ( ep ) { SETLINK(ep,l,e_node->right); }
else { e_node->right->parent = NULL; d->root = e_node->right; }

@@ Promoting |e_node|'s left child is symmetrical to the right case.
@@<Promote |e_node->left|@@>=
@@<Name the parent and its link@@>@@;
if ( ep ) { SETLINK(ep,l,e_node->left); }
else { e_node->left->parent = NULL; d->root = e_node->left; }

@@ The tough case is when |e_node| has two children.  

Move the smallest node in the right
subtree in place of the deleted node.  Then splay the old parent of that
leaf we promoted.

The difficulty with this is that the leftmost node in the right
subtree might itself have a right child (but it certainly won't have
a left child).  So we may need to promote that right child of that leftmost
node in that right subtree.


@@<Replace |e_node| by a merge of its two children@@>=
{	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;
	@@<Promote |e_node->right|@@>@@;
	e_node = save_e_node;

	/* Now put |erL| in place of |e_node| */
	SETLINK(erL,LEFT,e_node->left);
	if ( e_node->right != erL ) { SETLINK(erL,RIGHT,e_node->right);	}
/* |e_node->right| may have changed with the promotion!  
But it's ok because |e_node| is a pointer. */
	@@<Name the parent and its link@@>@@;
	if ( ep ) { SETLINK(ep,l,erL); }
	else { erL->parent = NULL; d->root = erL; }
}

@@ The |dict_delete_any| routine 
just deletes and returns the root node.  This is easy.

@@<Subroutines@@>=
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;
		@@<If |next| isn't |NULL|, delete it@@>@@;
		@@<Splay |here| to the root@@>@@;
		return ret;
	} else return NULL;
}

@@ The |dict_min| routine is almost as easy.

@@<Subroutines@@>=
void *
dict_min(dict_t *d) {
	dict_node_t *here;
	if ( d->root ) {
		for ( here=d->root ; here->left ; here = here->left )
			;
		@@<Splay |here| to the root@@>@@;
		return here->payload;
	} else return NULL;
}

@@ The |dict_max| routine is much the same.

@@<Subroutines@@>=
void *
dict_max(dict_t *d) 
{
	dict_node_t *here;
	if ( d->root ) {
		for ( here=d->root ; here->right ; here = here->right )
			;
		@@<Splay |here| to the root@@>@@;
		return here->payload;
	} else return NULL;
}

@@ The |dict_delete_min| and |dict_delete_max| routines are combinations
of what we've already seen.

@@<Subroutines@@>=

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;
		@@<If |next| isn't |NULL|, delete it@@>@@;
		@@<Splay |here| to the root@@>@@;
		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;
		@@<If |next| isn't |NULL|, delete it@@>@@;
		@@<Splay |here| to the root@@>@@;
		return payload;
	} else return NULL;
}

@@ The update procedure does a post-order traversal of the tree, calling
|proc| at each node.  (Hint: most of this code is stolen from the
|dict_delete_all| routine.)

@@<Subroutines@@>=
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 { /* Visit the |here| node . */
		proc(env1,&(here->payload));
		prev = here;
		here = here->parent;
	}
}
}

@@ As for returning the number of elements in the dictionary, the
|dict_insert|, |dict_delete|, |dict_destroy|, |dict_create|, and
|dict_delete_all| routines do all the hard work.
@@<Subroutines@@>=
size_t 
dict_size(dict_t *d)
{
	return d->size; 
}

@@* Debugging routines.
@@<Subroutines@@>=

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);
	}
}

@@
@@<Exported subroutines@@>=
void
dict_doall(dict_t *d, void (*action)(void *));   /* Unsupported! */
void
dict_show_node(dict_t *d,dict_node_t *h);		/* Unsupported! */

@@ The following program tests this module, though certainly not exhaustively.
@@(dicttest.c@@>=
#include <stdio.h>
#include <stdlib.h>
#include <stddef.h>
#include "error.h"
#include "memory.h"
#include "pool.h"
#include "dict.h"
#include "gb_flip.h"

#define N 5

static int intcmp(const void *a, const void *b);
static void prn(void *a);
static void del(void *a);
int main(int, char **);

static int
intcmp(const void *a, const void *b) 
{
	return (*(const int *)a)-(*(const int *)b);
}

void prn(void *a) 
{
	printf("%d",*(int *)a);
}
static void 
del(void *a) 
{
	printf("freeing integer %d\n",*(int *)a);
}

int 
main(int argc, char **argv) 
{
	int i;
	int a[N];
	dict_t *d;
	d = dict_create(intcmp,prn);
	printf("Empty is:\n"); dict_doall(d,prn); printf("\n");

	for ( i=0; i<N; i++ ) {
		a[i] = i;
		dict_insert(d,a+i);
		printf("Inserted %d:",i);
		dict_doall(d,prn);
		printf("\n-------\n");
	}
	printf("All built");
	dict_doall(d,prn);
	printf("\n-------\n");

	i = 7;
	dict_find(d,&i);
	printf("After find %d: ",i);dict_doall(d,prn);printf("\n------\n");

	for ( i=N-1;i>-1;i--) {
		int *r = dict_find(d,&i);
		printf("i==%d a+i == %x r == %x\n",i,(int)(a+i), (int)r);
		printf("  ");dict_doall(d,prn);printf("\n------\n");
	}

	i = 2;
	dict_find(d,&i);
	printf("After find %d: ",i);dict_doall(d,prn);printf("\n------\n");

	i = N*2;
	printf("About to dict_find(%d)\n",i);
	errorif( dict_find(d,&i) != NULL, "Should have returned NULL" );
	dict_doall(d,prn);
	printf("\n------\n");

	i = -N*2;
	printf("About to dict_find(%d)\n",i);
	errorif( dict_find(d,&i) != NULL, "Should have returned NULL" );
	dict_doall(d,prn);
	printf("\n------\n");

/* Randomized testing */
	gb_init_rand(42L);
	for ( i=0;i<N*N;i++) {
		int j, *r;
		j = gb_unif_rand((long)N*2)-N/2;
		r = dict_find(d,&j);
		if ( 0 <= j && j < N ) {
			if ( a+j != r ) {
printf("%d j==%d a+j == %x r == %x\n",i,j,(int)(a+j), (int)r);
printf("  ");dict_doall(d,prn);printf("\n------\n");
				errorif(1,"BUG");
			}
		} else {
			if ( r != NULL) {
				printf("r == %p != NULL when it should be.\n", (void *)r);
printf("%d j==%d a+j == %x r == %x\n",i,j,(int)(a+j), (int)r);
printf("  ");dict_doall(d,prn);printf("\n------\n");
			}
		}
	}

/* Bare long left */
	dict_delete_all(d,NULL);
	for (i=0;i<3;i++) dict_insert(d,a+i);
	i=1;dict_find(d,&i);
	i=2;dict_find(d,&i);
	printf("Bare long left bottom:");dict_doall(d,prn);printf("\n");
	i=0; dict_delete(d,&i,del);
	printf("Deleted %d:",i); dict_doall(d,prn); printf("\n------\n");

	dict_delete_all(d,NULL);
	for (i=0;i<3;i++) dict_insert(d,a+i);
	i=1;dict_find(d,&i);
	i=2;dict_find(d,&i);
	printf("Bare long left middle:");dict_doall(d,prn);printf("\n");
	i=1; dict_delete(d,&i,del);
	printf("Deleted %d:",i); dict_doall(d,prn); printf("\n------\n");

	dict_delete_all(d,NULL);
	for (i=0;i<3;i++) dict_insert(d,a+i);
	i=1;dict_find(d,&i);
	i=2;dict_find(d,&i);
	printf("Bare long left top:");dict_doall(d,prn);printf("\n");
	i=2; dict_delete(d,&i,del);
	printf("Deleted %d:",i); dict_doall(d,prn); printf("\n------\n");

/* Bare long right */
	dict_delete_all(d,NULL);
	for (i=0;i<3;i++) dict_insert(d,a+i);
	i=2;dict_find(d,&i);
	i=1;dict_find(d,&i);
	i=0;dict_find(d,&i);
	printf("Bare long right bottom:");dict_doall(d,prn);printf("\n");
	i=2; dict_delete(d,&i,del);
	printf("Deleted %d:",i); dict_doall(d,prn); printf("\n------\n");

	dict_delete_all(d,NULL);
	for (i=0;i<3;i++) dict_insert(d,a+i);
	i=2;dict_find(d,&i);
	i=1;dict_find(d,&i);
	i=0;dict_find(d,&i);
	printf("Bare long right middle:");dict_doall(d,prn);printf("\n");
	i=1; dict_delete(d,&i,del);
	printf("Deleted %d:",i); dict_doall(d,prn); printf("\n------\n");

	dict_delete_all(d,NULL);
	for (i=0;i<3;i++) dict_insert(d,a+i);
	i=2;dict_find(d,&i);
	i=1;dict_find(d,&i);
	i=0;dict_find(d,&i);
	printf("Bare long right top:");dict_doall(d,prn);printf("\n");
	i=0; dict_delete(d,&i,del);
	printf("Deleted %d:",i); dict_doall(d,prn); printf("\n------\n");

/* Bare balanced */
	dict_delete_all(d,NULL);
	for (i=0;i<3;i++) dict_insert(d,a+i);
	i=1;dict_find(d,&i);
	printf("Bare balanced left:");dict_doall(d,prn);printf("\n");
	i=0; dict_delete(d,&i,del);
	printf("Deleted %d:",i); dict_doall(d,prn); printf("\n------\n");

	dict_delete_all(d,NULL);
	for (i=0;i<3;i++) dict_insert(d,a+i);
	i=1;dict_find(d,&i);
	printf("Bare balanced middle:");dict_doall(d,prn);printf("\n");
	i=1; dict_delete(d,&i,del);
	printf("Deleted %d:",i); dict_doall(d,prn); printf("\n------\n");

	dict_delete_all(d,NULL);
	for (i=0;i<3;i++) dict_insert(d,a+i);
	i=1;dict_find(d,&i);
	printf("Bare balanced right:");dict_doall(d,prn);printf("\n");
	i=2; dict_delete(d,&i,del);