using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Drawing;

namespace DataStructures
{
    public class Graph<T>
    {
        public Graph()
        {
            Nodes = new List<Node<T>>();
            Connections = new List<Connection<T>>();
        }

        public List<Node<T>> Nodes { get; set; }
        public List<Connection<T>> Connections { get; set; }

        public void Add(params T[] newData)
        {
            for (int i = 0; i < newData.Length; i++)
                Add(newData[i], null);
        }

        public void Add(T newData, params Node<T>[] newConnections)
        {
            Node<T> newNode = new Node<T>(Nodes.Count, newData);
            Nodes.Add(newNode);

            if (newConnections != null)
                for (int i = 0; i < newConnections.Length; i++)
                    Connect(newNode, newConnections[i], 0);
        }

        public void Add(PointF newLocation, T newData)
        {
            Node<T> newNode = new Node<T>(Nodes.Count, newData, newLocation);
            Nodes.Add(newNode);
        }

        public void Add(params PointF[] newLocations)
        {
            for (int i = 0; i < newLocations.Length; i++)
                Add(newLocations[i], null);
        }

        public void Add(PointF newLocation, params Node<T>[] newConnections)
        {
            Node<T> newNode = new Node<T>(Nodes.Count, newLocation);
            Nodes.Add(newNode);

            if (newConnections != null)
                for (int i = 0; i < newConnections.Length; i++)
                    Connect(newNode, newConnections[i], 0);
        }

        public void Isolate(Node<T> rNode)
        {
            List<Connection<T>> removeConnections = new List<Connection<T>>();

            foreach (Connection<T> Connection in Connections)
                if (Connection.Start == rNode || Connection.End == rNode)
                    removeConnections.Add(Connection);

            foreach (Connection<T> Connection in removeConnections)
                Connections.Remove(Connection);
        }

        public void Isolate(int id)
        {
            Isolate(FindNodeFromID(id));
        }

        public void Remove(Node<T> rNode)
        {
            Nodes.Remove(rNode);
            Isolate(rNode);
        }

        public void Remove(int id)
        {
            Remove(FindNodeFromID(id));
        }

        public Node<T> FindNodeFromID(int id)
        {
            return Nodes.Find(delegate(Node<T> findNode) { return findNode.ID == id; });
        }

        public void Connect(Node<T> aNode, Node<T> bNode, float cost)
        {
            Connections.Add(new Connection<T>(aNode, bNode, cost));
        }

        public List<Node<T>> FindChildNodes(Node<T> findNode)
        {
            List<Node<T>> childNodes = new List<Node<T>>();

            foreach (Connection<T> Connection in Connections)
                if (Connection.Start == findNode)
                    childNodes.Add(Connection.End);

            return childNodes;
        }

        public float GetCost(Node<T> fromNode, Node<T> toNode)
        {
            foreach (Connection<T> Connection in Connections)
                if (Connection.Start == fromNode && Connection.End == toNode)
                    return Connection.Cost;

            return 0;
        }

        public List<Node<T>> Path(PathType type, Heuristics heuristic, Node<T> startNode, Node<T> targetNode)
        {
            return Path(type, heuristic, startNode, targetNode, true);
        }

        public List<Node<T>> Path(PathType type, Heuristics heuristic, Node<T> startNode, Node<T> targetNode, bool fixErrors)
        {
            List<Node<T>> openList = new List<Node<T>>();
            List<Node<T>> closedList = new List<Node<T>>();
            Node<T> activeNode;

            switch (type)
            {
                case PathType.DepthFirst:
                case PathType.BreadthFirst:

                    openList.Add(startNode);

                    do
                    {
                        activeNode = openList[0];
                        openList.Remove(activeNode);

                        if (closedList.Contains(activeNode))
                            continue;

                        if (activeNode == targetNode)
                        {
                            closedList.Add(activeNode);
                            break;
                        }

                        if (type == PathType.BreadthFirst)
                            openList.AddRange(FindChildNodes(activeNode));
                        else
                            openList.InsertRange(0, FindChildNodes(activeNode));

                        closedList.Add(activeNode);

                    } while (openList.Count > 0);

                    foreach (Node<T> Node in Nodes)
                        Node.Selected = false;

                    foreach (Node<T> Node in closedList)
                        Node.Selected = true;

                    return closedList;
                case PathType.AStar:

                    openList.Add(startNode);

                    do
                    {
                        activeNode = openList[0];
                        openList.Remove(activeNode);

                        if (activeNode == targetNode)
                            break;

                        if (closedList.Contains(activeNode))
                            continue;

                        openList.AddRange(FindChildNodes(activeNode));

                        openList.Sort(
                            delegate(Node<T> nA, Node<T> nB) 
                        {
                            float nACost = 0.0f;
                            float nBCost = 0.0f;

                            switch (heuristic)
                            {
                                case Heuristics.Manhattan:
                                    nACost = GetCost(nA, activeNode) + nA.DistanceTo(targetNode);
                                    nBCost = GetCost(nB, activeNode) + nB.DistanceTo(targetNode);
                                    break;

                                case Heuristics.DiagonalShortcut:
                                    float xDistance = Math.Abs(nA.Location.X - targetNode.Location.X);
                                    float yDistance = Math.Abs(nA.Location.Y - targetNode.Location.Y);

                                    if (xDistance > yDistance)
                                        nACost = Defaults.GraphDiagonalCost * yDistance + Defaults.GraphLinearCost * (xDistance - yDistance);
                                    else
                                        nACost = Defaults.GraphDiagonalCost * xDistance + Defaults.GraphLinearCost * (yDistance - xDistance);

                                    xDistance = Math.Abs(nB.Location.X - targetNode.Location.X);
                                    yDistance = Math.Abs(nB.Location.Y - targetNode.Location.Y);

                                    if (xDistance > yDistance)
                                        nBCost = Defaults.GraphDiagonalCost * yDistance + Defaults.GraphLinearCost * (xDistance - yDistance);
                                    else
                                        nBCost = Defaults.GraphDiagonalCost * xDistance + Defaults.GraphLinearCost * (yDistance - xDistance);
                                    break;

                                case Heuristics.Euclidean:
                                    nACost = nA.DistanceTo(targetNode);
                                    nBCost = nB.DistanceTo(targetNode);

                                    break;
                            }

                            return nACost.CompareTo(nBCost); 
                        }); 

                        closedList.Add(activeNode);

                    } while (openList.Count > 0);
                    break;
            }

            closedList.Add(targetNode);

            if (fixErrors)
            {
                List<Node<T>> nodeSplits = new List<Node<T>>();
                List<Node<T>> finalList = new List<Node<T>>();

                for (int i = 0; i < closedList.Count; i++)
                {
                    if (closedList[i] != targetNode)
                    {
                        if (!FindChildNodes(closedList[i]).Contains(closedList[i + 1]))
                        {
                            Console.WriteLine("Error: Node Split Between " + closedList[i].ID + " > " + closedList[i + 1].ID);
                            nodeSplits.Add(closedList[i + 1]);
                        }
                    }
                }

                if (nodeSplits.Count > 0)
                {
                    for (int i = nodeSplits.Count - 1; i >= 0; i--)
                    {
                        for (int j = 0; j < closedList.Count; j++)
                        {
                            if (!closedList.Contains(nodeSplits[i]))
                                break;

                            if (!FindChildNodes(closedList[j]).Contains(nodeSplits[i]))
                                continue;

                            int splitLocation = closedList.IndexOf(nodeSplits[i]);

                            closedList.RemoveRange(j, splitLocation - j);
                            break;
                        }
                    }
                }
            }

            foreach (Node<T> Node in Nodes)
                Node.Selected = false;

            foreach (Node<T> Node in closedList)
                Node.Selected = true;

            return closedList;
        }

        public override string ToString()
        {
            String outputStr = String.Empty;

            foreach (Node<T> Node in Nodes)
            {
                outputStr += "[" + Node.Data + "], ";
                outputStr += "\n";
            }

            return outputStr;
        }
    }

    public enum PathType
    {
        BreadthFirst,
        DepthFirst,
        AStar
    }
}
