using System;

using System.Collections;

using System.Collections.Generic;

using System.Linq;

using System.Diagnostics;

using System.IO;

​

public class Program

{

    public static void Main()

    {

        var source = Enumerable.Range(1, 1000).ToArray();

        var random = new Random(0);

        var sizes = source.ToDictionary(x => x,

            _ => (long)random.Next(5_000_000, 50_000_000));

        int loaderInvokedCount = 0;

        var query = GetPairs(source, x => sizes[x], x =>

        {

            loaderInvokedCount++;

            return new MemoryStream();

        }, 2_000_000_000);

        var emittedPairsCount = query.Count();

        Console.WriteLine($"Emitted {emittedPairsCount:#,0} pairs");

        Console.WriteLine($"Loader invoked {loaderInvokedCount:#,0} times");

    }

​

    public static IEnumerable<(TItem, TItem)> GetPairs<TSource, TItem>(

        IReadOnlyList<TSource> source,

        Func<TSource, long> sizeSelector,

        Func<TSource, TItem> itemLoader,

        long maxConcurrentSize) where TItem : IDisposable

    {

        List<(int Index, TItem Item, long Size)> loaded = new();

        try

        {

            long loadedSumSize = 0L;

            Queue<int> unloaded = new(Enumerable.Range(0, source.Count));

            int[] pending = new int[source.Count];

            for (int i = 0; i < pending.Length; i++) pending[i] = source.Count - 1;

            BitArray emittedPairs = new(checked(source.Count * (source.Count - 1) >> 1));

            while (unloaded.Count > 0)

            {

                // Select the next item to load, in FIFO order.

                int indexToLoad = unloaded.Dequeue();

                long sizeToLoad = Math.Max(0L, sizeSelector(source[indexToLoad]));

​

                // Unload already loaded items until there is enough space for the

                // new item, in LIFO order.

                while (loaded.Count > 1 && loadedSumSize + sizeToLoad > maxConcurrentSize)

                {

                    var toUnload = loaded[loaded.Count - 1];

                    loaded.RemoveAt(loaded.Count - 1);

                    toUnload.Item.Dispose();

                    unloaded.Enqueue(toUnload.Index);

                    loadedSumSize -= toUnload.Size;

                }

​

                // Load the new item.

                var itemToLoad = itemLoader(source[indexToLoad]);

                loaded.Add((indexToLoad, itemToLoad, sizeToLoad));

                checked { loadedSumSize += sizeToLoad; }

                var justLoaded = loaded[loaded.Count - 1];

​

                // Yield pairs constituted of the new item with all already loaded items.

                for (int i = 0; i < loaded.Count - 1; i++)

                {

                    var existing = loaded[i];

                    Debug.Assert(existing.Index != justLoaded.Index);

​

                    // Switch the order in case the pair is not in the correct order.

                    var (x, y) = existing.Index < justLoaded.Index ?

                        (existing, justLoaded) : (justLoaded, existing);

​

                    // Emit the pair if it's not already emitted.

                    int emittedIndex = (y.Index * (y.Index - 1) >> 1) + x.Index;

                    if (emittedPairs[emittedIndex]) continue;

                    yield return (x.Item, y.Item);

                    emittedPairs[emittedIndex] = true;

                    pending[x.Index]--;

                    pending[y.Index]--;

                }

​

                // Unload all items that are completed.

                for (int i = loaded.Count - 1; i >= 0; i--)

                {

                    var (index, item, size) = loaded[i];

                    if (pending[index] > 0) continue;

                    Debug.Assert(pending[index] == 0);

                    loaded.RemoveAt(i);

                    item.Dispose();

                    loadedSumSize -= size;

                }

            }

​

            // If the algorithm is correct, these final assertions should never fail.

            Debug.Assert(loaded.Count == 0);

            Debug.Assert(loadedSumSize == 0L);

            Debug.Assert(pending.All(n => n == 0));

            Debug.Assert(emittedPairs.Cast<bool>().All(b => b));

        }

        finally

        {

            // Ensure that in case the enumerable is enumerated only partially,

            // all currently loaded items will be disposed.

            foreach (var entry in loaded) entry.Item.Dispose();

        }

    }

​

    public static IEnumerable<(TItem, TItem)> GetPairs_Naive<TSource, TItem>(

        IReadOnlyList<TSource> source,

        Func<TSource, long> sizeSelector,

        Func<TSource, TItem> itemLoader,

        long maxConcurrentSize) where TItem : IDisposable

    {

        for (int i = 0; i < source.Count; i++)

        {

            using var first = itemLoader(source[i]);

            for (int j = i + 1; j < source.Count; j++)

            {

                using var second = itemLoader(source[j]);

                yield return (first, second);

            }

        }

    }

}

​