using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace DO_Lab6
{
    internal class DijkstraMethod
    {
        int[,] weigthMatrix;
        int[,] currentTable;
        List<int> revisedVerticies;
        int initialVertex;
        public DijkstraMethod(string path, int initialVertex = 1)
        {
            string[] data = File.ReadAllLines(path);
            weigthMatrix = new int[data.Length, data[0].Split(' ').Count()];
            currentTable = new int[2, weigthMatrix.GetLength(1)];
            revisedVerticies = new List<int>();

            for (int i = 0; i < weigthMatrix.GetLength(0); i++)
            {
                string[] current = data[i].Split(" ");
                for (int j = 0; j < weigthMatrix.GetLength(1); j++)
                {
                    if (current[j] == "-")
                    {
                        weigthMatrix[i, j] = -1;
                    }
                    else
                    {
                        weigthMatrix[i, j] = int.Parse(current[j]);
                    }
                }
            }

            for (int i = 0; i < currentTable.GetLength(0); i++)
            {
                for (int j = 0; j < currentTable.GetLength(1); j++)
                {
                    currentTable[i, j] = int.MaxValue;
                }
            }
            this.initialVertex = initialVertex - 1;
            currentTable[0, this.initialVertex] = 0;
        }
        private void printArr()
        {
            Console.Write("".PadRight(4));
            for (int i = 0; i < weigthMatrix.GetLength(0); i++)
            {
                Console.Write($"{i + 1}".PadRight(4));
            }
            Console.WriteLine();

            for (int i = 0; i < weigthMatrix.GetLength(0); i++)
            {
                Console.Write($"{i + 1}".PadRight(4));

                for (int j = 0; j < weigthMatrix.GetLength(1); j++)
                {
                    if (weigthMatrix[i, j] == -1)
                    {
                        Console.Write($"-".PadRight(4));
                    }
                    else
                    {
                        Console.Write($"{weigthMatrix[i, j]}".PadRight(4));
                    }
                }
                Console.WriteLine();
            }
        }
        private void printTable()
        {
            for (int i = 0; i < weigthMatrix.GetLength(0); i++)
            {
                Console.Write($"{i + 1}".PadRight(4));
            }
            Console.WriteLine();

            for (int i = 0; i < currentTable.GetLength(0); i++)
            {
                for (int j = 0; j < currentTable.GetLength(1); j++)
                {
                    if (currentTable[i, j] == int.MaxValue)
                    {
                        Console.Write($"-".PadRight(4));
                    }
                    else
                    {
                        if (i == 0)
                        {
                            Console.Write($"{currentTable[i, j]}".PadRight(4));
                        }
                        else
                        {
                            Console.Write($"{currentTable[i, j] + 1}".PadRight(4));
                        }
                    }
                }
                Console.WriteLine();
            }
        }
        private List<int> getAdjacentVertices(int vertexIndex)
        {
            List<int> adjacentVertices = new List<int>();

            for (int j = 0; j < weigthMatrix.GetLength(1); j++)
            {
                if (weigthMatrix[vertexIndex, j] > 0)
                {
                    adjacentVertices.Add(j);
                }
            }
            return adjacentVertices;
        }
        private int selectCheapestVertex()
        {
            int cheapest = int.MaxValue;
            int selected = -1;
            for (int j = 0; j < currentTable.GetLength(1); j++)
            {
                if (currentTable[0, j] < cheapest && !revisedVerticies.Contains(j))
                {
                    cheapest = currentTable[0, j];
                    selected = j;
                }
            }
            if (selected != -1)
            {
                revisedVerticies.Add(selected);
            }

            return selected;
        }
        private void printAdjacentVertices(List<int> adjacentVertices)
        {
            Console.Write("Adjacent Vertices: ");
            for (int i = 0; i < adjacentVertices.Count; i++)
            {
                Console.Write($"{adjacentVertices[i] + 1}".PadRight(4));
            }
            Console.WriteLine();
        }
        private void printRoutes()
        {
            Console.WriteLine("Маршрут".PadRight(9) + "Шлях".PadRight(15) + "Довжина");

            for (int i = 0; i < currentTable.GetLength(1); i++)
            {
                if (currentTable[1, i] == int.MaxValue)
                {
                    if (i == 0)
                    {
                        Console.WriteLine($"{initialVertex + 1}-{initialVertex + 1}".PadRight(9) + "-".PadRight(15) + $"{currentTable[0, i]}");
                    }
                    continue;
                }

                List<int> currentRoute = new List<int>();
                currentRoute.Add(i + 1);
                int intermediateVertex = i;
                while (intermediateVertex != initialVertex)
                {
                    intermediateVertex = currentTable[1, intermediateVertex];
                    currentRoute.Add(intermediateVertex + 1);
                }
                currentRoute.Reverse();
                string route = "";
                for (int j = 0; j < currentRoute.Count; j++)
                {
                    route += currentRoute[j].ToString();
                    if (j != currentRoute.Count - 1)
                    {
                        route += "->";
                    }
                }
                Console.WriteLine($"{initialVertex + 1}-{i + 1}".PadRight(9) + route.PadRight(15) + $"{currentTable[0, i]}");
            }
        }
        public void Solve()
        {
            printArr();
            Console.WriteLine();
            Console.WriteLine();
            int i = 0;
            bool isSolved = false;
            int iter = 2;
            while (!isSolved)
            {
                i = selectCheapestVertex();
                if (i == -1)
                {
                    break;
                }
                Console.WriteLine($"Iter {iter} selected {i + 1}");
                List<int> adjacentVertices = getAdjacentVertices(i);
                printAdjacentVertices(adjacentVertices);

                for (int j = 0; j < adjacentVertices.Count; j++)
                {
                    int currentVertex = adjacentVertices[j];
                    if (currentTable[0, currentVertex] > currentTable[0, i] + weigthMatrix[i, currentVertex])
                    {
                        currentTable[0, currentVertex] = currentTable[0, i] + weigthMatrix[i, currentVertex];
                        currentTable[1, currentVertex] = i;
                    }
                }

                printTable();
                Console.WriteLine();
                iter++;

                isSolved = (revisedVerticies.Count == weigthMatrix.GetLength(1));
            }
            printRoutes();
        }
    }
}