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 (assuming you are using "smart" dequeue strategy; otherwise the helper method should help the "smart" enqueue).  Depending on how you implement enqueue ("smart" or "dumb"), 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

Web-CAT will run your own unit tests and expect 100% statement coverage. 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 with the intent of making sure you didn't use a sort. There's a time limit of 4 seconds.

This output display was obtained by redirecting clientestdata.txt into ProsperoApp, like this:
java ProsperoApp < clienttestdata.txt

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


Here's an example JUnit test of ProsperoConsole: 
    public void testMenuDisplay() throws IOException
    {
        String dataIn = "Q\n";
        StringReader rdr = new StringReader(dataIn);
        FileWriter fw = new FileWriter(new File("displayout.txt"));
        new ProsperoConsole(rdr, fw).run();
        Scanner scan = new Scanner(new File("displayout.txt"));
        String line = scan.nextLine();
        assertEquals("Wrong app title.","Waiting Room Manager",line);
        line = scan.nextLine();
        assertEquals("Wrong menu.","A)dmit, G)et, P)rint, C)lear, Q)uit) Your Command? ",line);
        line = scan.nextLine();
        assertEquals("Wrong Bye.","Bye.",line);
    }
Suggested Timeline

Day 1:  Study assignment.  Study MyArrayList.  Write System Tests.
Day 2:  Write Priority Queue JUnit tests.  Write non-generic ArrayPriorityQueue for Strings without implementing PriorityQueue Interface.
Day 3:  make generic
Day 4: Implement PriorityQueue Interface including iterator.
Day 5. Write Guest and test generic ArrayPriorityQueue with it.
Day 6. Write Console.

Handing in Your Source Electronically
GRADING
Your project score is simply the score reported by Web-CAT. Included into that socre is a penalty for late submissions of 20% per day and and early submission bonus of 5% per day (max 10%). There is a limit of 20 submissions.  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.)


FAQ

Q: Can names and gifts contain embedded blanks?
A: Yes.

Q: Can we assume on project 4 that a console user will input integers for gift values of Guests?
A: Yes.

Q: How can I get Web-CAT to give me coverage of my IOException handler?
A: Make sure the catch block says: exception.printStackTrace() and not a System.out.println();

Q: Are there two blanks after the Visitor Name and Gift prompts, but only one after the gift value prompt?
A: Correct. Sorry I realize that's inconsistent.  Luckily, I don't actually test for exact matches to those prompts.

Q: I decided to try a "smart" enqueue() that would put each new item in its proper place in the arraylist, that way I could keep the array ordered and that would make dequeue() and peek() easy. But you said we are not allowed to sort the array so am I doing it wrong?
A: "Inserting" is allowed, "sorting" is not. Please read the text if you are unclear on the difference, or see me in office hours.

Q: Since the javadoc for ArrayPriorityQueue will be identical to that of PriorityQueue Interface, is there a shortcut so I don't have to copy and paste the javadoc comments into my source file?
A: Yes, use the @inheritDoc tag, like this: 
   /** {@inheritDoc} */
   public void clear()
   {
       list.clear();
   }

Q: Are the command inputs meaning only capital letters?
A: User command inputs may be upper or lower case.

Q: When the instructor reference tests on Web-CAT are compiled against my code I get this error:
 foreach not applicable to expression type
 for (Guest guest: pq)
But I made sure to provide an iterator() method. What's wrong?
A: Be sure your ArrayPriorityQueue declaration includes: extends Iterable

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.