using System;
using System.Collections.Generic;
using System.Text;
using System.ComponentModel;

namespace VisualPathFinder
{
    class PathFind : INotifyPropertyChanged
    {
        List<Point> Current;
        bool pathHighlight = true;
        int endX;
        int endY;
        bool optimal;
        bool diagonals;
        bool randomMoves;
        bool isHighlighted = false;
        Point oldTrace;
        int []xMoves;
        int []yMoves;
        int moves;
        int pathLength;
        bool breadthFirst;
        Random randGenerator = new Random();

        public PathFind()
        {
            AllowDiagonals = false;
            moves = 0;
            pathLength = 0;
            breadthFirst = false;
        }

        public bool BreadthFirst
        {
            get
            {
                return breadthFirst;
            }
            set
            {
                breadthFirst = value;
                OnPropertyChanged("BreadthFirst");
                OnPropertyChanged("BestFirst");
            }
        }

        public bool BestFirst
        {
            get
            {
                return !BreadthFirst;
            }
            set
            {
                BreadthFirst = !value;
            }
        }

        public bool RandomMoves
        {
            get
            {
                return randomMoves;
            }
            set
            {
                randomMoves = value;
            }
        }

        public bool Optimal
        {
            get
            {
                return optimal;
            }
            set
            {
                optimal = value;
            }
        }

        public int PathLength
        {
            get
            {
                return pathLength;
            }
            set
            {
                pathLength = value;
                OnPropertyChanged("PathLength");
            }
        }

        public int Moves
        {
            get
            {
                return moves;
            }
            set
            {
                moves = value;
                OnPropertyChanged("Moves");
            }
        }

        public int EndX
        {
            get
            {
                return endX;
            }
        }

        public int EndY
        {
            get
            {
                return endY;
            }
        }

        public bool PathHighlight
        {
            get
            {
                return pathHighlight;
            }
            set
            {
                pathHighlight = value;
            }
        }

        public void removePathHighlight(Point start, Map map)
        {
            if (isHighlighted && start != null)
            {
                Point temp = start;
                while (temp.Parent != null)
                {
                    map.Set(temp.X, temp.Y, Tile.CellType.NON_ENDPOINT);
                    temp = temp.Parent;
                }
                isHighlighted = false;
            }
        }

        public void addPathHighlight(Point start, Map map)
        {
            if (pathHighlight && start != null)
            {
                isHighlighted = true;
                Point temp = start;
                while (temp.Parent != null)
                {
                    map.Set(temp.X, temp.Y, Tile.CellType.HIGHLIGHT);
                    temp = temp.Parent;
                }
            }
        }

        public bool run(Map map)
        {
            if (RandomMoves)
            {
                scrambleMoveLocations();
            }

            Moves++;
            removePathHighlight(oldTrace, map);
            if (Current.Count > 0)
            {
                Point temp = Current[0];
                Current.RemoveAt(0);
                addPathHighlight(temp, map);
                oldTrace = temp;

                if (map.At(temp.X, temp.Y) != Tile.CellType.START)
                {
                    map.Set(temp.X, temp.Y, Tile.CellType.NON_ENDPOINT);
                }

                if (temp.X == endX && temp.Y == endY)
                {
                    foreach (Point ends in Current)
                    {
                        map.Set(ends.X, ends.Y, Tile.CellType.NON_ENDPOINT);
                    }
                    map.Set(temp.X, temp.Y, Tile.CellType.FINISH);
                    temp = temp.Parent;
                    PathLength = 1;

                    while (temp.Parent != null)
                    {
                        map.Set(temp.X, temp.Y, Tile.CellType.ENDPOINT);
                        temp = temp.Parent;
                        PathLength++;
                    }
                    return true;
                }

                for (int i = xMoves.Length - 1; i >= 0; i--)
                {
                    if (map.At(temp.X + xMoves[i], temp.Y + yMoves[i]) == Tile.CellType.EMPTY
                        || map.At(temp.X + xMoves[i], temp.Y + yMoves[i]) == Tile.CellType.FINISH)
                    {
                        map.Set(temp.X + xMoves[i], temp.Y + yMoves[i], Tile.CellType.ENDPOINT);
                        insertSorted(Current, buildPoint(temp, xMoves[i], yMoves[i]));
                    }

                    if (map.At(temp.X + xMoves[i], temp.Y + yMoves[i]) == Tile.CellType.ENDPOINT ||
                        map.At(temp.X + xMoves[i], temp.Y + yMoves[i]) == Tile.CellType.NON_ENDPOINT)
                    {
                        foreach (Point markedPoint in Current)
                        {
                            if (markedPoint.X == temp.X + xMoves[i] && markedPoint.Y == temp.Y + yMoves[i])
                            {
                                Point newPoint = buildPoint(temp, xMoves[i], yMoves[i]);
                                if (markedPoint.Rating > newPoint.Rating)
                                {
                                    markedPoint.Parent = newPoint.Parent;
                                    markedPoint.Moves = newPoint.Moves;
                                    markedPoint.MovesLeft = newPoint.MovesLeft;
                                }
                                break;
                            }
                        }
                    }

                }
            }
            else
            {
                return true;
            }
            return false;
        }

        private Point buildPoint(Point point, int dx, int dy)
        {
            int x = point.X + dx;
            int y = point.Y + dy;
            int remaining;
            if (diagonals)
            {
                remaining = Math.Max(Math.Abs(x - endX), Math.Abs(y - endY));
            }
            else
            {
                remaining = Math.Abs(x - endX) + Math.Abs(y - endY);
            }
            return new Point(x, y, point, remaining);
        }

        public void setup(Map map)
        {
            Current = new List<Point>();
            oldTrace = null;

            int width = map.Grid.Count;
            int height;
            if (width > 0)
            {
                height = map.Grid[0].Count;
            }
            else
            {
                return;
            }

            Moves = 0;
            PathLength = 0;

            int yStart = -1;
            int xStart = -1;
            endX = -1;
            endY = -1;
            for (int i = 0; i < width; i++)
            {
                for (int j = 0; j < height; j++)
                {
                    if (map.At(i, j) == Tile.CellType.START)
                    {
                        xStart = i;
                        yStart = j;
                    }
                    if (map.At(i, j) == Tile.CellType.FINISH)
                    {
                        endX = i;
                        endY = j;
                    }
                }
            }
            if (yStart < 0 || xStart < 0 || endX < 0 || endY < 0)
            {
                return;
            }

            Current.Add(new Point(xStart, yStart));
        }

        private void insertSorted(List<Point> list, Point item)
        {
            int end = list.Count;
            int start = 0;
            int mid = 0;

            if (breadthFirst)
            {
                list.Add(item);
                return;
            }

            while (start < end)
            {
                mid = (start + end) >> 1;
                bool comp = optimal ? list[mid].Moves > item.Moves : list[mid].Moves < item.Moves;
                if (list[mid].Rating > item.Rating
                    || ( list[mid].Rating == item.Rating && comp))
                {
                    end = mid;
                    if (end < start)
                        end = start;
                }
                else
                {
                    start = mid + 1;
                    if (end < start)
                        start = end;
                }
            }

            list.Insert(end, item);
        }

        public bool AllowDiagonals
        {
            set
            {
                diagonals = value;
                if (value)
                {
                    xMoves = new int[] { 1, -1, 1, -1, 1, -1, 0, 0 };
                    yMoves = new int[] { -1, -1, 1, 1, 0, 0, 1, -1 };
                }
                else
                {
                    xMoves = new int[] { 1, -1, 0, 0 };
                    yMoves = new int[] { 0, 0, 1, -1 };
                }
            }
        }

        private void scrambleMoveLocations()
        {
            for (int i = xMoves.Length - 1; i >= 0; i--)
            {
                int index = randGenerator.Next(0, xMoves.Length);
                int yTemp = yMoves[index];
                int xTemp = xMoves[index];
                yMoves[index] = yMoves[i];
                xMoves[index] = xMoves[i];
                yMoves[i] = yTemp;
                xMoves[i] = xTemp;
            }
        }

        #region INotifyPropertyChanged Implementation

        public event PropertyChangedEventHandler PropertyChanged;
        protected void OnPropertyChanged(string propName)
        {
            if (this.PropertyChanged != null)
            {
                PropertyChanged(this, new PropertyChangedEventArgs(propName));
            }
        }

        #endregion
    }
}
