implemented labels, arrow heads and began animation; things a little slower now

12 files changed, 170 insertions, 106 deletions

diff --git a/javascripts/Nfa.js b/javascripts/Nfa.js
index 2edc4b7..a214700 100644
--- a/javascripts/Nfa.js
+++ b/javascripts/Nfa.js
@@ -1,6 +1,6 @@
 /*
  * Nfa
- *
+ * NFA consisting of several NfaStates, following Thompson's algorithm.
  */
 function Nfa(symbol) {
 	this.startState = null;
@@ -13,13 +13,13 @@ function Nfa(symbol) {
     };
 };
 
-// 
+// Accessor functions.
 Nfa.prototype.getStartState = function()  { return this.startState; };
 Nfa.prototype.setStartState = function(s) { this.startState = s; };
 Nfa.prototype.getFinalState = function()  { return this.finalState; };
 Nfa.prototype.setFinalState = function(s) { this.finalState = s; };
 
-// 
+// Concatenations: ab
 Nfa.prototype.concat = function(nfa) {
     this.getFinalState().setFollowUp(0, nfa.getStartState());
     this.setFinalState(nfa.getFinalState());
@@ -27,7 +27,7 @@ Nfa.prototype.concat = function(nfa) {
 	return this;
 };
 
-// 
+// Union: (a|b)
 Nfa.prototype.union = function(nfa) {
     var s = new NfaState();
     var t = new NfaState();
@@ -44,7 +44,7 @@ Nfa.prototype.union = function(nfa) {
 	return this;
 };
 
-// 
+// Kleene Star: a*
 Nfa.prototype.kleene = function() {
     var s = new NfaState();
     var t = new NfaState();
diff --git a/javascripts/Nfa2Dfa.js b/javascripts/Nfa2Dfa.js
index 0e889f8..f38b2cf 100644
--- a/javascripts/Nfa2Dfa.js
+++ b/javascripts/Nfa2Dfa.js
@@ -1,9 +1,9 @@
 /*
  * Nfa2Dfa
- *
+ * Convert a NFA to a DFA utilizing epsilon closure.
  */
 
-// 
+// Compare two NfaStates for equality.
 function StateCmp(a, b) {
 	if (a.id == b.id) {
 		return true
@@ -11,28 +11,26 @@ function StateCmp(a, b) {
 	return false
 };
 
-// 
+// Compare two stacks filled with NfaStates for euqality.
 function NfaStackCmp(x, y) {
-	var ret = true;
+	var b = true;
 	if (x.length != y.length) { return false }
 	for (var i=0; i < x.length; i++) {
-		ret = ret && StateCmp(x.get(i), y.get(i));
+		b = b && StateCmp(x.get(i), y.get(i));
 	};
-	return ret;
+	return b;
 };
 
-// 
 function Nfa2Dfa(nfa) {
 	this.startState = nfa.getStartState();
     this.finalState = nfa.getFinalState();
 }
 
-// 
+// Accessor functions.
 Nfa2Dfa.prototype.getStartState = function() { return this.startState; };
 Nfa2Dfa.prototype.getFinalState = function() { return this.finalState; };
 
-// 
-var ttable = new Object();
+// Do conversion.
 Nfa2Dfa.prototype.do = function() {
 	var dfaStates = new Stack();
 	var q = new Stack();
@@ -40,47 +38,41 @@ Nfa2Dfa.prototype.do = function() {
 	var p = this.epsclosure(q)
 	var q = p.copy();
 	dfaStates.push(p);
-	//document.write('S '+p.str()+'<br />');
+	
 	var done = new Array();	
-	var ds = null;
-	var j = 0;
+	var ds, j = 0;
 	while (!dfaStates.isEmpty()) {
 		ds = dfaStates.pop();
 		
 		for (var i = 0; i < ALPHABET.length; i++) {
-			a = ALPHABET.substring(i, i+1);
-			var ds2 = ds.copy();
-			x = this.epsclosure(this.move(a, ds));
-			ds = ds2;
+			symbol = ALPHABET.substring(i, i+1);
+			var dsCopy = ds.copy();
+			next = this.epsclosure(this.move(symbol, ds));
+			ds = dsCopy;
 
-			var adone = false;
-			for (var w=0; w < done.length; w++) {
-				if(NfaStackCmp(done[w], x)) {
-					adone = true;
+			var alreadyDone = false;
+			for (var k = 0; k < done.length; k++) {
+				if(NfaStackCmp(done[k], next)) {
+					alreadyDone = true;
 					break;
 				};
 			};
 			
-			var q = ds.str().replace(/ /g, '_');
-			var qq = x.str().replace(/ /g, '_');
-			
-			if (!ttable[q]) {
-				ttable[q] = new Object();
-				if(q.split('_').indexOf(''+this.getFinalState().id) >= 0) {
-					ttable[q].isFinal = true;
+			var dsStr = ds.str().replace(/ /g, '_');			
+			if (!ttable[dsStr]) {
+				ttable[dsStr] = new Object();
+				if(dsStr.split('_').indexOf(''+this.getFinalState().id) >= 0) {
+					ttable[dsStr].isFinal = true;
 				} else {
-					ttable[q].isFinal = false;
+					ttable[dsStr].isFinal = false;
 				};
 			};
 			
-			ttable[q][a] = qq;
+			var nextStr = next.str().replace(/ /g, '_');
+			ttable[dsStr][symbol] = nextStr;
 			
-			if (x.length > 0 && !adone) {
-				for (var h=0; h < j; h++) {
-					//document.write("\t");
-				};
-				//document.write(a+' '+x.str()+'<br />');
-				dfaStates.push(x);
+			if (next.length > 0 && !alreadyDone) {
+				dfaStates.push(next);
 			};
 	    };
 		done.push(ds);
@@ -88,12 +80,9 @@ Nfa2Dfa.prototype.do = function() {
 	};
 };
 
-// 
+// Reachable states over epsilon transitions.
 Nfa2Dfa.prototype.epsclosure = function(q) {
-    var s = null;
-    var t = null;
-
-	var p = new Stack();
+    var s, t, p = new Stack();
 
     while(!q.isEmpty()) {
         s = q.pop();
@@ -102,7 +91,7 @@ Nfa2Dfa.prototype.epsclosure = function(q) {
         if(s.symbol == EPSILON) {
             for (var i = 0; i < 2; i++) {
                 t = s.getFollowUp(i);
-                if (t!=null) {
+                if (t != null) {
  					q.push(t);
                 };
             };
@@ -111,11 +100,10 @@ Nfa2Dfa.prototype.epsclosure = function(q) {
 	return p;
 };
 
-// 
+// Reachable states over transitions with symbol.
 Nfa2Dfa.prototype.move = function(str, p) {
-	var s = null;
-	var q = new Stack();
-
+	var s, q = new Stack();
+	
     while(!p.isEmpty()) {
         s = p.pop();
         s.mark(false);
diff --git a/javascripts/NfaSimulator.js b/javascripts/NfaSimulator.js
index 0c29914..c5a035f 100644
--- a/javascripts/NfaSimulator.js
+++ b/javascripts/NfaSimulator.js
@@ -1,16 +1,17 @@
 /*
  * NfaSimulator
- *
+ * Simulate a NFA with a word. Check if regular expression produces word.
  */
 function NfaSimulator(nfa) {
 	this.startState = nfa.getStartState();
     this.finalState = nfa.getFinalState();
 };
 
+// Accessor functions.
 NfaSimulator.prototype.getStartState = function() { return this.startState; };
 NfaSimulator.prototype.getFinalState = function() { return this.finalState; };
 
-// 
+// Main simulate function.
 NfaSimulator.prototype.simulate = function(word) {
 	var a, accepted = false;
     this.p = new Stack();
@@ -26,7 +27,7 @@ NfaSimulator.prototype.simulate = function(word) {
     return accepted;
 };
 
-// 
+// Get reachable states through epsilon transitions.
 NfaSimulator.prototype.epsclosure = function() {
     var s, t, accepted = false;
 
@@ -50,7 +51,7 @@ NfaSimulator.prototype.epsclosure = function() {
     return accepted;
 };
 
-// 
+// Get reachable states through transitions with symbol.
 NfaSimulator.prototype.move = function(symbol) {
     var s;
 
diff --git a/javascripts/NfaState.js b/javascripts/NfaState.js
index 2de256d..4291295 100644
--- a/javascripts/NfaState.js
+++ b/javascripts/NfaState.js
@@ -1,6 +1,6 @@
 /*
- * State
- *
+ * NfaState
+ * Represents a state of a NFA (following Thompson's algorithm).
  */
 function NfaState(symbol) {
     if(!symbol) {
@@ -13,6 +13,7 @@ function NfaState(symbol) {
 	this.id		   = NEXTSTATE++;
 };
 
+// Accessor functions.
 NfaState.prototype.mark = function(bool) { this.marked = bool; };
 NfaState.prototype.getFollowUp = function(index) { return this.followUps[index]; };
 NfaState.prototype.setFollowUp = function(index, state) {
diff --git a/javascripts/RegexParser.js b/javascripts/RegexParser.js
index 3abe426..42251af 100644
--- a/javascripts/RegexParser.js
+++ b/javascripts/RegexParser.js
@@ -1,14 +1,16 @@
 /*
  * RegexParser
- *
+ * Parsing a regular expression using recursive descent method.
+ * parse() returns a NFA (constructed following Thompson's algrotihm).
  */
 function RegexParser() {};
 
+// Accessor functions
 RegexParser.prototype.getRegex = function() { return this.regex; };
 RegexParser.prototype.getErrorMessage = function() { return this.errorMessage; };
 RegexParser.prototype.getErrorPosition = function() { return this.errorPosition; };
 
-// 
+// Next symbol in regex.
 RegexParser.prototype.lookahead = function() {
     if (this.str.length > 0) {
         return this.str.substring(0, 1);
@@ -16,12 +18,12 @@ RegexParser.prototype.lookahead = function() {
     return '';
 };
 
-// 
+// Removing the firstmost symbol of regex.
 RegexParser.prototype.consume = function(symbol) {
     this.str = this.str.substring(1);
 };
 
-// 
+// Check if symbol matches expected symbol.
 RegexParser.prototype.trymatch = function(symbol) {
     if (this.str.substring(0, symbol.length) == symbol) {
         this.consume(symbol);
@@ -30,14 +32,14 @@ RegexParser.prototype.trymatch = function(symbol) {
     return false;
 };
 
-// 
+// See above.
 RegexParser.prototype.match = function(symbol) {
     if (!this.trymatch(symbol)) {
         throw("RegexParser.match(): Expected symbol '"+symbol+"'.");
     };
 };
 
-// 
+// Checks if a symbol is in set of symbols.
 RegexParser.prototype.isIn = function(symbol, set) {
 	if (symbol.length > 0) {
 		return set.indexOf(symbol) >= 0;
@@ -45,12 +47,12 @@ RegexParser.prototype.isIn = function(symbol, set) {
 	return false;
 };
 
-// 
+// See above. Set = alphabet.
 RegexParser.prototype.isLetter = function(symbol) {
     return this.isIn(symbol, ALPHABET);
 };
 
-// 
+// Is symbol a literal?
 RegexParser.prototype.literal = function() {
     var symbol = this.lookahead();
     if(this.isLetter(symbol)) {
@@ -60,7 +62,7 @@ RegexParser.prototype.literal = function() {
     throw("RegexParser.literal(): Expected a letter or '"+EMPTYSYMBOL+"'."); 
 };
 
-// 
+// Atomar expression.
 RegexParser.prototype.atom = function() {
     if(this.trymatch('(')) {
         var nfa = this.expr();
@@ -70,12 +72,12 @@ RegexParser.prototype.atom = function() {
     return this.literal();
 };
 
-// 
+// Factor.
 RegexParser.prototype.factor = function() {
     return this.star(this.atom());
 };
 
-// 
+// Kleene Star.
 RegexParser.prototype.star = function(nfa) {
     if (this.trymatch('*')) {
         return this.star(nfa.kleene());
@@ -83,7 +85,7 @@ RegexParser.prototype.star = function(nfa) {
     return nfa;
 };
 
-// 
+// Term.
 RegexParser.prototype.term = function() {
     var nfa = this.factor();
     var symbol = this.lookahead();
@@ -93,7 +95,7 @@ RegexParser.prototype.term = function() {
     return nfa;
 };
 
-// 
+// Expression.
 RegexParser.prototype.expr = function() {
 	var nfa = this.term();
     if (this.trymatch('|')) {
@@ -102,7 +104,7 @@ RegexParser.prototype.expr = function() {
     return nfa;
 };
 
-// 
+// Parse function.
 var nfa;
 RegexParser.prototype.parse = function(regex) {
     this.str = regex;
diff --git a/javascripts/Stack.js b/javascripts/Stack.js
index c4e2db9..4ccd74e 100644
--- a/javascripts/Stack.js
+++ b/javascripts/Stack.js
@@ -1,19 +1,19 @@
 /*
  * Stack
- *
+ * Simple implementation of a stack using Array().
  */
 function Stack() {
 	this.a 		= new Array();
 	this.length = 0;
 };
 
-// 
+// Push an item.
 Stack.prototype.push = function(obj) {
 	this.a.push(obj);
 	this.length++;
 };
 
-// 
+// Pop an item.
 Stack.prototype.pop = function() {
 	if (this.isEmpty()) {
 		throw('Stack.pop(): Pop from empty stack.');
@@ -22,7 +22,7 @@ Stack.prototype.pop = function() {
 	return this.a.pop();
 };
 
-// 
+// Check if stack is empty.
 Stack.prototype.isEmpty = function() {
 	if (this.length == 0) {
 		return true;
@@ -30,12 +30,12 @@ Stack.prototype.isEmpty = function() {
 	return false;
 };
 
-// 
+// Get an item at position index.
 Stack.prototype.get = function(index) {
 	return this.a[index];
 };
 
-// 
+// Deep copy a stack.
 Stack.prototype.copy = function() {
 	var c = ((new Array()).concat(this.a));
 	var ret = new Stack();
@@ -44,7 +44,7 @@ Stack.prototype.copy = function() {
 	return ret;
 };
 
-// 
+// String representation.
 Stack.prototype.str = function(separator) {
 	if (!separator) { separator=' ' };
 	var a = new Array();
diff --git a/javascripts/globals.js b/javascripts/globals.js
index 88d5b2a..e8668b8 100644
--- a/javascripts/globals.js
+++ b/javascripts/globals.js
@@ -3,4 +3,8 @@ var EPSILON     = '~';
 var NEXTSTATE   = 0;
 var EMPTYSYMBOL = '%';
 var ALPHABET    = 'abc'+EMPTYSYMBOL;
+var ALPHABETS   = ALPHABET+'()|*';
 var REDELIMITER = '$';
+
+var ttable = new Object();
+var g;
diff --git a/javascripts/graph.js b/javascripts/graph.js
index c1460f2..1d7d17d 100644
--- a/javascripts/graph.js
+++ b/javascripts/graph.js
@@ -1,5 +1,5 @@
-// spurce: http://raphaeljs.com/graffle.html
-Raphael.fn.connection = function (obj1, obj2, line, bg, strokeColor) {	
+// source: http://raphaeljs.com/graffle.html (extended with labels and arrow heads)
+Raphael.fn.connection = function (obj1, obj2, line, bg, strokeColor, symbol, labelFontSize) {	
     if (obj1.line && obj1.from && obj1.to) {
         line = obj1;
         obj1 = line.from;
@@ -43,20 +43,38 @@ Raphael.fn.connection = function (obj1, obj2, line, bg, strokeColor) {
         y3 = [0, 0, 0, 0, y1 + dy, y1 - dy, y4, y4][res[1]].toFixed(3);
     var path = ["M", x1.toFixed(3), y1.toFixed(3),
 				"C", x2, y2, x3, y3, x4.toFixed(3), y4.toFixed(3)].join(",");
-	
+	var theLine = this.path(path).attr({stroke: color, fill: "none"});
+	var labelPoint = theLine.getPointAtLength(theLine.getTotalLength()/2);
+	var ahPoint = theLine.getPointAtLength(theLine.getTotalLength());
 	if (line && line.line) {
         line.bg && line.bg.attr({path: path});
         line.line.attr({path: path});
-    } else {
+		line.lbl.remove();
+		line.lbl = this.text(labelPoint.x+10, labelPoint.y+10, line.symbol
+			).attr({fill:'#000', 'font-size': line.labelFontSize});
+		line.ah.remove();
+		line.ah = this.circle(ahPoint.x, ahPoint.y, line.labelFontSize/4
+					).attr({stroke: 'none', fill: line.strokeColor});
+	} else {
         var color = typeof line == "string" ? line : strokeColor;
-        return {
+        var strokeWidth = bg.split("|")[1] || 3;
+        var stroke = bg.split("|")[0];
+        var ret = {
             bg: bg && bg.split && this.path(path
-				).attr({stroke: bg.split("|")[0],
-						fill: "none", "stroke-width": bg.split("|")[1] || 3}),
-            line: this.path(path).attr({stroke: color, fill: "none"}),
+				).attr({stroke: stroke,
+						fill: "none", "stroke-width": strokeWidth}),
+            line: theLine,
             from: obj1,
-			to: obj2
+			to: obj2,
+			symbol: symbol,
+			labelFontSize: labelFontSize,
+			strokeColor: strokeColor,
+			ah: this.circle(ahPoint.x, ahPoint.y, labelFontSize/4
+					).attr({stroke: 'none', fill: strokeColor}),
+			lbl: this.text(labelPoint.x+10, labelPoint.y+10, symbol
+					).attr({fill:'#000', 'font-size': labelFontSize})
         };
+		return ret;
     };
 };
 // source: http://stackoverflow.com/questions/2627436/svg-animation-along-path-with-raphael
@@ -120,7 +138,12 @@ Raphael.fn.aNode = function(x, y, r, isFinal, hasSelfConn,
 	};
 	return res;
 };
-
+// source: http://www.davidcramer.net/code/63/dir-in-javascript.html
+function dir(object) {
+    methods = [];
+    for (z in object) if (typeof(z) != 'number') methods.push(z);
+    return methods.join(', ');
+};
 
 function graph() {
 	var nodeRadius 	 = 30;
@@ -128,7 +151,7 @@ function graph() {
 	var nodeOpacity   = 1;
 	var nodeOpacityHi = .5;
 	var labelFontSize = 16;
-	var strokeWidth = 2;
+	var strokeWidth = 3;
 	var strokeColor = '#ccc';
 	
 	r = Raphael("holder", 1024, 640);
@@ -143,7 +166,7 @@ function graph() {
 				nodeById[this.id][i].translate(dx, dy);
 			};
 			for (var i = connections.length; i--;) {
-            	r.connection(connections[i]);
+				r.connection(connections[i]);
         	};
         	r.safari();
 		},
@@ -201,7 +224,8 @@ function graph() {
 						if (state == statex) {
 							continue;
 						} else {
-							connections.push(r.connection(nodes[k][0], nodes[l][0], strokeWidth, strokeColor));								
+							connections.push(r.connection(nodes[k][0], nodes[l][0],
+								strokeColor, strokeColor, strokeColor, ALPHABET[i], labelFontSize));								
 						};
 					};
 					l++;
@@ -210,4 +234,11 @@ function graph() {
 		};
 		k++;
 	};
+	return {
+		paper: r,
+		nodes: nodes,
+		nodeById: nodeById,
+		connections: connections,
+		test: 'test'
+	};
 };
diff --git a/javascripts/uifunc.js b/javascripts/uifunc.js
index 007305a..fd608f5 100644
--- a/javascripts/uifunc.js
+++ b/javascripts/uifunc.js
@@ -1,4 +1,4 @@
-// 
+// enable/disable if input length is > 0
 function checkLength(el, bId) {
 	if(el.value.length > 0) {
 		enable(bId);
@@ -7,17 +7,12 @@ function checkLength(el, bId) {
 	};
 };
 
-// 
-function enable(id) {
-		 $(id).removeAttr("disabled");
-};
-
-// 
-function disable(id) {
-	 $(id).attr("disabled","disabled");
-};
+// enable a disabled form item
+function enable(id) { $(id).removeAttr("disabled"); };
+// disable a form item
+function disable(id) { $(id).attr("disabled","disabled"); };
 
-// 
+// call of RegexParser.parse() from UI
 function uiParse() {
 	var parser = new RegexParser();
 	nfa = parser.parse($('#regex').attr('value'));
@@ -34,14 +29,35 @@ function uiParse() {
 		enable('#word');
 		var dfa = new Nfa2Dfa(nfa);
 		var ttable = dfa.do();
-		graph();
+		window.g = graph();
 		disable('#regex');
 		disable('#parseButton');
 	};
 	$('#parseMessage').effect("highlight", {}, 1000);
+	
+	s = 'abc';
+	/*g.mover = g.paper.circle(
+		g.nodes[0][1][0].cx.baseVal.value,
+		g.nodes[0][1][0].cy.baseVal.value, 30
+	).attr({fill:'#00f', stroke: 'none', opacity: 0.5});
+	for (var i=0; i < s.length; i++) {
+        (function(g, i) {
+            setTimeout(function() {
+				var state = g.nodes[i];
+				var x = state[1][0].cx.baseVal.value;
+				var y = state[1][0].cy.baseVal.value;
+              	g.mover.animateAlong(
+					g.paper.path(
+						'M'+x+state[1][0].r.baseVal.value+','+y+' '+g.connections[i].line.attr('path').toString().substring(1)
+						+'L'+(g.nodes[i+1][1][0].cx.baseVal.value+(i*2))+','+g.nodes[i+1][1][0].cy.baseVal.value
+						).attr({stroke:'none', 'stroke-width':4})
+				, 2000)
+			}, 2000*i);
+        })(g, i);
+	};*/
 };
 
-// 
+// call of NfaSimulator.simulate() from UI
 function uiSimulate() {
 	var simulator = new NfaSimulator(nfa);
 	var check = simulator.simulate($('#word').attr('value'));
@@ -60,3 +76,17 @@ function uiSimulate() {
 	};
 	$('#checkMessage').effect("highlight", {}, 1000);	
 };
+
+
+function getKey(e, set) {
+	var key = String.fromCharCode(e.which);
+	if (set.indexOf(key) >= 0 || e.which == 8) {
+		return true;
+	}
+	return false;
+};
+
+//
+function graphMove(symbol) {
+	true;
+};
diff --git a/regexvis.html b/regexvis.html
index a881d82..a99b991 100644
--- a/regexvis.html
+++ b/regexvis.html
@@ -55,7 +55,7 @@
 			<tr>
 				<td style='text-align:right'><strong>Regular Expression:</strong></td>
 				<td><input type="text" name="regex" id="regex" value=""
-						onchange='checkLength(this, "#parseButton")'
+						onchange='checkLength(this, "#parseButton")' onkeypress="return getKey(event, ALPHABETS)"
 						onmouseout='checkLength(this, "#parseButton")' autocomplete="off" />
 						<input type="button" name="parseButton" id="parseButton"
 						value="Parse" disabled='disabled' autocomplete="off" onclick="uiParse()" />
@@ -64,7 +64,7 @@
 			<tr>
 				<td style='text-align:right'><strong>Word:</strong></td>
 				<td><input type="text" name="word" id="word" value="" disabled='disabled'
-						onchange='checkLength(this, "#checkButton")'
+						onchange='checkLength(this, "#checkButton")' onkeypress="return getKey(event, ALPHABET)"
 						onmouseout='checkLength(this, "#checkButton")' autocomplete="off" />
 					<input type="button" name="checkButton" id="checkButton"
 						value="Check" disabled='disabled' autocomplete="off" onclick="uiSimulate()" />
diff --git a/resources/raphael.png b/resources/raphael.png
new file mode 100644
index 0000000..17f0358
--- /dev/null
+++ b/resources/raphael.png
diff --git a/resources/urls.txt b/resources/urls.txt
index 4b9dada..49d9c32 100644
--- a/resources/urls.txt
+++ b/resources/urls.txt
@@ -12,3 +12,10 @@ http://www.gamedev.net/reference/articles/article2170.asp
 http://raphaeljs.com/reference.html
 
 http://www.w3.org/TR/SVG/
+
+http://github.com/DmitryBaranovskiy/raphael/
+http://groups.google.com/group/raphaeljs/browse_thread/thread/f7f7cffa82331503/3d40c581a0e6f50b?lnk=raot
+http://groups.google.com.au/group/raphaeljs/browse_thread/thread/c4bf09bd58546625/6de8fd1b07a65315?lnk=gst&q=graffle#6de8fd1b07a65315
+http://groups.google.com.au/group/raphaeljs/browse_thread/thread/adaa2b0331f64d61/7dc6d9295ddf7a63?lnk=gst&q=graffle#7dc6d9295ddf7a63
+http://paste.ubuntu.com/205627/
+http://gist.github.com/205638