Make a generic Priority Queue

So far, our priority queue can only contain one kind of object, PQItem. We would like to be able to make a generic Priority Queue that can contain any kind of item. There are several ways to do this in Java, but one way is:

• Create an abstract class (interface) that defines the requirements for objects that want to be put into Priority Queues. In this case, the requirement is that the objects be comparable, so we'll call the abstract class Comparable. The book calls it ComparisonKey.

• Rewrite Priority Queue so that it can deal with any object that meets the specification of the abstract class; in other words, any object that implements the Comparable interface.

• Create a concrete class (PQItem) that implements the Comparable interface.

Here are the detailed steps you should follow:

1.

Make a copy of your working implementation of Priority Queue so that if things go horribly wrong you can back out.

2.

Create a new interface called Comparable that looks like this:

interface Comparable {
  int compareTo (Comparable other);
  String toString();
}

This is basically the ComparisonKey interface from page 140, except that I changed the name and removed the word public so that I could keep the whole program in one file.

3.

Modify the PriorityQueue class definition so that it works with Comparable objects rather than PQItems. Don't modify main, though--one of the goals of an ADT is to allow us to modify the implementation without changing the client code.

4.

In PQItem, add implements Comparable to the first line (following the example on page 141 of the text). Also, modify compareTo so that the second argument is a Comparable rather than a PQItem. That means you will have to do some typecasting inside the method.

5.

Finally, in main you will have to do some typecasting in order to add items to the Priority Queue and remove them. Since Comparable is an abstract class you cannot create instances of it; rather, you have to create PQItems and cast them to be Comparable before you insert them, then cast them back after you remove them.

6.

Print your modified version of the program. Please assemble your printouts into a coherent document, so that it is clear that there are two separate programs. Using a highlighter, mark all the sections of code that are different from the previous version (or underline them in pen). If you make life easier for the grader, the grader will make life easier for you!