import java.util.Random;

/**
 * This class implements the basic behaviour of a MineSweeper game board;
 * i.e. a grid of cells, each of which may contain a mine.  The cells are
 * initially covered (unknown) and can be selectively 'revealed'.  A revealed
 * cell either contains a mine or an integer indicating the number of mines in 
 * the (up to) eight adjacent cells.  Cells may also be 'marked', to indicate
 * cells that might contain a mine.  No more cells can be marked than there
 * are mines on the board.
 *
 * The board does not enforce any particular game rules (e.g. no special
 * action is taken if a mine is revealed).  Even the behaviour of the reveal() 
 * and mark() methods can be overridden if desired.  In particular, the draw() 
 * method is abtract and must be implemented in a subclass to give the board
 * any kind of visual representation.
 */
public abstract class Board {

  // Subclasses have access to protected variables

  // Board size
  protected int width, height;

  // Number of mines on the board
  protected int numMines;

  // Number of cells currently marked
  protected int numMarked;

  // Number of cells yet to be revealed
  protected int numUnknown;

  // Indicates where the mines are hidden
  protected boolean[][] mines;

  // The current state of the board
  protected int[][] board;

  // Constants for cell contents.  The MINE value might be returned by
  // reveal(), the others are only used internally but will probably be
  // required in subclasses.
  public static final int UNKNOWN = -1;
  public static final int MARKED = -2;
  public static final int MINE = -3;


  /**
   * Create a new game board with the given size and number of mines.  The
   * mines are randomly distributed across the board.  Currently no error
   * checking is done, so if numMines > width*height the program will hang.
   * C'est la vie.
   */
  public Board(int width, int height, int numMines) {

    // Initialise instance variables.  Note the use of 'this' when parameters
    // have the same name.
    this.width = width;
    this.height = height;
    this.numMines = numMines;
    this.numMarked = 0;
    this.numUnknown = width * height;

    // Allocate storage for game board and mines
    mines = new boolean[width][height];
    board = new int[width][height];

    // Clear the board
    for (int i = 0; i < width; i++) {
      for (int j = 0; j < height; j++) {
	mines[i][j] = false;
	board[i][j] = UNKNOWN;
      }
    }

    // Randomly allocate mines.  The loop runs until numMines mines have been
    // placed on the board.  The the purposes of this operation we treat the
    // board as a width*height linear array of cells, and simply try again if
    // the chosen cell already contains a mine.
    int cells = width * height;
    int temp = 0;
    Random rand = new Random();

    while (temp < numMines) {
      int cell = rand.nextInt();
      cell = (cell < 0 ? -cell : cell)%cells;
      if (!mines[cell%width][cell/width]) {
	mines[cell%width][cell/width] = true;
	temp++;
      }
    }
  }


  /**
   * Print/draw/(speak?) some representation of the board that can be
   * understood by a human player.  This method must be implemented by
   * subclasses.
   */
  public abstract void draw();


  /**
   * Reveal the contents of the cell at position (x, y) on the board.  Returns 
   * the contents thus revealed, which may be an integer in the range 0..8
   * indicating the number of neighbouring cells that contain a mine, or the
   * special constant MINE indicating that the cell contains a mine.
   */
  public int reveal(int x, int y) {
    switch (board[x][y]) {
     case MARKED:
      // If the cell was marked, unmark it
      numMarked--;
     case UNKNOWN:
      // One less unknown cell now
      numUnknown--;
      if (mines[x][y]) {
	board[x][y] = MINE;
      }
      else {
	// How many mines in the vicinity?
	board[x][y] = closeMines(x, y);
      }
      break;
    }
    // Return the revealed value
    return board[x][y];
  }


  /**
   * Reveal the contents of more cells around cell (x, y).  For each of the
   * (up to) eight cells surrounding (x, y):
   *    - if the cell contents are currently unknown and the cell does *not*
   *      contain a mine, the contents of the cell are revealed.
   *    - if the revealed cell is empty and has no neigbouring mines,
   *      revealMore() is called recursively on it.
   * The behaviour of this method is best understood by using it!
   */
  public void revealMore(int x, int y) {
    int minx, miny, maxx, maxy;
    int result = 0;

    // Don't try to check beyond the edges of the board...
    minx = (x <= 0 ? 0 : x - 1);
    miny = (y <= 0 ? 0 : y - 1);
    maxx = (x >= width - 1 ? width : x + 2);
    maxy = (y >= height - 1 ? height : y + 2);

    // Loop over all surrounding cells
    for (int i = minx; i < maxx; i++) {
      for (int j = miny; j < maxy; j++) {
	if (!mines[i][j] && board[i][j] == UNKNOWN) {
	  reveal(i, j);
	  if (board[i][j] == 0) {
	    // Call ourself recursively
	    revealMore(i, j);
	  }
	}
      }
    }
  }


  /**
   * 'Mark' the cell (x, y), probably to indicate that a player thinks there
   * may be a mine there.  Up to numMines cells may be marked simultaneously.
   * Returns true is the mark succeeded, false otherwise.
   */
  public boolean mark(int x, int y) {
    if ((numMines - numMarked) > 0 && board[x][y] == UNKNOWN) {
      board[x][y] = MARKED;
      numMarked++;
      return true;
    }
    else {
      return false;
    }
  }


  /**
   * Unmark the previously marked cell at (x, y).  Returns try if the unmark
   * succeeded (meaning that the cell was marked, false otherwise.
   */
  public boolean unmark(int x, int y) {
    if (board[x][y] == MARKED) {
      board[x][y] = UNKNOWN;
      numMarked--;
      return true;
    }
    else {
      return false;
    }
  }


  /**
   * Return the width of the game board.
   */
  public int getWidth() {
    return width;
  }

  /**
   * Return the height of the game board.
   */
  public int getHeight() {
    return height;
  }

  /**
   * Return the number of mines on the board.
   */
  public int getMines() {
    return numMines;
  }

  /**
   * Return the number of currently 'marked' cells on the game board.
   */
  public int getMarked() {
    return numMarked;
  }

  /**
   * Return the number of 'unknown' (as in not yet revealed) cells on the game 
   * board.
   */
  public int getUnknown() {
    return numUnknown;
  }


  /**
   * Work out how many neighbours of cell (x, y) contain mines.  Return the
   * number of explosive neighbours.
   */
  private int closeMines(int x, int y) {
    int minx, miny, maxx, maxy;
    int result = 0;

    // Don't check outside the edges of the board
    minx = (x <= 0 ? 0 : x - 1);
    miny = (y <= 0 ? 0 : y - 1);
    maxx = (x >= width - 1 ? width : x + 2);
    maxy = (y >= height - 1 ? height : y + 2);

    // Check all immediate neighbours for mines
    for (int i = minx; i < maxx; i++) {
      for (int j = miny; j < maxy; j++) {
	if (mines[i][j]) {
	  result++;
	}
      }
    }
    return result;
  }
}