About the sets class

The sets class can be used to perform set operations in your programs. It represents set elements as bits in a private array of unsigned long integers. The array size is a defined constant which can be changed to suit your application.

The sets class supports the following set operations by means of C++ operator overloading:

union

The union of two sets A, B is the set of all elements which belong to either A or B. In the sets class, the symbol + is the binary union operator:

A + B = {x: x is in A -or- x is in B }

intersection

The intersection of two sets A, B is the set of all elements which belong to both A and B. The symbol * is the binary intersection operator:

A * B = {x: x is in A -and- x is in B }

example

Let A = {1, 2, 3, 4} and B = {3, 4, 5, 6}. Then

A + B = {1, 2, 3, 4, 5, 6}
A * B = {3, 4}

complement

In set theory, sets are subsets of a fixed universal set U. In the sets class, U is the set of elements numbered from 1 to MAX_WORDS * WORD_SIZE. In the class declaration file below, the following definitions are made:

#define MAX_WORDS 2
#define WORD_SIZE ( 8 * sizeof( unsigned long ) )

These parameters make the range of U, 1 to 64 in sets. To increase or decrease the size of U, change the defined value of MAX_WORDS.

The complement of set A is the set of elements belonging to U but not belonging to A. The symbol ~ is the unary complement operator:

~A = {x: x is in U, x is not in A }

example

Let A = {1, 2, 3, 4} and B = {3, 4, 5, 6}. Then

~A = {5, 6, 7, . . .}
~B = {1, 2, 7, 8, 9, . . .}

difference

The difference of two sets A, B is the set of all elements which belong to A less those in B. The symbol - is the binary difference operator:

A - B = {x: x is in A, x is not in B}

example

Let A = {1, 2, 3, 4} and B = {3, 4, 5, 6}. Then

A - B = {1, 2}

It can be shown that A - B = A * ~B.

symmetric difference

The symmetric difference of two sets A, B is the set of all elements which belong to A or to B, but not both. The symbol ^ is the binary symmetric difference operator:

A ^ B = {x: x is in A + B, x is not in A * B }

example

Let A = {1, 2, 3, 4} and B = {3, 4, 5, 6}. Then

A ^ B = {1, 2, 5, 6}

It can be shown that A ^ B = (A - B) + (B - A).

methods

Several public methods are provided by to access and display the elements of a set:

sets::sets() is the default constructor. It initializes the set to be empty by setting all bits to zero.

sets::sets( const sets &rhs ) is the copy constructor, it initializes a new set to be equal to the set on the right hand side of an assignment.

void sets::binary() prints a binary representation of set to stdout.

int sets::cardinality() counts the number items in the set by counting the number of bits set to 1. It returns the count of items in the set.

void sets::clear() removes all items from the set by setting the all bits in the unsigned long integer array to 0.

void sets::define( char *input ) initializes elements of the set using an enumerated input string of numbers separated by spaces. Values of set elements that are not in the universal set are ignored. The string

"1 3 5 7 9"

void sets::insert( int bit ) puts an item into the set by setting the bit corresponding to bit in the unsigned long integer array to 1. Range errors are ignored.

int sets::item( int bit ) checks for the existence of an item in the set. If the corresponding bit is set it returns 1, or 0 if not. If bit is not in the universal set, item() returns -1 indicating a range error.

void sets::print() displays the contents of the set by printing a list of integers to stdout that corresponds to the bits set int the unsigned long integer array.

void sets::remove( int bit ) takes an item out of the set by setting the bit corresponding to bit in the unsigned long integer array to 0. Range errors are ignored.

In a C++ program, the following is a valid sequence of statements:

    sets A, B;

    A.define( "1 2 3 4" );
    B.define( "3 4 5 6" );
    sets C = A + B;        
    C.print();