}

// 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 ALT(r1, r2) => nullable(r1) || nullable(r2)

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

  case STAR(_) => true

}

// 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(d) => if (c == d) ONE else ZERO

  case ALT(r1, r2) => ALT(der(c, r1), der(c, r2))

  case SEQ(r1, r2) => 

    if (nullable(r1)) ALT(SEQ(der(c, r1), r2), der(c, r2))

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

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

}

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

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

  case Nil => r

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

// mkeps and injection part

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

  case ONE => Empty

  case ALT(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)

}

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 (ALT(r1, r2), Left(v1)) => Left(inj(r1, c, v1))

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

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

}

// main lexing function (produces a value)

// - no simplification

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)

// Bitcoded + Annotation

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

def retrieve(r: ARexp, v: Val) : List[Boolean] = (r, v) match {

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

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

  case (AALT(bs, r1, r2), Left(v)) => bs ++ retrieve(r1, v)

  case (AALT(bs, r1, r2), Right(v)) => bs ++ retrieve(r2, v)

  case (ASEQ(bs, r1, r2), Sequ(v1, v2)) => 

    bs ++ retrieve(r1, v1) ++ retrieve(r2, v2)

  case (ASTAR(bs, r), Stars(Nil)) => bs ++ List(true)

  case (ASTAR(bs, r), Stars(v :: vs)) => 

     bs ++ List(false) ++ retrieve(r, v) ++ retrieve(ASTAR(Nil, r), Stars(vs))

}

def encode(v: Val) : List[Boolean] = v match {

  case Empty => Nil

  case Chr(c) => Nil

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

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

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

  case Stars(Nil) => List(true)

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

}

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

  case AALT(_, r1, r2) => anullable(r1) || anullable(r2)

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

    if (anullable(r1)) bs ++ mkepsBC(r1) else bs ++ mkepsBC(r2)

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

  case AALT(bs, r1, r2) => AALT(bs, ader(c, r1), ader(c, r2))

    if (anullable(r1)) AALT(bs, ASEQ(Nil, ader(c, r1), r2), fuse(mkepsBC(r1), ader(c, r2)))

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

  case ASTAR(bs, r) => ASEQ(bs, fuse(List(false), ader(c, r)), ASTAR(Nil, r))

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

  case c::s => aders(s, ader(c, r))

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

  case Nil => if (anullable(r)) mkepsBC(r) else throw new Exception("Not matched")

  case c::cs => alex(ader(c, r), cs)

def pre_alexing(r: ARexp, s: String)  : List[Boolean] = alex(r, s.toList)

def alexing(r: Rexp, s: String) : Val = decode(r, pre_alexing(internalise(r), s))

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

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

  case AALT(bs1, r1, r2) => (asimp(r1), asimp(r2)) match {

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

  case Nil => if (anullable(r)) mkepsBC(r) 

              else throw new Exception("Not matched")

  case c::cs => alex(asimp(ader(c, r)), cs)

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

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

println(pre_alexing(internalise(rf), "ab"))

println(alexing(rf, "ab"))

println(alexing_simp(rf, "ab"))

println(pre_alexing(internalise(r0), "ab"))

println(alexing(r0, "ab"))

println(alexing_simp(r0, "ab"))

println(alexing(r1, "abcd"))

println(alexing_simp(r1, "abcd"))

println(alexing((("" | "a") ~ ("ab" | "b")), "ab"))

println(alexing_simp((("" | "a") ~ ("ab" | "b")), "ab"))

println(alexing((("" | "a") ~ ("b" | "ab")), "ab"))

println(alexing_simp((("" | "a") ~ ("b" | "ab")), "ab"))

println(alexing((("" | "a") ~ ("c" | "ab")), "ab"))

println(alexing_simp((("" | "a") ~ ("c" | "ab")), "ab"))

println(alexing(sulzmann, "a" * 10))

println(alexing_simp(sulzmann, "a" * 10))

for (i <- 1 to 4001 by 500) {

  println(i + ": " + "%.5f".format(time_needed(1, alexing_simp(sulzmann, "a" * i))))

  println(i + ": " + "%.5f".format(time_needed(1, alexing_simp(sulzmann, "ab" * i))))

}

// some automatic testing

def clear() = {

  print("")

  //print("\33[H\33[2J")

}

// enumerates regular expressions until a certain depth

def enum(n: Int, s: String) : Stream[Rexp] = n match {

  case 0 => ZERO #:: ONE #:: s.toStream.map(CHAR)

  case n => {  

    val rs = enum(n - 1, s)

    rs #:::

    (for (r1 <- rs; r2 <- rs) yield ALT(r1, r2)) #:::

    (for (r1 <- rs; r2 <- rs) yield SEQ(r1, r2)) #:::

    (for (r1 <- rs) yield STAR(r1))

  }

}

//enum(2, "ab").size

//enum(3, "ab").size

//enum(3, "abc").size

//enum(4, "ab").size

import scala.util.Try

def test_mkeps(r: Rexp) = {

  val res1 = Try(Some(mkeps(r))).getOrElse(None)

  val res2 = Try(Some(decode(r, mkepsBC(internalise(r))))).getOrElse(None) 

  if (res1 != res2) println(s"Mkeps disagrees on ${r}")

  if (res1 != res2) Some(r) else (None)

}

println("Testing mkeps")

enum(2, "ab").map(test_mkeps).toSet

//enum(3, "ab").map(test_mkeps).toSet

//enum(3, "abc").map(test_mkeps).toSet

//enumerates strings of length n over alphabet cs

def strs(n: Int, cs: String) : Set[String] = {

  if (n == 0) Set("")

  else {

    val ss = strs(n - 1, cs)

    ss ++

    (for (s <- ss; c <- cs.toList) yield c + s)

  }

}

//tests lexing and lexingB

def tests_inj(ss: Set[String])(r: Rexp) = {

  clear()

  println(s"Testing ${r}")

  for (s <- ss.par) yield {

    val res1 = Try(Some(alexing(r, s))).getOrElse(None)

    val res2 = Try(Some(alexing_simp(r, s))).getOrElse(None)

    if (res1 != res2) println(s"Disagree on ${r} and ${s}")

    if (res1 != res2) println(s"   ${res1} !=  ${res2}")

    if (res1 != res2) Some((r, s)) else None

  }

//println("Testing lexing 1")

//enum(2, "ab").map(tests_inj(strs(2, "ab"))).toSet

//println("Testing lexing 2")

//enum(2, "ab").map(tests_inj(strs(3, "abc"))).toSet

//println("Testing lexing 3")

//enum(3, "ab").map(tests_inj(strs(3, "abc"))).toSet

def tests_alexer(ss: Set[String])(r: Rexp) = {

  clear()

  println(s"Testing ${r}")

  for (s <- ss.par) yield {

    val d = der('b', r)

    val ad = ader('b', internalise(r))

    val res1 = Try(Some(encode(inj(r, 'a', alexing(d, s))))).getOrElse(None)

    val res2 = Try(Some(pre_alexing(ad, s))).getOrElse(None)

    if (res1 != res2) println(s"Disagree on ${r} and 'a'::${s}")

    if (res1 != res2) println(s"   ${res1} !=  ${res2}")

    if (res1 != res2) Some((r, s)) else None

  }

}

println("Testing alexing 1")

println(enum(2, "ab").map(tests_alexer(strs(2, "ab"))).toSet)

def values(r: Rexp) : Set[Val] = r match {

  case ZERO => Set()

  case ONE => Set(Empty)

  case CHAR(c) => Set(Chr(c))

  case ALT(r1, r2) => (for (v1 <- values(r1)) yield Left(v1)) ++ 

                      (for (v2 <- values(r2)) yield Right(v2))

  case SEQ(r1, r2) => for (v1 <- values(r1); v2 <- values(r2)) yield Sequ(v1, v2)

  case STAR(r) => (Set(Stars(Nil)) ++ 

                  (for (v <- values(r)) yield Stars(List(v)))) 

    // to do more would cause the set to be infinite

}

def tests_ader(c: Char)(r: Rexp) = {

  val d = der(c, r)

  val vals = values(d)

  for (v <- vals) {

    println(s"Testing ${r} and ${v}")

    val res1 = retrieve(ader(c, internalise(r)), v)

    val res2 = encode(inj(r, c, decode(d, retrieve(internalise(der(c, r)), v))))

    if (res1 != res2) println(s"Disagree on ${r}, ${v} and der = ${d}")

    if (res1 != res2) println(s"   ${res1} !=  ${res2}")

    if (res1 != res2) Some((r, v)) else None

  }

}

println("Testing ader/der")

println(enum(2, "ab").map(tests_ader('a')).toSet)

val er = SEQ(ONE,CHAR('a')) 

val ev = Right(Empty) 

val ed = ALT(SEQ(ZERO,CHAR('a')),ONE)

retrieve(internalise(ed), ev) // => [true]

internalise(er)

ader('a', internalise(er))

retrieve(ader('a', internalise(er)), ev) // => []

decode(ed, List(true)) // gives the value for derivative

decode(er, List())     // gives the value for original value

val dr = STAR(CHAR('a'))

val dr_der = SEQ(ONE,STAR(CHAR('a'))) // derivative of dr

val dr_val = Sequ(Empty,Stars(List())) // value of dr_def

val res1 = retrieve(internalise(der('a', dr)), dr_val) // => [true]

val res2 = retrieve(ader('a', internalise(dr)), dr_val) // => [false, true]

decode(dr_der, res1) // gives the value for derivative

decode(dr, res2)     // gives the value for original value

encode(inj(dr, 'a', decode(dr_der, res1)))