Homework 2: Sparse Maze!

This assignment introduces you to sparse data structures through an interactive maze implementation.

Important Dates

Motivation for Sparse Maze

Imagine you're designing a video game with massive worlds - think Minecraft with its virtually infinite landscapes. Most of these worlds are largely empty space or filled with the same default terrain (like air blocks or grass). Storing every single cell would be enormously wasteful!

Storing every cell would waste enormous amounts of memory. Instead, we can be clever: assume all cells are open by default, and only store the locations of walls!

Your maze is a sparse data structure.

A sparse data structure is one which only stores values that differ from the default value.

This concept is fundamental in computer graphics, game development, scientific computing, and anywhere large datasets have mostly uniform values with scattered exceptions.

In this homework, you will implement a sparse maze that efficiently stores only the non-default cells.

Starter Code

Download the starter code from the following link: hw2.zip

The starter code is a zip file named hw2-starter.zip. You must unzip this file. After unzipping, you will get a folder called hw2-starter. Open this folder as an IntelliJ project.

Sparse Maze Implementation

• A sparse maze only stores cells that differ from the default value (open or blocked).
• For sparse mazes, it is wasteful to store every cell explicitly since most cells have the same value.
• Instead, we store only the exceptions - cells that differ from the default.

Write a class SparseMaze that implements the Maze interface. Do not modify the Maze interface! Use a linked list of nodes instead of arrays to store only non-default cell values. (The starter code includes Dense1DMaze and Dense2DMaze as examples of dense implementations.)

Each node in your linked list stores:

• The linear index of the cell in the maze (calculated as row * width + col)
• The value at that position (true for open, false for blocked)
• A reference to the next node

Your SparseMaze must use a singly linked list with only a head pointer. The Node class must be private (protected) and nested inside SparseMaze. You may not use Java Collections (ArrayList, LinkedList, etc.) or advanced data structures not yet covered in class.

Here's how your implementation should work:

• Start with a sentinel node (a dummy head node that simplifies linked list operations).

• For setCell:

  • If setting to a non-default value: add or update a node for that position
  • If setting to the default value: remove the node for that position (if it exists)

• For isOpen:

  • Search for a node with the target linear index
  • If found, return the stored value
  • If not found, return the default value

Here is a visual representation of how SparseMaze should work:

Maze maze = new SparseMaze(5, 4, true); // 5×4 maze, default = open (true)

Initially, the maze has no stored nodes since all cells have the default value:

Internal state: 
head (sentinel: index=-1) -> null

Logical maze:
T T T T T
T T T T T
T T T T T
T T T T T

Now, we'll block a cell:

maze.setCell(1, 2, false); // Block cell at row 1, column 2

Now we have one node storing the non-default value:

Internal state: 
head (sentinel: index=-1) -> [index=7, value=false] -> null
(Linear index 7 = row 1 * width 5 + col 2 = 1*5+2 = 7)

Logical maze:
T T T T T
T T F T T
T T T T T
T T T T T

Next, we'll block another cell:

maze.setCell(2, 4, false); // Block cell at row 2, column 4

Internal state: 
head (sentinel: index=-1) -> [index=7, value=false] -> [index=14, value=false] -> null
(Linear indices: 7 = row 1 * 5 + col 2, 14 = row 2 * 5 + col 4)

Logical maze:
T T T T T
T T F T T
T T T T F
T T T T T

We can un-block a cell, setting the value back to its default:

maze.setCell(1, 2, true); // Open cell at row 1, column 2 (back to default)

The node is removed since the value equals the default:

Internal state: 
head (sentinel: index=-1) -> [index=14, value=false] -> null
(Linear index 14 = row 2 * 5 + col 4)

Logical maze:
T T T T T
T T T T T
T T T T F
T T T T T

It is required to remove nodes when values are set back to default!

Iterator Implementation

The Maze interface extends Iterable<Boolean>, so you must implement an iterator. Your iterator should traverse all cells in row-major order (row 0 from left to right, then row 1 from left to right, etc.), returning the appropriate value for each cell.

The iterator must present the complete logical maze, not just the stored nodes. For cells not in your linked list, return the default value.

The Efficiency of Your Iterator

Before reading this section, make sure you have a correct implementation of SparseMaze that passes all provided tests.

Once you have a working implementation, consider the efficiency of your iterator. In particular, think about scenarios where your maze is accessed frequently through iteration but modified rarely. When you iterate over the maze in row-major order, how quickly can you get the "next" cell?

We have not yet formalized a notion of "efficiency." For this task, you can consider the iterators of the Dense1DMaze and the Dense2DMaze as examples of efficient implementations. Those implementations take a few operations to get the "next" element (the operations involve looking up/updating an index or a reference variable). The same can be said about the hasNext operation and the constructor.

You may need to refactor your implementation of SparseMaze to make its iterator efficient. Make sure first to commit your current working implementation and push it to GitHub. In case you end up breaking your solution to make it more efficient, you can always revert to the earlier working version.

Submission

In preparation, you must (1) run checkstyle to ensure your code is checkstyle compliant (if not, fix the styling issues). (2) Create a zip file containing the src folder (and all therein). (3) Submit the zip file to Gradescope.

You can submit as many times as you like until deadline. We will only grade the last submission.

Rubric

Teaching assistants will evaluate your submission using the following criteria:

Please note, we reserve the right to change this rubric without advance notice, even after the submission deadline. However, the chances of doing so are slim, and at any rate, should not be a significant change.

• Spec 1: SparseMaze constructor correctly initializes dimensions, default value, and uses a sentinel node. Throws DimensionException for invalid dimensions. [2 points]

• Spec 2: SparseMaze.getWidth and SparseMaze.getHeight return correct dimensions consistently. [1 point]

• Spec 3: SparseMaze.getDefaultValue returns the correct default value and remains consistent during modifications. [1 point]

• Spec 4: SparseMaze.isOpen is implemented correctly and efficiently searches the sparse linked list. [2 points]

• Spec 5: SparseMaze.setCell correctly adds, updates, and removes nodes. Properly maintains sparsity by only storing non-default values. [3 points]

• Spec 6: SparseMaze.setCell correctly maintains the storedCellCount field when adding or removing nodes. [1 points]

• Spec 7: SparseMaze.setCell throws CellIndexOutOfBoundsException for invalid coordinates. [0.5 points]

• Spec 8: SparseMaze.clear correctly resets the maze to new default state, clears all stored nodes, and resets storedCellCount. [1.5 points]

• Spec 9: The SparseMaze iterator correctly traverses all cells in row-major order, returning stored values or default values as appropriate. [2 points]

• Spec 10: The SparseMaze iterator is efficient, avoiding unnecessary searching or computation during traversal. [2 points]

• Spec 11: Implementation uses only a singly linked list with sentinel node (no doubly linked list, tail pointer, or Java Collections). [1 point]

• Spec 12: The code exhibits good programming style, including modular organization, appropriate method lengths, and proper encapsulation. The Node class is properly nested and private/protected. [1 point]

The total score for this homework is 18 points.