--- /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()
+ }
+}
+