import java.util.Comparator;
import java.util.Objects;
import java.util.PriorityQueue;

// shortest path
public class GraphAdjacentMatrix_Dijkstra_BFS_MinHeap {
    public static int empty = -1;

    private int adjMatrix[][];
    private int numVertices;
    private boolean visited[];

    public GraphAdjacentMatrix_Dijkstra_BFS_MinHeap(int numVertices) {
        this.numVertices = numVertices;

        adjMatrix = new int[numVertices][numVertices];
        for (int i = 0; i < adjMatrix.length; i++) {
            for (int j = 0; j < adjMatrix[i].length; j++) {
                adjMatrix[i][j] = empty;
            }
        }

        visited = new boolean[numVertices];
    }


    public int getWeight(int i, int j){
        return adjMatrix[i][j];
    }

    public void setEdge(int i, int j, int weight) {
        adjMatrix[i][j] = weight;
//        adjMatrix[j][i] = true; // directed
    }

    public void delEdge(int i, int j) {
        adjMatrix[i][j] = empty;
//        adjMatrix[j][i] = false; // directed
    }

    public boolean isEdge(int i, int j) {
        return (adjMatrix[i][j] != -1);
    }

    public int first(int v1){
        int[] ary = this.adjMatrix[v1];
        int firstNeighborIndex = this.numVertices; // return n if none
        for (int i = 0; i < ary.length; i++) {
            if (ary[i] != empty){
                firstNeighborIndex = i;
                break;
            }
        }
        return firstNeighborIndex;
    }

    public int next(int v1, int v2){
        int[] ary = this.adjMatrix[v1];
        int nextNeighborIndex = this.numVertices; // return n if none
        for (int i = v2 + 1; i < ary.length; i++) {
            if (ary[i] != empty){
                nextNeighborIndex = i;
                break;
            }
        }
        return nextNeighborIndex; // return n if none
    }

    // calculate the shortest distances between the startingVertice to all other vertices
    public static int[] dijkstra(int startingVertice, GraphAdjacentMatrix_Dijkstra_BFS_MinHeap gam) {
        // initialize the final result array
        int[] distance = new int[gam.numVertices];
        for (int i = 0; i < distance.length; i++) {
            distance[i] = Integer.MAX_VALUE;
        }
        // the first vertex reached
        distance[startingVertice] = 0; // initialize first data - from startingVertice to each vertice (we will update this whenver we reach a vertex)

        // build MinHeap
        PriorityQueue<VElement> minHeap = new PriorityQueue<>(new VElementComparrator());
        for (int i = 0; i < gam.numVertices; i++) {
            minHeap.add(new VElement(i, distance[i]));
        }

        while(!minHeap.isEmpty()){
            VElement ve = minHeap.remove(); // newtVertexWithTheMinimumDistance
            if (distance[ve.v] == Integer.MAX_VALUE) return distance; // if the next vertex with the minimum path is not reachable, we can end here noew

            gam.visited[ve.v] = true;

            // to think about whether it would be shorter if we take advantage the newly oppcupied vertex.
            for (int neighborV = gam.first(ve.v); neighborV < gam.numVertices; neighborV = gam.next(ve.v, neighborV)) {
                if (distance[neighborV] > (distance[ve.v] + gam.getWeight(ve.v, neighborV))) {
                    int previousDistance = distance[neighborV];
                    distance[neighborV] = (distance[ve.v] + gam.getWeight(ve.v, neighborV));
                    // if this happens, we need to update our minHeap, too
                    minHeap.remove(new VElement(neighborV, previousDistance));// check the overrided equals(...) and hash(...) of VElemnt
                    minHeap.add(new VElement(neighborV, distance[neighborV]));// check the overrided equals(...) and hash(...) of VElemnt
                }
            }
        }

//        for (int i = 0; i < gam.numVertices; i++) { // process all vertices
//            int v = gam.minVertex(distance); // get the next vertice with the shorted path here
//            if (v == empty) return distance;// all vertices are visited
//            if (distance[v] == Integer.MAX_VALUE) return distance; // if the next vertex is not reachable
//
//            gam.visited[v] = true;
//
//            // to think about whether it would be shorter if we take advantage the newly oppcupied vertex.
//            for (int neighborV = gam.first(v); neighborV < gam.numVertices; neighborV = gam.next(v, neighborV)) {
//                if (distance[neighborV] > (distance[v] + gam.getWeight(v, neighborV))) {
//                    distance[neighborV] = (distance[v] + gam.getWeight(v, neighborV));
//                }
//            }
//
//        }

        return distance;
    }

    // Imagine we convert the length n into n vertices and use BFS;
    // we will be making many redundant waves until we reach a vertex
    // Therefore, this method here is to help us save those steps and find the next vertex right away
    // (we could use minHeap to replace this method)
    //
    // find the shorted distance from startingVertice to D so far; this will be our next starting point
    private int minVertex(int[] distance) {
        int nextVWithShortestDistance = empty; // if all vertices are visited
        // initialize v to some unvisited vertex
        int i;
        for (i = 0; i < this.numVertices; i++) {
            if (!visited[i]) {
                nextVWithShortestDistance = i;
                break;
            }
        }
        // find the smallest D value
        for (i++; i < this.numVertices; i++) {
            if (!visited[i] && distance[i] < distance[nextVWithShortestDistance]) {
                nextVWithShortestDistance = i;
            }
        }

        return nextVWithShortestDistance;
    }

    private void Previsit(boolean[][] graph, int v) {
        System.out.println("Previsit: " + v);
    }

    private void Postvisit(boolean[][] graph, int v) {
        System.out.println("Postvisit: " + v);
    }

    public String toString() {
        StringBuilder s = new StringBuilder();
        for (int i = 0; i < numVertices; i++) {
            s.append(i + ": ");
            for (int j : adjMatrix[i]) {
                s.append((i != empty?1:0) + " ");
            }
            s.append("\n");
        }
        return s.toString();
    }

    public static void main(String[] args) {
        GraphAdjacentMatrix_Dijkstra_BFS_MinHeap gam = new GraphAdjacentMatrix_Dijkstra_BFS_MinHeap(8);

        // directed graph
        gam.setEdge(1, 2, 10);
        gam.setEdge(1, 3, 3);
        gam.setEdge(1, 4, 20);
        gam.setEdge(2, 4, 5);
        gam.setEdge(3, 2, 2);
        gam.setEdge(3, 5, 15);
        gam.setEdge(4, 5, 11);

        int[] distances = dijkstra(1, gam);
        printArray(distances);
        System.out.printf("the shortest distance between %d and %d = %d %n", 1, 1, distances[1]);
        System.out.printf("the shortest distance between %d and %d = %d %n", 1, 2, distances[2]);
        System.out.printf("the shortest distance between %d and %d = %d %n", 1, 3, distances[3]);
        System.out.printf("the shortest distance between %d and %d = %d %n", 1, 4, distances[4]);
        System.out.printf("the shortest distance between %d and %d = %d %n", 1, 5, distances[5]);

        System.out.println();
    }



    public static class VElement {
        public Integer v;
        public Integer distanceFromStartToV;

        public VElement(Integer v, Integer distanceFromStartToV) {
            this.v = v;
            this.distanceFromStartToV = distanceFromStartToV;
        }

        @Override
        public boolean equals(Object obj)
        {
            if(this == obj)
                return true;
            if(obj == null || obj.getClass()!= this.getClass())
                return false;

            // type casting of the argument.
            VElement ve = (VElement) obj;
            return  (ve.v == this.v);
        }

        @Override
        public int hashCode() {
            return Objects.hash(v);
        }

    }

    public static class VElementComparrator implements Comparator<VElement> {
        @Override
        public int compare(VElement ve1, VElement ve2) {
            return ve1.distanceFromStartToV.compareTo(ve2.distanceFromStartToV);
        }
    }

    ////////// UTIL ///////////

    private static void printArray(int[] ary){
        for (int i = 0; i < ary.length; i++) {
            System.out.printf("%4d" , ary[i]);
        }
        System.out.println();
    }
}