/*
   MST_Prim.js: JavaScript implementation of Prim's minimum spanning tree algorithm.[1]
                Requires the Prototype JavaScript library (1.5 or later).

    Copyright (C) 2008-2009 Kalle Räisänen.

    This program is free software: you can redistribute it and/or modify
    it under the terms of the GNU Affero General Public License as published by
    the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU Affero General Public License for more details.

    You should have received a copy of the GNU Affero General Public License
    along with this program.  If not, see <http://www.gnu.org/licenses/>.



   [1] Orwant, Jon, Jarkko Hietaniemi, and John Macdonald (1999). /Mastering Algorithms
            with Perl/. Sebastopol, CA: O'Reilly Books.
*/

var INF = 0xffffffff; // Infinite is only (2^32)-1! Film at 11.

var MST_Prim = Class.create({
/*
 *	new MST_Prim(graph)
 *		graph: 2-dimensional array, structured like:
 *			[
 *				[e0-0, e0-1, e0-2, ...],
 *				[e1-0, e1-1, e1-2, ...],
 *				[e2-0, e2-1, e2-2, ...],
 *				...
 *			]
 *			So, graph[1][0] represents the edge-weight 1->0, &c.
 *			INF weights represent unconnected vertices.
 *
 *	returns: a new MST_Prim object.
 */
	initialize: function(graph)
	{
		this._inGraph = graph;
	}

/*
 *	MST_Prim.prim(sortResult)
 *		sortResult: boolean, whether to sort the returned result.
 *
 *	returns: an array of hashes, each representing an edge in the
 *	         form {from, to, weight}.
 */
	,prim: function(sortResult) {
		var inGraph   = this._inGraph;
		var mstEdges  = [];
		var connected = new Array(inGraph.length);
		var i;
	
		for(i = 0; i < connected.length; i++)
			connected[i] = false;

		for(i = 0; i < connected.length - 1; i++) {
			var found     = {weight: INF};
			var firstTime = (i == 0);

			for(var j = 0; j < inGraph.length; j++) {
				for(var k = j + 1; k < inGraph.length; k++) {
					if( ( firstTime || (connected[j] !=  connected[k]) )
							&& (inGraph[j][k] < found.weight)  )
						found = {weight: inGraph[j][k], from: j, to: k};
				}
			}
				if(found.weight < INF) {
					mstEdges.push(found);
					connected[found.from] = true;
					connected[found.to]   = true;
				}
		}

		if(typeof sortResult != 'undefined' && sortResult)
			return mstEdges.sort(this._edgeCmp);
		else
			return mstEdges;

	} // .prim

/*
 *	MST_Prim._edgeCmp(a, b)
 *		a: an edge in the form {from, to, weight}.
 *		b: ditto.
 *
 *	returns: -1 if a is "less than" b and 1 if is b is "less than" a.
 */
	,_edgeCmp: function(a, b) {
		if(a.from == b.from)
			return a.to   < b.to   ? -1 : 1;
		else
			return a.from < b.from ? -1 : 1;
	} // ._edgeCMP

}); // MST_Prim