Program #3

In this assignment you will modify the Date class, write a new class called Person, and write a class template called PriorityQueue. You will then test your classes by writing a suitable main to exercise them.

The New Date Class

Modify the Date class to use operator overloading. Modify equals, lessThan, daysBetween, and futureDate to use operator overloading by choosing appropriate operators. Also provide both an input and output operator by overloading operator<< and operator>>. Accept input dates in the form mm/dd/yyyy (mm, dd, yyyy must all be integers, but need not be two, two, and four digits, respectively). If you did not get Program #2 to work, here is a sketch of the Date class (minus comments, that I still expect you to add).  Date.h  Date.cpp

The Person Class

Here is the Person class, with its private members only. You must design the public interface, and then provide an implementation. You should also provide two global functions. One performs output, printing the employee's name and birthdate. The other is operator< which compares two employees on the basis of birthdate (so the employee with earlier birthdate is considered less than the employee with later birthdate).

class Person
{
  public:
    // Provide constructors as you see fit.

    // Provide accessors to get a full name (firstName + " " + lastName)
    // or birthDate.

    // Provide a print member function.

    // Provide a setValue member function to initialize all data members.
    // Or if you prefer, provide separate setter functions.

  private:
    string firstName;
    string lastName;
    Date birthDate;
};

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. 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.

Due Date

This program is due on Tuesday, July 20.