using System;

using System.Collections.Generic;

using System.Linq;

​

public static class Program

{

    public static void Main()

    {

        const int itemsCount = 6;

        const int minWeight = 1;

        const int maxWeight = 1;

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

        var random = new Random(0);

        var sizes = source.ToDictionary(x => x, _ => (long)random.Next(minWeight, maxWeight + 1));

        long maxConcurrentSize = (long)Math.Ceiling(sizes.Values.Sum() * 0.50);

        Console.WriteLine($"Items Count: {source.Length:#,0}");

        Console.WriteLine($"Size Sum: {sizes.Values.Sum():#,0}, Avg: {sizes.Values.Average():#,0}");

        Console.WriteLine($"MaxConcurrentSize: {maxConcurrentSize:#,0}");

        int sizeSelectorCount = 0;

        int loadedCount = 0, unloadedCount = 0;

        long totalLoadedSize = 0;

        long currentLoadedSize = 0;

        SortedSet<int> loaded = new();

        Func<int, long> sizeSelector = key =>

        {

            sizeSelectorCount++;

            return sizes[key];

        };

        Func<int, Resource<int>> itemLoader = key =>

        {

            var item = new Resource<int>(key, () =>

            {

                bool removed = loaded.Remove(key);

                //if (!removed) throw new InvalidOperationException($"Not removed #{key}, Loaded: [{String.Join(", ", loaded)}]");

                if (!removed) Console.WriteLine($"Disposing #{key} error: Not loaded!");

                unloadedCount++;

                if (removed) currentLoadedSize -= sizes[key];

            });

            loaded.Add(key);

            loadedCount++;

            currentLoadedSize += sizes[key];

            if (currentLoadedSize > maxConcurrentSize && loaded.Count > 2) throw new InvalidOperationException($"Max size violation, {currentLoadedSize} > {maxConcurrentSize}.");

            totalLoadedSize += sizes[key];

            return item;

        };

        var query = GetPairs(source, sizeSelector, itemLoader, maxConcurrentSize);

        List<(int, int)> pairs = new();

        foreach (var (x, y) in query)

        {

            pairs.Add((x.Key, y.Key));

        }

        Console.WriteLine();

        var expectedPairsCount = ((long)itemsCount * (itemsCount - 1)) / 2;

        Console.WriteLine($"Pairs: {pairs.Count:#,0}" + (pairs.Count == expectedPairsCount ? "" : $" Error! (expected: {expectedPairsCount:#,0})"));

        var baseLoadedCount = source.Select((x, i) => i + 1).Sum();

        var baseLoadedSize = source.Select((x, i) => sizes[x] * (i + 1)).Sum();

        Console.WriteLine($"Loaded: {loadedCount:#,0} (discount: {(loadedCount - baseLoadedCount) / (double)baseLoadedCount:+0.0%;-0.0%;0.0%} / {(totalLoadedSize - baseLoadedSize) / (double)baseLoadedSize:+0.0%;-0.0%;0.0%})");

        Console.WriteLine($"Unloaded: {unloadedCount:#,0}" + (unloadedCount == loadedCount && loaded.Count == 0 ? "" : $" Error! (non-disposed count: {loaded.Count:#,0})"));

        Console.WriteLine($"Size selector Count: {sizeSelectorCount:#,0}");

        var orderedPairs = pairs.OrderBy(p => p.Item1).ThenBy(p => p.Item2);

        var expectedPairs = source.SelectMany((x, i) => source.Skip(i + 1), (x, y) => (x, y));

        var pairsOK = orderedPairs.SequenceEqual(expectedPairs);

        Console.WriteLine($"Validation: {(pairsOK ? "OK" : "Error!")}");

        if (!pairsOK)

        {

            foreach (var (x, y) in orderedPairs.Zip(expectedPairs))

            {

                if (x != y)

                {

                    Console.WriteLine($"- First Error: {x} instead of {y}");

                    break;

                }

            }

            Console.WriteLine($"Received: [{String.Join(", ", orderedPairs)}]");

            Console.WriteLine($"Expected: [{String.Join(", ", expectedPairs)}]");

        }

    }

​

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

        IReadOnlyList<TSource> source,

        Func<TSource, long> sizeSelector,

        Func<TSource, TItem> itemLoader,

        long maxConcurrentSize) where TItem : IDisposable

    {

​

        var itemCount = source.Count;

        var comparisons = new List<Comparison<TSource>>(itemCount * itemCount / 2);

        for (int i = 0; i < itemCount - 1; i++)

        {

            for (int j = i + 1; j < itemCount; j++)

            {

                comparisons.Add(new(source[i], source[j]));

            }

        }

        return GetPairs_Internal(comparisons, sizeSelector, itemLoader, maxConcurrentSize);

​

        static IEnumerable<(TItem, TItem)> GetPairs_Internal(List<Comparison<TSource>> remainingComparisons,

            Func<TSource, long> sizeSelector,

            Func<TSource, TItem> itemLoader,

            long maxConcurrentSize)

        {

            if (!remainingComparisons.Any()) yield break;

            var images = LoadImages(remainingComparisons, sizeSelector, itemLoader, maxConcurrentSize);//load as many images as possible from the remaining comparisons

            var imageCount = images.Count;

            for (int i = 0; i < imageCount - 1; i++)

            {

                var (path1, image1) = images[i];

                for (int j = i + 1; j < imageCount; j++)

                {

                    var (path2, image2) = images[j];

                    yield return new(image1, image2);

                    var comparison = new Comparison<TSource>(path1, path2);

                    remainingComparisons.RemoveAll(c => c.IsEquivalentTo(comparison));

                }

            }

​

            //dispose

            foreach (var image in images.Select(i => i.Image))

            {

                image.Dispose();

            }

​

            images = null;//allow GC

            foreach (var pair in GetPairs_Internal(remainingComparisons, sizeSelector, itemLoader, maxConcurrentSize))

            {

                yield return pair;

            }

        }

​

        static List<(TSource Path, TItem Image)> LoadImages(List<Comparison<TSource>> remainingComparisons, Func<TSource, long> sizeSelector,

            Func<TSource, TItem> itemLoader,

            long maxConcurrentSize)

        {

            var availableMemory = maxConcurrentSize;

            remainingComparisons = remainingComparisons.ToList();//copy the list so we can alter it in local scope

            var loadedImages = new List<(TSource Path, TItem Image)>();

            if (!TryGetSeed(out var seed)) throw new Exception("One of the images is too large to load into memory");

            while (remainingComparisons.Any())

            {

                if (!remainingComparisons.TryGetFirst(c => c.Contains(seed), out var comparison))

                {

                    if (!TryGetSeed(out seed)) break;

                    continue;

                }

​

                var other = comparison.Other(seed);

                remainingComparisons.Remove(comparison);

                if (!TryLoad(other)) break;

​

            }

​

            return loadedImages;

​

            bool TryLoad(TSource path)

            {

                var fileSize = sizeSelector(path);

                if (fileSize > availableMemory) return false;

                loadedImages.Add(new(path, itemLoader(path)));

                availableMemory -= fileSize;

                return true;

            }

​

            bool TryGetSeed(out TSource seed)

            {

                //first, remove any comparisons that are relevant to the current loaded list

                var loadedImageCount = loadedImages.Count;

                for (int i = 0; i < loadedImageCount - 1; i++)

                {

                    for (int j = 1; j < loadedImageCount; j++)

                    {

                        var localComparison = new Comparison<TSource>(loadedImages[i].Path, loadedImages[j].Path);

                        remainingComparisons.RemoveAll(c => c.IsEquivalentTo(localComparison));

                    }

                }

​

                if (!remainingComparisons.TryGetFirst(out var firstRemaining))

                {

                    seed = default;

                    return false;

                }

​

                seed = firstRemaining.Path1;

                return TryLoad(seed);

            }

        }

    }

​

    record Comparison<T>(T Path1, T Path2)

    {

        public bool Contains(T path) => Path1.Equals(path) || Path2.Equals(path);

​

​

        public T Other(T path)

        {

            if (Path1.Equals(path)) return Path2;

            if (Path2.Equals(path)) return Path1;

            throw new Exception("invalid path");

        }

​

        public bool IsEquivalentTo(Comparison<T> other) => (other.Path1.Equals(Path1) && other.Path2.Equals(Path2)) ||

                                                            (other.Path2.Equals(Path1) && other.Path1.Equals(Path2));

    }

​

    private static bool TryGetFirst<T>(this IEnumerable<T> items, out T value) =>

        items.TryGetFirst(t => true, out value);

    private static bool TryGetFirst<T>(this IEnumerable<T> items, Predicate<T> condition, out T value)

    {

        foreach (var item in items)

        {

            if (condition(item))

            {

                value = item;

                return true;

            }

        }

        value = default;

        return false;

    }

​

    private class Resource<TKey> : IDisposable

    {

        private Action _disposeAction;

​

        public TKey Key { get; }

        public Resource(TKey key, Action disposeAction)

        {

            Key = key;

            _disposeAction = disposeAction ?? throw new ArgumentNullException();

        }

        public void Dispose()

        {

            if (_disposeAction == null) throw new InvalidOperationException($"Key #{Key} disposed twice.");

            _disposeAction();

            _disposeAction = null;

        }

    }

}