package object comp1 {

// Abacus to TM translation

import lib._

import turing._

import abacus._

// TMs used in the translation

val TMInc = TM((WOc, 1), (R, 2), (WOc, 3), (R, 2), (WOc, 3), (R, 4), 

               (L, 7), (WBk, 5), (R, 6), (WBk, 5), (WOc, 3), (R, 6),

               (L, 8), (L, 7), (R, 9), (L, 7), (R, 10), (WBk, 9))

val TMDec = TM((WOc, 1), (R, 2), (L, 14), (R, 3), (L, 4), (R, 3),

               (R, 5), (WBk, 4), (R, 6), (WBk, 5), (L, 7), (L, 8),

               (L, 11), (WBk, 7), (WOc, 8), (R, 9), (L, 10), (R, 9),

               (R, 5), (WBk, 10), (L, 12), (L, 11), (R, 13), (L, 11),

               (R, 17), (WBk, 13), (L, 15), (L, 14), (R, 16), (L, 14),

               (R, 0), (WBk, 16))

val TMGoto = TM((Nop, 1), (Nop, 1))

val TMMopup_aux = TM((R, 2), (R, 1), (L, 5), (WBk, 3), (R, 4), (WBk, 3),

                     (R, 2), (WBk, 3), (L, 5), (L, 6), (R, 0), (L, 6))

def TMFindnth(n: Int) : TM = n match {

  case 0 => TM(Nil)

  case n => TMFindnth(n - 1) ++ TM((WOc, 2 * n - 1), (R, 2 * n), (R, 2 * n + 1), (R, 2 * n))

}

def TMMopup(n: Int) = {

  def TMMopup1(n: Int) : TM = n match {

    case 0 => TM(Nil)

    case n => TMMopup1(n - 1) ++ TM((R, 2 * n + 1), (WBk, 2 * n), (R, 2 * n - 1), (WOc, 2 * n))

  }

  TMMopup1(n) ++ TMMopup_aux.shift(2 * n)

}

// start address of the nth instruction

def address(p: AProg, n: Int) = {

  def layout(p: AProg) = p.map(_ match {

    case Inc(n) => 2 * n + 9 

    case Dec(n, _) => 2 * n + 16 

    case Goto(n) => 1

  })

  layout(p).take(n).sum + 1

}

def compile_Inc(s: Int, n: Int) = 

  TMFindnth(n).shift(s - 1) ++ TMInc.shift(2 * n).shift(s - 1)

def compile_Dec(s: Int, n: Int, e: Int) = 

  TMFindnth(n).shift(s - 1) ++ TMDec.shift(2 * n).shift(s - 1).adjust(e)

def compile_Goto(s: Int) = TMGoto.shift(s - 1)

def compile(p: AProg, s: Int, i: AInst) = i match {

  case Inc(n) => compile_Inc(s, n)

  case Dec(n, e) => compile_Dec(s, n, address(p, e))

  case Goto(e) => compile_Goto(address(p, e))

}

// component TMs for each instruction

def TMs(p: AProg) = 

  p.zipWithIndex.map{case (i, n) => compile(p, address(p, n), i)}

def toTM(p: AProg) = TMs(p).reduceLeft(_ ++ _)

}