Cleanup in aisle scala.util.automata! And fix f...

Cleanup in aisle scala.util.automata! And fix for #1988.

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 : _*)
 }