0
+ − 1 import RexpRelated._
+ − 2 import RexpRelated.Rexp._
+ − 3 import Spiral._
+ − 4 import scala.collection.mutable.ArrayBuffer
+ − 5 abstract class BRexp
+ − 6 case object BZERO extends BRexp
+ − 7 case object BONE extends BRexp
+ − 8 case class BCHAR(c: Char) extends BRexp
+ − 9 case class BALTS(b: Bit, rs: List[BRexp]) extends BRexp
+ − 10 case class BSEQ(r1: BRexp, r2: BRexp) extends BRexp
+ − 11 case class BSTAR(r: BRexp) extends BRexp
+ − 12
+ − 13 object BRexp{
+ − 14 def brternalise(r: Rexp) : BRexp = r match {//remember the initial shadowed bit should be set to Z as there
+ − 15 //are no enclosing STAR or SEQ
+ − 16 case ZERO => BZERO
+ − 17 case ONE => BONE
+ − 18 case CHAR(c) => BCHAR(c)
+ − 19 case ALTS(rs) => BALTS(Z, rs.map(brternalise))
+ − 20 case SEQ(r1, r2) => BSEQ( brternalise(r1), brternalise(r2) )
+ − 21 case STAR(r) => BSTAR(brternalise(r))
+ − 22 case RECD(x, r) => brternalise(r)
+ − 23 }
+ − 24 def brnullable (r: BRexp) : Boolean = r match {
+ − 25 case BZERO => false
+ − 26 case BONE => true
+ − 27 case BCHAR(_) => false
+ − 28 case BALTS(bs, rs) => rs.exists(brnullable)
+ − 29 case BSEQ(r1, r2) => brnullable(r1) && brnullable(r2)
+ − 30 case BSTAR(_) => true
+ − 31 }
+ − 32 def brder(c: Char, r: BRexp) : BRexp = r match {
+ − 33 case BZERO => BZERO
+ − 34 case BONE => BZERO
+ − 35 case BCHAR(d) => if (c == d) BONE else BZERO
+ − 36 case BALTS(bs, rs) => BALTS(S, rs.map(brder(c, _)))//After derivative: Splittable in the sense of PD
+ − 37 case BSEQ(r1, r2) =>
+ − 38 if (brnullable(r1)) BALTS(S, List(BSEQ(brder(c, r1), r2), brder(c, r2) ) )//in r1\c~r2 r2's structure is maintained together with its splittablility bit
+ − 39 else BSEQ(brder(c, r1), r2)
+ − 40 case BSTAR(r) => BSEQ(brder(c, r), BSTAR(r))
+ − 41 }
+ − 42 def bflat(rs: List[BRexp]): List[BRexp] = {
+ − 43 //println("bs: " + bs + "rs: "+ rs + "length of bs, rs" + bs.length + ", " + rs.length)
+ − 44 //assert(bs.length == rs.length - 1 || bs.length == rs.length)//bs == Nil, rs == Nil May add early termination later.
+ − 45 rs match {
+ − 46 case Nil => Nil//TODO: Look at this! bs should have been exhausted one bit earlier.
+ − 47 case BZERO :: rs1 => bflat(rs1)
+ − 48 case BALTS(S, rs1) :: rs2 => rs1 ::: bflat(rs2)
+ − 49 case BALTS(Z, rs1) :: rs2 => BALTS(Z, rs1) :: bflat(rs2)
+ − 50 case r1 :: rs2 => r1 :: bflat(rs2)
+ − 51 }
+ − 52 }
+ − 53 def stflat(rs: List[BRexp]): List[BRexp] = {
+ − 54 //println("bs: " + bs + "rs: "+ rs + "length of bs, rs" + bs.length + ", " + rs.length)
+ − 55 //assert(bs.length == rs.length - 1 || bs.length == rs.length)//bs == Nil, rs == Nil May add early termination later.
+ − 56 rs match {
+ − 57 case Nil => Nil//TODO: Look at this! bs should have been exhausted one bit earlier.
+ − 58 case BZERO :: rs1 => bflat(rs1)
+ − 59 case BALTS(_, rs1) :: rs2 => rs1 ::: bflat(rs2)
+ − 60 case r1 :: rs2 => r1 :: bflat(rs2)
+ − 61 }
+ − 62 }
+ − 63 def berase(r:BRexp): Rexp = r match{
+ − 64 case BZERO => ZERO
+ − 65 case BONE => ONE
+ − 66 case BCHAR(f) => CHAR(f)
+ − 67 case BALTS(bs, rs) => ALTS(rs.map(berase(_)))
+ − 68 case BSEQ(r1, r2) => SEQ (berase(r1), berase(r2))
+ − 69 case BSTAR(r)=> STAR(berase(r))
+ − 70 }
+ − 71 def br_simp(r: BRexp): BRexp = r match {
+ − 72 case BSEQ(r1, r2) => (br_simp(r1), br_simp(r2)) match {
+ − 73 case (BZERO, _) => BZERO
+ − 74 case (_, BZERO) => BZERO
+ − 75 case (BONE, r2s) => r2s
+ − 76 case (r1s, r2s) => BSEQ(r1s, r2s)
+ − 77 }
+ − 78 case BALTS(bs, rs) => {
+ − 79 //assert(bs.length == rs.length - 1)
+ − 80 val dist_res = if(bs == S) {//all S
+ − 81 val rs_simp = rs.map(br_simp)
+ − 82 val flat_res = bflat(rs_simp)
+ − 83 distinctBy(flat_res, berase)
+ − 84 }
+ − 85 else{//not allowed to simplify (all Z)
+ − 86 rs
+ − 87 }
+ − 88 dist_res match {
+ − 89 case Nil => {BZERO}
+ − 90 case s :: Nil => { s}
+ − 91 case rs => {BALTS(bs, rs)}
+ − 92 }
+ − 93 }
+ − 94 //case BSTAR(r) => BSTAR(r)
+ − 95 case r => r
+ − 96 }
+ − 97
+ − 98 def strong_br_simp(r: BRexp): BRexp = r match {
+ − 99 case BSEQ(r1, r2) => (strong_br_simp(r1), strong_br_simp(r2)) match {
+ − 100 case (BZERO, _) => BZERO
+ − 101 case (_, BZERO) => BZERO
+ − 102 case (BONE, r2s) => r2s
+ − 103 case (r1s, r2s) => BSEQ(r1s, r2s)
+ − 104 }
+ − 105 case BALTS(bs, rs) => {
+ − 106 //assert(bs.length == rs.length - 1)
+ − 107 val dist_res = {//all S
+ − 108 val rs_simp = rs.map(strong_br_simp)
+ − 109 val flat_res = stflat(rs_simp)
+ − 110 distinctBy(flat_res, berase)
+ − 111 }
+ − 112 dist_res match {
+ − 113 case Nil => {BZERO}
+ − 114 case s :: Nil => { s}
+ − 115 case rs => {BALTS(bs, rs)}
+ − 116 }
+ − 117 }
+ − 118 //case BSTAR(r) => BSTAR(r)
+ − 119 case r => r
+ − 120 }
+ − 121
+ − 122 def break_chain(bs: Bit, rs: List[BRexp]): List[Rexp] = {
+ − 123 //do it in a functional style
+ − 124 if(bs == S)
+ − 125 rs.flatMap(bspill)
+ − 126 else
+ − 127 List(ALTS(rs.map(berase)))
+ − 128 }
+ − 129
+ − 130 def bspill(r: BRexp): List[Rexp] = {//need to take SEQ(SEQ...) and many other structs into consideration
+ − 131 r match {//TODO: break chain rs according to bs
+ − 132 case BALTS(bs, rs) => {
+ − 133 break_chain(bs, rs)
+ − 134 }
+ − 135 //rs.flatMap(r1 => bspill(r1) ).toSet how to write if r's bit says no, do not split it with the adjacent regex?
+ − 136 case BSEQ(r2, r3) => bspill(r2).map( a => if(a == ONE) berase(r3) else SEQ(a, berase(r3)) )
+ − 137 case BZERO => List()
+ − 138 case r => List(berase(r))
+ − 139 }
+ − 140
+ − 141 }
+ − 142
+ − 143 }