Implement each method in A5Stack.java and show output in A5Tester.java public class A5Stack implements Stack { private Node head; public A5Stack() { // TODO: implement this } public void push(T v) { // TODO: implement this } public T pop() { // TODO: implement this return null; // so it compiles } public T top() { // TODO: implement this return null; // so it compiles } public void popAll() { // TODO: implement this } public boolean isEmpty() { // TODO: implement this return false; // so it compiles } }

public class MazeRunner { Maze mazeToSolve; A5Stack path; FilePrinter fileWriter; public MazeRunner(Maze aMaze) { mazeToSolve = aMaze; path = new A5Stack(); fileWriter = new FilePrinter(); } /* * Purpose: Determines whether there is a path from start to finish in this maze * Parameters: MazeLocation start - starting coordinates of this maze * MazeLocation finish - finish coordinates of this maze * Returns: true if there is a path from start to finish */ public boolean solve(MazeLocation start, MazeLocation finish) { fileWriter.println("Searching maze from start: "+start+" to finish: "+finish); path.push(start); return findPath(start, finish); } /* * Purpose: Recursively determines if there is a path from cur to finish * Parameters: MazeLocation cur - current cordinates in this maze * MazeLocation finish - goal coordinates of this maze * Returns: true if there is a path from cur to finish * * NOTE: This method updates the Maze's mazeData array when locations * are visited to an 'o', and further updates locations to an 'x' * if it is determined they lead to dead ends. If the finish * location is found, the Stack named path should contain all of * loations visited from the start location to the finish. */ private boolean findPath(MazeLocation cur, MazeLocation finish) { int row = cur.getRow(); int col = cur.getCol(); mazeToSolve.setChar(row, col, 'o'); fileWriter.println(" "+mazeToSolve.toString()); return false; // so it compiles } /* * Purpose: Creates a string of maze locations found in the stack * Parameters: None * Returns: A String representation of maze locations */ public String getPathToSolution() { String details = ""; while(!path.isEmpty()) { details = path.pop() + " " + details; } return details; } /* * Purpose: Print the results of the maze run. Outputs the locations * visited on the path from start to finish if the maze is * solvable, or that no path was found if it is not. * Parameters: boolean - whether or not the maze was solved * Returns void - nothing */ public void printResults(boolean solved) { if (solved) { fileWriter.println(" *** Maze Solved ***"); fileWriter.println(getPathToSolution()); } else { fileWriter.println(" --- No path to solution found ---"); } fileWriter.close(); } }

public class A5Tester { private static int testPassCount = 0; private static int testCount = 0; public static void main(String[] args) { testStackOperations(); testStackIsGeneric(); testExceptions(); testMazeRunner(args); System.out.println("Passed " + testPassCount + " / " + testCount + " tests"); } public static void testStackOperations() { System.out.println("Stack Operations Tests:"); A5Stack testStack = new A5Stack(); int result = 0; displayResults(testStack.isEmpty(), "stack initially empty"); testStack.push(2); result = testStack.top(); displayResults(!testStack.isEmpty(), "stack no longer empty"); displayResults(result==2, "top works after initial push"); //TODO: add more tests here System.out.println(); } public static void testStackIsGeneric() { System.out.println("Stack Generics Tests:"); A5Stack s1 = new A5Stack(); A5Stack s2 = new A5Stack(); A5Stack s3 = new A5Stack(); int result1; String result2; double result3; s1.push(3); s1.push(8); s2.push("CSC"); s2.push("ENGR"); s3.push(5.5); s3.push(9.1); result1 = s1.pop(); result2 = s2.pop(); result3 = s3.pop(); displayResults(result1==8, "Integer Stack"); displayResults(result2.equals("ENGR"), "String Stack"); displayResults(result3==9.1, "Double Stack"); result1 = s1.top(); result2 = s2.top(); result3 = s3.top(); displayResults(result1==3, "Integer Stack"); displayResults(result2.equals("CSC"), "String Stack"); displayResults(result3==5.5, "Double Stack"); //TODO: add more tests here System.out.println(); } public static void testExceptions() { System.out.println("Stack Exception Tests:"); A5Stack s1 = new A5Stack(); try { s1.pop(); displayResults(false, "popping from empty stack should throw exception"); } catch (EmptyStackException e) { displayResults(true, "popping from empty stack should throw StackEmptyException"); } catch (Exception e) { displayResults(false, "popping from empty stack should throw exception"); } try { s1.top(); displayResults(false, "trying to get top from empty stack should throw exception"); } catch (EmptyStackException e) { displayResults(true, "trying to get top from empty stack should throw StackEmptyException"); } catch (Exception e) { displayResults(false, "trying to get top from empty stack should throw exception"); } //TODO: add more tests here System.out.println(); } public static void testMazeRunner(String[] args) { if (args.length < 1) { displayResults(false, "testing MazeRunner"); System.err.println("You must specify a maze file"); System.err.println("Usage: java A5Tester "); return; } System.out.println("testing MazeRunner with "+args[0]); System.out.println("Results are in A5-output.txt"); Maze maze = initialize(args[0]); MazeRunner mr = new MazeRunner(maze); boolean solved = mr.solve(maze.getStart(), maze.getFinish()); mr.printResults(solved); } /* * Purpose: Creates a maze by reading the contents of an input file * Parameters: String - name of the input file containing maze data * Returns: Maze - the maze created from input file data */ public static Maze initialize(String data) { try { Scanner infileScanner = new Scanner(new File(data)); int rows = infileScanner.nextInt(); int columns = infileScanner.nextInt(); int startRow = infileScanner.nextInt(); int startColumn = infileScanner.nextInt(); int finishRow = infileScanner.nextInt(); int finishColumn = infileScanner.nextInt(); infileScanner.nextLine(); char[][] mazeData = new char[rows][columns]; for (int row = 0; row < rows; row++) { String line = infileScanner.nextLine(); for (int col = 0; col < columns; col++) { mazeData[row][col] = line.charAt(col); } } return new Maze(mazeData, new MazeLocation(startRow, startColumn), new MazeLocation(finishRow, finishColumn)); } catch (FileNotFoundException ex) { System.out.println("Error scanning file "+data); System.exit(2); } catch(NoSuchElementException ex) { System.out.println("Maze data file is not formatted correctly, should be:"); System.out.println(" "); System.out.println(" "); System.out.println(" "); System.out.println(""); System.out.println("Example:"); System.out.println("7 8"); System.out.println("0 1"); System.out.println("6 6"); System.out.println("H HHHHHH"); System.out.println("H H H"); System.out.println("HHHH H H"); System.out.println("H H"); System.out.println("H HHHHHH"); System.out.println("H H"); System.out.println("HHHHHH H"); System.exit(3); } return null; } public static void displayResults (boolean passed, String testName) { /* There is some magic going on here getting the line number * Borrowed from: * http://blog.taragana.com/index.php/archive/core-java-how-to-get-java-source-code-line-number-file-name-in-code/ */ testCount++; if (passed) { System.out.println ("Passed test: " + testName); testPassCount++; } else { System.out.println ("Failed test: " + testName + " at line " + Thread.currentThread().getStackTrace()[2].getLineNumber()); } } }

interface Stack { /* * Purpose: Insert an item onto the top of the stack * Parameters: T - the item to insert * Returns: Nothing */ public void push(T v); /* * Purpose: Removes and returns the top item from the stack * Parameters: None * Returns: T - the data value of the element removed * Throws: EmptyStackException if stack is empty */ public T pop(); /* * Purpose: Accesses the top item on the stack * Parameters: None * Returns: T - the data value of the top element * Throws: EmptyStackException if stack is empty */ public T top(); /* * Purpose: Determines whether the stack is empty * Parameters: None * Returns: boolean - true if the stack is empty, false otherwise */ public boolean isEmpty(); /* * Purpose: Removes all elements from the stack * Parameters: None * Returns: Nothing */ public void popAll(); }

public class Node{ private T data; protected Node next; public Node (T value) { this.data = value; this.next = null; } /* Parameters: nothing * Purpose: get the data value of this Node * Returns: int - the value */ public T getData() { return data; } /* Parameters: nothing * Purpose: get the next of this Node * Returns: (Node) the next */ public Node getNext() { return next; } /* Parameters: Node next * Purpose: set the next of this Node to next * Returns: nothing */ public void setNext(Node next) { this.next = next; } }