diff -r 000000000000 -r 902326e1615a Spiral.scala
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/Spiral.scala	Wed Mar 13 13:14:38 2019 +0000
@@ -0,0 +1,351 @@
+import Element.elem
+import RexpRelated._
+import RexpRelated.Rexp._
+import Partial._
+import BRexp._
+import scala.collection.mutable.ListBuffer
+object Spiral{
+
+  val space = elem(" ")
+  val corner = elem("+")
+
+  def spiral(nEdges: Int, direction: Int): Element = {
+    if(nEdges == 1)
+      elem("+")
+    else {
+      val sp = spiral(nEdges - 1, (direction + 3) % 4)
+      def verticalBar = elem('|', 1, sp.height)
+      def horizontalBar = elem('-', sp.width, 1)
+      if(direction == 0)
+        (corner beside horizontalBar) above sp//(sp beside space)
+      else if (direction == 1)
+        sp beside (corner above verticalBar)
+      else if (direction == 2)
+        (space beside sp) above (horizontalBar beside corner)
+      else
+        (verticalBar above corner) beside (space above sp)
+    }
+  }
+  val alphabet = ("""abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789.:"=()\;-+*!<>\/%{} """+"\n\t").toSet//Set('a','b','c')
+  def bregx_tree(r: BRexp): Element = regx_tree(berase(r))
+  def regx_tree(r: Rexp): Element = aregx_tree(internalise(r))
+  def aregx_tree(r: ARexp): Element = {
+    r match {
+      case ACHAR(bs, d) => {
+        //val Some(d) = alphabet.find(f)
+        d match {
+          case '\n' => elem("\\n")
+          case '\t' => elem("\\t")
+          case ' ' => elem("space")
+          case d => elem(d.toString)
+        }   
+      }
+      case AONE(bs) => {
+        elem("ONE")
+      }
+      case AZERO => {
+        elem("ZERO")
+      }
+      case ASEQ(bs, r1, r2) => {
+        binary_print("SEQ", r1, r2)
+      }
+      case AALTS(bs, rs) => {
+        //elem("Awaiting completion")
+        list_print("ALT", rs)
+      }
+      case ASTAR(bs, r) => {
+        list_print("STA", List(r))
+      }
+    }
+  }
+  val port = elem(" └-")
+  def list_print(name: String, rs: List[ARexp]): Element = {
+    rs match {
+      case r::Nil => {
+        val pref = aregx_tree(r)
+        val head = elem(name)
+        (head left_align (port up_align pref) ) 
+      }
+      case r2::r1::Nil => {
+        binary_print(name, r2, r1)
+      }
+      case r::rs1 => {
+        val pref = aregx_tree(r)
+        val head = elem(name)
+        if (pref.height > 1){
+          val link = elem('|', 1, pref.height - 1)
+          (head left_align ((port above link) beside pref)) left_align tail_print(rs1)    
+        }
+        else{
+          (head left_align (port beside pref) ) left_align tail_print(rs1)
+        }
+      }
+    }
+  }
+  def tail_print(rs: List[ARexp]): Element = {
+    rs match {
+      case r2::r1::Nil => {
+        val pref = aregx_tree(r2)
+        val suff = aregx_tree(r1)
+        if (pref.height > 1){
+          val link = elem('|', 1, pref.height - 1)
+          ((port above link) beside pref) left_align (port up_align suff)
+        }
+        else{
+          (port beside pref) left_align (port up_align suff)
+        } 
+      }
+      case r2::rs1 => {
+        val pref = aregx_tree(r2)
+        
+        if (pref.height > 1){
+          val link = elem('|', 1, pref.height - 1)
+          ((port above link) beside pref) left_align tail_print(rs1)//(port up_align tail_print(rs1) )
+        }
+        else{
+          (port beside pref) left_align tail_print(rs1)//(port up_align tail_print(rs1))
+        } 
+        //pref left_align tail_print(rs1)
+      }
+    }
+  }
+
+  def binary_print(name: String, r1: ARexp, r2: ARexp): Element = {
+    val pref = aregx_tree(r1)
+    val suff = aregx_tree(r2)
+    val head = elem(name)
+    if (pref.height > 1){
+      val link = elem('|', 1, pref.height - 1)
+      (head left_align ((port above link) beside pref) ) left_align (port up_align suff)
+    }
+    else{
+      (head left_align (port beside pref) ) left_align (port up_align suff)
+    }
+  }
+  val arr_of_size = ListBuffer.empty[Int]
+  def spill(r: Rexp, or: Rexp): Set[Rexp] = {
+    if(r == or) 
+      Set(r)
+    else{
+      r match {
+          case ALTS(rs) => rs.flatMap(r1 => spill(r1, or)).toSet
+          case SEQ(ALTS(rs), r3) => rs.flatMap(r1 => spill(r1, or).map(a => if(a == ONE) r3 else SEQ(a, r3)) ).toSet
+          case ZERO => Set()
+          case r => Set(r)
+      }
+    }
+  }
+  def pC(r: Rexp): Set[Rexp] = {//PD's companion
+    r match {
+      case SEQ(r1, r2) => pC(r2)
+      case ALTS(rs) => rs.flatMap(a => pC(a) ).toSet
+      case CHAR(c) => Set(r)
+      case r => Set()
+    }
+  }
+
+  def aspill(ar: ARexp, or: Rexp): Set[Rexp] = spill(erase(ar), or)
+  def illustration(r: Rexp, s: String){
+    var i_like_imperative_style = internalise(r)
+    val all_chars = s.toList
+    for (i <- 0 to s.length - 1){
+      val der_res =  bder(all_chars(i), i_like_imperative_style)
+      val simp_res = bsimp(der_res)
+      println("The original regex, the regex after derivative w.r.t " + all_chars(i) + " and the simplification of the derivative.")
+      println(aregx_tree(i_like_imperative_style) up_align aregx_tree(der_res) up_align aregx_tree(simp_res))
+      //println(asize(i_like_imperative_style), asize(der_res), asize(simp_res))
+      arr_of_size += asize(i_like_imperative_style)
+      //println(asize(simp_res), asize(simp_res) / arr_of_size(0) )
+      i_like_imperative_style = simp_res
+    }
+    arr_of_size += asize(i_like_imperative_style)
+  }
+  val ran = scala.util.Random
+  var alphabet_size = 3
+  def balanced_seq_star_gen(depth: Int, star: Boolean): Rexp = {
+    if(depth == 1){
+      ((ran.nextInt(4) + 97).toChar).toString
+    }
+    else if(star){
+      STAR(balanced_seq_star_gen(depth - 1, false))
+    }
+    else{
+      SEQ(balanced_seq_star_gen(depth - 1, true), balanced_seq_star_gen(depth - 1, true))
+    }
+  }
+  def max(i: Int, j: Int): Int = {
+    if(i > j)
+      i
+    else 
+      j
+  }
+  def random_struct_gen(depth:Int): Rexp = {
+    val dice = ran.nextInt(3)
+    val dice2 = ran.nextInt(3)
+    (dice, depth) match {
+      case (_, 0) => ((ran.nextInt(3) + 97).toChar).toString
+      case (0, i) => STAR(random_struct_gen(max(0, i - 1 - dice2)))
+      case (1, i) => SEQ(random_struct_gen(max(0, i - 1 - dice2)), random_struct_gen(max(0, i - 1 - dice2)))
+      case (2, i) => ALTS( List(random_struct_gen(max(0, i - 1 - dice2)), random_struct_gen(max(0, i - 1 - dice2))) )
+    }
+  }
+  def balanced_struct_gen(depth: Int): Rexp = {
+    val dice = ran.nextInt(3)
+    (dice, depth) match {
+      case (_, 0) => ((ran.nextInt(3) + 97).toChar).toString
+      case (0, i) => STAR(random_struct_gen(depth - 1))
+      case (1, i) => SEQ(random_struct_gen(depth - 1), random_struct_gen(depth - 1))
+      case (2, i) => ALTS( List(random_struct_gen(depth - 1), random_struct_gen(depth - 1) ) )
+    }
+  }
+  def rd_string_gen(alp_size: Int, len: Int): String = {
+    if( len > 0)
+      ((ran.nextInt(alp_size) + 97).toChar).toString + rd_string_gen(alp_size, len - 1)
+    else
+      ((ran.nextInt(alp_size) + 97).toChar).toString
+  }
+  def plot(b: List[Int]){
+    println(b(0),b.max)
+
+  }
+  def dep_exp(depth: List[Int]){
+    for(i <- depth){
+      arr_of_size.clear()
+      val s = rd_string_gen(alphabet_size, (i-8)*(i-8)+10)
+      val r = random_struct_gen(i)
+      println("depth: "+i)
+      illustration(r, s) //"abcabadaaadcabdbabcdaadbabbcbbdabdabbcbdbabdbcdb") 
+      //println("depth: " + i + " general stats:"+ arr_of_size(0), arr_of_size.max, arr_of_size.max/arr_of_size(0))
+      //println("x y label alignment")
+      /*for(i <- 0 to s.length - 1){
+        if(s(i) == '\n')
+          println(i+" "+arr_of_size(i)+" "+"nl"+" -140")
+        else if(s(i) ==  ' ')
+          println(i+" "+arr_of_size(i)+" "+"sp"+" -140")
+        else
+          println(i+" "+arr_of_size(i)+" "+s(i)+" -140")
+      }*/
+      //println(s.length + " " + arr_of_size(s.length) + " ]" + " -140")
+    }
+  }
+  def case_study(ss: List[String], r: Rexp){
+    for(s <- ss){
+      arr_of_size.clear()
+      illustration(r, s)
+      println("x y label alignment")
+      for(i <- 0 to s.length - 1){
+        if(s(i) == '\n')
+          println(i+" "+arr_of_size(i)+" "+"nl"+" -140")
+        else if(s(i) ==  ' ')
+          println(i+" "+arr_of_size(i)+" "+"sp"+" -140")
+        else
+          println(i+" "+arr_of_size(i)+" "+s(i)+" -140")
+      }
+    }
+  }
+  def star_gen(dp: Int): Rexp = {
+    if(dp > 0)
+      STAR(star_gen(dp - 1))
+    else
+      "a"
+  }
+  def strs_gen(len: Int, num: Int): List[String] = {
+    if(num > 0){
+      rd_string_gen(3, len)::strs_gen(len, num - 1)
+    }
+    else{
+      Nil
+    }
+  }
+  def regx_print(r: Rexp): String = {
+    r match {
+      case ZERO =>
+        "ZERO"
+      case CHAR(c) => {
+         //val Some(c) = alphabet.find(f)
+         "\"" + c.toString + "\""
+      }
+      case ONE => {
+        "ONE"
+      }
+      case ALTS(rs) => {
+        "ALTS(List("+(rs.map(regx_print)).foldLeft("")((a, b) => if(a == "") b else a + "," + b)+"))"
+      }
+      case SEQ(r1, r2) => {
+        "SEQ(" + regx_print(r1) + "," + regx_print(r2) + ")"
+      }
+      case STAR(r) => {
+        "STAR(" + regx_print(r) + ")"
+      }
+    }
+  }
+  val mkst = "abcdefghijklmnopqrstuvwxyz"
+  def weak_sub_check(r: Rexp, s: String, i: Int, f: (List[Rexp], Set[Rexp]) => Boolean){
+    //we first compute pders over the set of all strings on the alphabet
+    val pd = pderas(Set(r), i + 4)
+    //then "b-internalise" the regular expression into a brexp(this is essentially 
+    //attaching a bit Z to every alts to signify that they come from the original regular expression)
+    var old = brternalise(r)
+    //this is for comparison between normal simp and the weakened version of simp
+    //normal simp will be performed on syncold
+    //weakend simp will be performed on old
+    var syncold = brternalise(r)
+    val all_chars = s.toList
+    for (i <- 0 to s.length - 1){
+      val syncder_res = brder(all_chars(i), syncold)
+      val syncsimp_res = strong_br_simp(syncder_res)
+      //see brder for detailed explanation
+      //just changes bit Z to S when deriving an ALTS, 
+      //signifying that the structure has been "touched" and
+      //therefore able to be spilled in the bspill function
+      val der_res =  brder(all_chars(i), old)
+      val simp_res = br_simp(der_res)
+      val anatomy = bspill(simp_res)
+      //track if the number of regular expressions exceeds those in the PD set(remember PD means the pders over A*)
+      if(f(anatomy, pd)  == false){
+        /*println("regular expression")
+        println(regx_tree(r))
+        println("string at " + i)
+        println(s)
+        println("partial derivatives")
+        (pd.foreach(a => println(regx_tree(a))))
+        println("simp result")
+        println(bregx_tree(simp_res))
+        println("bspill result")
+        (anatomy.foreach(a => println(regx_tree(a))))*/
+        println(size(berase(syncsimp_res)))
+        println(size(berase(simp_res)))
+        println(anatomy.map(size).sum)
+        println(pd.map(size).sum)
+      }  
+      old = simp_res
+      syncold = syncsimp_res
+    }
+  }
+  def inclusion_truth(anatomy: List[Rexp], pd: Set[Rexp]): Boolean = {
+    val aset = anatomy.toSet
+    if(aset subsetOf pd){
+      true
+    }
+    else{
+      println("inclusion not true")
+      false
+    }
+  }
+  def size_comp(anatomy: List[Rexp], pd: Set[Rexp]):Boolean = {println("size of PD and bspilled simp regx: ", pd.size, anatomy.size); true}
+  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}
+  
+  def check_all(){
+    for(i <- 1 to 1)
+    {
+        val s = "bbb"//rd_string_gen(alphabet_size, 5)//"ac"//rd_string_gen(alphabet_size, 5)
+        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)
+        //subset_check(r, s)
+        weak_sub_check(r, s, 5, size_expansion_rate)
+    }
+  }
+  def main(args: Array[String]) {
+    check_all()   
+  } 
+}
+