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.)

[eiriktsarpalis]

It would probably though need to live in Comparer<T>, since the untyped variant lives in the System.Collections namespace?

[jnm2]

I proposed it on System.Collections.Comparer so that the generic type argument can be inferred in C#. The same thing will happen when I propose a method returning IComparer<(T1, T2)>.

[eiriktsarpalis]

That's a reasonable consideration, but there is the precedent of Comparer<T>.Default (which could have been Comparer.Default<T>()). I'm concerned we'd be violating convention (as well as spreading similar members across two separate namespaces).

[jnm2]

In the case of Comparer<T>.Default(), inference wasn't a consideration because the method has no parameters. You're right though, it might be worse long-term to split methods between the two classes in order to avoid explicitly specifying type parameters.

Really quick, taking an example API I haven't proposed but intend to, is it even possible to place it in Comparer<T>? If not, that should steer us in a direction for all such future APIs, right?

// Usage: Comparer.Create(StringComparer.OrdinalIgnoreCase, EqualityComparer<int>.Default)
namespace System.Collections
{
    public static class Comparer
    {
+       public static IComparer<(T1, T2)> Create<T1, T2>(IComparer<T1> first, IComparer<T2> second);
    }
}

// Usage: Comparer<???>.Create(StringComparer.OrdinalIgnoreCase, EqualityComparer<int>.Default)
namespace System.Collections.Generic
{
    public static class Comparer<T>
    {
+       public static IComparer<(T1, T2)> Create<T1, T2>(IComparer<T1> first, IComparer<T2> second);
    }
}

[eiriktsarpalis]

That's a good point. We could perhaps add a new static class in System.Collections.Generic that hosts the methods (e.g. something like ComparerHelper).

[eiriktsarpalis]

Echoing #44796, do you think we should also add comparer definitions for array and memory types?

[jnm2]

Yes, I was thinking that anything IEnumerable would be supported by default. Memory<T> would need to be marshaled to IEnumerable<T> first. Instead of returning IComparer<IEnumerable<T>>, perhaps a new SequenceComparer<T> class could be returned which would implement both IComparer<IEnumerable<T>> and IComparer<Memory<T>>.

[eiriktsarpalis]

Triage: would like to see this added, however it is not clear if the non-generic System.Collections.Comparer class is the right location to host this (and similar) methods.