using System;
using System.Collections.Generic;
using System.Linq;

namespace My.Collections;

public class ShortestPathGraph<T> : Graph<T>
{
    public ShortestPathGraph(bool directed = true) => Directed = directed;

    public (List<Node<T>> path, double distance) BFS(Node<T> start, Node<T> end)
    {
        var queue = new Queue<Node<T>>();
        var visited = new Dictionary<Node<T>, Node<T>?>();
        var distances = new Dictionary<Node<T>, double>();

        queue.Enqueue(start);
        visited[start] = null;  // Startknoten ohne Vorgänger
        distances[start] = 0;

        while (queue.Count > 0)
        {
            var current = queue.Dequeue();

            foreach (var neighbor in current.Neighbors)
            {
                if (visited.ContainsKey(neighbor) == false)
                {
                    visited[neighbor] = current;
                    distances[neighbor] = distances[current] + 1;
                    queue.Enqueue(neighbor);

                    if (neighbor == end)
                    {
                        var path = ReconstructPath(end, visited);
                        return (path, path.Count);
                    }
                }
            }
        }
        // keinen Pfad gefunden
        return (new List<Node<T>>(0), double.PositiveInfinity);
    }

    static List<Node<T>> ReconstructPath(Node<T> end, Dictionary<Node<T>, Node<T>?> previous)
    {
        var path = new List<Node<T>>();
        var current = end;

        while (current != null)
        {
            path.Add(current);
            previous.TryGetValue(current, out current);
        }
        path.Reverse(); // Pfad umkehren (Start -> Ziel)

        return path;
    }
    public (List<Node<T>> path, double distance) Dijkstra(Node<T> start, Node<T> end)
    {
        var unvisited = new List<Node<T>>(Nodes);   // Nodes kopieren
        var distances = new Dictionary<Node<T>, double>();
        var previous = new Dictionary<Node<T>, Node<T>?>();

        Nodes.ForEach(node => distances.Add(node, double.PositiveInfinity));

        distances[start] = 0;

        while (unvisited.Count > 0)
        {
            var current = unvisited.OrderBy(node => distances[node]).First();

            unvisited.Remove(current);

            for (int i = 0; i < current.Neighbors.Count; i++)
            {
                var neighbor = current.Neighbors[i];
                if (unvisited.Contains(neighbor))
                {
                    double weight = current.Weights[i] ?? 0;
                    double newDistance = distances[current] + weight;
                    if (newDistance < distances[neighbor])
                    {
                        distances[neighbor] = newDistance;
                        previous[neighbor] = current;
                    }
                }
            }
        }

        // keinen Pfad gefunden
        if (distances[end] == double.PositiveInfinity)
            return (new List<Node<T>>(0), double.PositiveInfinity);

        var path = ReconstructPath(end, previous);
        return (path, distances[end]);
    }
    public (List<Node<T>> path, double distance) BellmanFord(Node<T> start, Node<T> end)
    {
        var distances = new Dictionary<Node<T>, double>();
        var previous = new Dictionary<Node<T>, Node<T>?>();

        Nodes.ForEach(node => distances.Add(node, double.PositiveInfinity));

        distances[start] = 0;

        for (int i = 0; i < Nodes.Count - 1; i++)
        {
            foreach (var current in Nodes)
            {
                if (distances[current] == double.PositiveInfinity)
                    continue;
                for (int j = 0; j < current.Neighbors.Count; j++)
                {
                    var neighbor = current.Neighbors[j];
                    var weight = current.Weights[j] ?? 0;
                    var newDistance = distances[current] + weight;

                    if (newDistance < distances[neighbor])
                    {
                        distances[neighbor] = newDistance;
                        previous[neighbor] = current;
                    }
                }
            }
        }

        foreach (var current in Nodes)
        {
            for (int j = 0; j < current.Neighbors.Count; j++)
            {
                var neighbor = current.Neighbors[j];
                var weight = current.Weights[j] ?? 0;
                var newDistance = distances[current] + weight;

                if (newDistance < distances[neighbor])
                    throw new InvalidOperationException("Negativer Zyklus gefunden");
            }
        }
        // Falls kein Pfad gefunden wurde, Rückgabe eines leeren Pfads mit Länge 0
        if (distances[end] == double.PositiveInfinity)
            return (new List<Node<T>>(0), 0);

        var path = ReconstructPath(end, previous);
        return (path, distances[end]);
    }

    public (List<Node<T>> path, double distance) AStar(Node<T> start, Node<T> end, Func<Node<T>, Node<T>, double> heuristic)
    {
        var gScore = new Dictionary<Node<T>, double>();
        var fScore = new Dictionary<Node<T>, double>();
        var openSet = new SortedSet<Node<T>>(Comparer<Node<T>>.Create((a, b) => fScore[a].CompareTo(fScore[b])));
        var cameFrom = new Dictionary<Node<T>, Node<T>?>();

        foreach (var node in Nodes)
        {
            gScore[node] = double.PositiveInfinity;
            fScore[node] = double.PositiveInfinity;
        }

        gScore[start] = 0;
        fScore[start] = heuristic(start, end);

        openSet.Add(start);

        while (openSet.Count > 0)
        {
            var current = openSet.Min;
            if (current != null && current.Equals(end))
            {
                var path = ReconstructPath(end, cameFrom);
                return (path, gScore[end]);
            }

            openSet.Remove(current!);

            for (int i = 0; i < current!.Neighbors.Count; i++)
            {
                var neighbor = current.Neighbors[i];
                double weight = current.Weights[i] ?? 0;
                double tentativeGScore = gScore[current] + weight;

                if (tentativeGScore < gScore[neighbor])
                {
                    cameFrom[neighbor] = current;
                    gScore[neighbor] = tentativeGScore;
                    fScore[neighbor] = gScore[neighbor] + heuristic(neighbor, end);

                    if (!openSet.Contains(neighbor))
                    {
                        openSet.Add(neighbor);
                    }
                }
            }
        }

        // Falls kein Pfad gefunden wurde, Rückgabe eines leeren Pfads mit Länge 0
        return (new List<Node<T>>(0), double.PositiveInfinity);
    }
    public (List<Node<T>> path, double distance) FloydWarshall(Node<T> start, Node<T> end)
    {
        int n = Nodes.Count;
        var distances = new double[n, n];
        var next = new Node<T>?[n, n];

        // Initialisierung der Distanzmatrix und der Next-Matrix
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (i == j)
                    distances[i, j] = 0;
                else
                    distances[i, j] = double.PositiveInfinity;
            }
        }

        // Füllen der Distanzmatrix mit den Gewichten der Kanten
        for (int i = 0; i < n; i++)
        {
            var node = Nodes[i];
            for (int j = 0; j < node.Neighbors.Count; j++)
            {
                var neighbor = node.Neighbors[j];
                double weight = node.Weights[j] ?? 0;
                int neighborIndex = Nodes.IndexOf(neighbor);
                distances[i, neighborIndex] = weight;
                next[i, neighborIndex] = neighbor;
            }
        }

        // Floyd-Warshall Algorithmus
        for (int k = 0; k < n; k++)
        {
            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < n; j++)
                {
                    if (distances[i, k] + distances[k, j] < distances[i, j])
                    {
                        distances[i, j] = distances[i, k] + distances[k, j];
                        next[i, j] = next[i, k];
                    }
                }
            }
        }

        // Falls kein Pfad gefunden wurde, Rückgabe eines leeren Pfads mit Länge 0
        if (distances[Nodes.IndexOf(start), Nodes.IndexOf(end)] == double.PositiveInfinity)
            return (new List<Node<T>>(0), double.PositiveInfinity);

        // Rekonstruktion des Pfads
        var path = new List<Node<T>>();
        var u = start;
        var uIndex = Nodes.IndexOf(u);
        var vIndex = Nodes.IndexOf(end);

        while (u != null && u != end)
        {
            path.Add(u);
            u = next[uIndex, vIndex];
            if (u == null) break;
            uIndex = Nodes.IndexOf(u);
        }

        if (u != null)
            path.Add(u);

        return (path, distances[Nodes.IndexOf(start), Nodes.IndexOf(end)]);
    }

}
