Lab 19: Designing an ADT

Setup

This is a “paper and pencil” exercise, with no tested code component. However, you will be implementing a portion of your abstract data type (ADT) in the next lab.

So far in this course, I’ve been dictating the behaviour of the code that you write. In this exercise, I want you to think about the behaviour that makes sense for a new data type: a set of integers.

Background Info

Having a set data type is occasionally useful. In this lab, you will begin the development of an ADT for sets. For now, only a finite set of integers will be considered.

1. Understanding Sets

From mathematics, you know that a set is a collection of elements, where:

• the collection is unordered, and
• each element is unique

For example:

• { } is a set (the “empty set”)
• { 4, -27, 0, 95 } is a set
• { 1, 1, 1 } is not a set (because duplicates are not allowed)
• { 1, 2, 3 } = { 3, 2, 1 } (order is unimportant)

It is always possible to ask if a given value is an element of a set. For example:

• $42 \in \{ 34, 513, -2 \}$ evaluates to false
• $3 \in \{ 2, 1, 3 \}$ evaluates to true

There are many common set operations. Two of the most useful are intersection and union. Relational operations (e.g. subset, superset and equality) are also important. For example:

The Public Interface

Our goal is to begin the definition of a SetInt class, which encapsulates finite sets of integers and their commonly needed operations.

Assume the client code (the calling scope) instantiates 3 sets of integers, A, B, and C, as follows:

SetInt A;
SetInt B;
SetInt C;

Think about the following questions:

1. What should be the default initialization of each set, at declaration time? Are there other ways of initializing the set?

2. How will the client add elements to the set? Prototype (declare) a suitable member function and show how the client would call it. How should the member function behave if the value being added is already an element of the set?

3. How will the client query whether a particular value is an element of the set? Prototype a suitable member function and show how the client would call it.

4. Should the ADT provide operations such as “sort” or “reverse”? Why, or why not?

5. Write a point-form list of all the other operations this ADT should provide for the client’s use. Indicate whether each is a “getter” (i.e. a query or accessor, and should be const) or a “setter” (i.e. a modifier or mutator). Try to think of all the set-like behaviour that the client will expect of a set ADT.

6. Using the above information, write a class definition for SetInt as it would appear in setint.h. For now, leave the private section empty.

Private Implementation

To complete the SetInt ADT, we must decide on:

• its internal representation
• the implementation of its member functions

It may also be useful to write some private helper member functions.

1. List 2-3 possible representations (ways of storing the set of integers). For each, list some pros and cons.

2. One possible representation is a dynamic array. Identify the private data members that are required for this representation. Complete the private section of the class definition started in the previous section.

3. Implement the default constructor for the SetInt class using the dynamic array representation.

4. Now, implement all of the remaining member functions using the dynamic array implementation. Remember that a member function can call any other member function(s) to perform a sub-task!

5. Finally, implement a client program that tests the public member functions of the SetInt ADT.