using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AI_Lab1.lib
{
    public interface IPathFinder
    {
        Result FindPath(Field field, Coordinate start, Coordinate target, int depth = 4);
    }

    public class PathFinder : IPathFinder
    {
        public Result FindPath(Field field, Coordinate start, Coordinate target, int depth = 8)
        {
            var openNodesCount = 0;
            int maxDepth = depth;
            while(!ReachTarget(field, start, target, new LinkedList<Diff>(), maxDepth, ref openNodesCount, 0))
            {
                maxDepth++;
                Console.WriteLine(maxDepth);
            }
            return null;
        }

        private bool ReachTarget(Field field
            , Coordinate current
            , Coordinate target
            , LinkedList<Diff> path
            , int maxDepth
            , ref int openNodesCount
            , int depth = 0)
        {
            openNodesCount++;

            // Рассчитать возможные ходы и положить в массив
            List<Coordinate> potentialPositions = new List<Coordinate>
            {
                new Coordinate { X = current.X + 2, Y = current.Y + 1},
                new Coordinate { X = current.X + 1, Y = current.Y + 2},
                new Coordinate { X = current.X - 2, Y = current.Y + 1},
                new Coordinate { X = current.X - 1, Y = current.Y + 2},
                new Coordinate { X = current.X + 2, Y = current.Y - 1},
                new Coordinate { X = current.X + 1, Y = current.Y - 2},
                new Coordinate { X = current.X - 2, Y = current.Y - 1},
                new Coordinate { X = current.X - 1, Y = current.Y - 2},
            };

            var lastDiff = path.Last;
            if (lastDiff != null)
            {
                var prevCoord = lastDiff.Value.Act.PrevCoord;
                potentialPositions.RemoveAll(x => x.X == prevCoord.X && x.Y == prevCoord.Y); //.Remove(lastDiff.Value.Act.PrevCoord);
            }

            //var newState = field;
            // Пройтись циклом по массиву и посмотреть, что будет
            for (int i = 0; i < potentialPositions.Count && depth < maxDepth; i++)
            {
                if (field.CanMove(potentialPositions[i], target, PlaceStates.Horse))
                {
                    var newState = field.MoveFigure(current, potentialPositions[i], PlaceStates.Horse);
                    var diff = new Diff
                    {
                        Act = new Act { NewCoord = potentialPositions[i], PrevCoord = current },
                        Field = newState
                    };

                    //Console.WriteLine("--------------------");
                    //Console.WriteLine(newState.ToString());
                    //Console.WriteLine($"from ({diff.Act.PrevCoord.X};{diff.Act.PrevCoord.Y}) to ({diff.Act.NewCoord.X};{diff.Act.NewCoord.Y})");
                    //Console.WriteLine("--------------------");

                    // Добавить этап пройденного пути
                    path.AddLast(diff);

                    // Фигура на позиции, цель достигнута
                    if (newState.IsOnPosition(PlaceStates.Horse, target))
                    {
                        return true;
                    }

                    if (depth < maxDepth)
                    {
                        var targetReached = ReachTarget(newState
                            , potentialPositions[i]
                            , target
                            , path
                            , maxDepth
                            , ref openNodesCount
                            , depth + 1);

                        if (targetReached)
                        {
                            return true;
                        }
                    }
                }
            }
            if (path.Count > 0)
            {
                path.RemoveLast();
            }
            return false;

            throw new NotImplementedException();
        }
    }

    public class Result
    {
        public LinkedList<Diff> Path { get; set; }
        public int OpenNodes { get; set; }
    }
}