About Me

Hello, I'm an eclectic software professional working with enterprise software at SAP. This blog only contains my personal views, thoughts and opinions. It is not endorsed by SAP nor does it constitute any official communication of SAP.

Wednesday, April 21, 2010

A more understandable IComparable

"Any fool can write code that a computer can understand. Good programmers write code that humans can understand." - Martin Fowler

In the .NET framework the IComparable<T> interface is used to compare values:

public interface IComparable<T> {
  int CompareTo(T other);
}

The comparison is done with the CompareTo method. It returns zero if the current object is equal to the passed in parameter; a negative number if it's less than the parameter; and a positive number if it's greater than it. That's a very non-intuitive return value, reminiscent of the C strcmp function. I know that this scheme is already ingrained in our brains, but it creates code that's not directly decipherable:

static int BinarySearch<T>(IList<T> list, T target) where T : IComparable<T> {
  if (list == null) throw new ArgumentNullException("list");
  int lower = 0;
  int upper = list.Count - 1;
  while (lower <= upper) {
    int middle = lower + (upper - lower) / 2;
    int compare = target.CompareTo(list[middle]);
    if (compare == 0) return middle;
    if (compare < 0) upper = middle - 1;
    else lower = middle + 1;
  }
  return -1;
}

...

  int[] mySortedArray = ...

  int indexOfTheAnswer = BinarySearch(mySortedArray, 42);

(Note: this is just an example, there're already binary searches implementations in classes Array and List<T>.)

Wouldn't it be nicer to use the comparison operators instead of the clumsy CompareTo method? C# doesn't support extension operators, so in order to provide the operators to any IComparable<T>, a wrapper type must be used:

public class ComparableWithOperators<T> where T : IComparable<T> {
  T _comparable;
  public ComparableWithOperators(T comparable) {
    if (comparable == null) throw new ArgumentNullException("comparable");
    _comparable = comparable;
  }

  public static implicit operator ComparableWithOperators<T>(T comparable) {
    return new ComparableWithOperators<T>(comparable);
  }
  public static bool operator <(ComparableWithOperators<T> left, ComparableWithOperators<T> right) {
    return left._comparable.CompareTo(right._comparable) < 0;
  }
  public static bool operator >(ComparableWithOperators<T> left, ComparableWithOperators<T> right) {
    return left._comparable.CompareTo(right._comparable) > 0;
  }
  public static bool operator <=(ComparableWithOperators<T> left, ComparableWithOperators<T> right) {
    return left._comparable.CompareTo(right._comparable) <= 0;
  }
  public static bool operator >=(ComparableWithOperators<T> left, ComparableWithOperators<T> right) {
    return left._comparable.CompareTo(right._comparable) >= 0;
  }
  public static bool operator ==(ComparableWithOperators<T> left, ComparableWithOperators<T> right) {
    return left._comparable.CompareTo(right._comparable) == 0;
  }
  public static bool operator !=(ComparableWithOperators<T> left, ComparableWithOperators<T> right) {
    return left._comparable.CompareTo(right._comparable) != 0;
  }

  ...
}

This class implements the comparison operators for itself, and since there's also an implicit cast operator from a T, which is constrained to be an IComparable<T>, it can also compare itself to any IComparable<T>. So, the binary search example can now be changed to this:

static int BinarySearch<T>(IList<T> list, ComparableWithOperators<T> target) where T : IComparable<T> {
  if (list == null) throw new ArgumentNullException("list");
  int lower = 0;
  int upper = list.Count - 1;
  while (lower <= upper) {
    int middle = lower + (upper - lower) / 2;
    var candidate = list[middle];
    if (target == candidate) return middle;
    if (target < candidate) upper = middle - 1;
    else lower = middle + 1;
  }
  return -1;
}

...

  int[] mySortedArray = ...

  int indexOfTheAnswer = BinarySearch<int>(mySortedArray, 42);

But now the caller must provide the type parameter to the method, because the compiler's type inference can't figure it out. Also, sometimes you already have an IComparable<T>, and to use the operators in the same context, you'd need to convert it to the wrapper class:

IComparable<T> comparable = ...
ComparableWithOperators<T> comparableWithOperators = comparable;

To make this statement read better, a converter extension method can be used:

public static class ComparableExtensions {
  public static ComparableWithOperators<T> WithOperators<T>(this T self) where T : IComparable<T> {
    if (self == null) throw new ArgumentNullException();
    return self;
  }
}

Now the statement will read:

IComparable<T> comparable = ...
var comparableWithOperators = comparable.WithOperators();

And the binary search can be implemented like this:

static int BinarySearch<T>(IList<T> list, T target) where T : IComparable<T> {
  if (list == null) throw new ArgumentNullException("list");
  int lower = 0;
  int upper = list.Count - 1;
  while (lower <= upper) {
    int middle = lower + (upper - lower) / 2;
    var candidate = list[middle].WithOperators();
    if (target == candidate) return middle;
    if (target < candidate) upper = middle - 1;
    else lower = middle + 1;
  }
  return -1;
}

This solution also alleviates the requirements for new classes that implement IComparable<T>. They don't need to provide the comparison operators by themselves anymore, which would add a lot of boilerplate code. The same logic can be used to tackle the IEquatable<T> interface as well.

Note that F# has a (meta) generic type constraint, named comparison, which gives us the desired syntax out of the box:

let BinarySearch<'a when 'a : comparison>(list: IList<'a>, target: 'a) =
  if list = null then raise(ArgumentNullException("list"))
  let rec Loop(lower, upper) =
    if (lower <= upper) then
      let middle = lower + (upper - lower) / 2
      let candidate = list.[middle]
      if (candidate = target) then middle
      elif (target < candidate) then Loop(lower, middle - 1)
      else Loop(middle + 1, upper)
    else -1
  Loop(0, list.Count - 1)

No comments:

Post a Comment