Begin with the starter code provided

package game;

import java.util.List; import java.util.Stack;

public interface Game {

public enum Player {X, O} public Player getTurn();

public Move getAutoMove();

public Move getPlayerMove(int row, int col);

public Board getBoard();

public boolean checkForVictory();

public boolean isStalemated();

public boolean isOver(); public Player getPlayer();

public void undo(); public void redo(); public Stack getHistory(); public Stack getUndone(); public String getStacks();

}

--------------------------------------------------------------

package game;

import java.util.Stack;

import solver.SolverImpl; import solver.TicTacToeSolver;

public class GameImpl implements Game { private Player player; private Player turn; private Board board; private TicTacToeSolver autoPlayer; private Stack history;

private Stack undone;

public GameImpl(Player playerIn) { player = playerIn; history = new Stack(); undone = new Stack(); turn = Player.X; autoPlayer = new SolverImpl(); board = new Board();

}

@Override public Player getTurn() { return turn; }

private void switchTurns() { if (turn == Player.X) turn = Player.O; else turn = Player.X; }

@Override public Move getAutoMove() { Move m = autoPlayer.getMove(turn, board); history.push(new Board(board)); board.setValue(m.getRow(), m.getCol(), String.valueOf(m.getPlayer()).charAt(0)); switchTurns(); return m; }

@Override public Move getPlayerMove(int row, int col) { Move m = new MoveImpl(player, row, col); history.push(new Board(board)); board.setValue(m.getRow(), m.getCol(), String.valueOf(m.getPlayer()).charAt(0)); switchTurns(); return m; }

@Override public Board getBoard() { return board; }

public Stack getHistory() { return history; }

public Stack getUndone() { return undone; }

@Override public boolean checkForVictory() { if (rowVictory()) return true; if (colVictory()) return true; if (diagonalVictory()) return true; return false; }

private boolean rowVictory() { Character curr = ' '; for (int row = 0; row < 3; row++) { curr = board.getValue(row, 0); if (curr != ' ' && curr == board.getValue(row, 1) && curr == board.getValue(row, 2)) { return true; } } return false; }

private boolean colVictory() { char curr = ' '; for (int col = 0; col < 3; col++) { curr = board.getValue(0, col); if (curr != ' ' && curr == board.getValue(1, col) && curr == board.getValue(2, col)) return true; } return false; }

private boolean diagonalVictory() { char curr = ' '; curr = board.getValue(0, 0); if (curr != ' ') { if (board.getValue(1, 1) == curr & board.getValue(2, 2) == curr) { return true; } }

curr = board.getValue(0, 2); if (curr != ' ') { if (board.getValue(1, 1) == curr & board.getValue(2, 0) == curr) { return true; } } return false; }

@Override public boolean isStalemated() { for (int row = 0; row < 3; row++) for (int col = 0; col < 3; col++) if (board.getValue(row, col) == ' ') return false; return true; }

@Override public boolean isOver() { return checkForVictory() || isStalemated(); }

@Override public Player getPlayer() { return player; }

@Override public void undo() {

//complete this method }

@Override public void redo() { //complete this method } public String getStacks(){ // complete this method return null; // this line is just to prevent a syntax error in the starter code. Replace it. } }

----------------------------------------------------------------

This application implements the game Tic Tac Toe. Study the code one class at a time until you understand it. Note that the game board is represented by a class that contains a two-dimensional array of Characters. I recommend you look at the classes in this bottom-up order:

1. Board
2. Move, which is an interface that defines what a class must contain to model a Tic Tac Toe move, and MoveImpl, which implements Move
3. TicTacToeSolver, an interface that defines what a class must contain to be able to calculate automatic moves for the application, and SolverImpl.
4. Game, an interface, and GameImpl
5. TicTacToe UI, which provides the user interface
6. TTTMain, which just has a main() method to start the application.

Part I:

Code that implements undo and redo functionality has been removed from GameImpl. Your assignment is to implement these features. All the code you write will be in GameImpl.java. DO NOT CHANGE CODE IN ANY OTHER CLASSES, because your GameImpl.java must work with the rest of the code in its original state.

You will need two stacks of Boards, one for boards that represent states on the path to the current state, and one for boards that represent states that have been undone.

Note the comments I have made at several points in GameImpl.java.

getStacks() should return the toString of each Board in the undone stack and each Board in the history stack. It should not print them out, just return one big String.

Part II:

Write JUnit tests to test your work. Note that the methods used to play the game are all public methods in GameImpl. Make some moves, undo some of them, and check the number of Boards on the stack and some of the values at particular squares. Then redo some moves and test in the same way.

Turn in GameImpl.java, and JUnit test case