dict.w,v

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

head	1.128;
access
	david
	neto;
symbols
	zero-five-zero:1.128
	zero-four-seventeen:1.128
	zero-four-ten:1.127
	zero-four-nine:1.127
	zero-four-eight:1.127
	zero-four-five:1.127
	zero-four-zero:1.127;
locks
	neto:1.128;


1.128
date	98.10.16.20.43.58;	author neto;	state Exp;
branches;
next	1.127;

1.127
date	98.07.16.21.58.55;	author neto;	state Exp;
branches;
next	1.126;

1.126
date	98.06.12.22.48.21;	author neto;	state Exp;
branches;
next	1.125;

1.125
date	98.05.23.16.36.37;	author neto;	state Exp;
branches;
next	1.124;

1.124
date	98.05.21.20.28.29;	author neto;	state Exp;
branches;
next	1.123;

1.123
date	97.09.27.18.05.36;	author neto;	state Exp;
branches;
next	1.122;

1.122
date	97.08.15.20.18.25;	author neto;	state Exp;
branches;
next	1.121;

1.121
date	97.05.16.22.39.33;	author neto;	state Exp;
branches;
next	1.120;

1.120
date	97.05.16.21.30.19;	author neto;	state Exp;
branches;
next	1.119;

1.119
date	97.05.16.18.11.41;	author neto;	state Exp;
branches;
next	1.118;

1.118
date	97.05.16.18.09.40;	author neto;	state Exp;
branches;
next	1.117;

1.117
date	97.05.16.16.45.31;	author neto;	state Exp;
branches;
next	1.116;

1.116
date	97.05.16.16.34.16;	author neto;	state Exp;
branches;
next	1.115;

1.115
date	97.05.16.16.21.31;	author neto;	state Exp;
branches;
next	1.114;

1.114
date	97.05.16.16.20.20;	author neto;	state Exp;
branches;
next	1.113;

1.113
date	97.05.14.20.23.29;	author neto;	state Exp;
branches;
next	1.112;

1.112
date	97.01.27.16.35.30;	author neto;	state Exp;
branches;
next	1.111;

1.111
date	97.01.21.21.55.55;	author david;	state Exp;
branches;
next	1.110;

1.110
date	96.12.17.10.58.36;	author neto;	state Exp;
branches;
next	1.109;

1.109
date	96.08.20.11.30.14;	author neto;	state Exp;
branches;
next	1.108;

1.108
date	96.08.16.13.04.40;	author neto;	state Exp;
branches;
next	1.107;

1.107
date	96.08.15.14.14.53;	author neto;	state Exp;
branches;
next	1.106;

1.106
date	96.08.15.13.14.35;	author neto;	state Exp;
branches;
next	1.105;

1.105
date	96.08.02.14.20.24;	author neto;	state Exp;
branches;
next	1.104;

1.104
date	96.08.01.15.50.44;	author neto;	state Exp;
branches;
next	1.103;

1.103
date	96.07.29.17.09.58;	author neto;	state Exp;
branches;
next	1.102;

1.102
date	96.07.29.16.19.45;	author neto;	state Exp;
branches;
next	1.101;

1.101
date	96.06.19.14.14.57;	author neto;	state Exp;
branches;
next	1.100;

1.100
date	96.05.29.11.13.07;	author neto;	state Exp;
branches;
next	1.5;

1.5
date	96.05.24.16.44.12;	author neto;	state Exp;
branches;
next	1.4;

1.4
date	96.03.15.15.59.27;	author neto;	state Exp;
branches;
next	1.3;

1.3
date	96.03.04.14.40.18;	author neto;	state Exp;
branches;
next	1.2;

1.2
date	96.03.04.14.01.38;	author neto;	state Exp;
branches;
next	1.1;

1.1
date	96.03.04.13.53.34;	author neto;	state Exp;
branches;
next	;


desc
@Dictionary ADT.
@


1.128
log
@Fixed typo
@
text
@


\noindent Copyright \copyright 1994, 1995, 1996, 1997, 1998 David Neto
\smallskip

\noindent 
   This library is free software; you can redistribute it and/or
   modify it under the terms of the GNU Library General Public
   License as published by the Free Software Foundation; either
   version 2 of the License, or (at your option) any later version.
\smallskip

\noindent 
   This library is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
   Library General Public License for more details.
\smallskip

\noindent   
   You should have received a copy of the GNU Library General Public
   License along with this library; if not, write to the
   Free Software Foundation, Inc., 59 Temple Place - Suite 330,
   Boston, MA  02111-1307, USA.
\smallskip

\noindent   
   You may contact David Neto via email at {\tt netod@@@@acm.org}, or with
   greater latency at
\smallskip
\noindent{\obeylines
     Department of Computer Science
     University of Toronto
     10 King's College Rd.
     Toronto, Ontario
     M5S 3G4
     Canada
}
\medskip


\noindent\hbox{}\hrule\hbox{}\penalty-1000
\vskip0.5cm\relax



@@i webdefs.w
@@i types.w

{\obeylines
$Log: dict.w,v $
Revision 1.127  1998/07/16 21:58:55  neto
Added the LGPL notice in each file.

Revision 1.126  1998/06/12 22:48:21  neto
Fixed a bug.  delete min and delete max weren't returning the right
think.  (That's ok, LK wasn't using that stuff anyway...)

Revision 1.125  1998/05/23 16:36:37  neto
Get rid of unused l in delete min and delete max.
Give a value to variable here so GCC's dataflow analysis is satisfied.

Revision 1.124  1998/05/21 20:28:29  neto
Added dict size, dict delete min, dict delete max.

Revision 1.123  1997/09/27 18:05:36  neto
Fixed RCS log behaviour.

Revision 1.122  1997/08/15  20:18:25  neto
Added Index major section.

Revision 1.121  1997/05/16  22:39:33  neto
Fix the pointer print spec.

Revision 1.120  1997/05/16  21:30:19  neto
Fixed a printf spec: from integer to pointer.
(This is in dicttest).

Revision 1.119  1997/05/16  18:11:41  neto
Break locks by david and neto.
Include <config.h> and "lkconfig.h"

Revision 1.118  1997/05/16  18:09:40  neto
Include <config.h> and lkconfig.h

Revision 1.117  1997/05/16  16:45:31  neto
Make dicttest's main conform to ANSI standard by making it take
int, char ** arguments.

Revision 1.116  1997/05/16  16:34:16  neto
Removed dumb conditional in dicttest.

Revision 1.115  1997/05/16  16:21:31  neto
Dont discard const.

Revision 1.114  1997/05/16  16:20:20  neto
Add prototypes for functions in dicttest.

Revision 1.113  1997/05/14  20:23:29  neto
dicttest.w doesn't actually use resource measurement. removed.

Revision 1.112  97/01/27  16:35:30  neto
Fixed the function definition for dict\_ create

Revision 1.111  1997/01/21  21:55:55  david
Added standard copyright notice by including copyrt.w

Revision 1.110  96/12/17  10:58:36  neto
Fixed some dataflow analysis warnings.

Revision 1.109  96/08/20  11:30:14  neto
Fixed uninitialized variable l.  That was a bug.
Also fixed ggpl.  Not a bug, but a dataflow analysis warning.

Revision 1.108  96/08/16  13:04:40  neto
Added fixincludes.

Revision 1.107  96/08/15  14:14:53  neto
Adde prototype to satisfy all the warning options of GCC.

Revision 1.106  96/08/15  13:14:35  neto
Make it pass -Wall

Revision 1.105  96/08/02  14:20:24  neto
Allow others to get dict without first getting pool.

Revision 1.104  96/08/01  15:50:44  neto
Maked dict\_delete return the item it just deleted.

Revision 1.103  96/07/29  17:09:58  neto
Fixed to compile.

Revision 1.102  96/07/29  16:19:45  neto
Added *\_rcs\_id.
Made sure RCS log is activated within this file.

}

@@*Dictionaries.
This module is implements the dictionary abstract data type over
any totally ordered domain.

% Format |dict_t| as an int.
@@s dict_t int

@@ The outline of this module is as follows:
@@c
#include <config.h>
#include "lkconfig.h"
@@<System headers@@>@@;
@@<Module headers@@>@@;

@@<Module macros@@>@@;
@@<Subroutines@@>@@;
const char *dict_rcs_id = "$Id: dict.w,v 1.127 1998/07/16 21:58:55 neto Exp neto $";

@@ We will be using many routines from external libraries.  The interfaces
to those routines are described in the following headers.

@@<System headers@@>=
#include <stdio.h>
#include <stdlib.h>
#include <stddef.h>
#include <assert.h>
#include "fixincludes.h"

@@ The exported interface is contained in the \file{dict.h} header file,
which has the following form.

@@(dict.h@@>=
#if !defined(_DICT_H_)
#define _DICT_H_
@@<Headers required for the interface@@>@@;
extern const char *dict_rcs_id;
@@<Exported type definitions@@>@@;
@@<Exported subroutines@@>@@;
#endif

@@ To ensure consistency between the interface and the implementation,
we include our own header.
@@<Module headers@@>=
#include "dict.h"

@@ The interface is as follows:

|dict_t *dict_create(int (*cmp_fnc)(const void *, const void*),void (*prn_fnc)(void *))| 
takes a comparison function
and returns a new dictionary for items that may be compared with that
function.  The comparison function is the same kind as required for
the |qsort| library function.  That is, given pointers to two objects,
it should return an integer that is less than, equal to, or greater than
zero if the first object compares less than, equal to, or greater than
the second object, respectively.
For debugging purposes, we also take a node printing function.


|void dict_destroy(dict_t *d, void (*action)(void *))| 
destroys a previously created dictionary.  If |action != NULL|, then
|action| is called on every item in the dictionary.

|int dict_insert(dict_t *d,void *e)| inserts item |e| into the given dictionary.
This function returns a non-zero value if and only if the item was 
already in the dictionary.  If the item was already present, then a new
copy is {\it not} added.  You can always get around this no-duplicates
limitation
by modifying the comparison function to return the difference of the two
pointers if the pointed-to items would otherwise compare as equal.

|void *dict_find(dict_t *d,void *e)| finds any previously inserted item
which tests as equal to the given item.  If the item is found, it
returns the previously stored pointer (not necessarily the pointer
provided in this call); otherwise, NULL is returned.

|void *dict_delete(dict_t *d, void *e, void (*action)(void *))| 
deletes the item which compares equal
to the given item.  If it isn't present, then nothing happens.
If |action| is non-NULL, then it is called with the item found equal to |e|.
(This is useful for deallocation of space, for example.)
The procedure returns the entry that it deleted, if any.  Note that this
is not necessarily the same pointer value passed to it as |e|, but is
the pointer value that compared as equal to |e|.  If no entry was
deleted, then this procedure returns |NULL|.


|void dict_delete_all(dict_t *, void (*action)(void *))| 
empties the dictionary.  If |action != NULL|, then it is called on every
deleted element.

|void *dict_delete_any(dict_t *)| deletes and 
returns an arbitrary element of the dictionary.
If the dictionary is empty, then it returns |NULL|.

|void *dict_min(dict_t *)| returns the minimum element of the dictionary.
If the dictionary is empty, then it returns |NULL|.

|void *dict_delete_min(dict_t *)| returns the minimum element of the
dictionary,
removing it from the dictionary.
If the dictionary is empty, then it returns |NULL|.

|void *dict_max(dict_t *)| returns the maximum element of the dictionary.
If the dictionary is empty, then it returns |NULL|.

|void *dict_delete_max(dict_t *)| returns the maximum element of the dictionary,
removing it from the dictionary.
If the dictionary is empty, then it returns |NULL|.

|void dict_update_all(dict_t *,void (*proc)(void *env2,void **payload_p),void *env1)|,
for each item in the dictionary, calls |proc| on |env1| and a pointer to 
that item's payload pointer.  This allows update in place of all the
items in the dictionary.   Procedure |proc| must not call any of the other
dictionary routines on this dictionary.
It also must not change the relative ordering of any of the nodes.
The results are undefined if |proc| breaks either of these rules.

|size_t dict_size(dict_t *)| returns the number of elements in the
dictionary.
This is accounting is ok if the routines aren't used re-entrantly on
the same dictionary.  That is, if the destruction routine for a
dictionary
entry calls a routine modifying the entry, then this count could be wrong.
Heck all hell might break loose.


@@<Exported subroutines@@>=
dict_t *dict_create(int (*cmp_fnc)(const void *, const void*), 
		void (*prn_fnc)(void *));
void dict_destroy(dict_t *d,void (*action)(void *));
int dict_insert(dict_t *d,void *e);
void *dict_find(dict_t *d,void *e);
void *dict_delete(dict_t *d, void *e, void (*action)(void *));
void dict_delete_all(dict_t *d, void (*action)(void *));
void *dict_delete_any(dict_t *d, void (*action)(void *));
void *dict_min(dict_t *d);
void *dict_max(dict_t *d);
void *dict_delete_min(dict_t *d);
void *dict_delete_max(dict_t *d);
void dict_update_all(dict_t *d,void (*proc)(void *env2,void **payload_p),void *env1);
size_t dict_size(dict_t *d);


@@ Up front, we know we'll need interfaces to
the error checking and memory allocation
modules.

@@<Module headers@@>=
#include "error.h"
#include "memory.h"

@@*The dictionary implementation.
I'll use splay trees.  They have linear worst-case storage, and logarithmic
amortized worst-case time per operation.  
Splay trees have the added
feature that
perform very well when there is a lot of locality present in the
sequence of operations.  They adjust well to a shifting distribution of
accesses.

% Format |pool_t| as if it were an |int|.
@@s pool_t int

@@ Each dictionary consists of just a pointer to the root node, 
a pointer to the comparison function, and an optional pointer to 
a payload printing function.

Each node has pointers to its parent, its left and right children,
and the payload.

Each dictionary allocates from its own pool of memory.  We keep a pointer
to that pool.

@@<Exported type definitions@@>=

typedef struct dict_node_s {
	void *payload;
	struct dict_node_s *link[3];
} dict_node_t;

typedef struct {
	dict_node_t *root;
	int (*cmp)(const void *a, const void *b);
	void (*prn)(void *a);
	pool_t *pool;
	size_t size;
} dict_t;

@@ We need the interface for the pool-oriented allocator.  Since
part of our own interface includes a pool type, we must include the
pool interface within our own interface.

@@<Headers required for the interface@@>=
#include "pool.h"

@@ We've allocated space for three links per node.  It will be convenient
to give them the following standard names.  

I've allocated an an array instead of using the names themselves because
it will compact the code later on.

@@<Module macros@@>=
#define NILLINK (-2)	/* A nonsense value, for debugging purposes. */
#define SELF (-1)
#define PARENT (0)
#define LEFT (1)
#define RIGHT (2)
#define parent link[PARENT]
#define left link[LEFT]
#define right link[RIGHT]

@@ Creating the dictionary just means allocating and initializing a 
|dict_t| structure.

@@<Subroutines@@>=
dict_t *dict_create(int (*the_cmp)(const void *a, const void *b),void (*the_prn)(void *a)) {
	dict_t *d = new_of(dict_t);
	d->root = NULL;
	errorif(the_cmp == NULL,"Need a non-null comparison function");
	d->cmp = the_cmp;
	d->prn = the_prn;
	d->pool = pool_create(sizeof(dict_node_t),1000);
	d->size = 0;
	return d;
}

@@ Destroying the dictionary involves freeing all the nodes int the tree,
and freeing the |dict_t| structure as well.


@@<Subroutines@@>=
void
dict_destroy(dict_t *d, void (*action)(void *)) {
	if ( d != NULL ) {
		@@<Deallocate the subtree rooted at |d->root|, calling |action| on each item@@>@@;
		d->cmp = NULL;
		d->prn = NULL;
		d->root = NULL;
		pool_destroy(d->pool);
		d->pool = NULL;
		d->size = 0;
		free_mem(d);
	}
}

@@ We can traverse the entire tree non-recursively because we have parent
pointers.  This is a darn clever bit of code.  It does a post-order
traversal.

Note that this bit of code requires only constant space.  A recursive
traversal would take linear space in the worst case.  Remember that
splay trees have bad operation sequences which sometimes force them to 
into degenerate trees.

@@<Deallocate the subtree rooted at |d->root|, calling |action| on each item@@>=
{
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 { /* Deallocate the |here| node. */
		if ( action ) action(here->payload);
		prev = here;
		here = here->parent;
		pool_free(d->pool,prev);
	}
}
}


@@ We've just coded most of what is needed for |dict_delete_all|.  It does
a subset of |dict_destroy|.

@@<Subroutines@@>=
void
dict_delete_all(dict_t *d,void (*action)(void *)) {
	@@<Deallocate the subtree rooted at |d->root|, calling |action| on each item@@>@@;
	d->root = NULL;
	d->size = 0;
}

@@ We will take some care in coding  the insertion routine so that we can
reuse parts of it later.

To insert a node, we find where it should go, add it there, and then 
splay it to the root.

If there already was an item that compared equal to |e|, then we don't
add anything.

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

	next = d->root;
	@@<Find |e| in the subtree rooted at |next|@@>@@;
	if ( 0!=(was_absent = (l!=SELF)) )  {
		@@<Add |e|, and make |here| to point its node@@>@@;
		d->size++;
	}
	@@<Splay |here| to the root@@>@@;
	return !was_absent;
}

@@ To find a node, we do the usual binary search down from the root.
We do the test for equality last because it is the most likely test
to fail.  Make the common code fast, and make the fast code common.

If |e| exists in the subtree, then this code will make both |next| and |here|
point to its node, and set |l| to |SELF|.  The otherwise case
splits into two cases.  If |e| isn't in the tree because the tree
is empty, then |l| is set to something other than |SELF| and |here| is
set to |NULL|.  If |e| isn't in the tree and the tree is non-empty,
then we make
|next==NULL|, and 
|here->link[l]| is the null pointer that should point to a new node for 
|e|.

@@<Find |e| in the subtree rooted at |next|@@>=
l=PARENT;	/* Something other than |SELF|. */
for ( here = NULL; next && next != here ; ) {
	int compared_as = d->cmp(e,next->payload);
	here = next;
	if ( compared_as < 0 ) {