UMBC CMSC 202, Computer Science II, Fall 1999

Project 3: Sets and Set Operations

Due: November 11, 1999

Objectives

• Implement an abstract data type (ADT) using a C++ class.
• Use the bool data type.
• Write copy constructor and overloaded assignment operator.
• Implement binary operations using friend functions.
• Use pointers and dynamic memory allocation/deallocation in C++.

Background

Some definitions which you may find useful are provided below:

• The special set which contains no elements is called the empty set.

• The cardinality of set A is the number of elements in A.

• Element x is a member of set A if it is contained in A.

• The union of sets A and B is the set of all elements that belong to at least one of A and B.

• The intersection of sets A and B is the set of all elements that belong to both A and B.

• The difference (A - B) of sets A and B is the set of elements that belong to A but do not belong to B.

• The set A is a subset of set B if and only if every element of A is an element of B.

• The set A equals the set B if and only if A is a subset of B and B is a subset of A.

• The set A is a proper subset of set B if and only if A is a subset of B and A does not equal B.

Tasks

1. Begin with Set.H. Add additional comments as needed.

2. Design the private section of the Set class. You may add any data or function members to the private section that you wish. There are only two restrictions:

   • The memory used to store the elements of the set MUST be dynamically allocated.

   • You may NOT change any of the declarations for the public member functions or the friend functions Union(), Intersection, and Difference. Read the comments in Set.H carefully, and be sure that your functions conform to all specified requirements.

3. Implement the member functions and the three friend functions in a source file called Set.C.

4. Write a test program called Proj3.C which tests your class and produces the following output:

   
   Constructing some sets: 
   
   Set A = Empty
   Set B = Empty
   Set C = { 0 }
   Set D = { 1 }
   Set E = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 }
   Set F = { 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20 }
   Set G = { 2, 4, 6, 8, 10 }
   Set H = { 1, 3, 5, 7, 9 }
   
   Testing Copy Constructor: 
   
   Set I (Copy of A) = Empty
   Set J (Copy of C) = { 0 }
   Set K (Copy of E) = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 }
   Set L (Copy of G) = { 2, 4, 6, 8, 10 }
   
   Testing Assignment: 
   
   After assigning H to I, Set I = { 1, 3, 5, 7, 9 }
   After assigning F to J, Set J = { 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20 }
   After assigning D to K, Set K = { 1 }
   After assigning B to L, Set L = Empty
   
   Testing Cardinality: 
   
   Cardinality of A = 0
   Cardinality of C = 1
   Cardinality of E = 12
   Cardinality of G = 5
   
   Testing Membership: 
   
   5 is NOT a member of A
   5 is NOT a member of C
   5 IS a member of E
   5 is NOT a member of F
   5 is NOT a member of G
   5 IS a member of H
   
   Testing Equality: 
   
   A IS equal to B
   B IS equal to L
   C is NOT equal to E
   E is NOT equal to F
   F IS equal to J
   G is NOT equal to H
   
   Testing Subset: 
   
   A IS a subset of C
   B IS a subset of L
   C is NOT a subset of E
   D IS a subset of E
   E is NOT a subset of H
   H IS a subset of E
   
   Testing Proper Subset: 
   
   A IS a proper subset of C
   B is NOT a proper subset of L
   C is NOT a proper subset of E
   D IS a proper subset of E
   E is NOT a proper subset of H
   H IS a proper subset of E
   
   Testing Union: 
   
   Union of A and B = Empty
   Union of A and G = { 2, 4, 6, 8, 10 }
   Union of C and D = { 0, 1 }
   Union of C and E = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 }
   Union of E and H = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 }
   
   Testing Intersection: 
   
   Intersection of A and B = Empty
   Intersection of C and D = Empty
   Intersection of D and E = { 1 }
   Intersection of E and G = { 2, 4, 6, 8, 10 }
   Intersection of E and H = { 1, 3, 5, 7, 9 }
   Intersection of G and H = Empty
   
   Testing Set Difference: 
   
   C - D = { 0 }
   D - C = { 1 }
   D - E = Empty
   E - D = { 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 }
   E - F = { 1, 2, 3, 4, 5, 6, 7, 8, 9 }
   F - E = { 13, 14, 15, 16, 17, 18, 19, 20 }
   
   

5. For this project, you should submit a makefile and three source files named as follows:
   • Proj3.C
   • Set.H
   • Set.C