----->

Project 1

Assigned	Monday, 6 September 1999
Due	Monday, 20 September 1999

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 get a chance to see how exceptions can be used to handle error situations.

You will write 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.

Description

Basically, you will be doing Exercises 1.13 and 1.14 from the Weiss text. However, instead of storing Collection elements in an array, you will store them in a vector. The vector you will use is the one described in Appendix B of the text.

Because OrderedCollection IS-A Collection, it is appropriate to use inheritance. Therefore, Collection is to be the base class for OrderedCollection.

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/a/n/anastasi/pub/CMSC-341/
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/a/n/anastasi/pub/CMSC-341/
Implement the Collection ADT as a C++ class. Use appropriate header (.H) and implementation (.C) files. Your implementation must store the Collection elements in a vector (Appendix B) that is a private data member of the Collection class. Make sure your files are properly documented.
Implement the OrderedCollection ADT as a C++ class. Use appropriate header and implementation files. Your implementation must derive from Collection. Make sure your files are properly documented.
Use the main function provided in the file: /afs/umbc.edu/users/a/n/anastasi/pub/CMSC-341/Proj1/Proj1.C
Use the function as-is, no changes. Note that the main function expects to be called with a command line argument consisting of a single integer, namely the number of elements to be inserted in the collection.
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.
The main function calls getNumbElems. You must write this function. It takes the command line parameters to main (argc and argv) and returns the int that appeared on the command line.
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 stderr and the program is to exit with a failure indication.
The function getNumbElems should not be defined in the same file as the main function. Put it in a separate file (suggested name for this file: Proj1_aux.C).
Write a makefile. You can copy the file /afs/umbc.edu/users/a/n/anastasi/pub/CMSC-341/Proj1/Makefile
and modify it as needed.
Use the definition of CollectionException provided in the files /afs/umbc.edu/users/a/n/anastasi/pub/CMSC-341/Proj1/CollectionException.H
and /afs/umbc.edu/users/a/n/anastasi/pub/CMSC-341/Proj1/CollectionException.C

Note: There is no need to copy these files to your own directory. Your makefile must access the files from the directory in which they are provided. Do not submit either of the CollectionException files.
Answer the questions posed in 341-Fall99-proj1_questions.txt. Copy the file /afs/umbc.edu/users/a/n/anastasi/pub/CMSC-341/Proj1/341-Fall99-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 counts 10% toward this project's grade.

Note that your class designs must handle all exceptional situations. For example, what will you do if a vector index is out of bounds? Document and implement your approaches appropriately. In some cases, your only choice will be to throw an exception. In other cases, you might choose a different approach. Error handling is often the most significant and time-consuming part of programming. Think about your choices carefully.

C++ Exceptions

C++ exceptions are used by the text in various places. Perhaps the first use is on page 74 in the retrieve method. Since you will be seeing exceptions throughout the course, this project will give you some easy experience with them. The particular exception you will use is the CollectionException provided to you. The text defines a few other exceptions such as Underflow, Overflow, OutOfMemory, and BadIterator. You will not be using these in this project, but you will see them used in the text.

An exception can be "thrown" at any point in a program when an exceptional situation occurs. For example, an Overflow exception might be thrown when a quotient has a denominator of zero. An exception is thrown by using the syntax "throw exception". Typical code for Overflow would be:

       if (denom == 0)
          throw Overflow()
       else
          quotient = numer/denom;

When an exception is thrown, the normal flow of control is terminated while a suitable "catcher" is sought along the calling sequence. In this project, the findMin and findMax methods of OrderedCollection throw a CollectionException if the collection is empty. Here's the type of code that would be used:

template <class Comparable>
const Comparable & 
OrderedCollection::findMin() const
{
  string err_string("findMin in empty Collection");
  if (isEmpty() == true)
    throw CollectionException(err_string);

  otherwise return the appropriate value
}

Take a look at the main function. The code that calls findMin and findMax is surrounded by a "try-catch" block.

  try
    {
      oc.findMax();
    }
  catch (CollectionException & exc)
    {
      cout <<  "Exception: " << exc.errorMsg() << endl;
    }

What happens is that if the call to findMax is made on an empty collection, a CollectionException will be thrown. The enclosing "catch" block catches the exception and deals with it. In this case it simply prints the error message that is part of the exception. If the "try-catch" block were not present, the exception would not be caught, and it would cause the program to terminate.

For this project, all you need to worry about is throwing the appropriate exception from findMin and findMax following the model given above.

Grading and Academic Integrity

Project grading is described in the Project Policy handout.

Your answers to 341-Fall99-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.

Definition of the ADTs

`Collection`:

A Collection is a homogeneous collection of Objects in no particular order. Duplicates are allowed. Every Collection has infinite 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 Collection are:

Construction of an empty collection (constructor of no arguments).
Construction of a collection as a copy of another collection (copy constructor).
Destruction of a collection (destructor).
bool insert(const Object & x) inserts x into the collection. Returns true if the insertion succeeds, false if not.
bool isEmpty() const returns true if the collection is empty.
bool isPresent(const Object & x) const returns true if element x is present in the collection. x is present if it is == to any element in the collection.
void makeEmpty() causes the size of the collection to become zero. Any elements that were in the collection are to be handled by their own destructors.
const Collection & operator=(const Collection & coll) assignment operator.
bool remove(Object x) removes x from the collection, if present. Returns true if x successfully removed.
int size() const returns the number of elements in the collection.
void print(ostream & out) const prints the elements of the collection to the indicated ostream.
Note: Your implementation must use the print idiom described in the Weiss text on the bottom of page 35. This means you must write both the print method of the Collection class and a non-class, non-friend function
```
ostream & operator<<(ostream &, const Collection &)
```
Take a look at the sample output below. Note that a collection is printed as a comma-separated list of the elements enclosed by angle brackets. Observe carefully that there is no comma after the last element. An empty collection is presented simply as a pair of angle brackets.

`OrderedCollection`:

An OrderedCollection is a Collection in which the elements are maintained in non-decreasing sorted order. The elements of an OrderedCollection are Comparables, not just Objects. In addition to all the inherited Collection operations, OrderedCollection provides the operations:

const Comparable & findMin() const returns the element in the collection that has the smallest value. It is an error to invoke this method on an empty collection.
const Comparable & findMax() const returns the element in the collection that has the largest value. It is an error to invoke this method on an empty collection.

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:

the Collection class files
the OrderedCollection class files.
auxiliary files. The getNumbElems function should be defined in these files.
your makefile.
341-Fall99-proj1_questions.txt - containing your answers to the questions.

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

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

Main Function Definition

The file containing the main function is on the GL machine: /afs/umbc.edu/users/a/n/anastasi/pub/CMSC-341/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/a/n/anastasi/pub/CMSC-341/Proj1/341-Fall99-p1-sample_output.txt
It was obtained by executing Proj1 on umbc9 with a command-line argument of 5. To understand it, you should read it along with the main function.

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

/afs/umbc.edu/users/a/n/anastasi/pub/CMSC-341/Proj1/Proj1