/***************************  hashing-bool-ops.c  *****************************

  Purpose:	Hashing-based implementation of boolean operations.

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

  Notes:	None.

**/

#include	<stdio.h>
#include	"hash.h"

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

#define hash(s,e) (abs((*((s)->hashing_function))(e)) % (s)->Number_Of_Buckets)

extern char	*malloc();

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

  	Create(lower, upper, s)

  Returns:	void

  Purpose:	Create a hashing-based implementation of a set, using
  		application-provided specifications of the details
		of hashing (function, comparison routine, and number of
		buckets).

  Plan:		Set the values of "s" to the parameters, and allocate
  		global storage for the buckets.

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

**/

void Create(Number_Of_Buckets, Hashing_Function, Comparator, s)
    int     Number_Of_Buckets;
    int     (*Hashing_Function)();
    boolean (*Comparator)();
    set     *s;
{
    register unsigned int    Bucket_Array_Size;
    register int    	     i;

    if ( Number_Of_Buckets <= 0 ) {
        error_occurred = TRUE;
        return;
    }
    s->Number_Of_Buckets = Number_Of_Buckets;
    s->hashing_function = Hashing_Function;
    s->comparator = Comparator;
    Bucket_Array_Size = sizeof(bucket_element) * Number_Of_Buckets;
    s->buckets = (bucket_element **)malloc(Bucket_Array_Size);
    if ( error_occurred = (s->buckets == NULL) )
        return;
    for ( i = 0; i < Number_Of_Buckets; i++ )
        s->buckets[i] = (bucket_element *)NULL;

}

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

  	Clear(s)

  Returns:	void

  Purpose:	Indicate that set s is empty.

  Plan:		Set all buckets of s to NULL.

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

**/

void Clear(s)
        set     *s;
{
    register int            i;
    register bucket_element *b, *next_b;

    for ( i = 0; i < s->Number_Of_Buckets; i++ )
        if ( s->buckets[i] != NULL ) {
            b = s->buckets[i];
            while ( b != NULL ) {
                next_b = b->next_datum;
                free( (char *)b );
                b = next_b;
            }
            s->buckets[i] = NULL;
        }
    error_occurred = FALSE;
}


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

  	Insert(s, e)

  Returns:	void

  Purpose:	Insert element e into set s.

  Plan:		Hash the element to its bucket, and insert it into
  		the linked list for that bucket.

  Notes:	e may already be in s; if so, it is not added.

**/

void Insert(s, e)
    set             *s;
    elementType     e;
{
    register bucket_element *b, *New_Element;
    register int            bucket;

    error_occurred = FALSE;

    bucket = hash(s,e);
    for ( b = s->buckets[bucket]; b != NULL ; b = b->next_datum )
        if ( (*(s->comparator))(b->datum, e) )
            return;

    New_Element = (bucket_element *)malloc(sizeof (bucket_element));
    if ( New_Element == NULL ) {
        error_occurred = TRUE;
        return;
    }
    New_Element->datum = e;
    New_Element->next_datum = s->buckets[bucket];
    s->buckets[bucket] = New_Element;
}

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

  	Delete(s, e)

  Returns:	void

  Purpose:	Delete element e from set s.

  Plan:		Find the bucket in which e should reside, search for
  		it in the bucket's list, and, if it's there, remove
		it from the list.

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

**/


void Delete(s, e)
        set             *s;
        elementType     e;
{
    register bucket_element *b, *previous;
    register int            bucket;

    error_occurred = FALSE;

    bucket = hash(s, e);
    if ( (b = s->buckets[bucket]) == NULL )
        return;
    if ( (*(s->comparator))(b->datum, e) )
        s->buckets[bucket] = b->next_datum;
    else {
        while ( b->next_datum != NULL ) {
            if ( (*(s->comparator))(b->datum, e) )
                break;
            previous = b;
            b = b->next_datum;
        }
        if ( b == NULL )
            return;
        previous->next_datum = b->next_datum;
    }
    free( (char *)b );
}

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

  	Empty(s)

  Returns:	boolean

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

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

  Notes:	None.

**/


boolean Empty(s)
    set     *s;
{
    register int i;

    error_occurred = FALSE;
    for ( i = 0; i < s->Number_Of_Buckets; i++ )
        if ( s->buckets[i] != NULL )
            return FALSE;
    return TRUE;
}

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

  	Member(s, e)

  Returns:	boolean

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

  Plan:		Look for e in the list for bucket hash(s, e).

  Notes:	None.

**/


boolean Member(s, e)
        set             *s;
        elementType     e;
{
    register bucket_element *b;
    register int            bucket;

    error_occurred = FALSE;

    bucket = hash(s, e);
    for ( b = s->buckets[bucket]; b != NULL ; b = b->next_datum )
        if ( (*(s->comparator))(b->datum, e) )
            return TRUE;
    return FALSE;
}

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

  	Unite(s1, s2, s3)

  Returns:	void

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

  Plan:		Copy s1 into s3, and then use Insert() to add
  		elements of s2 to s3.

  Notes:	None.

**/

void Unite(s1, s2, s3)
    set     *s1, *s2;
    set     *s3;
{
    register int            i;
    register bucket_element *b;

    Copy(s1, s3);
    if ( Error_Occurred() )
        return;

    for ( i = 0; i < s2->Number_Of_Buckets; i++ ) {
        if ( s2->buckets[i] == NULL )
            continue;
        for ( b = s2->buckets[i]; b != NULL; b = b->next_datum )
            if ( ! Member(s3, b->datum) ) {
                Insert(s3, b->datum);
                if ( Error_Occurred() )
                   return;
	    }
    }
    error_occurred = FALSE;
}

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

  	Intersect(s1, s2, s3)

  Returns:	void

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

  Plan:		Clear s3.  Then, for each bucket in s1, search
  		through its elements, testing if each element is
		in s2; if so, add that element to s3.

  Notes:	None.

**/

void Intersect(s1, s2, s3)
    set     *s1, *s2;
    set     *s3;
{
    register int            i;
    register bucket_element *b;

    Clear(s3);

    for ( i = 0; i < s1->Number_Of_Buckets; i++ ) {
        if ( s1->buckets[i] == NULL )
            continue;
        for ( b = s1->buckets[i]; b != NULL; b = b->next_datum )
            if ( Member(s2, b->datum) ) {
                Insert(s3, b->datum);
                if ( Error_Occurred() )
                    return;
            }
    }
    error_occurred = FALSE;
}

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

  	Subtract(s1, s2, s3)

  Returns:	void

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

  Plan:		Clear s3.  Then, for each element in s1, insert it in
  		s3 only if it's not in s2.

  Notes:	None.

**/

void Subtract(s1, s2, s3)
    set     *s1, *s2;
    set     *s3;
{
    register int            i;
    register bucket_element *b;

    Clear(s3);

    for ( i = 0; i < s1->Number_Of_Buckets; i++ ) {
        if ( s1->buckets[i] == NULL )
            continue;
        for ( b = s1->buckets[i]; b != NULL; b = b->next_datum )
            if ( ! Member(s2, b->datum) ) {
                Insert(s3, b->datum);
                if ( Error_Occurred() )
                    return;
            }
    }
    error_occurred = FALSE;
}

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

  	Copy(source, destination)

  Returns:	void

  Purpose:	Create a copy of a set.

  Plan:		Clear the destination set.  Then, for each element of
  		the source, create a copy by finding its hash address
		in the destination and inserting it there.

  Notes:	The source and destination sets don't have to have the
  		same number of buckets.

**/

void Copy(source, destination)
    set	*source, *destination;
{
    register int                i, h;
    register bucket_element     *e, *b;
    
    Clear(destination);
    for ( i = 0; i < source->Number_Of_Buckets; i++ ) {
        if ( source->buckets[i] == NULL )
            continue;
        for ( b = source->buckets[i]; b != NULL; b = b->next_datum ) {
            h = hash(destination, b->datum);
            e = (bucket_element *)malloc(sizeof (bucket_element));
            if ( e == NULL ) {
                error_occurred = TRUE;
                return;
            }
            e->datum = b->datum;
            e->next_datum = destination->buckets[h];
            destination->buckets[h] = e;
        }
    }
    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:		Scan the buckets in sequence; for each one that is not
  		NULL, invoke the iterator function supplied during
		Create() on each element in that bucket's list.

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

**/

void Iterate(s, f)
    set     *s;
    boolean (*f)();
{
    register int    		i;
    register bucket_element	*b;

    error_occurred = FALSE;

    for ( i = 0; i < s->Number_Of_Buckets; i++ )
	for ( b = s->buckets[i]; b != NULL; b = b->next_datum )
            if ( ! (*f)(b->datum) )
                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;
}