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

/**
 * Class DESC provides a grid for a Double-Ended Spam Cruncher.
 * It also provides the mechanism for breadth-first search for spam.
 */

import java.io.*;
import java.awt.*;

class Grid
{
/**
 * character used to show spam on the grid when tracing
 */

public static String spamChar     = "x";


/**
 * character used to show a DESC end cell on the grid when tracing
 */

public static String DESCendChar = "o";


/**
 * character used to show a DESC body cell on the grid when tracing
 */

public static String DESCbodyChar = "o";


/**
 * character used to show an empty Grid square
 */

public static String blankChar    = " ";


/**
 * an integer returned when there is no more input in populating the Grid
 * with spam
 */

private static int inputStop = -1;


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

private int rows;


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

private int cols;


/** 
 * the Squares of the Grid
 */

private 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());
  setSpam(sample.elements());
  }


/** 
 * Set spam on a single Square of the grid, as specified by Pair.
 *
 * @param pair the coordinates where spam is to be placed
 */

public boolean setSpam(Pair pair)
  {
  return setSpam(pair.row, pair.col);
  }


/** 
 * Set spam on a single Square of the grid, as specified by row and column.
 *
 * @param row row at which the spam is to be placed
 * @param col column at which the spam is to be placed
 */

public boolean setSpam(int row, int col)
  {
  return set(row, col, spamChar);
  }


/** 
 * Set spam on Pairs in an enumeration of Pairs.
 *
 * @param pairs the enumeration of Pairs given
 */

public void setSpam(java.util.Enumeration pairs)
  {
  while( pairs.hasMoreElements() )
    {
    setSpam((Pair)pairs.nextElement());
    }
  }


/** 
 * 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, spamChar);
  }


/** 
 * 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, blankChar);
  }


/** 
 * 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, DESCendChar);
  }


/** 
 * 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, DESCbodyChar);
  }


/** 
 * 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, DESCendChar);
  }


/** 
 * 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, DESCbodyChar);
  }


/** 
 * 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, blankChar);
  }


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

String 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, String c)
  {
  if( inRange(row, col) )
    {
    square[row][col].set(c);
    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, String c)
  {
  return set(pair.row, pair.col, c);
  }


/** 
 * 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, blankChar);
  }


/**
 * 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, String s)
  {
  return square[row][col].contains(s);
  }


/**
 * 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();
  }


/**
 * 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(blankChar);
      }
    }
  }


/**
 * 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 MyQueue();

  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
 * @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 MyDeque();

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

  }


/**
 * Return a grid created from the specifications in an input stream.
 * The specifications begin with the number of rows and columns, 
 * followed by the coordinates of any spam to be placed.
 *
 * @param stream the InputStream containing the specification
 */

static Grid gridFromInputStream(InputStream stream)
  {
  LineBufferInputStream in = new LineBufferInputStream(stream);
  
  int rows = getInt(in);
  int cols = getInt(in);

  if( rows < 1 || cols < 1 )
    {
    System.out.println("*** Rows and columns must be > 0.");
    return null;
    }

  Grid grid = new Grid(rows, cols);

  int row, col;
  while( (row = getInt(in)) > inputStop && (col = getInt(in)) > inputStop )
    {
    grid.setSpam(row, col);
    }

  return grid;
  }


/**
 * Get the next int from a LineBufferInputStream, returning -1 if
 * there is no more input.
 *
 * @param in the LineBufferInputStream from which to get the int.
 */

static int getInt(LineBufferInputStream in)
  {
  if( in.eof() ) return inputStop;

  String str = in.getString();

  return Integer.parseInt(str);
  }


/**
 * Return a String representation of this Grid.
 */

public String toString()
  {
  StringBuffer buffer = new StringBuffer();

  for( int col = 0; col < cols; col++ )
    {
    buffer.append("/");
    }
  buffer.append("////\n");

  for( int row = 0; row < rows; row++ )
    {
    buffer.append("//");
    for( int col = 0; col < cols; col++ )
      {
      buffer.append(square[row][col]);      
      }
    buffer.append("//\n");
    }

  for( int col = 0; col < cols; col++ )
    {
    buffer.append("/");
    }
  buffer.append("////\n");

  return buffer.toString();
  }

/**
 * 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;
  }

}