set.c

常用数据结构算法代码库

/****************************************************************************
*
*					Copyright (C) 1991 Kendall Bennett.
*							All rights reserved.
*
* Filename:		$RCSfile: set.c $
* Version:		$Revision: 1.4 $
*
* Language:		ANSI C
* Environment:	any
*
* Description:	Module to implement bit oriented set maniuplation.
*
* $Id: set.c 1.4 91/12/31 19:40:33 kjb Exp $
*
* Revision History:
* -----------------
*
* $Log:	set.c $
* Revision 1.4  91/12/31  19:40:33  kjb
* Modified include file directories
* 
* Revision 1.3  91/09/03  18:28:26  ROOT_DOS
* Ported to UNIX.
* 
* Revision 1.2  91/09/01  01:14:33  ROOT_DOS
* Changed search for include files to look in current directory
* 
* Revision 1.1  91/08/16  13:28:48  ROOT_DOS
* Initial revision
* 
****************************************************************************/

#include <stdio.h>
#include <malloc.h>
#include <ctype.h>
#include <signal.h>
#include <string.h>
#include "debug.h"
#include "set.h"

PUBLIC SET *newset(void)
/****************************************************************************
*
* Function:		newset
* Returns:		Pointer to the set, NULL upon error.
*
* Description:	Creates a new set and returns a pointer to it. If an error
*				occurs, and error message is output and SIGABRT is raised.
*				NULL is returned if raise() returns.
*
****************************************************************************/
{
	SET	*p;

	if (!(p = (SET *)malloc( sizeof(SET)))) {
		fprintf(stderr,"Can't get memory to create set\n");
		raise(SIGABRT);
		return NULL;			/* Usually won't get here */
		}

	memset(p, 0, sizeof(SET));
	p->map = p->defmap;
	p->nwords = _DEFWORDS;
	p->nbits = _DEFBITS;
	return p;
}

PUBLIC void delset(SET *set)
/****************************************************************************
*
* Function:		delset
* Parameters:	set		- Set to delete
*
* Description:	Delete's a set previously created with a call to newset.
*
****************************************************************************/
{
	if (set->map != set->defmap)
		free(set->map);
	free(set);
}

PUBLIC SET *dupset(SET *set)
/****************************************************************************
*
* Function:		dupset
* Parameters:	set		- Set to duplicate
* Returns:		Pointer to the duplicated set
*
* Description:	Create a new set that has the same members as the input set.
*
****************************************************************************/
{
	SET		*new;

	if (!(new = (SET *)malloc(sizeof(SET)))) {
		fprintf(stderr,"Can't get memory to duplicate set\n");
		return NULL;
		}

	memset(new,0,sizeof(SET));
	new->compl = set->compl;
	new->nwords = set->nwords;
	new->nbits = set->nbits;

	if (set->map == set->defmap) {				/* Default bit map in use */
		new->map = new->defmap;
		memcpy(new->defmap,set->defmap, _DEFWORDS * sizeof(_SETTYPE));
		}
	else {
		new->map = (_SETTYPE *)malloc(set->nwords * sizeof(_SETTYPE));
		if (!new->map) {
			fprintf(stderr,"Can't get memory to duplicate set bit map\n");
			return NULL;
			}
		memcpy(new->map, set->map, set->nwords * sizeof(_SETTYPE));
		}
	return new;
}

PRIVATE void enlarge(int need,SET *set)
/****************************************************************************
*
* Function:		enlarge
* Parameters:	need	- Number of words required (total)
*				set		- The set to enlarge
*
* Description:	Enlarge the set to "need" words, filling in the extre words
*				with zeros. Prints an error message and aborts by calling
*				exit() if there's not enough memory. This routine calls
*				malloc and is hence slow and should be avoided. if possible.
*
****************************************************************************/
{
	_SETTYPE	*new;

	if (!set || need <= set->nwords)
		return;

	D(printf("enlarging %d word map to %d words\n", set->nwords,need);)

	if ( !(new = (_SETTYPE *) malloc(need * sizeof(_SETTYPE))) )
	{
		fprintf(stderr,"Can't get memory to expand set\n");
		return;
	}
	memcpy(new, set->map, set->nwords * sizeof(_SETTYPE));
	memset(new + set->nwords, 0, (need - set->nwords) * sizeof(_SETTYPE));

	if (set->map != set->defmap)
		free(set->map);

	set->map = new;
	set->nwords = (unsigned char)need;
	set->nbits = need * _BITS_IN_WORD;
}

PUBLIC int _addset(SET *set,int bit)
/****************************************************************************
*
* Function:		addset
* Parameters:	set		- Set to add element to
*				bit		- Element to add to the set
*
* Description:	Called by the ADD() macro when the set isn't big enough to
*				hold the element being added. It exands the set to the
*				necessary size and sets the indicated bit.
*
****************************************************************************/
{
	enlarge(_ROUND(bit),set);
	return _GBIT(set,bit, |= );
}

PUBLIC int num_ele(SET *set)
/****************************************************************************
*
* Function:		num_ele
* Parameters:	set		- Set to determine cardinality of
* Returns:		Cardinality of the set (number of elements)
*
* Description:	Returns the number of element (nonzero bits) in the set.
*				NULL sets are considered empty. nbits[] is indexed by any
*				number in the range 0-255, and it evalulates to the number
*				of bits in the number.
*
****************************************************************************/
{
	static unsigned char nbits[] = {
		/*   0-15  */	0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
		/*  16-31  */	1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
		/*  32-47  */	1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
		/*  48-63  */	2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
		/*  64-79  */	1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
		/*  80-95  */	2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
		/*  96-111 */	2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
		/* 112-127 */	3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
		/* 128-143 */	1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
		/* 144-159 */	2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
		/* 160-175 */	2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
		/* 176-191 */	3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
		/* 192-207 */	2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
		/* 208-223 */	3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
		/* 224-239 */	3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
		/* 240-255 */	4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8,
		};

	int				i;
	unsigned int	count = 0;
	unsigned char	*p;

	if (!set)
		return 0;

	p = (unsigned char *)set->map;

	for( i = _BYTES_IN_ARRAY(set->nwords); --i >= 0 ;)
		count += nbits[*p++];

	return count;
}

PUBLIC int _set_test(SET *set1,SET *set2)
/****************************************************************************
*
* Function:		_set_test
* Parameters:	set1	- First set to test
*				set2	- Second set to test
* Returns:		Result of the test
*
* Description:	Compares two sets. Returns the following codes:
*
* 					_SET_EQUIV		Sets are equivalent
*					_SET_INTER		Sets intersect but aren't equivalent
*					_SET_DISJ		Sets are disjoint
*
*				The smaller set is made larger if the two sets are of
*				differing sizes.
*
****************************************************************************/
{
	int			i, rval = _SET_EQUIV;
	int			intersect = 0;
	_SETTYPE	*p1,*p2;

	i = MAX( set1->nwords, set2->nwords);

	enlarge(i,set1);			/* Make the sets the same size */
	enlarge(i,set2);

	p1 = set1->map;
	p2 = set2->map;

	for (; --i >= 0; p1++,p2++) {
		if (*p1 != *p2) {
			/* You get here if the sets aren't equivalent. You can return
			 * immediately if the sets intersect but have to keep going in
			 * the case of disjoint sets (because the sets might actually
			 * intersect at some byte, as yet unseen).
			 */

			if (intersect || (*p1 & *p2))
				return _SET_INTER;
			else
				rval = _SET_DISJ;
			}
		else {
			/* If the words that we are currently testing are equal, then
			 * we must test whether they actually contain members. If they
			 * do, then we must assume that they also intersect (equivalent
			 * sets that are not empty MUST intersect!). Then we can test
			 * this value above, to ensure that we return with a value of
			 * _SET_INTER even when the sets intersect at words previously
			 * checked, and not in the word we are currently checking!
			 */

			intersect = (*p1 != 0) || intersect;
			}
		}

	return rval;				/* They're equivalent or disjoint */
}