set.c

来自「SRI international 发布的OAA框架软件」· C语言 代码 · 共 817 行 · 第 1/2 页

	CHK(a); CHK(b);

    if (a.n == 0) return 1;
    count=MIN(a.n,b.n);
    for (i=0; i < count; i++) {
      if (a.setword[i] & ~b.setword[i]) return 0;
    };
    if (a.n <= b.n) {
      return 1;
    } else {
      for (i=count; i<a.n ; i++) {
        if (a.setword[i]) return 0;
      };
    };
    return 1;
}

unsigned
#ifdef __USE_PROTOS
set_int( set b )
#else
set_int( b )
set b;
#endif
{
	/* Fast pick any element of the set b */
	register unsigned *p = b.setword;
	register unsigned *endp = &(b.setword[b.n]);

	CHK(b);
	if ( b.n == 0 ) return( nil );

	do {
		if (*p) {
			/* Found a non-empty word of the set */
			register unsigned i = ((p - b.setword) << LogWordSize);
			register unsigned t = *p;
			p = &(bitmask[0]);
			while (!(*p & t)) {
				++i; ++p;
			}
			return(i);
		}
	} while (++p < endp);

	/* Empty -- only element it contains is nil */
	return(nil);
}

int
#ifdef __USE_PROTOS
set_el( unsigned b, set a )
#else
set_el( b, a )
unsigned b;
set a;
#endif
{
	CHK(a);
	/* nil is an element of every set */
	if (b == nil) return(1);
	if ( a.n == 0 || NumWords(b) > a.n ) return(0);
	
	/* Otherwise, we have to check */
	return( a.setword[DIVWORD(b)] & bitmask[MODWORD(b)] );
}

int
#ifdef __USE_PROTOS
set_nil( set a )
#else
set_nil( a )
set a;
#endif
{
	/* Fast check for nil set */
	register unsigned *p = a.setword;
	register unsigned *endp;

	CHK(a);
	if ( a.n == 0 ) return(1);
	endp = &(a.setword[a.n]);
	
	/* The set is not empty if any word used to store
	   the set is non-zero.  This means one must be a
	   bit careful about doing things like negation.
	*/
	do {
		if (*p) return(0);
	} while (++p < endp);
	
	return(1);
}

char *
#ifdef __USE_PROTOS
set_str( set a )
#else
set_str( a )
set a;
#endif
{
	/* Fast convert set a into ASCII char string...
	   assumes that all word bits are used in the set
	   and that SETSIZE is a multiple of WORDSIZE.
	   Trailing 0 bits are removed from the string.
	   if no bits are on or set is empty, "" is returned.
	*/
	register unsigned *p = a.setword;
	register unsigned *endp = &(a.setword[a.n]);
	static char str_tmp[StrSize+1];
	register char *q = &(str_tmp[0]);

	CHK(a);
	if ( a.n==0 ) {*q=0; return( &(str_tmp[0]) );}
	do {
		register unsigned t = *p;
		register unsigned *b = &(bitmask[0]);
		do {
			*(q++) = (char) ((t & *b) ? '1' : '0');
		} while (++b < &(bitmask[WORDSIZE]));
	} while (++p < endp);

	/* Trim trailing 0s & NULL terminate the string */
	while ((q > &(str_tmp[0])) && (*(q-1) != '1')) --q;
	*q = 0;

	return(&(str_tmp[0]));
}

set
#ifdef __USE_PROTOS
set_val( register char *s )
#else
set_val( s )
register char *s;
#endif
{
	/* Fast convert set ASCII char string into a set.
	   If the string ends early, the remaining set bits
	   are all made zero.
	   The resulting set size is just big enough to hold all elements.
	*/
	static set a;
	register unsigned *p, *endp;

	set_new(a, strlen(s));
	p = a.setword;
	endp = &(a.setword[a.n]);
	do {
		register unsigned *b = &(bitmask[0]);
		/* Start with a word with no bits on */
		*p = 0;
		do {
			if (*s) {
				if (*s == '1') {
					/* Turn-on this bit */
					*p |= *b;
				}
				++s;
			}
		} while (++b < &(bitmask[WORDSIZE]));
	} while (++p < endp);

	return(a);
}

/*
 * Or element e into set a.  a can be empty.
 */
void
#ifdef __USE_PROTOS
set_orel( unsigned e, set *a )
#else
set_orel( e, a )
unsigned e;
set *a;
#endif
{
	CHK((*a));
	if ( e == nil ) return;
	if ( NumWords(e) > a->n ) set_ext(a, NumWords(e));
	a->setword[DIVWORD(e)] |= bitmask[MODWORD(e)];
}

/*
 * Or set b into set a.  a can be empty. does nothing if b empty.
 */
void
#ifdef __USE_PROTOS
set_orin( set *a, set b )
#else
set_orin( a, b )
set *a;
set b;
#endif
{
	/* Fast set union operation */
	/* size(a) is max(a, b); */
	unsigned int m;
	register unsigned *p,
					  *q    = b.setword,
					  *endq; /* MR20 */

	CHK((*a)); CHK(b);
	if ( b.n == 0 ) return;
	endq = &(b.setword[b.n]); /* MR20 */
	m = (a->n > b.n) ? a->n : b.n;
	set_ext(a, m);
	p = a->setword;
	do {
		*p++ |= *q++;
	} while ( q < endq );
}

/*
 * And set b into set a.  a can be empty. does nothing if b empty.
 */
void
#ifdef __USE_PROTOS
set_andin( set *a, set b )
#else
set_andin( a, b )
set *a;
set b;
#endif
{
	/* Fast set intersection operation */
	/* size(a) is max(a, b); */
	unsigned int m;
	register unsigned *p,
					  *q    = b.setword,
					  *endq = &(b.setword[b.n]);

	CHK((*a)); CHK(b);
	if ( b.n == 0 ) return;
	m = (a->n > b.n) ? a->n : b.n;
	set_ext(a, m);
	p = a->setword;
	do {
		*p++ &= *q++;
	} while ( q < endq );
}

void
#ifdef __USE_PROTOS
set_rm( unsigned e, set a )
#else
set_rm( e, a )
unsigned e;
set a;
#endif
{
	/* Does not effect size of set */
	CHK(a);
	if ( (e == nil) || (NumWords(e) > a.n) ) return;
	a.setword[DIVWORD(e)] ^= (a.setword[DIVWORD(e)]&bitmask[MODWORD(e)]);
}

void
#ifdef __USE_PROTOS
set_clr( set a )
#else
set_clr( a )
set a;
#endif
{
	/* Does not effect size of set */
	register unsigned *p = a.setword;
	register unsigned *endp;
	
	CHK(a);
	if ( a.n == 0 ) return;
	endp = &(a.setword[a.n]);
	do {
		*p++ = 0;
	} while ( p < endp );
}

set
#ifdef __USE_PROTOS
set_dup( set a )
#else
set_dup( a )
set a;
#endif
{
	set b;
	register unsigned *p,
					  *q    = a.setword,
					  *endq; /* MR20 */
	
	CHK(a);
	b = empty;
	if ( a.n == 0 ) return( empty );
	endq = &(a.setword[a.n]);	/* MR20 */
	set_ext(&b, a.n);
	p = b.setword;
	do {
		*p++ = *q++;
	} while ( q < endq );
	
	return(b);
}

/*
 * Return a nil terminated list of unsigned ints that represents all
 * "on" bits in the bit set.
 *
 * e.g. {011011} --> {1, 2, 4, 5, nil}
 *
 * _set_pdq and set_pdq are useful when an operation is required on each element
 * of a set.  Normally, the sequence is:
 *
 *		while ( set_deg(a) > 0 ) {
 *			e = set_int(a);
 *			set_rm(e, a);
 *			...process e...
 *		}
 * Now,
 *
 *		t = e = set_pdq(a);
 *		while ( *e != nil ) {
 *			...process *e...
 *			e++;
 *		}
 *		free( t );
 *
 * We have saved many set calls and have not destroyed set a.
 */
void
#ifdef __USE_PROTOS
_set_pdq( set a, register unsigned *q )
#else
_set_pdq( a, q )
set a;
register unsigned *q;
#endif
{
	register unsigned *p = a.setword,
					  *endp = &(a.setword[a.n]);
	register unsigned e=0;

	CHK(a);
	/* are there any space (possibility of elements)? */
	if ( a.n == 0 ) return;
	do {
		register unsigned t = *p;
		register unsigned *b = &(bitmask[0]);
		do {
			if ( t & *b ) *q++ = e;
			++e;
		} while (++b < &(bitmask[WORDSIZE]));
	} while (++p < endp);
	*q = nil;
}

/*
 * Same as _set_pdq except allocate memory.  set_pdq is the natural function
 * to use.
 */
unsigned *
#ifdef __USE_PROTOS
set_pdq( set a )
#else
set_pdq( a )
set a;
#endif
{
	unsigned *q;
	int max_deg;
	
	CHK(a);
	max_deg = WORDSIZE*a.n;
	/* assume a.n!=0 & no elements is rare, but still ok */
	if ( a.n == 0 ) return(NULL);
	q = (unsigned *) malloc((max_deg+1)*BytesPerWord);
	if ( q == NULL ) return( NULL );
	_set_pdq(a, q);
	return( q );
}

/* a function that produces a hash number for the set
 */
unsigned int
#ifdef __USE_PROTOS
set_hash( set a, register unsigned int mod )
#else
set_hash( a, mod )
set a;
register unsigned int mod;
#endif
{
	/* Fast hash of set a (assumes all bits used) */
	register unsigned *p = &(a.setword[0]);
	register unsigned *endp = &(a.setword[a.n]);
	register unsigned i = 0;

	CHK(a);
	while (p<endp){
		i += (*p);
		++p;
	}

	return(i % mod);
}