using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using U.Graph;
using U.ListOperations;

namespace Algorithms.Nw.ShortestPath
{
    public class Dijkstra : ShortestPathAlgorithm
    {
        private int N;
        private bool[] visited;
        
        // t = -1 if the algorithm will run for all destinations
        public override void run(Graph graph, SubGraph subGraph, int s, int t, bool keepTime)
        {
            if (subGraph == null) { calculate(graph, s, t, keepTime); return; }
            initialize(graph, keepTime);
            int i = s;
            d[i] = 0;
            bool cont = true;
            while (cont)
            {
                Node node = graph.getNode(i);
                int[] outArcIndices = node.getOutArcIndices();
                for (int a = 0; a < outArcIndices.Length; a++)
                {
                    Arc arc = graph.getArc(outArcIndices[a]);
                    int j = arc.getToIndex();
                    if (!subGraph.isArcClosed(i, j))
                    {
                        double cost = arc.getCost();
                        if (d[j] > d[i] + cost)
                        {
                            d[j] = d[i] + cost;
                            p[j] = i;
                        }
                    }
                }
                visited[i] = true;
                i = getMinCostNode(d, visited);
                if (i == -1 || i == t) { cont = false; }
            }
            finalize(keepTime);
        }
        // no subgraph
        private void calculate(Graph graph, int s, int t, bool keepTime)
        {
            initialize(graph, keepTime);
            int i = s;
            d[i] = 0;
            bool cont = true;
            while (cont)
            {
                Node node = graph.getNode(i);
                int[] outArcIndices = node.getOutArcIndices();
                for (int a = 0; a < outArcIndices.Length; a++)
                {
                    Arc arc = graph.getArc(outArcIndices[a]);
                    int j = arc.getToIndex();
                    double cost = arc.getCost();
                    if (d[j] > d[i] + cost)
                    {
                        d[j] = d[i] + cost;
                        p[j] = i;
                    }
                }
                visited[i] = true;
                i = getMinCostNode(d, visited);
                if (i == -1 || i == t) { cont = false; }
            }
            finalize(keepTime);
        }


        // Private
        private void initialize(Graph graph, bool keepTime)
        {
            this.N = graph.getNbNodes();
            this.visited = new bool[N];
            this.d = UArray.sameValues<double>(double.MaxValue, N);
            this.p = UArray.sameValues<int>(-1, N);
            if (keepTime) { base.startTimer(); }
        }
        private void finalize(bool keepTime)
        {
            if (keepTime) { base.stopTimer(); }
            Array.Clear(visited, 0, N);
        }
        private int getMinCostNode(double[] d, bool[] visited)
        {
            double cost = double.MaxValue;
            int minIndex = -1;
            for (int i = 0; i < d.Length; i++) { if (!visited[i]) { if (d[i] < cost) { cost = d[i]; minIndex = i; } } }
            return minIndex;
        }

    }
}
