import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.List;


/**
 * Computes shortest paths using Dijksta's algorithm modified for MapReduce.
 */
public class Dijkstra {


    /**
     * Finds the shortest paths from the specified node to all other nodes.
     *
     * @param adjacencyMatrix the graph represented as an adjacency matrix
     * @param startNode       the start node
     * @return an array containing the lengths of the shortest paths from
     * startNode to the node corresponding to the index
     */
    public static int[] findShortestPaths(final int[][] adjacencyMatrix, final int startNode) {
        Mapper mapper = new Mapper() {
            @Override
            public List<Pair> map(Object node, Object shortestPath) {
                List<Pair> list = new ArrayList<>();
                for (int i = 0; i <adjacencyMatrix.length ; i++) {
                    int j =  (int) node;
                    list.add(new Pair(i,(int) shortestPath + adjacencyMatrix[i][j]));
                }
                return list;
            }
        };

        Reducer reducer = new Reducer() {
            @Override
            public List<Pair> reduce(Object o, List list) {
                int tmp = (int) list.get(0);
                for (int i = 1; i < list.size(); i++) {
                    if(tmp > (int) list.get(i)){
                        tmp = (int) list.get(i);
                    }
                }
                List res = new ArrayList();
                res.add(new Pair(o,tmp));
                return res;
            }
        };

        //init
        SequentialMapReduce seq = new SequentialMapReduce(mapper,reducer);
      //  ParallelMapReduce par = new ParallelMapReduce(mapper,reducer,4);
        List<Pair> list = new ArrayList<>();
        int shortestDistance = 99999;
        int shortestNode = startNode;
        int key = startNode;

        //init startlist
        for (int i = 0; i < adjacencyMatrix.length; i++) {
                list.add(new Pair(i,adjacencyMatrix[startNode][i]));
        }


       while(shortestNode != key || shortestNode == startNode ){
            shortestNode = key;
            //Compute the distance from startNode
            Iterable seqIt = seq.submit(list);
            Iterator it = seqIt.iterator();
           // Iterable parIt = par.submit(list);
           // Iterator it = parIt.iterator();

            //Retrieve node with shortest distance to startNode
            while (it.hasNext()) {
                Pair<Integer, Integer> pair = (Pair) it.next();
                if (pair.getValue() < shortestDistance) {
                    shortestDistance = pair.getValue();
                    key = pair.getKey();
                }
            }
            list.clear();
            for (int i = 0; i < adjacencyMatrix.length; i++) {
                list.add(new Pair(i, adjacencyMatrix[key][i]));
            }
        }

        int[] res = new int[list.size()];
        for (int r = 0; r < list.size(); r++) {
            res[r] = (int) list.get(r).getValue();
        }

        return res;
    }


    public static void main(final String[] args) {

        final int[][] adjacencyMatrix = {
                {0, 10, 1, 8, -1, -1},
                {10, 0, 7, -1, -1, 2},
                {1, 7, 0, 4, -1, 6},
                {8, -1, 4, 0, 6, -1},
                {-1, -1, -1, 6, 0, 3},
                {-1, 2, 6, -1, 3, 0}
        };

        final int[] shortest = findShortestPaths(adjacencyMatrix, 0);
        System.out.println(Arrays.toString(shortest));
    }
}