RoutingAlgorithm = function(){
	this.infinite=100000;
	this.undef=-1;
	this.names= new Array();
	this.m = new Array();
}

RoutingAlgorithm.prototype.weight = function(a,b){
	//return (this.m[a][b])[0];
	var array = this.m[a][b];
	if (array[2]) { //don't use central points for routing
		return 10000;
	}
	if (array[1]) { //segment inside buildings
		return (array[0] * 2);
	}
	return array[0];
}

RoutingAlgorithm.prototype.weightWarmest = function(a,b){
	var array = this.m[a][b];
	if (array[2]) { //don't use central points for routing
		return 10000;
	}
	if (array[1]) {
		return 0;
	}
	return array[0];
}

RoutingAlgorithm.prototype.shortestPath = function(V,s,d,isWarmest){
	
	//V - points + entrances
	//s - starting point
	//d - destination

	//create an array of points + entrances
	var P = new Array(V);
	var done = new Array(V);
	var pred = new Array(V);

	var i = V;
    var first = true;
    do {
    	var j = i - 1;
    	P[j] = this.infinite;
        pred[j]=this.undef;
        done[j]=false;
    } while (--i);
    P[s]=0;

    if (isWarmest) {
    	var v = V;
    	do {
            var minDist = this.infinite, closest = -1;
            var i = V;
            do {
            	var j = i -1;
                if(!done[j]){
                    if(P[j] <= minDist){
                        minDist = P[j];
                        closest = j;
                    }
                }
            } while (--i);
            done[closest] = true;

            var i = V;
            do {
            	var j = i - 1;
                if (!done[j]){
                	var w = this.weightWarmest(closest, j);
                    if (P[closest]+w < P[j]){
                        P[j] = P[closest] + w;
                        pred[j] = closest;
                    }
                }
            } while (--i);
        } while (--v);
    } else {
    	var v = V;
    	do {
            var minDist = this.infinite, closest = -1;
            var i = V;
            do {
            	var j = i - 1;
                if(!done[j]){
                    if(P[j] <= minDist){
                        minDist = P[j];
                        closest = j;
                    }
                }
            } while (--i);
            done[closest] = true;

            var i = V;
            do {
            	var j = i - 1;
                if (!done[j]){
                	var w = this.weight(closest, j);
                    if (P[closest]+w < P[j]){
                        P[j] = P[closest] + w;
                        pred[j] = closest;
                    }
                }
            } while (--i);
        } while (--v);
    }
    
    //done, now print
    i=d
    if (P[i] < this.infinite) {
        var thePath = this.names[i];
        var v = i;
        var addDistance = 0;
        var insidePath = new Array();
        //var lightedPath = new Array();
        while (v>0){
        	if (pred[v] != -1) {
        		var array = this.m[v][pred[v]];
            	if (array[1]) {
            		insidePath.push([this.names[v],this.names[pred[v]]]);
            		addDistance += array[0];
            	}
//            	if (array[3]) {
//            		lightedPath.push([this.names[v],this.names[pred[v]]]);
//            	}
            }
            v = pred[v];
            if (v>=0) {
            	thePath = this.names[v] + ',' + thePath;
            }
        }
        //var result = {addDistance: addDistance, path: thePath, insidePath: insidePath, lightedPath: lightedPath};
        var result = {addDistance: addDistance, path: thePath, insidePath: insidePath};
        return result;
        //return("Distance:" + P[i]+' ('+thePath+')'+"\n");
    } else {
        return {distance: null, path: null};
    }
}

RoutingAlgorithm.prototype.printMatrix = function(m){
	s="";

			for(var i =0; i < m.length; i++){
							for (var j=0; j < m.length; j++){
									s = s + "-----" + m[i][j];

							}
							s = s + "\n";
						}

	alert(s);
}
RoutingAlgorithm.prototype.init = function(adjacency, namesArr){
  	 
    this.m = adjacency;
    this.names = namesArr;
    
}

/*** TESTING CODE
var algorithm = new RoutingAlgorithm();
var names=new Array('1d','2p','3p','4p');
var x=inf;
 m = new Array();
	m[0]=new Array(0,19,x,x);
    m[1]=new Array(19,0,64,x);
    m[2]=new Array(x,64,0,105);
    m[3]=new Array(x,x,105,0);

algorithm.init(m,names);
algorithm.shortestPath(m.length,3,2);
*/