import java.util.*;

/** This is the board object that will hold references to pieces in the
arrangement they are found on the chess board.  It is implemented using an
array of ChessPiece references.  It also has a copy() method that is used to
make copies of it for the tree used in deciding how to move. */
public class Board
{
	/** This is the array of ChessPieces.  It is an 8 by 8 array of ChessPiece
	references.  Nothing more, nothing less. */
	protected ChessPiece[][] board = new ChessPiece[8][8];
        
        // These Stacks store a history of the game for unmaking moves
        private Stack captureStack, moveStack;
	
	/** Builds a new board setup to start a new game of chess. */
	public Board()
	{
                // Initialize the stacks;
                captureStack = new Stack();
                moveStack = new Stack();
                
                // Associate references of the board[][] object with appropriate chess
                // pieces.  I hope this will be good enough for pseudocode.
                
                // Add the pawns for both sides
                for (int i = 0; i < 8; i++) {
                        setPiece(1, i, new ChessPiece(0 /*pawn*/, true /*white*/));
                        setPiece(6, i, new ChessPiece(0 /*pawn*/, false /*black*/));
                }
                
                // Add the rooks for each side
                setPiece(0, 0, new ChessPiece(3 /*rook*/, true /*white*/));
                setPiece(0, 7, new ChessPiece(3 /*rook*/, true /*white*/));
                setPiece(7, 0, new ChessPiece(3 /*rook*/, false /*black*/));
                setPiece(7, 7, new ChessPiece(3 /*rook*/, false /*black*/));
                
                // Add the knights for each side
                setPiece(0, 1, new ChessPiece(1 /*knight*/, true /*white*/));
                setPiece(0, 6, new ChessPiece(1 /*knight*/, true /*white*/));
                setPiece(7, 1, new ChessPiece(1 /*knight*/, false /*black*/));
                setPiece(7, 6, new ChessPiece(1 /*knight*/, false /*black*/));
                
                // Add the bishops for each side
                setPiece(0, 2, new ChessPiece(2 /*bishop*/, true /*white*/));
                setPiece(0, 5, new ChessPiece(2 /*bishop*/, true /*white*/));
                setPiece(7, 2, new ChessPiece(2 /*bishop*/, false /*black*/));
                setPiece(7, 5, new ChessPiece(2 /*bishop*/, false /*black*/));
                
                // Add the king and queen for each side
                setPiece(0, 3, new ChessPiece(4 /*queen*/, true /*white*/));
                setPiece(0, 4, new ChessPiece(5 /*king*/, true /*white*/));
                setPiece(7, 3, new ChessPiece(4 /*queen*/, false /*black*/));
                setPiece(7, 4, new ChessPiece(5 /*king*/, false /*black*/));
	}
	
	/** Builds a new board based on the given board.  This constructor is used in
	copy(). 
        @param <CODE>b</CODE>
                The board to copy. This method no longer works.
        */
	public Board(Board b)
	{
                /* pseudocode
                for all squares s in b
                        setPiece(s, a copy of b.getPiece(s))
                */
                
                for (int i = 0; i < 8; i++) {
                        for (int j = 0; j < 8; j++) {
                                if (b.getPiece(i, j) != null)
                                        this.setPiece(i, j, b.getPiece(i, j).copy());
                        }
                }
	}
	
	/** Returns the piece at the specified location.
        @param <CODE>row</CODE>
                The row of the piece.
        @param <CODE>col</CODE>
                The column of the piece.
        @return The <CODE>ChessPiece</CODE> at <CODE>row</CODE>, <CODE>col</CODE>.
        */
	public ChessPiece getPiece(int row, int col)
	{
                // Returns null if there is no piece
		return board[row][col];
	}
	
	/** Used to add pieces to the board.  Should only be needed by the
	constructors and the copy() method. 
        @param <CODE>row</CODE>
                The row of the piece.
        @param <CODE>col</CODE>
                The column of the piece.
        @param <CODE>piece</CODE>
                The <CODE>ChessPiece</CODE> to be added to this <CODE>Board</CODE>
        */
	protected void setPiece(int row, int col, ChessPiece piece)
	{
                // Hopefully board[row][col] will be set to null if piece is null
                board[row][col] = piece;
	}
	
	/** Makes a move according to the specified Move object, taking pieces if
	needed (by simply overwriting their spot in the array), leaving a null
	reference behind where the piece was originally located. 
        @param <CODE>theMove</CODE>
                The <CODE>Move</CODE> to be applied to this board.  
                The move should be logical for this board, but does 
                not necessarily have to be legal.
        */
        
        // Precondition: the move must be logical for this board
        //               (i.e. the source should not be null/empty, and the Move
        //                should be on this board.)
        // Postcondition: the move's source is null/empty and the dest is non-null
	public void movePiece(Move theMove)
	{
                        
                //ChessEngine.outWriter.println("Applying to board move: " + theMove);

                // Push this move onto the stack
                moveStack.push(theMove);
                
                // Just for the sake of ease
                int sourceRow = theMove.getSourceRow();
                int sourceCol = theMove.getSourceCol();
                int destRow = theMove.getDestRow();
                int destCol = theMove.getDestCol();
                
                // If the destination isn't empty set the lastCapture field to point to
                // the piece that was there.  Otherwise make the destination
                // square point to the piece that was the source and make the source null.                
                if (board[destRow][destCol] != null) {
                        captureStack.push(board[destRow][destCol]);
                } else {
                        // Make sure that we don't think the last move yielded a capture.
                        captureStack.push(new Object() /* Any old object */);
                }
                board[destRow][destCol] = board[sourceRow][sourceCol];
                board[sourceRow][sourceCol] = null;
	}
        
        /** Makes a move. Calls movePiece with theMove.*/
        public void makeMove(Move theMove) {
                if (isLegal(theMove)) {
                        movePiece(theMove);
                }
        }
        
        /** Unmakes the last move made via movePiece() on this <CODE>Board</CODE>.
        If no move was previously made does nothing.
        */
        public void unmakeMove() {
                // Get the most recent move if the stack is not empty
                Move theMove;
                try {
                        theMove = (Move)moveStack.pop();
                } catch (EmptyStackException ex) {
                        return;
                }
                
                // Reverse the process of movePiece
                int sourceRow = theMove.getSourceRow();
                int sourceCol = theMove.getSourceCol();
                int destRow = theMove.getDestRow();
                int destCol = theMove.getDestCol();
                
                board[sourceRow][sourceCol] = board[destRow][destCol];
                
                // We try to cast the item on the top of the stack to a ChessPiece
                // If it is not a ChessPiece just set the square to null.
                try {
                        board[destRow][destCol] = (ChessPiece)captureStack.pop();
                } catch (ClassCastException ex) {
                        board[destRow][destCol] = null;
                }
        }
	
	/** Returns the current material value of the board.  Treating white pieces
	as negetive and black as positive. */
	public int evaluate()
	{ChessPiece piece; //Variable only used for readability
         
         int total=0; //return value of total points
                      //negative #'a are a good score for white
                      //positive #'s are a good score for black
         
         //go through every piece on the board
         for (int x=0; x<8; x++)
          for (int y=0; y<8; y++)
           if (board[x][y] != null)
           {
            piece=board[x][y]; //improve readability
            
            if (piece.isWhite()) //subtract values if white
            {total -= piece.value();
             
             if (piece.type() == ChessPiece.TYPE_PAWN)
              total -= WPawn_PosValue[x][y];
             else if (piece.type() == ChessPiece.TYPE_KNIGHT)
              total -= Knight_PosValue[x][y];
             else if (piece.type() == ChessPiece.TYPE_BISHOP)
              total -= Bishop_PosValue[x][y];
             else if (piece.type() == ChessPiece.TYPE_ROOK)
              total -= WRook_PosValue[x][y];
             else if (piece.type() == ChessPiece.TYPE_QUEEN)
              total -= Queen_PosValue[x][y];
             else if (piece.type() == ChessPiece.TYPE_KING)
              total -= WKing_PosValue[x][y];
            
            }//end of if the piece is white
            
            else //piece is black
            {total += piece.value();
             
            if (piece.type() == ChessPiece.TYPE_PAWN)
              total += BPawn_PosValue[x][y];
             else if (piece.type() == ChessPiece.TYPE_KNIGHT)
              total += Knight_PosValue[x][y];
             else if (piece.type() == ChessPiece.TYPE_BISHOP)
              total += Bishop_PosValue[x][y];
             else if (piece.type() == ChessPiece.TYPE_ROOK)
              total += BRook_PosValue[x][y];
             else if (piece.type() == ChessPiece.TYPE_QUEEN)
              total += Queen_PosValue[x][y];
             else if (piece.type() == ChessPiece.TYPE_KING)
              total += BKing_PosValue[x][y];
            }//end of else piece is black          
           }//end of for loop
         
         //check to see if your in check
         /*this may be skipped to increase simplicity in our project
         if (MyKingInCheck())
          if (WhitesTurn)
           total += 15;
          else
           total -= 15;
         */
         
         return total;
	}//end of Evaluate
	
	/** Returns a field for field copy of this object.  It calls the copy() method
	of ChessPiece, making copies of the pieces on the board as well.  This is so
	the entire board can be manipulated independently from the actual chess board.
        This method no longer works.
        @return A copy of this <CODE>Board</CODE>.
	*/
	public Board copy()
	{
                // Using the copy constructor idea elaborated by the design team we
                // should just call the copy constructor with this board instance.
                return new Board(this);
	}
	
        /** Constructs the string representation of this board. 
        @return The string representation of this <CODE>Board</CODE>.
        */
        public String toString() {
                String s = "";
                // I decided to switch to counting down so that white is at the
                // bottom, but still in the right rank/file/whatever.
                for (int i = 7; i >= 0; i--) {
                        s = s + (i + 1) + " ";
                        for (int j = 0; j < 8; j++) {
                                if (board[i][j] == null) {
                                        s = s + ". ";
                                } else {
                                        s = s + board[i][j] + " ";
                                }
                        }
                        s = s + "\n";
                }
                s = s + "  a b c d e f g h\n";
                return s;
        }
        
        public boolean isLegal(Move move) {
                // If the move goes out of bounds then it is not legal
                // This is ugly and inefficient, but works for now.
                ChessPiece source, dest;
                try {
                        source = board[move.getSourceRow()][move.getSourceCol()];
                        dest = board[move.getDestRow()][move.getDestCol()];
                } catch (ArrayIndexOutOfBoundsException ex) {
                        return false;
                }
                
                // If the move source is null or the source and dest refer to
                // the same piece then it really isn't a move at all.
                if (source == null || source == dest) {
                        return false;
                }
                
                // If the move tries to capture a friend then it is not legal
                if (dest != null) {
                        if ((source.isWhite() && dest.isWhite()) ||
                            (!source.isWhite() && !dest.isWhite())) {
                                return false;
                        }
                }
                
                int sr = move.getSourceRow();
                int dr = move.getDestRow();
                int sc = move.getSourceCol();
                int dc = move.getDestCol();
                
                // Evaluate all of the possible moves based on the piece type
                // The remainder of this code is extremely inelegant.
                // I should be ashamed of myself for even thinking of writing it.
                // We should please use this method sparingly.
                // Update: I changed from an iterative to a recursive solution
                // for the slides.  It makes the code no smaller, but I believe
                // that it is a great deal easier to read.  Also the remainder
                // of the code is no less inelegant.
                if (source.type() == ChessPiece.TYPE_KNIGHT) {
                        if ((Math.abs(dr - sr) == 2  && (Math.abs(dc - sc) == 1)) ||
                            (Math.abs(dr - sr) == 1  && (Math.abs(dc - sc) == 2))) {
                                return true;
                        }
                } else if (source.type() == ChessPiece.TYPE_PAWN) {
                        // This is extremely ugly and needs to be changed.
                        if ((dest != null && ((source.isWhite() && dr - sr == 1) ||
                                              (!source.isWhite() && dr - sr == -1)) && 
                             Math.abs(dc - sc) == 1) ||
                            (dest == null && ((source.isWhite() && (dr - sr == 1 || 
                                               (dr - sr == 2 && sr == 1 &&
                                                board[sr + 1][sc] == null)) ||
                                              (!source.isWhite() && (dr - sr == -1 || 
                                               (dr - sr == -2 && sr == 6 &&
                                                board[sr - 1][sc] == null))) && 
                             dc == sc)))) {
                                return true;
                        }
                } else if (source.type() == ChessPiece.TYPE_KING) {
                        if ((Math.abs(dr - sr) == 1 || Math.abs(dr - sr) == 0) &&
                            (Math.abs(dc - sc) == 1 || Math.abs(dc - sc) == 0)) {
                                return  true;
                        }
                } else if (source.type() == ChessPiece.TYPE_ROOK) {
                        return canSlideStraight(sr, sc, dr, dc, true);
                } else if (source.type() == ChessPiece.TYPE_BISHOP) {
                        return canSlideDiagonal(sr, sc, dr, dc, true);
                } else if (source.type() == ChessPiece.TYPE_QUEEN) {
                        return (canSlideStraight(sr, sc, dr, dc, true) ||
                                canSlideDiagonal(sr, sc, dr, dc, true));
                }
                
                return false;
        }
        
        // I believe that the two following methods could be combined into one because
        // they share much code in common, but I am lazy, and that might be more 
        // difficult to understand.
        private boolean canSlideDiagonal(int sr, int sc, int dr, int dc, boolean endOfSlide) {
                // Grounding conditions for recursion
                if (sr == dr && sc == dc) {
                        // We have finished checking intervening moves
                        return true;
                }
                
                
                if (board[dr][dc] != null && !endOfSlide) {
                        // Somebody is in the way of this move
                        return false;
                }
                
                
                // Recursively call this function for each move between the given move
                // in order to see if the move jumps over anybody.
                // An efficient solution would not use a try-catch block to detect
                // a divide-by-zero exception.
                try {
                        if (((double)(dr -sr))/((double)(dc - sc)) == 1) {
                                if (dc - sc > 0) {
                                        // Sliding right and up
                                        return canSlideDiagonal(sr, sc, dr - 1, dc - 1, false);
                                } else {
                                        // Sliding left and down
                                        return canSlideDiagonal(sr, sc, dr + 1, dc + 1, false);
                                }
                        } else if (((double)(dr - sr))/((double)(dc - sc)) == -1) {
                                if (dr - sr > 0) {
                                        // Sliding left and up
                                        return canSlideDiagonal(sr, sc, dr - 1, dc + 1, false);
                                } else {
                                        // Sliding right and down
                                        return canSlideDiagonal(sr, sc, dr + 1, dc - 1, false);
                                }
                        }
                } catch (ArithmeticException ex) {
                        return false;
                }
                
                // We get here in the event that the slide is not valid at all
                // (i.e. the quotient of the differences between the rank and file
                // are not zero)
                return false;
        }
        
        private boolean canSlideStraight(int sr, int sc, int dr, int dc, boolean endOfSlide) {
                // Refer to comments for diagonal slides
                if (sr == dr && sc == dc) {
                        return true;
                }
                
                if (board[dr][dc] != null && !endOfSlide) {
                        // Somebody is in the way of this move
                        return false;
                }

                
                if (dr == sr) {
                        if (dc - sc > 0) {
                                // Sliding right
                                return canSlideStraight(sr, sc, dr, dc - 1, false);
                        } else {
                                // Sliding left
                                return canSlideStraight(sr, sc, dr, dc + 1, false);
                        }
                } else if (dc == sc) {
                        if (dr - sr > 0) {
                                // Sliding up
                                return canSlideStraight(sr, sc, dr - 1, dc, false);
                        } else {
                                //Sliding down
                                return canSlideStraight(sr, sc, dr + 1, dc, false);
                        }
                }
                
                return false;
        }
        
        private final int[][] WPawn_PosValue = { // Add value to the position of the pawn
          {14,14,14,14,14,14,14,14},
          {12,12,12,12,12,12,12,12},
          {10,10,10,10,10,10,10,10},
          { 8, 8, 8,10,10, 8, 8, 8},
          { 5, 5, 6, 9, 9, 6, 5, 5},
          { 4, 4, 4, 4, 4, 4, 4, 4},
          { 2, 2, 2, 2, 2, 2, 2, 2},
          { 0, 0, 0, 0, 0, 0, 0, 0}
         };
        
         private final int[][] BPawn_PosValue = {  // Add value to the position of the pawn
          { 0, 0, 0, 0, 0, 0, 0, 0},
          { 2, 2, 2, 2, 2, 2, 2, 2},
          { 4, 4, 4, 4, 4, 4, 4, 4},
          { 5, 5, 6, 9, 9, 6, 5, 5},
          { 8, 8, 8,10,10, 8, 8, 8},
          {10,10,10,10,10,10,10,10},
          {12,12,12,12,12,12,12,12},
          {14,14,14,14,14,14,14,14}
         };
         
         private final int[][] Knight_PosValue = {        // Add value to the position of the knight
          { 0, 1, 2, 2, 2, 2, 1, 0},
          { 1, 2, 3, 3, 3, 3, 2, 1},
          { 2, 3, 7, 5, 5, 7, 3, 2},
          { 2, 3, 5, 8, 8, 5, 3, 2},
          { 2, 3, 5, 8, 8, 5, 3, 2},
          { 2, 3, 7, 5, 5, 7, 3, 2},
          { 1, 2, 3, 3, 3, 3, 2, 1},
          { 0, 1, 2, 2, 2, 2, 1, 0}
         };
        
         
         private final int[][] WRook_PosValue = {        // Add value to the position of the Rook
          {4 , 4 , 4 , 4 , 4 , 4 , 4 , 4},
          {4 , 4 , 4 , 4 , 4 , 4 , 4 , 4},
          {2 , 2 , 2 , 4 , 4 , 2 , 2 , 2},
          {2 , 2 , 2 , 4 , 4 , 2 , 2 , 2},
          {2 , 2 , 2 , 4 , 4 , 2 , 2 , 2},
          {2 , 2 , 2 , 4 , 4 , 2 , 2 , 2},
          {2 , 2 , 2 , 6 , 6 , 2 , 2 , 2},
          {2 , 2 , 2 , 6 , 6 , 2 , 2 , 2}
         };
        
          private final int[][] BRook_PosValue = {        // Add value to the position of the Rook
           {2 , 2 , 2 , 6 , 6 , 2 , 2 , 2},
           {2 , 2 , 2 , 6 , 6 , 2 , 2 , 2},
           {2 , 2 , 2 , 4 , 4 , 2 , 2 , 2},
           {2 , 2 , 2 , 4 , 4 , 2 , 2 , 2},
           {2 , 2 , 2 , 4 , 4 , 2 , 2 , 2},
           {2 , 2 , 2 , 4 , 4 , 2 , 2 , 2},
           {4 , 4 , 4 , 4 , 4 , 4 , 4 , 4},
           {4 , 4 , 4 , 4 , 4 , 4 , 4 , 4}
          };
         
         private final int[][] Bishop_PosValue = {        // Add value to the position of the bishop
          {1 , 1 , 1 , 1 , 1 , 1 , 1 , 1},
          {1 , 2 , 2 , 2 , 2 , 2 , 2 , 1},
          {1 , 2 , 4 , 4 , 4 , 4 , 2 , 1},
          {1 , 2 , 4 , 6 , 6 , 4 , 2 , 1},
          {1 , 2 , 4 , 6 , 6 , 4 , 2 , 1},
          {1 , 2 , 4 , 4 , 4 , 4 , 2 , 1},
          {1 , 2 , 2 , 2 , 2 , 2 , 2 , 1},
          {1 , 1 , 1 , 1 , 1 , 1 , 1 , 1}
         };
         
          private final int[][] Queen_PosValue = {  // Add value to the position of the Queen
          {2 , 2 , 2 , 2 , 2 , 2 , 2 , 2},
          {2 , 3 , 3 , 3 , 3 , 3 , 3 , 2},
          {2 , 3 , 4 , 4 , 4 , 4 , 3 , 2},
          {2 , 3 , 4 , 5 , 5 , 4 , 3 , 2},
          {2 , 3 , 4 , 5 , 5 , 4 , 3 , 2},
          {2 , 3 , 4 , 4 , 4 , 4 , 3 , 2},
          {2 , 3 , 3 , 3 , 3 , 3 , 3 , 2},
          {2 , 2 , 2 , 2 , 2 , 2 , 2 , 2} 
         };
           
         private final int[][] WKing_PosValue = {        // Add value to the position of the king
           {-8,-8,-8,-8,-8,-8,-8,-8},
           {-8,-8,-8,-8,-8,-8,-8,-8},
           {-8,-8,-8,-8,-8,-8,-8,-8},
           {-8,-8,-8,-8,-8,-8,-8,-8},
           {-8,-8,-8,-8,-8,-8,-8,-8},
           {-8,-8,-8,-8,-8,-8,-8,-8},
           { 1, 1, 1, 1, 1, 1, 1, 1},
           { 1, 1, 9, 1, 1, 2, 9, 2}
         };
        
         private final int[][] BKing_PosValue = {        // Add value to the position of the king
          { 1, 1, 9, 1, 1, 2, 9, 2},
          { 1, 1, 1, 1, 1, 1, 1, 1},
          {-8,-8,-8,-8,-8,-8,-8,-8},
          {-8,-8,-8,-8,-8,-8,-8,-8},
          {-8,-8,-8,-8,-8,-8,-8,-8},
          {-8,-8,-8,-8,-8,-8,-8,-8},
          {-8,-8,-8,-8,-8,-8,-8,-8},
          {-8,-8,-8,-8,-8,-8,-8,-8}
         };

}