|
1 import RexpRelated._ |
|
2 import RexpRelated.Rexp._ |
|
3 import Spiral._ |
|
4 object Partial{ |
|
5 def dot_prod(rs: Set[Rexp], r: Rexp): Set[Rexp] = r match { |
|
6 case ZERO => Set() |
|
7 case ONE => rs |
|
8 case r => rs.map((re) => if (re == ONE) r else SEQ(re, r) ) |
|
9 } |
|
10 def cir_prod(l: Lin, t: Rexp): Lin = t match {//remember this Lin is different from the Lin in Antimirov's paper. Here it does not mean the set of all subsets of linear forms that does not contain zero, but rather the type a set of linear forms |
|
11 case ZERO => Set() |
|
12 case ONE => l |
|
13 case t => l.map( m => m._2 match {case ZERO => m case ONE => (m._1, t) case p => (m._1, SEQ(p, t)) } ) |
|
14 } |
|
15 def lf(r: Rexp): Lin = r match { |
|
16 case ZERO => Set() |
|
17 case ONE => Set() |
|
18 case CHAR(f) => { |
|
19 //val Some(c) = alphabet.find(f) |
|
20 Set((f, ONE)) |
|
21 } |
|
22 case ALTS(rs) => { |
|
23 rs.foldLeft(Set[Mon]())((acc, r) => acc ++ lf(r)) |
|
24 } |
|
25 case STAR(r1) => cir_prod(lf(r1), STAR(r1)) //may try infix notation later...... |
|
26 case SEQ(r1, r2) =>{ |
|
27 if (nullable(r1)) |
|
28 cir_prod(lf(r1), r2) ++ lf(r2) |
|
29 else |
|
30 cir_prod(lf(r1), r2) |
|
31 } |
|
32 } |
|
33 def lfs(r: Set[Rexp]): Lin = { |
|
34 r.foldLeft(Set[Mon]())((acc, r) => acc ++ lf(r)) |
|
35 } |
|
36 |
|
37 def pder(x: Char, t: Rexp): Set[Rexp] = { |
|
38 val lft = lf(t) |
|
39 (lft.filter(mon => if(mon._1 == x) true else false)).map(mon => mon._2) |
|
40 } |
|
41 def pders_single(s: List[Char], t: Rexp) : Set[Rexp] = s match { |
|
42 case x::xs => pders(xs, pder(x, t)) |
|
43 case Nil => Set(t) |
|
44 } |
|
45 def pders(s: List[Char], ts: Set[Rexp]) : Set[Rexp] = s match { |
|
46 case x::xs => pders(xs, ts.foldLeft(Set[Rexp]())((acc, t) => acc ++ pder(x, t))) |
|
47 case Nil => ts |
|
48 } |
|
49 def pderss(ss: List[List[Char]], t: Rexp): Set[Rexp] = ss.foldLeft( Set[Rexp]() )( (acc, s) => pders_single(s, t) ++ acc ) |
|
50 def pdera(t: Rexp): Set[Rexp] = lf(t).map(mon => mon._2) |
|
51 //all implementation of partial derivatives that involve set union are potentially buggy |
|
52 //because they don't include the original regular term before they are pdered. |
|
53 //now only pderas is fixed. |
|
54 def pderas(t: Set[Rexp], d: Int): Set[Rexp] = if(d > 0) pderas(lfs(t).map(mon => mon._2), d - 1) ++ t else lfs(t).map(mon => mon._2) ++ t//repeated application of pderas over the newest set of pders. |
|
55 |
|
56 def sigma_lf(l: Set[Mon]) : Rexp = ALTS(l.map(mon => SEQ(CHAR(mon._1),mon._2)).toList) |
|
57 def sigma(rs: Set[Rexp]) : Rexp = ALTS(rs.toList) |
|
58 def o(r: Rexp) = if (nullable(r)) ONE else ZERO |
|
59 def nlf(t: Rexp) : Rexp = ALTS(List( o(t), sigma_lf(lf(t)) )) |
|
60 def pdp(x: Char, r: Rexp) : Set[Rexp] = r match { |
|
61 case ZERO => Set[Rexp]() |
|
62 case ONE => Set[Rexp]() |
|
63 case CHAR(f) => if(x == f) Set(ONE) else Set[Rexp]() |
|
64 case ALTS(rs) => rs.foldLeft(Set[Rexp]())((acc, r) => acc ++ pdp(x, r)) |
|
65 case STAR(r1) => pdp(x, r).map(a => SEQ(a, STAR(r1))) |
|
66 case SEQ(a0, b) => if(nullable(a0)) pdp(x, a0).map(a => SEQ(a, b)) ++ pdp(x, b) else pdp(x, a0).map(a => SEQ(a, b)) |
|
67 } |
|
68 def pdps(s: List[Char], ts: Set[Rexp]): Set[Rexp] = s match { |
|
69 case x::xs => pdps(xs, ts.foldLeft(Set[Rexp]())((acc, t) => acc ++ pder(x, t))) |
|
70 case Nil => ts |
|
71 } |
|
72 def pdpss(ss: List[List[Char]], t: Rexp): Set[Rexp] = ss.foldLeft( Set[Rexp]())((acc, s) => pdps(s, Set(t)) ++ acc) |
|
73 |
|
74 //this function currently the problem of counting the same char as different ones |
|
75 //because they are defined as "pred" |
|
76 def subterms(r: Rexp): Set[Rexp] = {//excluding zeros. |
|
77 r match { |
|
78 case ZERO => { |
|
79 Set[Rexp]() |
|
80 } |
|
81 case SEQ(r1, r2) => { |
|
82 Set(r1, r2) ++ subterms(r1) ++ subterms(r2) |
|
83 } |
|
84 case ALTS(rs) => { |
|
85 rs.toSet ++ rs.foldLeft(Set[Rexp]())((acc, r) => acc ++ subterms(r)) |
|
86 } |
|
87 case STAR(r) => { |
|
88 Set(r) ++ subterms(r) |
|
89 } |
|
90 case r => Set(r) |
|
91 } |
|
92 } |
|
93 def comp(s: List[Char], t: Rexp) = { |
|
94 //var r = internalise(t) |
|
95 //var setr = Set(t) |
|
96 |
|
97 /*for(i <- 0 to s.length - 1){ |
|
98 val mamaipi = bsimp(bder(s(i), r)) |
|
99 val mamaimapi = pdps(List(s(i)), setr) |
|
100 //compare dersimp and pder w.r.t each character in string s |
|
101 println("current string: " + s.slice(0,i + 1)) |
|
102 println("der+simp: ") |
|
103 println(aregx_tree(mamaipi)) |
|
104 println("pder: ") |
|
105 mamaimapi.foreach(m => println(regx_tree(m))) |
|
106 r = mamaipi |
|
107 setr = mamaimapi |
|
108 }*/ |
|
109 for(i <- 1 to 10) |
|
110 println(pderas(Set(t), i).size, i) |
|
111 //val alphabet_star_t = pderas(Set(t), 10) |
|
112 //println("all possible elements in pder (probably...): ") |
|
113 //alphabet_star_t.foreach(r => println(regx_tree(r))) |
|
114 } |
|
115 } |
|
116 /* val delta = lfs(t).map(mon => mon._2) |
|
117 if(delta.size == t.size) |
|
118 { |
|
119 println(delta.size) |
|
120 println("steady: "+delta.size) |
|
121 return delta |
|
122 } |
|
123 |
|
124 else |
|
125 { |
|
126 val a = pderas(delta) |
|
127 println("increment: "+delta.size+a.size) |
|
128 return a |
|
129 }*/ |