// package zre 

//Zre5: eliminated mems table

import scala.collection.mutable.{Map => MMap}

import scala.collection.mutable.{ArrayBuffer => MList}

//import pprint._

import scala.util.Try

import pprint._

abstract class Val

case object Empty extends Val

case class Chr(c: Char) extends Val

case class Sequ(v1: Val, v2: Val) extends Val

case class Left(v: Val) extends Val

case class Right(v: Val) extends Val

case class Stars(vs: List[Val]) extends Val

case object DummyFilling extends Val

// abstract class Rexp {

//      def equals(other: Rexp) : Boolean = this.eq(other)

// }

abstract class Rexp

case object ZERO extends Rexp                    // matches nothing

case object ONE extends Rexp                     // matches an 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 AL1(r1: Rexp) extends Rexp

case class SEQ(r1: Rexp, r2: Rexp) extends Rexp  // sequence

case class STAR(r: Rexp) extends Rexp

case object RTOP extends Rexp

//Seq a b --> Seq Seqa Seqb

//Seq a b --> Sequ chra chrb

//ALT r1 r2 --> mALT

//         AltC L   AltC R

var cyclicPreventionList : Set[Int]= Set()

abstract class Ctx   

case object RootC extends Ctx

case class SeqC( mForMyself:  Mem, processedSibling: List[Val], unpSibling: List[Rexp]) extends Ctx

case class AltC( mForMyself:  Mem, wrapper: Val => Val) extends Ctx

case class StarC(mForMyself:  Mem, vs: List[Val], inside: Rexp) extends Ctx

case class Mem(var parents: List[Ctx], var result : MList[(Int, Val)])

//AltC(Mem(RootC::Nil, Map()))

type Zipper = (Val, Mem)

var mems : MMap[(Int, Rexp), Mem] = MMap()

        //start pos, original regex --> result entry

var pos : Int = 0

//input ..................

//          ^       ^

//          p       q

//          r

//parse r[p...q] --> v

//(a+aa)*

//aaa

//[R(Sequ(a, a)), vs]

//[L(a), L(a), vs]

def check_before_down(c: Ctx, r: Rexp, d: Int = 0) : List[Zipper] = {

    mems.get((pos, r)) match {

        case Some(m) => 

            m.parents = c::m.parents//:::List(c)

            m.result.find(tup2 => tup2._1 == pos) match {

                // case Some((i, v)) => 

                //   original_up(v, c, d)

                case None => 

                  List()

            }

        case None => 

            val m = Mem(c::Nil, MList.empty[(Int, Val)])

            mems = mems + ((pos, r) -> m)

            original_down(r, m, d)

    }

    // val m = Mem(c::Nil, MList.empty[(Int, Val)])

    // original_down(r, m, d)

}

//mems  pstart r  --> m parents [(pend, vres), ...]

//aaa

//012

//seq a a 

//0 a~a --> m ... [(2, Sequ a a)]

        // c match {

        //     case StarC(mst, vst, rst) => print(s"StarC $vst\t")

        //     case SeqC(mse, pr, unp) => print(s"SeqC $unp\t")

        //     case AltC(mal, w) => print(s"AltC ${w(Empty)}\t")

        //     case RootC => print("Root")

        // }

def reorderCtx(cs: List[Ctx]): List[Ctx] = {

    Nil

}

def mem_up(vres: Val, m: Mem, rec_depth : Int = 0) : List[Zipper] = {

    m.result += (pos -> vres)

    //m.parents = m.parents.reverse

    // if(m.parents.size > 1){//println()

    //     println()  

    //     println("each of the contexts")

    //     m.parents.reverse.foreach (c =>

    //         println(simpleCtxDisplay(c))

    //     )

    //     println("after distinctCtx")

    //     distinctCtx(m.parents.reverse).foreach(c =>

    //         println(simpleCtxDisplay(c))

    //     )

    //     //println(s"vs is $vss")

    // }

    //.distinctBy(zipBackToRegex(_))

    (m.parents).distinctBy(zipBackToRegex(_)).flatMap((c: Ctx) =>

        original_up(vres, c, rec_depth)

    )    

    // m.parents.reverse.flatMap((c: Ctx) =>

    //     original_up(vres, c, rec_depth)

    // )

    // original_up(vres, m.parents.last, rec_depth)

}

def original_down(r: Rexp, m: Mem, d: Int = 0) : List[Zipper] = (r, m) match {

    case (CHAR(b), m) => {

        if (input(pos) == b) {

            List((Chr(b), m)) 

        }

        else 

            Nil

    }

    case (ONE, m) => Nil//mem_up(Empty, m, d + 1)

    case (SEQ(r1, r2), m) =>  

        // if(nullable(r1)){

        //     val mprime = Mem(AltC(m, x => x )::Nil, MList.empty[(Int, Val)])

        //     check_before_down(SeqC(mprime, Nil, List(r2)), r1, d) :::

        //     check_before_down(SeqC(mprime, mkeps(r1)::Nil, Nil), r2, d)

        // }

        // else

            check_before_down(SeqC(m, Nil, List(r2)), r1, d)

    case (ALT(r1, r2), m) => 

        check_before_down(AltC(m, Left(_)), r1, d) ::: 

        check_before_down(AltC(m, Right(_)), r2, d)

    case (STAR(r0), m) =>

        check_before_down(StarC(m, Nil, r0), r0, d) :::

        mem_up(Stars(Nil), m, d + 1)

    case (_, _) => throw new Exception("original down unexpected r or m")

}

def original_up(v: Val, c: Ctx, d: Int = 0) : List[Zipper] = 

{

(v, c) match {

    case (v, SeqC(m, v1::Nil, Nil)) => 

        mem_up(Sequ(v1, v), m, d + 1)

    case (v, SeqC(m, vs, u1::Nil)) => 

        check_before_down(SeqC(m, v::vs, Nil), u1, d)

    case (v, AltC(m, wrap)) => m.result.find(tup2 => tup2._1 == pos) match {

        case Some( (i, vPrime)  ) => 

            m.result += (i -> wrap(v))

            Nil

        case None => 

            mem_up(wrap(v), m, d + 1)

    } //mem_up(AL1(v), par)

    //case (v, StarC(m, vs, r0)) => throw new Exception("why not hit starC")

    case (v, RootC) => 

        Nil

    case (v, StarC(m, vs, r0) ) => //mem_up(Stars(v::vs), m, d + 1) //::: 

        check_before_down(StarC(m, v::vs, r0), r0, d) :::

        mem_up(Stars((v::vs).reverse), m, d + 1)

    case (_, _) => throw new Exception("hit unexpected context")

}

}

def derive(p: Int, z: Zipper) : List[Zipper] = {

    pos = p

    //println(s"z's actual size is ${actualZipperSize(z::Nil)}")

    z match {

        case (v, m) => 

            mem_up(v, m)

        case _ => throw new Exception("error")

    }

}

//let e' = Seq([]) in 

//

def init_zipper(r: Rexp) : Zipper = {

    val m_top = Mem(RootC::Nil, MList.empty[(Int, Val)])

    val c_top = SeqC(m_top, Nil, r::Nil)

    val m_r = Mem(c_top::Nil, MList.empty[(Int, Val)])

    println(s"initial zipper is (Empty, $m_r)")

    (Empty, m_r)//TODO: which val should we start with? Maybe Empty, maybe doesn't matter

    // val dummyRexp = ONE

    // val dummyMem = Mem()

}

def plug_convert(v: Val, c: Ctx) : List[Val] = 

{

c match {

    case RootC => List(v)

    //TODO: non-binary Seq requires ps.rev

    case SeqC(m, ps::Nil, Nil) => 

        plug_mem(Sequ(ps, v), m)

    //TODO: un not nullable--partial values?

    case SeqC(m, Nil, un::Nil) => 

        if(nullable(un))

            plug_mem(Sequ(v, mkeps(un)), m)

        else

            Nil

    //TODO: when multiple results stored in m, which one to choose?

    case AltC(m, wrap) => 

        plug_mem(wrap(v), m)

    case StarC(m, vs, r0) => plug_mem(Stars((v::vs).reverse), m)

}

}

var cnt = 0;

def plug_mem(v: Val, m: Mem) : List[Val] = {

    m.result += (pos -> v)

    m.parents.flatMap({c =>

        plug_convert(v, c)

    }

    )

}

def plug_all(zs: List[Zipper]) : List[Val] = {

    zs.flatMap(z => plug_mem(z._1, z._2))

}

def mkeps(r: Rexp) : Val = r match {

  case ONE => Empty

  case ALT(r1, r2) => 

    if (nullable(r1)) Left(mkeps(r1)) else Right(mkeps(r2))

  case SEQ(r1, r2) => Sequ(mkeps(r1), mkeps(r2))

  case _ => DummyFilling

}

def nullable(r: Rexp) : Boolean = r match {

  case ZERO => false

  case ONE => true

  case CHAR(_) => false

  case ALT(r1, r2) => nullable(r1) || nullable(r2)

  case SEQ(r1, r2) => nullable(r1) && nullable(r2)

  case _ => false

}

val tokList : List[Char] = "aab".toList

var input : List[Char] = tokList

def lexRecurse(zs: List[Zipper], index: Int) : List[Zipper] = {

    if(index <  input.length )

        lexRecurse(zs.flatMap(z => derive(index, z) ), index + 1)

    else 

        zs

}

def lex(r: Rexp, s: String) : List[Zipper] = {

    input = s.toList

    lexRecurse(init_zipper(r)::Nil,  0)

}

implicit def charlist2rexp(s: List[Char]): Rexp = s match {

    case Nil => ONE

    case c::Nil => CHAR(c)

    case c::cs => SEQ(CHAR(c), charlist2rexp(cs))

}

implicit def string2Rexp(s: String) : Rexp = charlist2rexp(s.toList)

implicit def RexpOps(r: Rexp) = new {

    def | (s: Rexp) = ALT(r, s)

    def ~ (s: Rexp) = SEQ(r, s)

    def % = STAR(r)

}

implicit def stringOps(s: String) = new {

    def | (r: Rexp) = ALT(s, r)

    def | (r: String) = ALT(s, r)

    def ~ (r: Rexp) = SEQ(s, r)

    def ~ (r: String) = SEQ(s, r)

    def % = STAR(s)

}

//derive(0, init_zipper(re0))

// println(re1s.length)

// mems.foreach(a => println(a))

// val re1sPlugged = plug_all(re1s)

// re1sPlugged.foreach(zipper => {

//                         println(zipper); 

//                         println("delimit") 

//                         })

// mems.clear()

// println(mems)

// println(re0)

// val re2s = lex(re0, "aab")

// val re2sPlugged = plug_all(re2s)

// re2sPlugged.foreach(v => {

//         val Sequ(Empty, vp) = v

//         println(vp)

//     }

// )

// val re0 = SEQ(ALT(CHAR('a'), SEQ(CHAR('a'),CHAR('a'))), 

// ALT(SEQ(CHAR('a'), CHAR('b')), SEQ(CHAR('b'), CHAR('c')) )

// )

// val (rgraph, re0root) = makeGraphFromObject(re0)

// val asciir = GraphLayout.renderGraph(rgraph)

// println("printing out re0")

// println(asciir)

// val re1s = lex(re0, "aabc")

def actualZipperSize(zs: List[Zipper]) : Int = zs match {

    case Nil => 0

    case z::zs1 => countParents(z._2) + actualZipperSize(zs1)

}

def countParents(m: Mem) : Int = {

    m.parents.map(c => countGrandParents(c)).sum

}

def countGrandParents(c: Ctx) : Int = {

    c match {

        case RootC => 1

        case SeqC(m, pr, unp) => countParents(m)

        case AltC(m, w) => countParents(m)

        case StarC(m, _, _) => countParents(m)

    }

}

//(a+aa)* \a --> (1 + a)(a+aa)* --> (a+aa)* + (1+a)(a+aa)*

//a(a+aa)* + 1(a+aa)* + (a+aa)*

//a~(a + aa)* \a -> 1 ~ (a + aa)* 

//va <-----> m --> SeqC(m1, pr, "a") --> AltC(m4, Right)--> StarC(m2, vs, "a" + "aa") --> SeqC(m) ---> Root

//           ^

//           ---> AltC(m4, Left) 

def zipBackToRegex(c: Ctx, r: Rexp = ONE) : Rexp = {

    c match {

        case RootC => r

        case SeqC(m, pr, Nil) => zipBackToRegex(m.parents.head, r)

        case SeqC(m, pr, unp::Nil) => zipBackToRegex(m.parents.head, SEQ(r, unp))

        case AltC(m, w) => zipBackToRegex(m.parents.head, r)

        case StarC(m, vs, r0) => zipBackToRegex(m.parents.head, SEQ(r, STAR(r0)))

    }

}

def zipperSimp(z: Zipper) : Unit = z match {

    case (v, m) => //m.parents = m.parents.distinctBy(c => zipBackToRegex(c))

}

def distinctCtx(cs: List[Ctx]) : List[Ctx] = cs.distinctBy(c => zipBackToRegex(c))

def simpleCtxDisplay(c: Ctx, indent : Int = 0) : String = c match {

    case SeqC(m, pr, unp) => "Sc[m:" ++ printMem(m, indent + 1) ++ 

        "pr:" ++ pr.map(v => shortValOutput(v)).mkString(", ") ++ " unp:" ++ unp.map(r2 => shortRexpOutput(r2)).mkString(", ") ++ "]"

    case AltC(m, w) =>

        w(Empty) match {

            case Left(_) => s"Ac(m:${printMem(m, indent + 1)}, Left(_))"

            case Right(_) => s"Ac(m:${printMem(m, indent + 1)}, Right(_))"

            case Empty => s"Ac(m:${printMem(m, indent + 1)}, id)"

        } 

    case StarC(m, vs, r0) => s"StarC[m:" ++ printMem(m, indent + 1) ++ 

        "vs:" ++ vs.map(v => shortValOutput(v)).mkString(", ") ++ " r0: " ++ shortRexpOutput(r0)

    case RootC => "Root"

    //case AL1(r) => s"(+${shortRexpOutput(r)})"

    //case STAR(r) => "STAR(" ++ shortRexpOutput(r) ++ ")"

    //case RTOP => "RTOP"

  }

def printMem(m: Mem, indent: Int = 0) : String = {

   "M(par:" ++

   m.parents.map(c => simpleCtxDisplay(c, indent + 1)).mkString("(",",", ")")  ++

  ("， results:")  ++

  (for(iRexp <- m.result) 

    yield iRexp match {case (p: Int, v: Val) => s"$p->${shortValOutput(v)}"}

  ).mkString("(",",", ")")  ++ 

   ")" 

}

def shortRexpOutput(r: Rexp) : String = r match {

    case CHAR(c) => c.toString

    case ONE => "1"

    case ZERO => "0"

    case SEQ(r1, r2) => "[" ++ shortRexpOutput(r1) ++ "~" ++ shortRexpOutput(r2) ++ "]"

    case ALT(r1, r2) => "(" ++ shortRexpOutput(r1) ++ "+" ++ shortRexpOutput(r2) ++ ")"

    case STAR(r) => "[" ++ shortRexpOutput(r) ++ "]*"

    //case STAR(r) => "STAR(" ++ shortRexpOutput(r) ++ ")"

    case RTOP => "RTOP"

  }

def shortValOutput(v: Val) : String = v match {

    case Left(v) => "L(" ++ shortValOutput(v) ++ ")"

    case Right(v) => "R(" ++ shortValOutput(v) ++ ")"

    case Empty => "e"

    case Sequ(v1, v2) => "[" ++ shortValOutput(v1) ++ "~" ++ shortValOutput(v2) ++ "]"

    case Chr(a) => a.toString

    case Stars(vs) => "Stars" ++ vs.map(shortValOutput(_)).mkString("[", ",", "]")

    case _ => "???"

}

//def crystalizeZipper

for(i <- 1 to 10) {

    mems.clear()

println(s"there are $i number of a's")

val re1 = (("a" | "b") ~ "c" | ("b" | "e") ~ "c" ) ~ "f"//("a" | "aa" |"ab").%

val re1Lexed = lex(re1, "bcf")//"a"*i+"b")

//drawZippers(re1Lexed)

println("size of actual zipper (including memoized contexts")

println(actualZipperSize(re1Lexed))

//println(re1Lexed)

//re1Lexed.foreach(zipperSimp(_))

//println(actualZipperSize(re1S))

val re1resPlugged = plug_all(re1Lexed)

//println(actualZipperSize(re1Lexed))

println("value extracted")

re1resPlugged.foreach(v => {

        val Sequ(Empty, vp) = v

        println(vp)

}

)

  val mb = 1024*1024

val runtime = Runtime.getRuntime

println("ALL RESULTS IN MB")

println("** Used Memory:  " + (runtime.totalMemory - runtime.freeMemory) / mb)

println("** Free Memory:  " + runtime.freeMemory / mb)

println("** Total Memory: " + runtime.totalMemory / mb)

println("** Max Memory:   " + runtime.maxMemory / mb)

}

mems.clear()

val re2 = SEQ(ONE, "a")

val re2res = lex(re2, "a")

//lex(1~a, "a") --> lexRecurse((1v, m  (SeqC(m (RootC, Nil), Nil, [1~a] ) )))

println(re2res)

val re2resPlugged = plug_all(re2res)

re2resPlugged.foreach(v => {

        val Sequ(Empty, vp) = v

        println(vp)

}

)

// println("remaining regex")

// println(re1ss.flatMap(z => zipBackMem(z._2)))

// val re1ssPlugged = plug_all(re1ss)

// println("each of the values")

// re1ssPlugged.foreach(v => {

//         //val Sequ(Empty, vp) = v

//         //println(vp)

//         println(v)

//     }

// )

// println(mems.size)

//println(mems)

//mems.map({case (ir, m) => if (ir._1 == 1 && ir._2 == CHAR('b')) println(printMem(m)) })

// println("Mkeps + inj:")

// println(

//     mems.get((0, re1)) match {

//         case Some(m) => printMem(m)

//         case None => ""

//     }

//     )

// println(re1sPlugged)

//drawZippers(re1s, plugOrNot = false)