using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using Greedy.Architecture;
using System.Drawing;

namespace Greedy
{
    public class DijkstraData
    {
        public Point Previous { get; set; }
        public int Price { get; set; }
    }
    public class DijkstraPathFinder
    {
        public IEnumerable<PathWithCost> GetPathsByDijkstra(State state, Point start,
            IEnumerable<Point> targets)
        {
            var notVisited = new List<Point>();
            for (int i = 0; i < state.MapWidth; i++)
                for (int j = 0; j < state.MapHeight; j++)
                {
                    notVisited.Add(new Point(i, j));
                }
            var track = new Dictionary<Point, DijkstraData>();
            track[start] = new DijkstraData { Previous = new Point(-100,-100), Price = 0 };
            while (true)
            {
                Point toOpen = new Point(-100, -100);
                var bestPrice = int.MaxValue;
                foreach (var e in notVisited)
                {
                    if (track.ContainsKey(e) && track[e].Price < bestPrice)
                    {
                        bestPrice = track[e].Price;
                        toOpen = e;
                    }
                }
                if (toOpen == new Point(-100, -100)) yield break;
                if (targets.Count() == 0) yield break;
                for (var dy = -1; dy <= 1; dy++)
                    for (var dx = -1; dx <= 1; dx++)
                    {
                        if ((dx != 0 && dy != 0) && (dx == 0 && dy == 0)) continue; //1
                        var nextPoint = new Point(toOpen.X + dx, toOpen.Y + dy);
                        if (!state.InsideMap(nextPoint) && state.IsWallAt(nextPoint)) continue;//2
                        track.Add(nextPoint, new DijkstraData { Previous = toOpen, Price = state.CellCost[nextPoint.X, nextPoint.Y] + track[toOpen].Price });
                    }
                notVisited.Remove(toOpen);
            }
            foreach(var target in targets)
            {
                if(track.ContainsKey(target))
                    var result = new List<Point>();
                    while (toOpen != null)
                    {
                        result.Add(toOpen);
                        toOpen = track[toOpen].Previous;
                        yield return new PathWithCost(bestPrice, result.Reverse());
                    }
            }

        }
    }
}