Assignment 4: A Taste of Polymorphism and a Minefield of Spam!
Due Monday, February 14 by 11:59 PM.

Please start this assignment early. It is fun and challenging! Most people find it a step up in challenge level from the previous assignment.

The assignment has two parts. The first part is a short programming exercise which uses inheritance to build polymorphic double-ended queues or "deques" (pronounced "decks"). You'll use your deque class again in Assignment 5's "Spampede" game. The second (larger) part of the assignment is to write a Spamsweeper Applet. You can do these parts of the assignment in any order - they are entirely independent of one another. In particular, however, we will cover the Deque problem in more detail on Thursday, so you may want to start (if you start early!) on Spamsweeper.

Playing with a full deque! (20 Points)

First, we have provided some files for you which you will find in the directory /cs/cs60/assignments/assignment4/Deque. Copy all of these files into your own directory.

One of these files is Queue.java, an implementation of a polymorphic queue using linked lists. Notice that the polymorphism simply allows the queue to contain any Object. The Node class used by this queue is at the bottom of the Queue.java file. (Java permits multiple classes to be defined in the same file.) You'll notice that this Queue class has some of it's methods renamed from the usual names. Specifically, dequeue has been renamed dequeueFront and enqueue has been renamed enqueueBack. There is also a method called peekFront which returns the element at the front of the queue without removing it.

Your mission is to implement polymorphic double-ended queues, or "deques". A deque is like a queue except that data can be inserted (enqueued) at the front or at the end and, similarly, data can be deleted (dequeued) from the front or end. Your deque will be polymorphic: It will be able to deal with any types of objects. Since a deque is an abstract data type, it must implement a provided DequeADT interface which you will find in the file /cs/cs60/assignments/assignment4/Deque/DequeADT.java which looks like this:

// DequeADT.java

// A set of methods that a Deque must implement to
// ensure that it has all the expected capabilities
// and a few special capabilities as well!

interface DequeADT
{
  public Object dequeueFront();        // Also in Queue
  public Object dequeueBack();         // New!  Remove element at back

  public void enqueueFront(Object o);  // New!  Add element to front
  public void enqueueBack(Object o);   // Also in Queue

  public Object peekFront();           // Also in Queue
  public Object peekBack();            // New!  Return element at back

  public Object peek2Front();          // New!  Return 2nd to front element
  public Object peek2Back();           // New!  Return 2nd to back element

  public boolean isEmpty();            // Also in Queue
  public String toString();            // A good thing to have

  public void reverse();               // New!  Reverse the order of elements
}

Here are the details of the Deque methods you need to implement this week:

• A constructor that creates an empty Deque (with a null head and tail). It should have signature:

         public Deque()
         

• Methods dequeueFront and dequeueBack that remove one DNode from your Deque from the appropriate side. They also return the Object that had been stored in the removed node. The signatures:

         public Object dequeueFront()
         public Object dequeueBack()
         

• Methods enqueueFront and enqueueBack that add one DNode to your Deque in the appropriate direction: they create and link a new cell containing the input data o. The signatures:

         public void enqueueFront(Object o)
         public void enqueueBack(Object o)
         

• Methods peekFront and peekBack that do not remove any DNodes from your Deque, but simply "peek" into the appropriate one and return its contents. If the deque is empty, these methods should return null. The signatures:

         public Object peekFront()
         public Object peekBack()
         

• Methods peek2Front and peek2Back that do not remove any DNodes from your Deque, but simply "peek" into the appropriate one (second from the front or second from the back, respectively) and return its contents. If the deque has fewer than two nodes, these methods should return null. The signatures:

         public Object peek2Front()
         public Object peek2Back()
         

• Methods isEmpty and toString that return appropriate information! The signatures:

         public boolean isEmpty()
         public String toString()
         

• The method reverse should change the Deque that calls it, so that the elements are in the opposite order than they were before the call. There are many ways to do this; try to keep your code as simple and elegant as possible. The signature:

         public void reverse()
         

Inheritance:   Even though there are eight methods in the above DequeADT interface, you will not have to implement all of them! The reason for this is that you are provided a Queue class (in Queue.java). Since a deque is a kind of queue, you will use inheritance so that your Deque class extends the capabilities of the existing Queue class.

What about Node?   Inside the provided Queue.java file, there is a Node class that implements a singly-linked list node. Because your Deque class will require doubly-linked list nodes, you will need to create a DNode class, which extends and inherits from the Node class. The start of both the Deque and DNode classes are available in the file Deque.java.

• Copy all of the files from /cs/cs60/assignments/assignment4/Deque to the directory in which you're working.


• The only file you will need to change is Deque.java, which will include both the Deque and the DNode classes. Please do not modify the file Queue.java.


• You may use any code that we wrote in class.


• For full credit, keep your code as simple and clean as possible. In particular, do not reimplement a method in Deque if you can inherit the implementation from Queue. Even if you can't inherent the entire method, try to invoke Queue methods where possible to minimize the amount of new code that must be written in Deque.


• There is a file for testing your Deque class named DequeTest.java. Be sure your Deque passes those tests, but also realize that our final testing will be even more thorough. Writing your own testers is an important part of programming.

Submission   The easiest way to submit is to send us all of your .java files with the command

  >  cs60submitall

Spamsweeper! (80 Points)

Now for Spamsweeper! Note that the applet that you will be writing will run under most (but not all) web browsers. In particular, we have found that some versions of Netscape have trouble running some applets.

Another reliable and very convenient way to run an applet is using appletviewer on turing. To do so, you must be using a terminal in the CS terminal room. (You can also use an Xwindows client on your own computer - but if this isn't something you're familiar with, you're best off in the CS terminal room.) Again, most browsers (Internet Explorer, newer versions of Netscape, Safari, Mozilla, and others) will also run this applet.

First, click here to see what the Spamsweeper applet will look like when you're done. You will need to click on the "reload" (or "refresh") button on your browser each time you want to start a new game after the first game. (Depending on where you are running your browser, you may hear some sound effects. The sound effects are NOT required! You may add sound effects if you wish, but it's not required. We'll talk about sound effects next week, but in the meantime you may snoop around on the web or in a Java book to learn more about it.)

Your program should have the following features:

• The game is played on a 12 x 12 board with 20 hidden cans of Spam. Give readable names to these values so that there aren't "magic values" throughout your program.
  
  
• If the user clicks on a cell that does not contain Spam, the program indicates how many of the neighboring cells (a cell has up to 8 neighbors) contain Spam. If this number is zero, the program uses recursive depth-first search to recursively expose all of the neighbors as described in class. (Please use recursion here - it's the cleanest and simplest approach.)
  
  
• If the user clicks on a cell that contains Spam (without holding the SHIFT key down) then the game ends. At this point, a message is displayed near the bottom of the applet screen with the message "GAME OVER. THAT WAS A CAN OF SPAM!". The applet continues running (stopping the applet is best done manually by leaving the web page or, if using appletviewer, typing CTRL-C) but it does not respond to any subsequent input from the player. The applet can be restarted by pressing the "reload" button on your web browser or by stopping and restarting the appletviewer.
  
  
• If the user clicks on a cell that contains Spam while holding down the SHIFT key, the letter "S" is exposed at that location. The number of remaining cans of Spam is displayed at the bottom of the applet screen.
  
  
• If the user clicks on a cell that does not contain Spam while holding down the SHIFT key, the game ends with the message "GAME OVER. THERE WAS NO SPAM THERE" displayed at the bottom of the applet. Again, the applet need not end, but there should be no response to subsequent user input.
  
  
• If all 20 cans of Spam are successfully defused, the player is congratulated with some sort of effusive compliment printed at the bottom of the screen. The applet doesn't end but it does not respond to subsequent user input.

We've left the basic components of Spamsweeper, as described in class, in the directory /cs/cs60/assignments/assignment4/Spamsweeper/. We've also left you the MicroMouse.java and MicroMouse.html files demonstrated in class, so that you can look these over, modify them, etc. to get more familiar with how applets work.

Copy all of these files into your own directory. Also, copy the file /cs/cs60/assignments/assignment4/copyFiles into your directory. (More on this later.)

You will be writing all of the interesting code for this program! In particular, you will need to write the constructor for Gameboard.java and all of the interesting methods in Spamsweeper.java. You should compile Spamsweeper.java in the normal way.

To run the applet, you can simply type appletviewer Spamsweeper.html. Remember, the appletviewer will only work if you are on a terminal in the CS terminal room (or have X-windows installed on your own machine).

Another alternative is to run the applet from your web site. You can do this from almost any browser as follows:

• By running ./copyFiles from the directory in which you have your compiled java files and the html files, you will copy and set permissions for the class files and html files needed to run the applet. Note the period and forward slash in front of copyFiles.
• The copyFiles program copies the relevant files to ~/public_html, which is your webspace on turing. You can cd ~/public_html to that directory and check it out!
• Point your browser to www.cs.hmc.edu/~yourusername/MicroMouse.html or www.cs.hmc.edu/~yourusername/Spamsweeper.html, and the applet will load and run. (~yourusername refers to your turing login name preceded by a tilde symbol (~) in front of it.)
• On some browsers, after you copy a new updated version of your game into your webspace, the browser will still run the old version. This can be very annoying and confusing. On some browsers you can press Option and click the "reload" button or Control and "reload". Others allow you to type a particular letter at the Java console, e.g., if you use Safari on the Mac, type an 'x' within the Java console and it will flush its cache of .class files so that you can reload from scratch the next time. If all else fails, quit the browser and restart it.

Debugging:   We strongly recommend that you write your program incrementally, and test it for correctness as you go. From our experience, this can reduce the debugging time very substantially. For example, after writing the constructor for the Gameboard class, write a simple tester program to make sure that it's working. Similarly, make sure that your applet can draw the grid before worrying about filling it in.

What happens to my System.out.println commands? Printing out "stuff" is a key debugging tool. However, System.out.println commands will not be displayed in the same window in which your applet is running. If you are using the appletviewer, your System.out.println commands will simply cause text to be printed in the window from which you invoked the appletviewer. However, if you are running your applet from a web browser, you'll need to take one small extra step inorder to see your System.out.printlns: You will need to "ask" your web browser to display these print statements in something called the "Java console". This is a little window which appears next to your browser window and contains the printed out text from the System.out.println commands. Here's how to do this:

• If you are using the terminals in the CS terminal room, please use the Mozilla browser. You can invoke it by typing mozilla or by clicking on the mozilla icon on the bottom right corner of the screen. In Mozilla, go to the Tools menu, select Web Development and from there select Java Console. The console will pop up when your applet starts and you're all set.
• If you are using a Macintosh (OS X), go to Applications, then Utilities, then Java, then Java Settings. Click on all of the check boxes. Then go to Applications and Utilities and double-click on the Console application. Now start your browser and the console will display the text generated by your program.
• If you are using a PC, you will need to have the Java runtime environment installed (java.sun.com). Go to Start, then Settings, then Control Panel, and then Java Plug-in and choose "Show console". Hit "Apply" and then launch your applet.

Please sumbit ALL of the files associated with your solution, including all files ending with java and html. Your best bet is to use cs60submitall so that you don't overlook submitting any file. That command will make sure to submit everything you need!

For Totally Optional Bonus Credit create an implementation called Bonussweeper.java applet (and any other auxilliary files) which augments Spamsweeper with one or more of the following features (up to 3 bonus points for each feature, up to a maximum of 9 bonus points):

• A feature which ensures that the player's first probe never detonates a can of Spam (that Spam can is just moved if the user's first probe is at that location).



• A feature which displays a picture of a Spam can rather than the letter "S". You can easily find an image of a can of Spam on the web and then use Java methods to plunk this image at the appropriate cell on the gameboard. Surf the web or a good Java book to figure out how to do this!



• You might consider adding sound to the applet... again, this would require some research into how to play sounds in Java. Sun's Java API and tutorials are good places to start.



• Any single additional feature that you think would be cool.