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

namespace Greedy
{
    public class NotGreedyPathFinder : IPathFinder
    {
        private Dictionary<Point, Dictionary<Point, PathWithCost>> paths =
            new Dictionary<Point, Dictionary<Point, PathWithCost>>();
        private State fieldState;
        private int maxTakenChests = 0;
        private List<Point> bestPointPath = new List<Point>();

        private void CalculatePathsCost()
        {
            var pathFinder = new DijkstraPathFinder();
            var points = new List<Point>(fieldState.Chests);
            points.Add(fieldState.Position);
            foreach (var point in points)
            {
                if (!paths.ContainsKey(point))
                    paths.Add(point, new Dictionary<Point, PathWithCost>());
                foreach (var path in pathFinder.GetPathsByDijkstra(fieldState, point, fieldState.Chests))
                {
                    if (path.End != path.Start)
                    {
                        paths[path.Start][path.End] = path;
                    }
                }
            }
        }

        private void FindPath(int energy, Point position, HashSet<Point> remainingChests,
            int takenChests, List<Point> pointPath)
        {
            var newRemainingChests = new HashSet<Point>(remainingChests);
            newRemainingChests.Remove(position);
            foreach (var chest in newRemainingChests)
                if (paths[position][chest].Cost <= energy)
                {
                    var newPath = new List<Point>(pointPath);
                    newPath.Add(chest);
                    FindPath(energy - paths[position][chest].Cost, chest, newRemainingChests,
                        takenChests + 1, newPath);
                }
            if (takenChests > maxTakenChests)
            {
                bestPointPath = pointPath;
                maxTakenChests = takenChests;
            }
        }

        public List<Point> FindPathToCompleteGoal(State state)
        {
            fieldState = state;
            CalculatePathsCost();
            var pathFinder = new DijkstraPathFinder();
            foreach (var path in paths[fieldState.Position])
            {
                var remainingChests = new HashSet<Point>();
                foreach (var chest in paths[path.Key])
                    remainingChests.Add(chest.Key);
                var pathPoints = new List<Point> { fieldState.Position, path.Key };
                FindPath(fieldState.Energy - path.Value.Cost, path.Key, remainingChests, 1, pathPoints);
            }
            var result = new List<Point>();
            for (int i = 0; i < bestPointPath.Count - 1; ++i)
                result = result.Concat(paths[bestPointPath[i]][bestPointPath[i + 1]].Path.Skip(1)).ToList();
            return result;
        }
    }
}