/*
 * file:    maze.js
 * author:  Michael Laskowski
 * date:    1/31/2008
 * purpose: provides methods for maze traversal. These methods are limited to
 *          primarily the logic for determining which direction to move in the
 *          maze in response to a word spoken. State variables such as the current
 *          user position in the maze and the number of times a word has been spoken
 *          are maintained. The gui for the maze is defined in mazeVisualGenerator.js.
 *          The physical definition of the maze is contained in mazeCreation.js.
 *
 * summary: Two objects are defined: Object Cell and Object Maze (see header comments for more detail, below).
 *          The maze is a perfect maze (ie. only one way to get to any word).
 *          The maze is represented as a graph, with a path being determined via a depth first search strategy.
 */

/*
 * Constructor function: Object Cell
 * purpose: Represents a cell in the maze.
 *          A cell has a north, south, east, west direction.
 *          At each position in the maze, one of the following circumstances will occur:
 *            1. A wall is in a particaluar direction. Represent as the string "wall"
 *            2. A single word may occur in a direction. Represent as a string for that word.
 *            3. Several words may be possible. Represent as an array of strings.
 *            4. May be nothing in that direction, for example, west of the initial position
 *               of the user icon. Represent as boolean false.
 *           ** see mazeCreation.js for usage and clarification **
 */
 function Cell(north,south,east,west) {
  this.north = north;
  this.south = south;
  this.east  = east;
  this.west  = west;
}

/*
 * add peek method to Array Object
 */
Array.prototype.peek = function () {
                         var top = this.pop();
                         this.push(top);
                         return top;
                       }

/*
 * error thrown by maze application
 * thrown when a path cannot be found from current cell to spoken word
 */
 function mazeError(message) {
   this.message = message;
 }

/*
 * Constructor Function: Object Maze
 * private variables:
 *   mazeLayout - a 2-dimensional array of cells that form a maze.
 *   adjList    - adjacency list (modified with additional information) to represent maze (images are vertices).
 *                Format of adjacency list:
 *       adjList[a maze word] = [word_is_available, word_gotten, marked_by_dfs_search, list_of_adjacent_words, position_of_word]
 *
 * Public methods/fields defined in header comments below.
 */
function Maze() {
  var mazeLayout    = new Object();
  var adjList       = new Object();

  adjList["start"]     = [false, true,  false, ["carrot"],                                           "1,1"];
  adjList["carrot"]      = [true,  false, false, ["start", "log"],                                   "0,2"];
  adjList["log"]       = [false, false, false, ["carrot", "lettuce", "locust"],                      "0,7"];
  adjList["lettuce"]   = [false, false, false, ["lamp", "locust","log"],                           "1,3"];
  adjList["locust"]    = [false, false, false, ["lettuce", "log", "ladybug"],                      "4,9"];
  adjList["lamp"]      = [false, false, false, ["lettuce"],                                        "8,1"];
  adjList["ladybug"]   = [false, false, false, ["locust", "lips", "leopard", "lighthouse"],          "7,5"];
  adjList["leopard"]   = [false, false, false, ["ladybug", "lighthouse", "lips"],                    "4,4"];
  adjList["lighthouse"]  = [false, false, false, ["leopard", "ladybug", "leg", "lawnmower", "lips"], "5,7"];
  adjList["leg"]       = [false, false, false, ["lighthouse", "lawnmower"],                          "2,6"];
  adjList["lawnmower"] = [false, false, false, ["leg", "lighthouse"],                                "6,8"];
  adjList["lips"]      = [false, false, false, ["ladybug", "leopard", "lighthouse", "lion"],         "4,6"];
  adjList["lion"]      = [false, false, false, ["lips", "lollipop", "lemon", "ladder", "cake"],     "6,2"];
  adjList["lollipop"]  = [false, false, false, ["lion", "ladder", "lemon", "cake"],                 "4,1"];
  adjList["ladder"]    = [false, false, false, ["lion", "lollipop", "lemon", "cake"],               "10,6"];
  adjList["cake"]       = [false, false, false, [],                                                 "9,7"];
  adjList["lemon"]     = [false, false, false, ["lion", "ladder", "lollipop", "cake"],              "8,6"];

  //use timesWordSaid to manage how many time user required to say a word
  this.timesWordSaid = new Object();
  this.timesWordSaid["carrot"]     = 0;
  this.timesWordSaid["log"]        = 0
  this.timesWordSaid["lettuce"]    = 0;
  this.timesWordSaid["locust"]     = 0;
  this.timesWordSaid["lamp"]       = 0;
  this.timesWordSaid["ladybug"]    = 0;
  this.timesWordSaid["leopard"]    = 0
  this.timesWordSaid["lighthouse"] = 0;
  this.timesWordSaid["leg"]        = 0;
  this.timesWordSaid["lawnmower"]  = 0;
  this.timesWordSaid["lips"]       = 0;
  this.timesWordSaid["lion"]        = 0
  this.timesWordSaid["lollipop"]   = 0;
  this.timesWordSaid["ladder"]     = 0;
  this.timesWordSaid["cake"]       = 0;
  this.timesWordSaid["lemon"]      = 0;

  //start position is 1,1. Maintains current user position in maze.
  this.currentPosition = "1,1";

  //used to create maze. See mazeCreation.js for usage.
  this.addCell = function(cellPositionString, north, south, east, west) {
                   mazeLayout[cellPositionString] = new Cell(north, south, east, west);
                 }

  //return reference to a Cell object based on cell position
  //usage: mazeObj.getCell("1,2");
  this.getCell = function(cellPositionString) {
                   return mazeLayout[cellPositionString];
                 }

  //return cell position string for a word
  this.getWordPosition = function(word) {
                           return adjList[word][4];
                         }

  //return true/false based on if a word is available for speaking
  this.isAvailable = function(word) {
                       return adjList[word][0];
                     }

  //returns the set of words available for speaking
  this.availableWords = function() {
                          var availWords = new Array();
                          for (var aWord in adjList)
                            if (adjList[aWord][0])
                              availWords.push(aWord);
                          return availWords;
                        }

  /*
   * adjusts adjacency list such that a word is not available for speaking.
   * note: once a word is made not available, other words may become available.
   * this method takes care of this also.
   */
  this.makeNotAvailable = function(word) {
                            adjList[word][0] = false; //word is not available
                            adjList[word][1] = true; //word is gotten

                            //make adjacent words available
                            var adjWords = adjList[word][3];
                            for (var i=0; i<adjWords.length; i++)
                              if ( !adjList[adjWords[i]][0] && !adjList[adjWords[i]][1] )
                                adjList[adjWords[i]][0] = true;
                          }

  /*
   * stack based depth first search.
   * finds a path to a word, returns direction to move from current cell.
   * note: this method needs to take into account that a path between two words
   * may be available even if a word(s) is between these two words - that is a intermediary
   * word is 'gotten' by user and so doesn't represent a barrier to movement.
   */
  this.thePath = function(spokenWord, cell) {
                   //initialize "vertices" for depth first search (ie marked/not marked)
                   //false mean not visited, spoken word is immed init'd to true to avoid cycle
                   for (var vertex in adjList)
                     adjList[vertex][2] = false;

                   adjList[spokenWord][2] = true;

                   var found  = false;
                   var vertex = spokenWord;
                   var stack  = new Array(vertex);
                   var adjDirection;

                  do {
                       vertex = stack.pop();
                       adjDirection = this.getDirectionFromCell(vertex, cell);
                       if ( typeof adjDirection == "string" )
                         found = true;
                       else {
                         var adjWords = adjList[vertex][3];
                         for (var i=0; i<adjWords.length; i++) {
                           var adj_word = adjWords[i];
                           if (!adjList[adj_word][0] && !adjList[adj_word][2] && adjList[adj_word][1] ) {
                             adjList[adj_word][2] = true;
                             stack.push(adj_word);
                           }
                         }
                       }
                     } while ( (stack.length != 0) && !found );

                     return adjDirection;
                   }
                 }

/*
 * Top level function for maze, called by VoiceXML document
 * spokenWord is the word spoken by the user and captured by voiceXML
 * This function updates this.currenPosition in response to a spoken word
 */
Maze.prototype.move = function(spokenWord)
{
  try {
    var directionToMove = this.getDirectionToMove(spokenWord);
    } catch (errMessage) {
      alert(errMessage.message + " current position is: " + this.currentPosition);
    }

    var cellPositions = this.currentPosition.split(",");
    var currentRow    = parseInt(cellPositions[0]);
    var currentCol    = parseInt(cellPositions[1]);

    switch(directionToMove) {
      case "north": this.currentPosition = (currentRow-1) + "," + currentCol;
                    break;
      case "south": this.currentPosition = (currentRow+1) + "," + currentCol;
                    break;
      case "east" : this.currentPosition  = currentRow    + "," + (currentCol + 1);
                    break;
      case "west" : this.currentPosition = currentRow     + "," + (currentCol - 1);
    }
}

/**
 * finds if a spoken word is immediately reachable (immediately adjacent) from current position in the maze
 * if the word is immediately adjacent to current cell, returns the direction (as a string) otherwise
 * returns boolean false.
 */

Maze.prototype.getDirectionFromCell = function (spokenWord, cell)
{
    for ( var direction in cell ) {
      switch (typeof cell[direction]) {
        case "string" :  if (spokenWord == cell[direction])
                           return direction;
                         continue;

        default : for (var i=0; i<cell[direction].length; i++)
                    if (spokenWord == cell[direction][i])
                      return direction;
                    continue;
      }
    }
    return false;
}

/**
 * given a spoken word, finds the direction to move, (N,S,E,or W) from current position in the maze
 * 2 levels of searching:
 *  first - checks if the word spoken is immediately reachable from the current position.
 *          if so, then returns that result.
 *  second - if direction wasn't found from first pass, then the spoken word may be available, but its
 *           way may be blocked by another word that is not available BUT has been gotten. Therefore a
 *           depth first style graph search traversal is performed to find if there is a path from the
 *           current position to the spoken word.
 */
Maze.prototype.getDirectionToMove = function (spokenWord)
{
  var currentCell = this.getCell(this.currentPosition);

  //first level search
  var immedAdjacent = this.getDirectionFromCell(spokenWord, currentCell);
  if (typeof immedAdjacent == "string")
    return immedAdjacent;

  //second level search
  var dir = this.thePath(spokenWord, currentCell);
  if ( typeof dir == "string" )
    return dir;

  throw new mazeError("no where to go");
}

/**
 * FOR TESTING ONLY
 */
 Maze.prototype.changePosition = function (newPositionString) {
                                   this.currentPosition = newPositionString;
                                 }