Program #4

In this assignment you will use the Date and Person classes from Program #3, and write a class template called PriorityQueue. You will then test PriorityQueue by writing a suitable main.

The PriorityQueue Template

The PriorityQueue template allows one to add to a container, find the minimum, or remove the minimum. One can also test if the container is empty, and make it empty. Here is the complete interface:

class Underflow
{
};

template <class Comparable>
class PriorityQueue
{
  public:
    bool isEmpty( ) const;
    Comparable findMin( ) const;

    void makeEmpty( );
    void insert( const Comparable & x );
    void removeMin( );
    void removeMin( Comparable & minValue );

  private:
    vector<Comparable> items;
};

The basic algorithm is as follows. The items vector will store the items in the priority queue. The priority queue is empty if and only if items has size 0. To perform insert, do a push_back on items. To perform findMin, do a sequential search, returning the smallest item (if the priority queue is empty, throw an Underflow exception). To perform removeMin, find the location of the minimum item (you may want to add a private member function that can be shared by findMin and removeMin to help you avoid redundancy). Once the location is found, copy into this location the item in the last array position, and then resize the array, making it one smaller. The second form of removeMin uses an output parameter. Prior to overwriting the location that has the minimum, copy the minimum value into the minValue parameter. This allows the caller to know what was removed from the priority queue. minValue is not an input parameter. Both forms of removeMin throw an exception if the priority queue is empty. HINT: Do the test for emptiness in the private member function suggested above!

Testing Program

If everything works, you should be able to do the following in the same main routine:
  1. Create a PriorityQueue<int> object, insert some ints, and do some removeMin and findMin operations.
  2. Create a PriorityQueue<Date> object, insert some Dates, and do some removeMin and findMin operations (with earliest dates being found first).
  3. Create a PriorityQueue<Person> object, insert some Persons, and do some removeMin and findMin operations
Try to interleave insertions and removes (in other words, don't simply do all the insertions first).

Your test program should be self explanatory. In other words, you cannot simply output a bunch of numbers. Instead, output some answers, and have you program also output what the correct answers would be if there are no bugs. It should then be easy to verify that the program is indeed producing correct answers.

If you try to access the minimum of an empty priority queue, your program will throw the exception and terminate (i.e. crash). You do not have to try to catch the exception. So your main program does not need to test this case, although you may want to test it separately to convince yourself that it works. (In other words, you can write a second version of main for yourself, try to remove from an empty priority queue and see if main crashes, as would be expected if you correctly threw the exception.)

Due Date

This program is due on Tuesday, October 5.