package csx55.overlay.dijkstra;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.PriorityQueue;
import csx55.overlay.wireformats.LinkWeights;

/**
 * This class is used to compute the shortest path from a node to every other node in the overlay.
 * When the messaging nodes receive the link weights, it creates a RoutingCache object. This object
 * will call the createSP method of this class to find the shortest path, which is then cached in
 * RoutingCache. To calculate the shortest path, Dijkstra's algorithm is utilized. Therefore,
 * the algorithm will not work for negative edge weights.
 */
public class ShortestPath {
    private int adjMatrix[][];
    /*
     * An inner class that extends Comparable. It will be used for the priority queue so that Dijkstra's
     * algorithm is efficient.
     */
    class Vertex implements Comparable<Vertex> {
        String node;
        int distance;

        public Vertex(String node, int distance) {
            this.node = node;
            this.distance = distance;
        }

        @Override
        public int compareTo(Vertex rhs) {
            return Integer.compare(this.distance, rhs.distance);//compare this distance to distance passed in
        }
    }

    /**
     * This method is called from the RoutingCache class. It fills a HashMap that contains all of the routes to all other
     * nodes in this format: <ip:port, [ip:port1, ip:port2, ...]>. The weights contains all of the edge weights for all edges
     * in the overlay. The ipPort is an identifier for the current node, and allConnections is essentially msgRoutes.keySet().
     * This will first create an adjacency matrix of node size x node size and fill all values with the weights associated with
     * that link. The diagonal will be 0s since this is an undirected graph. It will then call dijkstra.
     */
    public void createSP(HashMap<String, String[]> msgRoutes, LinkWeights weights, String ipPort, ArrayList<String> allConnections) {
        int numNodes = allConnections.size();
        adjMatrix = new int[numNodes][numNodes];

        for (String connection: weights.getLinks()) {
            String[] splitLink = connection.split("\\s+");//Source: 0, Dest: 1, Weight: 2
            adjMatrix[allConnections.indexOf(splitLink[0])][allConnections.indexOf(splitLink[1])] = Integer.parseInt(splitLink[2]);
            adjMatrix[allConnections.indexOf(splitLink[1])][allConnections.indexOf(splitLink[0])] = Integer.parseInt(splitLink[2]);
        }

        //constructing Dijkstra
        dijkstra(msgRoutes, adjMatrix, allConnections, ipPort);
    }

    /**
     * This method follows the standard algorithm for computing the shortest paths using Dijkstra on a adjacency matrix.
     * The priority queue maintains the link weights in sorted order and greedly builds the shortest path. shortestPath is a
     * reference to the HashMap and this method modifies it by adding the shortest path to each peer.
     */
    private void dijkstra(HashMap<String, String[]> shortestPaths, int[][] adjMatrix, ArrayList<String> allNodes, String startNode) {
        int V = adjMatrix.length;
        int[] dist = new int[V];
        int[] pred = new int[V];
        PriorityQueue<Vertex> pq = new PriorityQueue<>();//create a priority queue

        Arrays.fill(dist, Integer.MAX_VALUE);//set all values to inf
        Arrays.fill(pred, -1);//set all values to -1
        dist[allNodes.indexOf(startNode)] = 0;
        pq.add(new Vertex(startNode, 0));

        while (!pq.isEmpty()) {
            Vertex current = pq.poll();
            int u = allNodes.indexOf(current.node);

            for (int i = 0; i < V; i++) {
                if (adjMatrix[u][i] != 0 && dist[u] != Integer.MAX_VALUE) {
                    int newDist = dist[u] + adjMatrix[u][i];
                    if (newDist < dist[i]) {
                        dist[i] = newDist;
                        pred[i] = u;
                        pq.add(new Vertex(allNodes.get(i), dist[i]));
                    }
                }
            }
        }

        //add to shortestPaths
        for (int i = 0; i < V; i++) {
            ArrayList<Integer> path = new ArrayList<>();
            ArrayList<String> strPath = new ArrayList<>();
            String curr = allNodes.get(i);
            if (!curr.equals(startNode)) {
                joinPath(i, pred, path);
                
                for (Integer j: path) {
                    if (allNodes.get(j).equals(startNode)) continue;
                    strPath.add(allNodes.get(j));
                }

                shortestPaths.put(curr, strPath.toArray(new String[strPath.size()]));
                path.clear();
            }
        }
    }

    /**
     * This method will construct the path from the starting node to the sink node
     * recursively by adding the node to the path list if the value at pred is not -1.
     * At each value of pred, the value indicates the index of the predecessor.
     */
    private void joinPath(int curr, int[] pred, ArrayList<Integer> path) {
        if (curr == -1) return;
        joinPath(pred[curr], pred, path);
        path.add(curr);
    }
}