kainm
BAN USER//Winner will be declared in constant time, no need to run loops to check winner on each move.
//This is main class to run a sample case
public class TicTacToeSample {
public static void main(String[] args) {
try {
final Board board = new Board(3);
Player X = new Player("X", board);
Player Y = new Player("Y", board);
X.takePosition(0, 0);
Y.takePosition(1, 1);
X.takePosition(2, 0);
Y.takePosition(2, 0);
Y.takePosition(1, 0);
X.takePosition(2, 2);
Y.takePosition(1, 2);
X.takePosition(2, 1);
} catch (WinnerException e) {
System.out.println(e.getMessage());
}
}
}
class Board{
private final Player[][] board;
private final int size;
public Board(int size){
this.size = size;
this.board = new Player[size][size];
}
public int getRows() {
return size;
}
public int getCols() {
return size;
}
public int getDiagonals() {
return 2;
}
public void setOnwer(Player player, int row, int col) throws IllegalStateException {
if(board[row][col] == null){
board[row][col] = player;
}else{
throw new IllegalStateException("Position already taken by player " + board[row][col]);
}
}
public Player getOnwer(int row, int col) {
return board[row][col];
}
public int totalPositions() {
return size;
}
}
@SuppressWarnings("serial")
class WinnerException extends Exception{
public WinnerException(String msg) {
super(msg);
}
}
class Player{
private final String name;
private final Board board;
private final int[] rows;
private final int[] cols;
private final int[] diagonal;
public Player(String name, Board board){
this.name = name;
this.board = board;
this.rows = new int[board.getRows()];
this.cols = new int[board.getCols()];
this.diagonal = new int[2];
}
@Override
public String toString() {
return name;
}
public void takePosition(int row, int col) throws WinnerException {
board.setOnwer(this, row, col);
if(++rows[row] == board.totalPositions()){
throw new WinnerException("Game winner is player " + this + " taken complete row " + row );
}
if(++cols[col] == board.totalPositions()){
throw new WinnerException("Game winner is player " + this + " taken complete column " + row );
}
if(row == col){
if(++diagonal[0] == board.totalPositions()){
throw new WinnerException("Game winner is player " + this + " taken complete diagonal left");
}
}
if(row + col + 1 == board.totalPositions()){
if(++diagonal[1] == board.totalPositions()){
throw new WinnerException("Game winner is player " + this + " taken complete diagonal right");
}
}
}
}
The required data structure will compose of following standard data structures:
{
1. ArrayList<ItemObject> list;
//ArrayList to store all items.
2. TreeMap<KeyValue, List<Position>> index;
//TreeMap for Key to Item Indexing and Sorted order iteration.
//KeyValue is value of any key in Item and Position is index number of Item in ArrayList. List Of Position is taken because multiple Items may have same key.
3. HashMap<KeyType, TreeMap<KeyValue, List<Position>>> mapOfIndexes;
//HashMap to manage indexes for each key type.
//KeyType is type of key and TreeMap is described above as index.
The required operations are as follow:
method add(item): void
1. add item in ArrayList and save its position.
2. For each key in itemObject, get TreeMap from HashMap and add itemPosition in TreeMap.
method search(key): List<Item>
1. Get TreeMap from HashMap for provided key
2. Get List of position from TreeMap for the key value
3. Prepare List Of item from List of position
4. return List Of Items
method delete(key): List<Item>
1. Using search method get List Of item
2. Delete items from ArrayList and also delete its mapping from all TreeMap
method sortedIterator(keytype): Iterator
1. Get TreeMap from HashMap for provided key
2. Get EntrySet from TreeMap
3. return EntrySet.iterator();
}
All operation are almost constant time.
- kainm July 11, 2014