abstract class Bit

case object Z extends Bit

case object S extends Bit

type Bits = List[Bit]

case class AONE(bs: Bits) extends ARexp

case class ACHAR(bs: Bits, c: Char) extends ARexp

case class AALTS(bs: Bits, rs: List[ARexp]) extends ARexp 

case class ASEQ(bs: Bits, r1: ARexp, r2: ARexp) extends ARexp 

case class ASTAR(bs: Bits, r: ARexp) extends ARexp 

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

case class Position(i: Int, v: Val) extends Val  // for testing purposes

case object Undefined extends Val                // for testing purposes

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

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

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

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

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

//erase function: extracts the regx from Aregex

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

  case AZERO => ZERO

  case AONE(_) => ONE

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

  case AALTS(bs, Nil) => ZERO

  case AALTS(bs, r::Nil) => erase(r)

  case AALTS(bs, r::rs) => ALT(erase(r), erase(AALTS(bs, rs)))

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

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

}

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

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

  case ALT(r1, r2) => AALT(Nil, fuse(List(Z), internalise(r1)), fuse(List(S), internalise(r2)))

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

  case (ALT(r1, r2), Z::bs) => {

  case (ALT(r1, r2), S::bs) => {

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

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

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

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

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

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

  case Stars(Nil) => List(S)

  case Stars(v::vs) =>  Z :: encode(v) ::: encode(Stars(vs))

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

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

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

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

  case AALTS(bs, r::Nil) => bs ++ bmkeps(r) 

  case AALTS(bs, r::rs) => 

    if (bnullable(r)) bs ++ bmkeps(r) else bmkeps(AALTS(bs, rs))  

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

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

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

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

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

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

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

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

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

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

  case Nil => if (bnullable(r)) bmkeps(r) else throw new Exception("Not matched")

  case c::cs => blex(bder(c, r), cs)

def pre_blexing(r: ARexp, s: String)  : Bits = blex(r, s.toList)

def blexing(r: Rexp, s: String) : Val = decode(r, pre_blexing(internalise(r), s))

// example by Tudor

val reg = ((("a".%)) ~ ("b" | "c")).%

println(blexing(reg, "aab"))

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

// simplification 

//

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

  case Nil => Nil

  case AZERO :: rs => flts(rs)

  case AALTS(bs, rs1) :: rs => rs1.map(fuse(bs, _)) ++ flts(rs)

  case r1 :: rs => r1 :: flts(rs)

}

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)

  }

} 

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

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

      //case (AALTS(bs, rs), r2) => AALTS(bs, rs.map(ASEQ(Nil, _, r2)))

  case AALTS(bs1, rs) => distinctBy(flts(rs.map(bsimp)), erase) match {

      case Nil => AZERO

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

      case rs => AALTS(bs1, rs)

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

  case Nil => if (bnullable(r)) bmkeps(r) 

  case c::cs => blex(bsimp(bder(c, r)), cs)

}

def blexing_simp(r: Rexp, s: String) : Val = 

  decode(r, blex_simp(internalise(r), s.toList))

println(blexing_simp(reg, "aab"))

// bsimp2 by Chengsong

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

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

    case ( r::rs1, Right(v)) => pos_i(rs1, v) + 1

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

}

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

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

    case (r::rs1, Right(v)) => pos_v(rs1, v)

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

}

def unify(rs: List[ARexp], v: Val): Val = {

  Position(pos_i(rs, v), pos_v(rs, v))

}

// coat does the job of "coating" a value

// given the number of right outside it

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

  case 0 => v

  case i => if (i > 0) coat(Right(v), i - 1) else { println(v, i); throw new Exception("coat minus")}

def distinctBy2[B, C](v: Val, xs: List[B], f: B => C, acc: List[C] = Nil, res: List[B] = Nil): (List[B], Val) = xs match {

    case Nil => (res, v)

    case (x::xs) => {

      val re = f(x)

      if (acc.contains(re)) v match { 

        case Position(i, v0) => distinctBy2(Position(i - 1, v0), xs, f, acc, res)  

        case _ => throw new Exception("dB2")

      }

      else distinctBy2(v, xs, f, re::acc, x::res)

    }

  }

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 flats2(front: List[ARexp], i: Int, rs: List[ARexp], v: Val): (List[ARexp], Val) = v match {

    case Position(j, v0) => {

      if (i < 0) (front ::: flats(rs), Position(j, v0) ) 

      else if(i == 0){

        rs match {

          case AALTS(bs, rs1) :: rs2 => ( (front ::: rs1.map(fuse(bs, _))):::flats(rs2), Position(j + rs1.length - 1, pos_v(rs1, v0)))

          case r::rs2 => (front ::: List(r) ::: flats(rs2), Position(j, v0))

          case _ => throw new Exception("flats2 i = 0")

        }

      }

      else{

        rs match {

          case AZERO::rs1 => flats2(front, i - 1, rs1, Position(j - 1, v0))

          case AALTS(bs, rs1) ::rs2 => flats2(front:::rs1.map(fuse(bs, _)), i - 1, rs2, Position(j + rs1.length - 1, v0))

          case r::rs1 => flats2(front:::List(r), i - 1, rs1, Position(j, v0)) 

          case _ => throw new Exception("flats2 i>0")

        }

      }

    }

    case _ => throw new Exception("flats2 error")

  }

def deunify(rs_length: Int, v: Val): Val = v match{

  case Position(i, v0) => {

      if (i <0 ) { println(rs_length, v); throw new Exception("deunify minus") } 

      else if (rs_length == 1) {println(v); v}

      else if (rs_length - 1 == i) coat(v0, i) 

      else coat(Left(v0), i)

  }

  case _ => throw new Exception("deunify error")

}

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) => {

      val vlist = unify(rs, v)

      vlist match {

        case Position(i, v0) => {

          val v_simp = bsimp2(rs(i), v0)._2

          val rs_simp = rs.map(bsimp)

          val flat_res = flats2( Nil, i, rs_simp, Position(i, v_simp) )

          val dist_res = distinctBy2(flat_res._2, flat_res._1, erase)

          val rs_new = dist_res._1

          val v_new = deunify(rs_new.length, dist_res._2)

          rs_new match {

            case Nil => (AZERO, Undefined)

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

            case rs => (AALTS(bs1, rs), v_new)

          }

        }

        case _ => throw new Exception("Funny vlist bsimp2")

      }

    }

    // STAR case

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

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

  }

val dr = ASEQ(List(),AALTS(List(S),List(AONE(List(Z)), AONE(List(S)))),ASTAR(List(),AALTS(List(),List(ACHAR(List(Z),'a'), ACHAR(List(S),'a')))))

val dv = Sequ(Left(Empty),Stars(List()))

println(bsimp2(dr, dv))

/*

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

  case Nil => if (bnullable(r)) bmkeps(r) 

              else throw new Exception("Not matched")

  case c::cs => blex(bsimp2(bder(c, r)), cs)

}

def blexing_simp2(r: Rexp, s: String) : Val = 

  decode(r, blex_simp2(internalise(r), s.toList))

println(blexing_simp2(reg, "aab"))

*/

/*

val evil1 = (("a").%) ~ "b"

val evil2 = (((("a").%).%).%) ~ "b"

val evil3 = (("a"~"a") | ("a")).%

for(i <- 1 to 10000 by 1000) {

    println(time_needed(1, blex_simp(internalise(evil1), ("a"*i + "b").toList)))

}

for(i <- 1 to 10000 by 1000) {

    println(time_needed(1, blexing_simp(evil1, "a"*i + "b")))

}

for(i <- 1 to 10000 by 1000) {

    println(time_needed(1, blexing_simp(evil2, "a"*i + "b")))

}