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

namespace Application
{
    public static class TopologicalSorter
    {
        /// <summary>
        /// Returns a set of items sorted by topological order.
        /// </summary>
        /// <typeparam name="T">The element type of the sequence.</typeparam>
        /// <param name="source">The source.</param>
        /// <param name="dependencies">The dependencies.</param>
        /// <param name="throwOnCycle">If set to <c>true</c> cyclic dependency is not allowed.</param>
        /// <returns>The sorted sequence.</returns>
        public static IEnumerable<T> TplgSort<T>(this IEnumerable<T> source, Func<T, IEnumerable<T>> dependencies, bool throwOnCycle = false)
        {
            var sorted = new List<T>();
            var visited = new HashSet<T>();

            foreach (var item in source)
            {
                Visit(item, visited, sorted, dependencies, throwOnCycle);
            }

            return sorted;
        }

        private static void Visit<T>(T item, HashSet<T> visited, List<T> sorted, Func<T, IEnumerable<T>> dependencies, bool throwOnCycle)
        {
            if (visited.Contains(item) == false)
            {
                visited.Add(item);

                foreach (var dep in dependencies(item))
                {
                    Visit(dep, visited, sorted, dependencies, throwOnCycle);
                }

                sorted.Add(item);
            }
            else
            {
                if (throwOnCycle && sorted.Contains(item) == false)
                {
                    throw new Exception("Cyclic dependency found");
                }
            }
        }
    }
}