diff options
-rw-r--r-- | config/list/library.lst | 1 | ||||
-rw-r--r-- | sources/scala/collection/BitSet.scala | 9 | ||||
-rw-r--r-- | sources/scala/collection/immutable/BitSet.scala | 2 | ||||
-rw-r--r-- | sources/scala/collection/mutable/BitSet.scala | 2 | ||||
-rw-r--r-- | sources/scala/util/automata/DetWordAutom.scala | 18 | ||||
-rw-r--r-- | sources/scala/util/automata/NondetWordAutom.scala | 67 | ||||
-rw-r--r-- | sources/scala/util/automata/SubsetConstruction.scala | 143 | ||||
-rw-r--r-- | sources/scala/util/automata/WordBerrySethi.scala | 63 | ||||
-rw-r--r-- | sources/scala/util/regexp/Base.scala | 12 | ||||
-rw-r--r-- | sources/scala/util/regexp/PointedHedgeExp.scala | 8 | ||||
-rw-r--r-- | sources/scala/util/regexp/WordExp.scala | 6 | ||||
-rw-r--r-- | sources/scala/xml/dtd/ContentModel.scala | 10 |
12 files changed, 264 insertions, 77 deletions
diff --git a/config/list/library.lst b/config/list/library.lst index c0612d7d6a..fae335761d 100644 --- a/config/list/library.lst +++ b/config/list/library.lst @@ -194,6 +194,7 @@ util/automata/BaseBerrySethi.scala util/automata/DetWordAutom.scala util/automata/Inclusion.scala util/automata/NondetWordAutom.scala +util/automata/SubsetConstruction.scala util/automata/WordBerrySethi.scala util/grammar/HedgeRHS.scala #util/grammar/ImmutableTreeHedgeGrammar.scala diff --git a/sources/scala/collection/BitSet.scala b/sources/scala/collection/BitSet.scala index 6f93efe86d..aa77d59e60 100644 --- a/sources/scala/collection/BitSet.scala +++ b/sources/scala/collection/BitSet.scala @@ -59,14 +59,9 @@ abstract class BitSet with Function1[Int,Boolean] { }; /** - * returns an immutable bitset with same information + * applies f to any index which is set to true. */ - def makeImmutable: immutable.BitSet; - - /** - * returns a mutable bitset with same information - */ - def makeMutable: mutable.BitSet; + def foreach(f: Int => Unit): Unit = toSet(true).foreach(f); /** * Returns a string representation of this bitset in hexadecimal form, diff --git a/sources/scala/collection/immutable/BitSet.scala b/sources/scala/collection/immutable/BitSet.scala index 758278dc15..aa43a54c8f 100644 --- a/sources/scala/collection/immutable/BitSet.scala +++ b/sources/scala/collection/immutable/BitSet.scala @@ -98,8 +98,6 @@ class BitSet(n:Int, ba: Array[Int], copy: Boolean) extends collection.BitSet wit (array(j) & mask) != 0; } - def makeImmutable = this; - def makeMutable = { val rbs = new mutable.BitSet(size) ; val it = this.toSet(true).elements; diff --git a/sources/scala/collection/mutable/BitSet.scala b/sources/scala/collection/mutable/BitSet.scala index 5531e0c42d..6961ed2520 100644 --- a/sources/scala/collection/mutable/BitSet.scala +++ b/sources/scala/collection/mutable/BitSet.scala @@ -81,6 +81,4 @@ class BitSet(initSize: Int) extends scala.collection.BitSet { def makeImmutable = new scala.collection.immutable.BitSet(this); - /** returns this object */ - def makeMutable = this; } diff --git a/sources/scala/util/automata/DetWordAutom.scala b/sources/scala/util/automata/DetWordAutom.scala index 7a2829fc01..117454b4b4 100644 --- a/sources/scala/util/automata/DetWordAutom.scala +++ b/sources/scala/util/automata/DetWordAutom.scala @@ -9,16 +9,18 @@ import scala.collection.{ Set, Map }; * All states are reachable. Accepting states are those for which * the partial function 'finals' is defined. */ -abstract class DetWordAutom[A] { +abstract class DetWordAutom[T] { val nstates: Int; val finals: Array[Int] ; - val delta: Array[Map[A,Int]]; + val delta: Array[Map[T,Int]]; val default: Array[Int] ; - def isFinal(q:Int) = finals(q) != 0; + def isFinal(q: Int) = finals(q) != 0; - def next(q:Int, label:A) = { + def isSink(q: Int) = delta(q).isEmpty && default(q) == q; + + def next(q: Int, label: T) = { delta(q).get(label) match { case Some(p) => p case _ => default(q) @@ -26,16 +28,15 @@ abstract class DetWordAutom[A] { } override def toString() = { - "DetWordAutom" - /* val sb = new StringBuffer(); - sb.append("[nfa nstates="); + sb.append("[DetWordAutom nstates="); sb.append(nstates); sb.append(" finals="); var map = new scala.collection.immutable.ListMap[Int,Int]; var j = 0; while( j < nstates ) { if(finals.isDefinedAt(j)) - map = map.update(j,finals(j)) + map = map.update(j,finals(j)); + j = j + 1; } sb.append(map.toString()); sb.append(" delta=\n"); @@ -51,6 +52,5 @@ abstract class DetWordAutom[A] { } } sb.toString(); - */ } } diff --git a/sources/scala/util/automata/NondetWordAutom.scala b/sources/scala/util/automata/NondetWordAutom.scala index be4347459e..ee0b2cc07d 100644 --- a/sources/scala/util/automata/NondetWordAutom.scala +++ b/sources/scala/util/automata/NondetWordAutom.scala @@ -1,6 +1,6 @@ package scala.util.automata ; -import scala.collection.{ Set, Map }; +import scala.collection.{ immutable, mutable, Set, Map }; /** A nondeterministic automaton. States are integers, where * 0 is always the only initial state. Transitions are represented @@ -11,22 +11,24 @@ import scala.collection.{ Set, Map }; */ abstract class NondetWordAutom { - type T_label; + type _labelT; val nstates: Int; - val finals: Array[Int] ; // -1 means not final - val delta: Array[Map[T_label,List[Int]]]; - val default: Array[List[Int]]; + val labels: Seq[_labelT]; + + val finals: Array[Int] ; // 0 means not final + val delta: Array[Map[_labelT, immutable.BitSet]]; + val default: Array[immutable.BitSet]; /** returns true if the state is final */ - final def isFinal(state: Int) = finals( state ) > -1; + final def isFinal(state: Int) = finals( state ) > 0; /** returns tag of final state */ final def finalTag(state: Int) = finals( state ); /** returns true if the set of states contains at least one final state */ - final def containsFinal(Q: Set[Int]):Boolean = { - val it = Q.elements; + final def containsFinal(Q: immutable.BitSet): Boolean = { + val it = Q.toSet(true).elements; while( it.hasNext ) if( isFinal( it.next )) return true; @@ -43,30 +45,59 @@ abstract class NondetWordAutom { r } + /** returns a bitset with the next states for given state and label */ + def next(q:Int, a: _labelT): immutable.BitSet = { + delta(q).get(a).match { + case Some(bs) => bs + case _ => default(q) + } + } + + /** returns a bitset with the next states for given state and label */ + def next(Q:immutable.BitSet, a: _labelT): immutable.BitSet = { + val x = new mutable.BitSet(nstates); + for(val q <- Q.toSet(true)) { + for(val i <- next(q,a).toSet(true)) { + x.set(i); + } + } + x.makeImmutable + } + + + def nextDefault(Q:immutable.BitSet): immutable.BitSet = { + val x = new mutable.BitSet(nstates); + for(val q <- Q.toSet(true)) { + for(val i <- default(q).toSet(true)) { //@todo: OR + x.set(i) + } + } + x.makeImmutable; + } + override def toString() = { - "NondetWordAutom" - /* val sb = new StringBuffer(); - sb.append("[nfa nstates="); + sb.append("[NondetWordAutom nstates="); sb.append(nstates); - sb.append(" finals="); + sb.append(" finals="); var map = new scala.collection.immutable.ListMap[Int,Int]; var j = 0; while( j < nstates ) { - if(finals.isDefinedAt(j)) - map = map.update(j,finals(j)) + if(isFinal(j)) + map = map.update(j,finals(j)); + j = j + 1; } sb.append(map.toString()); - sb.append(" delta=\n"); + sb.append(" delta=\n"); for( val i <- Iterator.range(0,nstates)) { + sb.append(" "); sb.append( i ); sb.append("->"); sb.append(delta(i).toString()); - sb.append('\n'); + sb.append("\n "); sb.append(" _>"); - sb.append(default(i).mkString("",",","")); + sb.append(default(i).toString()); sb.append('\n'); } sb.toString(); - */ } } diff --git a/sources/scala/util/automata/SubsetConstruction.scala b/sources/scala/util/automata/SubsetConstruction.scala new file mode 100644 index 0000000000..ac08ef02e3 --- /dev/null +++ b/sources/scala/util/automata/SubsetConstruction.scala @@ -0,0 +1,143 @@ +package scala.util.automata ; + +class SubsetConstruction(val nfa: NondetWordAutom) { + + import nfa.{ _labelT, labels }; + + import scala.collection.{immutable, mutable, Map} ; + + import immutable.{ BitSet, TreeMap, TreeSet } ; + + /** the set {0} */ + final val _initialBitSet = { + val rbs = new mutable.BitSet(1); + rbs.set(0); + rbs.makeImmutable; + } + + /** the set {} */ + final val _sinkBitSet = { + new mutable.BitSet(1).makeImmutable; + } + + final val _emptyBitSet = { + val rbs = new scala.collection.mutable.BitSet(1); + new BitSet(rbs); + } + + def selectTag(Q:BitSet, finals:Array[Int]) = { + val it = Q.toSet(true).elements; + var mintag = java.lang.Integer.MAX_VALUE; + while(it.hasNext) { + val tag = finals(it.next); + if((0 < tag) && (tag < mintag)) + mintag = tag + } + mintag + } + + def determinize: DetWordAutom[_labelT] = { + + // for assigning numbers to bitsets + var indexMap = new TreeMap[ BitSet, Int ]; + var invIndexMap = new TreeMap[ Int, BitSet ]; + var ix = 0; + + // we compute the dfa with states = bitsets + var states = new TreeSet[BitSet](); + val delta = new mutable.HashMap[BitSet, + mutable.HashMap[_labelT, BitSet]]; + var deftrans = new TreeMap[BitSet, BitSet]; + var finals = new TreeMap[BitSet, Int]; + + val q0 = _initialBitSet; + states = states + q0; + + val sink = _emptyBitSet; + states = states + sink; + + deftrans = deftrans.update(q0,sink); + deftrans = deftrans.update(sink,sink); + + val rest = new mutable.Stack[BitSet](); + + def add(Q: BitSet): Unit = { + if(!states.contains(Q)) { + states = states + Q; + rest.push(Q); + if(nfa.containsFinal(Q)) + finals = finals.update(Q, selectTag(Q,nfa.finals)); + } + } + rest.push( sink ); + val sinkIndex = 1; + rest.push( q0 ); + while(!rest.isEmpty) { + // assign a number to this bitset + val P = rest.pop; + indexMap = indexMap.update(P,ix); + invIndexMap = invIndexMap.update(ix,P); + ix = ix + 1; + + // make transitiion map + val Pdelta = new mutable.HashMap[_labelT, BitSet]; + delta.update( P, Pdelta ); + + val it = labels.elements; while(it.hasNext) { + val label = it.next; + + val Q = nfa.next(P,label); + + Pdelta.update( label, Q ); + + add(Q); + } + + // collect default transitions + val Pdef = nfa.nextDefault(P); + deftrans = deftrans.update(P,Pdef); + add(Pdef); + }; + + // create DetWordAutom, using indices instead of sets + val nstatesR = states.size; + val deltaR = new Array[Map[_labelT,Int]](nstatesR); + val defaultR = new Array[Int](nstatesR); + val finalsR = new Array[Int](nstatesR); + + for(val w <- states) { + val Q = w; + val q = indexMap(Q); + val trans = delta(Q); + val transDef = deftrans(Q); + val qDef = indexMap(transDef); + val ntrans = new mutable.HashMap[_labelT,Int](); + val it = trans.keys; while(it.hasNext) { + val label = it.next; + val p = indexMap(trans(label)); + if( p != qDef ) + ntrans.update(label, p) + } + deltaR.update(q, ntrans); + defaultR.update(q, qDef); + + //cleanup? leave to garbage collector? + //delta.remove(Q); + //default.remove(Q); + + } + + for(val fQ <- finals.keys) { + finalsR(indexMap(fQ)) = finals(fQ); + } + + new DetWordAutom [ _labelT ] { + + //type _labelT = SubsetConstruction.this.nfa._labelT; + val nstates = nstatesR; + val delta = deltaR; + val default = defaultR; + val finals = finalsR; + } + } +} diff --git a/sources/scala/util/automata/WordBerrySethi.scala b/sources/scala/util/automata/WordBerrySethi.scala index 49203c08c2..517c8643dd 100644 --- a/sources/scala/util/automata/WordBerrySethi.scala +++ b/sources/scala/util/automata/WordBerrySethi.scala @@ -14,16 +14,16 @@ abstract class WordBerrySethi extends BaseBerrySethi { override val lang: WordExp; - type T_label = this.lang.T_label; + type _labelT = this.lang._labelT; import lang.{Alt, Eps, Letter, Meta, RegExp, Sequ, Star} ; - protected var labels:mutable.HashSet[T_label] = _ ; + protected var labels:mutable.HashSet[_labelT] = _ ; // don't let this fool you, only labelAt is a real, surjective mapping - protected var labelAt: immutable.TreeMap[Int, T_label] = _; // new alphabet "gamma" + protected var labelAt: immutable.TreeMap[Int, _labelT] = _; // new alphabet "gamma" - protected var deltaq: Array[mutable.HashMap[T_label,List[Int]]] = _; // delta + protected var deltaq: Array[mutable.HashMap[_labelT,List[Int]]] = _; // delta protected var defaultq: Array[List[Int]] = _; // default transitions @@ -63,7 +63,7 @@ abstract class WordBerrySethi extends BaseBerrySethi { /** called at the leaves of the regexp */ - protected def seenLabel( r:RegExp, i:Int, label: T_label ): Unit = { + protected def seenLabel( r:RegExp, i:Int, label: _labelT ): Unit = { this.posMap.update( r, i ); this.labelAt = this.labelAt.update( i, label ); //@ifdef if( label != Wildcard ) { @@ -72,7 +72,7 @@ abstract class WordBerrySethi extends BaseBerrySethi { } // overriden in BindingBerrySethi - protected def seenLabel( r: RegExp, label: T_label ): Unit = { + protected def seenLabel( r: RegExp, label: _labelT ): Unit = { pos = pos + 1; seenLabel( r, pos, label ); } @@ -85,7 +85,7 @@ abstract class WordBerrySethi extends BaseBerrySethi { } - protected def makeTransition(src: Int, dest:Int, label: T_label ):Unit = { + protected def makeTransition(src: Int, dest:Int, label: _labelT ):Unit = { //@ifdef compiler if( label == Wildcard ) //@ifdef compiler defaultq.update(src, dest::defaultq( src )) //@ifdef compiler else @@ -98,9 +98,9 @@ abstract class WordBerrySethi extends BaseBerrySethi { protected def initialize(subexpr: Seq[RegExp]): Unit = { this.posMap = new mutable.HashMap[RegExp,Int](); - this.labelAt = new immutable.TreeMap[Int,T_label](); + this.labelAt = new immutable.TreeMap[Int,_labelT](); this.follow = new mutable.HashMap[Int,immutable.Set[Int]](); - this.labels = new mutable.HashSet[T_label](); + this.labels = new mutable.HashSet[_labelT](); this.pos = 0; @@ -117,12 +117,12 @@ abstract class WordBerrySethi extends BaseBerrySethi { protected def initializeAutom(): Unit = { finals = immutable.TreeMap.Empty[Int,Int]; // final states - deltaq = new Array[mutable.HashMap[T_label,List[Int]]]( pos ); // delta + deltaq = new Array[mutable.HashMap[_labelT,List[Int]]]( pos ); // delta defaultq = new Array[List[Int]]( pos ); // default transitions var j = 0; while( j < pos ) { - deltaq( j ) = new mutable.HashMap[T_label,List[Int]](); + deltaq( j ) = new mutable.HashMap[_labelT,List[Int]](); defaultq( j ) = Nil; j = j + 1 } @@ -135,9 +135,9 @@ abstract class WordBerrySethi extends BaseBerrySethi { while( it.hasNext ) { val k = it.next; if( pos == k ) - finals = finals.update( k, finalTag ) + finals = finals.update( j, finalTag ) else - makeTransition( j, k, labelAt( k )) + makeTransition( j, k, labelAt( k )); } j = j + 1; } @@ -161,8 +161,8 @@ abstract class WordBerrySethi extends BaseBerrySethi { if( x.isNullable ) // initial state is final finals = finals.update( 0, finalTag ); - var delta1: immutable.TreeMap[Int,Map[T_label,List[Int]]] = - new immutable.TreeMap[Int,Map[T_label,List[Int]]]; + var delta1: immutable.TreeMap[Int,Map[_labelT,List[Int]]] = + new immutable.TreeMap[Int,Map[_labelT,List[Int]]]; var i = 0; while( i < deltaq.length ) { @@ -174,7 +174,7 @@ abstract class WordBerrySethi extends BaseBerrySethi { var k = 0; while(k < pos) { finalsArr(k) = finals.get(k).match { case Some(z) => z; - case None => -1; + case None => 0; // 0 == not final }; k = k + 1; } @@ -189,21 +189,42 @@ abstract class WordBerrySethi extends BaseBerrySethi { } } - val deltaArr = new Array[Map[T_label,List[Int]]](pos); + val deltaArr = new Array[Map[_labelT,immutable.BitSet]](pos); { var k = 0; while(k < pos) { - deltaArr(k) = delta1(k); + val labels = delta1(k).keys; + val hmap = + new mutable.HashMap[_labelT,immutable.BitSet]; + for(val lab <- labels) { + val trans = delta1(k); + val x = new mutable.BitSet(pos); + for(val q <- trans(lab)) + x.set(q); + hmap.update(lab, x.makeImmutable); + } + deltaArr(k) = hmap; k = k + 1; } } + val defaultArr = new Array[immutable.BitSet](pos); + { + var k = 0; while(k < pos) { + val x = new mutable.BitSet(pos); + for(val q <- defaultq(k)) + x.set(q); + defaultArr(k) = x.makeImmutable; + k = k + 1; + } + } + new NondetWordAutom { - type T_label = WordBerrySethi.this.T_label; + type _labelT = WordBerrySethi.this._labelT; val nstates = pos; - //val labels = WordBerrySethi.this.labels; + val labels = WordBerrySethi.this.labels.toList; val initials = initialsArr; val finals = finalsArr; val delta = deltaArr; - val default = defaultq; + val default = defaultArr; } case _ => error("expected Sequ"); } diff --git a/sources/scala/util/regexp/Base.scala b/sources/scala/util/regexp/Base.scala index ccaa820663..cfdaaac10f 100644 --- a/sources/scala/util/regexp/Base.scala +++ b/sources/scala/util/regexp/Base.scala @@ -6,14 +6,14 @@ package scala.util.regexp ; trait Base { - type regexp <: RegExp; + type _regexpT <: RegExp; abstract class RegExp { val isNullable:Boolean; } /** Alt( R,R,R* ) */ - case class Alt(rs: regexp*) extends RegExp { + case class Alt(rs: _regexpT*) extends RegExp { // check rs \in R,R,R* // @todo: flattening @@ -26,7 +26,7 @@ trait Base { !it.hasNext } } - case class Sequ(rs: regexp*) extends RegExp { + case class Sequ(rs: _regexpT*) extends RegExp { // @todo: flattening // check rs \in R,R* if({ val it = rs.elements; !it.hasNext }) @@ -39,7 +39,7 @@ trait Base { } } - case class Star(r: regexp) extends RegExp { + case class Star(r: _regexpT) extends RegExp { final val isNullable = true; } @@ -49,12 +49,12 @@ trait Base { } /** this class can be used to add meta information to regexps */ - class Meta( r1:regexp ) extends RegExp { + class Meta( r1: _regexpT ) extends RegExp { final val isNullable = r1.isNullable; def r = r1; } - final def mkSequ(rs: regexp*): RegExp = + final def mkSequ(rs: _regexpT *): RegExp = if(!rs.elements.hasNext) Eps else diff --git a/sources/scala/util/regexp/PointedHedgeExp.scala b/sources/scala/util/regexp/PointedHedgeExp.scala index cd32021d7f..27da6338db 100644 --- a/sources/scala/util/regexp/PointedHedgeExp.scala +++ b/sources/scala/util/regexp/PointedHedgeExp.scala @@ -7,14 +7,14 @@ package scala.util.regexp ; */ trait PointedHedgeExp extends Base { - type T_label; - type regexp <: RegExp; + type _regexpT <: RegExp; + type _labelT; - case class Node(label: T_label, r: regexp) extends RegExp { + case class Node(label: _labelT, r: _regexpT) extends RegExp { final val isNullable = false; } - case class TopIter(r1: regexp, r2: regexp) extends RegExp { + case class TopIter(r1: _regexpT, r2: _regexpT) extends RegExp { final val isNullable = r1.isNullable && r2.isNullable; //? } diff --git a/sources/scala/util/regexp/WordExp.scala b/sources/scala/util/regexp/WordExp.scala index 14557d9578..a2c006ac50 100644 --- a/sources/scala/util/regexp/WordExp.scala +++ b/sources/scala/util/regexp/WordExp.scala @@ -13,10 +13,10 @@ trait WordExp extends Base { trait Label; - type T_label <: Label; - type regexp <: RegExp ; + type _regexpT <: RegExp ; + type _labelT <: Label; - case class Letter(a: T_label) extends RegExp { + case class Letter(a: _labelT) extends RegExp { final val isNullable = false; } diff --git a/sources/scala/xml/dtd/ContentModel.scala b/sources/scala/xml/dtd/ContentModel.scala index 09fd89d7e9..a0d8bcf059 100644 --- a/sources/scala/xml/dtd/ContentModel.scala +++ b/sources/scala/xml/dtd/ContentModel.scala @@ -2,8 +2,8 @@ package scala.xml.dtd ; object ContentModel extends scala.util.regexp.WordExp { - type T_label = ElemName; - type regexp = RegExp; + type _labelT = ElemName; + type _regexpT = RegExp; case class ElemName(name: String) extends Label { override def toString() = "ElemName(\""+name+"\")"; @@ -21,7 +21,7 @@ object ContentModel extends scala.util.regexp.WordExp { def parse(s: String): RegExp = Parser.parse( s ); - def isMixed(alt:Alt):boolean = { + def isMixed(alt: Alt): Boolean = { val it = alt.rs.elements; it.next == PCDATA_ && { while( it.hasNext && it.next.isInstanceOf[Letter] ) {} ; @@ -29,7 +29,7 @@ object ContentModel extends scala.util.regexp.WordExp { } } - def getLabels(r:RegExp): scala.collection.Set[String] = { + def getLabels(r: RegExp): scala.collection.Set[String] = { val s = new scala.collection.mutable.HashSet[String](); def traverse1(xs: Seq[RegExp]): Unit = { val it = xs.elements; @@ -77,7 +77,7 @@ object ContentModel extends scala.util.regexp.WordExp { case Alt(rs @ _*) => sb.append("Alt"); toString(rs, sb); - case Star(r:RegExp) => + case Star(r: RegExp) => sb.append("Star("); toString(r, sb); sb.append(')'); |