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 DijkstraPathFinder
    {
        // По аналогии с уроком
        class DijkstraData
        {
            public Point Previous { get; set; }
            public int Cost { get; set; }
        }
        public IEnumerable<PathWithCost> GetPathsByDijkstra(State state, Point start, IEnumerable<Point> targets)
        {
            var notVisited = MapProcessing(state).Where(a =>
            {
                return !state.IsWallAt(a);
            }).ToList();
            var previous = new Point(-1, -1);
            // Запоминаем путь, задаем начальное положение
            var track = new Dictionary<Point, DijkstraData>
            {
                [start] = new DijkstraData {Previous = previous, Cost = 0 }
            };
            // Количество сундуков
            var targetsCount = targets.Count();

            while (targetsCount > 0)
            {
                var Open = GetPoint(notVisited, track);
                if (Open.X == -1) yield break;

                if (targets.Contains(Open))
                {
                    yield return CreatePath(track, Open);
                }

                CheckPrice(Open, state, track);
                notVisited.Remove(Open);
                targetsCount--;
            }
        }
        private Point GetPoint(List<Point> notVisited, Dictionary<Point, DijkstraData> track)
        {
            var toOpen = new Point(-1, -1);
            var bestCost = double.PositiveInfinity;

            //П
            foreach (var e in notVisited)
            {
                if (track.ContainsKey(e) && track[e].Cost < bestCost)
                {
                    bestCost = track[e].Cost;
                    toOpen = e;
                }
            }
            return toOpen;
        }
        private PathWithCost CreatePath(Dictionary<Point, DijkstraData> track, Point target)
        {
            var path = new List<Point>();
            int cost = track[target].Cost;

            while (target.X != -1)
            {
                path.Add(target);
                target = track[target].Previous;
            }
            path.Reverse();

            var result = new PathWithCost(cost, path.ToArray());
            return result;
        }
        private void CheckPrice(Point p, State s, Dictionary<Point, DijkstraData> track)
        {
            foreach (var point in CheckNeighbours(p, s))
            {
                var costsNow = s.CellCost[point.X, point.Y] + track[p].Cost;
                if (track.ContainsKey(point) && track[point].Cost <= costsNow)
                {
                    continue;
                }
                track[point] = new DijkstraData { Previous = p, Cost = costsNow };
            }
        }
        private IEnumerable<Point> MapProcessing(State s)
        {
            var w = s.MapWidth;
            var h = s.MapHeight;

            for (var i = 0; i < w; i++)
            {
                for (var j = 0; j < h; j++)
                    yield return new Point(i, j);
            }
        }
        public IEnumerable<Point> CheckNeighbours(Point point1, State s)
        {
            int[] moves = { -1, 0, 1 };

            IEnumerable<Point> enumerable()
            {
                foreach (var x in moves)
                {
                    foreach (var y in moves)
                    {
                        if (Math.Abs(x) == Math.Abs(y))
                        {
                            continue;
                        }
                        yield return new Point(point1.X + x, point1.Y + y);
                    }
                }
            }
            return enumerable().Where(point =>
            {
                return !(!s.InsideMap(point) || s.IsWallAt(point));
            });
        }
    }
}