From 55fb705ed917a21b8553c2cc6e82e351da6e5c82 Mon Sep 17 00:00:00 2001
From: buraq <buraq@epfl.ch>
Date: Thu, 18 Nov 2004 11:01:46 +0000
Subject: hello

---
 config/list/library.lst                        |  5 +++
 sources/scala/util/automata/DetWordAutom.scala | 15 +++++--
 sources/scala/util/automata/Inclusion.scala    | 55 ++++++++++++++++++++++++++
 3 files changed, 71 insertions(+), 4 deletions(-)
 create mode 100644 sources/scala/util/automata/Inclusion.scala

diff --git a/config/list/library.lst b/config/list/library.lst
index 506ac01955..c0612d7d6a 100644
--- a/config/list/library.lst
+++ b/config/list/library.lst
@@ -192,6 +192,7 @@ testing/Benchmark.scala
 
 util/automata/BaseBerrySethi.scala
 util/automata/DetWordAutom.scala
+util/automata/Inclusion.scala
 util/automata/NondetWordAutom.scala
 util/automata/WordBerrySethi.scala
 util/grammar/HedgeRHS.scala
@@ -252,4 +253,8 @@ xml/parsing/MarkupParser.scala
 xml/parsing/XSDHandler.scala
 xml/path/Expression.scala
 
+xml/transform/BasicTransformer.scala
+xml/transform/RewriteRule.scala
+xml/transform/RuleTransformer.scala
+
 ##############################################################################
diff --git a/sources/scala/util/automata/DetWordAutom.scala b/sources/scala/util/automata/DetWordAutom.scala
index a33ab098ef..7a2829fc01 100644
--- a/sources/scala/util/automata/DetWordAutom.scala
+++ b/sources/scala/util/automata/DetWordAutom.scala
@@ -9,15 +9,22 @@ import scala.collection.{ Set, Map };
  *  All states are reachable. Accepting states are those for which
  *  the partial function 'finals' is defined.
  */
-abstract class DetWordAutom {
-
-  type T_label;
+abstract class DetWordAutom[A] {
 
   val nstates:  Int;
   val finals:   Array[Int] ;
-  val delta:    Array[Map[T_label,Int]];
+  val delta:    Array[Map[A,Int]];
   val default:  Array[Int] ;
 
+  def isFinal(q:Int) = finals(q) != 0;
+
+  def next(q:Int, label:A) = {
+    delta(q).get(label) match {
+      case Some(p) => p
+      case _       => default(q)
+    }
+  }
+
   override def toString() = {
     "DetWordAutom"
     /*
diff --git a/sources/scala/util/automata/Inclusion.scala b/sources/scala/util/automata/Inclusion.scala
new file mode 100644
index 0000000000..6f1eee3c09
--- /dev/null
+++ b/sources/scala/util/automata/Inclusion.scala
@@ -0,0 +1,55 @@
+package scala.util.automata ;
+
+/** a fast test of language inclusion between minimal automata.
+ *  inspired by the AMoRE automata library
+ *  @author Burak
+ */
+trait Inclusion[A] {
+
+  val labels: Seq[A];
+
+  /** returns true if dfa1 is included in dfa2 */
+  def inclusion(dfa1: DetWordAutom[A], dfa2: DetWordAutom[A]) = {
+
+    def encode(q1:Int, q2:Int) = 1 + q1 + q2 * dfa1.nstates;
+    def decode2(c:Int) = (c-1) / (dfa1.nstates); //integer division
+    def decode1(c:Int) = (c-1) % (dfa1.nstates);
+
+    var q1 = 0; //dfa1.initstate; // == 0
+    var q2 = 0; //dfa2.initstate; // == 0
+
+    val max = 1 + dfa1.nstates * dfa2.nstates;
+    val mark = new Array[Int](max);
+
+    var result = true;
+    var current = encode(q1,q2);
+    var last = current;
+    mark(last) = max; // mark (q1,q2)
+    while(current != 0 && result) {
+      //Console.println("current = [["+q1+" "+q2+"]] = "+current);
+      for(val letter <- labels) {
+        val r1 = dfa1.next(q1,letter);
+        val r2 = dfa2.next(q2,letter);
+        if(dfa1.isFinal(r1) && !dfa2.isFinal(r2))
+	  result = false;
+        val test = encode(r1,r2);
+        //Console.println("test = [["+r1+" "+r2+"]] = "+test);
+        if(mark(test) == 0) {
+	  mark(last) = test;
+	  mark(test) = max;
+	  last = test;
+        }
+      }
+      val ncurrent = mark(current);
+      if( ncurrent != max ) {
+        q1 = decode1(ncurrent);
+        q2 = decode2(ncurrent);
+        current = ncurrent
+      } else {
+        current = 0
+      }
+    }
+    result
+  }
+
+}
-- 
cgit v1.2.3