// An Interpreter for BF*** Programs
//===================================

import io.Source
import scala.util._

// loding a bf-file 
def load_bff(name: String) : String = 
  Try(Source.fromFile(name)("ISO-8859-1").mkString).getOrElse("")

// BF memory as a map
type Mem = Map[Int, Int]

// reading and writing 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))
      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)
}

// Testcases
//===========

// a Mandelbrot set generator in brainf*** written by Erik Bosman
// (http://esoteric.sange.fi/brainfuck/utils/mandelbrot/)
val b0 = load_bff("mandelbrot.bf")

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


// a benchmark program (counts down from 'Z' to 'A')
val b1 = """>++[<+++++++++++++>-]<[[>+>+<<-]>[<+>-]++++++++
            [>++++++++<-]>.[-]<<>++++++++++[>++++++++++[>++
            ++++++++[>++++++++++[>++++++++++[>++++++++++[>+
            +++++++++[-]<-]<-]<-]<-]<-]<-]<-]++++++++++."""

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