// file:    BreadthFirstApplet.java
// author:  Robert Keller
// purpose: Applet for demonstrating breadth-first search

/**  
 * BreadthFirstApplet.java
 * @version 1
 * @author  Robert M. Keller
 */

import java.applet.*;           // applet classes
import java.awt.*;              // Abstract Window Toolkit classes
import java.awt.event.*;

/**
 * Applet for demonstrating breadth-first search
 */ 

public class BreadthFirstApplet extends BaseApplet
{
/**
 * the index of the initial sample grid to be used
 */

static int initialSampleIndex = 4;


/**
 * suffix of a String for showing the number of steps
 */

static String stepsString = " steps ";


/**
 * prefix of a String for showing the path length
 */

static String pathString = "path length = ";


/**
 * String indicating no path
 */

static String noPathString = "There is no path.";


/**
 * font used for graphics
 */

Font mainBold = new Font("Helvetica", Font.BOLD, 18);


/**
 * possible delay values in the menu
 */

static int delayOption[] = {25, 50, 100, 200, 400, 800, 1600};


/**
 * x offset for the Grid
 */

int xGridOffset = 70;


/**
 * y offset for the Grid
 */

int yGridOffset = 70;   


/**
 * size of one square of the grid
 */

int gridSize = 20;


/**
 * x location of String indicating steps
 */

int xString = 50;

/**
 * y location of String indicating steps
 */

int yString = 50;


/**
 * default delay in ms
 */

int defaultDelay = 100; 


/**
 * choice menu for samples
 */

Choice sampleChoice;


/**
 * choice menu for delay values
 */

Choice delayChoice;


/**
 * array of samples
 */

Sample sample[];


/**
 * Grid extended for this applet
 */

AppletGrid grid;


/**
 * number of steps taken by game
 */

int stepsTaken;


/**
 * queue for breadth-first searching
 */

Queue searchQueue;


/**
 * specified start of the search
 */

Pair startSquare = new Pair(0, 1);


/**
 * a special parent value indicating "no parent"
 */

static Pair nilParent = new Pair(-1, -1);


/**
 * the current Square being searched
 */

Pair current;


/**
 * a deque for holding the path to spam
 */

Deque pathDeque;


/**
 * the computed length of the path to the spam
 */

int pathLength;


/**
 * the stage of the applet, indicating whether there is a search underway,
 * path-drawing, or idle (waiting for another sample)
 */

int stage;


/**
 * value indicating the idle stage
 */

static final int IDLE      = 0;


/**
 * value indicating the searching stage
 */

static final int SEARCHING = 1;


/**
 * value indicating the path-drawing stage
 */

static final int DRAWPATH  = 2;

/**
 *   Initialize the applet.
 */

public void init()
  {
  super.init();                         // Initialize BaseApplet.

  offScreen.setFont(mainBold);          // Set the font used in drawing.

  // Create Choice menu for selecting example.

  sampleChoice = new Choice();
  sampleChoice.setFont(mainBold);
  add(sampleChoice);
  sample = Sample.makeSamples();
  setSamples(sampleChoice, sample);
  sampleChoice.addItemListener(new SampleChoiceListener());

  // Set the initial sample.

  setInput(initialSampleIndex);

  // Create Choice menu for selecting delay.

  delayChoice = new Choice();
  delayChoice.setFont(mainBold);
  add(delayChoice);
  setDelays(delayChoice, delayOption);
  delayChoice.addItemListener(new DelayChoiceListener());

  setDelay(defaultDelay);
  }


/**
 * An inner class defining a listener for ItemEvents to the sample choice.
 */

class SampleChoiceListener implements ItemListener
  {
  /**
   * Act on a choice from a menu.
   */

  public void itemStateChanged(ItemEvent event)
    {
    // choose the input sample based on its index in the menu

    int index = sampleChoice.getSelectedIndex();

    // 0 is used as an instructional comment, not as a specific item chosen

    if( index > 0 )
      {
      setInput(index-1);
      stepsTaken = 0;
      }
    }
  }


/**
 * An inner class defining a listener for ItemEvents to the delay choice.
 */

class DelayChoiceListener implements ItemListener
  {
  public void itemStateChanged(ItemEvent event)
    {
    // choose a delay value based on its index in the menu

    int index = delayChoice.getSelectedIndex();

    // 0 is used as an instructional comment, not as a specific item chosen

    if( index > 0 )
      {
      setDelay(delayOption[index-1]);
      }
    }
  }


/**
 * Set the sample titles in a choice menu.
 */

void setSamples(Choice sampleChoice, Sample sample[])
  {
  sampleChoice.addItem("Choose Sample");

  int n = sample.length;

  for( int j = 1; j <= n; j++ )
    {
    sampleChoice.addItem(sample[j-1].getTitle());
    }
  }


/**
 * Set the delay values in a choice menu.
 */

void setDelays(Choice delayChoice, int delayOption[])
  {
  delayChoice.addItem("Choose Delay (ms)");

  for( int j = 1; j <= delayOption.length; j++ )
    {
    delayChoice.addItem("" + delayOption[j-1]);
    }
  }


/**
 * Set the input sample and create a new Grid.
 */

void setInput(int index)
  {
  grid = new AppletGrid(sample[index]);

  // Initialize the breadth-first search.

  searchQueue = new SLQueue();
  current = startSquare;

  if( maybeEnqueue(current.row, current.col, nilParent) )
    {
    stage = DRAWPATH;   // Spam found on the starting Square.
    }
  else
    {
    stage = SEARCHING;  // Go search for the spam.
    }
  }


/**
 * Take a single step.  
 * This over-rides the corresponding method in BaseApplet.
 */

public void step()
  {
  switch( stage )
    {
    case IDLE: break;   // There is nothing to do but wait.

    case SEARCHING:     // Continue a search under-way.
      {
      if(!searchQueue.isEmpty() )
        {
        current = (Pair)searchQueue.dequeue();  // Get the next closest Square.
        int row = current.row;
        int col = current.col;

        if( maybeEnqueue(row-1, col  , current) // Check each neighbor of
         || maybeEnqueue(row,   col+1, current) // the square for possible
         || maybeEnqueue(row+1, col  , current) // enqueuing. If any returns
         || maybeEnqueue(row,   col-1, current) // true, spam has been found.
          )
          {
          stage = DRAWPATH;                     // Spam found on enqueuing.

          pathDeque = new DLDeque();            // Construct the path
          pathLength = 0;                       // and compute its length.
          while( !current.equals(nilParent) )
            {
            pathDeque.enqueueFront(current);
            current = grid.getParent(current);
            pathLength++;
            }

          grid.clearParents();                  // Clear the grid in 
          break;                                // preparation for drawing
          }                                     // the path
        else
          {
          drawSearch();                         // Draw the search in progress.
          stepsTaken++;
          }
        }
      else
        {
        drawNotFound();                         // Queue is empty.
        stage = IDLE;                           // Indicate no path exists.
        }
      break;
      }

    case DRAWPATH:                              // Draw the path incrementally.
      {
      if(!pathDeque.isEmpty() )
        {
        grid.setParent((Pair)pathDeque.dequeueFront(), nilParent);
        drawPath();
        }
    else
      {
      stage = IDLE;                             // Path has been drawn.
      }            
    }
  }
}


/**
 * Maybe enqueue a cell at the designated coordinates
 */

boolean maybeEnqueue(int row, int col, Pair parent)
  {
  if(!grid.inRange(row, col)   ) return false;  // Check various things.
  if( grid.isBlocked(row, col) ) return false;
  if( grid.isMarked(row, col)  ) return false;

  grid.setParent(row, col, parent);             // Set the parent 

  if( grid.hasSpam(row, col)   )                // Check for spam
    {
    current = new Pair(row, col);
    return true;                                // Indicate spam found.
    }

  searchQueue.enqueue(new Pair(row, col));      // Enqueue this Square.
  return false;                                 // Indicate no spam found.
  }


/**
 * Draw the search in progress.
 */

void drawSearch()
  {
  clearOffScreenBuffer();
  drawGrid();
  drawSteps(stepsTaken);
  repaint();
  }


/**
 * Draw the path.
 */

void drawPath()
  {
  clearOffScreenBuffer();
  drawGrid();
  drawPathLength(pathLength);
  repaint();
  }


/**
 * Draw indication that there is no path.
 */

void drawNotFound()
  {
  clearOffScreenBuffer();
  drawGrid();
  drawNoPath();
  repaint();
  }


/**
 * Draw the grid and its contents.
 */

void drawGrid()
  {
  offScreen.setColor(foregroundColor);
  grid.draw(offScreen, xGridOffset, yGridOffset, gridSize);
  }


/**
 * Draw the String indicating number of steps.
 */

void drawSteps(int steps)
  {
  offScreen.setColor(Color.black);
  offScreen.drawString(stepsTaken + stepsString, xString, yString);
  }


/**
 * Draw the String indicating the path length
 */

void drawPathLength(int length)
  {
  offScreen.setColor(Color.black);
  offScreen.drawString(pathString + length, xString, yString);
  }


/**
 * Draw the String indicating no path.
 */

void drawNoPath()
  {
  offScreen.setColor(Color.black);
  offScreen.drawString(noPathString, xString, yString);
  }

} // BreadthFirstpplet