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();
    }


}