import java.awt.Color; import java.awt.Graphics; /** * Project 05 scaffold: the search algorithm shared by DFS and BFS. * * PROVIDED: fields, constructor, getters, the four abstract frontier methods, * and the two-argument search. * YOU WRITE: reset (Task 1), traceback (Task 2), search (Task 3), draw (Task 6). * * This class never knows whether the frontier is a Stack or a Queue. It only * calls the four abstract methods; each subclass decides what they do. */ public abstract class AbstractMazeSearch { private Maze maze; private Cell start; private Cell target; private Cell cur; /** * Saves the maze. Subclasses create their own frontier in THEIR constructors; * do not call the abstract methods from here. */ public AbstractMazeSearch(Maze maze) { this.maze = maze; this.start = null; this.target = null; this.cur = null; } public Maze getMaze() { return maze; } public Cell getStart() { return start; } public Cell getTarget() { return target; } public Cell getCur() { return cur; } public void setCur(Cell cell) { this.cur = cell; } // ------------------------------------------------------------------ // The frontier contract. Each subclass fills these in (Task 4). // ------------------------------------------------------------------ /** Removes and returns the next Cell to explore. */ public abstract Cell findNextCell(); /** Adds a newly discovered Cell to the frontier. */ public abstract void addCell(Cell next); /** Returns the number of Cells waiting in the frontier. */ public abstract int numRemainingCells(); /** Empties the frontier so a repeated search starts fresh. */ public abstract void clearFrontier(); // ------------------------------------------------------------------ // Shared code: written once, used by both searches. // ------------------------------------------------------------------ /** * Task 1: Clears the frontier, clears every Cell's prev in the maze, and sets * start, target, and cur back to null. */ public void reset() { // TODO } /** * Task 2: Returns the path from start to {@code cell}, start first and * {@code cell} last, by following prev links backward and pushing each Cell * onto the head of the result. Returns null if cell is null, undiscovered, * or the prev chain does not lead back to start. */ public LinkedList traceback(Cell cell) { // TODO return null; } /** Searches without a display. Provided. */ public LinkedList search(Cell start, Cell target) { return search(start, target, false, 0); } /** * Task 3: Searches from start to target. Returns the path found (start * first), or null if target is unreachable. Throws IllegalArgumentException * for invalid endpoints or a negative delay. * * Outline (details in Task 3 of the project page): * 1. Validate the arguments. * 2. Reset, then save start and target in the fields. * 3. Mark start discovered (start points to itself) and add it. * 4. While the frontier is nonempty: remove the next cell into cur; * if it is the target, return the traceback; otherwise mark and add * each undiscovered neighbor. * 5. The frontier emptied: return null. * Task 6 adds the display and delay inside this same method. */ public LinkedList search(Cell start, Cell target, boolean display, int delay) { // TODO return null; } /** * Task 6: Draws the maze, the discovered prev links, the current cell, the * found path, and finally the endpoints. Must work when start, target, or * cur is null. Called by MazeSearchDisplay. */ public void draw(Graphics g, int scale) { // TODO } }