// file:    Grid.java
// author:  Robert Keller
// purpose: Provide a grid on which a DESC moves.

/**
 * Class Grid provides a grid for various games.
 * It also provides the mechanism for breadth-first search for spam.
 * We store the contents of values as ints so we can switch on them.
 */

class Grid
{
/**
 * value for the blank character
 */

static final int BLANK    = 0;


/**
 * value for the spam character
 */

static final int SPAM     = 1;


/**
 * value for a blockage character
 */

static final int BLOCKAGE = 2;


/**
 * value for the DESC head character
 */

static final int DESChead = 3;


/**
 * value for the DESC body character
 */

static final int DESCbody = 4;


/** 
 * the number of rows of the Grid
 */

protected int rows;


/** 
 * the number of columns of the Grid
 */

protected int cols;


/** 
 * the Squares of the Grid
 */

protected Square square[][];


/** 
 * Construct a grid of a given size.
 *
 * @param rows the number of rows
 * @param cols the number of columns
 */

Grid(int rows, int cols)
  {
  this.rows = rows;
  this.cols = cols;

  initialize();
  }


/** 
 * Construct a grid from a Sample, which includes the relevant size
 * information and spam settins.
 *
 * @param sample the Sample specifying Grid size and contents
 */

Grid(Sample sample)
  {
  this(sample.getRows(), sample.getCols());
  setList(sample.spamEnumeration(), SPAM);
  setList(sample.blockEnumeration(), BLOCKAGE);
  }


/** 
 * Set value on squares indexed by Pairs from an enumeration.
 *
 * @param pairs the enumeration of Pairs given
 */

public void setList(java.util.Enumeration pairs, int value)
  {
  while( pairs.hasMoreElements() )
    {
    set((Pair)pairs.nextElement(), value);
    }
  }


/** 
 * Indicate whether a particular Square has spam.
 *
 * @param row row to be checked
 * @param col column to be checked
 */

public boolean hasSpam(int row, int col)
  {
  return contains(row, col, SPAM);
  }


/** 
 * Make a Square of the grid blank.
 *
 * @param row row of the Square
 * @param col column of the Square
 */

public boolean setBlank(int row, int col)
  {
  return set(row, col, BLANK);
  }


/** 
 * Set a Square of show a DESC end.
 *
 * @param row row of the Square
 * @param col column of the Square
 */

public boolean setToEnd(Pair pair)
  {
  return set(pair.row, pair.col, DESChead);
  }


/** 
 * Set a Square of show a DESC body.
 *
 * @param row row of the Square
 * @param col column of the Square
 */

public boolean setToBody(Pair pair)
  {
  return set(pair.row, pair.col, DESCbody);
  }


/** 
 * Check whether a Square is within the Grid.
 *
 * @param row row of the Square
 * @param col column of the Square
 */

boolean inRange(int row, int col)
  {
  return 0 <= row && row < rows 
      && 0 <= col && col < cols;
  }


/** 
 * Check whether a Square has a DESC end or body cell.
 *
 * @param row row of the Square
 * @param col column of the Square
 */

public boolean hasDESC(int row, int col)
  {
  return hasDESCend(row, col) || hasDESCbody(row, col);
  }


/** 
 * Check whether a Square has a DESC end cell.
 *
 * @param row row of the Square
 * @param col column of the Square
 */

public boolean hasDESCend(int row, int col)
  {
  return contains(row, col, DESChead);
  }


/** 
 * Check whether a Square has a DESC body cell.
 *
 * @param row row of the Square
 * @param col column of the Square
 */

public boolean hasDESCbody(int row, int col)
  {
  return contains(row, col, DESCbody);
  }


/** 
 * Indicate whether a particular Square is blank.
 *
 * @param row row to be checked
 * @param col column to be checked
 */

public boolean isBlank(int row, int col)
  {
  return contains(row, col, BLANK);
  }


/** 
 * Get the contents of a Square
 *
 * @param row row of the Square
 * @param col column of the Square
 * @return contents of the Sqaure
 */

int get(int row, int col)
  {
  return square[row][col].get();
  }


/** 
 * Set the contents of a Square, after first checking that it is in range.
 *
 * @param row row of the Square
 * @param col column of the Square
 * @param c string representing the new contents
 * @return whether setting was done
 */

boolean set(int row, int col, int v)
  {
  if( inRange(row, col) )
    {
    square[row][col].set(v);
    return true;
    }
  return false;
  }


/** 
 * Set the contents of a Square, after first checking that it is in range.
 *
 * @param pair coordinate pair of the Square
 * @param c string representing the new contents
 * @return whether setting was done
 */

boolean set(Pair pair, int v)
  {
  return set(pair.row, pair.col, v);
  }


/** 
 * Set coordinates of the parent of a Square
 *
 * @param current coordinates pair of the Square
 * @param parent coordinates of the parent of the Square
 */

void setParent(Pair current, Pair parent)
  {
  getSquare(current).setParent(parent);
  }


/** 
 * Set coordinates of the parent of a Square
 *
 * @param row row of the square
 * @param col column of the square
 * @param parent coordinates of the parent of the Square
 */

void setParent(int row, int col, Pair parent)
  {
  square[row][col].setParent(parent);
  }


/** 
 * Set the contents of a Square to blank
 *
 * @param current coordinates pair of the Square
 * @param parent coordinates of the parent of the Square
 */

boolean clear(Pair pair)
  {
  return set(pair, BLANK);
  }


/**
 * Determine whether a Square contains specified contents.
 *
 * @param row the row of the square
 * @param col the column of the square
 * @param s the contents to be checked.
 * @return indication of whether the square contains the specified contents.
 */

boolean contains(int row, int col, int v)
  {
  return square[row][col].contains(v);
  }


/**
 * Determine whether a Square has been visited during a search
 *
 * @param row the row of the square
 * @param col the column of the square
 * @return indication of whether the square has been visited
 */

boolean isMarked(int row, int col)
  {
  return square[row][col].isMarked();
  }


/**
 * Determine whether a Square has a blockage
 *
 * @param row the row of the square
 * @param col the column of the square
 * @return indication of whether the square is blocked
 */

boolean isBlocked(int row, int col)
  {
  return square[row][col].contains(BLOCKAGE);
  }


/**
 * Construct the Squares of the Grid and initialize them.
 */

void initialize()
  {
  square = new Square[rows][cols];
  for( int row = 0; row < rows; row++ )
    {
    for( int col = 0; col < cols; col++ )
      {
      square[row][col] = new Square(BLANK);
      }
    }
  }


/**
 * Clear all parents in preparation for a search.
 */

void clearParents()
  {
  for( int row = 0; row < rows; row++ )
    {
    for( int col = 0; col < cols; col++ )
      {
      setParent(row, col, null);
      }
    }
  }


/**
 * Find spam using breadth-first search from a given pair of starting 
 * points.  A path of Pairs will be returned in a Deque for whichever
 * path is shorter.
 */

Deque findSpam(Pair start0, Pair start1)
  {
  clearParents();               // clear parents, for establishing path
  Queue queue = new SLQueue();

  queue.enqueue(start1);
  queue.enqueue(start0);
  setParent(start0, start0);    // Set starting parents to themselves.
  setParent(start1, start1);    // This makes the parents non-null, but in a
                                // way that is recognizable on path recovery.

  while( !queue.isEmpty() )     // As long as there are more Squares to search
    {
    Pair current = (Pair)queue.dequeue();       // Get Square coordinates.

    int row = current.row;                      
    int col = current.col;

    if( hasSpam(row, col) )                     // If the Square has spam
      {
      return getPath(current);                  // compute path and return.
      }

    maybeEnqueue(row-1, col, current, queue);   // Look at each neighbor.
    maybeEnqueue(row+1, col, current, queue); 
    maybeEnqueue(row, col-1, current, queue);
    maybeEnqueue(row, col+1, current, queue);
    }

  return null;  // no solution
  }


/**
 * Enqueue a Square at the specified row and column, setting its parent,
 * provided that the Square is on the grid, does not contain the DESC
 * and has not been enqueued before in this search.
 *
 * @param row the row of the Square
 * @param col the column of the Square
 * @param parent coordinates of the parent Square
 * @param queue Queue being used in the search
 */

void maybeEnqueue(int row, int col, Pair parent, Queue queue)
  {
  if( inRange(row, col) 
  && (isBlank(row, col) || hasSpam(row, col))
  && !isMarked(row, col) )
    {
    setParent(row, col, parent);        
    queue.enqueue(new Pair(row, col));
    }
  }

/**
 * Get a path from the spam backward to a DESC end cell.
 *
 * @param current coordinates of the Square from which to search.
 * @return Deque containing the path.
 */

Deque getPath(Pair current)
  {
  Deque path = new DLDeque();

  while( !current.equals(getParent(current)) )
    {
    path.enqueueFront(current);
    current = getParent(current);
    }
  return path;

  }


/**
 * Get the Square located at a particular Pair of coordinates.
 */

Square getSquare(Pair pair)
  {
  return square[pair.row][pair.col];
  }


/**
 * Get the parent of a Square located at a particular Pair of coordinates.
 */

Pair getParent(Pair pair)
  {
  return getSquare(pair).parent;
  }

}