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 file called Comparable.java and type in the interface specification on page 140 of the text (except call it Comparable rather than ComparisonKey).

3.

In PriorityQueue.java, search and replace PQItem with Comparable, except in main.

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 PriorityQueue.java and PQItem.java. You don't have to include Comparable.java, but you can if you want. Please take some time to 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!