Priority queues exercises

Com 1201 – Spring 2003 – Jeff Raab

Introduction

In this exercise set you will write code that implements the Priority Queue ADT in two distinctly different fashions. You must follow the course guidelines for type- or handwritten answers, diagrams, and writing code, as posted on the course website.

Programming exercises

1. Write a class named SortedPriorityQueue that implements the given IPriorityQueue interface using a sorted recursive list design. You will have to write classes named AList, EmptyList, and RecursiveList to complete the recursive list design. The class hierarchy for this design is shown in the diagram below:

The EmptyList class must use the Singleton design pattern, where its data member named EMPTY will be the only EmptyList object ever created.

The SortedPriorityQueue class must use the Proxy design pattern, where its data member named elements will be made to do as much of the work of the IPriorityQueue methods as possible. You may add additional data members to this class if you like.

The methods provided by the recursive list design are up to you. Although two constructors are specified in the diagram for the RecursiveList class, this is just an example. It is up to you to decide what constructors you want and write them.

Add tests to the PriorityQueueTests class that thoroughly test each of the methods of each of these classes, in all cases you can identify.

2. Modify the createPriorityQueue method in the PriorityQueueFactory class so that it produces an IPriorityQueue object that represents an empty sorted priority queue. Run the application and click the RunHospitalSimulation button to see your class in action.

3. Write a class named HeapPriorityQueue that implements the given IPriorityQueue interface using a heap stored in a Java Vector object. The class hierarchy for this design is shown in the diagram below:

The HeapPriorityQueue class must use the Proxy design pattern. You may add additional data members to this class if you like. It will be easier for you to write your code if you write helper methods that calculate the parent, left, and right index for a given index. It is not required of you to write helper methods.

See the Java HTML documentation for details about the Vector class. Since the Java Vector stores only a single Object at each rank, you will have to write a class that associates a key and an element into a single object.

Add tests to the PriorityQueueTests class that thoroughly test each of the methods of this class, in all cases you can identify.

4. Modify the createPriorityQueue method in the PriorityQueueFactory class so that it produces an empty HeapPriorityQueue object. Run the application and click the RunHospitalSimulation button to see your class in action.

Submission

You must submit the following written and/or printed material:

• Printouts of classes and tests you wrote for programming problems

You must submit the following electronic material:

• A folder containing all of the provided files in the exercise

• Classes and tests you wrote for programming problems

Details for electronic submission are given on the course website.