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

namespace ChaKi.Common
{
    public interface INestable
    {
        int Level { get; set; }
    }

    // TolopogicalSortの要因となる半順序 ( true if, x is parent of y )
    public delegate bool IsParent<T>(T x, T y);

    // DAGの要素
    class DAGItem<T> where T: class
    {
        public T Node;
        public List<DAGItem<T>> Parents;

        public DAGItem()
        {
            this.Node = null;
            this.Parents = new List<DAGItem<T>>();
        }
        public DAGItem(T t)
            : this()
        {
            this.Node = t;
        }
    }

    /// <summary>
    /// 親子の半順序がある要素リストをトポロジカルソートする.
    /// 結果は要素のLevel値に反映され、末端のLevelが0,
    /// 親は全ての子のLevelよりも大きな値を持つようにする.
    /// </summary>
    /// <typeparam name="T"></typeparam>
    public class TopologicalSort<T> where T : class, INestable
    {
        private List<T> m_Source;
        // 末端から逆に親方向へ辿るツリーの末端を束ねるルートノード
        private DAGItem<T> m_DAGRoot;

        public TopologicalSort(List<T> input, IsParent<T> comparer)
        {
            m_Source = input;
            m_DAGRoot = new DAGItem<T>();
            foreach (T t in input)
            {
                m_DAGRoot.Parents.Add(new DAGItem<T>(t));
            }
            foreach (DAGItem<T> n1 in m_DAGRoot.Parents)
            {
                foreach (DAGItem<T> n2 in m_DAGRoot.Parents)
                {
                    if (n1 == n2) continue;
                    if (comparer(n1.Node, n2.Node))
                    {
                        // n1 is parent of n2, so...
                        n2.Parents.Add(n1);
                    }
                }
            }
        }

        public void Sort()
        {
            VisitNode(m_DAGRoot, 0, new List<DAGItem<T>>());

        }

        private void VisitNode(DAGItem<T> node, int curDepth, List<DAGItem<T>> visited_list)
        {
            visited_list.Add(node);
            if (node.Node != null)
            {
                curDepth = node.Node.Level = Math.Max(node.Node.Level, curDepth);
            }

            if (node.Parents.Count > 0)
            {
                curDepth++;
                foreach (DAGItem<T> t in node.Parents)
                {
                    if (visited_list.Contains(t))
                    {
                        Console.WriteLine("Cyclic link found in TopologicalSort.VisitNode; ignored!");
                        continue;
                    }
                    VisitNode(t, curDepth, visited_list);
                }
            }
            visited_list.Remove(node);
        }
    }    
}
