// A simple Interpreter for BF*** Programs

//=========================================

//

// Call with

//

//  mill bfi.scala --fname <<bf_program.bf>>

//

// BF memory is represented as a Map

type Mem = Map[Int, Int]

// safe reading and writing of BF memory

def sread(mem: Mem, mp: Int) : Int = 

  mem.getOrElse(mp, 0)

def write(mem: Mem, mp: Int, v: Int) : Mem =

  mem.updated(mp, v)

// Right and Left Jumps in BF loops

def jumpRight(prog: String, pc: Int, level: Int) : Int = {

  if (prog.length <= pc) pc 

  else (prog(pc), level) match {

    case (']', 0) => pc + 1

    case (']', l) => jumpRight(prog, pc + 1, l - 1)

    case ('[', l) => jumpRight(prog, pc + 1, l + 1)

    case (_, l) => jumpRight(prog, pc + 1, l)

  }

}

def jumpLeft(prog: String, pc: Int, level: Int) : Int = {

  if (pc < 0) pc 

  else (prog(pc), level) match {

    case ('[', 0) => pc + 1

    case ('[', l) => jumpLeft(prog, pc - 1, l - 1)

    case (']', l) => jumpLeft(prog, pc - 1, l + 1)

    case (_, l) => jumpLeft(prog, pc - 1, l)

  }

}

// main interpreter loop

def compute(prog: String, pc: Int, mp: Int, mem: Mem) : Mem = {

  if (0 <= pc && pc < prog.length) { 

    val (new_pc, new_mp, new_mem) = prog(pc) match {

      case '>' => (pc + 1, mp + 1, mem)

      case '<' => (pc + 1, mp - 1, mem)

      case '+' => (pc + 1, mp, write(mem, mp, sread(mem, mp) + 1))

      case '-' => (pc + 1, mp, write(mem, mp, sread(mem, mp) - 1))

      case '.' => { print(sread(mem, mp).toChar); (pc + 1, mp, mem) }

      case ',' => (pc + 1, mp, write(mem, mp, Console.in.read().toByte))   //scala.io.StdIn.readLine()

      case '['  => if (sread(mem, mp) == 0) 

                      (jumpRight(prog, pc + 1, 0), mp, mem) 

                   else (pc + 1, mp, mem) 

      case ']'  => if (sread(mem, mp) != 0) 

                      (jumpLeft(prog, pc - 1, 0), mp, mem) 

                   else (pc + 1, mp, mem) 

      case _ => (pc + 1, mp, mem)

    }		     

    compute(prog, new_pc, new_mp, new_mem)	

  }

  else mem

}

def run(prog: String, m: Mem = Map()) = compute(prog, 0, 0, m)

// helper code for timing information

def time_needed[T](n: Int, code: => T) = {

  val start = System.nanoTime()

  for (i <- 0 until n) code

  val end = System.nanoTime()

  (end - start)/(n * 1.0e9)

}

// Running Testcases

//===================

//@doc(" the argument should be a BF program ")

@main

def main(fname: String) = {

  val bf_str = os.read(os.pwd / fname)

  println(s"${time_needed(1, run(bf_str))} secs")

}