package graphs.weighteddigraphs;

import java.util.Vector;
import java.util.Collection;
import java.util.PriorityQueue;
import java.util.Iterator;

/**
 *  WeightedDiGraph class represents an directed graph of vertices named 0 through numV-1.
 *  Parallel edges and self-loops are permitted.
 */
public class WeightedDiGraph {
	
	 private final int numV;
	 private Vector<EdgeCouple>[] adjacents;
	    
	 /**
	  * Create an empty digraph with V vertices.
	  */
	 public WeightedDiGraph(int v) {
		 if (v < 0) 
			 throw new RuntimeException("Number of vertices must be nonnegative");
		 this.numV = v;
		 adjacents = (Vector<EdgeCouple>[]) new Vector[numV];
		 for (int i = 0; i < v; i++) {
			 adjacents[i] = new Vector<EdgeCouple>();
		 }
	 }

	 /**
	  * Return the number of vertices in the digraph.
	  */
	 public int numberOfVerteces() {
		 return numV;
	 }

	 /**
	  * Add directed edge to the digraph.
	  */
	 public void addEdge(int from, int to, double weight) {
		 adjacents[from].add(new EdgeCouple(to, weight));
	 }

	 /**
	  * Return the list of neighbors of vertex v as in Iterable.
	  */
	 public Iterable<EdgeCouple> adjacents(int v) {
		 return adjacents[v];
	 }
	 
	 /**
	  * Simple implementation of Dijkstra's shortest path
	  * algorithm in a weighted digraph.
	  * Method returns an array of minimal distances from
	  * source to every vertex of the graph.
	  */
	 public double[] dijkstraSP(int source) {
		 boolean included[] = new boolean[numV];
		 if(source < 0 || source >= numV)
			 throw new IllegalArgumentException("Illegal vertex number");
		 double[] result = new double[numV];
		 PriorityQueue<PathCouple> pq = new PriorityQueue<PathCouple>();
		 pq.add(new PathCouple(source,0));
		 while(!pq.isEmpty()) {
			 PathCouple c = pq.poll();
			 double d = c.getDist();
			 int v = c.getVert();
			 if(!included[v]) {
				 result[v] = d;
				 included[v] = true;
				 for(EdgeCouple e: adjacents(v))
					 pq.add(new PathCouple(e.toVertex(), e.weight() + d));
			 }
		 }
		 return result;
	 }

	 /**
	  * Return a string representation of the digraph.
	  */
	 public String toString() {
		 StringBuilder s = new StringBuilder();
		 s.append(numV + "  \n");
		 for (int v = 0; v < numV; v++) {
			 s.append(v + ": ");
			 for (EdgeCouple w : adjacents[v]) {
				 s.append(w + " ,");
			 }
			 s.append("\n");
		 }
		 return s.toString();
	 }

}

/**
*  Class represents a weighted edge in an directed graph.
*/
class EdgeCouple {
	private final int v;
    private final double weight;

   /**
     * Create a directed edge to v with given weight.
     */
    public EdgeCouple(int v, double weight) {
        this.v = v;
        this.weight = weight;
    }

   /**
     * Return the vertex where this edge ends.
     */
    public int toVertex() {
        return v;
    }

   /**
     * Return the weight of this edge.
     */
    public double weight() { return weight; }

   /**
     * Return a string representation of this edge.
     */
    public String toString() {
        return "< " + v + " ; " + weight + " >";
    }

}

/**
*  Class represents a couple <vertex, special distance to it>.
*/
class PathCouple implements Comparable<PathCouple> {
	  private int vertex;
	  private double distance;

	  public PathCouple (int v, double d) {
	    vertex = v;
	    distance = d;
	  }

	  public int compareTo(PathCouple c) {
	    if(this.distance == c.distance)
	      return 0;
	    if(this.distance < c.distance)
	      return -1;
	    return 1;
	  }

	  public double getDist() {
	    return distance;
	  }

	  public int getVert() {
	    return vertex;
	  }
}