package javakurs.musterloesung.uebung09.aufgabe2;

import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;

import javakurs.musterloesung.uebung08.DirectedGraph;
import javakurs.musterloesung.uebung08.Edge;
import javakurs.musterloesung.uebung08.VertexPropertyMap;

/**
 * {@link DijkstraShortestPath} provides a method to calculate single source
 * shortest paths in a graph using Dijkstra's algorithm.
 *
 * @author Bernd Kiefer, DFKI
 * @author Joerg Steffen, DFKI
 * @version $Id: DijkstraShortestPath.java,v 1.2 2011/01/21 08:38:08 steffen Exp $
 */
public final class DijkstraShortestPath {

  /**
   * This would create a new instance of {@link DijkstraShortestPath}. Not to be
   * used.
   */
  private DijkstraShortestPath() {

    // private constructor to enforce noninstantiability
  }


  /**
   * This calculates the shortest path from the given start vertex to the given
   * end vertex.
   *
   * @param g
   *          the directed graph where to search the shortest path
   * @param startVertex
   *          the start vertex
   * @param endVertex
   *          the end vertex
   * @return a list edges representing the shortest path or {@code null} if
   *         there is no path between the start vertex and the end vertex
   */
  public static List<Edge<Integer>> shortestPath(
      DirectedGraph<Integer> g,
      int startVertex,
      int endVertex) {

    // contains for each vertex the edge starting at the predecessor vertex if
    // existing
    VertexPropertyMap<Edge<Integer>> predecessor =
      new VertexPropertyMap<Edge<Integer>>(g);

    // contains for each vertex the distance
    VertexPropertyMap<Integer> distances = new VertexPropertyMap<Integer>(g);

    // init comparator to be used in priority queue
    Comparator<Integer> vertComp = new DistComp(distances);

    // init priority queue returning the vertex with the lowest distance
    PriorityQueue<Integer> q =
      new PriorityQueue<Integer>(
          g.getNumberOfVertices() / 4 + 1, vertComp);

    distances.put(startVertex, 0);
    // we will use the fact that a vertex is not in distances to indicate its
    // value is +infinity; see compare method in DistComp

    // add all vertices to the queue
    for (int vertex = 0; vertex < g.getNumberOfVertices(); ++vertex) {
      if (g.isVertex(vertex)) {
        q.offer(vertex);
      }
    }

    while (!q.isEmpty()) {
      int minWeightVertex = q.poll();
      // stop if end vertex is found
      if (minWeightVertex == endVertex) {
        break;
      }
      // follow outgoing edges
      for (Edge<Integer> outEdge : g.getOutEdges(minWeightVertex)) {
        // check if triangle equation holds
        int newDist = distances.get(minWeightVertex) + outEdge.getEdgeInfo();
        int target = outEdge.getEndVertex();
        if (distances.get(target) == null || newDist < distances.get(target)) {
          // update weight and predecessor
          distances.put(target, newDist);
          predecessor.put(target, outEdge);
          // re-insert vertex to trigger queue update
          q.remove(target);
          q.add(target);
        }
      }
    }

    // create edge list with shortest path
    List<Edge<Integer>> result = null;
    // is there a connection from start to end: distance end vertex < infinity?
    if (distances.get(endVertex) != null) {
      result = new LinkedList<Edge<Integer>>();
      Edge<Integer> curr = predecessor.get(endVertex);
      do {
        result.add(0, curr);
        curr = predecessor.get(curr.getStartVertex());
      } while (curr != null);
    }

    return result;
  }


  /**
   * {@link DistComp} implements a comparator for directed graph vertices based
   * on their distance.
   */
  static class DistComp
      implements Comparator<Integer> {

    /**
     * Contains the distance for each vertex.
     */
    private VertexPropertyMap<Integer> _distances;


    /**
     * This creates a new instance of {@link DistComp} using the given
     * distances.
     *
     * @param distances
     *          a properties map with the distances
     */
    public DistComp(VertexPropertyMap<Integer> distances) {

      _distances = distances;
    }


    /**
     * {@inheritDoc}
     */
    @Override
    public int compare(
        Integer vertex1, Integer vertex2) {

      Integer dist1 = _distances.get(vertex1);
      Integer dist2 = _distances.get(vertex2);

      if (dist1 == null) {
        return (dist2 == null) ? 0 : 1;
      }
      if (dist2 == null) {
        return -1;
      }
      return (dist1 - dist2);
    }
  }
}
