diff options
-rw-r--r-- | src/library/scala/util/automata/NondetWordAutom.scala | 79 | ||||
-rw-r--r-- | src/library/scala/util/automata/SubsetConstruction.scala | 137 | ||||
-rw-r--r-- | src/library/scala/util/regexp/Base.scala | 31 |
3 files changed, 58 insertions, 189 deletions
diff --git a/src/library/scala/util/automata/NondetWordAutom.scala b/src/library/scala/util/automata/NondetWordAutom.scala index 66f49360ac..b9c1e2ddef 100644 --- a/src/library/scala/util/automata/NondetWordAutom.scala +++ b/src/library/scala/util/automata/NondetWordAutom.scala @@ -11,7 +11,6 @@ package scala.util.automata - import scala.collection.{immutable, mutable, Set, Map} /** A nondeterministic automaton. States are integers, where @@ -21,8 +20,8 @@ import scala.collection.{immutable, mutable, Set, Map} * All states are reachable. Accepting states are those for which * the partial function 'finals' is defined. */ -abstract class NondetWordAutom[T <: AnyRef] { - +abstract class NondetWordAutom[T <: AnyRef] +{ val nstates: Int val labels: Seq[T] @@ -37,76 +36,26 @@ abstract class NondetWordAutom[T <: AnyRef] { final def finalTag(state: Int) = finals(state) /** returns true if the set of states contains at least one final state */ - final def containsFinal(Q: immutable.BitSet): Boolean = { - val it = Q.elements - while (it.hasNext) - if (isFinal(it.next)) - return true - return false - } + final def containsFinal(Q: immutable.BitSet): Boolean = Q exists isFinal /** returns true if there are no accepting states */ - final def isEmpty = { - var r = true - var j = 0; while(r && (j < nstates)) { - if (isFinal(j)) - r = false - } - r - } + final def isEmpty = (0 until nstates) forall (x => !isFinal(x)) /** returns a bitset with the next states for given state and label */ - def next(q: Int, a: T): immutable.BitSet = { - delta(q).get(a) match { - case Some(bs) => bs - case _ => default(q) - } - } + def next(q: Int, a: T): immutable.BitSet = delta(q).get(a) getOrElse default(q) /** returns a bitset with the next states for given state and label */ - def next(Q: immutable.BitSet, a: T): immutable.BitSet = { - val x = new mutable.BitSet(nstates) - for (q <- Q) { - for (i <- next(q,a)) { - x += i - } - } - x.toImmutable - } - + def next(Q: immutable.BitSet, a: T): immutable.BitSet = next(Q, next(_, a)) + def nextDefault(Q: immutable.BitSet): immutable.BitSet = next(Q, default) - def nextDefault(Q: immutable.BitSet): immutable.BitSet = { - val x = new mutable.BitSet(nstates) - for (q <- Q) { - for (i <- default(q)) { //@todo: OR - x += i - } - } - x.toImmutable - } + private def next(Q: immutable.BitSet, f: (Int) => immutable.BitSet): immutable.BitSet = + (Q map f).foldLeft(immutable.BitSet.empty)(_ ++ _) override def toString = { - val sb = new StringBuilder("[NondetWordAutom nstates=") - sb.append(nstates) - sb.append(" finals=") - var map = scala.collection.immutable.Map[Int,Int]() - var j = 0; while (j < nstates) { - if (isFinal(j)) - map = map.updated(j, finals(j)); - j += 1 - } - sb.append(map.toString) - sb.append(" delta=\n") - for (i <- 0 until nstates) { - sb.append(" ") - sb.append( i ) - sb.append("->") - sb.append(delta(i).toString) - sb.append("\n ") - sb.append(" _>") - sb.append(default(i).toString) - sb.append('\n') - } - sb.toString() + val finalString = Map(0 until nstates filter isFinal map (j => j -> finals(j)) : _*).toString + val deltaString = (0 until nstates) . + map (i => " %d->%s\n _>%s\n".format(i, delta(i).toString, default(i).toString)) mkString + + "[NondetWordAutom nstates=%d finals=%s delta=\n%s".format(nstates, finalString, deltaString) } } diff --git a/src/library/scala/util/automata/SubsetConstruction.scala b/src/library/scala/util/automata/SubsetConstruction.scala index 314704d44e..2dcad6d006 100644 --- a/src/library/scala/util/automata/SubsetConstruction.scala +++ b/src/library/scala/util/automata/SubsetConstruction.scala @@ -8,131 +8,70 @@ // $Id$ - package scala.util.automata - class SubsetConstruction[T <: AnyRef](val nfa: NondetWordAutom[T]) { import nfa.labels - import scala.collection.{immutable, mutable, Map} - import immutable.BitSet - - implicit def toOrdered(bs: BitSet): Ordered[BitSet] = new Ordered[BitSet] { - def compare(that: BitSet): Int = { - val it1 = bs.elements - val it2 = that.elements - var res = 0 - while((0 == res) && it1.hasNext) { - while((0 == res) && it2.hasNext) { - if (!it1.hasNext) - res = -1 - else { - val i1 = it1.next - val i2 = it2.next - if (i1 < i2) - res = -1 - else if (i1 > i2) - res = 1 - } - } - if (it1.hasNext) - res = 1 - } - if (it2.hasNext) - res = -1 - res - } - - override def equals(other: Any): Boolean = - other match { case that: BitSet => compare(that) == 0 - case that: AnyRef => this.eq(that) - case _ => false } + import collection.{ mutable, Map } + import collection.immutable.BitSet - //case _ => -(other.compare(this)) - } - - /** the set {0} */ - final val _initialBitSet = { - val rbs = new mutable.BitSet(1) - rbs += 0 - rbs.toImmutable - } - - /** the set {} */ - final val _sinkBitSet = new mutable.BitSet(1).toImmutable - - final val _emptyBitSet = new scala.collection.mutable.BitSet(1).toImmutable - - def selectTag(Q: BitSet, finals: Array[Int]) = { - val it = Q.elements - var mintag = Math.MAX_INT - while (it.hasNext) { - val tag = finals(it.next) - if ((0 < tag) && (tag < mintag)) - mintag = tag - } - mintag - } + def selectTag(Q: BitSet, finals: Array[Int]) = + Q map finals filter (_ > 0) min def determinize: DetWordAutom[T] = { - // for assigning numbers to bitsets var indexMap = Map[BitSet, Int]() var invIndexMap = Map[Int, BitSet]() var ix = 0 // we compute the dfa with states = bitsets - var states = Set[BitSet]() - val delta = new mutable.HashMap[BitSet, - mutable.HashMap[T, BitSet]] - var deftrans = Map[BitSet, BitSet]() - var finals = Map[BitSet, Int]() + val q0 = BitSet(0) // the set { 0 } + val sink = BitSet.empty // the set { } - val q0 = _initialBitSet - states = states + q0 + var states = Set(q0, sink) // initial set of sets + val delta = new mutable.HashMap[BitSet, mutable.HashMap[T, BitSet]] + var deftrans = Map(q0 -> sink, sink -> sink) // initial transitions + var finals: Map[BitSet, Int] = Map() - val sink = _emptyBitSet - states = states + sink - - deftrans = deftrans.updated(q0,sink); - deftrans = deftrans.updated(sink,sink); - - val rest = new mutable.ArrayStack[BitSet](); + val rest = new mutable.Stack[BitSet] + rest.push(sink, q0) + def addFinal(q: BitSet) { + if (nfa containsFinal q) + finals = finals.updated(q, selectTag(q, nfa.finals)) + } def add(Q: BitSet) { if (!states.contains(Q)) { states = states + Q - rest.push(Q) - if (nfa.containsFinal(Q)) - finals = finals.updated(Q, selectTag(Q,nfa.finals)); + rest push Q + addFinal(Q) } } - rest.push(sink) - val sinkIndex = 1 - rest.push(q0) + + addFinal(q0) // initial state may also be a final state + while (!rest.isEmpty) { - // assign a number to this bitset val P = rest.pop - indexMap = indexMap.updated(P,ix) - invIndexMap = invIndexMap.updated(ix,P) + // assign a number to this bitset + indexMap = indexMap.updated(P, ix) + invIndexMap = invIndexMap.updated(ix, P) ix += 1 // make transitiion map val Pdelta = new mutable.HashMap[T, 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) + labels foreach { label => + val Q = nfa.next(P, label) + Pdelta.update(label, Q) add(Q) } // collect default transitions - val Pdef = nfa.nextDefault(P) + val Pdef = nfa nextDefault P deftrans = deftrans.updated(P, Pdef) add(Pdef) - }; + } // create DetWordAutom, using indices instead of sets val nstatesR = states.size @@ -140,32 +79,26 @@ class SubsetConstruction[T <: AnyRef](val nfa: NondetWordAutom[T]) { val defaultR = new Array[Int](nstatesR) val finalsR = new Array[Int](nstatesR) - for (w <- states) { - val Q = w + for (Q <- states) { val q = indexMap(Q) val trans = delta(Q) val transDef = deftrans(Q) val qDef = indexMap(transDef) val ntrans = new mutable.HashMap[T,Int]() - val it = trans.keys; while(it.hasNext) { - val label = it.next - val p = indexMap(trans(label)) + + for ((label, value) <- trans) { + val p = indexMap(value) if (p != qDef) ntrans.update(label, p) } + deltaR(q) = ntrans defaultR(q) = qDef - - //cleanup? leave to garbage collector? - //delta.remove(Q); - //default.remove(Q); - } - for (fQ <- finals.keys) finalsR(indexMap(fQ)) = finals(fQ) + finals foreach { case (k,v) => finalsR(indexMap(k)) = v } new DetWordAutom [T] { - //type _labelT = SubsetConstruction.this.nfa._labelT; val nstates = nstatesR val delta = deltaR val default = defaultR diff --git a/src/library/scala/util/regexp/Base.scala b/src/library/scala/util/regexp/Base.scala index 091b617770..6ef0392c30 100644 --- a/src/library/scala/util/regexp/Base.scala +++ b/src/library/scala/util/regexp/Base.scala @@ -16,8 +16,8 @@ package scala.util.regexp * @author Burak Emir * @version 1.0 */ -abstract class Base { - +abstract class Base +{ type _regexpT <: RegExp abstract class RegExp { @@ -25,31 +25,22 @@ abstract class Base { } /** Alt( R,R,R* ) */ - case class Alt(rs: _regexpT*) extends RegExp { - + case class Alt(rs: _regexpT*) extends RegExp { // check rs \in R,R,R* // @todo: flattening - if ({ val it = rs.elements; !it.hasNext || {it.next; !it.hasNext }}) - throw new SyntaxError("need at least 2 branches in Alt"); + if (rs.size < 2) + throw new SyntaxError("need at least 2 branches in Alt") - final val isNullable = { - val it = rs.elements - while (it.hasNext && it.next.isNullable) {} - !it.hasNext - } + final val isNullable = rs forall (_.isNullable) } case class Sequ(rs: _regexpT*) extends RegExp { // @todo: flattening // check rs \in R,R* - if ({ val it = rs.elements; !it.hasNext }) + if (rs.isEmpty) throw new SyntaxError("need at least 1 item in Sequ") - final val isNullable = { - val it = rs.elements - while (it.hasNext && it.next.isNullable) {} - !it.hasNext - } + final val isNullable = rs forall (_.isNullable) } case class Star(r: _regexpT) extends RegExp { @@ -68,9 +59,5 @@ abstract class Base { } final def mkSequ(rs: _regexpT *): RegExp = - if (!rs.elements.hasNext) - Eps - else - Sequ(rs:_*) - + if (rs.isEmpty) Eps else Sequ(rs : _*) } |