using RichCreator.Utility.Structs;
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace RichCreator.Utility.PathFinding
{
    public class Dijkstra
    {
        private List<Node> nodes;
        private List<Edge> edges;

        public Dijkstra()
        {
            nodes = new List<Node>();
            edges = new List<Edge>();
        }

        public Dijkstra(List<Tuple<ZTPoint, ZTPoint, double>> edges)
        {
            nodes = new List<Node>();
            this.edges = new List<Edge>();
            InitEdge(edges);
        }

        public void InitEdge(List<Tuple<ZTPoint, ZTPoint, double>> edges)
        {
            this.edges = ConvertToEdge(edges);
            InitNodes();
        }

        public List<ZTPoint> Find(ZTPoint start, ZTPoint end)
        {
            var startNode = GetNodeByName(start);
            var endNode = GetNodeByName(end);

            if (startNode == null || endNode == null)
            {
                return new List<ZTPoint>();
            }

            var s = nodes.Where(x => x.Name == start).ToList();
            var u = nodes.Where(x => x.Name != start).ToList();

            s.ForEach(x =>
            {
                x.Weight = 0;
            });

            u.ForEach(x =>
            {
                x.Weight = double.PositiveInfinity;
            });

            while (u.Any())
            {
                var node = s.Last();

                //更新node到x的距离
                u.ForEach(x =>
                {
                    var edge = GetEdgeByTwoNode(node, x);

                    if (edge != null)
                    {
                        var weights = node.GetAllWeight() + edge.Weight;

                        if (weights < x.Weight)
                        {
                            x.Weight = weights;
                            x.Parent = node;
                        }
                    }
                });

                //找出距离最小的
                var minNode = u.OrderBy(x => x.Weight).FirstOrDefault();

                s.Add(minNode);
                u.Remove(minNode);
            }

            var paths = new Stack<ZTPoint>();

            while (endNode != null)
            {
                paths.Push(endNode.Name);
                endNode = endNode.Parent;
            }

            //如果路劲中包含起点
            if (paths.ToList().Contains(start))
            {
                return paths.ToList();
            }
            else
            {
                return new List<ZTPoint>();
            }
        }

        private Edge GetEdgeByTwoNode(Node start, Node end)
        {
            var edge = edges.FirstOrDefault(x => x.Start == start.Name && x.End == end.Name);

            if (edge == null)
            {
                edge = edges.FirstOrDefault(x => x.Start == end.Name && x.End == start.Name);
            }

            return edge;
        }

        /// <summary>
        /// 将权值转换成边
        /// </summary>
        /// <returns></returns>
        private List<Edge> ConvertToEdge(List<Tuple<ZTPoint, ZTPoint, double>> weights)
        {
            var edges = new List<Edge>();

            weights.ForEach(weight =>
            {
                edges.Add(new Edge()
                {
                    Start = weight.Item1,
                    End = weight.Item2,
                    Weight = weight.Item3
                });
            });

            return edges;
        }


        /// <summary>
        /// 根据名字获取节点
        /// </summary>
        /// <param name="nodeName"></param>
        /// <returns></returns>
        private Node GetNodeByName(ZTPoint nodeName)
        {
            return nodes.FirstOrDefault(x => x.Name == nodeName);
        }

        /// <summary>
        /// 初始化点
        /// </summary>
        private void InitNodes()
        {
            edges.ForEach(edge =>
            {
                if (nodes.All(x => x.Name != edge.Start))
                {
                    nodes.Add(new Node()
                    {
                        Name = edge.Start
                    });
                }

                if (nodes.All(x => x.Name != edge.End))
                {
                    nodes.Add(new Node()
                    {
                        Name = edge.End
                    });
                }
            });
        }
    }
}