using System.Diagnostics;
using System.Linq;
using System.Text.RegularExpressions;
using Graph;
using Graph.IO;

namespace TSP
{

    using Map = Graph<Vertex<Edge<double>, double>, Edge<double>, double>;

    public static class Solve
    {
        static Map Map { get; set; }
        static Tour BestTour = null;

        public static Tour BruteForce(string file, int init)
        {
            Map = GraphFile.Read(new FileReader(file));
            Tour intialTour = new Tour(Map.Vertices);
            GenerateTour(intialTour[init], new Tour(Map.Vertices), new Tour());

            return BestTour;
        }

        static void GenerateTour(City city, Tour tour, Tour visited)
        {
            // create local copy of Tour variables
            Tour currTour = new Tour(tour.Cities);
            Tour currVisited = new Tour(visited.Cities);
            City currCity = new City(city);

            // remove current City from tour
            currTour.Cities.RemoveAt(currTour.Cities.FindIndex(city => city.Id == currCity.Id));

            //? verify that city was removed
            Debug.Assert(currVisited.Cities.Find(city => city.Id == currCity.Id) == null,
                         $"Failed to remove a city from the tour. \nTour: {tour}\nCity: {currCity.Id}");

            // add current City to visited
            if (currVisited.Cities.Count > 0)
            {
                currCity.Parent = currVisited.Cities.Last().Id;
            }

            currVisited.Cities.Add(currCity);

            //? verify that city was added
            Debug.Assert(currVisited.Cities.Find(city => city.Id == currCity.Id) != null,
                         $"Failed to add a city to the tour. \nTour: {tour}\nCity: {currCity.Id}");

            // loop through each city. Each level of recursion has a one less city in currTour.Cities
            // leaving the base case
            foreach (City neighbor in currTour.Cities)
                GenerateTour(neighbor, currTour, currVisited);


            if (currTour.Cities.Count == 0)
            {
                currVisited.Cities.First().Parent = currVisited.Cities.Last().Id;

                if (BestTour == null || currVisited.Weight < BestTour.Weight)
                    BestTour = new Tour(currVisited.Cities);
                // Debug.Print($"{currTour}");
            }


            return;
        }
    }
}