/***************************  bv-bool-ops.c  *****************************

  Purpose:	Implementation of boolean operations as bit vectors.

  Provenance:	Written and tested by S. Wartik, April 1991.

  Notes:	None.

**/

#include	"bv.h"

static boolean error_occurred;	/* TRUE iff an error occurred on the	*/
				/* last call to a boolean operator.	*/

/**************************************************************************

  	Create(lower, upper, s)

  Returns:	void

  Purpose:	Create a set capable of containing values in the range
  		[lower,upper].

  Plan:		Set the values of "s" to the parameters.

  Notes:	This routine must be called before any of the other
  		routines (save error_occurred()) will work.

**/

void Create(lower, upper, s)
    int     lower, upper;	/* in: gives the set's domain.	*/
    set     *s;			/* out: the set.		*/
{
	if ( lower > upper || (upper - lower) >= MAX_ELEMENTS ) {
		error_occurred = TRUE;
		return;
	}
	s->lower = lower;
	s->upper = upper;
	error_occurred = FALSE;
}

/**************************************************************************

  	Clear(s)

  Returns:	void

  Purpose:	Indicate that set s is empty.

  Plan:		Set all bits of s to 0.

  Notes:	The Create() function does not automatically clear
  		a set; this routine must be called to do so.

**/

void Clear(s)
        set     *s;	/* out: the set to be cleared. */
{
    register int    i, Number_Of_Bytes;
    Number_Of_Bytes = (s->upper - s->lower)/WORDSIZE + 1;
    for ( i = 0; i < Number_Of_Bytes; i++ )
        s->bits[i] = 0;
    error_occurred = FALSE;
}

/**************************************************************************

  	Insert(s, e)

  Returns:	void

  Purpose:	Insert element e into set s.

  Plan:		Determine the bit in s to which e corresponds, and set
  		that bit to 1.

  Notes:	e may already be in s.

**/

void Insert(s, e)
    set             *s;	/* in out: the set to receive the element. */
    elementType     e;	/* in: the element to be inserted.	   */
{
    if ( e < s->lower || e > s->upper ) {
        error_occurred = TRUE;
        return;
    }
    s->bits[(e-s->lower)/WORDSIZE] |= 01 << ((e-s->lower)%WORDSIZE);
    error_occurred = FALSE;
}

/**************************************************************************

  	Delete(s, e)

  Returns:	void

  Purpose:	Delete element e from set s.

  Plan:		Determine the bit in s to which e corresponds, and set that
  		bit to 0.

  Notes:	e doesn't have to be in s.

**/

void Delete(s, e)
    set             *s;	/* in out: the set from which to delete. */
    elementType     e;	/* in: the element to delete.		 */
{
    if ( e < s->lower || e > s->upper ) {
        error_occurred = TRUE;
        return;
    }
    s->bits[(e-s->lower)/WORDSIZE] &= ~(01 << ((e-s->lower)%WORDSIZE));
    error_occurred = FALSE;
}

/**************************************************************************

  	Empty(s)

  Returns:	boolean

  Purpose:	Determine whether a set is empty: return TRUE iff it is.

  Plan:		Any non-zero bit indicates the set is not empty; test
  		for that.

  Notes:	None.

**/

boolean Empty(s)
    set     *s;		/* in: the set whose emptiness is to be checked. */
{
    register int    i, Number_Of_Bytes;
    error_occurred = FALSE;
    Number_Of_Bytes = (s->upper - s->lower)/WORDSIZE + 1;
    for ( i = 0; i < Number_Of_Bytes; i++ )
        if ( s->bits[i] )
            return FALSE;
    return TRUE;
}

/**************************************************************************

  	Member(s, e)

  Returns:	boolean

  Purpose:	Determine if e is a member of s: return TRUE iff it is.

  Plan:		Check the bit to which e corresponds.

  Notes:	None.

**/

boolean Member(s, e)
    set     *s;
    elementType     e;
{
    if ( error_occurred = (e < s->lower || e > s->upper) )
        return FALSE;
    return (s->bits[(e - s->lower)/WORDSIZE] >> (e - s->lower)%WORDSIZE) & 01;
}

/* The following macro tests whether two sets have an equivalent domain --
 * i.e., bounds.  It is only possible to perform the boolean operations
 * on equivalent sets.
 */
#define equivalent(s1, s2) \
  ((s1)->lower==(s2)->lower && (s1)->upper==(s2)->upper)

/**************************************************************************

  	Unite(s1, s2, s3)

  Returns:	void

  Purpose:	Return in s3 the union of sets s1 and s2.

  Plan:		Use the bitwise OR operator to construct the union
  		of each set of words in s1 and s2.

  Notes:	None.

**/

void Unite(s1, s2, s3)
    set     *s1, *s2;	/* in: the sets to be united.   */
    set     *s3;	/* out: the union of s1 and s2. */
{
    register int    i, Number_Of_Bytes;

    if ( ! (equivalent(s1, s2) && equivalent(s2, s3)) ) {
        error_occurred = TRUE;
        return;
    }

    Number_Of_Bytes = (s1->upper - s1->lower)/WORDSIZE + 1;
    for ( i = 0 ; i < Number_Of_Bytes; i++ )
        s3->bits[i] = (s1->bits[i] | s2->bits[i]);
    error_occurred = FALSE;
}

/**************************************************************************

  	Intersect(s1, s2, s3)

  Returns:	void

  Purpose:	Return in s3 the intersection of s1 and s2.

  Plan:		Use the bitwise AND operator to construct the intersection
  		of s1 and s2.

  Notes:	None.

**/
void Intersect(s1, s2, s3)
    set     *s1, *s2;		/* in: the sets to be intersected.     */
    set     *s3;		/* out: the intersection of s1 and s2. */
{
    register int    i, Number_Of_Bytes;

    if ( ! (equivalent(s1, s2) && equivalent(s2, s3)) ) {
        error_occurred = TRUE;
        return;
    }

    Number_Of_Bytes = (s1->upper - s1->lower)/WORDSIZE + 1;
    for ( i = 0 ; i < Number_Of_Bytes; i++ )
        s3->bits[i] = (s1->bits[i] & s2->bits[i]);
    error_occurred = FALSE;
}

/**************************************************************************

  	Subtract(s1, s2, s3)

  Returns:	void

  Purpose:	Return in s3 the difference between s1 and s2 (i.e., s1-s2).

  Plan:		Use the formula (A&~B) on each corresponding pair of
  		words in s1 and s2.

  Notes:	None.

**/

void Subtract(s1, s2, s3)
    set     *s1, *s2;	/* in: the sets to be subtracted.	  */
    set     *s3;	/* out: the difference between s1 and s2. */
{
    register int    i, Number_Of_Bytes;

    if ( ! (equivalent(s1, s2) && equivalent(s2, s3)) ) {
        error_occurred = TRUE;
        return;
    }

    Number_Of_Bytes = (s1->upper - s1->lower)/WORDSIZE + 1;
    for ( i = 0 ; i < Number_Of_Bytes; i++ )
        s3->bits[i] = s1->bits[i] & ~(s2->bits[i]);
    error_occurred = FALSE;
}

/**************************************************************************

  	Copy(source, destination)

  Returns:	void

  Purpose:	Create a copy of a set.

  Plan:		Trivial.

  Notes:	None.

**/

void Copy(source, destination)
    set *source,		/* in: the set to be copied. */
	*destination;		/* out: a copy of "source".  */
{
    register int       i;

    if ( ! equivalent(source, destination) ) {
        error_occurred = TRUE;
        return;
    }
    for ( i = 0; i < MAX_ELEMENTS/WORDSIZE; i++ )
        destination->bits[i] = source->bits[i];
    error_occurred = FALSE;
}

/**************************************************************************

  	Iterate(s, f)

  Returns:	void

  Purpose:	Perform some application-defined function f on each element
  		of set s.  The function f() should be of the form:

			boolean f(e)
			    elementType	e;

		The iteration will continue as long as more elements
		remain in the set and f() returns TRUE.

  Plan:		

  Notes:	There is no guaranteed order in which the elements are
  		passed to f().

**/

void Iterate(s, f)
    set     *s;		/* in: the set to iterate through.		*/
    boolean (*f)();	/* in: the function to perform on the elements. */
{
    register int    i, j, Number_Of_Bytes;
    Number_Of_Bytes = (s->upper - s->lower)/WORDSIZE + 1;

    error_occurred = FALSE;
        
    for ( i = 0; i < Number_Of_Bytes; i++ )
        for ( j = 0; j < WORDSIZE; j++ )
	    if ( (s->bits[i] >> j) % 2 )
		if ( ! (*f)(j + i*WORDSIZE + s->lower) )
		    return;
}

/**************************************************************************

  	Error_Occurred()

  Returns:	boolean

  Purpose:	Indicate whether the last operation could not be
  		completed due to some error.

  Plan:		The routine's value is the value of the local variable
  		"error_occurred".

  Notes:	It is the responsibility of each routine to correctly
  		set "error_occurred".

**/

boolean Error_Occurred()
{
    return error_occurred;
}