Hastlayer-SDK

using Hast.Common.Interfaces;
using Hast.Common.Models;
using System;
using System.Collections.Generic;
using System.Linq;

namespace Hast.Common.Extensions
{
    /// <summary>
    /// Extension for ordering <see cref="IRequirement{T}"/> collections.
    /// </summary>
    public static class RequirementExtensions
    {
        /// <summary>
        /// Returns a new collection where the items required by others are guaranteed to be prior to the ones requiring
        /// them. This way their load order will satisfy their requirements. Beside this, the order of items is an
        /// undefined implementation detail. If there are no requirements the <paramref name="source"/> order is kept.
        /// </summary>
        /// <param name="source">The original collection.</param>
        /// <typeparam name="TItem">The <see cref="IRequirement{T}"/> type of <paramref name="source"/>.</typeparam>
        /// <typeparam name="TKey">The <c>T</c> in <see cref="IRequirement{T}"/>.</typeparam>
        /// <returns></returns>
        public static List<TItem> OrderByRequirements<TItem, TKey>(this IEnumerable<TItem> source)
            where TItem : IRequirement<TKey>
            where TKey : IEquatable<TKey>
        {
            var items = source is IList<TItem> list ? list : source.ToList();
            var keys = items.Select(item => item.Name).ToList();
            CheckRequirements(items, keys);

            var descendantsByAncestor = items
                .SelectMany(item => item.Requirements.Select(requirement => new { item.Name, Ancestor = requirement }))
                .GroupBy(relationship => relationship.Ancestor)
                .ToDictionary(group => group.Key, group => group.Select(relationship => relationship.Name).ToList());
            var ancestors = descendantsByAncestor.SelectMany(pair => pair.Value).Distinct().ToHashSet();
            var roots = items
                .Where(item => !ancestors.Contains(item.Name))
                .Select(item => new RequirementTreeNode<TItem, TKey> { Data = item })
                .ToList();
            CreateForest(roots, descendantsByAncestor, items.ToDictionary(item => item.Name));
            PruneDuplicates(roots, new Dictionary<TKey, List<RequirementTreeNode<TItem, TKey>>>());

            var results = new List<TItem>();
            BuildResults(results, roots);
            return results;
        }

        private static void CheckRequirements<TItem, TKey>(IList<TItem> items, IList<TKey> keys)
            where TItem : IRequirement<TKey>
        {
            // Look for impossible requirements.
            foreach (var item in items)
            {
                foreach (var requirement in item.Requirements)
                {
                    if (!keys.Contains(requirement))
                    {
                        throw new KeyNotFoundException($"The required service \"{requirement}\" was not found!");
                    }
                }
            }
        }

        private static void CreateForest<TItem, TKey>(
            IReadOnlyCollection<RequirementTreeNode<TItem, TKey>> parents,
            IReadOnlyDictionary<TKey, List<TKey>> descendantsByAncestor,
            IReadOnlyDictionary<TKey, TItem> itemsDictionary)
            where TItem : IRequirement<TKey>
        {
            if (parents.Count == 0) return;

            foreach (var parent in parents)
            {
                if (descendantsByAncestor.TryGetValue(parent.Data.Name, out var descendants))
                {
                    var subCollection = descendants
                        .Select(key => new RequirementTreeNode<TItem, TKey> { Data = itemsDictionary[key] });
                    parent.Children.AddRange(subCollection);
                }

                CreateForest(parent.Children, descendantsByAncestor, itemsDictionary);
            }
        }

        private static void PruneDuplicates<TItem, TKey>(
            List<RequirementTreeNode<TItem, TKey>> parents,
            IDictionary<TKey, List<RequirementTreeNode<TItem, TKey>>> containersByName)
            where TItem : IRequirement<TKey>
            where TKey : IEquatable<TKey>
        {
            foreach (var parent in parents)
            {
                var key = parent.Data.Name;
                if (containersByName.TryGetValue(key, out var oldContainer))
                {
                    oldContainer.RemoveAll(item => item.Data.Name.Equals(key));
                }

                containersByName[key] = parents;

                PruneDuplicates(parent.Children, containersByName);
            }
        }

        private static void BuildResults<TItem, TKey>(
            List<TItem> results,
            List<RequirementTreeNode<TItem, TKey>> parents)
            where TItem : IRequirement<TKey>
        {
            foreach (var parent in parents)
            {
                results.Add(parent.Data);
                BuildResults(results, parent.Children);
            }
        }
    }
}