HW #4 (Integer Set)

• Design and implement, using C++, or Java if you prefer, a simple ADT called IntSet for sets of integers. Each object of class IntSet can hold zero or more integers in the range 0 through 100.
• A set should be represented internally as an array of ones and zeros. Array element a[i] is 1 if integer i is in the set. Array element a[j] is 0 if integer j is not in the set.
• The default constructor should initialize a set to an empty set, i.e., a set whose array representation contains all zeros.
• The ADT should support the following set of operations:

HW #4

• default constructor IntSet() – creates an empty set.
• constructor with one integer parameter – creates a set containing just the given integer. Example: IntSet(0) creates the set {0}.
• function isEmpty() – returns true if the set is empty, else false; does not change the set.
• function size() – returns the number of elements in the set, an integer between 0 and 100; does not change the set.

HW #4

• functiin setPrint() – prints set to cout with entries surrounded by curly braces and separated by commas (or a blank, if you prefer); returns nothing; does not change the set.

Example: if the set A has element 1, 4, and 7, A.setPrint() prints {1, 4, 7}.

• function setUnion() – creates a third set which is the settheoretic union of two existing sets.
• function setIntersetion() – creates a third set which is the set-theoretic intersection of two existing sets.

HW #4

• function relativeComplement() – creates a third set which is the set of elements that are in set A and not in set B.
• function symmetricDifference() – creates a third set whose elements belong to set A or to set B but not both.
• function isEqualTo() – returns true of the two sets are equal, false otherwise; does not change either set.

HW #4

• The class must be organized as two files, a header file, h, containing the class definition and an implementation file, intset.cpp, containing the code for the functions of the class.
• Order of values in a set is unimportant but the set should not contain duplicates.
• The following is a suggestion of how your h could possibly look like.

#ifndef INTSET_H #define INTSET_H

class IntSet { public:

IntSet() { emptySet(); } // default constructor

IntSet( int ); // alternate (overloaded) constructor

IntSet setUnion( const IntSet& ); IntSet setIntersection( const IntSet& ); bool isEmpty( void ); int size( void );

IntSet relativeComplement( const IntSet& ); IntSet symmetricDifference( const IntSet& ); void setPrint( void ) const; bool isEqualTo( const IntSet& ) const; // Auxiliary functions

……………….. private:

int set[ 101 ]; // range of 0 – 100 // Private member functions, if necessary

};

#endif

HW #4 (6)

• Testing your solution: Run the following test driver program to test you class. Make sure that all results are correct before submitting your solution.
• Feel free to write your own test program to ensure your solution is OK.

// Test program for the IntSet class

#include <iostream.h> #include “intset.h“

int main()

{

IntSet Empty; // the empty set

// for singleton sets {0} .. {3}

IntSet S0(0), S1(1), S2(2), S3(3);

IntSet A, B, C, D, E, F, G; // to hold computed sets

// Show and test empty set cout << “
Show and test the empty set…
”; cout << “Empty = “; Empty.setPrint();

cout << ” has “<< Empty.size() << ” elements.” << endl;

if ( Empty.isEmpty() )

cout << “The set is empty
” << endl;

else

cout << “The set is *not* empty
” << endl;

// Show and test {1} cout << “S1 = “; S1.setPrint();

cout << ” has “<< S1.size() << ” elements.” << endl;

if ( S1.isEmpty() )

cout << “Set S1 is empty
” << endl;

else

cout << “Set S1 is *not* empty
” << endl;

// Compute some unions

A = S0.setUnion(Empty); S0.setPrint(); cout << ” union “; Empty.setPrint(); cout << ” = “; A.setPrint(); cout << endl << endl;

• = S0.setUnion(S1);
• = S3.setUnion(S2);A.setPrint(); cout << ” union “; B.setPrint(); cout << ” = “; C = A.setUnion(B); C.setPrint(); cout << endl << endl;
• = A.setUnion(S3);
• = B.setUnion(S0);A.setPrint(); cout << ” union “; B.setPrint(); cout << ” = “; D = A.setUnion(B); D.setPrint(); cout << endl << endl; // Compute intersection, relative complement, and symmetric difference

E = A.setIntersection(S3); cout << “Intersection of “; A.setPrint(); cout << ” and “; S3.setPrint(); cout << ” is: “; E.setPrint(); cout << endl << endl;

G = D.relativeComplement(S0); cout << “Relative complement of “; D.setPrint(); cout << “and “; S0.setPrint(); cout << ” is: “; G.setPrint(); cout << endl << endl;

F = B.symmetricDifference(A); cout << “Symmetric difference of “; B.setPrint(); cout << ” and “; A.setPrint(); cout << ” is: “; F.setPrint(); cout << endl << endl;

// Test if two sets are equal cout << “Set A: “; A.setPrint(); cout << endl; cout << “Set B: “; B.setPrint(); cout << endl; if ( A.isEqualTo(B) )

cout << “Set A is equal to set B
”;

else

cout << “Set A is not equal to set B
”;

cout << endl; return 0; }

Show and test the empty set…Empty = {— } has 0 elements. The set is emptyS1 = { 1 } has 1 elements. Set S1 is *not* empty{ 0 } union {— } = { 0 }{ 0 1 } union { 2 3 } = { 0 1 2 3 }{ 0 1 3 } union { 0 2 3 } = { 0 1 2 3 }Intersection of { 0 1 3 } and { 3 } is: { 3 }Relative complement of { 0 1 2 3 } and { 0 } is: { 1 2 3 }Symmetric difference of { 0 2 3 } and { 0 1 3 } is: { 1 2 }Set A: { 0 1 3 }Set B: { 0 2 3 }Set A is not equal to set B

import lib.IntSet;

public class test { public static void main(String [] args) {

IntSet Empty = new IntSet();

IntSet S0 = new IntSet(0);

IntSet S1 = new IntSet(1);

IntSet S2 = new IntSet(2);

IntSet S3 = new IntSet(3);

IntSet A, B, C, D, E, F, G;

System.out.println(“
Show and test the empty set…”);

System.out.print(“Empty = “);

Empty.setPrint();

System.out.println(” has ” + Empty.size() + ” elements.”); if (Empty.isEmpty())

System.out.println(“The set is empty
”); else

System.out.println(“The set is *not* empty
”);

System.out.print(“S1 = “);

S1.setPrint();

System.out.println(” has ” + S1.size() + ” elements.”); if (S1.isEmpty())

System.out.println(“Set S1 is empty
”); else

System.out.println(“Set S1 is *not* empty
”);

A = S0.setUnion(Empty);

S0.setPrint();

System.out.print(” union “);

Empty.setPrint();

System.out.print(” = “);

A.setPrint();

System.out.print(“

”);

• = S0.setUnion(S1);
• = S3.setUnion(S2);

A.setPrint();

System.out.print(” union “);

B.setPrint();

System.out.print(” = “);

• = A.setUnion(B);

C.setPrint();

System.out.print(“

”);

• = A.setUnion(S3);
• = B.setUnion(S0);

A.setPrint();

System.out.print(” union “);

B.setPrint();

System.out.print(” = “);

• = A.setUnion(B);

D.setPrint();

System.out.print(“

”);

• = A.setIntersection(S3);

System.out.print(“Intersection of “);

A.setPrint();

System.out.print(” and “);

S3.setPrint();

System.out.print(” is “);

E.setPrint();

System.out.print(“

”);

G = D.relativeComplement(S0);

System.out.print(“Relative complement of “);

D.setPrint();

System.out.print(” and “);

S0.setPrint();

System.out.print(” is “);

G.setPrint();

System.out.print(“

”);

F = B.symmetricDifference(A);

System.out.print(“Symmetric difference of”);

B.setPrint();

System.out.print(” and “);

A.setPrint();

System.out.print(” is “);

F.setPrint();

System.out.print(“

”); System.out.print(“Set A:”);

A.setPrint();

System.out.println();

System.out.print(“Set B:”);

B.setPrint(); System.out.println(); if (A.isEqualTo(B))

System.out.println(“Set A is equal to set B
”); else

System.out.println(“Set A is not equal to set B
”);

System.out.println();

}

}