regexp lib

11 files changed, 263 insertions, 77 deletions

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(')');