A “set” is very similar to a “bag”, but duplicate values are not allowed. For this assignment, you are to convert the “IntBag” class presented in class into an “IntSet” class.

The first step is to take class “IntBag” and change all occurrences of “IntBag” to “IntSet”, and all occurrences of “bag” to “set”. We also want to get rid of method “pickRandom”, which isn’t really of interest and which might cause problems in some environments. This much has been done for you. Use files “skeleton.h” and “skeleton.cpp” as your starting point. They were created by taking “IntBag.h” and “IntBag.cpp”, making the appropriate name changes, and dropping “pickRandom”.

Method “countOccurrences” doesn’t really make any sense in a set context (because it’s not possible to have multiple occurrences of a value). Replace this method with a “bool” method called “valueExists”. Method “add” should have no effect if the value supplied is already in the set. While you’re modifying “add”, convert in into a void method that throws an “overflow_error” if a value cannot be added because the set is full. And, as a final basic change, provide a “removeAll” method. The “post-condition” for this method is that the set is left containing no values.

You might want to test your class at this point. Just take the test program supplied (test.cpp) and comment out switch cases 5, 6, and 7. These relate to additional class features discussed below.

Case 5 deals with comparing sets. We would like to be able compare sets using the “==” operator, and you must provide the necessary method. Two sets are equal if and only if they contain exactly the same values. This implies that, for two sets to be equal, they must have the same size, and all of the values in one of the sets must exist in the other. Note that seeing whether a value exists in a set is trivial, as we have a method that does exactly this. Our implementation of “==” is just 8 lines of code long, including the header and lines containing just a closing bracket (i.e. “}”). If you find yourself using much more than this, you’re on the wrong track.

In addition to being able to compare sets, we would like to able to find the intersection of two sets and the union of two sets (cases 6 and 7). You have probably encountered these concepts somewhere in your mathematical training (remember Venn diagrams?). The intersection of two sets is a set containing those values that exist in BOTH of the sets. The union of two sets is a set containing those values that exist in EITHER of the sets. Computing set intersections and unions may seem challenging, but in fact both of the required methods can be written using fewer than a dozen lines of code. The trick lies in making good use of methods “add” and “valueExists”. Since the intersection of two sets cannot be larger than the smaller of the two sets, overflow is impossible. This is not true when computing the union of two sets. If the union of two sets is too large, using “unionWith” should result in an “overflow_error” (note the careful wording – the exception need not necessarily be thrown within “unionWith”).

Method “unionWith” has been given this name, instead of the more obvious “union”, because “union” is a reserved word in C++, and so cannot be used.

Be sure to test that your class throws exceptions when it should. The easiest way to do this is to reduce set capacities to some really small number (i.e. 3 or 4).

Submit files “IntSet.h” and “IntSet.cpp”.

Updated: Tuesday, January 27th, 2009.