package Handouts

import io.Source
import scala.util.matching.Regex
import scala.util._

object Handout2 {
  abstract class Rexp
  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
  case class SEQ(r1: Rexp, r2: Rexp) extends Rexp
  case class STAR(r: Rexp) extends Rexp
  case class NTIMES(r: Rexp, n: Int) extends Rexp

  def OPT(r: Rexp) = ALT(r, EMPTY)                //> OPT: (r: Handouts.Handout2.Rexp)Handouts.Handout2.ALT

  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 NTIMES(r, i) => if (i == 0) true else nullable(r)
  }                                               //> nullable: (r: Handouts.Handout2.Rexp)Boolean

  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 NTIMES(r, i) =>
      if (i == 0) NULL else SEQ(der(c, r), NTIMES(r, i - 1))
  }                                               //> der: (c: Char, r: Handouts.Handout2.Rexp)Handouts.Handout2.Rexp

  def _ders(s: List[Char], r: Rexp): Rexp = s match {
    case Nil => r
    case c :: s => ders(s, der(c, r))
  }                                               //> _ders: (s: List[Char], r: Handouts.Handout2.Rexp)Handouts.Handout2.Rexp

  def ders(s: List[Char], r: Rexp): Rexp = s match {
    case Nil => r
    case c :: s => ders(s, simp(der(c, r)))
  }                                               //> ders: (s: List[Char], r: Handouts.Handout2.Rexp)Handouts.Handout2.Rexp

  def matches(r: Rexp, s: String): Boolean =
    nullable(ders(s.toList, r))                   //> matches: (r: Handouts.Handout2.Rexp, s: String)Boolean

  def simp(r: Rexp): Rexp = r match {
    case ALT(r1, r2) => {
      val r1s = simp(r1)
      val r2s = simp(r2)
      (r1s, r2s) match {
        case (NULL, _) => r2s
        case (_, NULL) => r1s
        case _ => if (r1s == r2s) r1s else ALT(r1s, r2s)
      }
    }
    case SEQ(r1, r2) => {
      val r1s = simp(r1)
      val r2s = simp(r2)
      (r1s, r2s) match {
        case (NULL, _) => NULL
        case (_, NULL) => NULL
        case (EMPTY, _) => r2s
        case (_, EMPTY) => r1s
        case _ => SEQ(r1s, r2s)
      }
    }
    case NTIMES(r, n) => NTIMES(simp(r), n)
    case r => r
  }                                               //> simp: (r: Handouts.Handout2.Rexp)Handouts.Handout2.Rexp

  /************************************************************************************************************************************/
  // der test
  // r = {(a.b) + b}*
  val r = STAR(ALT(SEQ(CHAR('a'), CHAR('b')), CHAR('b')))
                                                  //> r  : Handouts.Handout2.STAR = STAR(ALT(SEQ(CHAR(a),CHAR(b)),CHAR(b)))

  // => [{(_.b) + null} . {(a.b)+b}*]
  der('a', r)                                     //> res0: Handouts.Handout2.Rexp = SEQ(ALT(SEQ(EMPTY,CHAR(b)),NULL),STAR(ALT(SE
                                                  //| Q(CHAR(a),CHAR(b)),CHAR(b))))
  // => [{(null.b) + _} . {(a.b)+b}*]
  der('b', r)                                     //> res1: Handouts.Handout2.Rexp = SEQ(ALT(SEQ(NULL,CHAR(b)),EMPTY),STAR(ALT(SE
                                                  //| Q(CHAR(a),CHAR(b)),CHAR(b))))
  // => [{(null.b) + _} . {(a.b)+b}*]
  der('c', r)                                     //> res2: Handouts.Handout2.Rexp = SEQ(ALT(SEQ(NULL,CHAR(b)),NULL),STAR(ALT(SEQ
                                                  //| (CHAR(a),CHAR(b)),CHAR(b))))

  val r2 = ALT(SEQ(CHAR('a'), CHAR('b')), CHAR('b'))
                                                  //> r2  : Handouts.Handout2.ALT = ALT(SEQ(CHAR(a),CHAR(b)),CHAR(b))
  der('a', r2)                                    //> res3: Handouts.Handout2.Rexp = ALT(SEQ(EMPTY,CHAR(b)),NULL)

  val r3 = SEQ(CHAR('a'), CHAR('b'))              //> r3  : Handouts.Handout2.SEQ = SEQ(CHAR(a),CHAR(b))
  der('a', r3)                                    //> res4: Handouts.Handout2.Rexp = SEQ(EMPTY,CHAR(b))

  val r4 = CHAR('a')                              //> r4  : Handouts.Handout2.CHAR = CHAR(a)
  der('a', r4)                                    //> res5: Handouts.Handout2.Rexp = EMPTY

  nullable(r)                                     //> res6: Boolean = true
  nullable(r2)                                    //> res7: Boolean = false
  nullable(r3)                                    //> res8: Boolean = false
  nullable(r4)                                    //> res9: Boolean = false
}