// Implements sets of unsigned char using N-word arrays
// of long int, each of which has K = 8*sizeof(long int)
// bits, for a total of N*K = 256 bits.
// Each element of unsigned char is represented by a bit
// in the bit array.
// Bits 0..K-1 are in word 0, bits K..2*K-1 are in word 1, etc.
// For convenience, we choose to number the bits from right to
// left within each word; the rightmost bit is therefore bit 0.

/* INCLUDE  **************************************/

#include <stdlib.h>
#include <stdio.h>

/* CONSTANTS  ***********************************/

const int K = 8 * sizeof( long int );
const int N = 256/K;

/* TYPES  **************************************/

struct Set
{
	unsigned long _bits[N];	// the bit array
};

/* FUNCTIONS  ************************************/

unsigned long bit( int n )
{	
	return 1UL << n; // a 1 shifted left n places
}

Set makeSet_( ) // empty set
{
	Set r;
	XXXXXXXXXXXXXXXXXXXXXXXX
	return r;
}

Set add_( unsigned char c, Set A )
{	
	Set r = A;
	XXXXXXXXXXXXXXXXXXXXXXXX
	return r;
}

Set remove_( unsigned char c, Set A )
{
	Set r = A;
	XXXXXXXXXXXXXXXXXXXXXXXX
	return r;
}

Set union_( Set A, Set B )
{
	Set r = A;
	XXXXXXXXXXXXXXXXXXXXXXXX
	return r;
}

Set intersection_( Set A, Set B )
{
	Set r = A;
	XXXXXXXXXXXXXXXXXXXXXXXX
	return r;
}

int cardinality_( Set A )	// counts the number of bits with value 1
{
	int count = 0;
        XXXXXXXXXXXXXXXXXXXXXXXX
        return count;
}

int in_( unsigned char c, Set A )
{
	return XXXXXXXXXXXXXXXXXXXXXXXX;
}

int equal_( Set A, Set B )
{
        XXXXXXXXXXXXXXXXXXXXXXXX
}

int subset_( Set A, Set B )
{
        XXXXXXXXXXXXXXXXXXXXXXXX        
}

void show( char* name, Set A )
{
	printf( "\n%s: { ", name );
	unsigned char c = 0;
	for( ;; )
	{
		if( in_( c, A ) ) printf( "%c ", c );
		
		if( c < 0xFF ) c++;
		else break;
	}
	printf( "}\n" );
}

/* ..............................................*/

int main( )
{		
	printf( "Set tests.\n" );
	
	Set A = makeSet_( );
	Set B = makeSet_( );
	Set C = makeSet_( );
	Set D = makeSet_( );
	
	char c = 'a';
	
	while ( c <= 'z' )
	{
		B = add_( c, B );
		D = add_( c, D );
		c++;
		C = add_( c, C );
		D = add_( c, D );
		c++;
	}
			
	show( "A", A );
	show( "B", B );
	show( "C", C );
	show( "D", D );
	
	show( "B union C", union_( B, C ) );
	show( "B intersect C", intersection_( B, C ) );	
	show( "remove 'b' from D", remove_( 'b', D ) ); 
	
  	printf( "\n" );
	printf( "B subset C: %d\n", subset_( B, C ) );
	printf( "B subset D: %d\n", subset_( B, D ) );
	printf( "D subset B: %d\n", subset_( D, B ) );
	
	printf( "\n" );
	printf( "B equal D: %d\n", equal_( B, D ) );
	printf( "B equal B: %d\n", equal_( B, B ) );
	printf( "(B union C) equal D: %d\n", equal_( union_( B, C ), D ) );
	
	printf( "\n" );
	printf( "'b' in B: %d\n", in_( 'b', B ) );
	printf( "'c' in B: %d\n", in_( 'c', B ) );
	
	printf( "\n" );
	printf( "cardinality A: %d\n", cardinality_( A ) );
	printf( "cardinality B: %d\n", cardinality_( B ) );
	printf( "cardinality C: %d\n", cardinality_( C ) );
	printf( "cardinality D: %d\n", cardinality_( D ) ); 
	
	return 0;
	
}