Stream merge: Difference between revisions

Content added Content deleted
Line 590: Line 590:
namespace RosettaCode
namespace RosettaCode
{
{
class StreamMerge
static class StreamMerge
{
{
static IEnumerable<T> Merge2<T>(IEnumerable<T> i1, IEnumerable<T> i2) where T : IComparable
static IEnumerable<T> Merge2<T>(IEnumerable<T> source1, IEnumerable<T> source2) where T : IComparable
{
{
var q1 = new Queue<T>(i1);
var q1 = new Queue<T>(source1);
var q2 = new Queue<T>(i2);
var q2 = new Queue<T>(source2);
while (q1.Any() && q2.Any())
while (q1.Any() && q2.Any())
{
{
Line 605: Line 605:
}
}


static IEnumerable<T> MergeN<T>(params IEnumerable<T>[] enumerables) where T : IComparable
static IEnumerable<T> MergeN<T>(params IEnumerable<T>[] sources) where T : IComparable
{
{
var queues = enumerables.Select(e => new Queue<T>(e)).Where(q => q.Any()).ToList();
var queues = sources.Select(e => new Queue<T>(e)).Where(q => q.Any()).ToList();
var headComparer = Comparer<Queue<T>>.Create((x, y) => x.Peek().CompareTo(y.Peek()));

queues.Sort(headComparer);
while (queues.Any())
while (queues.Any())
{
{
var queueWithLowestItem = queues.Aggregate((q1, q2) => q1.Peek().CompareTo(q2.Peek()) <= 0 ? q1 : q2);
var q = queues.First();
yield return queueWithLowestItem.Dequeue();
queues.RemoveAt(0);
if (!queueWithLowestItem.Any()) queues.Remove(queueWithLowestItem);
yield return q.Dequeue();
if (q.Any())
{
var index = queues.BinarySearch(q, headComparer);
queues.Insert(index < 0 ? ~index : index, q);
}
}
}
}
}


static void Main(string[] args)
static void Main()
{
{
var a = new[] { 1, 4, 7, 10 };
var a = new[] { 1, 4, 7, 10 };