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 NTIMES(r: Rexp, n: Int): Rexp = n match {

    case 0 => EMPTY

    case 1 => r

    case n => SEQ(r, NTIMES(r, n - 1))

  }

  */

  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

}