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


namespace Data_Structures_Project_1
{
    class Program
    {
        static void Main(string[] args)
        {
            //1.soru A şıkkı:


            Console.WriteLine("Rastgele 20 noktanın koordinatları:");
            RandomYaz(20);


            Console.ReadLine();


            Console.WriteLine("Rastgele 50 noktanın koordinatları:");
            RandomYaz(50);
           


            Console.WriteLine("Bir tuşa basınız...");
            Console.ReadKey();


            NearestNeighbor(20);


            Console.ReadKey();
        }
        
        //Noktaları en yakın komşu algoritmasına göre dolaşan kod. Yani C şıkkı.
        public static void NearestNeighbor(int noktasayisi2)
        {
            Random rand3 = new Random();
            
            //Kendi noktalarımız arasından rastgele bir nokta seçeceğimiz için önceki bir noktadan tekrar başlamamak gerekir. Bu yüzden her noktanın index değerini tutarız.
            List<int> noktalar = new List<int>();
            //Her uzaklığı tutmak için bir liste.
            List<double> uzaklikList = new List<double>();
            //RandomCoor metotu ile 20 noktalık bir dizi oluşturduk. RandomCoor metotu 2d diziye return olduğu için burada yeni bir 2d diziye eşitleyebiliyoruz.
            double[,] knn2 = RandomCoor(20);
            double minYol = 0;
            //Her seferinde yeni bir noktaya geçmek için temporary değer tanımladık.
            double[,] temp = new double[1, 2];
            //Bu sayı listesi gezilen noktaların index değerini tutar. Gezilen bir noktaya geri dönmemek için.
            List<int> sayiList = new List<int>();
            double toplamYol = 0;
            double[,] distmatrix2 = new double[noktasayisi2, noktasayisi2];






            //Oluşturduğumuz noktalar içerisinde 10 kez döneceğimiz için 10luk bir for loopa aldık.
            for (int chp = 0; chp < 10; chp++)
            {


                sayiList.Clear();
                //Soruda rastgele bir nokta seçin dediği için randomx oluşturuluyor.Bu randomx 0 ile nokta sayısı arasında bir değer alır.
                //Sütunlar zaten sadece 2 adet olduğu için satır değeri bize noktayı verir.
                int randomx = rand3.Next(0, noktasayisi2);


                if (noktalar.Contains(randomx))
                {
                    continue;
                }
                noktalar.Add(randomx);


                Console.WriteLine("Tur numarası {0}:",chp+1);


                while (true)
                {




                    for (int qwe = 0; qwe < noktasayisi2; qwe++)
                    {
                        //Eğer qwe değeri sayı listesinde varsa döngüdeki diğer elemana geç.
                        if (sayiList.Contains(qwe))
                        {
                            continue;
                        }


                        //Uzaklık fonksiyonu ile ilk rastgele noktamızın diğerlerine olan uzaklıklarını hesaplar. 0'a eşit olmadığı zamanları listeye atar çünkü 0'a eşit olduğunda kendisiyle olan
                        //uzaklığı ölçülmüştür.
                        if (Uzaklik(knn2[randomx, 0], knn2[randomx, 1], knn2[qwe, 0], knn2[qwe, 1]) != 0)
                        {
                            uzaklikList.Add(Uzaklik(knn2[randomx, 0], knn2[randomx, 1], knn2[qwe, 0], knn2[qwe, 1]));
                        }




                    }


                    //En kısa yol bulunur.
                    minYol = uzaklikList.DefaultIfEmpty().Min();
                    toplamYol += minYol;


                    for (int akp = 0; akp < noktasayisi2; akp++)
                    {
                        //Rastgele noktamızın bütün noktalara olan uzaklığı, en kısa yolla karşılaştırılır. Eğer eşleşirse akp değeri ile yeni noktanın indexi tutulur.
                        if (Uzaklik(knn2[randomx, 0], knn2[randomx, 1], knn2[akp, 0], knn2[akp, 1]) == minYol)
                        {
                            //Yeni noktamızı temporary değerimize eşitleriz.
                            temp[0, 0] = knn2[akp, 0];
                            temp[0, 1] = knn2[akp, 1];
                            sayiList.Add(akp);
                        }
                    }


                    //ve randomx değerimizi de geçici değerimize eşitleriz. Böylece döngü en başa döndüğünde randomx değeri yeni nokta değeri olur ve hiçbir nokta yeniden gezilmemiş olur.
                    knn2[randomx, 0] = temp[0, 0];
                    knn2[randomx, 1] = temp[0, 1];




                    Console.WriteLine(knn2[randomx, 0] + " " + knn2[randomx, 1]);






                    //Her seferinde noktalar arası uzaklığın tutulduğu liste temizlenmelidir.Yoksa yeni noktaya geçip yeni uzaklıkları hesapladığımızda önceki değer yenilerinden küçükse
                    //minYol değeri hep aynı kalacaktır ve bu yüzden yeni geçeceğimiz noktanın indexini bulamayacağız.
                    uzaklikList.Clear();






                    //sayı listesinin elemanlarının sayısı nokta sayısına ulaştığında döngü biter.
                    if (sayiList.Count() == noktasayisi2 - 1)
                    {
                        break;
                    }
                }
            }


            Console.WriteLine("Sırasıyla gidilen yol(index):");
            sayiList.ForEach(Console.Write);


            for (int k = 0; k < noktasayisi2; k++)
            {
                for (int kx = 0; kx < noktasayisi2; kx++)
                {
                    distmatrix2[k, kx] = Uzaklik(knn2[k, 0], knn2[k, 1], knn2[kx, 0], knn2[kx, 1]);
                }
            }


            Console.WriteLine("Gidilen toplam yol " + toplamYol);


            Console.WriteLine("Noktaların arasındaki uzaklıklar(Uzaklık Matrisi):");


            for (int q = 0; q < noktasayisi2; q++)
            {
                for (int qx = 0; qx < noktasayisi2; qx++)
                {
                    Console.WriteLine(q + " ile " + qx + " arasındaki uzaklık:" + distmatrix2[q, qx]);
                }
            }
        }


        //Öklid uzaklığını hesaplayan fonksiyon.
        public static double Uzaklik(double x1, double y1, double x2, double y2)
        {
            return Math.Sqrt(((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)));
        }




        // Random noktaları yazdıran fonksiyon.
        public static void RandomYaz(int noktasayisi)
        {
            for (int j = 0; j < noktasayisi; j++)
            {
                Console.WriteLine("Nokta " + (j + 1).ToString() + "in x koordinatı:" + RandomCoor(noktasayisi)[j, 0] + " " + "y koordinatı:" + RandomCoor(noktasayisi)[j, 1]);
            }


        }


        //Random X ve Y koordinatları oluşturan metot.
        public static double[,] RandomCoor(int noktasayisi2)
        {
            
            var rand2 = new Random();
            double[,] knn = new double[noktasayisi2, 2];


            for (int ax = 0; ax<noktasayisi2; ax++)
            {
                knn[ax, 0] = rand2.NextDouble() * 19 + 1;
                knn[ax,1] = rand2.NextDouble() * 19 + 1;
            }


            


            return knn;
           
        }


        public static void DistMatrix(int noktasayisi)
        {
            RandomCoor(noktasayisi);
            double[,] dstmatrix = new double[noktasayisi, noktasayisi];
            
            for (int k = 0; k < noktasayisi; k++)
            {
                for (int kx = 0; kx < noktasayisi; kx++)
                {
                    dstmatrix[k, kx] = Uzaklik(RandomCoor(noktasayisi)[k, 0], RandomCoor(noktasayisi)[k, 1], RandomCoor(noktasayisi)[kx, 0], RandomCoor(noktasayisi)[kx, 1]);
                }
            }
            Console.WriteLine("Noktaların arasındaki uzaklıklar:");


            for (int q = 0; q < noktasayisi; q++)
            {
                for (int qx = 0; qx < noktasayisi; qx++)
                {
                    Console.WriteLine(q + " ile " + qx + " arasındaki uzaklık:" + dstmatrix[q, qx]);
                }
            }
        }
        


    }
}