using Algorithms.Nw.ShortestPath;
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using U.Graph;

namespace Algorithms.Nw.KShortestPath
{
    public class Yens : KShortestPathAlgorithm
    {
        public override void run(Graph graph, ShortestPathAlgorithm spa, int s, int t, int K, bool keepTime)
        {
            if (keepTime) { base.startTimer(); }
            int N = graph.getNbNodes();
            SubGraph subGraph = new SubGraph(N);
            
            P = new List<PathAndCost>();
            P.Add(PathAndCost.getShortestPath(graph, null, spa, s, t));
            List<PathAndCost> B = new List<PathAndCost>();
            if (K == 0) { return; }
            for (int k = 1; k < K; k++)
            {
                PathAndCost lastA = P[k - 1];
                for (int i = 0; i < lastA.nodeIndices.Count - 1; i++)
                {
                    int spurNode = lastA.nodeIndices[i];
                    PathAndCost rootPath = lastA.getRootPath(i + 1, graph);
                    foreach (PathAndCost ypath in P)
                    {
                        if (i + 1 < ypath.nodeIndices.Count)
                        {
                            if (ypath.sameRootPath(rootPath))
                            {
                                int from = ypath.nodeIndices[i];
                                int to = ypath.nodeIndices[i + 1];
                                subGraph.closeArc(from, to);
                            }
                        }
                    }
                    for (int r = 0; r < i; r++)
                    {
                        int toCloseNodeIndex = lastA.nodeIndices[r];
                        subGraph.closeNode(toCloseNodeIndex, graph);
                    }
                    PathAndCost spurPath = PathAndCost.getShortestPath(graph, subGraph, spa, spurNode, t);
                    if (spurPath != null)
                    {
                        PathAndCost totalPath = new PathAndCost(rootPath, spurPath, graph);
                        if (!B.Contains(totalPath)) { B.Add(totalPath); } // buna neden gerek oldugunu anlamadim ama gerek oldu
                    }
                    subGraph.restore();
                }
                if (B.Count == 0) { return; }
                B.OrderBy(x => x.cost);
                if (B.Count > K - k) { P.AddRange(B.GetRange(0, K - k)); return; }
                P.Add(B[0]);
                B.RemoveAt(0);
            }
        }

    }
}
