blob: 07b6afaeba60ebb9ec73f4fc876427db923ce258 (
plain) (
blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
|
/* __ *\
** ________ ___ / / ___ Scala API **
** / __/ __// _ | / / / _ | (c) 2003-2013, LAMP/EPFL **
** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ **
** /____/\___/_/ |_/____/_/ | | **
** |/ **
\* */
package scala
package xml.dtd.impl
/** A fast test of language inclusion between minimal automata.
* inspired by the ''AMoRE automata library''.
*
* @author Burak Emir
* @version 1.0
*/
@deprecated("This class will be removed", "2.10.0")
private[dtd] trait Inclusion[A <: AnyRef] {
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 (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
}
}
|
