API proposal: Sequence comparer

[jnm2]

There is no .NET API to sort sequences lexicographically. The closest thing I know of is Enumerable.SequenceEqual which reports elementwise equality but not order.

I've implemented one-off array/enumerable comparers in enough projects that this last time I figured I should propose it.

Usage example

var sortedPaths = path.OrderBy(
    path => path.GetSegmentNames(),
    Comparer.Sequence(StringComparer.OrdinalIgnoreCase));

Proposal

It should be a generic method on a non-generic type for usability (CA1000).

If an element comparer instance is not specified, Comparer<T>.Default should be used for consistency with other APIs.

IComparer<> is contravariant, so the returned comparer will be usable for any sequence of reference types implementing IEnumerable<T>.

The returned comparer type should likely not be a class that also implements IEqualityComparer because GetHashCode would have to be implemented as 0 if the user-specified element comparer cannot be cast to IEqualityComparer<T>.

namespace System.Collections
{
    public sealed class Comparer : IComparer, ISerializable
    {
+       public static IComparer<IEnumerable<T>> Sequence<T>(
+           IComparer<T>? elementComparer = null);

        // No other static members are declared by Comparer
    }
}

Draft implementation

Click to expand

private sealed class SequenceComparer<T> : IComparer<IEnumerable<T>>
{
    private readonly IComparer<T> elementComparer;

    public SequenceComparer(IComparer<T> elementComparer)
    {
        this.elementComparer = elementComparer;
    }

    public int Compare(IEnumerable<T>? x, IEnumerable<T>? y)
    {
        if (x == y) return 0;
        if (x is null) return -1; // x < y
        if (y is null) return 1; // x > y

        using var xEnumerator = x.GetEnumerator();
        using var yEnumerator = y.GetEnumerator();

        while (xEnumerator.MoveNext())
        {
            if (!yEnumerator.MoveNext()) return 1; // x > y

            var elementComparison = elementComparer.Compare(xEnumerator.Current, yEnumerator.Current);
            if (elementComparison != 0) return elementComparison;
        }

        return yEnumerator.MoveNext()
            ? -1 // x < y
            : 0; // x == y
    }
}

[Dotnet-GitSync-Bot]

I couldn't figure out the best area label to add to this issue. Please help me learn by adding exactly one area label.

[GSPP]

I have needed this a bunch of times for equality (IEqualityComparer<IEnumerable<T>>). Particularly often, I had the need to use byte arrays as keys in a hash table.

[svick]

@GSPP As proposed, this issue is only about IComparer<IEnumerable<T>>. Are you saying it should be expanded to also include IEqualityComparer<IEnumerable<T>>?

[GSPP]

It seems like a good idea to me to do both.

[eiriktsarpalis]

This seems reasonable, but is Comparer the right class to host this method? Perhaps it should go in Enumerable?

[jnm2]

@eiriktsarpalis I'd like to add more static methods to Comparer to create comparers, e.g. #33877 or one I didn't file yet to create comparers for tuples. (When a tuple containing a string is used as a dictionary key, it's not as simple as it should be to get an ordinal-ignore-case comparison.)