How to lazy merge a few enumerables by some rule

Question

For example I have to sequences:

IEnumerable<float> List1 = new float[] {
    0f, 0.1f, 0.5f, 0.9f, // < 1
    1f, 1.1f, 1.5f, 1.9f, // < 2
    2f, 2.9f // < 3
    };

IEnumerable<int> List2 = new int[] {
    1,
    2,
    3,
    4
    };

I need to get next result:

0f, 0.1f, 0.5f, 0.9f, 1,
1f, 1.1f, 1.5f, 1.9f, 2,
2f, 2.9f, 3,
4

I wrote two functions but thay are not lazy!

private static IEnumerable<object> Merge(IEnumerable<float> list1, IEnumerable<int> list2) {
    var queue1 = new Queue<float>( list1 ); // it is not lazy!!
    var queue2 = new Queue<int>( list2 );

    while (queue1.Any() && queue2.Any()) {
        if (queue1.Peek() < queue2.Peek()) {
            yield return queue1.Dequeue();
        } else {
            yield return queue2.Dequeue();
        }
    }

    while (queue1.Any()) {
        yield return queue1.Dequeue();
    }

    while (queue2.Any()) {
        yield return queue2.Dequeue();
    }
}


private static IEnumerable<object> Merge2(IEnumerable<float> list1, IEnumerable<int> list2) {
    var queue1 = new Queue<float>( list1 ); // it is not lazy!!

    foreach (var item2 in list2) {
        while (queue1.Any() && queue1.Peek() < item2) {
            yield return queue1.Dequeue();
        }
        yield return item2;
    }
}

How can I do it with lazy evaluation?

Answer 1

I made a comfortable wrapper for IEnumerator<T> and more beautiful Merge method.

public static IEnumerable<object> Merge(IEnumerable<float> list1, IEnumerable<int> list2) {
    using (var enumerator1 = new SmartEnumerator<float>( list1.GetEnumerator() ))
    using (var enumerator2 = new SmartEnumerator<int>( list2.GetEnumerator() )) {

        while (!enumerator1.IsCompleted && !enumerator2.IsCompleted) {
            if (enumerator1.Peek() < enumerator2.Peek()) {
                yield return enumerator1.Pull();
            } else {
                yield return enumerator2.Pull();
            }
        }

        while (!enumerator1.IsCompleted) {
            yield return enumerator1.Pull();
        }

        while (!enumerator2.IsCompleted) {
            yield return enumerator2.Pull();
        }
    }
}


public class SmartEnumerator<T> : IDisposable {

    private readonly IEnumerator<T> target;
    private bool hasValue;
    private T Value => target.Current;

    public bool IsCompleted {
        get {
            RequestNextValueIfNeeded();
            return !hasValue;
        }
    }


    public SmartEnumerator(IEnumerator<T> target) {
        this.target = target;
    }

    public void Dispose() {
        target.Dispose();
    }


    public T Peek() {
        if (IsCompleted && !hasValue) throw new InvalidOperationException( "Enumerator is already completed" );

        RequestNextValueIfNeeded();
        return Value;
    }

    public T Pull() {
        if (IsCompleted && !hasValue) throw new InvalidOperationException( "Enumerator is already completed" );

        RequestNextValueIfNeeded();
        hasValue = false;
        return Value;
    }


    // Helpers
    private void RequestNextValueIfNeeded() {
        if (!hasValue) RequestNextValue();
    }

    private void RequestNextValue() {
        hasValue = target.MoveNext();
    }


}

Answer 2

I assume you have two sequences that are already respectively ordered, and you want to return the ordered sequence that results from merging the two. This sequence is generated lazily, reading just the next element from each sequence at a time.

private static IEnumerable<object> Merge(IEnumerable<float> sequence1, IEnumerable<int> sequence2)
{
    // Get enumerators for iterating through the two sequences.
    using (var enumerator1 = sequence1.GetEnumerator())
    using (var enumerator2 = sequence2.GetEnumerator())
    {
        var remaining1 = enumerator1.MoveNext();
        var remaining2 = enumerator2.MoveNext();

        while (remaining1 && remaining2)
        {
            if (enumerator1.Current < enumerator2.Current)
            {
                yield return enumerator1.Current;
                remaining1 = enumerator1.MoveNext();
            }
            else
            {
                yield return enumerator2.Current;
                remaining2 = enumerator2.MoveNext();
            }
        }

        if (remaining1)
        {
            do { yield return enumerator1.Current; }
            while (enumerator1.MoveNext());
        }
        else if (remaining2)
        {
            do { yield return enumerator2.Current; }
            while (enumerator2.MoveNext());
        }
    }
}

Update: Based on Enigmativity's comment, you can generalize this to work with any comparable type:

private static IEnumerable<T> Merge<T>(IEnumerable<T> sequence1, IEnumerable<T> sequence2, IComparer<T> comparer = null)
{
    if (comparer == null)
        comparer = Comparer<T>.Default;

    // Get enumerators for iterating through the two sequences.
    using (var enumerator1 = sequence1.GetEnumerator())
    using (var enumerator2 = sequence2.GetEnumerator())
    {
        var remaining1 = enumerator1.MoveNext();
        var remaining2 = enumerator2.MoveNext();

        while (remaining1 && remaining2)
        {
            if (comparer.Compare(enumerator1.Current, enumerator2.Current) < 0)
            {
                yield return enumerator1.Current;
                remaining1 = enumerator1.MoveNext();
            }
            else
            {
                yield return enumerator2.Current;
                remaining2 = enumerator2.MoveNext();
            }
        }

        if (remaining1)
        {
            do { yield return enumerator1.Current; }
            while (enumerator1.MoveNext());
        }
        else if (remaining2)
        {
            do { yield return enumerator2.Current; }
            while (enumerator2.MoveNext());
        }
    }
}

However, for the OP's example of merging float[] with int[], one would need to cast the second list:

var result = Merge(List1, List2.Select(x => (float)x));