1 import Element.elem

     2 import RexpRelated._

     3 import RexpRelated.Rexp._

     4 import Partial._

     5 import BRexp._

     6 import scala.collection.mutable.ListBuffer

     7 object Spiral{

     8 

     9   val space = elem(" ")

    10   val corner = elem("+")

    11 

    12   def spiral(nEdges: Int, direction: Int): Element = {

    13     if(nEdges == 1)

    14       elem("+")

    15     else {

    16       val sp = spiral(nEdges - 1, (direction + 3) % 4)

    17       def verticalBar = elem('|', 1, sp.height)

    18       def horizontalBar = elem('-', sp.width, 1)

    19       if(direction == 0)

    20         (corner beside horizontalBar) above sp//(sp beside space)

    21       else if (direction == 1)

    22         sp beside (corner above verticalBar)

    23       else if (direction == 2)

    24         (space beside sp) above (horizontalBar beside corner)

    25       else

    26         (verticalBar above corner) beside (space above sp)

    27     }

    28   }

    29   val alphabet = ("""abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789.:"=()\;-+*!<>\/%{} """+"\n\t").toSet//Set('a','b','c')

    30   def bregx_tree(r: BRexp): Element = regx_tree(berase(r))

    31   def regx_tree(r: Rexp): Element = aregx_tree(internalise(r))

    32   def aregx_tree(r: ARexp): Element = {

    33     r match {

    34       case ACHAR(bs, d) => {

    35         //val Some(d) = alphabet.find(f)

    36         d match {

    37           case '\n' => elem("\\n")

    38           case '\t' => elem("\\t")

    39           case ' ' => elem("space")

    40           case d => elem(d.toString)

    41         }   

    42       }

    43       case AONE(bs) => {

    44         elem("ONE")

    45       }

    46       case AZERO => {

    47         elem("ZERO")

    48       }

    49       case ASEQ(bs, r1, r2) => {

    50         binary_print("SEQ", r1, r2)

    51       }

    52       case AALTS(bs, rs) => {

    53         //elem("Awaiting completion")

    54         list_print("ALT", rs)

    55       }

    56       case ASTAR(bs, r) => {

    57         list_print("STA", List(r))

    58       }

    59     }

    60   }

    61   val port = elem(" └-")

    62   def list_print(name: String, rs: List[ARexp]): Element = {

    63     rs match {

    64       case r::Nil => {

    65         val pref = aregx_tree(r)

    66         val head = elem(name)

    67         (head left_align (port up_align pref) ) 

    68       }

    69       case r2::r1::Nil => {

    70         binary_print(name, r2, r1)

    71       }

    72       case r::rs1 => {

    73         val pref = aregx_tree(r)

    74         val head = elem(name)

    75         if (pref.height > 1){

    76           val link = elem('|', 1, pref.height - 1)

    77           (head left_align ((port above link) beside pref)) left_align tail_print(rs1)    

    78         }

    79         else{

    80           (head left_align (port beside pref) ) left_align tail_print(rs1)

    81         }

    82       }

    83     }

    84   }

    85   def tail_print(rs: List[ARexp]): Element = {

    86     rs match {

    87       case r2::r1::Nil => {

    88         val pref = aregx_tree(r2)

    89         val suff = aregx_tree(r1)

    90         if (pref.height > 1){

    91           val link = elem('|', 1, pref.height - 1)

    92           ((port above link) beside pref) left_align (port up_align suff)

    93         }

    94         else{

    95           (port beside pref) left_align (port up_align suff)

    96         } 

    97       }

    98       case r2::rs1 => {

    99         val pref = aregx_tree(r2)

   100         

   101         if (pref.height > 1){

   102           val link = elem('|', 1, pref.height - 1)

   103           ((port above link) beside pref) left_align tail_print(rs1)//(port up_align tail_print(rs1) )

   104         }

   105         else{

   106           (port beside pref) left_align tail_print(rs1)//(port up_align tail_print(rs1))

   107         } 

   108         //pref left_align tail_print(rs1)

   109       }

   110     }

   111   }

   112 

   113   def binary_print(name: String, r1: ARexp, r2: ARexp): Element = {

   114     val pref = aregx_tree(r1)

   115     val suff = aregx_tree(r2)

   116     val head = elem(name)

   117     if (pref.height > 1){

   118       val link = elem('|', 1, pref.height - 1)

   119       (head left_align ((port above link) beside pref) ) left_align (port up_align suff)

   120     }

   121     else{

   122       (head left_align (port beside pref) ) left_align (port up_align suff)

   123     }

   124   }

   125   val arr_of_size = ListBuffer.empty[Int]

   126   def spill(r: Rexp, or: Rexp): Set[Rexp] = {

   127     if(r == or) 

   128       Set(r)

   129     else{

   130       r match {

   131           case ALTS(rs) => rs.flatMap(r1 => spill(r1, or)).toSet

   132           case SEQ(ALTS(rs), r3) => rs.flatMap(r1 => spill(r1, or).map(a => if(a == ONE) r3 else SEQ(a, r3)) ).toSet

   133           case ZERO => Set()

   134           case r => Set(r)

   135       }

   136     }

   137   }

   138   def pC(r: Rexp): Set[Rexp] = {//PD's companion

   139     r match {

   140       case SEQ(r1, r2) => pC(r2)

   141       case ALTS(rs) => rs.flatMap(a => pC(a) ).toSet

   142       case CHAR(c) => Set(r)

   143       case r => Set()

   144     }

   145   }

   146 

   147   def aspill(ar: ARexp, or: Rexp): Set[Rexp] = spill(erase(ar), or)

   148   def illustration(r: Rexp, s: String){

   149     var i_like_imperative_style = internalise(r)

   150     val all_chars = s.toList

   151     for (i <- 0 to s.length - 1){

   152       val der_res =  bder(all_chars(i), i_like_imperative_style)

   153       val simp_res = bsimp(der_res)

   154       println("The original regex, the regex after derivative w.r.t " + all_chars(i) + " and the simplification of the derivative.")

   155       println(aregx_tree(i_like_imperative_style) up_align aregx_tree(der_res) up_align aregx_tree(simp_res))

   156       //println(asize(i_like_imperative_style), asize(der_res), asize(simp_res))

   157       arr_of_size += asize(i_like_imperative_style)

   158       //println(asize(simp_res), asize(simp_res) / arr_of_size(0) )

   159       i_like_imperative_style = simp_res

   160     }

   161     arr_of_size += asize(i_like_imperative_style)

   162   }

   163   val ran = scala.util.Random

   164   var alphabet_size = 3

   165   def balanced_seq_star_gen(depth: Int, star: Boolean): Rexp = {

   166     if(depth == 1){

   167       ((ran.nextInt(4) + 97).toChar).toString

   168     }

   169     else if(star){

   170       STAR(balanced_seq_star_gen(depth - 1, false))

   171     }

   172     else{

   173       SEQ(balanced_seq_star_gen(depth - 1, true), balanced_seq_star_gen(depth - 1, true))

   174     }

   175   }

   176   def max(i: Int, j: Int): Int = {

   177     if(i > j)

   178       i

   179     else 

   180       j

   181   }

   182   def random_struct_gen(depth:Int): Rexp = {

   183     val dice = ran.nextInt(3)

   184     val dice2 = ran.nextInt(3)

   185     (dice, depth) match {

   186       case (_, 0) => ((ran.nextInt(3) + 97).toChar).toString

   187       case (0, i) => STAR(random_struct_gen(max(0, i - 1 - dice2)))

   188       case (1, i) => SEQ(random_struct_gen(max(0, i - 1 - dice2)), random_struct_gen(max(0, i - 1 - dice2)))

   189       case (2, i) => ALTS( List(random_struct_gen(max(0, i - 1 - dice2)), random_struct_gen(max(0, i - 1 - dice2))) )

   190     }

   191   }

   192   def balanced_struct_gen(depth: Int): Rexp = {

   193     val dice = ran.nextInt(3)

   194     (dice, depth) match {

   195       case (_, 0) => ((ran.nextInt(3) + 97).toChar).toString

   196       case (0, i) => STAR(random_struct_gen(depth - 1))

   197       case (1, i) => SEQ(random_struct_gen(depth - 1), random_struct_gen(depth - 1))

   198       case (2, i) => ALTS( List(random_struct_gen(depth - 1), random_struct_gen(depth - 1) ) )

   199     }

   200   }

   201   def rd_string_gen(alp_size: Int, len: Int): String = {

   202     if( len > 0)

   203       ((ran.nextInt(alp_size) + 97).toChar).toString + rd_string_gen(alp_size, len - 1)

   204     else

   205       ((ran.nextInt(alp_size) + 97).toChar).toString

   206   }

   207   def plot(b: List[Int]){

   208     println(b(0),b.max)

   209 

   210   }

   211   def dep_exp(depth: List[Int]){

   212     for(i <- depth){

   213       arr_of_size.clear()

   214       val s = rd_string_gen(alphabet_size, (i-8)*(i-8)+10)

   215       val r = random_struct_gen(i)

   216       println("depth: "+i)

   217       illustration(r, s) //"abcabadaaadcabdbabcdaadbabbcbbdabdabbcbdbabdbcdb") 

   218       //println("depth: " + i + " general stats:"+ arr_of_size(0), arr_of_size.max, arr_of_size.max/arr_of_size(0))

   219       //println("x y label alignment")

   220       /*for(i <- 0 to s.length - 1){

   221         if(s(i) == '\n')

   222           println(i+" "+arr_of_size(i)+" "+"nl"+" -140")

   223         else if(s(i) ==  ' ')

   224           println(i+" "+arr_of_size(i)+" "+"sp"+" -140")

   225         else

   226           println(i+" "+arr_of_size(i)+" "+s(i)+" -140")

   227       }*/

   228       //println(s.length + " " + arr_of_size(s.length) + " ]" + " -140")

   229     }

   230   }

   231   def case_study(ss: List[String], r: Rexp){

   232     for(s <- ss){

   233       arr_of_size.clear()

   234       illustration(r, s)

   235       println("x y label alignment")

   236       for(i <- 0 to s.length - 1){

   237         if(s(i) == '\n')

   238           println(i+" "+arr_of_size(i)+" "+"nl"+" -140")

   239         else if(s(i) ==  ' ')

   240           println(i+" "+arr_of_size(i)+" "+"sp"+" -140")

   241         else

   242           println(i+" "+arr_of_size(i)+" "+s(i)+" -140")

   243       }

   244     }

   245   }

   246   def star_gen(dp: Int): Rexp = {

   247     if(dp > 0)

   248       STAR(star_gen(dp - 1))

   249     else

   250       "a"

   251   }

   252   def strs_gen(len: Int, num: Int): List[String] = {

   253     if(num > 0){

   254       rd_string_gen(3, len)::strs_gen(len, num - 1)

   255     }

   256     else{

   257       Nil

   258     }

   259   }

   260   def regx_print(r: Rexp): String = {

   261     r match {

   262       case ZERO =>

   263         "ZERO"

   264       case CHAR(c) => {

   265          //val Some(c) = alphabet.find(f)

   266          "\"" + c.toString + "\""

   267       }

   268       case ONE => {

   269         "ONE"

   270       }

   271       case ALTS(rs) => {

   272         "ALTS(List("+(rs.map(regx_print)).foldLeft("")((a, b) => if(a == "") b else a + "," + b)+"))"

   273       }

   274       case SEQ(r1, r2) => {

   275         "SEQ(" + regx_print(r1) + "," + regx_print(r2) + ")"

   276       }

   277       case STAR(r) => {

   278         "STAR(" + regx_print(r) + ")"

   279       }

   280     }

   281   }

   282   val mkst = "abcdefghijklmnopqrstuvwxyz"

   283   def weak_sub_check(r: Rexp, s: String, i: Int, f: (List[Rexp], Set[Rexp]) => Boolean){

   284     //we first compute pders over the set of all strings on the alphabet

   285     val pd = pderas(Set(r), i + 4)

   286     //then "b-internalise" the regular expression into a brexp(this is essentially 

   287     //attaching a bit Z to every alts to signify that they come from the original regular expression)

   288     var old = brternalise(r)

   289     //this is for comparison between normal simp and the weakened version of simp

   290     //normal simp will be performed on syncold

   291     //weakend simp will be performed on old

   292     var syncold = brternalise(r)

   293     val all_chars = s.toList

   294     for (i <- 0 to s.length - 1){

   295       val syncder_res = brder(all_chars(i), syncold)

   296       val syncsimp_res = strong_br_simp(syncder_res)

   297       //see brder for detailed explanation

   298       //just changes bit Z to S when deriving an ALTS, 

   299       //signifying that the structure has been "touched" and

   300       //therefore able to be spilled in the bspill function

   301       val der_res =  brder(all_chars(i), old)

   302       val simp_res = br_simp(der_res)

   303       val anatomy = bspill(simp_res)

   304       //track if the number of regular expressions exceeds those in the PD set(remember PD means the pders over A*)

   305       if(f(anatomy, pd)  == false){

   306         /*println("regular expression")

   307         println(regx_tree(r))

   308         println("string at " + i)

   309         println(s)

   310         println("partial derivatives")

   311         (pd.foreach(a => println(regx_tree(a))))

   312         println("simp result")

   313         println(bregx_tree(simp_res))

   314         println("bspill result")

   315         (anatomy.foreach(a => println(regx_tree(a))))*/

   316         println(size(berase(syncsimp_res)))

   317         println(size(berase(simp_res)))

   318         println(anatomy.map(size).sum)

   319         println(pd.map(size).sum)

   320       }  

   321       old = simp_res

   322       syncold = syncsimp_res

   323     }

   324   }

   325   def inclusion_truth(anatomy: List[Rexp], pd: Set[Rexp]): Boolean = {

   326     val aset = anatomy.toSet

   327     if(aset subsetOf pd){

   328       true

   329     }

   330     else{

   331       println("inclusion not true")

   332       false

   333     }

   334   }

   335   def size_comp(anatomy: List[Rexp], pd: Set[Rexp]):Boolean = {println("size of PD and bspilled simp regx: ", pd.size, anatomy.size); true}

   336   def size_expansion_rate(anatomy: List[Rexp], pd: Set[Rexp]): Boolean = if(anatomy.size > (pd.size)*2 ) {println("size of PD and bspilled simp regx: ", pd.size, anatomy.size); inclusion_truth(anatomy, pd); false }else {true}

   337   

   338   def check_all(){

   339     for(i <- 1 to 1)

   340     {

   341         val s = "bbb"//rd_string_gen(alphabet_size, 5)//"ac"//rd_string_gen(alphabet_size, 5)

   342         val r = STAR(STAR(ALTS(List(SEQ(CHAR('b'),CHAR('b')), ALTS(List(CHAR('a'), CHAR('b')))))))//balanced_struct_gen(4)//SEQ(ALTS(List(STAR("a"),ALTS(List("a","c")))),SEQ(ALTS(List("c","a")),ALTS(List("c","b")))) //random_struct_gen(7)

   343         //subset_check(r, s)

   344         weak_sub_check(r, s, 5, size_expansion_rate)

   345     }

   346   }

   347   def main(args: Array[String]) {

   348     check_all()   

   349   } 

   350 }

   351