Prospero's Assistant

CSc 103 Programming Project

The goal of this project is to write an Java implementation of a priority queue and write a small client application that uses it.

Overview - Prospero in the Land of Ludicrous

A long, long time ago, far, far away in the Land of Ludicrous, there lived a chamberlain by the name of Prospero.  Prospero served the good king, Ludi, by being the court receptionist and scheduler of audiences before the king.

Now it is told that Prospero wished to serve the King Ludi well and perhaps earn a few kopecks in reward.  For this purpose, Prospero hit upon the idea of prioritizing the visitors to the palace based upon the grandeur of their gifts to the King. Naturally, those visitors bearing the greatest gifts should be received by the king first.  Thus, their priority is the value of their gift.  (Prospero hoped that the most generous gift bearers would also be generous tippers.)

You are to write a program to assist Prospero with his task by managing the queue of visitors in the waiting room.  Prospero's Assistant (or Waiting Room Manager) provides Prospero with a choice of operations that can be performed on the waiting room. 
These operations are:

1) Admit a new visitor to the waiting room.
2) Usher a visitor from the waiting room to the King.
3) Print a list of waiting visitors, gifts, and values (in priority order).
4) Clear the waiting room (King's audience is over).

Prospero's Assistant must display a menu of the above operations and perform all input and output to provide a complete interface for Prospero.  The program should NOT incorporate any details of priority scheduling. In other words, Prospero's Assistant deals only with getting a visitor name, gift, and gift value. The actual queue manipulations (such as deciding where the visitor must be placed in the line of visitors) are performed by an ADT called PriorityQueue. Notice that the ADT operations do NO input/output.  Prospero's Assistant (the client module) does all the screen displays and keyboard input.  (That way if we want to enhance the user interface we can do so without modifying the ADT).

Software Design

(Click on a class to view the javadocs)

class diagram


You are to implement three classes in the above design:
ArrayPriorityQueue,which implements the PriorityQueue Interface. Your implementation must delegate to Weiss's MyArrayList to do most of the work.
Guest, a class that implements Comparable and contains a visitor name (string), gift (string), and a gift value (Natural). 
ProsperoConsole, the client application that interacts with the user.
Your implementations must match the javadoc class specifications exactly.


Here are the .class files for the instructor components, ProsperoApp, PriorityQueue, MyArrayList, and Natural, in a JAR formatted file:   ProsperoComponents.jar

You may use the source code for PriorityQueue.java as a starting point for your ArrayPriorityQueue.

Strategy

Study Weiss's MyArrayList class very carefully. Write a driver and make sure you understand how all the methods operate.
Contemplate how you can implement the needed priority queue operations using the methods available to you from Weiss's class. Don't reinvent the wheel, but let his methods do most of the work.
As an exploration, you might write a non-generic priority queue, say for Strings, that does not implement the PriorityQueue interface, but has the same methods. If you can get that working, then convert it to a generic version, then implement the PriorityQueue interface.
Hints:  To implement the priority queue, create an instance of Weiss's MyArrayList class and call his methods to do most of the work.  clear(), size(), isEmpty() are the easiest.  Write a private helper method, getLargest() that both peek() and dequeue() can use.  Depending on how you implement enqueue, the iterator may be the hardest part.  It must iterate over the items in priority order. You do not need to implement the remove() method.

Lastly, implement the Guest class and the ProsperoConsole client program.

FYI, here are the instructor Lines Of Code (LOC) counts:
00074 ProsperoConsole.java
00045 ArrayPriorityQueue.java
00014 Guest.java

Sample Interactive Console Output

(Bold face text is user's keyboard input.)

Waiting Room Manager
A)dmit, G)et, P)rint, C)lear, Q)uit) Your Command? P
No visitors waiting.
A)dmit, G)et, P)rint, C)lear, Q)uit) Your Command? G
The waiting room is empty.
A)dmit, G)et, P)rint, C)lear, Q)uit) Your Command? A
  Visitor's name?  Jack
  Gift?  Beanstalk
  How many kopecks is the gift worth? 25

A)dmit, G)et, P)rint, C)lear, Q)uit) Your Command? P
Jack Beanstalk 25
A)dmit, G)et, P)rint, C)lear, Q)uit) Your Command? A
  Visitor's name?  Juliet
  Gift?  Roses
  How many kopecks is the gift worth? 50

A)dmit, G)et, P)rint, C)lear, Q)uit) Your Command? P
Juliet Roses 50
Jack Beanstalk 25
A)dmit, G)et, P)rint, C)lear, Q)uit) Your Command? A
  Visitor's name?  Frodo
  Gift?  Ring
  How many kopecks is the gift worth? 30

A)dmit, G)et, P)rint, C)lear, Q)uit) Your Command? P
Juliet Roses 50
Frodo Ring 30
Jack Beanstalk 25
A)dmit, G)et, P)rint, C)lear, Q)uit) Your Command? G
The next person to see the king is Juliet Roses 50
A)dmit, G)et, P)rint, C)lear, Q)uit) Your Command? G
The next person to see the king is Frodo Ring 30
A)dmit, G)et, P)rint, C)lear, Q)uit) Your Command? C
A)dmit, G)et, P)rint, C)lear, Q)uit) Your Command? P
No visitors waiting.
A)dmit, G)et, P)rint, C)lear, Q)uit) Your Command? x
Invalid command.
A)dmit, G)et, P)rint, C)lear, Q)uit) Your Command? Q
Bye.



Testing

Your components will be tested with instructor reference tests.  The reference tests are JUnit tests of your classes (shown in green in the class diagram above).  There will be a performance test: enqueing and dequeing 10,000 items. There's a time limit of 4 seconds.

On this project your solution must conform to the class coding standard. Your unit tests must demonstrate "statement" coverage (they cause every statement in your program to be executed.)


Handing in Your Source Electronically
Extra Credit (30%)
 This option is only available after you have completed the required assignment. The due date is one week after the required assignment. You will demo your solution to the instructor during lab or office hours.
Create a separate Swing GUI view of the PriorityQueue. ProsperoGUI can be invoked as an alternate to ProsperoConsole. No changes to any other component are needed.
Here are some draft screen shots of one possible version of a GUI - you may create something different.





If you are familiar with the NetBeans IDE, ProsperoGUI.zip contains the NetBeans project that was used to create the two windows above.
Document History

10/23/09 Revised to omit remove() method.
10/14/09 Revised for Fall 2009 to use JUnit testing.