In this assignment you will:
Storing data in a two-dimensional grid is common across a wide range of applications: games, physics simulations, linear algebra etc. Your objective in this assignment is to implement a Grid Abstract Data Type that will provide a set of common operations that are likely to be useful across many grid-based applications.
The obvious data structure to support a Grid ADT is a two-dimensional
array. The first step for this assignment is to implement an ArrayGrid
class according to the detailed specifications below.
The following UML diagram illustrates the Grid ADT along with a concrete array-based implementation. The classes in gray are provided for you or included in the Java standard libraries.
The provided Location
class (Location.java
)
represents the position of a grid cell. Access to elements in a Grid
is performed trough Location
objects rather than by specifying the
row and column directly. This design facilitates the use of iterators
to support access patterns that would be relatively inconvenient for a
user to implement directly. Here are some code snippets illustrating
how client code can interact with objects that implement the Grid
interface:
// Default Iterator example: we just need to iterate over the elements stored
// in the grid. We don't care where they are located.
public static int sumIntegerGrid(Grid<Integer> grid) {
int total = 0;
for (int value : grid) {
+= value;
total }
return total;
}
// Location iteration example: we want to iterate over all of the occupied
// locations to determine where the largest item is stored.
public static Location largestLocation(Grid<Integer> grid) {
int largestVal = Integer.MIN_VALUE;
Location largestLoc = null;
for (Location loc : grid.itemLocations()) {
if (grid.get(loc) > largestVal) {
= grid.get(loc);
largestVal = loc;
largestLoc }
}
return largestLoc;
}
// Another location iteration example: In this case we want to iterate over
// all locations to initialize each entry with a particular value.
public static <T> void fillGrid(Grid<T> grid, T value) {
for (Location loc : grid.allLocations()) {
.put(loc, value);
grid}
}
put
- Places the provided item at the indicated location in the
Grid. If the location is already occupied, the previous element is
replaced. Attempting to store a null
element must result in an
NullPointerException
.
get
- Returns the element stored at the indicated location, or
null
if the location is empty.
remove
- Removes and returns the element stored at the indicated
location, or null
if the location is empty.
numRows
, numCols
- Simple accessors.
numItems
- Returns the number elements that are stored in the
grid. This will be zero for a newly created grid object.
allLocations
- Returns an Iterable
that provides access to all
grid cells. Implementations must ensure that locations are accessed
in
row-major
order.
itemLocations
- Returns an Iterable
that provides access to all
occupied grid cells.
iterator
- The default iterator must iterate over all elements
(not Locations
!) currently stored in the Grid
.
equals
- Two grids are considered equal if they have the same
shape, and if the elements at corresponding locations in the
grids are equal.
toString
- The toString
method must exactly follow the format
illustrated below.
This code snippet:
<String> grid = new ArrayGrid<>(3, 4);
Grid.put(new Location(1, 0), "Joyful");
grid.put(new Location(2, 2), "Tree");
gridSystem.out.println(grid.toString());
would result in the output shown here:
+--------+--------+--------+--------+
| | | | |
+--------+--------+--------+--------+
| Joyful | | | |
+--------+--------+--------+--------+
| | | Tree | |
+--------+--------+--------+--------+
Notice that the width of all columns is determined by the cell with the longest string representation and that all strings are left justified within a column.
All methods that take a Location
object must throw an
IllegalArgumentException
if the provided location is invalid. A
Location
is considered valid if it is within the bounds of the grid.
The default iterator must support the remove
operation. The
remove
methods for all other iterators must throw an
UnsupportedOperationException
.
The methods allLocations
and itemLocations
must not return
collection objects containing the full set of relevant locations.
Instead, both methods must return an Iterable
object that will
provide access to an Iterator
that will generate appropriate
Location
objects on demand. This has important implications for
performance. The collection-based approach involves allocating a
potentially large amount of memory just to store a set of Location
items that could easily be generated as they are needed. Similarly,
the default iterator must not create a separate collection internally.
For methods that don’t specify an iteration order, implementations are free to iterate in any order.
The ArrayGrid
class must implement the Grid
interface according
the the UML above. Data elements in the ArrayGrid
class must be
stored in a two-dimensional array. The constructor must throw an
IllegalArgumentException
if either the height or width argument is
less than one.
In some cases we know in advance that nearly all grid cells will be empty at execution time. For example, imagine a grid-based map used to store the positions of ships in a region of the ocean. In this case, it would be extremely inefficient to represent the grid using a two-dimensional array, since nearly all array entries will remain empty.
Your goal for the second part of this assignment is to develop a
SparseGrid
class as an alternate implementation of the Grid
interface. Instead of storing entries in a two dimensional array, the
SparseGrid
will use a HashMap
to store a mapping from Location
s
to the elements stored at those locations. Any valid location that
is not mapped to a data element is assumed to be empty. This
implementation is vastly more efficient for nearly-empty grids because
it only uses memory for occupied cells.
In addition to implementing the SparseGrid
class you must refactor
your ArrayGrid
class so that your code conforms to the following UML
diagram.
This diagram introduces both the SparseGrid
class and an
AbstractGrid
class that will serve as the superclass for both
ArrayGrid
and SparseGrid
. The AbstractGrid
class must contain
the functionality that is common to the two concrete classes, except
in cases where efficiency considerations require different
implementations. For example, the itemLocations
iterator
implemented in the ArrayGrid
class will necessarily end up examining
all grid entries in order to determine which are occupied. The
SparseGrid
class could use the same implementation, but the result
would be very inefficient. It is more efficient for the SparseGrid
class to create an iterator using the keySet
method of the HashMap
class. (Unfortunately, this isn’t quite as simple as using the
keySet
iterator directly, since it supports removal. You’ll need to
create a wrapper class to to create an iterator that doesn’t allow for
removal.)
If implemented correctly, the AbstractGrid
class should significantly
simplify the development of SparseGrid
.
The SparseGrid
constructor must throw an IllegalArgumentException
if either the height or width argument is less than one.
Note that a correctly implemented equals
method should consider an
ArrayGrid
equal to a SparseGrid
as long as they have the same size
and equal contents. This is consistent with other Java collection
types. For example, an ArrayList
and a LinkedList
will be
considered equal as long as they have equal contents.
@Override
annotation where appropriate! This has several
benefits. It will prevent you from making some sneaky coding errors
(overloading/duplicating methods instead of overriding them). It
will also allow you to avoid writing Javadoc comments for overridden
methods: it is generally not necessary to provide Javadoc
comments for overridden methods, as long as the description in the
superclass or interface provides an adequate description of the method’s
behavior.Ignoring the advice above will negatively impact your grade, even if your code passes all of the submission tests.
For future assignments in this course, you will be responsible for developing your own JUnit tests. For this first assignment, We are providing you with the complete set of Gradescope submission tests:
The required functionality is nearly identical for ArrayGrid
and
SparseGrid
. In order to avoid code duplication in the Unit tests,
nearly all of the actual testing code is included in the abstract
classes GridBasicsTest
and GridIteratorsTest
. The concrete testing
classes just override an abstract superclass method that instantiates
a Grid
object of the appropriate type.
For the Part 1 deadline submit your completed Grid.java
, and ArrayGrid.java
.
For Part 2, submit Grid.java
, AbstractGrid.java
, ArrayGrid.java
and SparseGrid.java
.
All files must be in the pas.grid
package for submission.
The project will be graded as follows:
Part 1 Gradescope Functionality Tests | 20% |
Part 2 Gradescope Functionality Tests | 55% |
Part 2 Gradescope Formatting Checks | 5% |
Instructor Style Points | 20% |
Submissions that fail any functionality tests will receive at most 75% of the available points for that portion of the grade. Instructor style points will be based on the quality and efficiency of your code and the quality of your documentation. However, this score may be impacted by problems with functionality. For example, submitting a single file with just one method will not be enough to get full credit for style, even if that method is elegant, well-documented and efficient.