Skip to content

Instantly share code, notes, and snippets.

@erdomke
Created January 16, 2018 17:21
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save erdomke/06b242972a08676d1267d9b4bcbe3c81 to your computer and use it in GitHub Desktop.
Save erdomke/06b242972a08676d1267d9b4bcbe3c81 to your computer and use it in GitHub Desktop.
Merge two sorted lists
public static class Utils
{
[Flags]
public enum MergeStatus
{
LeftOnly = 1,
RightOnly = 2,
Both = 3,
}
public static void MergeSorted<T, TKey>(this IList<T> left, IList<T> right,
Func<T, TKey> keyGetter, Action<MergeStatus, T, T> callback) where TKey : IComparable
{
MergeSorted(left, right, keyGetter, callback, Comparer<TKey>.Default);
}
public static void MergeSorted<T, TKey>(this IList<T> left, IList<T> right,
Func<T, TKey> keyGetter, Action<MergeStatus, T, T> callback, IComparer<TKey> comparer)
{
var leftPtr = 0;
var rightPtr = 0;
var leftKey = keyGetter(left[leftPtr]);
var rightKey = keyGetter(right[rightPtr]);
int status;
while (leftPtr < left.Count && rightPtr < right.Count)
{
status = comparer.Compare(leftKey, rightKey);
if (status < 0)
{
callback(MergeStatus.LeftOnly, left[leftPtr], default(T));
leftKey = keyGetter(left[++leftPtr]);
}
else if (status > 0)
{
callback(MergeStatus.RightOnly, default(T), right[rightPtr]);
rightKey = keyGetter(right[++rightPtr]);
}
else
{
callback(MergeStatus.Both, left[leftPtr], right[rightPtr]);
leftKey = keyGetter(left[++leftPtr]);
rightKey = keyGetter(right[++rightPtr]);
}
}
while (leftPtr < left.Count)
{
callback(MergeStatus.LeftOnly, left[leftPtr], default(T));
leftPtr++;
}
while (rightPtr < right.Count)
{
callback(MergeStatus.RightOnly, default(T), right[rightPtr]);
rightPtr++;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment