// Copyright 2000 by Robert I. Pitts <rip@cs.bu.edu>
// All rights reserved.

function Maze(initialMazeStr)
{
  // public data

  // default maze chars--badpath char must be listed after path char
  // so that the replacement of defaults with new settings works
  // properly if path and badpath are the same character.
  this.chars = {
    open    : ".",
    blocked : "#",
    start   : "S",
    goal    : "G",
    path    : "+",
    badpath : "x"
  }

  // default search order
  this.dirorder = ["N", "E", "S", "W"]

  this.state = null

  // private data

  this.mat = new CharMatrix
  this.whitespaceChar = false

  this.reachedGoal = false
  this.startPos = null
  this.stack = null

  // public methods

  this.toString = function ()
  {
    return this.mat.toString()
  }

  this.set = function (str)
  {
    return this.mat.set(str, !this.whitespaceChar)
  }

  this.getCharsAsStr = function ()
  {
    var str = ""
    for (var i in this.chars)
      str += this.chars[i]
    return str
  }

  this.setChars = function (vals)
  {
    var error = ""
    var currChars = this.getCharsAsStr()  // save current
    var anyWhitespace = false

    for (var i in this.chars) {
      if (typeof vals[i] == "string") {
        if (vals[i].length != 1) {
          error += "- '" + i + "' symbol must be single character\n"
          continue
        }

        this.chars[i] = vals[i]

        if (vals[i].search(/\s/) != -1)
          anyWhitespace = true
      }
    }

    this.whitespaceChar = anyWhitespace
    this.mat.replaceChars(currChars, this.getCharsAsStr())

    return error
  }

  this.setDirorder = function (str)
  {
    if (typeof str == "string") {
      var tempOrder = str.toUpperCase().split("")

      if (tempOrder.concat().sort().join("") != "ENSW")
        return "- order must have exactly one of North, East, South, West\n"
      else
        this.dirorder = tempOrder
    }
    return ""
  }

  this.checkMaze = function ()
  {
    var error = ""

    if (this.mat.height == 0)
    {
      error += "- no maze\n"
    }
    else
    {
      if (!this.mat.validRows())
        error += "- maze rows not all same length\n"

      var validSet = this.chars.start + this.chars.goal +
                     this.chars.blocked + this.chars.open

      if (!this.mat.validChars(validSet))
        error += "- maze contains symbol(s) other than '" +
                 validSet.split("").join("', '") + "'\n"
    }

    return error
  }

  this.checkStart = function ()
  {
    if (this.mat.height != 0 &&
          this.mat.countChar(this.chars.start) != 1)
      return "- must have exactly one start position (marked with '" +
             this.chars.start + "')\n"
    return ""
  }

  this.checkGoal = function ()
  {
    if (this.mat.height != 0 &&
          this.mat.countChar(this.chars.goal) != 1)
      return "- must have exactly one goal position (marked with '" +
             this.chars.goal + "')\n"
    return ""
  }

  this.checkDirorder = function ()
  {
    if (this.dirorder.concat().sort().join("") != "ENSW")
      return "- order must have exactly one of North, East, South, West\n"
    return ""
  }

  this.resetSearch = function ()
  {
    this.state = null
    this.reachedGoal = false
    this.stack = null

    // erase any path
    this.mat.replaceChars(
      this.chars.path + this.chars.badpath,
      this.chars.open + this.chars.open
    )

    if (this.startPos != null) {
      this.mat.setCharAtXY(
        this.startPos.x, this.startPos.y, this.chars.start
      )
      this.startPos = null
    }
  }

  this.initSearch = function ()
  {
    var error = this.checkMaze() +
                this.checkStart() +
                this.checkGoal() +
                this.checkDirorder()

    if (error != "")
      return error

    this.startPos = this.mat.findFirstChar(this.chars.start)
    this.stack = newStack()
    this.stack.push(new State("B", "", "", null))
    this.stack.push(new State("R", this.startPos.x, this.startPos.y, null))
    return ""
  }

  this.nextStep = function nextStep()
  {
    if (!this.stack.length)
      return false

    this.state = this.stack.pop()
    var newstate = this.state.copy()

    switch (this.state.step) {
      case "R":  // In maze?
        if (!this.mat.hasLocationXY(this.state.x, this.state.y))
          break
        newstate.step = "G"
        this.stack.push(newstate)
        break

      case "G":  // Is goal?
        if (this.mat.getCharAtXY(this.state.x, this.state.y)
                == this.chars.goal) {
          this.reachedGoal = true
          break
        }
        newstate.step = "O"
        this.stack.push(newstate)
        break

      case "O":  // Is open?
        if (!this.mat.hasCharAtXY(
              this.state.x, this.state.y,
              this.chars.start +
              this.chars.open))
          break
        newstate.step = "M"
        this.stack.push(newstate)
        break

      case "M":  // Marking
        this.mat.setCharAtXY(
          this.state.x, this.state.y, this.chars.path
        )
        newstate.step = 0  // first direction
        this.stack.push(newstate)
        break

      case 0: // First direction,
      case 1: // 2nd direction...
      case 2:
      case 3:
        var backtrack = this.state.copy()
        backtrack.dir = this.state.step
        backtrack.step = "B"
        this.stack.push(backtrack)

        switch (this.dirorder[this.state.step]) {
          case "N": newstate.y--; break
          case "E": newstate.x++; break
          case "S": newstate.y++; break
          case "W": newstate.x--; break
        }
        newstate.step = "R"
        this.stack.push(newstate)
        break

      case "U":  // Unmarking
        this.mat.replaceCharAtXY(
          this.state.x, this.state.y,
          this.chars.path, this.chars.badpath
        )
        newstate.step = "F"
        this.stack.push(newstate)
        break

      case "F":  // No path from here
        break

      case "B":  // Backtracking
        if (!this.reachedGoal && this.state.dir != null) {
          // Go to next direction (or unmark step)
          newstate.step = ((this.state.dir + 1) < this.dirorder.length)
              ? (this.state.dir + 1) : "U"
          newstate.dir = null
          this.stack.push(newstate)
        }
        break
    }

    if (!this.stack.length)
      this.mat.setCharAtXY(
        this.startPos.x, this.startPos.y, this.chars.start
      )

    return true
  }

  this.noMoreSteps = function ()
  {
    return this.stack == null || !this.stack.length
  }

  this.startedSearch = function ()
  {
    return this.stack != null
  }

  this.currStep = function ()
  {
    if (this.state.step != "B")
      return this.state.step
    if (this.state.dir != null)
      return this.state.dir
    return null
  }

  if (arguments.length)
    this.set(initialMazeStr)
}

// Helper classes

function newStack()
{
  var stack = new Array

  // Unfortunately, IE doesn't seem to have push and pop methods
  // like Netscape, so simulate them if needed.

  if (typeof stack.push != "function") {
    stack.push = function (val) {
      this[this.length] = val
    }
    stack.pop = function () {
      var val = this[this.length-1]
       // must access element before decrement length
      this.length--
      return val
    }
  }

  return stack
}

function State(step, x, y, dir)
{
  this.step = step
  this.x = x
  this.y = y
  this.dir = dir
  this.copy = function () {
    return new State(this.step, this.x, this.y, this.dir)
  }
}