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

namespace RichCreator.Utility.PathFinding
{
    public class Dijkstra<T> where T : IEquatable<T>
    {
        private Dictionary<T, Dictionary<T, Int32>> edges = new Dictionary<T, Dictionary<T, Int32>>();

        /// <summary>
        /// 添加顶点
        /// </summary>
        /// <param name="vertice">顶点名称</param>
        /// <param name="targetVertice">顶点所有的边</param>
        public void AddEdge(T vertice, Dictionary<T, Int32> targetVertice)
        {
            foreach (var item in targetVertice)
            {
                AddEdge(vertice, item.Key, item.Value);
            }
        }

        /// <summary>
        /// 添加顶点
        /// </summary>
        /// <param name="vertice">顶点名称</param>
        /// <param name="targetVertice">可连接顶点</param>
        /// <param name="weight">权重</param>
        public void AddEdge(T vertice, T targetVertice, Int32 weight)
        {
            if (!this.edges.ContainsKey(vertice))
            {
                this.edges.Add(vertice, new Dictionary<T, Int32>());
            }

            if (!this.edges[vertice].ContainsKey(targetVertice))
            {
                this.edges[vertice].Add(targetVertice, weight);
            }


            if (!this.edges.ContainsKey(targetVertice))
            {
                this.edges.Add(targetVertice, new Dictionary<T, Int32>());
            }


            if (!this.edges[targetVertice].ContainsKey(vertice))
            {
                this.edges[targetVertice].Add(vertice, weight);
            }

        }

        /// <summary>
        /// 移除顶点
        /// </summary>
        /// <param name="name"></param>
        public void RemoveEdge(T name)
        {
            if (this.edges.ContainsKey(name))
            {
                return;
            }
            this.edges.Remove(name);
            foreach (var item in this.edges)
            {
                if (item.Value.ContainsKey(name))
                {
                    item.Value.Remove(name);
                }
            }
        }
        
        /// <summary>
        /// 查找最短路径
        /// </summary>
        /// <param name="start"></param>
        /// <param name="finish"></param>
        /// <returns></returns>

        public List<T> ShortestPath(T start, T finish)
        {
            var previous = new Dictionary<T, T>();
            var distances = new Dictionary<T, Int32>();
            var nodes = new List<T>();

            List<T> path = new List<T>();

            foreach (var vertex in edges)
            {
                if (vertex.Key.Equals(start))
                {
                    distances[vertex.Key] = 0;
                }
                else
                {
                    distances[vertex.Key] = Int32.MaxValue;
                }

                nodes.Add(vertex.Key);
            }

            while (nodes.Count != 0)
            {
                nodes.Sort((x, y) => distances[x] - distances[y]);

                var smallest = nodes[0];
                nodes.Remove(smallest);

                if (smallest.Equals(finish))
                {
                    while (previous.ContainsKey(smallest))
                    {
                        path.Add(smallest);
                        smallest = previous[smallest];
                    }

                    //倒译排列
                    path.Reverse();

                    break;
                }

                if (distances[smallest] == Int32.MaxValue)
                {
                    break;
                }

                foreach (var neighbor in edges[smallest])
                {
                    var alt = distances[smallest] + neighbor.Value;
                    if (alt < distances[neighbor.Key])
                    {
                        distances[neighbor.Key] = alt;
                        previous[neighbor.Key] = smallest;
                    }
                }
            }

            return path;
        }
    }
}