// Part 2 about a "Compiler" for the Brainf*** language

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

// !!! Copy any function you need from file bf.scala !!!

//

// If you need any auxiliary function, feel free to 

// implement it, but do not make any changes to the

// templates below.

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)

}

type Mem = Map[Int, Int]

import io.Source

import scala.util._

def load_bff(name: String) : String = 

  Try(Source.fromFile(name)("ISO-8859-1").mkString).getOrElse("")

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

  mem.getOrElse(mp, 0)

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

  mem.updated(mp, v)

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)

  }

}

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)

// The baseline to what we can compare our "compiler"

// implemented below. It should require something like 

// 60 seconds for the calculation on my laptop

//

//time_needed(1, run(load_bff("benchmark.bf")))

// DEBUGGING INFORMATION!!!

//

// Compiler, even real ones, are fiedishly difficult to get

// to prduce correct code. The point is that for example for

// the sierpinski program, they need to still generate code

// that displays such a triangle. If yes, then one usually

// can take comfort that all is well. If not, then something

// went wrong during the optimisations.

// (5) Write a function jtable that precomputes the "jump

//     table" for a bf-program. This function takes a bf-program 

//     as an argument and Returns a Map[Int, Int]. The 

//     purpose of this map is to record the information

//     that given on the position pc is a '[' or a ']',

//     then to which pc-position do we need to jump next?

// 

//     For example for the program

//    

//       "+++++[->++++++++++<]>--<+++[->>++++++++++<<]>>++<<----------[+>.>.<+<]"

//

//     we obtain the map

//

//       Map(69 -> 61, 5 -> 20, 60 -> 70, 27 -> 44, 43 -> 28, 19 -> 6)

//  

//     This states that for the '[' on position 5, we need to

//     jump to position 20, which is just after the corresponding ']'.

//     Similarly, for the ']' on position 19, we need to jump to

//     position 6, which is just after the '[' on position 5, and so

//     on. The idea is to not calculate this information each time

//     we hit a bracket, but just look up this information in the 

//     jtable. You can use the jumpLeft and jumpRight functions

//     from Part 1 for calculating the jtable.

//

//     Then adapt the compute and run functions from Part 1 in order 

//     to take advantage of the information stored in the jtable. 

//     This means whenever jumpLeft and jumpRight was called previously,

//     you should look up the jump address in the jtable.

def jtable(pg: String) : Map[Int, Int] = 

    (0 until pg.length).collect { pc => pg(pc) match {

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

      case ']' => (pc -> jumpLeft(pg, pc - 1, 0))

    }}.toMap

// testcase

// jtable("""+++++[->++++++++++<]>--<+++[->>++++++++++<<]>>++<<----------[+>.>.<+<]""")

// =>  Map(69 -> 61, 5 -> 20, 60 -> 70, 27 -> 44, 43 -> 28, 19 -> 6)

def compute2(pg: String, tb: Map[Int, Int], pc: Int, mp: Int, mem: Mem) : Mem = {

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

    val (new_pc, new_mp, new_mem) = pg(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) (tb(pc), mp, mem) else (pc + 1, mp, mem) 

      case ']'  => 

	if (sread(mem, mp) != 0) (tb(pc), mp, mem) else (pc + 1, mp, mem) 

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

    }		     

    compute2(pg, tb, new_pc, new_mp, new_mem)	

  }

  else mem

}

def run2(pg: String, m: Mem = Map()) = 

  compute2(pg, jtable(pg), 0, 0, m)

//time_needed(1, run2(load_bff("benchmark.bf")))

// (6) Write a function optimise which deletes "dead code" (everything

// that is not a bf-command) and also replaces substrings of the form

// [-] by a new command 0. The idea is that the loop [-] just resets the

// memory at the current location to 0. In the compute3 and run3 functions

// below you implement this command by writing the number 0 to mem(mp), 

// that is write(mem, mp, 0). 

//

// The easiest way to modify a string in this way is to use the regular

// expression """[^<>+-.,\[\]]""", which recognises everything that is 

// not a bf-command and replace it by the empty string. Similarly the

// regular expression """\[-\]""" finds all occurences of [-] and 

// by using the Scala method .replaceAll you can repplace it with the 

// string "0" standing for the new bf-command.

def optimise(s: String) : String = 

  s.replaceAll("""[^<>+-.,\[\]]""","").replaceAll("""\[-\]""", "0")

def compute3(pg: String, tb: Map[Int, Int], pc: Int, mp: Int, mem: Mem) : Mem = {

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

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

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

      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) (tb(pc), mp, mem) else (pc + 1, mp, mem) 

      case ']'  => 

	if (sread(mem, mp) != 0) (tb(pc), mp, mem) else (pc + 1, mp, mem) 

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

    }		     

    compute3(pg, tb, new_pc, new_mp, new_mem)	

  }

  else mem

}

def run3(pg: String, m: Mem = Map()) = { 

  val pg_opt = optimise(pg)

  compute3(pg_opt, jtable(pg_opt), 0, 0, m)

}

// testcases

//optimise(load_bff("benchmark.bf"))          // should have inserted 0's

//optimise(load_bff("mandelbrot.bf")).length  // => 11203

//time_needed(1, run3(load_bff("benchmark.bf")))

// (7)  Write a function combine which replaces sequences

// of repated increment and decrement commands by appropriate

// two-character commands. For example for sequences of +

//

//              orig bf-cmds  | replacement

//            ------------------------------

//              +             | +A 

//              ++            | +B

//              +++           | +C

//                            |

//              ...           |

//                            | 

//              +++....+++    | +Z

//                (where length = 26)

//

//  Similar for the bf-command -, > and <. All other commands should

//  be unaffected by this change.

//

//  Adapt the compute4 and run4 functions such that they can deal

//  appropriately with such two-character commands.

def splice(cs: List[Char], acc: List[(Char, Int)]) : List[(Char, Int)] = (cs, acc) match {

  case (Nil, acc) => acc  

  case ('[' :: cs, acc) => splice(cs, ('[', 1) :: acc)

  case (']' :: cs, acc) => splice(cs, (']', 1) :: acc)

  case ('.' :: cs, acc) => splice(cs, ('.', 1) :: acc)

  case (',' :: cs, acc) => splice(cs, (',', 1) :: acc)

  case ('0' :: cs, acc) => splice(cs, ('0', 1) :: acc)

  case (c :: cs, Nil) => splice(cs, List((c, 1)))

  case (c :: cs, (d, n) :: acc) => 

    if (c == d && n < 26) splice(cs, (c, n + 1) :: acc)

    else splice(cs, (c, 1) :: (d, n) :: acc)

}

def spl(s: String) = splice(s.toList, Nil).reverse

//spl(load_bff("benchmark.bf"))

def combine(s: String) : String = {

  (for ((c, n) <- spl(s)) yield c match {

    case '>' => List('>', (n + '@').toChar)

    case '<' => List('<', (n + '@').toChar)

    case '+' => List('+', (n + '@').toChar)

    case '-' => List('-', (n + '@').toChar)

    case _ => List(c)

  }).flatten.mkString

}

//combine(load_bff("benchmark.bf"))

def compute4(pg: String, tb: Map[Int, Int], pc: Int, mp: Int, mem: Mem) : Mem = {

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

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

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

      case '>' => (pc + 2, mp + (pg(pc + 1) - '@'), mem)

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

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

      case '-' => (pc + 2, mp, write(mem, mp, sread(mem, mp) - (pg(pc + 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) (tb(pc), mp, mem) else (pc + 1, mp, mem) 

      case ']'  => 

	if (sread(mem, mp) != 0) (tb(pc), mp, mem) else (pc + 1, mp, mem) 

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

    }		     

    compute4(pg, tb, new_pc, new_mp, new_mem)	

  }

  else mem

}

def run4(pg: String, m: Mem = Map()) = { 

  val pg_opt = combine(optimise(pg))

  compute4(pg_opt, jtable(pg_opt), 0, 0, m)

}

// testcases

//combine(optimise(load_bff("benchmark.bf"))) // => """>A+B[<A+M>A-A]<A[[....."""

//time_needed(1, run4(load_bff("benchmark.bf")))

//time_needed(1, run(load_bff("sierpinski.bf"))) 

//time_needed(1, run4(load_bff("sierpinski.bf"))) 

//time_needed(1, run4(load_bff("mandelbrot.bf")))

}