using System;
using System.Collections.Generic;
using System.Collections.Immutable;
using System.Linq;
using ASD.Graphs;

namespace Lab05
{
    public class PathFinder : System.MarshalByRefObject
    {
        private class DijkstraK
        {
            public Int32 LastVertex { get; set; }
            public Double Cost { get; set; }
            public LinkedListNode<Edge> History { get; set; }
        }

        private class LinkedListNode<T>
        {
            public T Element { get; set; }
            public LinkedListNode<T> Previous { get; set; }
        }

        public (Edge[] edges, Double? sum) KShortestPathDijkstra(Graph g, int start, int end, int k)
        {
            var paths = new List<(LinkedListNode<Edge>, Double)>();
            var pathCounts = new Int32[g.VerticesCount];

            var priorityQueue = new PriorityQueue<DijkstraK, Double>((x1, x2) => x1.Value < x2.Value);
            priorityQueue.Put(new DijkstraK
            {
                LastVertex = start,
                History = null
            }, 0);

            while (!priorityQueue.Empty && pathCounts[end] < k)
            {
                var puCost = priorityQueue.BestPriority();
                var pu = priorityQueue.Get();
                var u = pu.LastVertex;
                pathCounts[u] += 1;

                if (u == end)
                {
                    paths.Add((pu.History, pu.Cost));
                    continue;
                }

                if (pathCounts[u] <= k)
                {
                    foreach (var edge in g.OutEdges(u))
                    {
                        var pvCost = puCost + edge.Weight;
                        priorityQueue.Put(new DijkstraK
                        {
                            LastVertex = edge.To,
                            Cost = pvCost,
                            History = new LinkedListNode<Edge>
                            {
                                Element = edge,
                                Previous = pu.History
                            }
                        }, pvCost);
                    }
                }
            }

            if (paths.Count < k)
            {
                return (null, null);
            }

            var (pointer, cost) = paths[k - 1];
            var tmp = new LinkedList<Edge>();
            while (pointer != null)
            {
                tmp.AddFirst(pointer.Element);
                pointer = pointer.Previous;
            }
            var path = tmp.ToArray();
            return (path, cost);
        }

        public (Edge[] edges, Double? sum) ShortestPathDijkstra(Graph g, int start, int end) =>
            KShortestPathDijkstra(g, start, end, 1);

        /// <summary>
        /// Algorytm znajdujący drugą pod względem długości najkrótszą ścieżkę między a i b.
        /// Możliwe, że jej długość jest równa najkrótszej (jeśli są dwie najkrótsze ścieżki, algorytm zwróci jedną z nich).
        /// Dopuszczamy, aby na ścieżce powtarzały się wierzchołki i/lub krawędzie.
        /// Można założyć, że a!=b oraz że w grafie nie występują pętle.
        /// </summary>
        /// <remarks>
        /// Wymagana złożoność do O(D), gdzie D jest złożonością implementacji alogorytmu Dijkstry w bibliotece Graph.
        /// </remarks>
        /// <param name="g">badany graf</param>
        /// <param name="path">null jeśli druga ścieżka nie istnieje, wpp ściezka jako tablica krawędzi</param>
        /// <returns>null jeśli druga ścieżka nie istnieje, wpp długość znalezionej ścieżki</returns>
        public double? FindSecondShortestPath(Graph g, int a, int b, out Edge[] path)
        {
            var (shortestPath, cost) = KShortestPathDijkstra(g, a, b, 2);
            path = shortestPath;
            return cost;
        }

        /// <summary>
        /// Algorytm znajdujący drugą pod względem długości najkrótszą ścieżkę między a i b.
        /// Możliwe, że jej długość jest równa najkrótszej (jeśli są dwie najkrótsze ścieżki, algorytm zwróci jedną z nich).
        /// Wymagamy, aby na ścieżce nie było powtórzeń wierzchołków ani krawędzi.
        /// Można założyć, że a!=b oraz że w grafie nie występują pętle.
        /// </summary>
        /// <remarks>
        /// Wymagana złożoność to O(nD), gdzie D jest złożonością implementacji algorytmu Dijkstry w bibliotece Graph.
        /// </remarks>
        /// <param name="g">badany graf</param>
        /// <param name="path">null jeśli druga ścieżka nie istnieje, wpp ściezka jako tablica krawędzi</param>
        /// <returns>null jeśli druga ścieżka nie istnieje, wpp długość tej ścieżki</returns>
        public double? FindSecondSimpleShortestPath(Graph g, int a, int b, out Edge[] path)
        {
            Edge[] bestCandidate = null;
            Double? bestCanditateCost = Double.PositiveInfinity;

            var (shortestPath, cost) = ShortestPathDijkstra(g, a, b);
            if (shortestPath == null)
            {
                path = null;
                return null;
            }

            Double commonPathCost = 0;
            for (var i = 0; i < shortestPath.Length; i++)
            {
                var edge = shortestPath[i];
                var rootNode = edge.From;
                g.DelEdge(edge.From, edge.To);
                var (pathProposition, pathPropositionCost) = ShortestPathDijkstra(g, rootNode, b); // Ścieżka od {rootNode} do {b}
                if (pathProposition != null && commonPathCost + pathPropositionCost < bestCanditateCost)
                {
                    bestCanditateCost = commonPathCost + pathPropositionCost;
                    bestCandidate = new Edge[i + pathProposition.Length];
                    Array.Copy(shortestPath, bestCandidate, i);
                    pathProposition.CopyTo(bestCandidate, i);
                }
                g.AddEdge(edge.From, edge.To, edge.Weight);

                commonPathCost += edge.Weight;
            }

            path = bestCandidate;
            return bestCanditateCost == Double.PositiveInfinity ? null : bestCanditateCost;
        }
    }
}