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

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

object CW10b {

// !!! 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.

type Mem = Map[Int, Int]

import io.Source

import scala.util._

def load_bff(name: String) : String = 

  Try(scala.io.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 + (mp -> v)

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

    pc match {

        case pc: Int if (pc >= 0 && pc < prog.length) => {

            prog(pc) match {

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

                case ']' => if (level == 0) pc + 1 else jumpRight(prog, pc + 1, level - 1)

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

            }

        }

        case _ => pc

    }

}

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

    pc match {

        case pc: Int if (pc >= 0 && pc < prog.length) => {

            prog(pc) match {

                case '[' => if (level == 0) pc + 1 else jumpLeft(prog, pc - 1, level - 1)

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

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

            }

        }

        case _ => pc

    }

}

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

  prog(pc) match {

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

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

    case _ => println("Something went horrible wrong, I am sorry"); 0

  }

}

// DEBUGGING INFORMATION FOR COMPILERS!!!

//

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

// to produce correct code. One way to debug them is to run

// example programs ``unoptimised''; and then optimised. Does

// the optimised version still produce the same result?

// for timing purposes

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)

}

// TASKS

//=======

// (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 about

//     pc positions where '[' or a ']' are stored. The information

//     is 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 immediately look up the jump address in the jtable.

//  for ((char, index) <- str.zipWithIndex if (List('[', ']').contains(char))) yield (index, get_position(str, index, 0))

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

  val table = for ((char, index) <- pg.zipWithIndex if (List('[', ']').contains(char))) yield (index, get_position(pg, index, 0))

  table.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 = {

  pc match {

    case pc: Int if (pc >= 0 && pc < pg.length) => {

      pg(pc) match {

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

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

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

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

        case '.' => print(sread(mem, mp).toChar); compute2(pg, tb, pc + 1, mp, mem)

        case '[' => if (sread(mem, mp) == 0) compute2(pg, tb, tb(pc), mp, mem) else compute2(pg, tb, pc + 1, mp, mem)

        case ']' => if (sread(mem, mp) != 0) compute2(pg, tb, tb(pc), mp, mem) else compute2(pg, tb, pc + 1, mp, mem)

        case '*' => compute2(pg, tb, pc + 1, mp, write(mem, mp, sread(mem, mp) * sread(mem, mp - 1)))

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

        case '#' => print(sread(mem, mp)); compute2(pg, tb, pc + 1, mp, mem)

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

      }

    }

    case _ => mem

  }

}

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

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

}

// testcases

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

// time_needed(1, run2(load_bff("./main5/sierpinski.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 occurrences of [-] and 

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

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

// load_bff("./main5/mandelbrot.bf").replaceAll("""[^<>+‐.\[\]@#*]""", "").replaceAll("""\[-\]""", "0")

// "Correct" regex

// s.replaceAll("""[^<>+‐.\[\]@#*]""", "").replaceAll("""\[-\]""", "0")

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

def optimise(s: String) : String = {

  //s.replaceAll("""[^<>+-.\[\]@#*]""","")

  // .replaceAll("""\[-\]""", "0")

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

}

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

  pc match {

    case pc: Int if (pc >= 0 && pc < pg.length) => {

      pg(pc) match {

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

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

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

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

        case '.' => print(sread(mem, mp).toChar); compute3(pg, tb, pc + 1, mp, mem)

        case '[' => if (sread(mem, mp) == 0) compute3(pg, tb, tb(pc), mp, mem) else compute3(pg, tb, pc + 1, mp, mem)

        case ']' => if (sread(mem, mp) != 0) compute3(pg, tb, tb(pc), mp, mem) else compute3(pg, tb, pc + 1, mp, mem)

        case '*' => compute3(pg, tb, pc + 1, mp, write(mem, mp, sread(mem, mp) * sread(mem, mp - 1)))

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

        case '#' => print(sread(mem, mp)); compute3(pg, tb, pc + 1, mp, mem)

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

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

      }

    }

    case _ => mem

  }

}

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

  val optimised = optimise(pg)

  compute3(optimised, jtable(optimised), 0, 0, m)

}

// testcases

//

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

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

// 

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

// time_needed(1, run3(load_bff("./main5/mandelbrot.bf")))

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

// of repeated 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.

// val alphabet = "АБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ"

val alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"

// Try any alphabet, it will work as long as the character is recognised and the characters are unique

def get_number_from_character(char: Char) : Int = {

  alphabet.indexOf(char) + 1

}

def get_character_from_number(int: Int) : Char = {

  alphabet(int - 1)

}

@annotation.tailrec 

def split_by_repetition(string : String, list : List[String] = Nil) : List[String] = {

    if(string.size == 0) list.reverse 

    else {

        val (left_substring, right_substring) = string.span(_ == string(0))

        split_by_repetition(right_substring, left_substring :: list)

    }

}

def combine(s: String) : String = {

  val split_strings = split_by_repetition(s)

  val lists = for (string <- split_strings) yield {

    if (List("+"(0), "-"(0), "<"(0), ">"(0)).contains(string.head)) {

      val long_repeat = s"${string.head}${alphabet.last}" * (string.size / alphabet.length)

      val short_repeat = if ((string.size % alphabet.length) != 0) s"${string.head}${get_character_from_number(string.size % alphabet.length)}" else ""

      long_repeat + short_repeat

    } else string

  }

  lists.mkString("")

}

// testcase

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

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

  pc match {

    case pc: Int if (pc >= 0 && pc < pg.length) => {

      pg(pc) match {

        case '>' => val number = get_number_from_character(pg(pc + 1)); compute4(pg, tb, pc + 2, mp + number, mem)

        case '<' => val number = get_number_from_character(pg(pc + 1)); compute4(pg, tb, pc + 2, mp - number, mem)

        case '+' => val number = get_number_from_character(pg(pc + 1)); compute4(pg, tb, pc + 2, mp, write(mem, mp, sread(mem, mp) + number))

        case '-' => val number = get_number_from_character(pg(pc + 1)); compute4(pg, tb, pc + 2, mp, write(mem, mp, sread(mem, mp) - number))

        case '.' => print(sread(mem, mp).toChar); compute4(pg, tb, pc + 1, mp, mem)

        case '[' => if (sread(mem, mp) == 0) compute4(pg, tb, tb(pc), mp, mem) else compute4(pg, tb, pc + 1, mp, mem)

        case ']' => if (sread(mem, mp) != 0) compute4(pg, tb, tb(pc), mp, mem) else compute4(pg, tb, pc + 1, mp, mem)

        case '*' => compute4(pg, tb, pc + 1, mp, write(mem, mp, sread(mem, mp) * sread(mem, mp - 1)))

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

        case '#' => print(sread(mem, mp)); compute4(pg, tb, pc + 1, mp, mem)

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

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

      }

    }

    case _ => mem

  }

}

// should call first optimise and then combine on the input string

//

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

  val processed_prog = combine(optimise(pg))

  compute4(processed_prog, jtable(processed_prog), 0, 0, m)

}

// testcases

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

// testcases (they should now run much faster)

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

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

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

}