Wednesday, February 17, 2010

C# Stream Array Merge Extension Method

If the need to sort a collection larger than the amount of RAM available arises, merge sort algorithms are a good solution. The following extension method is a merge algorithm implementation that combines two or more sorted Streams using Read and Output functions passed as parameters.


public static class StreamArrayExtension
{
public static void Merge<T>(this Stream[] Streams,
Func<Stream, T> ReadItem, Action<T> OutputItem)
where T : IComparable<T>
{
T[] buffer = new T[Streams.Length];

for (int x = 0; x < Streams.Length; x++)
buffer[x] = ReadItem(Streams[x]);

int end = Streams.Length - 1;

bool[] completed = new bool[Streams.Length];

int completedCount = 0;

while (completedCount < Streams.Length)
for (int x = 0; x < Streams.Length; x++)
if (completed[x])
continue;
else
for (int y = 0; y < Streams.Length; y++)
if (x == y && x != end)
continue;
else if (!completed[y] &&
buffer[x].CompareTo(buffer[y]) == 1)
break;
else if (y == end)
{
OutputItem(buffer[x]);

if (Streams[x].Position != Streams[x].Length)
buffer[x] = ReadItem(Streams[x]);
else
{
completed[x] = true;

completedCount++;
}
}
}
}


It can be used as follows:

Stream[] sortedStreams = new Stream[]
{
new MemoryStream(new byte[] { 1, 2, 3 }),
new MemoryStream(new byte[] { 0, 4 }),
new MemoryStream(new byte[] { 1, 5 }),
};

sortedStreams.Merge(x => x.ReadByte(), x => Console.WriteLine(x));

Console.ReadKey();


With the resulting output:
0
1
1
2
3
4
5

No comments:

Post a Comment