// 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 "front" and the other the "back".
 */

class DESC extends DLDeque
{
/**
 * the coordinates of the initial Square occupied by front in an application
 */

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


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

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


/**
 * an array of the coordinates of back and front.
 * end[BACK] is the back and end[FRONT] is the front.
 */

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


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

static public final int BACK = 0;


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

static public final int FRONT  = 1;


/**
 * records which end is dominant, always FRONT or BACK
 */

private int dominant;


/**
 * records which end is not dominant, always FRONT or BACK
 */

private int nondominant;


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

static private int initialDominant = FRONT;


/**
 * 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 front the initial coordinates of the front
 * @param back the initial coordinates of the back
 */

DESC(Grid grid, Pair front, Pair back)
  {
  this.grid = grid;                             // Note the Grid
  dominant = initialDominant;                   // Set the dominant
  nondominant = opposite(dominant);             // and the nondominant.

  end[BACK] = back;                             // Record coordinates
  end[FRONT] = front;                           // of the DESC initially

  grid.setToEnd(back);                          // Show the DESC on the grid.
  grid.setToEnd(front);
  }


/**
 * 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 FRONT: enqueueFront(end[dominant]);  break;

    case BACK:  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 FRONT: end[nondominant] = (Pair)dequeueBack();  break;

    case BACK:  end[nondominant] = (Pair)dequeueFront(); break;
    }
  }


/**
 * Return whichever is opposite the end specified, front or back.
 */

int opposite(int which)
  {
  switch(which) 
    {
    case FRONT: return BACK;
    case BACK:  return FRONT;
    }
  return FRONT;
  }


/**
 * Switch the dominant from front to back, or vice-versa.
 */

void switchDominant()
  {
  switch( dominant )
    {
    case FRONT : dominant = BACK;  nondominant = FRONT; break;
    case BACK :  dominant = FRONT; nondominant = BACK;  break;
    }
  }


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

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

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

  return true;
  }

}