Please start this assignment early. It is fun and challenging!
The assignment has two parts. The first part is a short programming exercise which uses some of Java's abstraction facilities in the context of implementing double-ended queues or "deques" (pronounced "decks"). You'll use your deque class in Assignment 5 to continue your spam-oriented graphical programming!
The second 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. See the the course web page for a reminder of how the late homework policy works.
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 item of type Object. For this problem, you need to write a Deque class (in the file Deque.java). In the spirit of writing a "library-caliber" data structure, we ask you to adhere to a DequeADT interface and to use inheritance by deriving your Deque from a provided Queue class.
The interface Because users of your Deque class want to feel assured that it implements all of the functionality they might expect from a double-ended queue, you should have your Deque implement the DequeADT interface, which you should copy from /cs/cs60/assignments/assignment4/Deque/DequeADT.java.
// DequeADT.java
// A set of methods that a Deque must implement to
// ensure that it has all the expected capabilities
// and even some _unexpected_ ones for a double-ended queue.
interface DequeADT
{
public Object dequeueFront(); // also in Queue
public Object dequeueBack(); // new to Deque
public void enqueueFront(Object o); // new to Deque
public void enqueueBack(Object o); // also in Queue
public Object peekFront(); // also in Queue
public Object peekBack(); // new to Deque
public Object peek2Front(); // new to Deque
public Object peek2Back(); // new to Deque
public boolean isEmpty(); // also in Queue
public String toString(); // in Object and Queue
public void reverse(); // new to Deque
}
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 queue, you should 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. For ease of maintenance, the start of both the Deque and DNode classes are available in the file Deque.java.
Hints
All Deque methods Here are all of the methods your Deque class should support -- note that because you're inheriting from Queue, you will not have to write all of them!
public Deque()
public void enqueueFront(Object o)
public void enqueueBack(Object o)
public Object dequeueFront()
public Object dequeueBack()
public Object peekFront()
public Object peekBack()
public Object peek2Front()
public Object peek2Back()
public boolean isEmpty()
public String toString()
public void reverse()
Submission
The easiest way to submit is to send us all
of your .java files with the command
> cs60submitall
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 older 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. Specifically, your program should have the following features:
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. 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.
Another alternative is to run the applet from your web site. You can do this from almost any browser as follows:
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.
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 4 bonus points for each feature, up to a maximum of 12 bonus points):