Assignment 7 puts your code in the position of a laboratory mouse, seeking the shortest path from its starting point in a maze to an appropriate destination -- a destination containing, perhaps, a can of spam...! Reaching the spam by the shortest possible path will require implementing breadth-first search (BFS), as well as a Queue to help with that search algorithm.
Thus, the first part of this assignment is to create and test a Queue class -- using the class discussion and the example of Stack.java as a guide. Once your Queue is working, the second part of the assignment will ask you to use that information structure in the task of maze-solving.
Both parts of this assignment may be done individually or with a partner. If you choose to work with a partner, you should work with the same partner on both parts of the assignment, though you may choose to do part 1 with a partner and part 2 on your own, if you like. (Doing part 1 individually and part 2 with a partner is also possible, but more difficult because part 2 builds on part 1).
For this assignment, you should submit five files under assignment #7:
Go back to assignment #6 to complete merge and mergeSort. A solution to the other problems from assignment #6 is available here List.java.
This problem's task is to write a java class named Queue that implements a linked list that supports the standard Queue operations. Recall that a Queue is a list in which data are added (enqueued) at the "back" and removed (dequeued) from the "front."
In order to guarantee that your Queue class
supports the appropriate Queue capabilities, you should
make sure to download the file QueueInterface.java which
consists of the following interface:
/*Then, as you define your Queue class, you should declare that it will implement this interface, as follows:
* QueueInterface.java
*
* provides an interface for all of the funtions
* a Queue should implement
*
* If a class implements this interface, it can
* then be used as a Queue...
*/
interface QueueInterface
{
public boolean isEmpty();
public Object peek();
public Object dequeue();
public void enqueue(Object data);
public String toString();
}
class Queue implements QueueInterfaceThis technique uses the compiler to make sure that your code adheres to the contract set forth by the QueueInterface. A similar example is use in Stack.java, in which the Stack class implements StackInterface.
{
... rest of the Queue class here ...
More generally, you might want to use Stack as a good starting place for your Queue class. The source code for Stack and StackInterface are available, and we will cover/have covered both in class.
Inner class: QCell
Similar to the way in which the Stack class used
an inner class named StackCell, Your
Queue.java file might use an inner QCell
class that will be the type of each cell in your Queue.
Test Driven Development Practice
The description below describes the required methods to write for
Queue.java. Please use Test Driven Development
(TDD) and write the test cases for each of these methods
before writing the corresponding code. You will need to
write JUnit test cases in the file QueueTest.java
for the methods enqueue, dequeue,
peek, and isEmpty described below. Here
is a possible ordered list of tasks that uses TDD (If you
don't have experience with TDD, please follow this ordered
list!):
Data members for Queue
The Queue class itself should have two data members:
private QCell front; // the front of the Queue object - cells are removed from here
private QCell back; // the back of the Queue object - cells are added to here
Format to use for toString
In order to make testing your Queue class as uniform as
possible, we ask that you use the following format for
your toString method. Notice that <FRONT> and <BACK>
always are printed, and <FRONT> always has a single space after it. When
elements are present, they are printed from front-to-back, each with a single space
after it, including the final element. <BACK>, however, does not have a
space following it.
Feel free to use the toString method in
Stack.java as a guide... (it's very similar):
What to include in your Queue class:
public Queue()This constructor should return an empty Queue, with both the front and back being null. Feel free to write other constructors if you'd like, but you do not need to.
void enqueue(Object data)This should appropriately add the data (first putting it within a QCell!) to the invoking Queue. You might point out that data is plural, and you'd be correct! In fact, the input parameter data will hold a good deal of data when of type MazeCell.
Object dequeue()This method should return null if dequeue is called by an empty Queue; otherwise, dequeue should remove the next QCell from the invoking Queue object and return the piece of data that QCell contained.
Object peek()This method should return null if it is called by an empty Queue; otherwise, peek should return the piece of data contained in the front QCell without altering the calling Queue at all.
boolean isEmpty() {...}
that returns true when the invoking Queue
is empty, and false otherwise. Reminder: Your code in Queue.java should be clearly commented.
Your test cases in QueueTest.java should be clearly commented and will be evaluated based upon whether or not they catch bugs in ten buggy versions of the Queue class we have written.
In the Maze.java file in the top-level assignment directory, you will find two classes:
What is already in Maze?
The Maze class has a constructor for creating a new Maze object from a String. There are example input Strings provided in MazeTest.java. In the input String the asterisk '*' represents the walls, spaces are free space, and letters are special free space: 'S' is the start, and 'D' is the destination for the maze.
The Maze class also has a toString method, a method named findMazeCell that will return a MazeCell that is holding a particular character (S or D, usually).
What needs to be implemented?
You need to add test cases for super-small Mazes (that you invent) to
MazeTest.java. You should do this BEFORE writing your BFS
code. All of your test cases should be commented to explain what they test.
The method that needs to be implemented is
public ArrayList<String> BFS(MazeCell start, MazeCell destination)This BFS method needs to either:
Notes and details...
Here is what the Maze shown in the example above might look like when printed after calling BFS:
**********
*S* *
*o* oooo *
*oooo**o *
* *Do *
**********
**********
*S* *
*o*ooooo *
*ooo **o *
* *Do *
**********
To ease testing, we require that you consider paths starting with North (r-1,c), then South (r+1, c), then West (r, c-1), then East (r,c+1).
For completely voluntary bonus credit (up to +5 points), change your Maze class to handle mazes that do not necessarily have walls all around their outermost edge. In fact, you should interpret any edge as being connected to the corresponding "wrap-around" edge of the maze. This may lead to even shorter paths! For example, this is m5 from MazeTest.java, and is only slightly altered from above:
******** *
S*
* * *
* ** *
* *D *
******** *
********o*
oS* oo
* * *
* ** *
* *Doo*
********o*