// file:    DESC.java
// author:  Robert Keller
// purpose: Implement a Double-Ended Spam Cruncher.

/**
 * Class DESC represents a Double-Ended Spam Cruncher.
 * A DESC maintins it state as a sequence of Squares on a Grid.
 * Although it has two ends, one of them is considered dominant at any
 * point, and when instructed to move to a particular Square, the dominant
 * end is the one that moves there.  The square should be one adjacent
 * the dominant ends's current square.  We differentiate between the two
 * ends by calling one of the the "head" and the other the "tail".
 */

class DESC
{
/**
 * used for controlling the kind of output to System.out
 * If set to 0, there is no output to System.out.
 * If set to 1, the coordinates of the dominant head are printed.
 * If set to 2, the complete grid and other information is shown.
 *
 * The default is 0.
 * If main is run, the value is set to 1, unless -t is included 
 * after the class name on the command line, in which case the value is 2.
 */

static int traceLevel = 0;


/**
 * the coordinates of the initial Square occupied by head in an application
 */

static public final Pair start1 = new Pair(0, 1);


/**
 * the coordinates of the initial Square occupied by tail in an application
 */

static public final Pair start0 = new Pair(0, 0);


/**
 * an array of the coordinates of tail and head.
 * end[TAIL] is the tail and end[HEAD] is the head.
 */

private Pair end[] = new Pair[2];


/**
 * the index of the "tail" of the DESC in the 'end' array
 */

static public final int TAIL = 0;


/**
 * the index of the "head" of the DESC in the 'end' array
 */

static public final int HEAD  = 1;


/**
 * records which end is dominant, always HEAD or TAIL
 */

private int dominant;


/**
 * records which end is not dominant, always HEAD or TAIL
 */

private int nondominant;


/**
 * specifies which end is initially dominant
 */

static private int initialDominant = HEAD;


/**
 * a Deque, used to contain all but the head and tail cell coordinates
 */

Deque deque;


/**
 * the Grid on which the DESC moves
 */

Grid grid;


/**
 * Construct a DESC given a Grid on which it is to move.
 *
 * @param grid the Grid on which this DESC moves
 * @param head the initial coordinates of the head
 * @param tail the initial coordinates of the tail
 */

DESC(Grid grid, Pair head, Pair tail)
  {
  this.grid = grid;                             // Note the Grid
  deque    = new MyDeque();                     // Create Deque for body
  dominant = initialDominant;                   // Set the dominant
  nondominant = opposite(dominant);             // and the nondominant.

  end[TAIL] = tail;                             // Record coordinates
  end[HEAD] = head;                             // of the DESC initially

  grid.setToEnd(tail);                          // Show the DESC on the grid.
  grid.setToEnd(head);
  }


/**
 * Move the DESC by moving the dominant end to the specified row and column,
 * if possible.  If the specified Square has spam, then extend the DESC
 * by one cell at the dominant end. 
 *
 * @param row the new row of the dominant end
 * @param col the new columng of the dominant end
 * @return true if move was possible, false otherwise.
 */

boolean moveTo(int row, int col)
  {
  if( canMoveTo(row, col) )                     // See if move is possible.
    {
    boolean hasSpam = grid.hasSpam(row, col);   // Note whether spam present.

    addCell(new Pair(row, col));                // Move the dominant end.

    if( !hasSpam )
      {
      removeCell();                             // Remove the nondominant end.
      }
    return true;
    }
  return false;
  }


/**
 * Add the Cell indicated by coordinates in Pair to the DESC
 * at the dominant end.
 *
 * @param pair the coordinates of the Cell to be added
 */

void addCell(Pair pair)
  {
  grid.setToEnd(pair);                       // Make the new cell an end.
  grid.setToBody(end[dominant]);             // Make the old cell a body cell.
  enqueueDominant();                         // Enqueue the dominant end.
  end[dominant] = pair;                      // Set the new dominant end.
  }


/**
 * Remove a cell from the body of the DESC, depending on which end is dominant.
 */

void removeCell()
  {
  grid.clear(end[nondominant]);      // Remove cell from the non-dominant end.
  dequeueNonDominant();              // Dequeue the dominant end.
  grid.setToEnd(end[nondominant]);   // Show the new non-dominant cell.
  }


/**
 * Enqueue the dominant cell on the appropriate end of the Deque.
 */

void enqueueDominant()
  {
  switch( dominant )
    {
    case HEAD: deque.enqueueFront(end[dominant]);  break;

    case TAIL: deque.enqueueBack(end[dominant]);   break;
    }
  }


/**
 * Dequeue the nondominant cell from the appropriate end of the Deque.
 */

void dequeueNonDominant()
  {
  switch( dominant )                 // Get the new non-dominant end.
    {
    case HEAD: end[nondominant] = (Pair)deque.dequeueBack();  break;

    case TAIL: end[nondominant] = (Pair)deque.dequeueFront(); break;
    }
  }


/**
 * Return whichever is opposite the end specified, head or tail.
 */

int opposite(int which)
  {
  switch(which) 
    {
    case HEAD: return TAIL;
    case TAIL: return HEAD;
    }
  return HEAD;
  }


/**
 * Switch the dominant from head to tail, or vice-versa.
 */

void switchDominant()
  {
  switch( dominant )
    {
    case HEAD : dominant = TAIL; nondominant = HEAD; break;
    case TAIL : dominant = HEAD; nondominant = TAIL; break;
    }
  traceln(2, "// reversing");
  }


/**
 * Determine whether the DESC can move to the specified Square, i.e.
 * that the Square is within range and doesn't already contain a DESC cell.
 *
 * @param row the new row of the dominant end
 * @param col the new columng of the dominant end
 * @return true if move is possible, false otherwise.
 */

boolean canMoveTo(int row, int col)
  {
  return grid.inRange(row, col) 
     && !grid.hasDESC(row, col);
  }


/**
 * Move the DESC one step toward spam, if possible.
 *
 * @return true if move toward spam is possible, false otherwise
 */

boolean moveTowardSpam()
  {
  Deque path = grid.findSpam(end[dominant], end[nondominant]); // search

  if( path == null )
    {
    return false;                                              // no path found
    }

  Pair next = (Pair)path.dequeueFront();   // Get next Square.

  if( !next.adjacent(end[dominant]) )
    {
    switchDominant();                      // Switch dominant if necessary.
    }

  trace(1, next.toString());

  if( !path.isEmpty() )                    // Show target or crunch if desired.
    {
    Pair spam = (Pair)path.dequeueBack();

    trace(2, " // target is " + spam.row + " " + spam.col);
    }
  else
    {
    trace(2, " // crunch!");
    }

  traceln(1, "");

  moveTo(next.row, next.col);              // Make the actual move.


  traceln(2, grid.toString());             // Show the grid, if desired.
  return true;
  }


/**
 * a main program for testing the DESC.  It reads in the dimensions of a
 * Grid from System.in, and the coordinates of spam cells.  Then a 
 * DESC is created in the upper-left corner of the Grid and set to
 * seeking spam using breadth-first search, until it can no longer find any.
 */

public static void main(String arg[])
  {
  traceLevel = 1;
  if( arg.length > 0 && arg[0].equals("-t") )
      {
      traceLevel = 2;
      }

  Grid grid = Grid.gridFromInputStream(System.in);
  if( grid == null )
    {
    System.out.println("*** Could not read input.");
    }
  else
    {
    DESC desc = new DESC(grid, start0, start1);

    traceln(2, start1.toString());
    traceln(2, grid.toString());

    while( desc.moveTowardSpam() )
      {
      }
    }
  }


/**
 * Print a trace message if the first argument is below the currently-set
 * trace level.  No new line is printed after the message.
 *
 * @param level the trace level at which a message should be printed.
 * @param message the message to be printed
 */

static void trace(int level, String message)
  {
  if( traceLevel >= level )
    {
    System.out.print(message);
    }
  }

/**
 * Print a trace message if the first argument is below the currently-set
 * trace level.  A new line is printed after the message.
 *
 * @param level the trace level at which a message should be printed.
 * @param message the message to be printed
 */

static void traceln(int level, String message)
  {
  if( traceLevel >= level )
    {
    System.out.println(message);
    }
  }

}