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)

Comments

Post a Comment

Popular posts from this blog

The Acyclic Visitor Pattern

Knock knock The visitor design pattern is a way to add new operations to a hierarchy of classes without having to change the hierarchy itself. For example, with a simple hierarchy of fruits, you can have an IFruitVisitor interface that operates on the different classes in the hierarchy (in C#): interface IFruitVisitor { void Visit(Apple apple); void Visit(Grape grape); } The hierarchy classes then accept the visitor and fulfil the double-dispatching necessary to call the right Visit method: abstract class Fruit { public abstract void Accept(IFruitVisitor visitor); } class Apple : Fruit { public override void Accept(IFruitVisitor visitor) { visitor.Visit(this); } } class Grape : Fruit { public int NumberOfGrapes { get; set; } public override void Accept(IFruitVisitor visitor) { visitor.Visit(this); } } Note how each Accept method looks the same but is actually dispatching to a different method in the visitor ( Visit(Apple) and Visit(Grape) ).
Read more

C# Mixins With State

With the C# quasi-mixin pattern , one of the biggest limitations is that the mixins can't introduce state to a class. An alternative was for the mixin interface to require the composing classes to implement a property that the mixin would use as its own, as demonstrated in this example . In the .NET Framework 4.0, the ConditionalWeakTable<TKey, TValue> class can be used to associate arbitrary state to any instance. It's thread safe and it keeps a dictionary of weak references from the target instance to its associated state. If a target instance has no references outside the conditional weak table, then it can be reclaimed by the garbage collector. When that happens, its entry in the table is removed. This makes it possible for a mixin-like class to maintain state for the instances it extends. Let's look at a mixin for a message container: public enum MessageType { Error, Warning, Info } public class Message { public readonly MessageType Type;
Read more

Some OO Design

"The critical design tool for software development is a mind well educated in design principles. It is not the UML or any other technology." - Craig Larman I've recently found the following interview question on stackoverflow : Basic sales tax is applicable at a rate of 10% on all goods, except books, food, and medical products that are exempt. Import duty is an additional sales tax applicable on all imported goods at a rate of 5%, with no exemptions. When I purchase items I receive a receipt which lists the name of all the items and their price (including tax), finishing with the total cost of the items, and the total amounts of sales taxes paid. The rounding rules for sales tax are that for a tax rate of n%, a shelf price of p contains (np/100 rounded up to the nearest 0.05) amount of sales tax. This is a very familiar example that can be used as a really good gauge of various software development skills. There are many different ways to solve this problem.
Read more