TBL.CSharp/Base/Extension.Enumerable.cs

using System;
using System.Collections.Generic;
using System.Text;
using TBL.CSharp.Utilities.Random;

namespace TBL.CSharp.Base
{
    public static partial class Extension
    {
        /// <summary>
        /// 拓扑排序
        /// </summary>
        /// <param name="source">要排序的原始集合</param>
        /// <param name="getDependencies">每个项获得依赖项的方法</param>
        /// <param name="sortedElements">存储已排序元素的列表</param>
        /// <param name="visitedElements">存储已访问元素的映射表</param>
        /// <typeparam name="T">要排序的元素类型</typeparam>
        /// <returns>排序后的结果</returns>
        /// <exception cref="ArgumentException">无法完成拓扑排序</exception>
        public static IList<T> TopologicalSort<T>(
            this IEnumerable<T> source,
            Func<T, IEnumerable<T>> getDependencies,
            IList<T> sortedElements,
            IDictionary<T, bool> visitedElements
            )
        {
            void Visit(T item, Func<T, IEnumerable<T>> dependenciesProvider,
                ICollection<T> sorted, IDictionary<T, bool> visited)
            {
                if (item == null)
                    return;

                var alreadyVisited = visited.TryGetValue(item, out var inProcess);

                if (alreadyVisited)
                {
                    if (inProcess)
                    {
                        throw new ArgumentException("Cyclic dependency found.");
                    }
                }
                else
                {
                    visited[item] = true;

                    var dependencies = dependenciesProvider(item);
                    if (dependencies != null)
                    {
                        foreach (var dependency in dependencies)
                        {
                            Visit(dependency, dependenciesProvider, sorted, visited);
                        }
                    }

                    visited[item] = false;
                    sorted.Add(item);
                }
            }
            
            sortedElements.Clear();
            visitedElements.Clear();

            foreach (var item in source)
            {
                Visit(item, getDependencies, sortedElements, visitedElements);
            }

            return sortedElements;
        }

        /// <summary>
        /// 用默认临时对象进行拓扑排序
        /// </summary>
        /// <param name="source">要排序的原始集合</param>
        /// <param name="getDependencies">每个项获得依赖项的方法</param>
        /// <typeparam name="T">要排序的元素类型</typeparam>
        /// <returns>排序后的结果</returns>
        /// <exception cref="ArgumentException">无法完成拓扑排序</exception>
        public static IList<T> TopologicalSort<T>(
            this IEnumerable<T> source,
            Func<T, IEnumerable<T>> getDependencies
            ) => 
            TopologicalSort(source, getDependencies, new List<T>(), new Dictionary<T, bool>());

        /// <summary>
        /// 生成元素排列字符串
        /// </summary>
        public static string VisitElements<T>(
            this IEnumerable<T> source, 
            StringBuilder stringBuilder, 
            string separator = ", ",
            bool withInitialClear = true
            )
        {
            if (withInitialClear)
                stringBuilder.Clear();
            var i = 0;
            foreach (var element in source)
            {
                if (i != 0)
                    stringBuilder.Append(separator);
                stringBuilder.Append(element);
                i += 1;
            }
            return stringBuilder.ToString();
        }
        
        /// <summary>
        /// 生成元素排列字符串
        /// </summary>
        public static string VisitElements<T>(
            this IEnumerable<T> source, string separator = ", "
        )
        {
            var result = string.Empty;
            var i = 0;
            foreach (var element in source)
            {
                if (i != 0)
                    result += separator;
                result += element.ToString();
                i += 1;
            }
            return result;
        }
        
        /// <summary>
        /// 对传入列表进行洗牌操作
        /// <para>算法来源 <see href="https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle"/></para>
        /// </summary>
        public static void Shuffle<T>(IRandom random, IList<T> list)
        {
            for (var i = list.Count - 1; i > 0; --i)
            {
                var swapIndex = random.Next(i + 1);
                (list[swapIndex], list[i]) = (list[i], list[swapIndex]);
            }
        }

        /// <summary>
        /// 对传入非托管序列进行洗牌操作
        /// <para>算法来源 <see href="https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle"/></para>
        /// </summary>
        public static unsafe void Shuffle<T>(IRandom random, T* data, int count) where T : unmanaged
        {
            for (var i = count - 1; i > 0; --i)
            {
                var swapIndex = random.Next(i + 1);
                (data[swapIndex], data[i]) = (data[i], data[swapIndex]);
            }
        }

        /// <summary>
        /// 随机从列表中采取样本
        /// </summary>
        public static T Sample<T>(IRandom random, IList<T> list) => list[random.Next(list.Count)];

        /// <summary>
        /// 随机从非托管序列中采取样本
        /// </summary>
        public static unsafe T Sample<T>(IRandom random, T* data, int count) where T : unmanaged 
            => data[random.Next(count)];
    }
}