--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/Brexp.scala	Wed Mar 13 13:14:38 2019 +0000
@@ -0,0 +1,143 @@
+import RexpRelated._
+import RexpRelated.Rexp._
+import Spiral._
+import scala.collection.mutable.ArrayBuffer
+abstract class BRexp
+case object BZERO extends BRexp
+case object BONE extends BRexp
+case class BCHAR(c: Char) extends BRexp
+case class BALTS(b: Bit, rs: List[BRexp]) extends BRexp 
+case class BSEQ(r1: BRexp, r2: BRexp) extends BRexp 
+case class BSTAR(r: BRexp) extends BRexp 
+
+object BRexp{
+  def brternalise(r: Rexp) : BRexp = r match {//remember the initial shadowed bit should be set to Z as there 
+  //are no enclosing STAR or SEQ
+    case ZERO => BZERO
+    case ONE => BONE
+    case CHAR(c) => BCHAR(c)
+    case ALTS(rs) => BALTS(Z,  rs.map(brternalise))
+    case SEQ(r1, r2) => BSEQ( brternalise(r1), brternalise(r2) )
+    case STAR(r) => BSTAR(brternalise(r))
+    case RECD(x, r) => brternalise(r)
+  }
+  def brnullable (r: BRexp) : Boolean = r match {
+    case BZERO => false
+    case BONE => true
+    case BCHAR(_) => false
+    case BALTS(bs, rs) => rs.exists(brnullable)
+    case BSEQ(r1, r2) => brnullable(r1) && brnullable(r2)
+    case BSTAR(_) => true
+  }
+  def brder(c: Char, r: BRexp) : BRexp = r match {
+    case BZERO => BZERO
+    case BONE => BZERO
+    case BCHAR(d) => if (c == d) BONE else BZERO
+    case BALTS(bs, rs) => BALTS(S, rs.map(brder(c, _)))//After derivative: Splittable in the sense of PD
+    case BSEQ(r1, r2) => 
+      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
+      else BSEQ(brder(c, r1), r2)
+    case BSTAR(r) => BSEQ(brder(c, r), BSTAR(r))
+  }
+  def bflat(rs: List[BRexp]): List[BRexp] = {
+    //println("bs: " + bs + "rs: "+ rs + "length of bs, rs" + bs.length + ", " + rs.length)
+    //assert(bs.length == rs.length - 1 || bs.length == rs.length)//bs == Nil, rs == Nil  May add early termination later.
+    rs match {
+      case Nil => Nil//TODO: Look at this! bs should have been exhausted one bit earlier.
+      case BZERO :: rs1 => bflat(rs1)
+      case BALTS(S, rs1) :: rs2 => rs1 ::: bflat(rs2)
+      case BALTS(Z, rs1) :: rs2 => BALTS(Z, rs1) :: bflat(rs2)
+      case r1 :: rs2 => r1 :: bflat(rs2)
+    }
+  }
+  def stflat(rs: List[BRexp]): List[BRexp] = {
+    //println("bs: " + bs + "rs: "+ rs + "length of bs, rs" + bs.length + ", " + rs.length)
+    //assert(bs.length == rs.length - 1 || bs.length == rs.length)//bs == Nil, rs == Nil  May add early termination later.
+    rs match {
+      case Nil => Nil//TODO: Look at this! bs should have been exhausted one bit earlier.
+      case BZERO :: rs1 => bflat(rs1)
+      case BALTS(_, rs1) :: rs2 => rs1 ::: bflat(rs2)
+      case r1 :: rs2 => r1 :: bflat(rs2)
+    }
+  }
+  def berase(r:BRexp): Rexp = r match{
+    case BZERO => ZERO
+    case BONE => ONE
+    case BCHAR(f) => CHAR(f)
+    case BALTS(bs, rs) => ALTS(rs.map(berase(_)))
+    case BSEQ(r1, r2) => SEQ (berase(r1), berase(r2))
+    case BSTAR(r)=> STAR(berase(r))
+  }
+  def br_simp(r: BRexp): BRexp = r match {
+    case BSEQ(r1, r2) => (br_simp(r1), br_simp(r2)) match {
+        case (BZERO, _) => BZERO
+        case (_, BZERO) => BZERO
+        case (BONE, r2s) => r2s 
+        case (r1s, r2s) => BSEQ(r1s, r2s)
+    }
+    case BALTS(bs, rs) => {
+      //assert(bs.length == rs.length - 1)
+      val dist_res = if(bs == S) {//all S
+        val rs_simp = rs.map(br_simp)
+        val flat_res = bflat(rs_simp)
+        distinctBy(flat_res, berase)
+      }
+      else{//not allowed to simplify (all Z)
+        rs
+      }
+      dist_res match {
+        case Nil => {BZERO}
+        case s :: Nil => { s}
+        case rs => {BALTS(bs, rs)}
+      }
+    }
+    //case BSTAR(r) => BSTAR(r)
+    case r => r
+  }
+
+  def strong_br_simp(r: BRexp): BRexp = r match {
+    case BSEQ(r1, r2) => (strong_br_simp(r1), strong_br_simp(r2)) match {
+        case (BZERO, _) => BZERO
+        case (_, BZERO) => BZERO
+        case (BONE, r2s) => r2s 
+        case (r1s, r2s) => BSEQ(r1s, r2s)
+    }
+    case BALTS(bs, rs) => {
+      //assert(bs.length == rs.length - 1)
+      val dist_res = {//all S
+        val rs_simp = rs.map(strong_br_simp)
+        val flat_res = stflat(rs_simp)
+        distinctBy(flat_res, berase)
+      }
+      dist_res match {
+        case Nil => {BZERO}
+        case s :: Nil => { s}
+        case rs => {BALTS(bs, rs)}
+      }
+    }
+    //case BSTAR(r) => BSTAR(r)
+    case r => r
+  }
+
+  def break_chain(bs: Bit, rs: List[BRexp]): List[Rexp] = {
+    //do it in a functional style
+    if(bs == S)
+      rs.flatMap(bspill)
+    else
+      List(ALTS(rs.map(berase)))
+  }
+  
+  def bspill(r: BRexp): List[Rexp] = {//need to take SEQ(SEQ...) and many other structs into consideration
+      r match {//TODO: break chain rs according to bs
+          case BALTS(bs, rs) => {
+            break_chain(bs, rs)
+          }
+            //rs.flatMap(r1 =>  bspill(r1)  ).toSet    how to write if r's bit says no, do not split it with the adjacent regex?
+          case BSEQ(r2, r3) => bspill(r2).map( a => if(a == ONE) berase(r3) else SEQ(a, berase(r3)) )
+          case BZERO => List()
+          case r => List(berase(r))
+      }
+    
+  }
+
+}
\ No newline at end of file