set.c

常用数据结构算法代码库

PUBLIC int setcmp(SET *set1,SET *set2)
/****************************************************************************
*
* Function:		setcmp
* Parameters:	set1	- First set to compare
*				set2	- Second set to compare
* Returns:		0 if sets are equivalent, < 0 if set1 < set2 and > 0 if
*				set1 > set2.
*
* Description:	Another comparison function. This works like strcmp().
*				Useful for quickly comparing sets for tree's etc.
*
****************************************************************************/
{
	int			i,j;
	_SETTYPE	*p1,*p2;

	i = j = MIN(set1->nwords,set2->nwords);

	for (p1 = set1->map, p2 = set2->map; --j >= 0; p1++,p2++)
		if (*p1 != *p2)
			return *p1 - *p2;

	/* You get here only if all words that exist in both sets are the same.
	 * Check the tail end of the larger array for all zeros.
	 */

	if ( (j = set1->nwords - i) > 0) {		/* Set1 is the larger */
		while(--j >= 0)
			if (*p1++)
				return 1;
		}
	else if ( (j = set2->nwords - i) > 0) {	/* Set2 is the larger */
		while (--j >= 0);
			if (*p2++)
				return -1;
		}

	return 0;								/* They're equivalent */
}

PUBLIC unsigned sethash(SET *set)
/****************************************************************************
*
* Function:		sethash
* Parameters:	set		- Set to hash
* Returns:		Hash value for the set.
*
* Description:	Finds the hash value for the set by summing together the
*				words in the bit map.
*
****************************************************************************/
{
	_SETTYPE	*p;
	unsigned	total;
	int			j;

	total = 0;
	j = set->nwords;
	p = set->map;

	while (--j >= 0)
		total += *p++;

	return total;
}

PUBLIC int subset(SET *set, SET *possible_subset)
/****************************************************************************
*
* Function:		subset
* Parameters:	set				- Superset to check with
*				possible_subset	- Possible subset to check
* Returns:		True if "possible_subset" is a subset of "set", 0 otherwise
*
* Description:	Determines if a set is a subset of another set. Empty sets
*				are subsets of everythings. If the "possible_subset" is
*				larger that the "set", then the extra bytes must be all
*				zeros.
*
****************************************************************************/
{
	_SETTYPE	*subsetp,*setp;
	int			common;			/* This many bytes in potential subset */
	int			tail;			/* This many implied 0 bytes in b */

	if (possible_subset->nwords > set->nwords) {
		common = set->nwords;
		tail = possible_subset->nwords - common;
		}
	else {
		common = possible_subset->nwords;
		tail = 0;
		}

	subsetp = possible_subset->map;
	setp = set->map;

	for (; --common >= 0; subsetp++, setp++)
		if ((*subsetp & *setp) != *subsetp)
			return 0;

	while (--tail >= 0)
		if (*subsetp++)
			return 0;

	return 1;
}

PUBLIC void _set_op(int op, SET *dest, SET *src)
/****************************************************************************
*
* Function:		_set_op
* Parameters:	op		- Operation to perform
*				dest	- Destination set
*				src		- Source set
*
* Description:	Performs binary operations on the sets depending on op:
*
*				_UNION:			dest = union of src and dest
*				_INTERSECT:		dest = intersection of src and dest
*				_DIFFERENCE:	dest = symmetric difference of src and dest
*				_ASSIGN:		dest = src
*
*				The size of the destination set is adjusted so that it's
*				the same size as the source set.
*
****************************************************************************/
{
	_SETTYPE	*d;		/* Pointer to destination map */
	_SETTYPE	*s;		/* Pointer to source mape */
	int			ssize;	/* # of words in src set */
	int			tail;	/* dest set is this much bigger */

	ssize = src->nwords;

	if ((int)dest->nwords < ssize) /* make sure dest set is at least */
		enlarge(ssize,dest);			/* as big as the src set.		  */

	tail = dest->nwords - ssize;
	d = dest->map;
	s = src->map;

	switch (op) {
		case _UNION:
			while (--ssize >= 0)
				*d++ |= *s++;
			break;
		case _INTERSECT:
			while (--ssize >= 0)
				*d++ &= *s++;
			while (--tail >= 0)
				*d++ = 0;
			break;
		case _DIFFERENCE:
			while (--ssize >= 0)
				*d++ ^= *s++;
			break;
		case _ASSIGN:
			while (--ssize >= 0)
				*d++ = *s++;
			while (--tail >= 0)
				*d++ = 0;
			break;
		}
}

PUBLIC void invert(SET *set)
/****************************************************************************
*
* Function:		invert
* Parameters:	set		- Set to invert
*
* Description:	Physically inverts the bits in the set. Compare with the
*				COMPLEMENT() macro, which just modifies the complement bit.
*
****************************************************************************/
{
	_SETTYPE	*p, *end;

	for (p = set->map, end = p + set->nwords; p < end; p++)
		*p = ~*p;
}

PUBLIC void truncate(SET *set)
/****************************************************************************
*
* Function:		truncate
* Parameters:	set		- Set to truncate
*
* Description:	Clears the set but also set's it back to the original,
*				default size. Compare this routine to the CLEAR() macro
*				which clears all the bits in the map but doesn't modify the
*				size.
*
****************************************************************************/
{
	if (set->map != set->defmap) {
		free(set->map);
		set->map = set->defmap;
		}

	set->nwords = _DEFWORDS;
	set->nbits = _DEFBITS;
	memset(set->defmap, 0 , sizeof(set->defmap));
}

PUBLIC int next_member(SET *set)
/****************************************************************************
*
* Function:		next_member
* Parameters:	set		- Set to return next element from
* Returns:		The next element from the set (-1 if none)
*
* Description:	Finds and returns the next element that exists in the set.
*				If "set" equals "NULL" we reset the current element. If
*				"set" has changed since the last call, we reset and return
*				the first element from this set.
*
****************************************************************************/
{
	static SET	*oset = NULL;		/* "set" arg in last call */
	static int	current_member = 0;	/* last accessed member of cur.set */

	if (!set)
		return 0;

	if (oset != set)
	{
		oset = set;
		current_member = 0;
	}

	/* The increment must be put into the test because, if the TEST()
	 * invocation evaluates to true, then an increment on the right of a
	 * for() statement would never be executed.
	 */

	while ((unsigned int)current_member++ < set->nbits)
	{
		if (TEST(set, (unsigned int)(current_member-1)))
			return(current_member-1);
	}
	return(-1);
}

PUBLIC void pset(SET *set,int (*out)(void*,char*,int),void *param)
/****************************************************************************
*
* Function:		pset
* Parameters:	set		- Set to print
*				out		- Routine to call for each element
*				param	- Parameters to the output routine
*
* Description:	Prints the contents of the set in human-readable form. The
*				output routine is called for each element of the set with
*				the following arguments:
*
*				(*out)(param, "null",-1);	NULL set ("set" arg == NULL)
*				(*out)(param, "empty",-2);	Empty set (no elements)
*				(*out)(param, "%d ",N);		N is an element of the set
*
****************************************************************************/
{
	int		i,did_something = 0;

	if (!set)
		(*out)(param,"null",-1);
	else {
		next_member(NULL);
		while( (i = next_member(set)) >= 0) {
			did_something++;
			(*out)(param,"%d ",i);
			}
		next_member(NULL);

		if (!did_something)
			(*out)(param, "empty", -2);
		}
}