dict.w,v

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

	printf("Deleted %d:",i); dict_doall(d,prn); printf("\n------\n");


/* Now test the two-child delete where the right child must itself be 
replaced */
	for ( i=4;i>=0;i-- ) {
		dict_insert(d,a+i);
	}
	dict_find(d,a+3);
	dict_find(d,a+1);
	printf("Complex two-child delete:");dict_doall(d,prn);printf("\n");
	dict_delete(d,a+1,del);
	printf("Deleted %d:",1);dict_doall(d,prn);printf("\n------\n");

	dict_destroy(d,del);
	printf("\n------\nPassed all tests! (NOT EXHAUSTIVE)\n");
	return 0;
}

@@*Index.
@


1.127
log
@Added the LGPL notice in each file.
@
text
@d53 3
d156 1
a156 1
const char *dict_rcs_id = "$Id: dict.w,v 1.126 1998/06/12 22:48:21 neto Exp neto $";
d253 1
a253 1
dicitonary routines on this dictionary.
@


1.126
log
@Fixed a bug.  delete min and delete max weren't returning the right
think.  (That's ok, LK wasn't using that stuff anyway...)
@
text
@d1 47
a48 1
@@i copyrt.w
d53 4
d153 1
a153 1
const char *dict_rcs_id = "$Id: dict.w,v 1.125 1998/05/23 16:36:37 neto Exp neto $";
@


1.125
log
@Get rid of unused l in delete min and delete max.
Give a value to variable here so GCC's dataflow analysis is satisfied.
@
text
@d7 4
d103 1
a103 1
const char *dict_rcs_id = "$Id: dict.w,v 1.124 1998/05/21 20:28:29 neto Exp neto $";
d802 1
d810 1
a810 1
		void (*action)(void*)=NULL;
d814 1
d817 1
a817 1
		return m->payload;
d826 1
a826 1
		void (*action)(void*)=NULL;
d830 1
d833 1
a833 1
		return m->payload;
@


1.124
log
@Added dict size, dict delete min, dict delete max.
@
text
@d7 3
d99 1
a99 1
const char *dict_rcs_id = "$Id: dict.w,v 1.123 1997/09/27 18:05:36 neto Exp neto $";
d757 1
a757 1
		dict_node_t *next, *here, *splay_this; int l;
d804 1
a804 1
		dict_node_t *m, *next, *here, *splay_this; int l; 
d819 1
a819 1
		dict_node_t *m, *next, *here, *splay_this; int l; 
@


1.123
log
@Fixed RCS log behaviour.
@
text
@d2 1
d7 3
d96 1
a96 1
const char *dict_rcs_id = "$Id: dict.w,v 1.122 1997/08/15 20:18:25 neto Exp neto $";
d177 5
d185 4
d197 9
d217 2
d220 1
a220 1

d265 1
d302 1
d320 1
d364 1
d387 1
d666 1
d754 6
a759 2
		void *ret = d->root->payload;
		dict_delete(d,ret,action);
d782 2
a783 1
dict_max(dict_t *d) {
d793 34
d851 10
@


1.122
log
@Added Index major section.
@
text
@d4 5
a8 1
{\obeylines$Log: dict.w,v $
d92 1
a92 1
const char *dict_rcs_id = "$Id: dict.w,v 1.121 1997/05/16 22:39:33 neto Exp neto $";
@


1.121
log
@Fix the pointer print spec.
@
text
@d5 3
d88 1
a88 1
const char *dict_rcs_id = "$Id: dict.w,v 1.120 1997/05/16 21:30:19 neto Exp neto $";
d1014 2
@


1.120
log
@Fixed a printf spec: from integer to pointer.
(This is in dicttest).
@
text
@d5 4
d85 1
a85 1
const char *dict_rcs_id = "$Id: dict.w,v 1.119 1997/05/16 18:11:41 neto Exp neto $";
d913 1
a913 1
				printf("r == %x != NULL when it should be.\n", r);
@


1.119
log
@Break locks by david and neto.
Include <config.h> and "lkconfig.h"
@
text
@d5 4
d81 1
a81 1
const char *dict_rcs_id = "$Id: dict.w,v 1.118 1997/05/16 18:09:40 neto Exp neto $";
d909 1
a909 1
				printf("r == %d != NULL when it should be.\n", r);
@


1.118
log
@Include <config.h> and lkconfig.h
@
text
@d5 3
d77 1
a77 1
const char *dict_rcs_id = "$Id: dict.w,v 1.117 1997/05/16 16:45:31 neto Exp neto $";
@


1.117
log
@Make dicttest's main conform to ANSI standard by making it take
int, char ** arguments.
@
text
@d5 4
d67 2
d74 1
a74 1
const char *dict_rcs_id = "$Id: dict.w,v 1.116 1997/05/16 16:34:16 neto Exp neto $";
@


1.116
log
@Removed dumb conditional in dicttest.
@
text
@d5 3
d68 1
a68 1
const char *dict_rcs_id = "$Id: dict.w,v 1.115 1997/05/16 16:21:31 neto Exp neto $";
d818 1
a818 1
int main(void);
d837 1
a837 1
main(void) 
@


1.115
log
@Dont discard const.
@
text
@d5 3
d65 1
a65 1
const char *dict_rcs_id = "$Id: dict.w,v 1.114 1997/05/16 16:20:20 neto Exp neto $";
d892 2
a893 1
			if ( r != NULL,"r == %d != NULL", r) {
@


1.114
log
@Add prototypes for functions in dicttest.
@
text
@d5 3
d62 1
a62 1
const char *dict_rcs_id = "$Id: dict.w,v 1.113 1997/05/14 20:23:29 neto Exp neto $";
d817 1
a817 1
	return (*(int *)a)-(*(int *)b);
@


1.113
log
@dicttest.w doesn't actually use resource measurement. removed.
@
text
@d4 4
a7 1
{\obeylines$Log:	dict.w,v $
d59 1
a59 1
const char *dict_rcs_id = "$Id: dict.w,v 1.112 97/01/27 16:35:30 neto Exp Locker: neto $";
d806 8
a813 2
int
intcmp(const void *a, const void *b) {
d817 2
a818 1
void prn(void *a) {
d821 3
a823 1
void del(void *a) {
d827 3
a829 1
int main(void) {
@


1.112
log
@Fixed the function definition for dict\_ create
@
text
@d4 4
a7 1
{\obeylines$Log: dict.w,v $
d56 1
a56 1
const char *dict_rcs_id = "$Id: dict.w,v 1.111 1997/01/21 21:55:55 david Exp david $";
a798 1
#include "resource.h"
a818 1
	resource_setup(5);
@


1.111
log
@Added standard copyright notice by including copyrt.w
@
text
@d4 4
a7 1
{\obeylines$Log:	dict.w,v $
d53 1
a53 1
const char *dict_rcs_id = "$Id: dict.w,v 1.110 96/12/17 10:58:36 neto Exp $";
d231 1
a231 3
dict_t *
dict_create(int the_cmp(const void *a, const void *b), 
			void (*the_prn)(void *a)) {
@


1.110
log
@Fixed some dataflow analysis warnings.
@
text
@d5 3
d50 1
a50 1
const char *dict_rcs_id = "$Id: dict.w,v 1.109 96/08/20 11:30:14 neto Exp Locker: neto $";
@


1.109
log
@Fixed uninitialized variable l.  That was a bug.
Also fixed ggpl.  Not a bug, but a dataflow analysis warning.
@
text
@d5 4
d47 1
a47 1
const char *dict_rcs_id = "$Id: dict.w,v 1.108 96/08/16 13:04:40 neto Exp $";
d377 1
a377 1
	dict_node_t *p, *gp, *ggp; /* Parent, grandparent, and great-grandparent */
d607 7
d616 1
d620 1
a620 1
	else { errorif(1,"Bug"); l=NILLINK; /* Satisfy the GCC dataflow analysis. */}
@


1.108
log
@Added fixincludes.
@
text
@d5 3
d43 1
a43 1
const char *dict_rcs_id = "$Id: dict.w,v 1.107 96/08/15 14:14:53 neto Exp $";
d208 1
d322 6
a327 1
point to its node, and set |l| to |SELF|.  Otherwise, |next==NULL|, and 
d332 1
d374 3
a376 1
	int pl, gpl,ggpl;	/* Parent and grandparent links down to |here|. */
d488 7
a494 2
if ( ggp ) { SETLINK(ggp,ggpl,here); }
else { here->parent = NULL; d->root = here; }
d608 1
a608 1
	else { errorif(1,"Bug"); }
@


1.107
log
@Adde prototype to satisfy all the warning options of GCC.
@
text
@d5 3
d40 1
a40 1
const char *dict_rcs_id = "$Id: dict.w,v 1.106 96/08/15 13:14:35 neto Exp $";
d50 1
@


1.106
log
@Make it pass -Wall
@
text
@d5 3
d37 1
a37 1
const char *dict_rcs_id = "$Id: dict.w,v 1.105 96/08/02 14:20:24 neto Exp $";
d711 1
@


1.105
log
@Allow others to get dict without first getting pool.
@
text
@d5 3
d34 1
a34 1
const char *dict_rcs_id = "$Id: dict.w,v 1.104 96/08/01 15:50:44 neto Exp $";
d299 1
a299 1
	if ( was_absent = (l!=SELF) )  {
d549 1
a549 1
int l,pl;
d728 1
a728 1
	printf("%x",h);
d732 4
a735 1
		printf("\" p=%x l=%x r=%x}",h->parent, h->left, h->right);
@


1.104
log
@Maked dict\_delete return the item it just deleted.
@
text
@d5 3
a26 1
@@<Early module headers@@>@@;
d31 1
a31 1
const char *dict_rcs_id = "$Id: dict.w,v 1.103 96/07/29 17:09:58 neto Exp $";
d46 3
d52 1
a58 1

d181 5
a185 2
@@ We need the interface for the pool-oriented allocator.
@@<Early module headers@@>=
@


1.103
log
@Fixed to compile.
@
text
@d5 3
d29 1
a29 1
const char *dict_rcs_id = "$Id: dict.w,v 1.102 96/07/29 16:19:45 neto Exp $";
d84 1
a84 1
|void dict_delete(dict_t *d, void *e, void (*action)(void *))| 
d89 4
d94 1
d123 1
a123 1
void dict_delete(dict_t *d, void *e, void (*action)(void *));
d521 1
a521 1
void 
d523 1
a523 1
	dict_node_t *next, *here, *splay_this;
d527 1
d530 1
@


1.102
log
@Added *\_rcs\_id.
Made sure RCS log is activated within this file.
@
text
@d4 5
a8 1
{\obeylines$Log$
a19 1
const char dict_rcs_id[] = "$Id$";
d26 1
d41 1
a41 1
extern const char dict_rcs_id[] = "$Id$";
@


1.101
log
@Added dict_update_all.
@
text
@a0 1

d2 1
d4 3
d16 1
d37 1
d45 1
@


1.100
log
@This version works.  
Needs improvement:
	command-line switches
	faster tabu check
	allow Papadimitriou tabu rule
	faster preprocessing
	different candidate lists
@
text
@d91 8
d110 1
d648 25
@


1.5
log
@Cosmetic changes mostly.
Moved a couple of routines to the supported section.
Added braces in one place.
@
text
@@


1.4
log
@Initial implementation of LK.  This is buggy.
@
text
@d8 3
d61 4
a64 1
copy is {\it not} added.
d99 3
d122 3
d250 1
a250 1
add anything
d541 1
a541 1
if ( ep ) 
d545 1
d570 1
d598 2
a599 1
@@ The |dict_any| routine just returns the root node.  This is easy.
a638 5
@@ We must declare these functions.
@@<Exported subroutines@@>=
void *dict_delete_any(dict_t *d, void (*action)(void *));
void *dict_min(dict_t *d);
void *dict_max(dict_t *d);
@


1.3
log
@Fixed a TeX error.
@
text
@d11 1
d75 10
d120 3
d134 1
d137 4
d168 1
d184 2
a211 1
		dict_node_t *freed_node;
d213 1
a213 1
		freed_node = prev = here;
d215 1
a215 1
		free_mem(freed_node);	/* Doh!  |free_mem| sets the lvalue to NULL. */
d284 1
a284 1
	dict_node_t *node = new_of(dict_node_t);
d484 2
a485 3
	dict_node_t *next, *here, *e_node, *ep, *splay_this;
	int l,pl;

d488 1
a488 18
	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);
		free_mem(e_node);
		here = splay_this;
	}
d492 26
d584 46
d671 2
d675 1
@


1.2
log
@Added test code.
@
text
@d405 2
a406 2
$$((1A2)b3) \becomes (1A(2b3))$
$$(1a(2B3)) \becomes ((1a2)B3)$
@


1.1
log
@Initial revision
@
text
@d589 1
a589 1
dict_doall(dict_t *d, void (*action)(void *));
d591 1
a591 1
dict_show_node(dict_t *d,dict_node_t *h);
d593 8
d602 170
@