CMSC-341 Spring 2001

Project 1

Assigned	Monday 29 January, 2001
Due	Midnight, Wednesday 14 February 2001

Background

Abstract Data Types (ADT) are a central idea of this course and of Object-oriented programming in general. Recall that an ADT has two parts: (1) a description of the elements that make up the type, and (2) a description of the operations allowed on instances of the type. The ADT idea is implemented in C++ as a class.

The ADT is one of the most powerful and important ideas in computer science. This project will give you some exercise in using ADTs.

Another important OOP idea, parametric polymorphism, is implemented in C++ by templates. This project will give you some practice with C++ templates.

You will given a Makefile, include headers from multiple directories, and compile code from multiple directories. These are commonly used techniques in industry, so they're worth learning for future reference. You will be responsible for creating your own makefiles for all other projects.

Description

The set is one of the most fundamental objects in all areas of programming, computer science, and mathematics. This project gives you the opportunity to implement a generic set class. Note that the generic set class contains no duplicates. Trying to add an element that already exists in in the set is not an error -- it has no effect. Sets have no order -- i.e. there is no "largest" or "smallest" or "first" or "last" element.

You will use the vector template class, described in appendix B of the text. Our implementation will also require you to use the string class, also described in appendix B.

The ADTs described in the Exercises are expanded on in the "ADT" section, below. Use these expanded versions to design your classes. Please remember that you must provide good documentation as described in the "Project Organization" handout.

Here are your tasks:

Read and understand the text description of the vector ADT and its C++ implementation in Appendix B. Code for vector is available to you in the GL directory:
```
/afs/umbc.edu/users/e/d/edelman/pub/CMSC341/
```
Read and understand the text description of the string ADT and its C++ implementation in Appendix B. Code for string is available to you in the GL directory:
```
/afs/umbc.edu/users/e/d/edelman/pub/CMSC341/
```
Implement the Set ADT as a C++ class. Use appropriate header (.H) and implementation (.C) files. Your implementation must store the Set elements in a vector (Appendix B) that is a private data member of the Set class. Make sure your files are properly documented.
Use the main function provided in the file:
```
/afs/umbc.edu/users/e/d/edelman/pub/CMSC341/Proj1/Proj1.C
```
Use main() as-is, no changes. Note that the main function expects to be called with a command line argument consisting of 2 parameters. The first parameter is an integer, the number of randomly-generated int's to be inserted into a collection of int's. The second parameter is a filename of a file containing strings to be inserted into a second collection. Each line of the file consists of a single string that represents a single set element.
Note: There is no need to copy Proj1.C to your own directory. Your makefile must access the file from the directory in which it is provided. Do not submit Proj1.C.
Any errors on the command line (no argument, more than one argument, argument not an integer, argument is an integer but less than or equal to zero) are to be reported to cerr and the program is to exit with a failure indication.
Implement the functions getNumbElems and getFileName. These functions should not be defined in the same file as the main function. Put them in a separate file (suggested name for this file: Proj1_aux.C). You must also write the guarded header file, Proj1_aux.H which contains the prototypes for these functions and is #included in Proj1.C.
Modify the makefile. You should copy the file
```
/afs/umbc.edu/users/e/d/edelman/pub/CMSC341/Proj1/Makefile
```
and modify it as needed.
Answer the questions posed in 341-Spring01-proj1_questions.txt. Copy the file
```
/afs/umbc.edu/users/e/d/edelman/pub/CMSC341/Proj1/341-Spring01-proj1_questions.txt
```
to your own directory and edit it to provide your answers to the questions. Don't forget to submit the edited file; it is 10% of this project's grade.

Definition of the ADT

`Set`:

A Set is a homogeneous collection of Objects with no order relationship on the objects in the set. Duplicates are not allowed. Every Set has essentially unlimited capacity, the number of elements it is capable of holding. Its size, the actual number of elements it holds at a given time, increases as elements are inserted and decreases as they are removed.

The operations allowed on a Set are:

Construction of an empty set (constructor of no arguments).
Construction of a set as a copy of another set (copy constructor).
Destruction of a set (destructor).
const Set & operator=(const Set & rset) assignment operator.
an accessor function, size() that returns the number of elements in the set
bool isEmpty() const returns true if the set is empty.
bool isMember(const Object & x) const returns true if element x is present in the set.
void MakeEmpty() causes the size of the set to become zero.
an overloaded Set operator+ (const Set & S), the set union operator. It creates a new set consisting of all the elements in both the host Set and the set S. Recall that duplicates aren't allowed in a set. (the host Set is the object pointed to by the this pointer).
an overloaded booleanoperator==(const Set & S) , The equality operator that determines if the the set S and the host set contian exactly the same elements (added 2/3/01)
an overloaded Set operator *(const Set & S), the set intersection operator. It creates a new set consisting of only those elements in common in the 2 sets.
an overloaded bool operator < (const Set & S) returns true when the host Set is a proper subset of the set S.
an overloadedSet & operator- (const Set & S) is the set difference operator. It creates a new set consisting only of those elements in the host Set but not in set S.
an overloaded operator + (const Object & obj) that inserts obj into the host Set.
an overloaded Set & operator - (const Object & obj) removes obj from the host Set.
an overloaded non-member function ostream & operator << (const Set &).
Note: Your implementation must use the print idiom described in the Weiss text on page 35 (in the Employee class). This means you must write both the print method of the Set class and a non-class, non-friend function
```
ostream & operator<<(ostream &, const Set &)
```

Note that not all of these overloaded operators modify either set argument. They must create and return a new set (think about the type of the return value. do you want to return a Set, a Set &, or a const Set &?

Take a look at the sample output (also found in the Project 1 directory). Note that a set is printed as a comma-separated list of the elements enclosed by curly brackets. Observe carefully that there is no comma after the last element. An empty set is presented simply as a pair of angle brackets.

Main Function Definition

The file containing the main function is on the GL machine:

/afs/umbc.edu/users/e/d/edelman/pub/CMSC341/Proj1/Proj1.C

Remember, there is no need for you to copy this to your own directory. Use the main function as is; no changes, please.

Sample Output

Sample output is available for your study at

/afs/umbc.edu/users/e/d/edelman/pub/CMSC341/Proj1/341-Spring01-p1-sample_output.txt

It was obtained by executing Proj1 on linux1 with a command-line argument of 5 stringset1.txt. To understand it, you should read it along with the main function.

A copy of stringset1.txt is available. Note that this may not be the same file used to test your project.

A copy of the executable is available for you to try out. It is

/afs/umbc.edu/users/e/d/edelman/pub/CMSC341/Proj1/Proj1

Files To Be Submitted

You should submit only the files you have written, a makefile, and the file containing your answers to the questions. The files to be submitted are:

Implementation of the Set class files
Auxiliary file(s). The getNumbElems and getFileName. Including Proj1_aux.H functions should be defined in these files.
your makefile.
341-Spring01-proj1_questions.txt - containing your answers to the questions.

Please do not submit any of the files provided to you such as Proj1.C,

Submit the files using the procedure given to you for your section of the course.

If your makefile is set up correctly, you should be able to excute the command make submit.

Grading and Academic Integrity

Project grading is described in the Project Policy handout.

Your answers to 341-Spring01-proj1_questions.txt are worth 10% of your project grade.

Cheating in any form will not be tolerated. Please re-read the Project Policy handout for further details on honesty in doing projects for this course.

Remember, the due date is firm. Submittals made after midnight of the due date will not be accepted. Do not submit any files after that time.

Last modified on Saturday February 3, 2001 (09:37:09 EST) by Dennis Frey
email: frey@cs.umbc.edu