Meziantou.Polyfill by Gérald Barré

Nuget / site data
Details
How to use
- Example ( source csproj, source files )
- Generated Files
Usefull

Nuget / site data

Details

Info

info

Name: Meziantou.Polyfill

Source Generator to help multi-targeting projects.

Author: Gérald Barré

NuGet: https://www.nuget.org/packages/Meziantou.Polyfill/

You can find more details at https://www.meziantou.net/polyfills-in-dotnet-to-ease-multi-targeting.htm

Source : https://github.com/meziantou/Meziantou.Polyfill

Original Readme

note

Meziantou.Polyfill

Source Generator that adds polyfill methods and types. This helps working with multi-targeted projects.

You can use the following MSBuild properties to configure which polyfills are generated:

<PropertyGroup>
  <!-- semi-column separated list of name prefix -->
  <!-- Tip: The name of the generated polyfills are available in the generated "Debug.g.cs" file -->
  <MeziantouPolyfill_IncludedPolyfills>T:Type1|T:Type2|M:Member1</MeziantouPolyfill_IncludedPolyfills>
  <MeziantouPolyfill_ExcludedPolyfills>M:System.Diagnostics.</MeziantouPolyfill_ExcludedPolyfills>

  <!-- Optional: Output the generated files to the obj\GeneratedFiles folder  -->
  <EmitCompilerGeneratedFiles>True</EmitCompilerGeneratedFiles>
  <CompilerGeneratedFilesOutputPath>$(BaseIntermediateOutputPath)\GeneratedFiles</CompilerGeneratedFilesOutputPath>
</PropertyGroup>

How to add a new polyfill

Create a new file named <xml documentation id>.cs in the project Meziantou.Polyfill.Editor
Run Meziantou.Polyfill.Generator

Notes:

All files must be self contained. Use a file class if needed.
If you need to generate a file only when another polyfill is generated, add // when <xml documentation id> in the file

About

note

Generating polyfills that you can see source without de-compiling

How to use

Example ( source csproj, source files )

CSharp Project
Program.cs
StartProcess.cs

This is the CSharp Project that references Meziantou.Polyfill

<Project Sdk="Microsoft.NET.Sdk">

  <PropertyGroup>
    <OutputType>Exe</OutputType>
    <TargetFrameworks>net7.0;netstandard2.0</TargetFrameworks>
      <LangVersion>latest</LangVersion>
  </PropertyGroup>

  <ItemGroup>
    <PackageReference Include="Meziantou.Polyfill" Version="1.0.28">
      <IncludeAssets>runtime; build; native; contentfiles; analyzers; buildtransitive</IncludeAssets>
      <PrivateAssets>all</PrivateAssets>
    </PackageReference>
  </ItemGroup>

    <PropertyGroup>
        <EmitCompilerGeneratedFiles>true</EmitCompilerGeneratedFiles>
        <CompilerGeneratedFilesOutputPath>$(BaseIntermediateOutputPath)\GX</CompilerGeneratedFilesOutputPath>
    </PropertyGroup>
</Project>

This is the use of Meziantou.Polyfill in Program.cs

// See https://aka.ms/new-console-template for more information
System.Console.WriteLine("Hello, World!");

This is the use of Meziantou.Polyfill in StartProcess.cs

using System.Diagnostics;
using System.Threading.Tasks;

namespace Meziantou.PolyfillDemo
{

    internal class StartProcess
    {
        static async Task StartNotepad()
        {
            await Task.Delay(1000);
            var process = Process.Start("notepad.exe");

#if NET6_0_OR_GREATER
           await process.WaitForExitAsync();
#else
            process.WaitForExit();
#endif
            
        }
        static async Task StartNotepadPolyFill()
        {
            await Task.Delay(1000);
            var process = Process.Start("notepad.exe");
            //do remove nuget Meziantou.Polyfill - this line will not be ok.
            await process.WaitForExitAsync();

        }

    }
}

Generated Files

Those are taken from $(BaseIntermediateOutputPath)\GX

// IncludedMembers: <null>
// ExcludedMembers: <null>
// System.Collections.Immutable.ImmutableArray`1: False
// System.Memory`1: False
// System.Net.Http.HttpContent: True
// System.ReadOnlyMemory`1: False
// System.ReadOnlySpan`1: False
// System.Span`1: False
// System.Threading.Tasks.ValueTask: False
// System.Threading.Tasks.ValueTask`1: False
//
// M:System.Collections.Concurrent.ConcurrentDictionary`2.GetOrAdd``1(`0,System.Func{`0,``0,`1},``0): True
// M:System.Collections.Generic.CollectionExtensions.GetValueOrDefault``2(System.Collections.Generic.IReadOnlyDictionary{``0,``1},``0): True
// M:System.Collections.Generic.CollectionExtensions.GetValueOrDefault``2(System.Collections.Generic.IReadOnlyDictionary{``0,``1},``0,``1): True
// M:System.Collections.Generic.KeyValuePair`2.Deconstruct(`0@,`1@): True
// M:System.Collections.Generic.Queue`1.TryDequeue(`0@): True
// M:System.Collections.Immutable.ImmutableArray`1.AsSpan(System.Int32,System.Int32): False
// M:System.Collections.Immutable.ImmutableArray`1.AsSpan(System.Range): False
// M:System.Diagnostics.Process.WaitForExitAsync(System.Threading.CancellationToken): True
// M:System.IO.Stream.Read(System.Span{System.Byte}): False
// M:System.IO.Stream.ReadAsync(System.Memory{System.Byte},System.Threading.CancellationToken): False
// M:System.IO.Stream.ReadAtLeast(System.Span{System.Byte},System.Int32,System.Boolean): False
// M:System.IO.Stream.ReadAtLeastAsync(System.Memory{System.Byte},System.Int32,System.Boolean,System.Threading.CancellationToken): False
// M:System.IO.Stream.Write(System.ReadOnlySpan{System.Byte}): False
// M:System.IO.Stream.WriteAsync(System.ReadOnlyMemory{System.Byte},System.Threading.CancellationToken): False
// M:System.IO.StreamReader.ReadLineAsync(): False
// M:System.IO.StreamReader.ReadLineAsync(System.Threading.CancellationToken): False
// M:System.IO.TextReader.ReadAsync(System.Memory{System.Char},System.Threading.CancellationToken): False
// M:System.IO.TextReader.ReadToEndAsync(System.Threading.CancellationToken): True
// M:System.IO.TextWriter.WriteAsync(System.ReadOnlyMemory{System.Char},System.Threading.CancellationToken): False
// M:System.Linq.Enumerable.DistinctBy``2(System.Collections.Generic.IEnumerable{``0},System.Func{``0,``1}): True
// M:System.Linq.Enumerable.DistinctBy``2(System.Collections.Generic.IEnumerable{``0},System.Func{``0,``1},System.Collections.Generic.IEqualityComparer{``1}): True
// M:System.Linq.Enumerable.MaxBy``2(System.Collections.Generic.IEnumerable{``0},System.Func{``0,``1}): True
// M:System.Linq.Enumerable.MaxBy``2(System.Collections.Generic.IEnumerable{``0},System.Func{``0,``1},System.Collections.Generic.IComparer{``1}): True
// M:System.Linq.Enumerable.MinBy``2(System.Collections.Generic.IEnumerable{``0},System.Func{``0,``1}): True
// M:System.Linq.Enumerable.MinBy``2(System.Collections.Generic.IEnumerable{``0},System.Func{``0,``1},System.Collections.Generic.IComparer{``1}): True
// M:System.Linq.Enumerable.OrderDescending``1(System.Collections.Generic.IEnumerable{``0}): True
// M:System.Linq.Enumerable.OrderDescending``1(System.Collections.Generic.IEnumerable{``0},System.Collections.Generic.IComparer{``0}): True
// M:System.Linq.Enumerable.Order``1(System.Collections.Generic.IEnumerable{``0}): True
// M:System.Linq.Enumerable.Order``1(System.Collections.Generic.IEnumerable{``0},System.Collections.Generic.IComparer{``0}): True
// M:System.Linq.Enumerable.ToHashSet``1(System.Collections.Generic.IEnumerable{``0}): True
// M:System.Linq.Enumerable.ToHashSet``1(System.Collections.Generic.IEnumerable{``0},System.Collections.Generic.IEqualityComparer{``0}): True
// M:System.Linq.Enumerable.Zip``2(System.Collections.Generic.IEnumerable{``0},System.Collections.Generic.IEnumerable{``1}): True
// M:System.MemoryExtensions.AsSpan(System.String,System.Int32,System.Int32): False
// M:System.MemoryExtensions.Contains``1(System.ReadOnlySpan{``0},``0): False
// M:System.MemoryExtensions.Contains``1(System.Span{``0},``0): False
// M:System.Net.Http.HttpContent.CopyTo(System.IO.Stream,System.Net.TransportContext,System.Threading.CancellationToken): True
// M:System.Net.Http.HttpContent.CopyToAsync(System.IO.Stream): False
// M:System.Net.Http.HttpContent.CopyToAsync(System.IO.Stream,System.Net.TransportContext): False
// M:System.Net.Http.HttpContent.CopyToAsync(System.IO.Stream,System.Net.TransportContext,System.Threading.CancellationToken): True
// M:System.Net.Http.HttpContent.CopyToAsync(System.IO.Stream,System.Threading.CancellationToken): True
// M:System.Net.Http.HttpContent.ReadAsStream(System.Threading.CancellationToken): True
// M:System.Net.Http.HttpContent.ReadAsStream: True
// M:System.String.Contains(System.Char): True
// M:System.String.Contains(System.Char,System.StringComparison): True
// M:System.String.Contains(System.String,System.StringComparison): True
// M:System.String.CopyTo(System.Span{System.Char}): False
// M:System.String.EndsWith(System.Char): True
// M:System.String.GetHashCode(System.StringComparison): True
// M:System.String.IndexOf(System.Char,System.StringComparison): True
// M:System.String.Replace(System.String,System.String,System.StringComparison): True
// M:System.String.ReplaceLineEndings(System.String): True
// M:System.String.ReplaceLineEndings: True
// M:System.String.Split(System.Char,System.Int32,System.StringSplitOptions): True
// M:System.String.Split(System.Char,System.StringSplitOptions): True
// M:System.String.StartsWith(System.Char): True
// M:System.String.TryCopyTo(System.Span{System.Char}): False
// M:System.Text.Encoding.GetString(System.ReadOnlySpan{System.Byte}): False
// M:System.Text.StringBuilder.Append(System.ReadOnlyMemory{System.Char}): False
// M:System.Text.StringBuilder.Append(System.ReadOnlySpan{System.Char}): False
// M:System.Text.StringBuilder.AppendJoin(System.Char,System.Object[]): True
// M:System.Text.StringBuilder.AppendJoin(System.Char,System.String[]): True
// M:System.Text.StringBuilder.AppendJoin(System.String,System.Object[]): True
// M:System.Text.StringBuilder.AppendJoin(System.String,System.String[]): True
// M:System.Text.StringBuilder.AppendJoin``1(System.Char,System.Collections.Generic.IEnumerable{``0}): True
// M:System.Text.StringBuilder.AppendJoin``1(System.String,System.Collections.Generic.IEnumerable{``0}): True
// M:System.Threading.CancellationTokenSource.CancelAsync: True
// M:System.Threading.Tasks.Task.WaitAsync(System.Threading.CancellationToken): True
// T:System.Collections.Generic.PriorityQueue`2: True
// T:System.Collections.Generic.ReferenceEqualityComparer: True
// T:System.Diagnostics.CodeAnalysis.AllowNullAttribute: True
// T:System.Diagnostics.CodeAnalysis.DisallowNullAttribute: True
// T:System.Diagnostics.CodeAnalysis.DoesNotReturnAttribute: True
// T:System.Diagnostics.CodeAnalysis.DoesNotReturnIfAttribute: True
// T:System.Diagnostics.CodeAnalysis.DynamicDependencyAttribute: True
// T:System.Diagnostics.CodeAnalysis.DynamicallyAccessedMemberTypes: True
// T:System.Diagnostics.CodeAnalysis.DynamicallyAccessedMembersAttribute: True
// T:System.Diagnostics.CodeAnalysis.MaybeNullAttribute: True
// T:System.Diagnostics.CodeAnalysis.MaybeNullWhenAttribute: True
// T:System.Diagnostics.CodeAnalysis.MemberNotNullAttribute: True
// T:System.Diagnostics.CodeAnalysis.MemberNotNullWhenAttribute: True
// T:System.Diagnostics.CodeAnalysis.NotNullAttribute: True
// T:System.Diagnostics.CodeAnalysis.NotNullIfNotNullAttribute: True
// T:System.Diagnostics.CodeAnalysis.NotNullWhenAttribute: True
// T:System.Diagnostics.CodeAnalysis.RequiresAssemblyFilesAttribute: True
// T:System.Diagnostics.CodeAnalysis.RequiresDynamicCodeAttribute: True
// T:System.Diagnostics.CodeAnalysis.RequiresUnreferencedCodeAttribute: True
// T:System.Diagnostics.CodeAnalysis.SetsRequiredMembersAttribute: True
// T:System.Diagnostics.CodeAnalysis.StringSyntaxAttribute: True
// T:System.Diagnostics.CodeAnalysis.UnconditionalSuppressMessageAttribute: True
// T:System.Diagnostics.CodeAnalysis.UnscopedRefAttribute: True
// T:System.Diagnostics.StackTraceHiddenAttribute: True
// T:System.HashCode: True
// T:System.Index: True
// T:System.Net.Http.ReadOnlyMemoryContent: False
// T:System.Range: True
// T:System.Runtime.CompilerServices.AsyncMethodBuilderAttribute: True
// T:System.Runtime.CompilerServices.CallerArgumentExpressionAttribute: True
// T:System.Runtime.CompilerServices.CollectionBuilderAttribute: True
// T:System.Runtime.CompilerServices.CompilerFeatureRequiredAttribute: True
// T:System.Runtime.CompilerServices.DisableRuntimeMarshallingAttribute: True
// T:System.Runtime.CompilerServices.InterpolatedStringHandlerArgumentAttribute: True
// T:System.Runtime.CompilerServices.InterpolatedStringHandlerAttribute: True
// T:System.Runtime.CompilerServices.IsExternalInit: True
// T:System.Runtime.CompilerServices.ModuleInitializerAttribute: True
// T:System.Runtime.CompilerServices.RequiredMemberAttribute: True
// T:System.Runtime.CompilerServices.SkipLocalsInitAttribute: True
// T:System.Runtime.CompilerServices.TupleElementNamesAttribute: False
// T:System.Runtime.InteropServices.SuppressGCTransitionAttribute: True
// T:System.Runtime.InteropServices.UnmanagedCallersOnlyAttribute: True
// T:System.Runtime.Versioning.ObsoletedOSPlatformAttribute: True
// T:System.Runtime.Versioning.RequiresPreviewFeaturesAttribute: True
// T:System.Runtime.Versioning.SupportedOSPlatformAttribute: True
// T:System.Runtime.Versioning.SupportedOSPlatformGuardAttribute: True
// T:System.Runtime.Versioning.TargetPlatformAttribute: True
// T:System.Runtime.Versioning.UnsupportedOSPlatformAttribute: True
// T:System.Runtime.Versioning.UnsupportedOSPlatformGuardAttribute: True
// T:System.Threading.Tasks.TaskToAsyncResult: True
// T:System.ValueTuple: False
// T:System.ValueTuple`1: False
// T:System.ValueTuple`2: False
// T:System.ValueTuple`3: False
// T:System.ValueTuple`4: False
// T:System.ValueTuple`5: False
// T:System.ValueTuple`6: False
// T:System.ValueTuple`7: False
// T:System.ValueTuple`8: False
// T:System.ITupleInternal: False

// <auto-generated/>
#pragma warning disable
#nullable enable annotations
using System;
using System.Collections.Concurrent;

static partial class PolyfillExtensions
{
    public static TValue GetOrAdd<TKey, TValue, TArg>(this ConcurrentDictionary<TKey, TValue> target, TKey key, Func<TKey, TArg, TValue> valueFactory, TArg factoryArgument)
        where TKey : notnull
    {
        return target.GetOrAdd(key, key => valueFactory(key, factoryArgument));
    }
}

// <auto-generated/>
#pragma warning disable
#nullable enable annotations
using System.Collections.Generic;

static partial class PolyfillExtensions
{
    public static TValue GetValueOrDefault<TKey, TValue>(this IReadOnlyDictionary<TKey, TValue> dictionary, TKey key, TValue defaultValue)
        => dictionary.TryGetValue(key, out TValue? value) ? value : defaultValue;
}

// <auto-generated/>
#pragma warning disable
#nullable enable annotations
using System.Collections.Generic;

static partial class PolyfillExtensions
{
    public static TValue? GetValueOrDefault<TKey, TValue>(this IReadOnlyDictionary<TKey, TValue> dictionary, TKey key)
        => dictionary.GetValueOrDefault(key, default!);
}

// <auto-generated/>
#pragma warning disable
#nullable enable annotations
using System.Collections.Generic;

static partial class PolyfillExtensions
{
    public static void Deconstruct<TKey, TValue>(this KeyValuePair<TKey, TValue> target, out TKey key, out TValue value)
    {
        key = target.Key;
        value = target.Value;
    }
}

// <auto-generated/>
#pragma warning disable
#nullable enable annotations
using System.Collections.Generic;
using System.Diagnostics.CodeAnalysis;

static partial class PolyfillExtensions
{
    public static bool TryDequeue<T>(this Queue<T> target, [MaybeNullWhen(false)] out T result)
    {
        if (target.Count == 0)
        {
            result = default;
            return false;
        }

        result = target.Dequeue();
        return true;
    }
}

// <auto-generated/>
#pragma warning disable
#nullable enable annotations
using System.Threading.Tasks;
using System.Threading;
using System.Diagnostics;
using System;

static partial class PolyfillExtensions
{
    public static async Task WaitForExitAsync(this Process target, CancellationToken cancellationToken = default)
    {
        // https://source.dot.net/#System.Diagnostics.Process/System/Diagnostics/Process.cs,b6a5b00714a61f06
        // Because the process has already started by the time this method is called,
        // we're in a race against the process to set up our exit handlers before the process
        // exits. As a result, there are several different flows that must be handled:
        //
        // CASE 1: WE ENABLE EVENTS
        // This is the "happy path". In this case we enable events.
        //
        // CASE 1.1: PROCESS EXITS OR IS CANCELED AFTER REGISTERING HANDLER
        // This case continues the "happy path". The process exits or waiting is canceled after
        // registering the handler and no special cases are needed.
        //
        // CASE 1.2: PROCESS EXITS BEFORE REGISTERING HANDLER
        // It's possible that the process can exit after we enable events but before we reigster
        // the handler. In that case we must check for exit after registering the handler.
        //
        //
        // CASE 2: PROCESS EXITS BEFORE ENABLING EVENTS
        // The process may exit before we attempt to enable events. In that case EnableRaisingEvents
        // will throw an exception like this:
        //     System.InvalidOperationException : Cannot process request because the process (42) has exited.
        // In this case we catch the InvalidOperationException. If the process has exited, our work
        // is done and we return. If for any reason (now or in the future) enabling events fails
        // and the process has not exited, bubble the exception up to the user.
        //
        //
        // CASE 3: USER ALREADY ENABLED EVENTS
        // In this case the user has already enabled raising events. Re-enabling events is a no-op
        // as the value hasn't changed. However, no-op also means that if the process has already
        // exited, EnableRaisingEvents won't throw an exception.
        //
        // CASE 3.1: PROCESS EXITS OR IS CANCELED AFTER REGISTERING HANDLER
        // (See CASE 1.1)
        //
        // CASE 3.2: PROCESS EXITS BEFORE REGISTERING HANDLER
        // (See CASE 1.2)
        if (!target.HasExited)
        {
            // Early out for cancellation before doing more expensive work
            cancellationToken.ThrowIfCancellationRequested();
        }
        try
        {
            // CASE 1: We enable events
            // CASE 2: Process exits before enabling events (and throws an exception)
            // CASE 3: User already enabled events (no-op)
            target.EnableRaisingEvents = true;
        }
        catch (InvalidOperationException)
        {
            // CASE 2: If the process has exited, our work is done, otherwise bubble the
            // exception up to the user
            if (target.HasExited)
            {
                return;
            }
            throw;
        }
        var tcs = new TaskCompletionSourceWithCancellation<bool>();
        void Handler(object? s, EventArgs e) => tcs.TrySetResult(true);
        target.Exited += Handler;
        try
        {
            if (target.HasExited)
            {
                // CASE 1.2 & CASE 3.2: Handle race where the process exits before registering the handler
                return;
            }
            // CASE 1.1 & CASE 3.1: Process exits or is canceled here
            await tcs.WaitWithCancellationAsync(cancellationToken).ConfigureAwait(false);
        }
        finally
        {
            target.Exited -= Handler;
        }

        target.WaitForExit();
    }

    private sealed class TaskCompletionSourceWithCancellation<T> : TaskCompletionSource<T>
    {
        private CancellationToken _cancellationToken;
        public TaskCompletionSourceWithCancellation() : base(TaskCreationOptions.RunContinuationsAsynchronously)
        {
        }
        private void OnCancellation()
        {
            TrySetCanceled(_cancellationToken);
        }
#if NETCOREAPP3_1_OR_GREATER
        public async ValueTask<T> WaitWithCancellationAsync(CancellationToken cancellationToken)
        {
            _cancellationToken = cancellationToken;
            await using (cancellationToken.UnsafeRegister(s => ((TaskCompletionSourceWithCancellation<T>)s!).OnCancellation(), this))
            {
                return await Task.ConfigureAwait(false);
            }
        }
#else
        public async Task<T> WaitWithCancellationAsync(CancellationToken cancellationToken)
        {
            _cancellationToken = cancellationToken;
            using (cancellationToken.Register(s => ((TaskCompletionSourceWithCancellation<T>)s!).OnCancellation(), this))
            {
                return await Task.ConfigureAwait(false);
            }
        }
#endif
    }
}

// <auto-generated/>
#pragma warning disable
#nullable enable annotations
using System.IO;
using System.Threading;
using System.Threading.Tasks;

static partial class PolyfillExtensions
{
    public static Task<string> ReadToEndAsync(this TextReader target, CancellationToken cancellationToken)
    {
        cancellationToken.ThrowIfCancellationRequested();
        return target.ReadToEndAsync();
    }
}

// <auto-generated/>
#pragma warning disable
#nullable enable annotations
using System;
using System.Collections.Generic;

static partial class PolyfillExtensions
{
    public static IEnumerable<TSource> DistinctBy<TSource, TKey>(this IEnumerable<TSource> source, Func<TSource, TKey> keySelector, IEqualityComparer<TKey>? comparer)
    {
        var hashSet = new HashSet<TKey>(comparer);
        foreach (var item in source)
        {
            var key = keySelector(item);
            if (hashSet.Add(key))
                yield return item;
        }
    }
}

// <auto-generated/>
#pragma warning disable
#nullable enable annotations
using System;
using System.Collections.Generic;

static partial class PolyfillExtensions
{
    public static IEnumerable<TSource> DistinctBy<TSource, TKey>(this IEnumerable<TSource> source, Func<TSource, TKey> keySelector)
    {
        var hashSet = new HashSet<TKey>();
        foreach (var item in source)
        {
            var key = keySelector(item);
            if (hashSet.Add(key))
                yield return item;
        }
    }
}

// <auto-generated/>
#pragma warning disable
#nullable enable annotations
using System;
using System.Collections.Generic;

static partial class PolyfillExtensions
{
    public static TSource? MaxBy<TSource, TKey>(this IEnumerable<TSource> source, Func<TSource, TKey> keySelector)
    {
        return source.MaxBy(keySelector, comparer: null);
    }
}

// <auto-generated/>
#pragma warning disable
#nullable enable annotations
using System;
using System.Collections.Generic;

static partial class PolyfillExtensions
{
    public static TSource? MaxBy<TSource, TKey>(this IEnumerable<TSource> source, Func<TSource, TKey> keySelector, IComparer<TKey>? comparer)
    {
        if (source == null)
            throw new ArgumentNullException(nameof(source));

        if (keySelector == null)
            throw new ArgumentNullException(nameof(keySelector));

        comparer ??= Comparer<TKey>.Default;

        using IEnumerator<TSource> e = source.GetEnumerator();

        if (!e.MoveNext())
        {
            if (default(TSource) is null)
            {
                return default;
            }
            else
            {
                throw new InvalidOperationException("Sequence contains no elements");
            }
        }

        TSource value = e.Current;
        TKey key = keySelector(value);

        if (default(TKey) is null)
        {
            if (key == null)
            {
                TSource firstValue = value;

                do
                {
                    if (!e.MoveNext())
                    {
                        // All keys are null, surface the first element.
                        return firstValue;
                    }

                    value = e.Current;
                    key = keySelector(value);
                }
                while (key == null);
            }

            while (e.MoveNext())
            {
                TSource nextValue = e.Current;
                TKey nextKey = keySelector(nextValue);
                if (nextKey != null && comparer.Compare(nextKey, key) > 0)
                {
                    key = nextKey;
                    value = nextValue;
                }
            }
        }
        else
        {
            if (comparer == Comparer<TKey>.Default)
            {
                while (e.MoveNext())
                {
                    TSource nextValue = e.Current;
                    TKey nextKey = keySelector(nextValue);
                    if (Comparer<TKey>.Default.Compare(nextKey, key) > 0)
                    {
                        key = nextKey;
                        value = nextValue;
                    }
                }
            }
            else
            {
                while (e.MoveNext())
                {
                    TSource nextValue = e.Current;
                    TKey nextKey = keySelector(nextValue);
                    if (comparer.Compare(nextKey, key) > 0)
                    {
                        key = nextKey;
                        value = nextValue;
                    }
                }
            }
        }

        return value;
    }
}

// <auto-generated/>
#pragma warning disable
#nullable enable annotations
using System;
using System.Collections.Generic;

static partial class PolyfillExtensions
{
    public static TSource? MinBy<TSource, TKey>(this IEnumerable<TSource> source, Func<TSource, TKey> keySelector)
    {
        return source.MinBy(keySelector, comparer: null);
    }
}

// <auto-generated/>
#pragma warning disable
#nullable enable annotations
using System;
using System.Collections.Generic;

static partial class PolyfillExtensions
{
    public static TSource? MinBy<TSource, TKey>(this IEnumerable<TSource> source, Func<TSource, TKey> keySelector, IComparer<TKey>? comparer)
    {
        if (source == null)
            throw new ArgumentNullException(nameof(source));

        if (keySelector == null)
            throw new ArgumentNullException(nameof(keySelector));

        comparer ??= Comparer<TKey>.Default;

        using IEnumerator<TSource> e = source.GetEnumerator();

        if (!e.MoveNext())
        {
            if (default(TSource) is null)
            {
                return default;
            }
            else
            {
                throw new InvalidOperationException("Sequence contains no elements");
            }
        }

        TSource value = e.Current;
        TKey key = keySelector(value);

        if (default(TKey) is null)
        {
            if (key == null)
            {
                TSource firstValue = value;

                do
                {
                    if (!e.MoveNext())
                    {
                        // All keys are null, surface the first element.
                        return firstValue;
                    }

                    value = e.Current;
                    key = keySelector(value);
                }
                while (key == null);
            }

            while (e.MoveNext())
            {
                TSource nextValue = e.Current;
                TKey nextKey = keySelector(nextValue);
                if (nextKey != null && comparer.Compare(nextKey, key) < 0)
                {
                    key = nextKey;
                    value = nextValue;
                }
            }
        }
        else
        {
            if (comparer == Comparer<TKey>.Default)
            {
                while (e.MoveNext())
                {
                    TSource nextValue = e.Current;
                    TKey nextKey = keySelector(nextValue);
                    if (Comparer<TKey>.Default.Compare(nextKey, key) < 0)
                    {
                        key = nextKey;
                        value = nextValue;
                    }
                }
            }
            else
            {
                while (e.MoveNext())
                {
                    TSource nextValue = e.Current;
                    TKey nextKey = keySelector(nextValue);
                    if (comparer.Compare(nextKey, key) < 0)
                    {
                        key = nextKey;
                        value = nextValue;
                    }
                }
            }
        }

        return value;
    }
}

// <auto-generated/>
#pragma warning disable
#nullable enable annotations
using System.Collections.Generic;
using System.Linq;

static partial class PolyfillExtensions
{
    public static IOrderedEnumerable<T> OrderDescending<T>(this IEnumerable<T> source)
    {
        return source.OrderByDescending(_ => _);
    }
}

// <auto-generated/>
#pragma warning disable
#nullable enable annotations
using System.Collections.Generic;
using System.Linq;

static partial class PolyfillExtensions
{
    public static IOrderedEnumerable<T> OrderDescending<T>(this IEnumerable<T> source, IComparer<T>? comparer)
    {
        return source.OrderByDescending(_ => _, comparer);
    }
}

// <auto-generated/>
#pragma warning disable
#nullable enable annotations
using System.Collections.Generic;
using System.Linq;

static partial class PolyfillExtensions
{
    public static IOrderedEnumerable<T> Order<T>(this IEnumerable<T> source)
    {
        return source.OrderBy(_ => _);
    }
}

// <auto-generated/>
#pragma warning disable
#nullable enable annotations
using System.Collections.Generic;
using System.Linq;

static partial class PolyfillExtensions
{
    public static IOrderedEnumerable<T> Order<T>(this IEnumerable<T> source, IComparer<T>? comparer)
    {
        return source.OrderBy(_ => _, comparer);
    }
}

// <auto-generated/>
#pragma warning disable
#nullable enable annotations
using System.Collections.Generic;

static partial class PolyfillExtensions
{
    public static HashSet<TSource> ToHashSet<TSource>(this IEnumerable<TSource> source)
        => source.ToHashSet(null);
}

// <auto-generated/>
#pragma warning disable
#nullable enable annotations
using System.Collections.Generic;

static partial class PolyfillExtensions
{
    public static HashSet<TSource> ToHashSet<TSource>(this IEnumerable<TSource> source, IEqualityComparer<TSource>? comparer)
        => new HashSet<TSource>(source, comparer);
}

// <auto-generated/>
#pragma warning disable
#nullable enable annotations
using System.Collections.Generic;
using System.Linq;

static partial class PolyfillExtensions
{
    public static IEnumerable<(TFirst left, TSecond right)> Zip<TFirst, TSecond>(this IEnumerable<TFirst> first, IEnumerable<TSecond> second)
    {
        return first.Zip(second, (x, y) => (x, y));
    }
}

// <auto-generated/>
#pragma warning disable
#nullable enable annotations
using System.IO;
using System.Net;
using System.Net.Http;
using System.Threading;

static partial class PolyfillExtensions
{
    public static void CopyTo(this HttpContent target, Stream stream, TransportContext? context, CancellationToken cancellationToken)
    {
        target.CopyToAsync(stream, context, cancellationToken).Wait(cancellationToken);
    }
}

// <auto-generated/>
#pragma warning disable
#nullable enable annotations
using System;
using System.IO;
using System.Net;
using System.Net.Http;
using System.Reflection;
using System.Threading;
using System.Threading.Tasks;

static partial class PolyfillExtensions
{
    public static async Task CopyToAsync(this HttpContent target, Stream stream, TransportContext? context, CancellationToken cancellationToken)
    {
        if (stream == null)
            throw new ArgumentNullException(nameof(stream));

        var method = typeof(HttpContent).GetMethod("SerializeToStreamAsync", 
            BindingFlags.NonPublic | BindingFlags.Instance, 
            binder: null, 
            new Type[] { typeof(Stream), typeof(TransportContext) },
            modifiers: null);

        await (Task)method!.Invoke(target, new object?[] { stream, context })!;
    }
}

// <auto-generated/>
#pragma warning disable
#nullable enable annotations
using System.IO;
using System.Net.Http;
using System.Threading;
using System.Threading.Tasks;

static partial class PolyfillExtensions
{
    public static Task CopyToAsync(this HttpContent target, Stream stream, CancellationToken cancellationToken) => target.CopyToAsync(stream, cancellationToken);
}

// <auto-generated/>
#pragma warning disable
#nullable enable annotations
using System.IO;
using System.Net.Http;
using System.Threading;

static partial class PolyfillExtensions
{
    public static Stream ReadAsStream(this HttpContent httpContent, CancellationToken cancellationToken)
    {
        var ms = new MemoryStream();
        httpContent.CopyTo(ms, context: null, cancellationToken);
        ms.Seek(0, SeekOrigin.Begin);
        return ms;
    }
}

// <auto-generated/>
#pragma warning disable
#nullable enable annotations
using System.IO;
using System.Net.Http;
using System.Threading;

static partial class PolyfillExtensions
{
    public static Stream ReadAsStream(this HttpContent httpContent)
    {
        return httpContent.ReadAsStream(CancellationToken.None);    
    }
}

// <auto-generated/>
#pragma warning disable
#nullable enable annotations
static partial class PolyfillExtensions
{
    public static bool Contains(this string target, char value)
    {
        return target.IndexOf(value) != -1;
    }
}

// <auto-generated/>
#pragma warning disable
#nullable enable annotations
static partial class PolyfillExtensions
{
    public static bool Contains(this string target, char value, System.StringComparison comparisonType)
    {
        return target.IndexOf(value, comparisonType) != -1;
    }
}

// <auto-generated/>
#pragma warning disable
#nullable enable annotations
static partial class PolyfillExtensions
{
    public static bool Contains(this string target, string value, System.StringComparison comparisonType)
    {
        return target.IndexOf(value, comparisonType) != -1;
    }
}

// <auto-generated/>
#pragma warning disable
#nullable enable annotations
static partial class PolyfillExtensions
{
    public static bool EndsWith(this string target, char value)
    {
        return target.Length > 0 && target[target.Length - 1] == value;
    }
}

// <auto-generated/>
#pragma warning disable
#nullable enable annotations
using System;

static partial class PolyfillExtensions
{
    public static int GetHashCode(this string target, StringComparison comparisonType)
    {
        return Helpers.FromComparison(comparisonType).GetHashCode(target);
    }
}

file class Helpers
{
    public static StringComparer FromComparison(StringComparison comparisonType) =>
        comparisonType switch
        {
            StringComparison.CurrentCulture => StringComparer.CurrentCulture,
            StringComparison.CurrentCultureIgnoreCase => StringComparer.CurrentCultureIgnoreCase,
            StringComparison.InvariantCulture => StringComparer.InvariantCulture,
            StringComparison.InvariantCultureIgnoreCase => StringComparer.InvariantCultureIgnoreCase,
            StringComparison.Ordinal => StringComparer.Ordinal,
            StringComparison.OrdinalIgnoreCase => StringComparer.OrdinalIgnoreCase,
            _ => throw new ArgumentException("The string comparison type passed in is currently not supported.", nameof(comparisonType)),
        };
}

// <auto-generated/>
#pragma warning disable
#nullable enable annotations
static partial class PolyfillExtensions
{
    public static int IndexOf(this string target, char value, System.StringComparison comparisonType)
    {
        return target.IndexOf(value.ToString(), comparisonType);
    }
}

// <auto-generated/>
#pragma warning disable
#nullable enable annotations
using System;
using System.Text;

static partial class PolyfillExtensions
{
    public static string Replace(this string target, string oldValue, string? newValue, StringComparison comparisonType)
    {
        if (oldValue == null)
            throw new ArgumentNullException(nameof(oldValue));

        if (oldValue == "")
            throw new ArgumentException("The value cannot be an empty string.", nameof(oldValue));

        var sb = new StringBuilder();

        var previousIndex = 0;
        while (target.IndexOf(oldValue, previousIndex, comparisonType) is var index and not -1)
        {
            sb.Append(target, previousIndex, index - previousIndex);
            sb.Append(newValue);
            previousIndex = index + oldValue.Length;
        }

        sb.Append(target, previousIndex, target.Length - previousIndex);
        return sb.ToString();
    }
}

// <auto-generated/>
#pragma warning disable
#nullable enable annotations
using System.Text;

static partial class PolyfillExtensions
{
    public static string ReplaceLineEndings(this string target, string replacementText)
    {
        var sb = new StringBuilder();

        var previousIndex = 0;
        while (target.IndexOfAny(Constants.NewLineChars, previousIndex) is var index and not -1)
        {
            sb.Append(target, previousIndex, index - previousIndex);
            sb.Append(replacementText);

            previousIndex = index + 1;
            if (target[index] == '\r' && index + 1 < target.Length && target[index + 1] == '\n')
            {
                previousIndex++;
            }
        }

        sb.Append(target, previousIndex, target.Length - previousIndex);
        return sb.ToString();
    }
}

file static class Constants
{
    public static readonly char[] NewLineChars = new char[] { '\n', '\r', '\f', '\u0085', '\u2028', '\u2029' };
}

// <auto-generated/>
#pragma warning disable
#nullable enable annotations
static partial class PolyfillExtensions
{
    public static string ReplaceLineEndings(this string target)
    {
        return target.ReplaceLineEndings(System.Environment.NewLine);
    }
}

// <auto-generated/>
#pragma warning disable
#nullable enable annotations
using System;

static partial class PolyfillExtensions
{
    public static string[] Split(this string target, char separator, int count, StringSplitOptions options = StringSplitOptions.None)
    {
        return target.Split(new char[] { separator }, count, options);
    }
}

// <auto-generated/>
#pragma warning disable
#nullable enable annotations
using System;

static partial class PolyfillExtensions
{
    public static string[] Split(this string target, char separator, StringSplitOptions options = StringSplitOptions.None)
    {
        return target.Split(new char[] { separator }, options);
    }
}

// <auto-generated/>
#pragma warning disable
#nullable enable annotations
static partial class PolyfillExtensions
{
    public static bool StartsWith(this string target, char value)
    {
        return target.Length > 0 && target[0] == value;
    }
}

// <auto-generated/>
#pragma warning disable
#nullable enable annotations
using System.Text;

static partial class PolyfillExtensions
{
    public static StringBuilder AppendJoin(this StringBuilder target, char separator, params object?[] values)
    {
        var first = true;
        foreach (var value in values)
        {
            if (!first)
            {
                target.Append(separator);
            }

            target.Append(value);
            first = false;
        }

        return target;
    }
}

// <auto-generated/>
#pragma warning disable
#nullable enable annotations
using System.Text;

static partial class PolyfillExtensions
{
    public static StringBuilder AppendJoin(this StringBuilder target, char separator, params string?[] values)
    {
        var first = true;
        foreach (var value in values)
        {
            if (!first)
            {
                target.Append(separator);
            }

            target.Append(value);
            first = false;
        }

        return target;
    }
}

// <auto-generated/>
#pragma warning disable
#nullable enable annotations
using System.Text;

static partial class PolyfillExtensions
{
    public static StringBuilder AppendJoin(this StringBuilder target, string? separator, params object?[] values)
    {
        var first = true;
        foreach (var value in values)
        {
            if (!first)
            {
                target.Append(separator);
            }

            target.Append(value);
            first = false;
        }

        return target;
    }
}

// <auto-generated/>
#pragma warning disable
#nullable enable annotations
using System.Text;

static partial class PolyfillExtensions
{
    public static StringBuilder AppendJoin(this StringBuilder target, string? separator, params string?[] values)
    {
        var first = true;
        foreach (var value in values)
        {
            if (!first)
            {
                target.Append(separator);
            }

            target.Append(value);
            first = false;
        }

        return target;
    }
}

// <auto-generated/>
#pragma warning disable
#nullable enable annotations
using System.Collections.Generic;
using System.Text;

static partial class PolyfillExtensions
{
    public static StringBuilder AppendJoin<T>(this StringBuilder target, char separator, IEnumerable<T> values)
    {
        var first = true;
        foreach (var value in values)
        {
            if (!first)
            {
                target.Append(separator);
            }

            target.Append(value);
            first = false;
        }

        return target;
    }
}

// <auto-generated/>
#pragma warning disable
#nullable enable annotations
using System.Collections.Generic;
using System.Text;

static partial class PolyfillExtensions
{
    public static StringBuilder AppendJoin<T>(this StringBuilder target, string? separator, IEnumerable<T> values)
    {
        var first = true;
        foreach (var value in values)
        {
            if (!first)
            {
                target.Append(separator);
            }

            target.Append(value);
            first = false;
        }

        return target;
    }
}

// <auto-generated/>
#pragma warning disable
#nullable enable annotations
using System.Threading;
using System.Threading.Tasks;

static partial class PolyfillExtensions
{
    public static Task CancelAsync(this CancellationTokenSource target)
    {
        target.Cancel();
        return Task.CompletedTask;
    }
}

// <auto-generated/>
#pragma warning disable
#nullable enable annotations
using System.Threading.Tasks;
using System.Threading;

static partial class PolyfillExtensions
{
    /// <summary>
    /// Gets a <see cref="Task{TResult}"/> that will complete when the <paramref name="task"/> completes or when the specified <paramref name="cancellationToken"/> has cancellation requested.
    /// </summary>
    /// <typeparam name="TResult">The type of the task result.</typeparam>
    /// <param name="task">The task to wait on for completion.</param>
    /// <param name="cancellationToken">The <see cref="CancellationToken"/> to monitor for a cancellation request.</param>
    /// <returns>The <see cref="Task{TResult}"/> representing the asynchronous wait.</returns>
    public static Task<TResult> WaitAsync<TResult>(this Task<TResult> task, CancellationToken cancellationToken)
    {
        if (task.IsCompleted || (!cancellationToken.CanBeCanceled))
        {
            return task;
        }

        if (cancellationToken.IsCancellationRequested)
        {
            return Task.FromCanceled<TResult>(cancellationToken);
        }

        return WaitTask.WaitTaskAsync(task, cancellationToken);
    }
}

file sealed class WaitTask
{
    public static async Task<TResult> WaitTaskAsync<TResult>(Task<TResult> task, CancellationToken cancellationToken)
    {
        var tcs = new TaskCompletionSource<TResult>(TaskCreationOptions.RunContinuationsAsynchronously);
        using (cancellationToken.Register(static state => ((TaskCompletionSource<TResult>)state!).SetCanceled(), tcs, false))
        {
            var t = await Task.WhenAny(task, tcs.Task).ConfigureAwait(false);
            return t.GetAwaiter().GetResult();
        }
    }
}

// <auto-generated/>
#pragma warning disable
#nullable enable annotations
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Diagnostics.CodeAnalysis;

namespace System.Collections.Generic
{
    /// <summary>
    ///  Represents a min priority queue.
    /// </summary>
    /// <typeparam name="TElement">Specifies the type of elements in the queue.</typeparam>
    /// <typeparam name="TPriority">Specifies the type of priority associated with enqueued elements.</typeparam>
    /// <remarks>
    ///  Implements an array-backed quaternary min-heap. Each element is enqueued with an associated priority
    ///  that determines the dequeue order: elements with the lowest priority get dequeued first.
    /// </remarks>
    [DebuggerDisplay("Count = {Count}")]
    internal class PriorityQueue<TElement, TPriority>
    {
        /// <summary>
        /// Represents an implicit heap-ordered complete d-ary tree, stored as an array.
        /// </summary>
        private (TElement Element, TPriority Priority)[] _nodes;

        /// <summary>
        /// Custom comparer used to order the heap.
        /// </summary>
        private readonly IComparer<TPriority>? _comparer;

        /// <summary>
        /// Lazily-initialized collection used to expose the contents of the queue.
        /// </summary>
        private UnorderedItemsCollection? _unorderedItems;

        /// <summary>
        /// The number of nodes in the heap.
        /// </summary>
        private int _size;

        /// <summary>
        /// Version updated on mutation to help validate enumerators operate on a consistent state.
        /// </summary>
        private int _version;

        /// <summary>
        /// Specifies the arity of the d-ary heap, which here is quaternary.
        /// It is assumed that this value is a power of 2.
        /// </summary>
        private const int Arity = 4;

        /// <summary>
        /// The binary logarithm of <see cref="Arity" />.
        /// </summary>
        private const int Log2Arity = 2;

#if DEBUG
        static PriorityQueue()
        {
            Debug.Assert(Log2Arity > 0 && Math.Pow(2, Log2Arity) == Arity);
        }
#endif

        /// <summary>
        ///  Initializes a new instance of the <see cref="PriorityQueue{TElement, TPriority}"/> class.
        /// </summary>
        public PriorityQueue()
        {
            _nodes = Array.Empty<(TElement, TPriority)>();
            _comparer = InitializeComparer(null);
        }

        /// <summary>
        ///  Initializes a new instance of the <see cref="PriorityQueue{TElement, TPriority}"/> class
        ///  with the specified initial capacity.
        /// </summary>
        /// <param name="initialCapacity">Initial capacity to allocate in the underlying heap array.</param>
        /// <exception cref="ArgumentOutOfRangeException">
        ///  The specified <paramref name="initialCapacity"/> was negative.
        /// </exception>
        public PriorityQueue(int initialCapacity)
            : this(initialCapacity, comparer: null)
        {
        }

        /// <summary>
        ///  Initializes a new instance of the <see cref="PriorityQueue{TElement, TPriority}"/> class
        ///  with the specified custom priority comparer.
        /// </summary>
        /// <param name="comparer">
        ///  Custom comparer dictating the ordering of elements.
        ///  Uses <see cref="Comparer{T}.Default" /> if the argument is <see langword="null"/>.
        /// </param>
        public PriorityQueue(IComparer<TPriority>? comparer)
        {
            _nodes = Array.Empty<(TElement, TPriority)>();
            _comparer = InitializeComparer(comparer);
        }

        /// <summary>
        ///  Initializes a new instance of the <see cref="PriorityQueue{TElement, TPriority}"/> class
        ///  with the specified initial capacity and custom priority comparer.
        /// </summary>
        /// <param name="initialCapacity">Initial capacity to allocate in the underlying heap array.</param>
        /// <param name="comparer">
        ///  Custom comparer dictating the ordering of elements.
        ///  Uses <see cref="Comparer{T}.Default" /> if the argument is <see langword="null"/>.
        /// </param>
        /// <exception cref="ArgumentOutOfRangeException">
        ///  The specified <paramref name="initialCapacity"/> was negative.
        /// </exception>
        public PriorityQueue(int initialCapacity, IComparer<TPriority>? comparer)
        {
            if (initialCapacity < 0)
                throw new ArgumentOutOfRangeException(nameof(initialCapacity), $"{nameof(initialCapacity)} ('{initialCapacity}') must be a non-negative value.");

            _nodes = new (TElement, TPriority)[initialCapacity];
            _comparer = InitializeComparer(comparer);
        }

        /// <summary>
        ///  Initializes a new instance of the <see cref="PriorityQueue{TElement, TPriority}"/> class
        ///  that is populated with the specified elements and priorities.
        /// </summary>
        /// <param name="items">The pairs of elements and priorities with which to populate the queue.</param>
        /// <exception cref="ArgumentNullException">
        ///  The specified <paramref name="items"/> argument was <see langword="null"/>.
        /// </exception>
        /// <remarks>
        ///  Constructs the heap using a heapify operation,
        ///  which is generally faster than enqueuing individual elements sequentially.
        /// </remarks>
        public PriorityQueue(IEnumerable<(TElement Element, TPriority Priority)> items)
            : this(items, comparer: null)
        {
        }

        /// <summary>
        ///  Initializes a new instance of the <see cref="PriorityQueue{TElement, TPriority}"/> class
        ///  that is populated with the specified elements and priorities,
        ///  and with the specified custom priority comparer.
        /// </summary>
        /// <param name="items">The pairs of elements and priorities with which to populate the queue.</param>
        /// <param name="comparer">
        ///  Custom comparer dictating the ordering of elements.
        ///  Uses <see cref="Comparer{T}.Default" /> if the argument is <see langword="null"/>.
        /// </param>
        /// <exception cref="ArgumentNullException">
        ///  The specified <paramref name="items"/> argument was <see langword="null"/>.
        /// </exception>
        /// <remarks>
        ///  Constructs the heap using a heapify operation,
        ///  which is generally faster than enqueuing individual elements sequentially.
        /// </remarks>
        public PriorityQueue(IEnumerable<(TElement Element, TPriority Priority)> items, IComparer<TPriority>? comparer)
        {
            if (items == null)
                throw new ArgumentNullException(nameof(items));

            _nodes = EnumerableHelpers.ToArray(items, out _size);
            _comparer = InitializeComparer(comparer);

            if (_size > 1)
            {
                Heapify();
            }
        }

        /// <summary>
        ///  Gets the number of elements contained in the <see cref="PriorityQueue{TElement, TPriority}"/>.
        /// </summary>
        public int Count => _size;

        /// <summary>
        ///  Gets the priority comparer used by the <see cref="PriorityQueue{TElement, TPriority}"/>.
        /// </summary>
        public IComparer<TPriority> Comparer => _comparer ?? Comparer<TPriority>.Default;

        /// <summary>
        ///  Gets a collection that enumerates the elements of the queue in an unordered manner.
        /// </summary>
        /// <remarks>
        ///  The enumeration does not order items by priority, since that would require N * log(N) time and N space.
        ///  Items are instead enumerated following the internal array heap layout.
        /// </remarks>
        public UnorderedItemsCollection UnorderedItems => _unorderedItems ??= new UnorderedItemsCollection(this);

        /// <summary>
        ///  Adds the specified element with associated priority to the <see cref="PriorityQueue{TElement, TPriority}"/>.
        /// </summary>
        /// <param name="element">The element to add to the <see cref="PriorityQueue{TElement, TPriority}"/>.</param>
        /// <param name="priority">The priority with which to associate the new element.</param>
        public void Enqueue(TElement element, TPriority priority)
        {
            // Virtually add the node at the end of the underlying array.
            // Note that the node being enqueued does not need to be physically placed
            // there at this point, as such an assignment would be redundant.

            int currentSize = _size;
            _version++;

            if (_nodes.Length == currentSize)
            {
                Grow(currentSize + 1);
            }

            _size = currentSize + 1;

            if (_comparer == null)
            {
                MoveUpDefaultComparer((element, priority), currentSize);
            }
            else
            {
                MoveUpCustomComparer((element, priority), currentSize);
            }
        }

        /// <summary>
        ///  Returns the minimal element from the <see cref="PriorityQueue{TElement, TPriority}"/> without removing it.
        /// </summary>
        /// <exception cref="InvalidOperationException">The <see cref="PriorityQueue{TElement, TPriority}"/> is empty.</exception>
        /// <returns>The minimal element of the <see cref="PriorityQueue{TElement, TPriority}"/>.</returns>
        public TElement Peek()
        {
            if (_size == 0)
            {
                throw new InvalidOperationException("Queue empty.");
            }

            return _nodes[0].Element;
        }

        /// <summary>
        ///  Removes and returns the minimal element from the <see cref="PriorityQueue{TElement, TPriority}"/>.
        /// </summary>
        /// <exception cref="InvalidOperationException">The queue is empty.</exception>
        /// <returns>The minimal element of the <see cref="PriorityQueue{TElement, TPriority}"/>.</returns>
        public TElement Dequeue()
        {
            if (_size == 0)
            {
                throw new InvalidOperationException("Queue empty.");
            }

            TElement element = _nodes[0].Element;
            RemoveRootNode();
            return element;
        }

        /// <summary>
        ///  Removes the minimal element and then immediately adds the specified element with associated priority to the <see cref="PriorityQueue{TElement, TPriority}"/>,
        /// </summary>
        /// <param name="element">The element to add to the <see cref="PriorityQueue{TElement, TPriority}"/>.</param>
        /// <param name="priority">The priority with which to associate the new element.</param>
        /// <exception cref="InvalidOperationException">The queue is empty.</exception>
        /// <returns>The minimal element removed before performing the enqueue operation.</returns>
        /// <remarks>
        ///  Implements an extract-then-insert heap operation that is generally more efficient
        ///  than sequencing Dequeue and Enqueue operations: in the worst case scenario only one
        ///  shift-down operation is required.
        /// </remarks>
        public TElement DequeueEnqueue(TElement element, TPriority priority)
        {
            if (_size == 0)
            {
                throw new InvalidOperationException("Queue empty.");
            }

            (TElement Element, TPriority Priority) root = _nodes[0];

            if (_comparer == null)
            {
                if (Comparer<TPriority>.Default.Compare(priority, root.Priority) > 0)
                {
                    MoveDownDefaultComparer((element, priority), 0);
                }
                else
                {
                    _nodes[0] = (element, priority);
                }
            }
            else
            {
                if (_comparer.Compare(priority, root.Priority) > 0)
                {
                    MoveDownCustomComparer((element, priority), 0);
                }
                else
                {
                    _nodes[0] = (element, priority);
                }
            }

            _version++;
            return root.Element;
        }

        /// <summary>
        ///  Removes the minimal element from the <see cref="PriorityQueue{TElement, TPriority}"/>,
        ///  and copies it to the <paramref name="element"/> parameter,
        ///  and its associated priority to the <paramref name="priority"/> parameter.
        /// </summary>
        /// <param name="element">The removed element.</param>
        /// <param name="priority">The priority associated with the removed element.</param>
        /// <returns>
        ///  <see langword="true"/> if the element is successfully removed;
        ///  <see langword="false"/> if the <see cref="PriorityQueue{TElement, TPriority}"/> is empty.
        /// </returns>
        public bool TryDequeue([MaybeNullWhen(false)] out TElement element, [MaybeNullWhen(false)] out TPriority priority)
        {
            if (_size != 0)
            {
                (element, priority) = _nodes[0];
                RemoveRootNode();
                return true;
            }

            element = default;
            priority = default;
            return false;
        }

        /// <summary>
        ///  Returns a value that indicates whether there is a minimal element in the <see cref="PriorityQueue{TElement, TPriority}"/>,
        ///  and if one is present, copies it to the <paramref name="element"/> parameter,
        ///  and its associated priority to the <paramref name="priority"/> parameter.
        ///  The element is not removed from the <see cref="PriorityQueue{TElement, TPriority}"/>.
        /// </summary>
        /// <param name="element">The minimal element in the queue.</param>
        /// <param name="priority">The priority associated with the minimal element.</param>
        /// <returns>
        ///  <see langword="true"/> if there is a minimal element;
        ///  <see langword="false"/> if the <see cref="PriorityQueue{TElement, TPriority}"/> is empty.
        /// </returns>
        public bool TryPeek([MaybeNullWhen(false)] out TElement element, [MaybeNullWhen(false)] out TPriority priority)
        {
            if (_size != 0)
            {
                (element, priority) = _nodes[0];
                return true;
            }

            element = default;
            priority = default;
            return false;
        }

        /// <summary>
        ///  Adds the specified element with associated priority to the <see cref="PriorityQueue{TElement, TPriority}"/>,
        ///  and immediately removes the minimal element, returning the result.
        /// </summary>
        /// <param name="element">The element to add to the <see cref="PriorityQueue{TElement, TPriority}"/>.</param>
        /// <param name="priority">The priority with which to associate the new element.</param>
        /// <returns>The minimal element removed after the enqueue operation.</returns>
        /// <remarks>
        ///  Implements an insert-then-extract heap operation that is generally more efficient
        ///  than sequencing Enqueue and Dequeue operations: in the worst case scenario only one
        ///  shift-down operation is required.
        /// </remarks>
        public TElement EnqueueDequeue(TElement element, TPriority priority)
        {
            if (_size != 0)
            {
                (TElement Element, TPriority Priority) root = _nodes[0];

                if (_comparer == null)
                {
                    if (Comparer<TPriority>.Default.Compare(priority, root.Priority) > 0)
                    {
                        MoveDownDefaultComparer((element, priority), 0);
                        _version++;
                        return root.Element;
                    }
                }
                else
                {
                    if (_comparer.Compare(priority, root.Priority) > 0)
                    {
                        MoveDownCustomComparer((element, priority), 0);
                        _version++;
                        return root.Element;
                    }
                }
            }

            return element;
        }

        /// <summary>
        ///  Enqueues a sequence of element/priority pairs to the <see cref="PriorityQueue{TElement, TPriority}"/>.
        /// </summary>
        /// <param name="items">The pairs of elements and priorities to add to the queue.</param>
        /// <exception cref="ArgumentNullException">
        ///  The specified <paramref name="items"/> argument was <see langword="null"/>.
        /// </exception>
        public void EnqueueRange(IEnumerable<(TElement Element, TPriority Priority)> items)
        {
            if (items == null)
                throw new ArgumentNullException(nameof(items));

            int count = 0;
            var collection = items as ICollection<(TElement Element, TPriority Priority)>;
            if (collection is not null && (count = collection.Count) > _nodes.Length - _size)
            {
                Grow(checked(_size + count));
            }

            if (_size == 0)
            {
                // build using Heapify() if the queue is empty.

                if (collection is not null)
                {
                    collection.CopyTo(_nodes, 0);
                    _size = count;
                }
                else
                {
                    int i = 0;
                    (TElement, TPriority)[] nodes = _nodes;
                    foreach ((TElement element, TPriority priority) in items)
                    {
                        if (nodes.Length == i)
                        {
                            Grow(i + 1);
                            nodes = _nodes;
                        }

                        nodes[i++] = (element, priority);
                    }

                    _size = i;
                }

                _version++;

                if (_size > 1)
                {
                    Heapify();
                }
            }
            else
            {
                foreach ((TElement element, TPriority priority) in items)
                {
                    Enqueue(element, priority);
                }
            }
        }

        /// <summary>
        ///  Enqueues a sequence of elements pairs to the <see cref="PriorityQueue{TElement, TPriority}"/>,
        ///  all associated with the specified priority.
        /// </summary>
        /// <param name="elements">The elements to add to the queue.</param>
        /// <param name="priority">The priority to associate with the new elements.</param>
        /// <exception cref="ArgumentNullException">
        ///  The specified <paramref name="elements"/> argument was <see langword="null"/>.
        /// </exception>
        public void EnqueueRange(IEnumerable<TElement> elements, TPriority priority)
        {
            if (elements == null)
                throw new ArgumentNullException(nameof(elements));

            int count;
            if (elements is ICollection<TElement> collection &&
                (count = collection.Count) > _nodes.Length - _size)
            {
                Grow(checked(_size + count));
            }

            if (_size == 0)
            {
                // build using Heapify() if the queue is empty.

                int i = 0;
                (TElement, TPriority)[] nodes = _nodes;
                foreach (TElement element in elements)
                {
                    if (nodes.Length == i)
                    {
                        Grow(i + 1);
                        nodes = _nodes;
                    }

                    nodes[i++] = (element, priority);
                }

                _size = i;
                _version++;

                if (i > 1)
                {
                    Heapify();
                }
            }
            else
            {
                foreach (TElement element in elements)
                {
                    Enqueue(element, priority);
                }
            }
        }

        /// <summary>
        ///  Removes all items from the <see cref="PriorityQueue{TElement, TPriority}"/>.
        /// </summary>
        public void Clear()
        {
            Array.Clear(_nodes, 0, _size);
            _size = 0;
            _version++;
        }

        /// <summary>
        ///  Ensures that the <see cref="PriorityQueue{TElement, TPriority}"/> can hold up to
        ///  <paramref name="capacity"/> items without further expansion of its backing storage.
        /// </summary>
        /// <param name="capacity">The minimum capacity to be used.</param>
        /// <exception cref="ArgumentOutOfRangeException">
        ///  The specified <paramref name="capacity"/> is negative.
        /// </exception>
        /// <returns>The current capacity of the <see cref="PriorityQueue{TElement, TPriority}"/>.</returns>
        public int EnsureCapacity(int capacity)
        {
            if (capacity < 0)
                throw new ArgumentOutOfRangeException(nameof(capacity), $"{nameof(capacity)} ('{capacity}') must be a non-negative value.");

            if (_nodes.Length < capacity)
            {
                Grow(capacity);
                _version++;
            }

            return _nodes.Length;
        }

        /// <summary>
        ///  Sets the capacity to the actual number of items in the <see cref="PriorityQueue{TElement, TPriority}"/>,
        ///  if that is less than 90 percent of current capacity.
        /// </summary>
        /// <remarks>
        ///  This method can be used to minimize a collection's memory overhead
        ///  if no new elements will be added to the collection.
        /// </remarks>
        public void TrimExcess()
        {
            int threshold = (int)(_nodes.Length * 0.9);
            if (_size < threshold)
            {
                Array.Resize(ref _nodes, _size);
                _version++;
            }
        }

        /// <summary>
        /// Grows the priority queue to match the specified min capacity.
        /// </summary>
        private void Grow(int minCapacity)
        {
            Debug.Assert(_nodes.Length < minCapacity);

            const int GrowFactor = 2;
            const int MinimumGrow = 4;

            int newcapacity = GrowFactor * _nodes.Length;

            // Allow the queue to grow to maximum possible capacity (~2G elements) before encountering overflow.
            // Note that this check works even when _nodes.Length overflowed thanks to the (uint) cast
            if ((uint)newcapacity > ArrayHelpers.MaxLength) newcapacity = ArrayHelpers.MaxLength;

            // Ensure minimum growth is respected.
            newcapacity = Math.Max(newcapacity, _nodes.Length + MinimumGrow);

            // If the computed capacity is still less than specified, set to the original argument.
            // Capacities exceeding Array.MaxLength will be surfaced as OutOfMemoryException by Array.Resize.
            if (newcapacity < minCapacity) newcapacity = minCapacity;

            Array.Resize(ref _nodes, newcapacity);
        }

        /// <summary>
        /// Removes the node from the root of the heap
        /// </summary>
        private void RemoveRootNode()
        {
            int lastNodeIndex = --_size;
            _version++;

            if (lastNodeIndex > 0)
            {
                (TElement Element, TPriority Priority) lastNode = _nodes[lastNodeIndex];
                if (_comparer == null)
                {
                    MoveDownDefaultComparer(lastNode, 0);
                }
                else
                {
                    MoveDownCustomComparer(lastNode, 0);
                }
            }

            _nodes[lastNodeIndex] = default;
        }

        /// <summary>
        /// Gets the index of an element's parent.
        /// </summary>
        private static int GetParentIndex(int index) => (index - 1) >> Log2Arity;

        /// <summary>
        /// Gets the index of the first child of an element.
        /// </summary>
        private static int GetFirstChildIndex(int index) => (index << Log2Arity) + 1;

        /// <summary>
        /// Converts an unordered list into a heap.
        /// </summary>
        private void Heapify()
        {
            // Leaves of the tree are in fact 1-element heaps, for which there
            // is no need to correct them. The heap property needs to be restored
            // only for higher nodes, starting from the first node that has children.
            // It is the parent of the very last element in the array.

            (TElement Element, TPriority Priority)[] nodes = _nodes;
            int lastParentWithChildren = GetParentIndex(_size - 1);

            if (_comparer == null)
            {
                for (int index = lastParentWithChildren; index >= 0; --index)
                {
                    MoveDownDefaultComparer(nodes[index], index);
                }
            }
            else
            {
                for (int index = lastParentWithChildren; index >= 0; --index)
                {
                    MoveDownCustomComparer(nodes[index], index);
                }
            }
        }

        /// <summary>
        /// Moves a node up in the tree to restore heap order.
        /// </summary>
        private void MoveUpDefaultComparer((TElement Element, TPriority Priority) node, int nodeIndex)
        {
            // Instead of swapping items all the way to the root, we will perform
            // a similar optimization as in the insertion sort.

            Debug.Assert(_comparer is null);
            Debug.Assert(0 <= nodeIndex && nodeIndex < _size);

            (TElement Element, TPriority Priority)[] nodes = _nodes;

            while (nodeIndex > 0)
            {
                int parentIndex = GetParentIndex(nodeIndex);
                (TElement Element, TPriority Priority) parent = nodes[parentIndex];

                if (Comparer<TPriority>.Default.Compare(node.Priority, parent.Priority) < 0)
                {
                    nodes[nodeIndex] = parent;
                    nodeIndex = parentIndex;
                }
                else
                {
                    break;
                }
            }

            nodes[nodeIndex] = node;
        }

        /// <summary>
        /// Moves a node up in the tree to restore heap order.
        /// </summary>
        private void MoveUpCustomComparer((TElement Element, TPriority Priority) node, int nodeIndex)
        {
            // Instead of swapping items all the way to the root, we will perform
            // a similar optimization as in the insertion sort.

            Debug.Assert(_comparer is not null);
            Debug.Assert(0 <= nodeIndex && nodeIndex < _size);

Meziantou.Polyfill by Gérald Barré

Nuget / site data​

Details​

Info​

Original Readme​

Meziantou.Polyfill

How to add a new polyfill​

About​

How to use​

Example ( source csproj, source files )​

Generated Files​