// Main Part 5 about a "Compiler" for the Brainf*** language
//============================================================


object M5b {

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


// 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)
}


type Mem = Map[Int, Int]

import io.Source
import scala.util._

// ADD YOUR CODE BELOW
//======================

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

    if(pc<0 || pc>= prog.length())
        mem
    else
        prog.charAt(pc) match
            case '>' => compute(prog, pc+1, mp+1, mem)

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

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

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

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

            case '[' => 
                if(sread(mem, mp) == 0) 
                    compute(prog, jumpRight(prog, pc+1, 0), mp, mem)
                else 
                    compute(prog, pc+1, mp, mem) 

            case ']' => 
                if(sread(mem, mp) == 0) 
                    compute(prog, pc+1, mp, mem)
                else 
                    compute(prog, jumpLeft(prog, pc-1, 0), mp, mem) 

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



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


// (6) 
def jumpRight(prog: String, pc: Int, level: Int) : Int = 
    if (pc<0 || pc>= prog.length() )
        pc
    else
        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)


def jumpLeft(prog: String, pc: Int, level: Int) : Int = 
    if (pc<0 || pc>= prog.length() )
          pc
    else
        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)


def jtable(pg: String) : Map[Int, Int] = 
    val b1 = (0 until pg.length)
      .filter(n => pg.substring(n, n+1) == "[")
      .map(n => n -> jumpRight(pg, n + 1, 0)).toMap

    val b2 = (0 until pg.length)
       .filter(n => pg.substring(n, n+1) == "]")
       .map(n => n -> jumpLeft(pg, n-1, 0)).toMap

    b1++b2


// testcase
//
// jtable("""+++++[->++++++++++<]>--<+++[->>++++++++++<<]>>++<<----------[+>.>.<+<]""")
// =>  Map(69 -> 61, 5 -> 20, 60 -> 70, 27 -> 44, 43 -> 28, 19 -> 6)

def load_bff(name: String) : String =  
    try 
       Source.fromFile(name).mkString
    catch
        case e: Exception => ""

def sread(mem: Mem, mp: Int) : Int = 
    mem.getOrElse(mp,0)

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

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

    if(pc<0 || pc>= pg.length())
        mem
    else
        pg.charAt(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 '.' => 
                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, pc+1, mp, mem)
                else 
                    compute2(pg, tb, tb(pc), mp, mem)  

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

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

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



// (7) 

def optimise(s: String) : String = 
    val notCommand = """[^<>+\-.\[\]]""".r
    val occurrence = """\[-\]""".r

    val deleted = notCommand.replaceAllIn(s, "")
    occurrence.replaceAllIn(deleted, "0")


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

    if(pc<0 || pc>= pg.length())
        mem
    else
        pg.charAt(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 '.' => 
                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, pc+1, mp, mem)
                else 
                    compute3(pg, tb, tb(pc), mp, mem)  

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

def run3(pg: String, m: Mem = Map()) = 
    val opt = optimise(pg)
    compute3(opt, jtable(opt), 0, 0, m)



// testcases
//
// optimise(load_bff("benchmark.bf"))          // should have inserted 0's
// optimise(load_bff("mandelbrot.bf")).length  // => 11205
// 
// time_needed(1, run3(load_bff("benchmark.bf")))



// (8)  
// consider if the char does not exist\\

def counterHelper(chars: List[Char], consec: Int, charToCount: Char): Int =
    chars match 
          case head :: tail if ((head == charToCount && head == tail.headOption.getOrElse(' ')) )=>
            counterHelper(tail, consec + 1, charToCount)

          case head :: tail if (head == charToCount && head != tail.headOption.getOrElse(' '))=>
            consec+1

          case head :: tail if (head != charToCount && head != tail.headOption.getOrElse(' '))=>
            consec
   

def counter(input: String, charToCount: Char): Int = 
    counterHelper(input.toList, 0, charToCount)

def handleCharacter(orgin: String, newstr: String, sindex: Int, letterMap: Map[Int, Char], charToCount: Char): String = 
    val num = counter(orgin.substring(sindex), charToCount)
    val lett = letterMap.getOrElse(num, "")
    combineHelper(orgin, newstr + charToCount + lett, sindex + num, letterMap)

def combineHelper(orgin: String, newstr: String, sindex: Int, letterMap: Map[Int, Char] ): String = 
    if (sindex >= orgin.length())
      newstr
    else 
      val result = 
        orgin.charAt(sindex) match 
            case '>' => handleCharacter(orgin, newstr, sindex, letterMap, '>')
            case '<' => handleCharacter(orgin, newstr, sindex, letterMap, '<')
            case '+' => handleCharacter(orgin, newstr, sindex, letterMap, '+')
            case '-' => handleCharacter(orgin, newstr, sindex, letterMap, '-')
            case _ => combineHelper(orgin, newstr + orgin.charAt(sindex), sindex + 1, letterMap)

      result

def combine(s: String) : String = 
    val letterMap = (1 to 26).zip('A' to 'Z').toMap
    combineHelper(s,"",0, letterMap)

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

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

    if(pc<0 || pc>= pg.length())
            mem
    else
        pg.charAt(pc) match
            case '>' => compute4(pg,tb, pc+1, mp+1, mem)

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

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

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

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

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

// should call first optimise and then combine on the input string
//
def run4(pg: String, m: Mem = Map()) = 
    val opt = optimise(pg)
    val com= combine(opt)
    compute4(com, jtable(com), 0, 0, m)
    
 
// testcases
// combine(optimise(load_bff("benchmark.bf"))) // => """>A+B[<A+M>A-A]<A[[....."""

// testcases (they should now run much faster)
// time_needed(1, run4(load_bff("benchmark.bf")))
// time_needed(1, run4(load_bff("sierpinski.bf"))) 
// time_needed(1, run4(load_bff("mandelbrot.bf")))


}