package ie.dcu.graph.dijkstra;

import java.util.*;

/**
 * Implementation of Dijkstra's shortest path algorithm, optimized
 * for nodes that have integer indices in a fixed integer range.
 * 
 * @author Kevin McGuinness
 */
public class IntGraph {
	
	/**
	 * Map of node indices to node objects.
	 */
	private final Node[] nodes;
	
	/**
	 * The source node from which all paths are found.
	 */
	private int source;
	
	/**
	 * Flag to indicate whether or not the algorithm has been run.
	 */
	private boolean done;

	/**
	 * Number of nodes inserted into the graph.
	 */
	private int nodeCount;
	
	/**
	 * Construct empty graph which can hold nodes up to the given node index.
	 */
	public IntGraph(int maxNodeIndex) {
		nodes = new Node[maxNodeIndex];
		nodeCount = 0;
		done = false;
	}
	
	/**
	 * Reset (clear) the graph.
	 */
	public void clear() {
		Arrays.fill(nodes, null);
		nodeCount = 0;
		done = false;
	}
	
	/**
	 * Add a directed edge between the given source and target objects.
	 */
	public void addDirectedEdge(int source, int target, double weight) {
		checkWeight(weight);
		
		// Get source node
		Node srcNode = nodes[source];
		if (srcNode == null) {
			srcNode = nodes[source] = new Node(source);
			nodeCount++;
		}
		
		// Get target node
		Node dstNode = nodes[target];
		if (dstNode == null) {
			dstNode = nodes[target] = new Node(target);
			nodeCount++;
		}
		
		// Add edge
		srcNode.addDirectedEdge(dstNode, weight);
		done = false;
	}
	
	/**
	 * Add an undirected edge between the given nodes
	 */
	public void addUndirectedEdge(int node1, int node2, double weight) {
		checkWeight(weight);
		
		// Get source node
		Node srcNode = nodes[node1];
		if (srcNode == null) {
			srcNode = nodes[node1] = new Node(node1);
			nodeCount++;
		}
		
		// Get target node
		Node dstNode = nodes[node2];
		if (dstNode == null) {
			dstNode = nodes[node2] = new Node(node2);
			nodeCount++;
		}
		
		// Add edge
		srcNode.addDirectedEdge(dstNode, weight);
		dstNode.addDirectedEdge(srcNode, weight);
		done = false;
	}
	
	/**
	 * Returns the set of nodes in the graph.
	 */
	public Set<Integer> nodes() {
		Set<Integer> nodeSet = new HashSet<Integer>();
		for (int i = 0; i < nodes.length; i++) {
			if (nodes[i] != null) {
				nodeSet.add(i);
			}
		}
		return nodeSet;
	}
	
	/**
	 * Returns true if the given object is a node in the graph.
	 */
	public boolean hasNode(int node) {
		return nodes[node] != null;
	}
	
	/**
	 * Returns the edge weight for the directed edge between src and dst, or
	 * positive infinity if there is no such edge.
	 */
	public double getEdgeWeight(int src, int dst) {
		Node n1 = nodes[src];
		if (n1 != null) {
			for (Edge 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(int source) {
		
		if (!hasNode(source)) {
			throw new IllegalArgumentException("src node not in graph: " + source);
		}
		
		// 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 node : nodes) {
				if (node != null) {
					node.visited = false;
					node.distance = Double.POSITIVE_INFINITY;
					node.previous = null;
				}
			}
			
			// Create node queue
			PriorityQueue<Node> queue = 
				new PriorityQueue<Node>();
			
			// Set distance to zero and add first node to the queue
			Node node = nodes[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 edge : node.edges) {
					Node target = edge.target;
					
					if (target.visited) {
						continue;
					}
					
					double distance = node.distance + edge.weight;
					if (distance < target.distance) {
						target.previous = node;
						target.distance = distance;
					}
				
					queue.add(target);	
				}
			}
			
			done = true;
		}
	}
	
	/**
	 * Returns the number of nodes in the graph.
	 */
	public int getNodeCount() {
		return nodeCount;
	}
	
	/**
	 * Returns the source node or null if the {@link #findPaths(int)}
	 * method has not yet been called.
	 */
	public int getSource() {
		return source;
	}

	/**
	 * Returns the shortest path from the source to the object.
	 * 
	 * @throws IllegalStateException
	 *         if the {@link #findPaths(int)} function has not been called.
	 */
	public List<Integer> getPathTo(int object) {
		List<Integer> path = getPathFrom(object);
		Collections.reverse(path);
		return path;
	}
	
	/**
	 * Returns the shortest path from the object to the source.
	 * 
	 * @throws IllegalStateException
	 *         if the {@link #findPaths(int)} function has not been called.
	 */
	public List<Integer> getPathFrom(int object) {
		ensureDone();
		Node node = nodes[object];
		List<Integer> list = new LinkedList<Integer>();
		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(int object) {
		ensureDone();
		Node node = nodes[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 n : nodes) {
			if (n != null && 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(int)} function has not been called.
	 */
	public int getFarthestNode() {
		ensureDone();
		
		int node = -1;
		double max = 0.0;
		for (Node n : nodes) {
			if (n != null && 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 implements Comparable<Node> {
		
		/**
		 * The object the node contains.
		 */
		public final int object;
		
		/**
		 * List of edges to adjacent nodes.
		 */
		public final List<Edge> 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 previous;
		
		/**
		 * Construct the node for an object.
		 * 
		 * @param object An object (non-null)
		 */
		public Node(int object) {
			this.object = object;
			this.edges = new ArrayList<Edge>(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 target, double weight) {
			edges.add(new Edge(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 {
		
		/**
		 * Target node
		 */
		public final Node target;
		
		/**
		 * Edge weight
		 */
		public final double weight;
		
		/**
		 * Edge constructor
		 */
		public Edge(Node target, double weight) {
			assert (target != null);
			this.target = target;
			this.weight = weight;
		}
	}
}