/***************************  driver.c  **************************************

  Purpose:	Test driver program for boolean operations code.

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

  Notes:	This module contains a main program and accompanying
  		subroutines that, when compiled, exercise every function
		of the boolean operations module.  The testing is purely
		in terms of the external interface that the boolean
		operations module presents.  That is, the effects of
		constructor functions are examined through the projector
		functions.  This makes the code (almost) implementation-
		independent.  For this reason, it may be used (with slight
		modifications, controlled through #ifdef's) to test both
		the bit-vector and the hashing implementations.
		
  		Usage for the bit-vector version is:

			driver lower-bound upper-bound

		where the bounds specify the legal domain of the set.  In
		the current implementation, abs(upper-bound - lower-bound)
		must be less than 256.
			
**/
#ifndef BIT_VECTOR_IMPL				/* Make the bit-vector	*/
#	ifndef HASHING_IMPL			/* implementation be	*/
#		define	BIT_VECTOR_IMPL		/* the default.		*/
#	endif
#endif

#include	<stdio.h>

#ifdef BIT_VECTOR_IMPL
#	include	"bv.h"
#else /* HASHING_IMPL */
#	include	"hash.h"
#endif

#define N_SETS		3

#define MIN_ELEMENTS	5		/* Make the tests "interesting". */
					/* Require at least 5 elements.	 */
#ifdef HASHING_IMPL
int	hash(key)			/* Define the hashing function   */
	elementType	key;		/* as the sum of the squares of  */
{					/* each bit's magnitude, base 3. */
	int	i;
	int	threePower;
	int	sum;

	threePower = 1;
	sum = 0;
	for ( i = 0; i < 8*sizeof(elementType); i++ ) {
		register int	bitValue;
		bitValue = (key & 01)*threePower;
		bitValue *= bitValue;
		sum += bitValue;
		threePower *= 3;
	}

	return sum;
}

boolean compare(v1, v2)
	elementType	v1, v2;
{
	return v1 == v2;
}
#endif


void	Exit_If_Error_On();
void	Exit_Indicating_Failed_Op();


void	Test_Set_Operators();		/* The main routine is implemented  */
void	Test_Union_Operators();		/* as a series of calls to several  */
void	Test_Intersection_Operators();	/* procedures, each of which tests  */
void	Test_Subtraction_Operators();	/* a particular aspect of the	    */
void	Test_Copy();			/* module.			    */
void	Test_Iterate();

boolean	Iterator();


main(argc, argv)
	int	argc;
	char	*argv[];
{
	set	s[N_SETS];
	int	lower, upper;
#ifdef HASHING_IMPL
	int	number_of_buckets;
#endif
	int	i;

#ifdef BIT_VECTOR_IMPL
	if ( argc != 3 ) {
		printf("Usage: %s lower-bound upper-bound\n", argv[0]);
#else
	if ( argc != 4 ) {
		printf("Usage: %s lower-bound upper-bound number-of-buckets\n", argv[0]);
#endif
		exit(1);
	}

	lower = atoi(argv[1]);
	upper = atoi(argv[2]);
	if ( upper < lower+MIN_ELEMENTS ) {
		printf("Please specify a set that can contain at least %d elements.\n",
		       MIN_ELEMENTS);
		exit(1);
	}
#ifdef BIT_VECTOR_IMPL
	else if ( upper - lower > MAX_ELEMENTS-1 ) {
		printf("This implementation can't accommodate upper-lower>%d.\n",
		       MAX_ELEMENTS-1);
		exit(1);
	}
#else
	if ( (number_of_buckets = atoi(argv[3])) <= MIN_ELEMENTS ) {
		printf("The 1st argument must be an integer >= %d.\n",
		       MIN_ELEMENTS);
		exit(1);
	}
	
#endif

	for ( i = 0; i < N_SETS; i++ ) {	/* Test creation. */
#ifdef BIT_VECTOR_IMPL
		Create(lower, upper, &s[i]);
#else
		Create(number_of_buckets, hash, compare, &s[i]);
#endif
		Exit_If_Error_On("Create");
	}
	fputs("Creation works.\n", stdout);

	for ( i = 0; i < 2; i++ ) {		/* Test clearing sets. */
		Clear(&s[i]);
		Exit_If_Error_On("Clear");
		if ( Empty(&s[i]) )
			Exit_If_Error_On("Empty");
		else	Exit_Indicating_Failed_Op("Empty");
	}
	fputs("Clearing works.\n", stdout);

	Test_Set_Operators(s, lower, upper);
	fputs("Basic operators works.\n", stdout);
	Test_Union_Operators(s, lower, upper);
	fputs("Union works.\n", stdout);
	Test_Intersection_Operators(s, lower, upper);
	fputs("Intersection works.\n", stdout);
	Test_Subtraction_Operators(s, lower, upper);
	fputs("Subtraction works.\n", stdout);
	Test_Copy(s, lower, upper);
	fputs("Copying works.\n", stdout);
	Test_Iterate(s, lower, upper);
	fputs("Iterating works.\n", stdout);

	fputs("\nThe implementation passes.\n", stdout);
	exit(0);
}

void Test_Set_Operators(s, lower, upper)
	set	s[];
	int	lower, upper;
{
	int	i;
	
	for ( i = lower; i <= upper; i++ ) {	/* Test insertion of all    */
		Insert(&s[0], i);		/* valid elements for a     */
		Exit_If_Error_On("Insert");	/* set that doesn't already */
		if ( Member(&s[0], i) )		/* contain them.	    */
			Exit_If_Error_On("Member");
		else	Exit_Indicating_Failed_Op("Member");
	}

	for ( i = lower; i <= upper; i++ ) {	/* Test insertion of all */
		Insert(&s[0], i);		/* valid elements for a  */
		Exit_If_Error_On("Insert");	/* set that already has  */
		if ( Member(&s[0], i) )		/* them.		 */
			Exit_If_Error_On("Member");
		else	Exit_Indicating_Failed_Op("Member");
	}

	for ( i = lower; i <= upper; i++ ) {	/* Test deletion of all  */
		Delete(&s[0], i);		/* valid elements when   */
		Exit_If_Error_On("Delete");	/* the set already has	 */
		if ( ! Member(&s[0], i) )	/* them.		 */
			Exit_If_Error_On("Delete");
		else	Exit_Indicating_Failed_Op("Member");
	}

	for ( i = lower; i <= upper; i++ ) {	/* Test deletion of all  */
		Delete(&s[0], i);		/* valid elements when   */
		Exit_If_Error_On("Delete");	/* the set doesn't have	 */
		if ( ! Member(&s[0], i) )	/* them.		 */
			Exit_If_Error_On("Delete");
		else	Exit_Indicating_Failed_Op("Member");
	}
}

void Test_Union_Operators(s, lower, upper)
	set	s[];
	int	lower, upper;
{
	int	i;

	Insert(&s[0], lower);			/* Test union of a set    */
	Exit_If_Error_On("Insert");		/* with an empty set.	  */
	Unite(&s[0], &s[1], &s[2]);		/*   s2 <- {lower}U{}	  */
	Exit_If_Error_On("Unite");
	if ( Member(&s[2], lower) )
		Exit_If_Error_On("Member");
	else	Exit_Indicating_Failed_Op("Member|Unite");
	for ( i = lower+1; i <= upper; i++ )
		if ( Member(&s[2], i) )
			Exit_Indicating_Failed_Op("Member|Unite");
		else	Exit_If_Error_On("Member");

	Insert(&s[1], lower+1);		    /* Test union of two non-    */
	Exit_If_Error_On("Insert");	    /* empty, non-intersecting   */
	Unite(&s[0], &s[1], &s[2]);	    /* sets.			 */
	Exit_If_Error_On("Unite");	    /*   s2 <- {lower}U{lower+1} */
	if ( Member(&s[2], lower) && Member(&s[2], lower+1) )
		Exit_If_Error_On("Member");
	else	Exit_Indicating_Failed_Op("Member|Unite");
	for ( i = lower+2; i <= upper; i++ )
		if ( Member(&s[2], i) )
			Exit_Indicating_Failed_Op("Member|Unite");
		else	Exit_If_Error_On("Member");

					/* Test union of two non-empty,   */
	Insert(&s[0], lower+1);		/* intersecting sets.		  */
	Exit_If_Error_On("Insert");	/*   s2 <- {lower,lower+1} U	  */
	Unite(&s[0], &s[1], &s[2]);	/*		{lower+1}	  */
	Exit_If_Error_On("Unite");
	if ( Member(&s[2], lower) && Member(&s[2], lower+1) )
		Exit_If_Error_On("Member");
	else	Exit_Indicating_Failed_Op("Member|Unite");
	for ( i = lower+2; i <= upper; i++ )
		if ( Member(&s[2], i) )
			Exit_Indicating_Failed_Op("Member|Unite");
		else	Exit_If_Error_On("Member");
}

void Test_Intersection_Operators(s, lower, upper)
	set	s[];
	int	lower, upper;
{
	int	i;

	Clear(&s[0]);
	Clear(&s[1]);

	Insert(&s[0], lower);			/* Test intersection of a */
	Exit_If_Error_On("Insert");		/* set with an empty set. */
	Intersect(&s[0], &s[1], &s[2]);		/*   s2 <- {lower}^{}	  */
	Exit_If_Error_On("Intersect");
	for ( i = lower; i <= upper; i++ )
		if ( Member(&s[2], i) )
			Exit_Indicating_Failed_Op("Member|Intersect");
		else	Exit_If_Error_On("Member");

	Insert(&s[0], lower);		    /* Test intersection of two    */
	Exit_If_Error_On("Insert");	    /* non-empty, non-intersecting */
	Insert(&s[1], lower+1);		    /* sets.		   	   */
	Exit_If_Error_On("Insert");	    /*   s2 <- {lower}^{lower+1}   */
	Intersect(&s[0], &s[1], &s[2]);
	Exit_If_Error_On("Intersect");
	for ( i = lower; i <= upper; i++ )
		if ( Member(&s[2], i) )
			Exit_Indicating_Failed_Op("Member|Intersect");
		else	Exit_If_Error_On("Member");

	Insert(&s[0], lower);		    /* Test intersection of two non- */
	Exit_If_Error_On("Insert");	    /* non-empty, intersecting sets. */
	Insert(&s[0], lower+1);		    /*   s2 <- {lower,lower+1}^	     */
	Exit_If_Error_On("Insert");	    /*		  {lower,lower+2}    */
	Clear(&s[1]);
	Insert(&s[1], lower);
	Exit_If_Error_On("Insert");
	Insert(&s[1], lower+2);
	Exit_If_Error_On("Insert");
	Intersect(&s[0], &s[1], &s[2]);
	Exit_If_Error_On("Intersect");
	if ( Member(&s[2], lower) )
		Exit_If_Error_On("Member");
	else	Exit_Indicating_Failed_Op("Member|Intersect");
	for ( i = lower+1; i <= upper; i++ )
		if ( Member(&s[2], i) )
			Exit_Indicating_Failed_Op("Member|Intersect");
		else	Exit_If_Error_On("Member");
}

void Test_Subtraction_Operators(s, lower, upper)
	set	s[];
	int	lower, upper;
{
	int	i;

	Clear(&s[0]);				/* Subtract one empty set   */
	Clear(&s[1]);				/* from another.	    */
	Subtract(&s[0], &s[1], &s[2]);
	Exit_If_Error_On("Subtract");
	for ( i = lower; i <= upper; i++ )
		if ( Member(&s[2], i) )
			Exit_Indicating_Failed_Op("Member|Subtract");
		else	Exit_If_Error_On("Member");
}

void Test_Copy(s, lower, upper)
	set	s[];
	int	lower, upper;
{
	int	i;
	
	Clear(&s[0]);				 /* Create a set with every */
	for ( i = lower; i <= upper; i += 3 ) {	 /* third possible value,   */
		Insert(&s[0], i);		 /* copy it, and make sure  */
		Exit_If_Error_On("Insert");	 /* both sets have the same */
	}					 /* members.		    */

	Copy(&s[0], &s[1]);

	for ( i = lower; i <= upper; i++ )
		if ( Member(&s[0], i) != Member(&s[1], i) )
			Exit_Indicating_Failed_Op("Member|Copy");
		else	Exit_If_Error_On("Member");
}

int	Count_Of_Elements_Iterated_Over;

boolean Iterator(e)
	int	e;
{
	if ( e % 2 != 0 )	/* passed a value that wasn't inserted. */
		Exit_Indicating_Failed_Op("Iterate");
	Count_Of_Elements_Iterated_Over++;
	return TRUE;
}

void Test_Iterate(s, lower, upper)
	set	s[];
	int	lower, upper;
{
	int	i;
	int	Count_Of_Elements_Added;

	Count_Of_Elements_Added = Count_Of_Elements_Iterated_Over = 0;

	Clear(&s[0]);
	for ( i = (lower/2)*2 + 2; i <= upper; i += 2 ) {
		Insert(&s[0], i);		/* Insert all even values */
		Exit_If_Error_On("Insert");	/* (except perhaps the	  */
		Count_Of_Elements_Added++;	/* first) into the set.   */
	}

	Iterate(&s[0], Iterator);
	Exit_If_Error_On("Iterate");
	if ( Count_Of_Elements_Added != Count_Of_Elements_Iterated_Over )
		Exit_Indicating_Failed_Op("Iterate");
}

void Exit_If_Error_On(operation)
	char	operation[];
{
	if ( ! Error_Occurred() )
		return;
	printf("%s operation caused an error.\n", operation);
	exit(1);
}


void Exit_Indicating_Failed_Op(operation)
	char	operation[];
{
	printf("%s operation failed to function correctly.\n", operation);
	exit(1);
}