Starting from:
$30
CSE12-Homework 3 Data Structures Solved
In this assignment you will implement data structures that provide an implementation for three abstract data types: A double-ended queue using a circular array, a stack and a queue. In addition, these data structures will be used in a game of Minesweeper (provided for you). Also, along the way you will get more experience with implementing Java interfaces, writing JUnit test cases, and using the Adapter design pattern.
The following files are provided for you and can be found on the HW page:
● BoundedDeque.java
● BoundedStack.java
● BoundedQueue.java
● MineSweeperGUI.java
● Stack12Tester.java
● Queue12Tester.java
● Javadocs for BoundedDeque, BoundedStack, and BoundedQueue
Logistics:
In EACH AND EVERY FILE that you turn in, we need the following in comments at the top of each file.
NAME: <your name
ID: <your student ID
LOGIN: <your class login
Part 1: Deque12 and BoundedDequeTester
BoundedDequeTester.java
Read the documentation in the source code file for the BoundedDeque<E interface, or view the javadoc page for BoundedDeque which is included in the PR3 resources. Understand the responsibilities of each method required by the interface. Sketch a test plan for a class that implements this interface. Define a class named BoundedDequeTester that extends junit.framework.TestCase and that implements your test plan, using an Deque12 object as a test fixture.
We will run your tester as shown in lecture notes:
The class you will be testing is Deque12. Deque12 implements the BoundedDeque interface. There is NO starter code for this particular class so you must write it yourself. You should have at least one test for every method, but it is better form to create multiple tests for some methods depending on the condition you are testing. For example, you’ll probably want a separate test for adding to a full Deque from the test for adding to a non-full Deque.
As a practical matter, you do not need to completely write your BoundedDequeTester program before starting to define Deque12. In fact, an iterative test-driven development process can work well: write some tests in BoundedDequeTester, and implement the functionality in Deque12 that will be tested by those tests, test that functionality with BoundedDequeTester, write more tests, etc. The end result will (hopefully!) be the same: A good tester, and a good implementation of the class being tested.
As for previous (and future) assignments, make sure that your BoundedDequeTester does not depend on anything not specified by the documentation of the BoundedDeque interface and the Deque12 class. For example, do not make use of any other constructors or instance or static methods or variables that the ones required in the documentation.
Deque12.java
Define a public generic class Deque12<E that implements the BoundedDeque<E interface. Besides the requirements for the methods and constructor documented in that interface, for this assignment there is the additional requirement that this implementation must use a circular array to hold its elements. (Note also that, as for other assignments, your Deque12 should not define any public methods or constructors other than those in the interface specification.)
A circular array can be rather tricky to implement correctly! It will be worth your time to sketch it out on paper before you start writing code.
You will of course need to create an array with length equal to the capacity of the Deque12 object. Because raw arrays don’t play nicely with generics, you should use an ArrayList object for this purpose. However, there are a couple of subtleties to look out for when using an ArrayList instead of an array:
● Be careful with the difference between the ArrayList’s add method and its set method. You’ll almost certainly want to use set, not add. But this means that you must add capacity items to your ArrayList before you do anything else (i.e. in the constructor), or set will throw an IndexOutOfBounds error.
● Remember that no matter what size you initialize your ArrayList, it can always be increased, so be careful not to accidentally grow your ArrayList beyond your BoundedDeque’s capacity. Once your Deque12 instance has been properly constructed, If you only use set and not add, you should not run into this problem.
You will want to have instance variables for the size of the Deque12 (how many data elements it is currently holding), and to indicate which elements of the array are the current front and back elements. Think about what the values of these instance variables should be if the Deque12 is empty, or has one element, or is full (has size equal to its capacity). And in each case, think carefully about what needs to change for an element to be added or removed from the front or the back. Different solutions are possible, as long as all the design decisions you make are consistent with each other, and with the requirements of the interface you are implementing.
Part 2: Queue12
Now that you have your Deque built and fully tested, you will use it to implement a Stack and a Queue.
Stack12.java
We have provided a full implementation of Stack12.java that adapts Deque12 using the adapter design pattern. It is liberally documented so that you can see what a fully-documented code really looks like. Read and understand the interface specification in BoundedStack.java (or view the javadoc page for BoundedStack which is included in the PR3 resources). We’ve provided you with some unit tests that you can use to test that Stack12 behaves properly with YOUR implementation of Deque12. Note that the methods required by the BoundedStack interface are different from, though closely related to, the BoundedDeque interface methods.
Queue12.java
Read and understand the interface specification in BoundedQueue.java (or view the javadoc page for BoundedQueue which is included in the PR3 resources) and then define a generic class Queue12<E that implements the BoundedQueue<E interface. Use the existing Stack12 as a guide and adapt Deque12 to Implement Queue12. Again note that the methods required by the BoundedQueue interface are different from, though closely related to, the BoundedDeque interface methods, and so the Adapter pattern is applicable here as well.
As is often the case when the Adapter pattern is used, if the adapted class (Deque12 in this case) is tested and debugged, the adapting class shouldn't need much testing, because almost all of the work is being handled by delegation to the adapted class's methods. We provide you with a few simple tests which should be sufficient.
You must properly document your Queue12.java using javadoc in a similar manner to the provided Stack12. Including pre-conditions and the like is good practice in writing “real documentation”
Part 3: Minesweeper, Depth First Search and Breadth First
Search
The last part of this assignment is to make sure that YOUR implementation of Deque12 and the adapted classes Stack12 and Queue12 work properly from an application’s viewpoint. Provided to you in the implementation of a program that implements the popular game of Minesweeper
(http://minesweeperonline.com/). If you’ve never played Minesweeper take a few minutes to familiarize yourself with the game by playing a little bit. But just a little bit… try not to get too distracted!
We’ve provided to you a very basic implementation of Minesweeper that is reasonably complete. When you click on a cell with 0 mined neighbors, the game is supposed to automatically expose all of the surrounding neighbors of that cell, and then if any of those have no neighbors, it auto-exposes all of its neighbors, etc, until all of the connected cells with no mined neighbors and all of their connected neighbors are exposed.
Implementing this functionality is done by searching outward from the first exposed cell, expanding the search until all connected neighbors that should be exposed have been explored. As we saw/will see in class on Thursday/Friday, this can be done using depth first search or breadth first search, and the only difference between the two algorithms is whether you use a stack or a queue as your data store during the search.
We have provided an implementation of both DFS and BFS for you. Once you have your Queue12 class working, you can run and play the game STUDY the difference between the behavior of the two algorithms (DFS vs. BFS).
Part A
The first step is to understand the provided code. In your PR3.pdf file, Answer the following questions:
1. Which method is called when the user clicks on one of the cells in the grid?
2. What are the two central classes used to implement Minesweeper? Roughly, what does each do?
3. What class implements the necessary MouseListener methods that are attached to each of the cells in the board?
4. What does the exposeSlowly method do? How do you control the animation speed?
5. What is the purpose of the actionPerformed method implemented in the MineSweeperGUI class?
Part B
Finally, explore the difference between the two algorithms. Play the game with each algorithm, and notice how the animation changes. In your PR3.pdf file in a section labeled Part B describe the difference you see between how the cells are exposed when you use depth first search vs. breadth first search.
The following files are provided for you and can be found on the HW page:
● BoundedDeque.java
● BoundedStack.java
● BoundedQueue.java
● MineSweeperGUI.java
● Stack12Tester.java
● Queue12Tester.java
● Javadocs for BoundedDeque, BoundedStack, and BoundedQueue
Logistics:
In EACH AND EVERY FILE that you turn in, we need the following in comments at the top of each file.
NAME: <your name
ID: <your student ID
LOGIN: <your class login
Part 1: Deque12 and BoundedDequeTester
BoundedDequeTester.java
Read the documentation in the source code file for the BoundedDeque<E interface, or view the javadoc page for BoundedDeque which is included in the PR3 resources. Understand the responsibilities of each method required by the interface. Sketch a test plan for a class that implements this interface. Define a class named BoundedDequeTester that extends junit.framework.TestCase and that implements your test plan, using an Deque12 object as a test fixture.
We will run your tester as shown in lecture notes:
The class you will be testing is Deque12. Deque12 implements the BoundedDeque interface. There is NO starter code for this particular class so you must write it yourself. You should have at least one test for every method, but it is better form to create multiple tests for some methods depending on the condition you are testing. For example, you’ll probably want a separate test for adding to a full Deque from the test for adding to a non-full Deque.
As a practical matter, you do not need to completely write your BoundedDequeTester program before starting to define Deque12. In fact, an iterative test-driven development process can work well: write some tests in BoundedDequeTester, and implement the functionality in Deque12 that will be tested by those tests, test that functionality with BoundedDequeTester, write more tests, etc. The end result will (hopefully!) be the same: A good tester, and a good implementation of the class being tested.
As for previous (and future) assignments, make sure that your BoundedDequeTester does not depend on anything not specified by the documentation of the BoundedDeque interface and the Deque12 class. For example, do not make use of any other constructors or instance or static methods or variables that the ones required in the documentation.
Deque12.java
Define a public generic class Deque12<E that implements the BoundedDeque<E interface. Besides the requirements for the methods and constructor documented in that interface, for this assignment there is the additional requirement that this implementation must use a circular array to hold its elements. (Note also that, as for other assignments, your Deque12 should not define any public methods or constructors other than those in the interface specification.)
A circular array can be rather tricky to implement correctly! It will be worth your time to sketch it out on paper before you start writing code.
You will of course need to create an array with length equal to the capacity of the Deque12 object. Because raw arrays don’t play nicely with generics, you should use an ArrayList object for this purpose. However, there are a couple of subtleties to look out for when using an ArrayList instead of an array:
● Be careful with the difference between the ArrayList’s add method and its set method. You’ll almost certainly want to use set, not add. But this means that you must add capacity items to your ArrayList before you do anything else (i.e. in the constructor), or set will throw an IndexOutOfBounds error.
● Remember that no matter what size you initialize your ArrayList, it can always be increased, so be careful not to accidentally grow your ArrayList beyond your BoundedDeque’s capacity. Once your Deque12 instance has been properly constructed, If you only use set and not add, you should not run into this problem.
You will want to have instance variables for the size of the Deque12 (how many data elements it is currently holding), and to indicate which elements of the array are the current front and back elements. Think about what the values of these instance variables should be if the Deque12 is empty, or has one element, or is full (has size equal to its capacity). And in each case, think carefully about what needs to change for an element to be added or removed from the front or the back. Different solutions are possible, as long as all the design decisions you make are consistent with each other, and with the requirements of the interface you are implementing.
Part 2: Queue12
Now that you have your Deque built and fully tested, you will use it to implement a Stack and a Queue.
Stack12.java
We have provided a full implementation of Stack12.java that adapts Deque12 using the adapter design pattern. It is liberally documented so that you can see what a fully-documented code really looks like. Read and understand the interface specification in BoundedStack.java (or view the javadoc page for BoundedStack which is included in the PR3 resources). We’ve provided you with some unit tests that you can use to test that Stack12 behaves properly with YOUR implementation of Deque12. Note that the methods required by the BoundedStack interface are different from, though closely related to, the BoundedDeque interface methods.
Queue12.java
Read and understand the interface specification in BoundedQueue.java (or view the javadoc page for BoundedQueue which is included in the PR3 resources) and then define a generic class Queue12<E that implements the BoundedQueue<E interface. Use the existing Stack12 as a guide and adapt Deque12 to Implement Queue12. Again note that the methods required by the BoundedQueue interface are different from, though closely related to, the BoundedDeque interface methods, and so the Adapter pattern is applicable here as well.
As is often the case when the Adapter pattern is used, if the adapted class (Deque12 in this case) is tested and debugged, the adapting class shouldn't need much testing, because almost all of the work is being handled by delegation to the adapted class's methods. We provide you with a few simple tests which should be sufficient.
You must properly document your Queue12.java using javadoc in a similar manner to the provided Stack12. Including pre-conditions and the like is good practice in writing “real documentation”
Part 3: Minesweeper, Depth First Search and Breadth First
Search
The last part of this assignment is to make sure that YOUR implementation of Deque12 and the adapted classes Stack12 and Queue12 work properly from an application’s viewpoint. Provided to you in the implementation of a program that implements the popular game of Minesweeper
(http://minesweeperonline.com/). If you’ve never played Minesweeper take a few minutes to familiarize yourself with the game by playing a little bit. But just a little bit… try not to get too distracted!
We’ve provided to you a very basic implementation of Minesweeper that is reasonably complete. When you click on a cell with 0 mined neighbors, the game is supposed to automatically expose all of the surrounding neighbors of that cell, and then if any of those have no neighbors, it auto-exposes all of its neighbors, etc, until all of the connected cells with no mined neighbors and all of their connected neighbors are exposed.
Implementing this functionality is done by searching outward from the first exposed cell, expanding the search until all connected neighbors that should be exposed have been explored. As we saw/will see in class on Thursday/Friday, this can be done using depth first search or breadth first search, and the only difference between the two algorithms is whether you use a stack or a queue as your data store during the search.
We have provided an implementation of both DFS and BFS for you. Once you have your Queue12 class working, you can run and play the game STUDY the difference between the behavior of the two algorithms (DFS vs. BFS).
Part A
The first step is to understand the provided code. In your PR3.pdf file, Answer the following questions:
1. Which method is called when the user clicks on one of the cells in the grid?
2. What are the two central classes used to implement Minesweeper? Roughly, what does each do?
3. What class implements the necessary MouseListener methods that are attached to each of the cells in the board?
4. What does the exposeSlowly method do? How do you control the animation speed?
5. What is the purpose of the actionPerformed method implemented in the MineSweeperGUI class?
Part B
Finally, explore the difference between the two algorithms. Play the game with each algorithm, and notice how the animation changes. In your PR3.pdf file in a section labeled Part B describe the difference you see between how the cells are exposed when you use depth first search vs. breadth first search.
1 file (13.4KB)
