package RexpRelated

import scala.language.implicitConversions    

import scala.language.reflectiveCalls

import scala.annotation.tailrec   

import scala.util.Try

abstract class Bit

case object Z extends Bit

case object S extends Bit

//case class C(c: Char) extends Bit

abstract class Rexp 

case object ZERO extends Rexp

case object ONE extends Rexp

case class CHAR(c: Char) extends Rexp

case class ALTS(rs: List[Rexp]) extends Rexp 

case class SEQ(r1: Rexp, r2: Rexp) extends Rexp 

case class STAR(r: Rexp) extends Rexp 

case class RECD(x: String, r: Rexp) extends Rexp

object Rexp{

  type Bits = List[Bit]

  // abbreviations

  type Mon = (Char, Rexp)

  type Lin = Set[Mon]

  def ALT(r1: Rexp, r2: Rexp) = ALTS(List(r1, r2))

  def PLUS(r: Rexp) = SEQ(r, STAR(r))

  def AALT(bs: Bits, r1: ARexp, r2: ARexp) = AALTS(bs, List(r1, r2))

  def distinctBy[B, C](xs: List[B], f: B => C, acc: List[C] = Nil): List[B] = xs match {

    case Nil => Nil

    case (x::xs) => {

      val res = f(x)

      if (acc.contains(res)) distinctBy(xs, f, acc)  

      else x::distinctBy(xs, f, res::acc)

    }

  } 

  // some convenience for typing in regular expressions

  def charlist2rexp(s : List[Char]): Rexp = s match {

    case Nil => ONE

    case c::Nil => CHAR(c)

    case c::s => SEQ(CHAR(c), charlist2rexp(s))

  }

  implicit def string2rexp(s : String) : Rexp = charlist2rexp(s.toList)

  implicit def RexpOps(r: Rexp) = new {

    def | (s: Rexp) = ALT(r, s)

    def % = STAR(r)

    def ~ (s: Rexp) = SEQ(r, s)

  }

  implicit def stringOps(s: String) = new {

    def | (r: Rexp) = ALT(s, r)

    def | (r: String) = ALT(s, r)

    def % = STAR(s)

    def ~ (r: Rexp) = SEQ(s, r)

    def ~ (r: String) = SEQ(s, r)

    def $ (r: Rexp) = RECD(s, r)

  }

  // translation into ARexps

  def fuse(bs: Bits, r: ARexp) : ARexp = r match {

    case AZERO => AZERO

    case AONE(cs) => AONE(bs ++ cs)

    case ACHAR(cs, f) => ACHAR(bs ++ cs, f)

    case AALTS(cs, rs) => AALTS(bs ++ cs, rs)

    case ASEQ(cs, r1, r2) => ASEQ(bs ++ cs, r1, r2)

    case ASTAR(cs, r) => ASTAR(bs ++ cs, r)

  }

  def internalise(r: Rexp) : ARexp = r match {

    case ZERO => AZERO

    case ONE => AONE(Nil)

    case CHAR(c) => ACHAR(Nil, c)

    case ALTS(List(r1, r2)) => 

      AALTS(Nil, List(fuse(List(Z), internalise(r1)), fuse(List(S), internalise(r2))))

    case ALTS(r1::rs) => {

      val AALTS(Nil, rs2) = internalise(ALTS(rs))

      AALTS(Nil, fuse(List(Z), internalise(r1)) :: rs2.map(fuse(List(S), _)))

    }

    case SEQ(r1, r2) => ASEQ(Nil, internalise(r1), internalise(r2))

    case STAR(r) => ASTAR(Nil, internalise(r))

    case RECD(x, r) => internalise(r)

  }

  internalise(("a" | "ab") ~ ("b" | ""))

  def decode_aux(r: Rexp, bs: Bits) : (Val, Bits) = (r, bs) match {

    case (ONE, bs) => (Empty, bs)

    case (CHAR(f), bs) => (Chr(f), bs)

    case (ALTS(r::Nil), bs) => decode_aux(r, bs)//this case seems only used when we simp a regex before derivatives and it contains things like alt("a")

    case (ALTS(rs), bs) => bs match {

      case Z::bs1 => {

        val (v, bs2) = decode_aux(rs.head, bs1)

        (Left(v), bs2)

      }

      case S::bs1 => {

        val (v, bs2) = decode_aux(ALTS(rs.tail), bs1)

        (Right(v), bs2)			

      }

    }

    case (SEQ(r1, r2), bs) => {

      val (v1, bs1) = decode_aux(r1, bs)

      val (v2, bs2) = decode_aux(r2, bs1)

      (Sequ(v1, v2), bs2)

    }

    case (STAR(r1), S::bs) => {

      val (v, bs1) = decode_aux(r1, bs)

      //println(v)

      val (Stars(vs), bs2) = decode_aux(STAR(r1), bs1)

      (Stars(v::vs), bs2)

    }

    case (STAR(_), Z::bs) => (Stars(Nil), bs)

    case (RECD(x, r1), bs) => {

      val (v, bs1) = decode_aux(r1, bs)

      (Rec(x, v), bs1)

    }

  }

  def decode(r: Rexp, bs: Bits) = decode_aux(r, bs) match {

    case (v, Nil) => v

    case _ => throw new Exception("Not decodable")

  }

  def code(v: Val): Bits = v match {

    case Empty => Nil

    case Chr(a) => Nil

    case Left(v) => Z :: code(v)

    case Right(v) => S :: code(v)

    case Sequ(v1, v2) => code(v1) ::: code(v2)

    case Stars(Nil) => Z::Nil

    case Stars(v::vs) => S::code(v) ::: code(Stars(vs))

  }

  def retrieve(r: ARexp, v: Val): Bits = (r,v) match {

    case (AONE(bs), Empty) => bs

    case (ACHAR(bs, c), Chr(d)) => bs

    case (AALTS(bs, a::Nil), v) => bs ++ retrieve(a, v)

    case (AALTS(bs, as), Left(v)) => bs ++ retrieve(as.head,v)

    case (AALTS(bs, as), Right(v)) => bs ++ retrieve(AALTS(Nil,as.tail),v)

    case (ASEQ(bs, a1, a2), Sequ(v1, v2)) => bs ++ retrieve(a1, v1) ++ retrieve(a2, v2)

    case (ASTAR(bs, a), Stars(Nil)) => bs ++ List(Z) 

    case (ASTAR(bs, a), Stars(v::vs)) => bs ++ List(S) ++ retrieve(a, v) ++ retrieve(ASTAR(Nil, a), Stars(vs))

  }

  //erase function: extracts the regx from Aregex

  def erase(r:ARexp): Rexp = r match{

    case AZERO => ZERO

    case AONE(_) => ONE

    case ACHAR(bs, f) => CHAR(f)

    case AALTS(bs, rs) => ALTS(rs.map(erase(_)))

    case ASEQ(bs, r1, r2) => SEQ (erase(r1), erase(r2))

    case ASTAR(cs, r)=> STAR(erase(r))

  }

  //--------------------------------------------------------------------------------------------------------START OF NON-BITCODE PART

  // nullable function: tests whether the regular 

  // expression can recognise the empty string

  def nullable (r: Rexp) : Boolean = r match {

    case ZERO => false

    case ONE => true

    case CHAR(_) => false

    case ALTS(rs) => rs.exists(nullable)

    case SEQ(r1, r2) => nullable(r1) && nullable(r2)

    case STAR(_) => true

    case RECD(_, r) => nullable(r)

    //case PLUS(r) => nullable(r)

  }

  // derivative of a regular expression w.r.t. a character

  def der (c: Char, r: Rexp) : Rexp = r match {

    case ZERO => ZERO

    case ONE => ZERO

    case CHAR(f) => if (c == f) ONE else ZERO

    case ALTS(List(r1, r2)) => ALTS(List(der(c, r1), der(c, r2)))

    case SEQ(r1, r2) => 

      if (nullable(r1)) ALTS(List(SEQ(der(c, r1), r2), der(c, r2)))

      else SEQ(der(c, r1), r2)

    case STAR(r) => SEQ(der(c, r), STAR(r))

    case RECD(_, r1) => der(c, r1)

    //case PLUS(r) => SEQ(der(c, r), STAR(r))

  }

  def flatten(v: Val) : String = v match {

    case Empty => ""

    case Chr(c) => c.toString

    case Left(v) => flatten(v)

    case Right(v) => flatten(v)

    case Sequ(v1, v2) => flatten(v1) + flatten(v2)

    case Stars(vs) => vs.map(flatten).mkString

    case Rec(_, v) => flatten(v)

  }

  // extracts an environment from a value

  def env(v: Val) : List[(String, String)] = v match {

    case Empty => Nil

    case Chr(c) => Nil

    case Left(v) => env(v)

    case Right(v) => env(v)

    case Sequ(v1, v2) => env(v1) ::: env(v2)

    case Stars(vs) => vs.flatMap(env)

    case Rec(x, v) => (x, flatten(v))::env(v)

  }

  // injection part

  def mkeps(r: Rexp) : Val = r match {

    case ONE => Empty

    case ALTS(List(r1, r2)) => 

      if (nullable(r1)) Left(mkeps(r1)) else Right(mkeps(r2))

    case SEQ(r1, r2) => Sequ(mkeps(r1), mkeps(r2))

    case STAR(r) => Stars(Nil)

    case RECD(x, r) => Rec(x, mkeps(r))

    //case PLUS(r) => Stars(List(mkeps(r)))

  }

  def inj(r: Rexp, c: Char, v: Val) : Val = (r, v) match {

    case (STAR(r), Sequ(v1, Stars(vs))) => Stars(inj(r, c, v1)::vs)

    case (SEQ(r1, r2), Sequ(v1, v2)) => Sequ(inj(r1, c, v1), v2)

    case (SEQ(r1, r2), Left(Sequ(v1, v2))) => Sequ(inj(r1, c, v1), v2)

    case (SEQ(r1, r2), Right(v2)) => Sequ(mkeps(r1), inj(r2, c, v2))

    case (ALTS(List(r1, r2)), Left(v1)) => Left(inj(r1, c, v1))

    case (ALTS(List(r1, r2)), Right(v2)) => Right(inj(r2, c, v2))

    case (CHAR(_), Empty) => Chr(c) 

    case (RECD(x, r1), _) => Rec(x, inj(r1, c, v))

    //case (PLUS(r), Sequ(v1, Stars(vs))) => Stars(inj(r, c, v1)::vs)

  }

  def lex(r: Rexp, s: List[Char]) : Val = s match {

    case Nil => if (nullable(r)) mkeps(r) else throw new Exception("Not matched")

    case c::cs => inj(r, c, lex(der(c, r), cs))

  }

  def lexing(r: Rexp, s: String) : Val = lex(r, s.toList)

  // some "rectification" functions for simplification

  def F_ID(v: Val): Val = v

  def F_RIGHT(f: Val => Val) = (v:Val) => Right(f(v))

  def F_LEFT(f: Val => Val) = (v:Val) => Left(f(v))

  def F_ALT(f1: Val => Val, f2: Val => Val) = (v:Val) => v match {

    case Right(v) => Right(f2(v))

    case Left(v) => Left(f1(v))

  }

  def F_SEQ(f1: Val => Val, f2: Val => Val) = (v:Val) => v match {

    case Sequ(v1, v2) => Sequ(f1(v1), f2(v2))

  }

  def F_SEQ_Empty1(f1: Val => Val, f2: Val => Val) = 

    (v:Val) => Sequ(f1(Empty), f2(v))

  def F_SEQ_Empty2(f1: Val => Val, f2: Val => Val) = 

    (v:Val) => Sequ(f1(v), f2(Empty))

  def F_RECD(f: Val => Val) = (v:Val) => v match {

    case Rec(x, v) => Rec(x, f(v))

  }

  def F_ERROR(v: Val): Val = throw new Exception("error")

  // simplification of regular expressions returning also an

  // rectification function; no simplification under STAR 

  def simp(r: Rexp): (Rexp, Val => Val) = r match {

    case ALTS(List(r1, r2)) => {

      val (r1s, f1s) = simp(r1)

      val (r2s, f2s) = simp(r2)

      (r1s, r2s) match {

        case (ZERO, _) => (r2s, F_RIGHT(f2s))

        case (_, ZERO) => (r1s, F_LEFT(f1s))

        case _ => if (r1s == r2s) (r1s, F_LEFT(f1s))

                  else (ALTS(List(r1s, r2s)), F_ALT(f1s, f2s)) 

      }

    }

    case SEQ(r1, r2) => {

      val (r1s, f1s) = simp(r1)

      val (r2s, f2s) = simp(r2)

      (r1s, r2s) match {

        case (ZERO, _) => (ZERO, F_ERROR)

        case (_, ZERO) => (ZERO, F_ERROR)

        case (ONE, _) => (r2s, F_SEQ_Empty1(f1s, f2s))

        case (_, ONE) => (r1s, F_SEQ_Empty2(f1s, f2s))

        case _ => (SEQ(r1s,r2s), F_SEQ(f1s, f2s))

      }

    }

    case RECD(x, r1) => {

      val (r1s, f1s) = simp(r1)

      (RECD(x, r1s), F_RECD(f1s))

    }

    case r => (r, F_ID)

  }

  /*

  val each_simp_time = scala.collection.mutable.ArrayBuffer.empty[Long]

  val each_simp_timeb = scala.collection.mutable.ArrayBuffer.empty[Long]

  */

  def lex_simp(r: Rexp, s: List[Char]) : Val = s match {

    case Nil => {

      if (nullable(r)) {

        mkeps(r) 

      }

      else throw new Exception("Not matched")

    }

    case c::cs => {

      val (r_simp, f_simp) = simp(der(c, r))

      inj(r, c, f_simp(lex_simp(r_simp, cs)))

    }

  }

  def lexing_simp(r: Rexp, s: String) : Val = lex_simp(r, s.toList)

  //println(lexing_simp(("a" | "ab") ~ ("b" | ""), "ab"))

  // filters out all white spaces

  def tokenise(r: Rexp, s: String) = 

    env(lexing_simp(r, s)).filterNot { _._1 == "w"}

  //reads the string from a file 

  def fromFile(name: String) : String = 

    io.Source.fromFile(name).mkString

  def tokenise_file(r: Rexp, name: String) = 

    tokenise(r, fromFile(name))

  //   Testing

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

  def time[T](code: => T) = {

    val start = System.nanoTime()

    val result = code

    val end = System.nanoTime()

    println((end - start)/1.0e9)

    result

  }

  //--------------------------------------------------------------------------------------------------------END OF NON-BITCODE PART

  // bnullable function: tests whether the aregular 

  // expression can recognise the empty string

  def bnullable (r: ARexp) : Boolean = r match {

    case AZERO => false

    case AONE(_) => true

    case ACHAR(_,_) => false

    case AALTS(_, rs) => rs.exists(bnullable)

    case ASEQ(_, r1, r2) => bnullable(r1) && bnullable(r2)

    case ASTAR(_, _) => true

  }

  def mkepsBC(r: ARexp) : Bits = r match {

    case AONE(bs) => bs

    case AALTS(bs, rs) => {

      val n = rs.indexWhere(bnullable)

      bs ++ mkepsBC(rs(n))

    }

    case ASEQ(bs, r1, r2) => bs ++ mkepsBC(r1) ++ mkepsBC(r2)

    case ASTAR(bs, r) => bs ++ List(Z)

  }

  // derivative of a regular expression w.r.t. a character

  def bder(c: Char, r: ARexp) : ARexp = r match {

    case AZERO => AZERO

    case AONE(_) => AZERO

    case ACHAR(bs, f) => if (c == f) AONE(bs) else AZERO

    case AALTS(bs, rs) => AALTS(bs, rs.map(bder(c, _)))

    case ASEQ(bs, r1, r2) => 

      if (bnullable(r1)) AALT(bs, ASEQ(Nil, bder(c, r1), r2), fuse(mkepsBC(r1), bder(c, r2)))

      else ASEQ(bs, bder(c, r1), r2)

    case ASTAR(bs, r) => ASEQ(bs, fuse(List(S), bder(c, r)), ASTAR(Nil, r))

  }

  def ders (s: List[Char], r: Rexp) : Rexp = s match {

    case Nil => r

    case c::s => ders(s, der(c, r))

  }

  // derivative w.r.t. a string (iterates bder)

  @tailrec

  def bders (s: List[Char], r: ARexp) : ARexp = s match {

    case Nil => r

    case c::s => bders(s, bder(c, r))

  }

  def flats(rs: List[ARexp]): List[ARexp] = rs match {

      case Nil => Nil

      case AZERO :: rs1 => flats(rs1)

      case AALTS(bs, rs1) :: rs2 => rs1.map(fuse(bs, _)) ::: flats(rs2)

      case r1 :: rs2 => r1 :: flats(rs2)

  }

  /*

  def remove(v: Val): Val = v match{

    case Right(v1) => v1

    case Left(v1) => v1

    case _ => throw new Exception("Not removable")

  }*/

  def augment(v: Val, i: Int): Val = if(i > 1) augment(Right(v), i - 1) else Right(v)

//an overly complex version

/*

    if(rel_dist >0){//the regex we are dealing with is not what v points at

      rs match{

        case Nil => throw new Exception("Trying to simplify a non-existent value")

        case AZERO :: rs1 => flats_vsimp(rs1, rel_dist - 1, remove(v))

        case AALTS(bs, rs1) :: rs2 => flats_vsimp(rs2, rel_dist - 1, augment(v, rs1.length - 1))//rs1 is guaranteed to have a len geq 2

        case r1 :: rs2 => flats_vsimp(rs2, rel_dist - 1, v)

      }

    }

    else if(rel_dist == 0){//we are dealing with regex v is pointing to -- "v->r itself"

      rs match{//r1 cannot be zero

        AALTS(bs, rs1) :: rs2 => flats_vsimp(  )

        AZERO::rs2 => throw new Exception("Value corresponds to zero")

        r1::rs2 => flats_vsimp(rs2, rel_dist - 1, v)

      }

    }

    else{

    }

    */

  def flats_vsimp(rs: List[ARexp], position: Int): Int = (rs, position) match {

    case (_, 0) => 0

    case (Nil, _) => 0

    case (AZERO :: rs1, _) => flats_vsimp(rs1, position - 1) - 1

    case (AALTS(bs, rs1) :: rs2, _) => rs1.length - 1 + flats_vsimp(rs2, position - 1)

    case (r1 :: rs2, _) => flats_vsimp(rs2, position - 1)

  }

  def rflats(rs: List[Rexp]): List[Rexp] = rs match {

    case Nil => Nil

    case ZERO :: rs1 => rflats(rs1)

    case ALTS(rs1) :: rs2 => rs1 ::: rflats(rs2)

    case r1 :: rs2 => r1 :: rflats(rs2)

  }

  var flats_time = 0L

  var dist_time = 0L

  def bsimp(r: ARexp): ARexp = r match {

    case ASEQ(bs1, r1, r2) => (bsimp(r1), bsimp(r2)) match {

        case (AZERO, _) => AZERO

        case (_, AZERO) => AZERO

        case (AONE(bs2), r2s) => fuse(bs1 ++ bs2, r2s)

        case (r1s, r2s) => ASEQ(bs1, r1s, r2s)

    }

    case AALTS(bs1, rs) => {

      val rs_simp = rs.map(bsimp)

      val flat_res = flats(rs_simp)

      val dist_res = distinctBy(flat_res, erase)

      dist_res match {

        case Nil => AZERO

        case s :: Nil => fuse(bs1, s)

        case rs => AALTS(bs1, rs)  

      }

    }

    //case ASTAR(bs, r) => ASTAR(bs, bsimp(r))

    case r => r

  }

  def find_pos(v: Val, rs: List[ARexp]): Int = (v, rs) match{

    case (v, r::Nil) => 0

    case (Right(v), r::rs) => find_pos(v, rs) + 1

    case (Left(v), r::rs) => 0

    //case (v, _) => 0

  }

  def find_pos_aux(v: Val, r: ARexp): Int = r match {

    case AALTS(bs, rs) => find_pos(v, rs)

    case r => 0

  }

  def remove(v: Val, rs: List[ARexp]) : Val = (v,rs) match {//remove the outmost layer of ALTS's Left and Right

    //we have to use r to detect the bound of nested L/Rs

    case (v, r::Nil) => v

    case (Right(v), r::rs) => remove(v, rs) 

    case (Left(v), r::rs) => v 

    //case (v, r::Nil) => v

  }

  def simple_end(v: Val): Boolean = v match {

    case Left(v) => return false

    case Right(v) => return simple_end(v)

    case v => return true

  }

  def isend(v: Val, rs: List[ARexp], position: Int): Boolean = {//TODO: here the slice api i am not familiar with so this call might be incorrect and crash the bsimp2

    val rsbh = rs.slice(position + 1, rs.length)

    val out_end = if(flats(rsbh) == Nil) true else false

    val inner_end = simple_end(v)

    inner_end && out_end

  }

  def get_coat(v: Val, rs: List[Rexp], vs: Val): Val = (v, rs) match{//the dual operation of remove(so-called by myself)

    case (Right(v), r::Nil) => Right(vs)

    case (Left(v), r::rs) => Left(vs) 

    case (Right(v), r::rs) => Right(get_coat(v, rs, vs))

  }

  def coat(v: Val, i: Int) : Val = i match {

    case 0 => v

    case i => coat(Right(v), i - 1)

  }

  //This version takes a regex and a value, return a simplified regex and its corresponding simplified value 

  def bsimp2(r: ARexp, v: Val): (ARexp, Val) = (r,v) match{

    case (ASEQ(bs1, r1, r2), Sequ(v1, v2)) => (bsimp2(r1, v1), bsimp2(r2, v2)) match {

        case ((AZERO, _), (_, _) )=> (AZERO, undefined)

        case ((_, _), (AZERO, _)) => (AZERO, undefined)

        case ((AONE(bs2), v1s) , (r2s, v2s)) => (fuse(bs1 ++ bs2, r2s), v2s )//v2 tells how to retrieve bits in r2s, which is enough as the bits of the first part of the sequence has already been integrated to the top level of the second regx.

        case ((r1s, v1s), (r2s, v2s)) => (ASEQ(bs1, r1s, r2s),  Sequ(v1s, v2s))

    }

    case (AALTS(bs1, rs), v) => {

      //phase 1 transformation so that aalts(bs1, rs) => aalts(bs1, rsf) and v => vf

      val init_ind = find_pos(v, rs)

      //println(rs)

      //println(v)

      val vs = bsimp2(rs(init_ind), remove(v, rs))//remove all the outer layers of left and right in v to  match the regx rs[i]

      //println(vs)

      val rs_simp = rs.map(bsimp)

      val vs_kernel = rs_simp(init_ind) match {

        case AALTS(bs2, rs2) => remove(vs._2, rs2)//remove the secondary layer of left and right

        case r => vs._2

      }

      val flat_res = flats(rs_simp)

      //println(rs_simp)

      //println(flat_res)

      //println(init_ind)

      val vs_for_coating = if(isend(vs._2, rs_simp, init_ind)||flat_res.length == 1) vs_kernel else Left(vs_kernel)

      //println(vs_for_coating)

      val r_s = rs_simp(init_ind)//or vs._1

      val shift = flats_vsimp(rs_simp, init_ind) + find_pos_aux(vs._2, rs_simp(init_ind))

      //println(shift)