import Lab3Help.*;
import graph.*;
import java.util.*;

class Dijkstra implements Path
{
    private Graph	g;
    private LinkedList	path;
    private int		pathLength;

    public Dijkstra (String stopFile, String lineFile)
    {
	buildGraph(stopFile, lineFile);
	path	    = new LinkedList();
	pathLength  = 0;
    }

    private void buildGraph (String stopFile, String lineFile)
    {
	Lab3File    lab3    = new Lab3File();
	Vector	    stops   = lab3.readStops(stopFile);
	Vector	    lines   = lab3.readLines(lineFile);
	Iterator    i;

	g = new Graph();

	/* Add stops */
	i = stops.iterator();
	while (i.hasNext())
	    g.addNode(((BStop)i.next()).getName());
	
	/* Add edges */
	i = lines.iterator();
	while (i.hasNext())
	{
	    BLineTable	lt	= (BLineTable)i.next();
	    BLineStop	bstops[] = lt.getStops();

	    for (int n = 1; n < bstops.length; n++)
		g.addEdge(g.nodeIndex(bstops[n-1].getName()), g.nodeIndex(bstops[n].getName()), bstops[n].getTime());
	}
    }

    public void computePath (String from, String to)
    {
	int distances[] = new int[g.nodeCount()];
	int parents[]	= new int[g.nodeCount()];
	Heap q		= new Heap();
	int start	= g.nodeIndex(from);
	int end		= g.nodeIndex(to);

	/* Initialize */
	for (int n = 0; n < parents.length; n++)
	    parents[n] = -1;

	/* Add start edge to queue */
	q.insertItem(new Integer(0), new Graph.Edge(start, start, 0));
	
	/* Do the lambada */
	while (!q.isEmpty())
	{
	    int		d = ((Integer)q.minKey()).intValue();
	    Graph.Edge	e = (Graph.Edge)q.removeMin();

	    /* New-found node or shorter distance */
	    if (parents[e.to()] == -1
		|| d < distances[e.to()])
	    {
		distances[e.to()]   = d;
		parents[e.to()]	    = e.from();

		/* Add neighbours to queue */
		Iterator i = g.getNeighbours(e.to()).iterator();
		while (i.hasNext())
		{
		    Graph.Edge neighbour = (Graph.Edge)i.next();
		    q.insertItem(new Integer(d + neighbour.weight()), neighbour);
		}
	    }
	}

	/* Set path information */
	path = new LinkedList();
	parents[start] = -1;

	if (start == end)
	    path.addFirst(g.nodeName(start));
	else if (parents[end] != -1)
	{
	    int	node = end;

	    do {
		//System.err.println("  at " + g.nodeName(node));
		path.addFirst(g.nodeName(node));
		node = parents[node];
	    } while (node != -1);
	}
	pathLength = distances[end];
    }

    public Iterator getPath ()
    {
	return path.iterator();
    }

    public int getPathLength ()
    {
	return pathLength;
    }

}