import RexpRelated._
import RexpRelated.Rexp._
import Spiral._
object Partial{
  def dot_prod(rs: Set[Rexp], r: Rexp): Set[Rexp] = r match {
    case ZERO => Set()
    case ONE => rs
    case r => rs.map((re) => if (re == ONE) r else SEQ(re, r)  )   
  }
  def cir_prod(l: Lin, t: Rexp): Lin = t match {//remember this Lin is different from the Lin in Antimirov's paper. Here it does not mean the set of all subsets of linear forms that does not contain zero, but rather the type a set of linear forms
    case ZERO => Set()
    case ONE => l
    case t => l.map( m => m._2 match {case ZERO => m case ONE => (m._1, t) case p => (m._1, SEQ(p, t)) }  )
  }
  def lf(r: Rexp): Lin = r match {
    case ZERO => Set()
    case ONE => Set()
    case CHAR(f) => {
      //val Some(c) = alphabet.find(f) 
      Set((f, ONE))
    }
    case ALTS(rs) => {
      rs.foldLeft(Set[Mon]())((acc, r) => acc ++ lf(r))
    }
    case STAR(r1) => cir_prod(lf(r1), STAR(r1)) //may try infix notation later......
    case SEQ(r1, r2) =>{
      if (nullable(r1))
        cir_prod(lf(r1), r2) ++ lf(r2)
      else
        cir_prod(lf(r1), r2) 
    }
  }
  def lfs(r: Set[Rexp]): Lin = {
    r.foldLeft(Set[Mon]())((acc, r) => acc ++ lf(r))
  }

  def pder(x: Char, t: Rexp): Set[Rexp] = {
    val lft = lf(t)
    (lft.filter(mon => if(mon._1 == x) true else false)).map(mon => mon._2)
  }
  def pders_single(s: List[Char], t: Rexp) : Set[Rexp] = s match {
    case x::xs => pders(xs, pder(x, t))
    case Nil => Set(t)
  }
  def pders(s: List[Char], ts: Set[Rexp]) : Set[Rexp] = s match {
    case x::xs => pders(xs, ts.foldLeft(Set[Rexp]())((acc, t) => acc ++ pder(x, t)))
    case Nil => ts 
  }
  def pderss(ss: List[List[Char]], t: Rexp): Set[Rexp] = ss.foldLeft( Set[Rexp]() )( (acc, s) => pders_single(s, t) ++ acc )
  def pdera(t: Rexp): Set[Rexp] = lf(t).map(mon => mon._2)
  //all implementation of partial derivatives that involve set union are potentially buggy
  //because they don't include the original regular term before they are pdered.
  //now only pderas is fixed.
  def pderas(t: Set[Rexp], d: Int): Set[Rexp] = if(d > 0) pderas(lfs(t).map(mon => mon._2), d - 1) ++ t else lfs(t).map(mon => mon._2) ++ t//repeated application of pderas over the newest set of pders.
  
  def sigma_lf(l: Set[Mon]) : Rexp = ALTS(l.map(mon => SEQ(CHAR(mon._1),mon._2)).toList)
  def sigma(rs: Set[Rexp]) : Rexp = ALTS(rs.toList)
  def o(r: Rexp) = if (nullable(r)) ONE else ZERO
  def nlf(t: Rexp) : Rexp = ALTS(List( o(t), sigma_lf(lf(t)) ))
  def pdp(x: Char, r: Rexp) : Set[Rexp] = r match {
    case ZERO => Set[Rexp]()
    case ONE => Set[Rexp]()
    case CHAR(f) => if(x == f) Set(ONE) else Set[Rexp]()
    case ALTS(rs) => rs.foldLeft(Set[Rexp]())((acc, r) => acc ++ pdp(x, r))
    case STAR(r1) => pdp(x, r).map(a => SEQ(a, STAR(r1)))
    case SEQ(a0, b) => if(nullable(a0)) pdp(x, a0).map(a => SEQ(a, b)) ++ pdp(x, b) else pdp(x, a0).map(a => SEQ(a, b))
  }
  def pdps(s: List[Char], ts: Set[Rexp]): Set[Rexp] = s match {
    case x::xs => pdps(xs, ts.foldLeft(Set[Rexp]())((acc, t) => acc ++ pder(x, t)))
    case Nil => ts   
  }
  def pdpss(ss: List[List[Char]], t: Rexp): Set[Rexp] = ss.foldLeft( Set[Rexp]())((acc, s) => pdps(s, Set(t)) ++ acc)

  //this function currently  the problem of counting the same char as different ones 
  //because they are defined as "pred"
  def subterms(r: Rexp): Set[Rexp] = {//excluding zeros.
    r match {
      case ZERO => {
        Set[Rexp]()
      }
      case SEQ(r1, r2) => {
        Set(r1, r2) ++ subterms(r1) ++ subterms(r2)
      }
      case ALTS(rs) => {
        rs.toSet ++ rs.foldLeft(Set[Rexp]())((acc, r) => acc ++ subterms(r))
      }
      case STAR(r) => {
        Set(r) ++ subterms(r)
      }
      case r => Set(r)
    }
  }
  def comp(s: List[Char], t: Rexp) = {
    //var r = internalise(t)
    //var setr = Set(t)
    
    /*for(i <- 0 to s.length - 1){
      val mamaipi = bsimp(bder(s(i), r))
      val mamaimapi = pdps(List(s(i)), setr)
      //compare dersimp and pder w.r.t each character in string s
      println("current string: " + s.slice(0,i + 1))
      println("der+simp: ")
      println(aregx_tree(mamaipi))
      println("pder: ")
      mamaimapi.foreach(m => println(regx_tree(m)))
      r = mamaipi
      setr = mamaimapi 
    }*/
    for(i <- 1 to 10)
      println(pderas(Set(t), i).size, i)
    //val alphabet_star_t = pderas(Set(t), 10)
    //println("all possible elements in pder (probably...): ")
    //alphabet_star_t.foreach(r => println(regx_tree(r)))
  }
}
/*    val delta = lfs(t).map(mon => mon._2)                
    if(delta.size == t.size)
    {
      println(delta.size)
      println("steady: "+delta.size)
      return delta
    }
      
    else
    {
      val a = pderas(delta)
      println("increment: "+delta.size+a.size)
      return a
    }*/