import scala.language.implicitConversions    
import scala.language.reflectiveCalls 

abstract class Rexp {
  def simp : Rexp = this
}

case object NULL extends Rexp
case object EMPTY extends Rexp
case class CHAR(c: Char) extends Rexp
case class ALT(r1: Rexp, r2: Rexp) extends Rexp {
  override def toString = r1.toString + " | " + r2.toString
  override def simp = (r1.simp, r2.simp) match {
    case (NULL, r) => r
    case (r, NULL) => r
    case (r, EMPTY) => if (nullable(r)) r else ALT(r, EMPTY)
    case (EMPTY, r) => if (nullable(r)) r else ALT(r, EMPTY)
    case (r1, r2) => if (r1 == r2) r1 else ALT(r1, r2)
  }
}
case class RANGE(cs: List[Char]) extends Rexp {
  //override def toString = cs.mkString("[",",","]")
  override def toString = "[" + cs.head + " .. " + cs.last + "]"
}
object RANGE {
  def apply(s: String) : RANGE = RANGE(s.toList)
}
case class SEQ(r1: Rexp, r2: Rexp) extends Rexp {
  override def toString = r1.toString + " ~ " + r2.toString
  override def simp = (r1.simp, r2.simp) match {
    case (NULL, _) => NULL
    case (_, NULL) => NULL
    case (EMPTY, r) => r
    case (r, EMPTY) => r
    case (r1, r2) => SEQ(r1, r2)
  }
}
case class PLUS(r: Rexp) extends Rexp {
  override def simp = r.simp match {
    case NULL => EMPTY
    case EMPTY => EMPTY
    case r => PLUS(r)
  }
}
case class STAR(r: Rexp) extends Rexp {
  override def simp = r.simp match {
    case NULL => EMPTY
    case EMPTY => EMPTY
    case r => STAR(r)
  }
}
case class NTIMES(r: Rexp, n: Int) extends Rexp {
  override def simp = if (n == 0) EMPTY else 
    r.simp match {
      case NULL => NULL
      case EMPTY => EMPTY
      case r => NTIMES(r, n)
    }
}
case class NUPTOM(r: Rexp, n: Int, m: Int) extends Rexp {
  override def simp = if (m == 0) EMPTY else 
    r.simp match {
      case NULL => NULL
      case EMPTY => EMPTY
      case r => NUPTOM(r, n, m)
    }
}
def NMTIMES(r: Rexp, n: Int, m: Int) = {
  if(m < n) throw new IllegalArgumentException("the number m cannot be smaller than n.")
  else NUPTOM(r, n, m - n)
}


case class NOT(r: Rexp) extends Rexp {
  override def simp = NOT(r.simp)
}
case class OPT(r: Rexp) extends Rexp {
  override def simp = OPT(r.simp)
}

// nullable function: tests whether the regular 
// expression can recognise the empty string
def nullable (r: Rexp) : Boolean = r match {
  case NULL => false
  case EMPTY => true
  case CHAR(_) => false
  case ALT(r1, r2) => nullable(r1) || nullable(r2)
  case SEQ(r1, r2) => nullable(r1) && nullable(r2)
  case STAR(_) => true
  case PLUS(r) => nullable(r)
  case NTIMES(r, i) => if (i == 0) true else nullable(r)
  case NUPTOM(r, i, j) => if (i == 0) true else nullable(r)
  case RANGE(_) => false
  case NOT(r) => !(nullable(r))
  case OPT(_) => true
}

def zeroable (r: Rexp) : Boolean = r match {
  case NULL => true
  case EMPTY => false
  case CHAR(_) => false
  case ALT(r1, r2) => zeroable(r1) && zeroable(r2)
  case SEQ(r1, r2) => zeroable(r1) || zeroable(r2)
  case STAR(_) => false
  case PLUS(r) => zeroable(r)
  case NTIMES(r, i) => if (i == 0) false else zeroable(r)
  case NUPTOM(r, i, j) => if (i == 0) false else zeroable(r)
  case RANGE(_) => false
  case NOT(r) => !(zeroable(r))
  case OPT(_) => false
}

// derivative of a regular expression w.r.t. a character
def der (c: Char, r: Rexp) : Rexp = r match {
  case NULL => NULL
  case EMPTY => NULL
  case CHAR(d) => if (c == d) EMPTY else NULL
  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 PLUS(r) => SEQ(der(c, r), STAR(r))
  case NTIMES(r, i) => 
    if (i == 0) NULL else der(c, SEQ(r, NTIMES(r, i - 1)))
  case NUPTOM(r, i, j) =>
    if (i == 0 && j == 0) NULL else 
    if (i == 0) ALT(der(c, NTIMES(r, j)), der(c, NUPTOM(r, 0, j - 1)))
    else der(c, SEQ(r, NUPTOM(r, i - 1, j)))
  case RANGE(cs) => if (cs contains c) EMPTY else NULL
  case NOT(r) => NOT(der (c, r))
  case OPT(r) => der(c, 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, der(c, r).simp)
}

// main matcher function
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 => EMPTY
  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)
}

println("EMAIL:")
val LOWERCASE = "abcdefghijklmnopqrstuvwxyz"
val DIGITS = "0123456789"
val EMAIL = PLUS(RANGE(LOWERCASE + DIGITS + "_" + "." + "-")) ~ "@" ~ 
            PLUS(RANGE(LOWERCASE + DIGITS + "." + "-")) ~ "." ~
            NMTIMES(RANGE(LOWERCASE + "."), 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 = RANGE(LOWERCASE + " ")
val COMMENT = "/*" ~ (NOT(ALL.% ~ "*/" ~ ALL.%)) ~ "*/"

println(matcher(COMMENT, "/**/"))
println(matcher(COMMENT, "/*foobar_comment*/"))
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(RANGE(LOWERCASE + "."), 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)))
  println("Is Zeroable: " + zeroable(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)