// CW 1

import scala.language.implicitConversions    

import scala.language.reflectiveCalls 

abstract class Rexp

case object ZERO extends Rexp                            // matches nothing

case object ONE extends Rexp                             // matches the empty string

case class CHAR(c: Char) extends Rexp                    // matches a character c

case class ALT(r1: Rexp, r2: Rexp) extends Rexp          // alternative

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

case class STAR(r: Rexp) extends Rexp                    // star

case class RANGE(cs: Set[Char]) extends Rexp             // set of characters

case class PLUS(r: Rexp) extends Rexp                    // plus

case class OPT(r: Rexp) extends Rexp                     // optional

case class NTIMES(r: Rexp, n: Int) extends Rexp          // n-times

case class UPNTIMES(r: Rexp, n: Int) extends Rexp        // up n-times

case class FROMNTIMES(r: Rexp, n: Int) extends Rexp      // from n-times

case class NMTIMES(r: Rexp, n: Int, m: Int) extends Rexp // between nm-times

case class NOT(r: Rexp) extends Rexp                     // not

case class CFUN(f: Char => Boolean) extends Rexp         // subsuming CHAR and RANGE

def CHAR(c: Char) = CFUN(d => c == d)

val ALL = CFUN(_ => true)

def RANGE(cs: Set[Char]) = CFUN(d => cs.contains(d))

def CHAR(c: Char) = CFUN(c == _)

val ALL = CFUN(_ => true)

def RANGE(cs: Set[Char]) = CFUN(cs.contains(_))

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

  case RANGE(_) => false

  case PLUS(r) => nullable(r)

  case OPT(_) => true

  case NTIMES(r, n) => if (n == 0) true else nullable(r)

  case UPNTIMES(_, _) => true

  case FROMNTIMES(r, n) => if (n == 0) true else nullable(r)

  case NMTIMES(r, n, m) => if (n == 0) true else nullable(r)

  case NOT(r) => !nullable(r)

  case CFUN(_) => false

}

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

  case RANGE(cs) => if (cs contains c) ONE else ZERO

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

  case OPT(r) => der(c, r)

  case NTIMES(r, n) => 

    if (n == 0) ZERO else SEQ(der(c, r), NTIMES(r, n - 1))

  case UPNTIMES(r, n) =>

    if (n == 0) ZERO else SEQ(der(c, r), UPNTIMES(r, n - 1))

  case FROMNTIMES(r, n) =>

    if (n == 0) SEQ(der(c, r), STAR(r)) else SEQ(der(c, r), FROMNTIMES(r, n - 1))

  case NMTIMES(r, n, m) =>

    if (m < n) ZERO else

    if (n == 0 && m == 0) ZERO else 

    if (n == 0) SEQ(der(c, r), UPNTIMES(r, m - 1)) 

    else SEQ(der(c, r), NMTIMES(r, n - 1, m - 1)) 

  case NOT(r) => NOT(der (c, r))

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

}

def simp(r: Rexp) : Rexp = r match {

  case ALT(r1, r2) => (simp(r1), simp(r2)) match {

    case (ZERO, r2s) => r2s

    case (r1s, ZERO) => r1s

    case (r1s, r2s) => if (r1s == r2s) r1s else ALT (r1s, r2s)

  }

  case SEQ(r1, r2) =>  (simp(r1), simp(r2)) match {

    case (ZERO, _) => ZERO

    case (_, ZERO) => ZERO

    case (ONE, r2s) => r2s

    case (r1s, ONE) => r1s

    case (r1s, r2s) => SEQ(r1s, r2s)

  }

  case r => 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))

}

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

  case Nil => r

  case c::s => ders_simp(s, simp(der(c, r)))

}

// main matcher function including simplification

def matcher(r: Rexp, s: String) : Boolean = 

  nullable(ders_simp(s.toList, r))

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

}

val r1 = NTIMES("a", 3)

val r2 = NTIMES(OPT("a"), 3)

val r3 = UPNTIMES("a", 3)

val r4 = UPNTIMES(OPT("a"), 3)

val r5 = NMTIMES("a", 3, 5)

val r6 = NMTIMES(OPT("a"), 3, 5)

val rs = List(r1, r2, r3, r4, r5, r6)

rs.map(matcher(_, ""))

rs.map(matcher(_, "a"))

rs.map(matcher(_, "aa"))

rs.map(matcher(_, "aaa"))

rs.map(matcher(_, "aaaa"))

rs.map(matcher(_, "aaaaa"))

rs.map(matcher(_, "aaaaaa"))

println("EMAIL:")

val LOWERCASE = ('a' to 'z').toSet

val DIGITS = ('0' to '9').toSet

val EMAIL = { PLUS(CFUN(LOWERCASE | DIGITS | ("_.-").toSet)) ~ "@" ~ 

              PLUS(CFUN(LOWERCASE | DIGITS | (".-").toSet)) ~ "." ~

              NMTIMES(CFUN(LOWERCASE | Set('.')), 2, 6) }

val my_email = "christian.urban@kcl.ac.uk"

println(EMAIL);

println(matcher(EMAIL, my_email))

println(ders_simp(my_email.toList, EMAIL))

println("COMMENTS:")

val ALL = CFUN((c:Char) => true)

val COMMENT = "/*" ~ (NOT(ALL.% ~ "*/" ~ ALL.%)) ~ "*/"

println(matcher(COMMENT, "/**/"))

println(matcher(COMMENT, "/*foobar*/"))

println(matcher(COMMENT, "/*test*/test*/"))

println(matcher(COMMENT, "/*test/*test*/"))

println("EVILS:")

val EVIL1 = PLUS(PLUS("a" ~ "a" ~ "a"))

val EVIL2 = PLUS(PLUS("aaaaaaaaaaaaaaaaaaa" ~ OPT("a")))  // 19 as ~ a?

//40 * aaa matches

//43 * aaa + aa does not

//45 * aaa + a

println("EVIL1:")

println(matcher(EVIL1, "aaa" * 40))

println(matcher(EVIL1, "aaa" * 43 + "aa"))

println(matcher(EVIL1, "aaa" * 45 + "a"))

println("EVIL2:")

println(matcher(EVIL2, "aaa" * 40))

println(matcher(EVIL2, "aaa" * 43 + "aa"))

println(matcher(EVIL2, "aaa" * 45 + "a"))

println("TEST for bug pointed out by Filips Ivanovs")

val test = NMTIMES(CFUN(LOWERCASE | Set('.')), 2, 6)

println(matcher(test,"a"))

println(matcher(test,"ab"))

println(matcher(test,"abcdef"))

println(matcher(test,"abc"))

println(matcher(test,"...."))

println(matcher(test,"asdfg"))

println(matcher(test,"abcdefg"))

println(test)

println(ders_simp("a".toList, test))

println(ders_simp("aa".toList, test))

println(ders_simp("aaa".toList, test))

println(ders_simp("aaaa".toList, test))

println(ders_simp("aaaaa".toList, test))

println(ders_simp("aaaaaa".toList, test))

println(ders_simp("aaaaaaa".toList, test))

def TEST(s: String, r: Rexp) = {

  println("Rexp |" + s + "|")

  println("Derivative:\n" + ders_simp(s.toList, r))

  println("Is Nullable: " + nullable(ders_simp(s.toList, r)))

  Console.readLine

}

val ALL2 = "a" | "f"

val COMMENT2 = ("/*" ~ NOT(ALL2.% ~ "*/" ~ ALL2.%) ~ "*/")

println("1) TEST TEST")

TEST("", COMMENT2)

TEST("/", COMMENT2)

TEST("/*", COMMENT2)

TEST("/*f", COMMENT2)

TEST("/*f*", COMMENT2)

TEST("/*f*/", COMMENT2)

TEST("/*f*/ ", COMMENT2)

val ALL3 = "a" | "f"

val COMMENT3 = ("/" ~ NOT(ALL3.% ~ "&" ~ ALL3.%) ~ "&")

println("2) TEST TEST")

TEST("", COMMENT3)

TEST("/", COMMENT3)

TEST("/", COMMENT3)

TEST("/f", COMMENT3)

TEST("/f&", COMMENT3)

TEST("/f& ", COMMENT3)

//test: ("a" | "aa") ~ ("a" | "aa")*

val auxEVIL3 = ALT(CHAR('a'), SEQ(CHAR('a'), CHAR('a')))

val EVIL3 = SEQ(auxEVIL3, STAR(auxEVIL3))

val EVIL3p = FROMNTIMES(auxEVIL3, 1)

for (i <- 1 to 100 by 1) {

  println(i + " " + "%.5f".format(time_needed(2, matcher(EVIL3, "a" * i))) + " size: " + 

	  size(ders(("a" * i).toList, EVIL3)))

}

val t1 = EVIL3

val t2 = simp(der('a', t1))

val t3 = simp(der('a', t2))

val t4 = simp(der('a', t3))

val t1 = EVIL3p

val t2 = simp(der('a', t1))

val t3 = simp(der('a', t2))

val t4 = simp(der('a', t3))