views:

139

answers:

2

In .NET the BinarySearch algorithm (in Lists, Arrays, etc.) appears to fail if the items you are trying to search inherit from an IComparable instead of implementing it directly:

List<B> foo = new List<B>(); // B inherits from A, which implements IComparable<A>
foo.Add(new B());
foo.BinarySearch(new B());   // InvalidOperationException, "Failed to compare two elements in the array."

Where:

public abstract class A : IComparable<A>
{
    public int x;

    public int CompareTo(A other)
    {
        return x.CompareTo(other.x);
    }
}

public class B : A {}

Is there a way around this? Implementing CompareTo(B other) in class B doesn't seem to work.

+5  A: 

The documentation makes this quite clear:

checks whether type T implements the IComparable generic interface and uses that implementation, if available. If not, Comparer.Default checks whether type T implements the IComparable interface. If type T does not implement either interface, Comparer.Default throws an InvalidOperationException.

So, a simple solution is to implement the non-generic interface IComparable.
Adding CompareTo(B other) will work for you, as long as you also implement IComparable<B> - you probably forgot that bit.

An interesting solution is to compile the code using C# 4, where it runs without any errors. C# 4 introduces Generic Covariance: public interface IComparable<in T> vs public interface IComparable<T>, and the posted code works as expected.

Kobi
Contravariance FTW!
Eric Lippert
+1  A: 

Right, so the problem is it tries to see if class B implements IComparable<B>, which it doesn't, because it actually implements IComparable<A>, then tries IComparable then gives up. As Kobi pointed out, implementing non-generic IComparable will solve this problem.

Igor Zevaka