package ie.dcu.graph.dijkstra;

import java.util.*;

/**
 * Implementation of Dijkstra's shortest path algorithm.
 * 
 * @author Kevin McGuinness
 * 
 * @param <T>
 *        The node type for the graph.
 */
public class Graph<T> {
	
	/**
	 * Map of nodes to node objects.
	 */
	private final Map<T, Node<T>> nodes;
	
	/**
	 * The source node from which all paths are found.
	 */
	private T source;
	
	/**
	 * Flag to indicate whether or not the algorithm has been run.
	 */
	private boolean done;
	
	/**
	 * Construct empty graph.
	 */
	public Graph() {
		nodes = new HashMap<T, Node<T>>();
		done = false;
	}
	
	/**
	 * Construct empty graph with the given initial capacity of nodes.
	 */
	public Graph(int initialCapacity) {
		nodes = new HashMap<T, Node<T>>(initialCapacity);
		done = false;
	}
	
	/**
	 * Add a directed edge between the given source and target objects.
	 */
	public void addDirectedEdge(T source, T target, double weight) {
		checkWeight(weight);
		
		// Get source node
		Node<T> srcNode = nodes.get(source);
		if (srcNode == null) {
			srcNode = new Node<T>(source);
			nodes.put(source, srcNode);
		}
		
		// Get target node
		Node<T> dstNode = nodes.get(target);
		if (dstNode == null) {
			dstNode = new Node<T>(target);
			nodes.put(target, dstNode);
		}
		
		// Add edge
		srcNode.addDirectedEdge(dstNode, weight);
		done = false;
	}
	
	/**
	 * Add an undirected edge between the given nodes
	 */
	public void addUndirectedEdge(T node1, T node2, double weight) {
		checkWeight(weight);
		
		// Get source node
		Node<T> srcNode = nodes.get(node1);
		if (srcNode == null) {
			srcNode = new Node<T>(node1);
			nodes.put(node1, srcNode);
		}
		
		// Get target node
		Node<T> dstNode = nodes.get(node2);
		if (dstNode == null) {
			dstNode = new Node<T>(node2);
			nodes.put(node2, dstNode);
		}
		
		// Add edge
		srcNode.addDirectedEdge(dstNode, weight);
		dstNode.addDirectedEdge(srcNode, weight);
		done = false;
	}
	
	/**
	 * Returns the (unmodifiable) set of nodes in the graph.
	 */
	public Set<T> nodes() {
		return Collections.unmodifiableSet(nodes.keySet());
	}
	
	/**
	 * Returns true if the given object is a node in the graph.
	 */
	public boolean hasNode(T node) {
		return nodes.containsKey(node);
	}
	
	/**
	 * Returns the edge weight for the directed edge between src and dst, or
	 * positive infinity if there is no such edge.
	 */
	public double getEdgeWeight(T src, T dst) {
		Node<T> n1 = nodes.get(src);
		if (n1 != null) {
			for (Edge<T> edge : n1.edges) {
				if (edge.target.equals(dst)) {
					return edge.weight;
				}
			}
		}
		return Double.POSITIVE_INFINITY;
	}
	
	/**
	 * Run Dijkstra's method for the given source node.
	 */
	public void findPaths(T source) {
		
		if (!hasNode(source)) {
			throw new IllegalArgumentException("src node not in graph");
		}
		
		// Check if we are re-running for a new source node
		if (this.source != source) {
			this.source = source;
			this.done = false;
		}
		
		if (!done) {
			
			// Initialize nodes
			for (Node<T> node : nodes.values()) {
				node.visited = false;
				node.distance = Double.POSITIVE_INFINITY;
				node.previous = null;
			}
			
			// Create node queue
			PriorityQueue<Node<T>> queue = 
				new PriorityQueue<Node<T>>();
			
			// Set distance to zero and add first node to the queue
			Node<T> node = nodes.get(source);
			node.distance = 0.0;
			queue.add(node);
			
			// Run Dijkstra's method
			while (!queue.isEmpty()) {
				node = queue.remove();
				
				if (node.visited) {
					continue;
				}
			
				node.visited = true;
				
				for (Edge<T> edge : node.edges) {
					Node<T> target = edge.target;

					double distance = node.distance + edge.weight;
					if (distance < target.distance) {
						target.previous = node;
						target.distance = distance;
					}
					
					if (!target.visited) {
						queue.add(target);
					}
				}
			}
			
			// Done
			done = true;
		}
	}
	
	/**
	 * Returns the source node or null if the {@link #findPaths(Object)}
	 * method has not yet been called.
	 */
	public T getSource() {
		return source;
	}

	/**
	 * Returns the shortest path from the source to the object.
	 * 
	 * @throws IllegalStateException
	 *         if the {@link #findPaths(Object)} function has not been called.
	 */
	public List<T> getPathTo(T object) {
		List<T> path = getPathFrom(object);
		Collections.reverse(path);
		return path;
	}
	
	/**
	 * Returns the shortest path from the object to the source.
	 * 
	 * @throws IllegalStateException
	 *         if the {@link #findPaths(Object)} function has not been called.
	 */
	public List<T> getPathFrom(T object) {
		ensureDone();
		Node<T> node = nodes.get(object);
		List<T> list = new LinkedList<T>();
		while (node != null) {
			list.add(node.object);
			node = node.previous;
		}
		return list;
	}
	
	/**
	 * Get the distance to the object. Returns infinity if the object is
	 * not in the graph.
	 */
	public double getDistanceTo(T object) {
		ensureDone();
		Node<T> node = nodes.get(object);
		return node != null ? node.distance : Double.POSITIVE_INFINITY;
	}
	
	/**
	 * Get the distance from the source node to the farthest node in graph. 
	 * Returns zero if there are no nodes.
	 */
	public double getDistanceOfLongestPath() {
		double max = 0.0;
		for (Node<T> n : nodes.values()) {
			if (n.distance > max) {
				max = n.distance;
			}
		}
		return max;
	}
	
	/**
	 * Returns the node that is farthest away from the source node.
	 * 
	 * @throws IllegalStateException
	 *         if the {@link #findPaths(Object)} function has not been called.
	 */
	public T getFarthestNode() {
		ensureDone();
		
		T node = null;
		double max = 0.0;
		for (Node<T> n : nodes.values()) {
			if (n.distance > max) {
				max = n.distance;
				node = n.object;
			}
		}
		
		return node;
	}
	
	/**
	 * Throws an exception if the done flag is not set.
	 */
	private final void ensureDone() {
		if (!done) {
			throw new IllegalStateException("findPaths never called");
		}
	}
	
	/**
	 * Check the specified edge weight is valid.
	 */
	private static void checkWeight(double weight) {
		if (weight < 0) {
			throw new IllegalArgumentException("negative weights not allowed");
		}
		
		if (weight == Double.POSITIVE_INFINITY) {
			throw new IllegalArgumentException("infinite weights not allowed");
		}
	}
	
	/**
	 * Graph node containing an object of type T.
	 */
	private static class Node<T> implements Comparable<Node<?>> {
		
		/**
		 * The object the node contains.
		 */
		public final T object;
		
		/**
		 * List of edges to adjacent nodes.
		 */
		public final List<Edge<T>> edges;
		
		/**
		 * Flag to indicate the node has been visited (dijkstras algorithm).
		 */
		public boolean visited;
		
		/**
		 * The minimum distance so far to this node (dijkstras algorithm)
		 */
		public double distance;
		
		/**
		 * The previous node in the shortest path.
		 */
		public Node<T> previous;
		
		/**
		 * Construct the node for an object.
		 * 
		 * @param object An object (non-null)
		 */
		public Node(T object) {
			assert (object != null);
			this.object = object;
			this.edges = new ArrayList<Edge<T>>(8);
			this.visited = false;
			this.distance = Double.POSITIVE_INFINITY;
			this.previous = null;
		}
		
		/**
		 * Add a directed edge between this node and an adjacent one.
		 */
		public final void addDirectedEdge(Node<T> target, double weight) {
			edges.add(new Edge<T>(target, weight));
		}
		
		/**
		 * Nodes are sorted based on distance.
		 */
		public int compareTo(Node<?> n) {
			return distance < n.distance ? -1 : (distance == n.distance ? 0 : 1);
		}
	}
	
	/**
	 * A weighted directed edge.
	 */
	private static class Edge<T> {
		
		/**
		 * Target node
		 */
		public final Node<T> target;
		
		/**
		 * Edge weight
		 */
		public final double weight;
		
		/**
		 * Edge constructor
		 */
		public Edge(Node<T> target, double weight) {
			assert (target != null);
			this.target = target;
			this.weight = weight;
		}
	}
}