package se.chalmers.cs.gf.graph;

import java.util.*;
import java.io.*;

/**
 *  Uses Dijkstras shortest-path algorithm to find a shortest path
 *  in a graph.
 */
public class DijkstraPath {

        private Graph<NodeData,String> graph;

        public DijkstraPath(Graph<?,String> graph) {
                this.graph = graph.copyChangeNodeValues(null);
        }

        /**
         *  Find the shortest path between two nodes in the graph.
         */
        public Path computePath(String fromName, String toName) {
                // reset all node data
                for (Graph<NodeData,String>.Node node : graph.nodes())
                        node.setValue(new NodeData());

                Graph<NodeData,String>.Node from = graph.getNode(fromName);
                from.getValue().dist = 0.0;

                PriorityQueue<Double,Graph<NodeData,String>.Node> q = HeapPriorityQueue.create();
                q.insertItem(0.0, from);
      
                int nodesLeft = graph.countNodes();
                while (!q.isEmpty() && nodesLeft > 0) {
                        Graph<NodeData,String>.Node u = q.removeMin();
                        NodeData uData = u.getValue();
                        if (!uData.visited) {
                                uData.visited = true;
                                nodesLeft--;
                                for (Graph<NodeData,String>.Edge edge : u.adjacent()) {
                                        Graph<NodeData,String>.Node to = edge.getTo();
                                        NodeData toData = to.getValue();
                                        double newDist = uData.dist + edge.getWeight();
                                        if (newDist < toData.dist) {
                                                toData.dist = newDist;
                                                toData.prev = edge;
                                                q.insertItem(newDist, to);
                                        }
                                }
                        }
                }

                List<Graph<NodeData,String>.Edge> pathEdges = edgesTo(graph.getNode(toName));
                return edgesToPath(pathEdges);
        }

        /**
         *  Get the list of edges going from the start node to the given node.
         */
        private List<Graph<NodeData,String>.Edge> edgesTo(Graph<NodeData,String>.Node node) {
                LinkedList<Graph<NodeData,String>.Edge> edges = new LinkedList<Graph<NodeData,String>.Edge>();
                Graph<NodeData,String>.Edge e = node.getValue().prev;
                while (e != null) {
                        edges.addFirst(e);
                        e = e.getFrom().getValue().prev;
                }
                return edges;
        }

        /**
         *  Take a list of edges and make a Path.
         */
        private Path edgesToPath(List<Graph<NodeData,String>.Edge> edges) {
                Path path = new Path();
                for (Graph<NodeData,String>.Edge e : edges)
                        path.addLeg(e.getFrom().getKey(), e.getTo().getKey(), 
                                    e.getWeight(), e.getValue());

                return path;
        }

        private static class NodeData {
                public double dist = Double.POSITIVE_INFINITY;
                public Graph<NodeData,String>.Edge prev = null;
                public boolean visited = false;
        }

}