Learning Objectives

In this assignment you will:

• Gain experience developing multiple implementations of the same Abstract Data type using different Data Structures.
• Begin to think about space and time efficiency in data structures and algorithms.
• Gain experience implementing generic collection types.
• Gain experience implementing iterators.

Introduction

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.

Part 1 - Grid and ArrayGrid

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) {
      total += value;
    }
    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) {
        largestVal = grid.get(loc);
        largestLoc = loc;
      }
    }
    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()) {
      grid.put(loc, value);
    }
  }

Detailed Grid Specifications

• 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.
• eightNeighbors - Returns an Iterable that provides access to all valid eight-connected neighbors of the indicated location.
• fourNeighbors - Returns an Iterable that provides access to all valid four-connected neighbors of the indicated location.
• 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.

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.

The “no collections” requirement also applies to the iterator method, but eightNeighbors and fourNeighbors may return collection objects. The performance impact is minimal for these methods since we are guaranteed that the size of the required collections will be small. You’ll need to be careful here since most Java collection types provide an iterator that supports removal, which would violate the specification. The Collections.unmodifiableList method can be used to address this issue.

For methods that don’t specify an iteration order, implementations are free to iterate in any order.

ArrayGrid Specifications

The ArrayGrid class must implement the Grid 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.

Part 2 - Sparse Grid

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 Locations 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.

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.

Implementation Tips

1. Use the @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.
2. Don’t forget everything you learned in CS 149 and CS 159!
   • Code duplication is bad: use helper methods where appropriate.
   • Code duplication is bad: use the abstract superclass to handle functionality that is the same across both concrete classes. If you have identical methods in the two subclasses, that functionality should almost certainly be moved to the superclass.

Ignoring the advice above will negatively impact your grade, even if your code passes all of the submission tests.

Testing Code

For future assignments in this course, you will be responsible for developing your own JUnit tests. For this first assignment, I am providing you with the complete set of Autolab submission tests:

• GridBasicsTest.java
• GridIteratorsTest.java
• ArrayGridBasicsTest.java
• ArrayGridIteratorsTest.java
• SparseGridBasicsTest.java
• SparseGridIteratorsTest.java

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.

Submission and Grading

In order to submit, create a .zip file named grid.zip and upload it to Autolab. The .zip file should contain: Grid.java, AbstractGrid.java, ArrayGrid.java and SparseGrid.java.

The project will be graded as follows:

Submissions that fail any functionality tests in a category (Basics or Iterators) will receive at most 50% of the available points for that portion of the grade. It will not be possible to receive any credit for Iterator functionality if your submissions fails any of the Basics tests. Submissions that fail any automated style checks will receive at most 50% of the points in that category. 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.

Autolab Submission Details

Since the functionality grading for this assignment is broken into two components, you will need to make two separate Autolab submissions: the “PA1 - Grid Basics” submission will run the automated style checks and the basic JUnit tests. The “PA1 - Iterators” submission will only test the iterator functionality. Both submissions must include exactly the same code. Non-matching submissions may receive a score of zero.