favila · March 6, 2015 04:23
diff --git a/jforms.html b/jforms.html
 <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd">
 <html lang="en">
 <head>
 <meta http-equiv="Content-Type" content="text/html; charset=utf-8">
 <title>xforms dependency algorithm</title>
 </head>
 <body>
 <div>
    <form action="" method="post" accept-charset="utf-8">
        <ol style="list-style-type:lower-latin">
            <li><input type="text" id="a" value="0"></li>
            <li><input type="text" id="b" value="0"></li>
            <li><input type="text" id="c" value="0" readonly="readonly"> a*b &lt;=100</li>
            <li><input type="text" id="d" value="0" readonly="readonly"> a+b &lt;=20</li>
        </ol>
    </form>
 </div>
 <div>
 <script type="text/javascript">
 // <![CDATA[
 var VertexType = {
    NULL:null,
    VALUE:1,
    CALCULATE:2,
    RELEVANT:3,
    READONLY:4,
    REQUIRED:5,
    CONSTRAINT:6
 };

 function Vertex(type, instancenode) {
    this.InstanceNode = instancenode || null;//a reference to the associated instance data node
    this.type = type || VertexType.NULL; //indicates the aspect of the instance node represented by the vertex (the text content or a model item property such as readOnly or required)
    this.depList = [];     // a list of vertices that refer to this vertex
    this.inDegree = 0;      // the number of vertices on which this vertex depends
    this.visited = false;     // a flag used to ensure vertices are not added to a subgraph multiple times
    this.index = null;       // an association between vertices in the master dependency directed graph and a subgraph
 }
 Vertex.prototype.clone = function() {
    var v = new this.constructor(this.type, this.InstanceNode);
    return v;
 };
 Vertex.prototype.recalculate = function() {
    switch (this.type) {
        case VertexType.CALCULATE:
            this.InstanceNode.value = this.InstanceNode.calc();
            break;
        case VertexType.CONSTRAINT:
            this.InstanceNode.style.backgroundColor = (this.InstanceNode.isvalid()) ? 'green':'red';
            break;
    }
 };
 Vertex.prototype.resetVisited = function() {
    for (var i=0; i < this.depList.length; i+=1) {
        this.depList[i].resetVisited();
    }
    this.visited = false;
 }
 function DepGraph(verticies) {
    this.graph = verticies || [];
 }
 DepGraph.prototype.dependencySubgraph = function(Lc) {
    // http://www.w3.org/TR/xforms11/#rpm-processing-recalc-mddg
    var stack=[], stackItem, r, v, w, wS, x, vS, S = [], Lci, Si;
    for (Lci=0; Lci < Lc.length, r=Lc[Lci]; Lci+=1) {
        if (!r.visited) {
            stack.push([null, r]);
            while (stack.length) {
                stackItem = stack.pop();
                v = stackItem[0], w = stackItem[1];
                if (!w.visited) {
                    w.visited = true;
                    wS = w.clone();
                    // this.graph[wS.index] <=> S[w.index]
                    
                    w.index = S.length; // w.index = index of wS in S
                    wS.index = this.indexOf(w); // wS.index = index of w in this.graph
                    S.push(wS);
                    for (x=0; x < w.depList.length; x+=1) {
                        stack.push([w, w.depList[x]]);
                    }
                } else {
                    wS = S[w.index];
                }
                if (v) {
                    vS = S[v.index];
                    vS.depList.push(wS);
                    wS.inDegree += 1;
                }
            }
        }
    }
    for (Si = S.length-1; Si >= 0, vS=S[Si]; Si-=1){
        v = this.graph[vS.index];
        v.visited = false;
    }
    return S;
 };
 DepGraph.topsort = function(S) {
    // static function
    var L = [];
    function visit(v) {
        if (!v.visited) {
            v.visited = true;
            for (var i=0; i < v.depList.length; i+=1) {
                visit(v.depList[i]);
            }
            L.push(v);
        }
    }
    for (var Si=0; Si < S.length; Si+=1) {
        visit(S[Si]);
    }
    for (var i = L.length - 1; i >= 0; i-=1){
        L[i].visited = false;
    }
    L.reverse();
    return L;
 };
 DepGraph.prototype.indexOf = function(vertex) {
    // TODO: make more efficient
    return this.graph.indexOf(vertex);
 };


 (function _test() {
    var A = document.getElementById('a');
    var B = document.getElementById('b');
    var C = document.getElementById('c');
    var D = document.getElementById('d');
    
    C.calc = function(){
        return parseInt(A.value, 10) * parseInt(B.value, 10);
    };
    D.calc = function(){
        return parseInt(A.value, 10) + parseInt(B.value, 10);
    };
    C.isvalid = function() {
        return parseInt(C.value, 10)<=100;
    };
    D.isvalid = function() {
        return parseInt(D.value, 10)<=20;
    };
    
    var a = new Vertex(VertexType.VALUE, A);
    var b = new Vertex(VertexType.VALUE, B);
    var v = new Vertex(VertexType.CALCULATE, C);
    var w = new Vertex(VertexType.CONSTRAINT, C);
    var x = new Vertex(VertexType.CALCULATE, D);
    var y = new Vertex(VertexType.CONSTRAINT, D);


    a.depList.push(v);
    a.depList.push(x);
    b.depList.push(v);
    b.depList.push(x);
    v.depList.push(w);
    x.depList.push(y);


    var master = new DepGraph([a, b, v, w, x, y]);
    
    function recalculate() {
        var Lc = [], S = [], i;
        if (this===window) {
            Lc = master.graph;
        } else {
            for (i=0; i < master.graph.length; i+=1) {
                if (master.graph[i].InstanceNode===this) {
                    Lc.push(master.graph[i]);
                }
            }
        }
        S = master.dependencySubgraph(Lc);
        console.dir(S);
        S = DepGraph.topsort(S);
        console.dir(S);
        for (i=0; i < S.length; i+=1) {
            S[i].recalculate();
        }
    }
    A.onchange = B.onchange = C.onchange = D.onchange = recalculate;
    recalculate();
    
 })();

 // ]]>
 </script>
 </div>
 </body>
 </html>
	<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd">
	<html lang="en">
	<head>
	<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
	<title>xforms dependency algorithm</title>
	</head>
	<body>
	<div>
	<form action="" method="post" accept-charset="utf-8">
	<ol style="list-style-type:lower-latin">
	<li><input type="text" id="a" value="0"></li>
	<li><input type="text" id="b" value="0"></li>
	<li><input type="text" id="c" value="0" readonly="readonly"> a*b <=100</li>
	<li><input type="text" id="d" value="0" readonly="readonly"> a+b <=20</li>
	</ol>
	</form>
	</div>
	<div>
	<script type="text/javascript">
	// <![CDATA[
	var VertexType = {
	NULL:null,
	VALUE:1,
	CALCULATE:2,
	RELEVANT:3,
	READONLY:4,
	REQUIRED:5,
	CONSTRAINT:6
	};

	function Vertex(type, instancenode) {
	this.InstanceNode = instancenode \|\| null;//a reference to the associated instance data node
	this.type = type \|\| VertexType.NULL; //indicates the aspect of the instance node represented by the vertex (the text content or a model item property such as readOnly or required)
	this.depList = []; // a list of vertices that refer to this vertex
	this.inDegree = 0; // the number of vertices on which this vertex depends
	this.visited = false; // a flag used to ensure vertices are not added to a subgraph multiple times
	this.index = null; // an association between vertices in the master dependency directed graph and a subgraph
	}
	Vertex.prototype.clone = function() {
	var v = new this.constructor(this.type, this.InstanceNode);
	return v;
	};
	Vertex.prototype.recalculate = function() {
	switch (this.type) {
	case VertexType.CALCULATE:
	this.InstanceNode.value = this.InstanceNode.calc();
	break;
	case VertexType.CONSTRAINT:
	this.InstanceNode.style.backgroundColor = (this.InstanceNode.isvalid()) ? 'green':'red';
	break;
	}
	};
	Vertex.prototype.resetVisited = function() {
	for (var i=0; i < this.depList.length; i+=1) {
	this.depList[i].resetVisited();
	}
	this.visited = false;
	}
	function DepGraph(verticies) {
	this.graph = verticies \|\| [];
	}
	DepGraph.prototype.dependencySubgraph = function(Lc) {
	// http://www.w3.org/TR/xforms11/#rpm-processing-recalc-mddg
	var stack=[], stackItem, r, v, w, wS, x, vS, S = [], Lci, Si;
	for (Lci=0; Lci < Lc.length, r=Lc[Lci]; Lci+=1) {
	if (!r.visited) {
	stack.push([null, r]);
	while (stack.length) {
	stackItem = stack.pop();
	v = stackItem[0], w = stackItem[1];
	if (!w.visited) {
	w.visited = true;
	wS = w.clone();
	// this.graph[wS.index] <=> S[w.index]

	w.index = S.length; // w.index = index of wS in S
	wS.index = this.indexOf(w); // wS.index = index of w in this.graph
	S.push(wS);
	for (x=0; x < w.depList.length; x+=1) {
	stack.push([w, w.depList[x]]);
	}
	} else {
	wS = S[w.index];
	}
	if (v) {
	vS = S[v.index];
	vS.depList.push(wS);
	wS.inDegree += 1;
	}
	}
	}
	}
	for (Si = S.length-1; Si >= 0, vS=S[Si]; Si-=1){
	v = this.graph[vS.index];
	v.visited = false;
	}
	return S;
	};
	DepGraph.topsort = function(S) {
	// static function
	var L = [];
	function visit(v) {
	if (!v.visited) {
	v.visited = true;
	for (var i=0; i < v.depList.length; i+=1) {
	visit(v.depList[i]);
	}
	L.push(v);
	}
	}
	for (var Si=0; Si < S.length; Si+=1) {
	visit(S[Si]);
	}
	for (var i = L.length - 1; i >= 0; i-=1){
	L[i].visited = false;
	}
	L.reverse();
	return L;
	};
	DepGraph.prototype.indexOf = function(vertex) {
	// TODO: make more efficient
	return this.graph.indexOf(vertex);
	};


	(function _test() {
	var A = document.getElementById('a');
	var B = document.getElementById('b');
	var C = document.getElementById('c');
	var D = document.getElementById('d');

	C.calc = function(){
	return parseInt(A.value, 10) * parseInt(B.value, 10);
	};
	D.calc = function(){
	return parseInt(A.value, 10) + parseInt(B.value, 10);
	};
	C.isvalid = function() {
	return parseInt(C.value, 10)<=100;
	};
	D.isvalid = function() {
	return parseInt(D.value, 10)<=20;
	};

	var a = new Vertex(VertexType.VALUE, A);
	var b = new Vertex(VertexType.VALUE, B);
	var v = new Vertex(VertexType.CALCULATE, C);
	var w = new Vertex(VertexType.CONSTRAINT, C);
	var x = new Vertex(VertexType.CALCULATE, D);
	var y = new Vertex(VertexType.CONSTRAINT, D);


	a.depList.push(v);
	a.depList.push(x);
	b.depList.push(v);
	b.depList.push(x);
	v.depList.push(w);
	x.depList.push(y);


	var master = new DepGraph([a, b, v, w, x, y]);

	function recalculate() {
	var Lc = [], S = [], i;
	if (this===window) {
	Lc = master.graph;
	} else {
	for (i=0; i < master.graph.length; i+=1) {
	if (master.graph[i].InstanceNode===this) {
	Lc.push(master.graph[i]);
	}
	}
	}
	S = master.dependencySubgraph(Lc);
	console.dir(S);
	S = DepGraph.topsort(S);
	console.dir(S);
	for (i=0; i < S.length; i+=1) {
	S[i].recalculate();
	}
	}
	A.onchange = B.onchange = C.onchange = D.onchange = recalculate;
	recalculate();

	})();

	// ]]>
	</script>
	</div>
	</body>
	</html>