import java.util.*;

import org.junit.jupiter.api.Test;
import org.junit.jupiter.api.Assertions;

/**
 * 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 its node
     * field. The total cost of this path is stored in its cost field. And the
     * predecessor SearchNode within this path is referenced by the predecessor
     * field (this field is null within the SearchNode containing the starting
     * node in its 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 pred;

        public SearchNode(Node startNode) {
            this.node = startNode;
            this.cost = 0;
            this.pred = null;
        }

        public SearchNode(SearchNode pred, Edge newEdge) {
            this.node = newEdge.succ;
            this.cost = pred.cost + newEdge.data.doubleValue();
            this.pred = pred;
        }

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

    /**
     * Constructor that sets the map that the graph uses.
     */
    public DijkstraGraph() {
        super(new HashTableMap<>());
    }

    /**
     * Insert a new directed edge with a non-negative weight into the graph. If
     * an edge between pred and succ already exists, update the data stored in
     * that edge to the new weight.
     *
     * @param pred is the data contained in the new edge's predecesor node
     * @param succ is the data contained in the new edge's succ node
     * @param weight is the non-negative data to be stored in the new edge
     * @return true if the edge could be inserted or updated, or false if the
     * pred or succ data are not found in any graph nodes or the weight
     * specified is negative.
     */
    @Override
    public boolean insertEdge(NodeType pred, NodeType succ, EdgeType weight) {
        if (weight.doubleValue() < 0)
            return false;
        return super.insertEdge(pred, succ, weight);
    }

    /**
     * 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 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 starting node for the path
     * @param end   the destination node for the path
     * @return SearchNode for the final end node within the shortest path
     * @throws NoSuchElementException if either the start or the end node
     * cannot be found, or there is no path from start node to end node
     * @throws NullPointerException if the start or end node are null
     */
    protected SearchNode computeShortestPath(Node start, Node end) {
        if (start == null || end == null) {
            throw new NullPointerException("Start and end cannot be null");
        }

        // Make priority queue to store paths ordered by cost
        PriorityQueue<SearchNode> pq = new PriorityQueue<>();

        // Use HashTableMap to keep track of visited nodes
        HashTableMap<Node, Node> visited = new HashTableMap<>();

        // Initialize search with start node
        pq.add(new SearchNode(start));

        while (!pq.isEmpty()) {
            // Get path with lowest total cost
            SearchNode currentPath = pq.poll();

            // If we've already found the shortest path to node, skip it in loop
            if (visited.containsKey(currentPath.node)) {
                continue;
            }

            // Mark node as visited in set
            visited.put(currentPath.node, currentPath.node);

            // If destination reached, return SearchNode, which is the end of the chain
            if (currentPath.node.equals(end)) {
                return currentPath;
            }

            // Go through all outgoing edges from current node
            for (Edge edge : currentPath.node.edgesLeaving) {
                // Consider paths that have not been finalized yet
                if (!visited.containsKey(edge.succ)) {
                    // Create another SearchNode as the path to successor
                    SearchNode nextPath = new SearchNode(currentPath, edge);
                    pq.add(nextPath);
                }
            }
        }

        // If priority queue empty and nothing is returned, no path exists, throw error
        throw new NoSuchElementException("No path exists between start and end node");

    }
    /**
     * 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 shortest 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 nodes along this shortest path
     * @throws NoSuchElementException if either the start or the end node
     * cannot be found, or there is no path from start node to end node
     * @throws NullPointerException if the start or end node are null
     */
    public List<NodeType> shortestPathData(NodeType start, NodeType end) {
        // Look up start and end nodes in map and throws NoSuchElementException if not found
        Node startNode = nodes.get(start);
        Node endNode = nodes.get(end);

        //Compute shortest path with Dijkstra's algorithm
        SearchNode resultPath = computeShortestPath(startNode, endNode);

        // Trace back from end node to start with references to predecessor nodes
        LinkedList<NodeType> pathData = new LinkedList<>();
        SearchNode current = resultPath;

        while (current != null) {
            // Add to front of linked list to make final order start to end
            pathData.addFirst(current.node.data);
            current = current.pred;
        }

        return pathData;
    }

    /**
     * Returns the cost of the path (sum over edge weights) of the shortest
     * path from 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
     * @throws NoSuchElementException if either the start or the end node
     * cannot be found, or there is no path from start node to end node
     * @throws NullPointerException if the start or end node are null
     */
    public double shortestPathCost(NodeType start, NodeType end) {
        //Look up start and end nodes in map and throw NoSuchElementException if not found
        Node startNode = nodes.get(start);
        Node endNode = nodes.get(end);

        // Compute shortest path and return total cost stored in SearchNode
        SearchNode resultPath = computeShortestPath(startNode, endNode);
        return resultPath.cost;
    }

    /**
     * This test case verifies that the implementation when used on the graph traced in lecture
     * returns the expected values. Checks the shortest path from node A to node H.
     * Hand computed result from lecture should be [A, B, D, F, H] with 9.0 cost
     */
    @Test
    public void testLectureExamplePath() {
        DijkstraGraph<String, Integer> graph = new DijkstraGraph<>();
        // Insert all nodes from lecture example
        graph.insertNode("A");
        graph.insertNode("B");
        graph.insertNode("C");
        graph.insertNode("D");
        graph.insertNode("E");
        graph.insertNode("F");
        graph.insertNode("G");
        graph.insertNode("H");

        // Insert proper edges and weights as shown in lecture
        graph.insertEdge("A", "B", 4);
        graph.insertEdge("A", "C", 2);
        graph.insertEdge("A", "E", 15);
        graph.insertEdge("B", "D", 1);
        graph.insertEdge("B", "E", 10);
        graph.insertEdge("C", "D", 5);
        graph.insertEdge("D", "E", 3);
        graph.insertEdge("D", "F", 0);
        graph.insertEdge("F", "D", 2);
        graph.insertEdge("F", "H", 4);
        graph.insertEdge("G", "F", 4);

        // Verify cost to H: A(0) -> D(5) -> F(5) -> H(9)
        double expectedCost = 9.0;
        Assertions.assertEquals(expectedCost, graph.shortestPathCost("A", "H"), 0.001);

        // Verify path sequence to H
        List<String> expectedPath = Arrays.asList("A", "B", "D", "F", "H");
        Assertions.assertEquals(expectedPath, graph.shortestPathData("A", "H"));

    }

    /**
     * Checks the cost and sequence for a different path in lecture graph
     *  Checking path from A to E
     *  Expected result from tracing: Path [A, B, D, E] with cost 8.0.
     */
    @Test
    public void testLectureExampleDiffPath() {

        DijkstraGraph<String, Integer> graph = new DijkstraGraph<>();
        // Insert all nodes from lecture example
        graph.insertNode("A");
        graph.insertNode("B");
        graph.insertNode("C");
        graph.insertNode("D");
        graph.insertNode("E");
        graph.insertNode("F");
        graph.insertNode("G");
        graph.insertNode("H");

        // Insert proper edges and weights as shown in lecture
        graph.insertEdge("A", "B", 4);
        graph.insertEdge("A", "C", 2);
        graph.insertEdge("A", "E", 15);
        graph.insertEdge("B", "D", 1);
        graph.insertEdge("B", "E", 10);
        graph.insertEdge("C", "D", 5);
        graph.insertEdge("D", "E", 3);
        graph.insertEdge("D", "F", 0);
        graph.insertEdge("F", "D", 2);
        graph.insertEdge("F", "H", 4);
        graph.insertEdge("G", "F", 4);

        // Path A -> B -> D -> E (4 + 1 + 3 = 8) is shorter than A -> E (15) or other paths
        Assertions.assertEquals(8.0, graph.shortestPathCost("A", "E"), 0.001);
        Assertions.assertEquals(Arrays.asList("A", "B", "D", "E"), graph.shortestPathData("A", "E"));

    }

    /**
     * Tests behavior when no path exists (like node G from A)
     * or when nodes are missing from graph
     */
    @Test
    public void testLectureExampleMissing() {
        DijkstraGraph<String, Integer> graph = new DijkstraGraph<>();
        // Insert all nodes from lecture example
        graph.insertNode("A");
        graph.insertNode("B");
        graph.insertNode("C");
        graph.insertNode("D");
        graph.insertNode("E");
        graph.insertNode("F");
        graph.insertNode("G");
        graph.insertNode("H");

        // Insert proper edges and weights as shown in lecture
        graph.insertEdge("A", "B", 4);
        graph.insertEdge("A", "C", 2);
        graph.insertEdge("A", "E", 15);
        graph.insertEdge("B", "D", 1);
        graph.insertEdge("B", "E", 10);
        graph.insertEdge("C", "D", 5);
        graph.insertEdge("D", "E", 3);
        graph.insertEdge("D", "F", 0);
        graph.insertEdge("F", "D", 2);
        graph.insertEdge("F", "H", 4);
        graph.insertEdge("G", "F", 4);

        // Path from A to G does not exist
        Assertions.assertThrows(NoSuchElementException.class, () -> {
           graph.shortestPathCost("A", "G");
        });

        // Node "Z" should not exist in graph
        Assertions.assertThrows(NoSuchElementException.class, () -> {
            graph.shortestPathData("A", "Z");
        });
    }




}