// Thompson Construction
//=======================

import $file.dfa, dfa._ 
import $file.nfa, nfa._
import $file.enfa, enfa._


// states for Thompson construction
case class TState(i: Int) extends State

object TState {
  var counter = 0
  
  def apply() : TState = {
    counter += 1;
    new TState(counter)
  }
}


// some types abbreviations
type NFAt = NFA[TState, Char]
type NFAtrans = (TState, Char) :=> Set[TState]
type eNFAtrans = (TState, Option[Char]) :=> Set[TState]

 
// NFA that does not accept any string
def NFA_ZERO(): NFAt = {
  val Q = TState()
  NFA(Set(Q), { case _ => Set() }, Set())
}

// NFA that accepts the empty string
def NFA_ONE() : NFAt = {
  val Q = TState()
  NFA(Set(Q), { case _ => Set() }, Set(Q))
}

// NFA that accepts the string "c"
def NFA_CHAR(c: Char) : NFAt = {
  val Q1 = TState()
  val Q2 = TState()
  NFA(Set(Q1), { case (Q1, d) if (c == d) => Set(Q2) }, Set(Q2))
}


// for composing an eNFA transition with an NFA transition
// | is for set union
implicit def nfaOps(f: eNFAtrans) = new {
  def +++(g: NFAtrans) : eNFAtrans = 
  { case (q, None) =>  applyOrElse(f, (q, None)) 
    case (q, Some(c)) => applyOrElse(f, (q, Some(c))) | applyOrElse(g, (q, c))  }
}


// sequence of two NFAs
def NFA_SEQ(nfa1: NFAt, nfa2: NFAt) : NFAt = {
  val new_delta : eNFAtrans = 
    { case (q, None) if nfa1.fins(q) => nfa2.starts }
  
  eNFA(nfa1.starts, 
       new_delta +++ nfa1.delta +++ nfa2.delta, 
       nfa2.fins)
}

// alternative of two NFAs
def NFA_ALT(nfa1: NFAt, nfa2: NFAt) : NFAt = {
  val new_delta : NFAtrans = { 
    case (q, c) =>  applyOrElse(nfa1.delta, (q, c)) | 
                    applyOrElse(nfa2.delta, (q, c)) }
  val new_fins = (q: TState) => nfa1.fins(q) || nfa2.fins(q)

  NFA(nfa1.starts | nfa2.starts, new_delta, new_fins)
}

// star of a NFA
def NFA_STAR(nfa: NFAt) : NFAt = {
  val Q = TState()
  val new_delta : eNFAtrans = 
    { case (Q, None) => nfa.starts
      case (q, None) if nfa.fins(q) => Set(Q) }

  eNFA(Set(Q), new_delta +++ nfa.delta, Set(Q))
}


// We are now ready to translate regular expressions
// into DFAs (via eNFAs and NFAs, and the subset construction)

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

// thompson construction 
def thompson (r: Rexp) : NFAt = r match {
  case ZERO => NFA_ZERO()
  case ONE => NFA_ONE()
  case CHAR(c) => NFA_CHAR(c)  
  case ALT(r1, r2) => NFA_ALT(thompson(r1), thompson(r2))
  case SEQ(r1, r2) => NFA_SEQ(thompson(r1), thompson(r2))
  case STAR(r1) => NFA_STAR(thompson(r1))
}

//optional regular expression (one or zero times)
def OPT(r: Rexp) = ALT(r, ONE)

//n-times regular expression (explicitly expanded)
def NTIMES(r: Rexp, n: Int) : Rexp = n match {
  case 0 => ONE
  case 1 => r
  case n => SEQ(r, NTIMES(r, n - 1))
}


def tmatches_nfa(r: Rexp, s: String) : Boolean =
  thompson(r).accepts(s.toList)

def tmatches_nfa2(r: Rexp, s: String) : Boolean =
  thompson(r).accepts2(s.toList)

// dfas via subset construction
def tmatches_dfa(r: Rexp, s: String) : Boolean =
  subset(thompson(r)).accepts(s.toList)

// Test Cases
//============

// the evil regular expression  a?{n} a{n}
def EVIL1(n: Int) : Rexp = SEQ(NTIMES(OPT(CHAR('a')), n), NTIMES(CHAR('a'), n))

// the evil regular expression (a*)*b
val EVIL2 : Rexp = SEQ(STAR(STAR(CHAR('a'))), CHAR('b'))

//for measuring time
def time_needed[T](i: Int, code: => T) = {
  val start = System.nanoTime()
  for (j <- 1 to i) code
  val end = System.nanoTime()
  (end - start)/(i * 1.0e9)
}

// the size of the NFA can be large, 
// thus slowing down the breadth-first search
println("Breadth-first search EVIL1 / EVIL2")

for (i <- 1 to 13) {
  println(i + ": " + "%.5f".format(time_needed(2, tmatches_nfa(EVIL1(i), "a" * i))))
}

for (i <- 1 to 100 by 5) {
  println(i + " " + "%.5f".format(time_needed(2, tmatches_nfa(EVIL2, "a" * i))))
}


// the backtracking that is needed in depth-first 
// search can be painfully slow
println("Depth-first search EVIL1 / EVIL2")

for (i <- 1 to 9) {
  println(i + " " + "%.5f".format(time_needed(2, tmatches_nfa2(EVIL1(i), "a" * i))))
}

for (i <- 1 to 7) {
  println(i + " " + "%.5f".format(time_needed(2, tmatches_nfa2(EVIL2, "a" * i))))
}



// while my thompson->enfa->subset->partial-function-chain
// is probably not the most effcient way to obtain a fast DFA 
// (the test below should be much faster with a more direct 
// construction), in general the DFAs can be slow because of 
// the state explosion in the subset construction

for (i <- 1 to 7) {
  println(i + ": " + "%.5f".format(time_needed(2, tmatches_dfa(EVIL1(i), "a" * i))))
}

for (i <- 1 to 100 by 5) {
  println(i + " " + "%.5f".format(time_needed(2, tmatches_dfa(EVIL2, "a" * i))))
}