using System;
using System.Collections.Generic;
using System.Drawing;
using System.Linq;
using Greedy.Architecture;
using Greedy.Architecture.Drawing;

namespace Greedy
{
    public class NotGreedyPathFinder : IPathFinder
    {
        public const int Limiter = 8;

        private static State _state;
        private static readonly Dictionary<Edge, double> Weights = new Dictionary<Edge, double>();
        public List<Point> FindPathToCompleteGoal(State state)
        {
            _state = state;
            var graph = new Graph(state.MapHeight * state.MapWidth);
            var chests = state.Chests.Take(Limiter);
            var bestPath = new List<Point>();
            var pathsBetweenChests = new Dictionary<Point, Dictionary<Point, List<Point>>>();

            InitializeGraphOnCells(graph);
            pathsBetweenChests[state.Position] = GetPathToChests(graph, state.Position);

            var points = chests as List<Point> ?? chests.ToList();
            points.ToList().ForEach(chest =>
            {
                pathsBetweenChests[chest] = GetPathToChests(graph, chest);
            });

            for (var i = 1; i <= Limiter; i++)
            {
                var reachableChestPermutations =
                    GetPermutations(points, i)
                        .Where(perm => PathsStaminaCost(perm, pathsBetweenChests) <= state.Energy);

                var chestPermutations = reachableChestPermutations.ToList();
                if (!chestPermutations.ToArray().Any()) break;
                bestPath = chestPermutations.ToArray()
                    .First()
                    .ToList();
            }

            return GetTotalPath(state, bestPath, pathsBetweenChests);
        }

        private static Dictionary<Point, List<Point>> GetPathToChests(Graph graph, Point start)
        {
            var result = new Dictionary<Point, List<Point>>();
            var chests = _state.Chests.Where(chest => chest != start);
            chests.ToList().ForEach(chest => { result[chest] = GetPathToChest(graph, start, chest); });
            return result;
        }

        private static List<Point> GetPathToChest(Graph graph,Point start, Point chest)
        {
            var initialPositionNumber = start.X + start.Y * _state.MapWidth;
            var chestPositionNumber = chest.X + chest.Y * _state.MapWidth;
            var path = Dijkstra(graph, graph[initialPositionNumber], graph[chestPositionNumber]);
            return path?.Select(n => new Point(n.Number % _state.MapWidth, n.Number / _state.MapWidth))
                       .Skip(1)
                       .ToList() ?? new List<Point>();
        }

        private static int PathsStaminaCost(IEnumerable<Point> chests,
            IReadOnlyDictionary<Point, Dictionary<Point, List<Point>>> pathsBetweenChests)
        {
            var current = _state.Position;
            var total = 0;

            chests.ToList().ForEach(chest =>
            {
                total += pathsBetweenChests[current][chest].Sum(point => _state.CellCost[point.X, point.Y]);
                current = chest;
            });

            return total;
        }

        private static List<Point> GetTotalPath(State state, IEnumerable<Point> pointsPermutation,
            IReadOnlyDictionary<Point, Dictionary<Point, List<Point>>> pathsBetweenChests)
        {
            var current = state.Position;
            var result = new List<Point>();

            pointsPermutation.ToList().ForEach(point =>
            {
                result.AddRange(pathsBetweenChests[current][point]);
                current = point;
            });
            return result;
        }

        private static IEnumerable<IEnumerable<T>> GetPermutations<T>(IEnumerable<T> list, int length)
        {
            if (length == 1) return list.Select(t => new[] {t});
            var enumerable = list.ToList();
            return GetPermutations(enumerable, length - 1)
                .SelectMany(t =>
                        enumerable.Where(o => !t.Contains(o)),
                    (t1, t2) => t1.Concat(new[] {t2}));
        }

        private static void InitializeGraphOnCells(Graph graph)
        {
            for (var y = 0; y < _state.MapHeight; y++)
            for (var x = 0; x < _state.MapWidth; x++)
            {
                var point = new Point(x, y);
                var pointsList = new List<Point>
                {
                    new Point(x, y - 1),
                    new Point(x, y + 1),
                    new Point(x + 1, y),
                    new Point(x - 1, y)
                };
                pointsList.ForEach(newPoint =>
                {
                    if (!_state.InsideMap(newPoint) || _state.IsWallAt(newPoint)) return;
                    var pointNumber = point.X + point.Y * _state.MapWidth;
                    var neighbourNumber = newPoint.X + newPoint.Y * _state.MapWidth;
                    Weights[graph.Connect(pointNumber, neighbourNumber)] = _state.CellCost[newPoint.X, newPoint.Y];
                });
            }
        }

        private static IEnumerable<Node> Dijkstra(Graph graph, Node start, Node end)
        {
            var notVisited = graph.Nodes.ToList();
            var track = new Dictionary<Node, DijkstraData>
            {
                [start] = new DijkstraData
                {
                    Price = 0,
                    Previous = null
                }
            };

            Node toOpen = null;

            while (toOpen != end)
            {
                var bestPrice = double.PositiveInfinity;
                toOpen = null;
                notVisited.ForEach(e =>
                {
                    if (!track.ContainsKey(e) || !(track[e].Price < bestPrice)) return;
                    bestPrice = track[e].Price;
                    toOpen = e;
                });
                if (toOpen == null) return null;
                toOpen.IncidentEdges
                    .Where(z => z.Output == toOpen)
                    .ToList()
                    .ForEach(e =>
                    {
                        var currentPrice = track[toOpen].Price + Weights[e];
                        var nextNode = e.OtherNode(toOpen);
                        if (!track.ContainsKey(nextNode)
                            || track[nextNode].Price > currentPrice)
                            track[nextNode] = new DijkstraData
                            {
                                Previous = toOpen,
                                Price = currentPrice
                            };
                    });
                notVisited.Remove(toOpen);
            }

            var result = new List<Node>();

            while (end != null)
            {
                result.Add(end);
                end = track[end].Previous;
            }

            result.Reverse();
            return result;
        }

        internal class DijkstraData
        {
            public Node Previous { get; set; }
            public double Price { get; set; }
        }

        internal class Edge
        {
            public readonly Node Output;
            public readonly Node Input;

            public Edge(Node output, Node input)
            {
                Output = output;
                Input = input;
            }

            public bool IsIncident(Node node)
            {
                return Output == node || Input == node;
            }

            public Node OtherNode(Node node)
            {
                if (!IsIncident(node)) throw new ArgumentException();
                return Output == node ? Input : Output;
            }
        }

        internal class Node
        {
            private readonly List<Edge> edges = new List<Edge>();
            public int Number;
            public IEnumerable<Edge> IncidentEdges => edges;

            public static Edge Connect(Node node1, Node node2, Graph graph)
            {
                if (!graph.Nodes.Contains(node1) || !graph.Nodes.Contains(node2)) throw new ArgumentException();
                var edge = new Edge(node1, node2);
                node1.edges.Add(edge);
                return edge;
            }
        }

        internal class Graph
        {
            private readonly Node[] nodes;
            public Node this[int index] => nodes[index];
            public IEnumerable<Node> Nodes => nodes;

            public Graph(int nodesCount)
            {
                nodes = Enumerable.Range(0, nodesCount)
                    .Select(z => new Node {Number = z})
                    .ToArray();
            }

            public Edge Connect(int index1, int index2)
            {
                return Node.Connect(nodes[index1], nodes[index2], this);
            }
        }
    }
}