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

namespace AI_Coursework
{
    public class ListWithDuplicates : List<KeyValuePair<int, int>>
    {
        public void Add(int key, int value)
        {
            var element = new KeyValuePair<int, int>(key, value);
            this.Add(element);
        }
    }

    class Graph
    {
        private int vertices;
        private List<Int32>[] adjacent;
        private double weight;

        public Graph(int v)
        {
            // THE AMOUNT OF VERTICES IN THE GRAPH
            vertices = v;
            // Create a list of size v to store edges
            adjacent = new List<Int32>[v];
            for (int i = 0; i < v; i++)
            {
                adjacent[i] = new List<int>();
            }
        }
        public double FindWeight(int a, int b, int x, int y)
        {
            int wA = a - b;
            int wX = x - y;
            weight = Math.Sqrt(wA * wA + wX * wX);

            Console.WriteLine("The Weight from: " + a + ", " + b + " too " + x + ", " + y + " is: " + weight);
            return weight;
        }
        public void AddEdge(int c, int v)
        {
            adjacent[c].Add(v);
        }
        public void DFS(int v)
        {
            // Create an array of bools that is the size of the amount of vertices
            bool[] visited = new bool[vertices];
            // Create a stack
            Stack<Int32> stack = new Stack<int>();
            // Set the first visited vertice in visited list to true
            visited[v] = true;
            stack.Push(v);

            // while the stack is not empty
            while(stack.Count != 0)
            {
                // v is set to the first value out of the stack and is then removed
                v = stack.Pop();
                // Prints the stack
                Console.WriteLine("next->" + v);

                foreach(int i in adjacent[v])
                {
                    Console.WriteLine(i);
                    // If the value at visited[i] is false
                    if(!visited[i])
                    {
                        // Set it to true
                        visited[i] = true;
                        // Push the value in i onto the stack
                        stack.Push(i);
                    }
                }
            }
        }
    }


    public class Program
    {

        static void Main(string[] arg)
        {
            // VARIABLES
            char[] seperator = { ',' };
            string[] cavArray;
            int caveCounter = 1;
            // VALUES FOR CALCULATING WEIGHT OF EDGES
            int xFrom = 0, yFrom = 0, xToo = 0, yToo = 0;


            // CAVES IN FILE
            int size = 0;

            // READING CAV FILE INTO STRING
            string cav = System.IO.File.ReadAllText(@"C:\Caverns\input1.cav");
            if (cav != null)
            {
                Console.WriteLine("File Loaded.");
            }
            else
            {
                Console.WriteLine("File Failed to Load");
            }

            // SPLITTING CAV STRING INTO ARRAY
            cavArray = cav.Split(seperator, StringSplitOptions.RemoveEmptyEntries);
            // MOVING CAV ARRAY INTO A LIST
            List<int> cavList = new List<int>();
            for (int i = 0; i < cavArray.Length; i++)
            {
                cavList.Add(Convert.ToInt32(cavArray[i]));
            }
            // FINDING THE AMOUNT OF CAVES IN THE FILE THEN REMOVING FROM LIST
            size = Convert.ToInt32(cavList[0]);
            // INITIALISE GRAPH
            Graph graph = new Graph(size * 2);

            cavList.RemoveAt(0);

            // CREATING LINKED LIST FOR COORDINATES
            List<int> coordList = new List<int>();
            // ADDING ALL COORDINATES TO THE LIST
            for (int i = 0; i < size * 2; i++)
            {
                coordList.Add(cavList[0]);
                cavList.RemoveAt(0);
            }
            // CREATING LINKED LIST FOR CONNECTIONS
            List<int> connectionsList = new List<int>();
            // ADDING ALL CONNECTIONS TO THE LIST
            for (int i = 0; i < size * size; i++)
            {
                connectionsList.Add(cavList[0]);
                cavList.RemoveAt(0);
            }
            // REMOVING CAVLIST AS UNNECESSARY
            cavList.Clear();

            // SPLITTING THE LIST OF COORDINATES INTO A SEPERATE COORDINATE LIST
            var list = new ListWithDuplicates();
            for(int i = 0; i < size * 2; i++)
            {
                if(caveCounter % 2 == 0)
                {
                    // SETTING APPROPRIATE X Y COORDINATES
                    int x = coordList[0];
                    coordList.RemoveAt(0);
                    int y = coordList[0];
                    coordList.RemoveAt(0);
                    // ADDING THEM TO A LIST
                    list.Add(x, y);
                }
                caveCounter++;
            }
            // RESETTING CAVE COUNTER
            caveCounter = 1;
            var connectionCounter = 0;


            foreach (int n in connectionsList)
            {
                connectionCounter++;
                if (n == 1)
                {
                    // ADDING THE CONNECTIONS TO THE CURRENT CAVE
                    graph.AddEdge(caveCounter, connectionCounter);
                }
                if (connectionCounter % size == 0)
                {
                    connectionCounter = 0;
                    caveCounter++;
                }
            }
            graph.DFS(1);
        }
    }
}