var inf = 1.0e9;
var continents = [
	"Sepharia",
	"Avros",
	"Auryn",
	"Beltane"
];
var from = -1;
var to = -1;
var cmode = 'normal';
var ccont = 0;
var es = [
	[1,		2,	"2j3e", '', 0],
	[1,		3,	"3w3hn2hnh2nhn2h2n4hnhnh10nj4njn2j3n3j2njnj3nj7nj2n3jn2je3jn2je2j6nh2nhnhn5h3w", '', 0],
	[3,		4,	"2wh3wh3whwhw2hn2h7nh2whwhw2h6w3ksk2s3ks2k5wh3whwhwh2w4hnh2nh2n2h4nj6nj3n3jn2j4n3hj", '', 0],
	[2,		5,	"3nhnh8nh15nh2nh9nj5nj2njn5jn3jnj4njnj2n2j2n3jn4jn2jnj8n2h6nh2nh4nh2n2h12nj5nj7nh3nhnhnh2n", '', 0],
	[8,		7,	"5n4jn6jej2ej2ej2ejej2e2je2jej2ej4e2j2ej2ej6el5el3ej4ejejej2e2jeje4jeje2jej2e4je2jejej2ej4el4ele4l2el3el5el23ej9el2el3el11ejej8ejej5ej13ej11el3e2l4el2elel3el2el2el3el4el4elel2e2le2l3el2el6ejlj7e2j25el2elele2l3el4el7ejel11elj3e3j5nh2nh3nj3njn3jn3j2e3j2ej2ej3ej9e2lelelele4lsl3sl5s2kskwkwkwk2wk3wh3wh2whwhw2hnh5njn2jn3j2ej5el3e5l2slsks2kwk7w3h4nje", '', 0],
	[2,		34,	"ls4l2s2lslsl6s", '', 0],
	[34,	9,	"11sk2s2ks2ks3ks3ks2ks5kwk2wk4w11ksksk14sl3sl2sl6sk4sks", '', 0],
	[9,		24,	"2sks3ks7kw2k2sk3sk2skw2kwk3wk2wk3wk2wk2w2kw2kw4ksk2sk2s2ks5ks2ksk3s2k6sksks3ks2ks5kwk", '', 0],
	[5,		8,	"2hn3h9nh3nhnh13nj2nj2nj2njn2j3n3jn7jn7j5nj3njnj2nj2n2jn2j9nj4nj2njnjn10je2jejeje2je", '', 0],
	[8,		45,	"e3lsl2s3ls2le2l3sl2slsl2slslsls3lel2e7lsl4sl7sk3sk3sk2s2ks14ksk2s2k2sk3sk6sls3le3l2el2el13e2jej2e7je2jejej2e2je2jeje4j3e", '', 0],
	[45,	13,	"je3jn4jn3jn5jn6jej2ej3ej2eje2je3je2jejeje2j2ej2ej6ele", '', 0],
	[45,	46,	"lel2slslel2e", '', 0],
	[13,	11,	"el2elel2elel2elele3l3e", '', 0],
	[11,	6,	"s6e3s3e6s4elel2s4ls6le8l2el2el2e6ls2lelel2el6e3lelelel2e3le10ls2lsls2lsl6s6l2el3elsl2slsl3sle2l2s3l2ej", '', 0],
	[11,	47,	"2e2lel2sl2sks2k3w", '', 0],
	[47,	48,	"s3le2lsl2e4l2e3le2lelsle3ls2ls7ls5ls2ls5lslslslsls2lsls3le3lelel3e", '', 0],
	[48,	16,	"3el3el2ele4l2ele5lslel2s2l3s5le2le2l2elele2le2lelel9s2k2wk3wh", '', 0],
	[14,	15,	"n5hw2hn2h2n5hw2h3w4hw2hwhwh2wh3wh2w3h2wh2w2hwhw2hwhnh7n2jnj17n3hnhn4hwhwk4w3k8skw2k6s2ks3k2w2ks4k5wh2w2h3w", '', 0],
	[18,	17,	"4s3le4l2e", '', 0],
	[17,	19,	"lele2le3le8le7lele5lelel2e3ls4ls5le7ls2ls2ls3l3sl2slslsl2s2lslslsl6sls3ls5lslslslslslsls2lslsl7sk4sks", '', 0],
	[20,	17,	"4sls5k2wkwkwkwk2sls9ksk5sl3e4l2elel2sks4k3wk2w3k2sk2slel4el2e2lslelel4el5s2k2w4k4wkwkw2k2w3kw2kw3k7s3le3l2sls2l10sl12s4kw2kwk2w4k2wk2wk2w3k5s2kskwkh3w2ksks", '', 0],
	[10,	22,	"4h4n7jeje2j3n", '', 0],
	[22,	23,	"lel2e", '', 0],
	[23,	24,	"3e", '', 0],
	[22,	25, "8whwhwhw2hwh2wh3wh2wh2whwh2whwhwh3wh2wh2whwh2w", '', 0],
	[25,	26,	"2nhn3h2n2hwhw2hwh2w2hwh13wh2nhk3w", '', 0],
	[26,	21,	"2w2hw2hnhnh5n2h3w2hn2h8nhnh9n2jn2j6nh6n2jn2jnj11njnj6nh12n2j6nhnh19nh5n2hn3hn2h4nj2nhn2hwh2w2hn2h2nhnh3njnh4n2hn4hnh8n2hn2h6nj2e3l2j7e4jej2e5je2jn2j11nj3n2jnjej2eje3jn2hn", '', 0],
	[21,	27,	"5eje4j9nhnh4w", '', 0],
	[27,	28,	"7n2j2els4lel2ele2jnj2n8j2e2jeje2je2jnjnj2nj6n2j2nj4n2h2nh3nhnh8nj3n2jnjej2e", '', 0],
	[22,	29,	"6nhnhnh2nh2nj2n2jn10j2nj5nj3nh", '', 0],
	[29,	30,	"2wkw", '', 0],
	[29,	31,	"nh8nj2nh", '', 0],
	[31,	32,	"j5n8hn4h4n3h6wk7w3hn10h6nh7nhnh7n3j2n6j10ej5n2h2n4h5n3hwh3njnjnh2n2jel", '', 0],
	[25,	33,	"3k2sk5sl3s2l2sk6slk3s5k2w3kwks3ksk2s3l6s2l8sksk7s3ls6l4sl4sk10s2le2l2s5le5l3slel2e2le2lele4lslsl2sl2sl3slslslsl6sl2s3l2s2l3sk6s2lsl7sk10s2ks6kw7k6sk3s4ks4kwk2wkwks6ks2k2s3kwkwk11wh3wk4w2kw2kw3k2wkw4k3s2kw2ks4k6wh3whwh2nhn3h4nh3njnj", '', 0],
	[36,	35,	"3s2l2e2jej2n2j3njnh6je3j2e", '', 0],
	[35,	37,	"7n5h3n2hnhn7hwhnhn2h2nhn11hw2hwh9wk2wk7whw2hwhnhn3hw3hn17hw2hw10hw3hw2h2w2k3s2kwk3wh3w2h2wk2wk3whwh5wh4wh3w2h3nje", '', 0],
	[35,	39,	"s5l2s3lelsl2s5ls2l3sl5s3k2s5k5w2k2w4ksk2s2k3sk2sksk3sksk2sk2sksks6kwk2wk12wh5whwhwhwhn2h2nh4n3hn2hnh", '', 0],
	[39,	38,	"6n2h10n3jnjn2jnjn2j2njn2j5nh2nhnhn4hn3hn2hw2hn3h2wh2wh", '', 0],
	[39,	40,	"2k3sl4sl2sls2lsls6le4le7le3lelelel2el2el5el3ele3ls2l3s2le3lel4ej4elej3el2el4el2e2le4ls2l2ej4e2jejej2e2j2el4e2l5s2l2sl3sls3l2sl4s2k7sls", '', 0],
	[40,	41,	"2ej3el5e2l2e4l4ej5e2jnjn2hn", '', 0],
	[24,	43,	"le5lsl3sl8s2kw", '', 0],
	[34,	44,	"2w2k3w2kwk4w2h2n", '', 0]
];

var ES_FROM = 0;
var ES_TO = 1;
var ES_PATH = 2;
var ES_RPATH = 3;
var ES_WEIGHT = 4;

var vs = {
	1:	[1,		"New Rigel (n)",		true,	0,	801,	545,	false,	inf],
	2:	[2,		"NR North Intersect",	false,	0,	806,	543,	false,	inf],
	3:	[3,		"Tavern of the Boars",	true,	0,	797,	445,	false,	inf],
	4:	[4,		"Wroth",				true,	0,	736,	391,	false,	inf],
	5:	[5,		"Bazaar",				true,	0,	818,	386,	false,	inf],
	6:	[6,		"Lowangen",				true,	0,	1159,	421,	false,	inf],
	7:	[7,		"Tower of Art",			true,	0,	1271,	211,	false,	inf],
	8:	[8,		"N/E Intersect",		false,	0,	866,	257,	false,	inf],
	9:	[9,		"Traveler's Retreat",	true,	0,	776,	651,	false,	inf],
	10:	[10,	"Rune (w)",				true,	0,	684,	760,	false,	inf],
	11:	[11,	"Thorne",				true,	0,	1031,	316,	false,	inf],
	13:	[13,	"The Twin Moons Inn",	true,	0,	1007,	306,	false,	inf],
	14:	[14,	"Sigil (n)",			true,	2,	435,	1226,	false,	inf],
	47:	[47,	"Sigil (s)",			true,	2,	436,	1238,	false,	inf],
	15:	[15,	"Vospire",				true,	2,	330,	1176,	false,	inf],
	16:	[16,	"Diocletian",			true,	2,	553,	1360,	false,	inf],
	17: [17,	"S Temp Intersect",		false,	1,	1630,	553,	false,	inf],
	18:	[18,	"Templeton",			true,	1,	1620,	542,	false,	inf],
	19:	[19,	"Tellerium",			true,	1,	1724,	685,	false,	inf],
	20:	[20,	"Frost Giant's Keep",	true,	1,	1689,	389,	false,	inf],
	21:	[21,	"Xaventry (s)",			true,	0,	602,	454,	false,	inf],
	22:	[22,	"N Rune Intersect 1",	false,	0,	692,	739,	false,	inf],
	23:	[23,	"Hall of Heroes",		true,	0,	697,	741,	false,	inf],
	24:	[24,	"N Rune Intersect 2",	false,	0,	700,	741,	false,	inf],
	25:	[25,	"Rune/NK/Xav IS",		false,	0,	638,	721,	false,	inf],
	26:	[26,	"The Lonely Dragon Inn",true,	0,	600,	700,	false,	inf],
	27:	[27,	"Xaventry (n)",			true,	0,	607,	437,	false,	inf],
	28:	[28,	"Mandrake Forest",		true,	0,	654,	365,	false,	inf],
	29:	[29,	"Lasler Intersect",		false,	0,	702,	694,	false,	inf],
	30:	[30,	"Lasler",				true,	0,	698,	695,	false,	inf],
	31:	[31,	"Rune Forest",			true,	0,	701,	680,	false,	inf],
	32:	[32,	"Avarice",				true,	0,	671,	572,	false,	inf],
	33:	[33,	"New Kolvir",			true,	0,	571,	984,	false,	inf],
	34:	[34,	"NR South Intersect",	false,	0,	815,	563,	false,	inf],
	35:	[35,	"E Maldra Intersect",	false,	3,	1326,	1075,	false,	inf],
	36:	[36,	"Maldra's Keep",		true,	3,	1304,	1092,	false,	inf],
	37:	[37,	"Pirate's Cove",		true,	3,	1174,	975,	false,	inf],
	38:	[38,	"Dungeon Deceit",		true,	3,	1254,	1071,	false,	inf],
	39:	[39,	"S Deceit Intersect",	false,	3,	1268,	1139,	false,	inf],
	40:	[40,	"Some unknown area",	false,	3,	1399,	1244,	false,	inf],
	41:	[41,	"Some unknown dungeon",	false,	3,	1430,	1241,	false,	inf],
	43: [43,	"Rune (e)",				true,	0,	706,	763,	false,	inf],
	44: [44,	"New Rigel (s)",		true,	0,	798,	564,	false,	inf],
	45:	[45,	"Gilvery Intersect",	false,	0,	941,	348,	false,	inf],
	46:	[46,	"Gilvery",				true,	0,	950,	356,	false,	inf],
	48:	[48,	"Emperor's Crossroads",	true,	2,	506,	1309,	false,	inf]
};

var VS_ID		= 0;
var VS_NAME		= 1;
var VS_END		= 2;
var VS_ZONE		= 3;
var VS_X		= 4;
var VS_Y		= 5;
var VS_DONE		= 6;	
var VS_WEIGHT	= 7;

var rmap = {
	'n': 's',
	's': 'n',
	'w': 'e',
	'e': 'w',
	'h': 'l',
	'j': 'k',
	'k': 'j',
	'l': 'h',
	'u': 'd',
	'd': 'u'
};

var path = "";
var num = 0;
var t = [];

window.onload = function() {
	for (var i = 0; i < es.length; i++) {
		path = "";
		results = es[i][ES_PATH].match(/([0-9]+)?([nsewhjklud])/g);
		for (var j = 0; j < results.length; j++) {
			num = parseInt(results[j].replace(/[nsewhjklud]/, ''));
			num = num ? num : 1;
			var s = results[j].match(/[nsewhjklud]/)[0];
			while (num-- > 0)
				path += s;
		}
		es[i][ES_PATH] = path;
		es[i][ES_WEIGHT] = path.length;
	}
	for (i in vs) {
		if (vs[i][VS_END] == false) continue;
		t[t.length] = [vs[i][VS_NAME], i];
	}
	t = t.sort()

	for (i in t) {
		div = document.createElement("li");
		div.innerHTML = "<span>" + t[i][0] + "</span><a onclick=\"return true;\" target=\"gal\" href=\"gal.php?xpos="+vs[t[i][1]][4]+"&ypos="+vs[t[i][1]][5]+"\">(" + vs[t[i][1]][4] + ", " + vs[t[i][1]][5] + ")</a>";
		div.n = t[i][1];
		div2 = div.cloneNode(true);
		div.cont = vs[t[i][1]][3];
		div2.cont = vs[t[i][1]][3];
		div2.n = t[i][1];
		div.onmouseover = div2.onmouseover = function() {
			this.style.backgroundColor = '#FFF';
		};
		div.onmouseout = div2.onmouseout = function() {
			this.style.backgroundColor = (this.className == 'selected' ? '#FFF' : 'transparent');
		};
		div.onclick = div2.onclick = function() {
			var e = this.parentNode;
			if (cmode == 'normal') {
				for (var i = 0; i < e.childNodes.length; i++) {
					e.childNodes[i].style.backgroundColor = 'transparent';
					e.childNodes[i].style.fontWeight = 'normal';
					e.childNodes[i].className = '';
				}
			}
			if (this.className == 'selected') {
				this.style.backgroundColor = 'transparent';
				this.style.fontWeight = 'normal';
				this.className = '';
			} else {
				this.style.backgroundColor = '#FFF';
				this.className = 'selected';
				this.style.fontWeight = 'bold';
				if (this.parentNode.id == 'from')
					from = this.n;
				else if (this.parentNode.id == 'to')
					to = this.n;
			}
		};
		document.getElementById('from').appendChild(div);
		document.getElementById('to').appendChild(div2);
	}

	document.getElementById('modeNormal').checked = document.getElementById('slotZMUD').checked = true;

	for (i in continents) {
		li = document.createElement("li");
		li.innerHTML = continents[i];
		li.n = i;
		li.onclick = function() {
			ccont = this.n;
			displayContinent(this.n);
			var e = this.parentNode;
			for (var i = 0; i < e.childNodes.length; i++) {
				e.childNodes[i].className = '';
			}
			this.className = 'selected';
		};
		if (i == 0) {
			li.className = "selected";
		}
		document.getElementById('zones').appendChild(li);
	}
	mode('normal');
	document.getElementById("output").value = "";
}

function displayContinent(n) {
	var e = document.getElementById('from');
	var e2 = document.getElementById('to');
	var first1 = false;
	var first2 = false;
	for (var i = 0; i < e.childNodes.length; i++) {
		var l = e.childNodes[i];
		if ((cmode == 'normal' && n != l.cont) || first1) {
			l.style.backgroundColor = 'transparent';
			l.style.fontWeight = 'normal';
			l.className = '';
		}
		if (cmode == 'normal' && l.className == 'selected')
			first1 = true;
		l.style.display = (n == l.cont ? 'block' : 'none');
		var l = e2.childNodes[i];
		if ((cmode == 'normal' && n != l.cont) || first2) {
			l.style.backgroundColor = 'transparent';
			l.style.fontWeight = 'normal';
			l.className = '';
		}
		if (cmode == 'normal' && l.className == 'selected')
			first2 = true;
		l.style.display = (n == l.cont ? 'block' : 'none');
	}
	document.getElementById('arrow').style.paddingTop = Math.round((document.getElementById('from').scrollHeight - 51) / 2) + 'px';
}

function mode(s) {
	cmode = s;
	displayContinent(ccont);
	if (s == 'normal') {
		document.getElementById('arrow').style.display = 'block';
		document.getElementById('to').style.display = 'block';
		document.getElementById('output').style.display = 'block';
		document.getElementById('outputlist').style.display = 'none';
		document.getElementById('h1').innerHTML = "1. Choose two locations";
		document.getElementById('plength').style.display = 'block';
	} else {
		document.getElementById('arrow').style.display = 'none';
		document.getElementById('to').style.display = 'none';
		document.getElementById('output').style.display = 'none';
		document.getElementById('outputlist').style.display = 'block';
		document.getElementById('h1').innerHTML = "1. Choose locations to start from";
		document.getElementById('plength').style.display = 'none';
	}
}

function generateSW() {
	var client = '';
	if (document.getElementById('slotZMUD').checked == true) client = "zmud";
	if (document.getElementById('slotMUSH').checked == true) client = "mush";
	if (document.getElementById('slotPORTAL').checked == true) client = "portal";
	//if (document.getElementById('slotHUMAN').checked == true) client = "human";
	if (cmode == 'normal') {
		errors = '';
		if (to == -1 || from == -1) {
			errors += "<li>Select some places. We won't charge.</li>\n";
		} else if (from == to) {
			errors += "<li>You're trying to walk to the same place you start at! Silly.</li>\n";
		} else if (vs[from][VS_ZONE] != vs[to][VS_ZONE]) {
			errors += "<li>You're trying to walk between two zones. You'll get your feet wet.</li>\n";
		}

		if (errors.length == 0) {
			var walk = dijkstra(es, vs, from, to);
			document.getElementById('length').innerHTML = walk.length;
			document.getElementById('output').value = formatSW(walk, client);
			document.getElementById('e1').innerHTML = "";
		} else {
			document.getElementById('e1').innerHTML = "<ul>" + errors + "</ul>";
			document.getElementById('length').innerHTML = "0";
			document.getElementById('output').value = "";
		}
	} else if (cmode == 'list') {
		var walk = "";
		var e = document.getElementById('from');
		document.getElementById('outputlist').value = '';
		var nodes = [];
		for (var i = 0; i < e.childNodes.length; i++) {
			var l = e.childNodes[i];
			if (l.className != 'selected') continue;
			nodes[nodes.length] = l.n;
		}
		for (var ii = 0; ii < nodes.length; ii++) {
			i = nodes[ii];
			dijkstra(es, vs, i, -1);
			for (var jj = 0; jj < nodes.length; jj++) {
				j = nodes[jj];
				if (i == j || !vs[j][VS_END]) continue;
				var walk = walkBack(es, vs, j);
				if (walk !== false) {
					document.getElementById('outputlist').value = document.getElementById('outputlist').value + formatSWList(i, j, walk, client) + "\n";
				}
			}
		}
	}
}

function formatSW(s, f) {
	if (f == 'zmud') {
		s = '.' + formatSWMultiple(s);
	}
	if (f == 'mush') {
		s = '#' + formatSWMultiple(s).replace(/h/g, '(nw)').replace(/j/g, '(ne)').replace(/k/g, '(sw)').replace(/l/g, '(se)');
	}
	if (f == 'portal') {
		s = s.replace(/(.)/g, ';$1').replace(/h/g, 'nw').replace(/j/g, 'ne').replace(/k/g, 'sw').replace(/l/g, 'se');
	}
	if (f == 'human') {
		s = formatSWMultiple(s).replace(/h/g, " northwest,").replace(/j/g, " northeast,").replace(/k/g, " southwest,").replace(/l/g, " southeast,").replace(/n/g, " north,").replace(/s/g, " south,").replace(/w/g, " west,").replace(/e/g, " east,");
	}
	return s;
}

function formatSWMultiple(s) {
	var r = "";
	var results = s.match(/(n+|s+|w+|e+|h+|j+|k+|l+|u+|d+)/g);
	for (var d = 0; d < results.length; d++) {
		r += (results[d].length == 1 ? '' : '' + results[d].length) + results[d].charAt(0);
	}
	return r;
}

function formatSWList(from, to, s, f) {
	if (f == 'zmud') {
		return "#PATH {" + vs[from][VS_NAME] + " to " + vs[to][VS_NAME] + "} {" + formatSW(s, f) + "}";
	}
}

function dijkstra(es, vs, from, to) {
	var i = 0;
	var c = from;
	for (i in vs) {
		vs[i][VS_DONE] = false;
		vs[i][VS_WEIGHT] = inf;
	}

	vs[c][VS_DONE] = true;
	vs[c][VS_WEIGHT] = 0;

	while (true) {
		for (var i = 0; i < es.length; i++) {
			if ((es[i][ES_TO] == c || es[i][ES_FROM] == c) && (es[i][ES_WEIGHT] + vs[c][VS_WEIGHT] < vs[(es[i][ES_TO] == c ? es[i][ES_FROM] : es[i][ES_TO])][VS_WEIGHT])) {
				vs[(es[i][ES_TO] == c ? es[i][ES_FROM] : es[i][ES_TO])][VS_WEIGHT] = es[i][ES_WEIGHT] + vs[c][VS_WEIGHT];
			}
		}
		var min = inf;
		for (i in vs) {
			if (vs[i][VS_WEIGHT] < min && vs[i][VS_DONE] == false) {
				min = vs[i][VS_WEIGHT];
				c = i;
			}
		}
		if (min == inf) {
			break;
		}
		vs[c][VS_DONE] = true;
	}

	if (to == -1) {
		return "";
	} else {
		var walk = walkBack(es, vs, to);
		return walk;
	}
}

function walkBack(es, vs, to) {
	var c = to;
	var walk = "";
	while (true) {
		if (vs[c][VS_WEIGHT] == 0) {
			break;
		}
		var oc = c;
		for (var i = 0; i < es.length; i++) {
			if (c == es[i][ES_FROM] && vs[c][VS_WEIGHT] == vs[es[i][ES_TO]][VS_WEIGHT] + es[i][ES_WEIGHT]) {
				c = es[i][ES_TO];
				if (es[i][ES_RPATH].length == 0) {
					es[i][ES_RPATH] = reverse(es[i][ES_PATH]);
				}
				walk = es[i][ES_RPATH] + walk;
			} else if (c == es[i][ES_TO] && vs[c][VS_WEIGHT] == vs[es[i][ES_FROM]][VS_WEIGHT] + es[i][ES_WEIGHT]) {
				c = es[i][ES_FROM];
				walk = es[i][ES_PATH] + walk;
			}
		}
		if (oc == c) return false;
	}
	return walk;
}
function reverse(s) {
	r = "";
	for (var i = 0; i < s.length; i++) {
		r = rmap[s.charAt(i)] + r;
	}
	return r;
}
function cloneObject(what) {
	for (i in what) {
		if (typeof what[i] == 'object') {
			this[i] = new cloneObject(what[i]);
		}
		else
			this[i] = what[i];
	}
}