// watch:done,pred,P,i,v
var undef=-1;

function weight(a,b,arr){
    if(arr[a][b] == undefined)
        return inf;
    else
        return arr[a][b];
}

function Dijkstra(V,s,d,arr)
{
    var P = new Array(V);
    var i;
    var done = new Array(V);
    var pred = new Array(V);

    for(i=0; i<V; i++){
        P[i] = inf;
        pred[i]=undef;
        done[i]=false;
    }
    P[s]=0;

    var v;
    for(v=0; v<V; v++){
        var minDist = inf, closest = -1;
        for (i=0; i<V; i++){
            if(!done[i]){
                if(P[i] <= minDist){
                    minDist = P[i]; closest = i;
                }
            }
        }
        done[closest] = true;

        for (i=0; i<V; i++){
            if (!done[i]){
                var w = weight(closest, i, arr);
                if (P[closest]+w < P[i]){
                    P[i] = P[closest] + w;
                    pred[i] = closest;
                }
            }
        }
    }
    printPath(d,P,pred);
}

function getNextValidSegment(v,pred)
{
    var c = v;
    var p;
    while(c >= 0)
    {
        p = c;
        c = pred[c];
        if(c>=0 && segs[getSegment(c,p)])
            return(getSegment(c,p));
    }
    return undefined;
}

function getRow(src,hwy,dst,seg)
{
    for(var i=0; i<src.length; i++)
    {
        if(hwy == src[i][0] &&
                dst == src[i][1] &&
                seg == src[i][2])
        {
            return(src[i]);
        }
    }
}

function printPath(i,P,pred)
{
    var route = new Array();

    if (P[i] < inf) 
    {
        var thePath = '';
        var ttime = 0.0;
        var tdist = 0;
        var v = i;
        var prev;
        var lasthwy = -1;
        var turn = '';
        var alt = 0;
        var alttxt='';
        while (v>=0)
        {
            prev = v;
            v = pred[v];
            if(v>=0 && segs[getSegment(v,prev)])
            {
                var idx = getSegment(v,prev);
                var nextidx;
                var row = new Array();

                
                turn = '';
                segs[idx] ? lasthwy = segs[idx][0] : null;
                nextidx = getNextValidSegment(v,pred);
                if(segs[nextidx] && lasthwy != segs[nextidx][0]){ 
                    if( lasthwy != -1)
                        turn = '<b><u>Turn</u></b> onto <b>Hwy&nbsp;'+segs[idx][0]+ '</b><br>'; 
                }
                if(nextidx == undefined)
                {
                    turn = '<b><u>Start</u></b> on <b>Hwy&nbsp;'+segs[idx][0] + '</b><br>';
                }
                row['turn'] = turn;

                row['firstcol'] = '<td rowspan="2">' + turn;
                row['firstcol'] += turn=='' ? 'Hwy&nbsp;' + segs[idx][0] + ' ' : '';
                row['firstcol'] += segs[idx] ? 'for '+segs[idx][5]+'km' : '';
                row['firstcol'] += segs[idx] ? ' (' + Math.round(segs[idx][6]) + 'min) ' : '';
                row['firstcol'] += '</td>';
                row['middlecol'] = '<td id="from">';
                row['middlecol'] += turn=='' ? 'Continue on Hwy <b>'+segs[idx][0]+'</b>' : 'From <b>' + names[v] +'</b>';
                row['middlecol'] += ' to <b>' + names[prev] +'</b></td>';
               
                row['hwy'] = segs[idx][0];
                row['dist'] = segs[idx][5];
                row['time'] = Math.round(segs[idx][6]);
                row['from'] = names[v];
                row['to'] = names[prev];
                
                tdist += segs[idx] ? segs[idx][5] : 0;
                ttime += segs[idx] ? parseFloat(segs[idx][6]) : 0;
                var w = getWeather(prev);
                var wd = getWeatherDataRow(prev);
                row['w'] = w;
                row['wd'] = wd;
                
                row['weathercol'] = '<td rowspan="2">';
                row['weathercol'] += (w && wd) ? ' <table><tr><td><a href="'+w+'" target="_blank"><img src="'+wd[2]+'" align="left" border="0"></a></td><td class="weather"><a href="'+w+'" target="_blank">'+getWeatherString(wd[1])+'</td></tr></table>' : '';
                row['weathercol'] += '</td></tr>';

                // lookup conditions
                var cond = '';
                if(segs[idx])
                {
                    var r = getRow(cndtxt,segs[idx][0],segs[idx][1],segs[idx][2]);
                    if(r)
                    {
                        row['cond1'] = '<td colspan=1>'+r[3].replace(/^:\ /g, '').replace(/^\ :\ /g, '')+'&nbsp;&nbsp;('+r[4]+')</td></tr>';
                        cond += row['cond1']; 
                    }
                    r = getRow(iabr,segs[idx][0],segs[idx][1],segs[idx][2]);
                    if(r)
                    {
                        row['cond2'] = '<td></td><td colspan=2>'+r[3]+' '+r[4]+' (<a href="'+r[6]+'" onClick="return popwin(\''+r[6]+'\');">details</a>)&nbsp;&nbsp;&nbsp;'+r[5]+'</td></tr>';
                        cond += row['cond2'];
                    }

                }
                row['cond'] = cond;
                alt = alt ^ 1; // XOR between 0 and 1
                alttxt = alt ? 'class="alt"' : '';
                route.unshift(row);
            }
        }

        var rowstr = '';
        var first, last, writerow;
        var cdist = 0;
        var ctime = 0;
        var alt = 1;
        var alttxt = '';
        var held = false;
        for (var i=0; i<route.length; i++)
        {
            writerow = false;

            if(i+1 == route.length)
                writerow = true;
            if(route[(i+1)] && route[(i+1)]['turn'] != '') 
                writerow = true;
            if(route[i]['w'] && route[i]['wd']) 
                writerow = true;
            if(route[(i+1)] && route[(i+1)]['cond'] != route[i]['cond']) 
                writerow = true;

            cdist += route[i]['dist'];
            ctime += route[i]['time'];
            
            if(writerow)
            {
                var firstcol, middlecol;
                alttxt = alt ? 'class="alt"' : '';
                firstcol = '<td rowspan="2">';
                if(first) 
                {
                    firstcol += first['turn'];
                    firstcol += first['turn'] =='' ? 'Hwy&nbsp;' + first['hwy'] + ' ' : '';
                    middlecol = first['turn'] =='' ? route[i]['middlecol'] : first['middlecol'];
                }
                else
                {
                    firstcol += route[i]['turn'];
                    firstcol += route[i]['turn'] =='' ? 'Hwy&nbsp;' + route[i]['hwy'] + ' ' : '';
                    middlecol = route[i]['middlecol'];
                }
                firstcol += 'for '+cdist+'km';
                firstcol += ' (' + ctime + 'min) ';
                firstcol += '</td>';
                rowstr += '<tr '+alttxt+'>' + firstcol + middlecol + route[i]['weathercol'] + '<tr '+alttxt+'>' + route[i]['cond1'];
                if(route[i]['cond2']) rowstr += '<tr '+alttxt+'>' + route[i]['cond2'];
                cdist = 0;
                ctime = 0;
                held = false;
                last = undefined;
                first = undefined;
                alt = alt ^ 1; // XOR between 0 and 1
            }
            else
            {
                if(!held)
                {
                    // first row to be held over
                    first = route[i];
                }
                held = true;
                last = route[i];
            }
        }

        thePath = '<table><tr class="head"><td></td><td id="to">Road Segment and Conditions</td><td>Weather</td></tr>'+rowstr+'</table>';
        //var timestr = parseInt(ttime/60) +':' + ((Math.round(ttime%60)<10)?'0'+Math.round(ttime%60):Math.round(ttime%60));
        var timestr = parseInt(ttime/60) +' hours ' + ((Math.round(ttime%60)<10)?'0'+Math.round(ttime%60):Math.round(ttime%60))+ ' minutes';
        message("Distance: <b>" + tdist +'</b> km in approximately <b>'+ timestr +'</b>  '+nl+thePath+' '+nl);

     } 
     else 
     {
        message("no path");
     }
}

function getSegment(start,end)
{
    for(var i=0; i<segs.length; i++)
    {
        if(segs[i][3] == start && segs[i][4] == end ||
            segs[i][3] == end && segs[i][4] == start)
        {
            return(i);
        }
    }
    return(-1);
}

function getWeather(idx)
{
    for(var i=0; i<weather.length; i++)
    {
        if(weather[i][0] == idx)
            return weather[i][2];
    }
}
function getWeatherDataRow(idx)
{
    if(! weather_data)
        return undefined;
    for(var i=0; i<weather.length; i++)
    {
        if(weather[i][0] == idx)
        {
            for(var j=0; j<weather_data.length; j++)
            {
                if(weather[i][1] == weather_data[j][0])
                {
                    return weather_data[j];
                }
            }
        }
    }
}
function getWeatherString(i)
{
    return(city[i] +'</a><br><b>'+ cond2[i] +'</b><br>'+ cond3[i]);
}