/**
Maze Traversal:
The maze is a perfect maze (ie only one way to get to any word).
*/

/**
 * CELL OBJECT
 * Represents a cell in the maze at maze start time.
 * A cell has a north, south, east, west direction. In each direction one of the
 * following circumstances may occur:
 * 1. A wall is in that direction. Represent as the string "wall"
 * 2. A single word may occur in that direction. Represent as a string for that word.
 * 3. Several words may be possible. Represent as an array of strings. These are immediately available words in the direction.
 * 4. May be nothing in that direction, for example, west of "start". Represent as boolean false.
 */
 function Cell(north,south,east,west) {
  this.north = north;
  this.south = south;
  this.east  = east;
  this.west  = west;
}

//add peek method to Array
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 curren cell to spoken word
 */
 function mazeError(message) {
   this.message = message;
 }

/**
 * MAZE OBJECT Constructor
 * private variables:
 * mazeLayout - a 2 dimensional array of cells that form a maze.
 * adjList    - adjacency list for depth first searching for a path.
 *              Also includes other information. Format:
 *              adjList[a maze word] = [word_is_available, word_gotten, marked_by_dfs_search, list_of_adjacent_words, position_of_word]
 * startPosition - the starting cell for the maze. Always at cell "1,1"
 */
function Maze() {
  var mazeLayout    = new Object();
  var adjList       = new Object();

  adjList["start"]     = [false, true,  false, ["leaf"],                                           "1,1"];
  adjList["leaf"]      = [true,  false, false, ["start", "log"],                                   "0,2"];
  adjList["log"]       = [false, false, false, ["leaf", "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", "end"],     "6,2"];
  adjList["lollipop"]  = [false, false, false, ["lion", "ladder", "lemon", "end"],                 "4,1"];
  adjList["ladder"]    = [false, false, false, ["lion", "lollipop", "lemon", "end"],               "10,6"];
  adjList["end"]       = [false, false, false, [],                                                 "9,7"];
  adjList["lemon"]     = [false, false, false, ["lion", "ladder", "lollipop", "end"],              "8,6"];

  this.currentPosition = "1,1";

  this.addCell = function(cellPositionString, north, south, east, west) {
                   mazeLayout[cellPositionString] = new Cell(north, south, east, west);
                 }

  this.getCell = function(cellPositionString) {
                   return mazeLayout[cellPositionString];
                 } //usage: mazeObj.getCell("1,2");

  this.getWordPosition = function(word) {
                           return adjList[word][4];
                         }

  this.isAvailable = function(word) {
                       return adjList[word][0];
                     }

  this.availableWords = function() {
                          var availWords = new Array();
                          for (var aWord in adjList)
                            if (adjList[aWord][0])
                              availWords.push(aWord);
                          return availWords;
                        }

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

  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
 * @param spokenWord is the word spoken by the user and captured by voiceXML
 * @returns void.
 * 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);
    }
    return this.currentPosition;
}

/**
 * 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 pass
  var immedAdjacent = this.getDirectionFromCell(spokenWord, currentCell);
  if (typeof immedAdjacent == "string")
    return immedAdjacent;

  //not found in first pass so do a 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;
                                 }