using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Threading;
using System.Drawing;
using System.Reflection.Emit;
using System.Reflection;

namespace test
{
    public class Dijkstra<T> where T:IEquatable<T>
    {
        private Dictionary<T, Dictionary<T, int>> vertices = new Dictionary<T, Dictionary<T, int>>();

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

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

            if (this.vertices[name].ContainsKey(target))
            {
                return;
            }

            this.vertices[name].Add(target, weight);
        }

        /// <summary>
        /// 移除顶点
        /// </summary>
        /// <param name="name"></param>
        public void RemoveVertex(T name)
        {
            if (this.vertices.ContainsKey(name))
            {
                return;
            }
            this.vertices.Remove(name);
            foreach (var item in this.vertices)
            {
                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, int>();
            var nodes = new List<T>();

            List<T> path = null;

            foreach (var vertex in vertices)
            {
                if (vertex.Key .Equals( start))
                {
                    distances[vertex.Key] = 0;
                }
                else
                {
                    distances[vertex.Key] = int.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))
                {
                    path = new List<T>();
                    while (previous.ContainsKey(smallest))
                    {
                        path.Add(smallest);
                        smallest = previous[smallest];
                    }

                    break;
                }

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

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

            return path;
        }
    }



    public struct person:IEquatable<person>
    {
        public person(Int32 age,string name)
        {
            this.Age = age;
            this.Name = name;
        }
        public int Age { get; set; }

        public string Name { get; set; }

        public bool Equals(person other)
        {
            if (this.Age == other.Age && Name.Equals(other.Name, StringComparison.Ordinal))
            {
                return true;
            }
            return false;
        }

        public override int GetHashCode()
        {
            Int32 hashcode = 17;
            hashcode = hashcode * 23 + this.Age.GetHashCode();
            hashcode = hashcode * 23 + this.Name.GetHashCode();
            return hashcode;
        }

        public override string ToString()
        {
            return this.Name + "," + this.Age.ToString();
        }



    }
    class Program
    {
       

        static void Main(string[] args)
        {
            person a = new person(235, "a0");
            person b = new person(12, "b1");
            person c = new person(34, "c2");
            person d = new person(45, "d3");
            person e = new person(56, "e4");
            Dijkstra<person> dij = new Dijkstra<person>();
            dij.AddVertex(a, new Dictionary<person, int>() { { b, 7 }, { d, 8 } });
            dij.AddVertex(b, new Dictionary<person, int>() { { a, 7 }, { c, 2 },{ d,2} ,{ e,3} });
            dij.AddVertex(c, new Dictionary<person, int>() { { b, 8 }, { e, 6 } });
            dij.AddVertex(d, new Dictionary<person, int>() { { a, 8 },{ b,2} });
            dij.AddVertex(e, new Dictionary<person, int>() { { b, 1 },{ c,2} });

            dij.ShortestPath(d, e).ForEach(x => Console.WriteLine(x));
            ZTImage.Diagnostics.CodeTimer.Timer("dij", 10000, () =>
            {
                //g.ShortestPath('A', 'H').ForEach(x => Console.WriteLine(x));
                dij.ShortestPath(a, b);

            });





            Console.ReadKey();
        }
        
    }
}