BinarySearch based on values of other types

[virzak]

Background and Motivation

Following classes are present in the library - think of features of the road:

public class MyBase
{
    public MyBase(Guid id, double distance)
    {
        Distance = distance;
        Id = id;
    }
    public Guid Id { get; }
    public double Distance { get; }
}

public class MyDerivedN : MyBase
{
  ...
}

Some other class contains Arrays of the derived classes

public class Road 
{
  MyDerivedBearCrossing[] BearCrossings
  MyDerivedBridge[] Bridges
  MyDerivedGasStation[] GasStations
}

The code to find a previous feature of the road looks as follows:

int FindPrevious(double distance, MyBase[] array)
{
    var compareFeature = new MyBase(Guid.Empty, distance);
    var index = Array.BinarySearch(array, compareFeature, new MyBaseComparer());

    if (index < 0)
        index = ~index - 1;

    return index;
}

// Additionally a Comparer is needed:

class MyBaseComparer : IComparer<MyBase>
{
    public int Compare([AllowNull] MyBasex, [AllowNull] MyBasey)
    {
        if (x == y)
        {
            return 0;
        }
        if (x == null)
        {
            return -1;
        }
        if (y == null)
        {
            return 1;
        }
        return x.Distance.CompareTo(y.Distance);
    }
}

There is currently no way to use any other type with generics. MyBase, must be the type of the value to compare to, thus it can't be made abstract.

Closest existing non generic implementation is: System.Array.BinarySearch(Array, Object, IComparer)

It requires IComparer

class MyBaseComparer : System.Collections.IComparer
{
    public int Compare(object? x, object? y)
    {
        if (x == y)
        {
            return 0;
        }
        if (x == null)
        {
            return -1;
        }
        if (y == null)
        {
            return 1;
        }

        var @base = x as MyBase ?? throw new ArgumentException(...);
        var compareTo = y as double? ?? throw new ArgumentException(...);
        return @base.CompareTo(compareTo);
    }
}

Proposed API

namespace System
{
    public abstract class Array : ICollection, IEnumerable, IList, IStructuralComparable, IStructuralEquatable, ICloneable
    {
+        public static int BinarySearch<T, TOther>(T[] array, TOther value) where T : IComparable<TOther>
    }
}

Usage Examples

Because the comparison is mostly done by Distance, IComparable can be implemented. Also, since the BinarySearch takes a double, there is no need to instantiate MyBase and it is marked abstract

abstract public record MyBase : IComparable<double>
{
    protected MyBase(Guid id, double distance)
    {
        Distance = distance;
        Id = id;
    }
    public Guid Id { get; }
    public double Distance { get; }

    public int CompareTo(double other)
    {
        return Distance.CompareTo(other);
    }
}

int FindPrevious(double distance, MyBase[] array)
{
    var index = Array.BinarySearch(array, distance);

    if (index < 0)
        index = ~index - 1;

    return index;
}

Alternative / Complimentary Design

A more involved design would be to introduce:

public interface IComparer<in T, in TOther>
{
   int Compare(T? x, TOther? y);
}

and use is in System.Array

namespace System
{
    public abstract class Array : ICollection, IEnumerable, IList, IStructuralComparable, IStructuralEquatable, ICloneable
    {
+        public static int BinarySearch<T, TOther>(T[] array, TOther value, IComparer<T, TOther>? comparer)
    }
}

Ideally both could be implemented.

Risks

No known risks

[dotnet-issue-labeler[bot]]

I couldn't figure out the best area label to add to this issue. If you have write-permissions please help me learn by adding exactly one area label.

[sdrapkin]

IComparable<T> Notes-to-Implementers say to use the type implementing the interface as T (ie. for an IComparable<T> to itself). I haven't seen examples in .NET of types implementing IComparable<some other type>. This is likely because if our type T implements IComparable<TOther>, it places the onus on TOther to implement IComparable<T> for things to make sense, which is not something we can guarantee.

Having said that, System.MemoryExtensions.BinarySearch methods implement a slightly different flavor, where it is the other type (ie. comparable) that needs to implement IComparable<T> instead of T implementing IComparable<TOther>. This extended BinarySearch might suit your needs if you can wrap your T[] as Span<T>.

Example:

abstract public record MyBase(Guid Id, double Distance) : IComparable<double>
{
    public int CompareTo(double other) => Distance.CompareTo(other);
}

public record Bridge(Guid Id, double Distance) : MyBase(Id, Distance) { }

readonly struct MyBaseComparableOnDistance : IComparable<MyBase> // struct in hopes of GC-efficiency
{
    readonly double _distance;
    public MyBaseComparableOnDistance(double distance) => _distance = distance;
    public int CompareTo(MyBase other) => other is null ? 1 : _distance.CompareTo(other.Distance);
}

static int FindPrevious<T>(double distance, T[] array) where T : MyBase
{
    var comparable = new MyBaseComparableOnDistance(distance);
    return MemoryExtensions.BinarySearch<T>(array, comparable); // still boxed by interface cast :(
}

void Main()
{
    var bridges = new Bridge[]
    {
        new(Guid.NewGuid(), 1),
        new(Guid.NewGuid(), 3),
        new(Guid.NewGuid(), 5),
    };

    var result = FindPrevious(5, bridges);
    Console.WriteLine(result);
}