import java.util.PriorityQueue;

import org.junit.jupiter.api.Test;

import static org.junit.Assert.fail;
import static org.junit.jupiter.api.Assertions.assertEquals;

import java.util.Hashtable;
import java.util.List;
import java.util.LinkedList;
import java.util.NoSuchElementException;

/**
 * This class extends the BaseGraph data structure with additional methods for
 * computing the total cost and list of node data along the shortest path
 * connecting a provided starting to ending nodes. This class makes use of
 * Dijkstra's shortest path algorithm.
 */
public class DijkstraGraph<NodeType, EdgeType extends Number> extends BaseGraph<NodeType, EdgeType>
		implements GraphADT<NodeType, EdgeType> {

	/**
	 * While searching for the shortest path between two nodes, a SearchNode
	 * contains data about one specific path between the start node and another node
	 * in the graph. The final node in this path is stored in it's node field. The
	 * total cost of this path is stored in its cost field. And the predecessor
	 * SearchNode within this path is referened by the predecessor field (this field
	 * is null within the SearchNode containing the starting node in it's node
	 * field).
	 *
	 * SearchNodes are Comparable and are sorted by cost so that the lowest cost
	 * SearchNode has the highest priority within a java.util.PriorityQueue.
	 */
	protected class SearchNode implements Comparable<SearchNode> {
		public Node node;
		public double cost;
		public SearchNode predecessor;

		public SearchNode(Node node, double cost, SearchNode predecessor) {
			this.node = node;
			this.cost = cost;
			this.predecessor = predecessor;
		}

		public int compareTo(SearchNode other) {
			if (cost > other.cost)
				return +1;
			if (cost < other.cost)
				return -1;
			return 0;
		}
	}

	/**
	 * This helper method creates a network of SearchNodes while computing the
	 * shortest path between the provided start and end locations. The SearchNode
	 * that is returned by this method is represents the end of the shortest path
	 * that is found: it's cost is the cost of that shortest path, and the nodes
	 * linked together through predecessor references represent all of the nodes
	 * along that shortest path (ordered from end to start).
	 *
	 * @param start the data item in the starting node for the path
	 * @param end   the data item in the destination node for the path
	 * @return SearchNode for the final end node within the shortest path
	 * @throws NoSuchElementException when no path from start to end is found or
	 *                                when either start or end data do not
	 *                                correspond to a graph node
	 */
	protected SearchNode computeShortestPath(NodeType start, NodeType end) {
		// Check if both start and end nodes are present in the graph.
		if (!(nodes.containsKey(start) && nodes.containsKey(end))) {
			throw new NoSuchElementException("There was no path found.");
		}

		// Create a priority queue of SearchNode to store nodes to be processed.
		PriorityQueue<SearchNode> priorityQueue = new PriorityQueue<>();

		// Create a Hashtable to store visited nodes.
		Hashtable<NodeType, SearchNode> visitedNodes = new Hashtable<NodeType, SearchNode>();

		// Create a new SearchNode with the starting node and a cost of zero, and add it
		// to the priority queue.
		SearchNode startSN = new SearchNode(nodes.get(start), 0.0, null);
		priorityQueue.add(startSN);
		while (!(priorityQueue.isEmpty())) {

			// Remove the node with the lowest cost from the priority queue.
			SearchNode nodeVar = priorityQueue.poll();
			// Add the current node to the visitedNodes Hashtable.
			visitedNodes.put(nodeVar.node.data, nodeVar);

			// If the current node is the destination node, return the SearchNode.
			if (nodeVar.node.data.equals(end)) {
				return nodeVar;
			}
			for (Edge edge : nodeVar.node.edgesLeaving) {

				// Check if the successor node of the edge is unvisited.
				if (!visitedNodes.containsKey(nodeVar)) {
					SearchNode tempSN = new SearchNode(edge.successor, edge.data.doubleValue() + nodeVar.cost, nodeVar);

					priorityQueue.add(tempSN);
				}
			}
		}

		// If no path is found, throw a NoSuchElementException.
		throw new NoSuchElementException("No path found from " + start.toString() + " to " + end.toString());
	}

	/**
	 * Returns the list of data values from nodes along the shortest path from the
	 * node with the provided start value through the node with the provided end
	 * value. This list of data values starts with the start value, ends with the
	 * end value, and contains intermediary values in the order they are encountered
	 * while traversing this shorteset path. This method uses Dijkstra's shortest
	 * path algorithm to find this solution.
	 *
	 * @param start the data item in the starting node for the path
	 * @param end   the data item in the destination node for the path
	 * @return list of data item from node along this shortest path
	 */
	public List<NodeType> shortestPathData(NodeType start, NodeType end) {

		// Create a new linked list to store the nodes in the shortest path.
		List<NodeType> linkedList = new LinkedList<>();
		SearchNode endNode = computeShortestPath(start, end);

		// Loop through the SearchNodes starting from the end node, and add their data
		// to the linked list in reverse order.
		while (endNode != null) {
			linkedList.add(0, endNode.node.data);
			endNode = endNode.predecessor;
		}

		// Return the linked list containing the shortest path data.
		return linkedList;
	}

	/**
	 * Returns the cost of the path (sum over edge weights) of the shortest path
	 * freom the node containing the start data to the node containing the end data.
	 * This method uses Dijkstra's shortest path algorithm to find this solution.
	 *
	 * @param start the data item in the starting node for the path
	 * @param end   the data item in the destination node for the path
	 * @return the cost of the shortest path between these nodes
	 */
	public double shortestPathCost(NodeType start, NodeType end) {
		return computeShortestPath(start, end).cost;
	}

	/**
	 * 
	 * This test case verifies the accuracy of the shortestPathCost method in the
	 * DijkstraGraph class by comparing the computed shortest path value from Node A
	 * to Node F against the expected value from the April 4th lecture example.
	 */
	@Test
	public void test1() {
		// Create a new instance of DijkstraGraph
		DijkstraGraph dijkstraGraph = new DijkstraGraph();
		// Create the Nodes needed to build the graph
		Node nodeA = new Node((NodeType) "A");

		Node nodeB = new Node((NodeType) "B");
		Node nodeC = new Node((NodeType) "C");
		Node nodeD = new Node((NodeType) "D");
		Node nodeE = new Node((NodeType) "E");
		Node nodeF = new Node((NodeType) "F");

		// Insert the Nodes into the DijkstraGraph instance
		dijkstraGraph.insertNode(nodeA.data);
		dijkstraGraph.insertNode(nodeB.data);

		dijkstraGraph.insertNode(nodeC.data);
		dijkstraGraph.insertNode(nodeD.data);
		dijkstraGraph.insertNode(nodeE.data);
		dijkstraGraph.insertNode(nodeF.data);

		// Create the edges between the Nodes in the graph
		dijkstraGraph.insertEdge(nodeA.data, nodeB.data, 1);

		dijkstraGraph.insertEdge(nodeA.data, nodeC.data, 2);
		dijkstraGraph.insertEdge(nodeB.data, nodeF.data, 1.9);
		dijkstraGraph.insertEdge(nodeC.data, nodeD.data, 2);

		dijkstraGraph.insertEdge(nodeD.data, nodeE.data, 2);
		dijkstraGraph.insertEdge(nodeE.data, nodeF.data, 2);

		// Verify that the shortest path cost from Node A to Node F is equal to the
		// expected value

		assertEquals((dijkstraGraph.shortestPathCost(nodeA.data, nodeF.data)), 2.9);
	}

	/**
	 * 
	 * This test case tests whether the shortest path from Node A to Node D matches
	 * the example presented in the April 4th lecture. Additionally, it verifies
	 * that the sequence of nodes in the shortest path matches the expected
	 * sequence. The test aims to ensure that the implementation of the algorithm
	 * produces the expected results.
	 */
	@Test
	public void test2() {
		// Initialize objects and variables
		List<NodeType> linkedList = new LinkedList<>();

		DijkstraGraph dijkstraGraph = new DijkstraGraph();

		Node nodeA = new Node((NodeType) "A");
		Node nodeB = new Node((NodeType) "B");

		Node nodeC = new Node((NodeType) "C");
		Node nodeD = new Node((NodeType) "D");
		Node nodeE = new Node((NodeType) "E");
		Node nodeF = new Node((NodeType) "F");

		// Create a linked list with the expected shortest path
		linkedList.add(nodeA.data);
		linkedList.add(nodeC.data);

		linkedList.add(nodeD.data);
		linkedList.add(nodeE.data);

		// Add nodes to the graph
		dijkstraGraph.insertNode(nodeA.data);
		dijkstraGraph.insertNode(nodeB.data);

		dijkstraGraph.insertNode(nodeC.data);
		dijkstraGraph.insertNode(nodeD.data);
		dijkstraGraph.insertNode(nodeE.data);
		dijkstraGraph.insertNode(nodeF.data);

		// Add edges to the graph
		dijkstraGraph.insertEdge(nodeA.data, nodeB.data, 1);
		dijkstraGraph.insertEdge(nodeA.data, nodeC.data, 2);

		dijkstraGraph.insertEdge(nodeB.data, nodeF.data, 1.9);
		dijkstraGraph.insertEdge(nodeC.data, nodeD.data, 2);
		dijkstraGraph.insertEdge(nodeD.data, nodeE.data, 2);
		dijkstraGraph.insertEdge(nodeE.data, nodeF.data, 2);

		// Check if the calculated shortest path matches the expected sequence of nodes
		// and cost
		assertEquals((dijkstraGraph.shortestPathData(nodeA.data, nodeE.data)), linkedList);

		assertEquals((dijkstraGraph.shortestPathCost(nodeA.data, nodeE.data)), 6);
	}

	/**
	 * This test case is designed to ensure that the expected exception is thrown
	 * when attempting to find the shortest path from node D to node A in a graph
	 * where this path does not exist. The test is validating the correctness of the
	 * graph's shortest path algorithm by verifying that it throws the expected
	 * exception in this scenario.
	 */
	@Test
	public void test3() {
		// Create a linked list and a DijkstraGraph object
		List<NodeType> linkedList = new LinkedList<>();
		DijkstraGraph dijkstraGraph = new DijkstraGraph();

		// Create six Node objects with data A, B, C, D, E, F
		Node nodeA = new Node((NodeType) "A");
		Node nodeB = new Node((NodeType) "B");

		Node nodeC = new Node((NodeType) "C");
		Node nodeD = new Node((NodeType) "D");
		Node nodeE = new Node((NodeType) "E");
		Node nodeF = new Node((NodeType) "F");

		// Add three nodes to the linked list
		linkedList.add(nodeA.data);

		linkedList.add(nodeC.data);
		linkedList.add(nodeD.data);

		// Insert all six nodes into the DijkstraGraph object
		dijkstraGraph.insertNode(nodeA.data);
		dijkstraGraph.insertNode(nodeB.data);

		dijkstraGraph.insertNode(nodeC.data);
		dijkstraGraph.insertNode(nodeD.data);
		dijkstraGraph.insertNode(nodeE.data);
		dijkstraGraph.insertNode(nodeF.data);

		// Insert six edges into the DijkstraGraph object with their respective nodes
		// and weights
		dijkstraGraph.insertEdge(nodeA.data, nodeB.data, 1);

		dijkstraGraph.insertEdge(nodeA.data, nodeC.data, 2);
		dijkstraGraph.insertEdge(nodeB.data, nodeF.data, 1.9);
		dijkstraGraph.insertEdge(nodeC.data, nodeD.data, 2);
		dijkstraGraph.insertEdge(nodeD.data, nodeE.data, 2);

		dijkstraGraph.insertEdge(nodeE.data, nodeF.data, 2);

		// Test if calling the shortestPathCost method on nodeF to nodeC, nodeD to
		// nodeB,
		// nodeB to nodeA, and nodeD to nodeB will throw NoSuchElementExceptions as
		// expected
		try {
			dijkstraGraph.shortestPathCost(nodeF.data, nodeC.data);
			fail("Expected exception was not thrown");
		} catch (NoSuchElementException e) {

		}

		try {
			dijkstraGraph.shortestPathCost(nodeD.data, nodeB.data);
			fail("Expected exception was not thrown");
		} catch (NoSuchElementException e) {

		}

		try {
			dijkstraGraph.shortestPathData(nodeB.data, nodeA.data);
			fail("Expected exception was not thrown");
		} catch (NoSuchElementException e) {

		}

		try {
			dijkstraGraph.shortestPathData(nodeD.data, nodeB.data);
			fail("Expected exception was not thrown");
		} catch (NoSuchElementException e) {

		}
	}

}