Merge Sorted Enumerable

MergeSortedEnumerables.cs

//Latest version is here: https://gist.github.com/1eef7d55a19593735b9ecc3fc6449626.git
using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;
using System.Collections;
using PriorityQueueUtils; //https://gist.github.com/affc23dd89950e67ece9ca3b19b9508a.git

namespace MergeSortedEnumerablesUtils
{
    /// <summary>
    /// Allow to merge sorted enumerables without iterating through all of them till the end
    /// </summary>
    public static class SortedEnumerables
    {
        /// <summary>
        /// Allow to merge sorted enumerables without iterating through all of them till the end
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <param name="comparer"></param>
        /// <param name="sortedEnumerablesArray"></param>
        /// <returns></returns>
        public static IEnumerable<T> Merge<T>(IComparer<T> comparer, params IEnumerable<T>[] sortedEnumerablesArray)
        {
            return Merge(sortedEnumerablesArray, comparer);
        }

        /// <summary>
        /// Allow to merge sorted enumerables without iterating through all of them till the end
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <param name="sortedEnumerablesArray"></param>
        /// <returns></returns>
        public static IEnumerable<T> Merge<T>(params IEnumerable<T>[] sortedEnumerablesArray)
        {
            return Merge<T>(sortedEnumerablesArray, null);
        }

        /// <summary>
        /// Allow to merge sorted enumerables without iterating through all of them till the end
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <param name="sortedEnumerables"></param>
        /// <param name="comparer"></param>
        /// <returns></returns>
        public static IEnumerable<T> Merge<T>(IEnumerable<IEnumerable<T>> sortedEnumerables, IComparer<T> comparer = null)
        {
            return new SortedEnumerablesMerger<T>(sortedEnumerables, comparer);
        }
    }

    public class SortedEnumerablesMerger<T> : IEnumerable<T>
    {
        public IComparer<T> Comparer { get; protected set; } = Comparer<T>.Default;
        public IEnumerable<IEnumerable<T>> SortedEnumerables { get; protected set; }

        public SortedEnumerablesMerger(IEnumerable<IEnumerable<T>> sourceItemsEnums, IComparer<T> comparer = null)
        {
            SortedEnumerables = sourceItemsEnums;
            Comparer = comparer;
        }

        class SourceEnumeratorState
        {
            public IEnumerable<T> Items;
            public IEnumerator<T> Enumerator;
            public bool MoveNext;
            public T Current;

            public SourceEnumeratorState GetNext()
            {
                if (MoveNext = Enumerator.MoveNext())
                    Current = Enumerator.Current;
                return this;
            }
        }

        IEnumerable<T> IterateMerged()
        {
            var comparer = (Comparer ?? Comparer<T>.Default);
            var enumerators = SortedEnumerables
                .Select(se =>new { Items = se, Enumerator = se.GetEnumerator() })
                .Select(e => new SourceEnumeratorState()
                {
                    Items = e.Items,
                    Enumerator = e.Enumerator,
                }.GetNext()
                )
                .Where(e => e.MoveNext);
            var priorityQueue = PriorityQueue.Create(enumerators, e => e.Current, comparer);

            while (!priorityQueue.IsEmpty)
            {
                var nextItem = priorityQueue.Dequeue();
                yield return nextItem.Current;
                nextItem.MoveNext = nextItem.Enumerator.MoveNext();
                nextItem.Current = nextItem.MoveNext ? nextItem.Enumerator.Current : default(T);
                if (nextItem.MoveNext)
                    priorityQueue.Enqueue(nextItem);
            }

        }

        public IEnumerator<T> GetEnumerator()
        {
            return IterateMerged().GetEnumerator();
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }
    }
}