How to Implement IComparable<T> Interface in Base and Derived Classes

by Zoran Horvat
May 10, 2013

Generic IComparable<T> interface was introduced in .NET Framework 2.0 to allow comparison between instances of a type. Interface defines only one method, CompareTo(T), which receives an instance against which current object should be compared. CompareTo method returns Int32 indicating the order between this instance and the argument: negative return value means that this instance is less than the argument; zero indicates that two instances are equal; positive value indicates that this instance is greater than the argument.

CompareTo method is not meant to be called directly in code. It is rather provided for collections that needed it to distinguish and sort contained items.

Implementing IComparable<T> in a given class is in most of the cases straight-forward. However, this task must be done with caution in cases when another class is going to be derived from a class that implements IComparable<T>. In this article, we are going to analyze conditions that should be satisfied by a proper implementation of IComparable<T>. Guidelines that will be given should be accepted as a pattern to follow in custom implementations. Additional suggestions will also be given regarding members that operate in coordination with IComparable, such as overrides of Equals and GetHashCode methods.

Mathematical Background of Comparison

In order to define precisely what a proper implementation of CompareTo(T) method does, we will start from a mathematical definition of total order. In simple terms, total order is a binary relation on a set of values which defines an ordering of items in the set. This relation is typically denoted as ≤ to resemble arithmetic comparison, although it doesn't necessarily apply to sets of numbers. It applies to any set of objects that can be ordered: strings can be ordered lexicographically; raw materials can be ordered by density, electrical conductivity, thermal capacity, or combination of these; pianos can be ordered by subjective quality attributed by a master player. Possibilities are endless, but in any case total order relation must possess three qualities. It must be:

• Transitive - If a ≤ b and b ≤ c, then a ≤ c; this rule should be intuitively clear.
• Antisymmetric - If a ≤ b and b ≤ a then a = b; this rule says that two values cannot precede each other, or otherwise they are the same value.
• Total - For any two values a and b, either a ≤ b or b ≤ a (or both, if a and b are equal); this rule declares that all values in the set can be compared against each other.

These rules can be easily translated into terms of IComparable<T> interface. Transitivity simply states that CompareTo method should return consistent results when applied to related objects. Antisymmetry deals with results returned by a.CompareTo(b) and b.CompareTo(a). If both calls return the same value, then a and b must be the same. Totality rule states that there are no left-over objects that cannot be compared against other objects.

Specifically, null value for reference types must be taken into account when implementing CompareTo method. One possibility is to consider null to be less than any instance, meaning that CompareTo returns positive value when null is passed as an argument. Forgetting this special case breaks the totality rule because null is a valid value for a reference type variable.

In addition to null, totality rule requests all objects of the generic type from the interface declaration to be comparable with no exceptions. These rules must be preserved when implementing CompareTo method or otherwise some awkward situations might occur, generally leading to misbehaving code, or at least code that acts differently than user might expect in some cases.

Simple Implementation of CompareTo

Below is a very simple implementation of the IComparable<T> interface. This implementation will only serve a purpose of being a starting point, rather than finished solution. We are dealing with pianos, each of them having a mark assigned by the specialist. Comparison between pianos is performed solely by the mark.

public class Piano : IComparable<Piano>
{

    public float Mark { get; set; }

    public int CompareTo(Piano other)
    {
        // The very basic implementation of CompareTo

        if (object.ReferenceEquals(other, null))
            return 1;   // All instances are greater than null

        return Mark.CompareTo(other.Mark);

    }

}

Observe that this implementation follows the three rules of total order. It is transitive, meaning that if we have three pianos, second being better than the first, third being better than the second, then consequently third will be better than the first one. Antisymmetry is also preserved: should two pianos return same value from their CompareTo methods, then it's obvious that the value returned would be 0 and two pianos would have the same mark assigned. Finally, totality rule is preserved because we are free to compare any two instances of the Piano class, even the null value, to obtain a valid comparison result.

But this implementation is far from perfect. It fails when derived class is introduced, as will be shown in the following section.

Problems with Simple Implementation and Derived Class

Suppose that we wish to add a derived class to our system:

public class Piano : IComparable<Piano>
{

    public float Mark { get; set; }

    public int CompareTo(Piano other)
    {
        // The very basic implementation of CompareTo

        if (object.ReferenceEquals(other, null))
            return 1;   // All instances are greater than null

        return Mark.CompareTo(other.Mark);

    }

}

public class GrandPiano: Piano
{
    public string Producer { get; set; }
}

The GrandPiano class inherits Mark property from its base class, but also inherits implementation of the IComparable<Piano> interface - it is quite legal to compare regular piano with grand piano. We can even try it:

Piano p = new Piano()
{
    Mark = 3.2F
};

GrandPiano gp = new GrandPiano()
{
    Mark = 3.2F,
    Producer = "Schimmel"
};

Console.WriteLine(p.CompareTo(gp));

This code prints value 0, indicating that two objects are equal. But they are not - GrandPiano instance has an additional property (Producer) which was not taken into account and that property would cause the comparison result to be quite different, and certainly different than zero.

Correct Implementation of IComparable<T> Interface

In previous section we have seen some of the problems that occur when base class implements CompareTo method without taking care of its derived classes. First of all, there is no trace of polymorphism in this implementation. Derived class has no way to add logic to CompareTo method in order to incorporate new properties into comparison. In particular, GrandPiano class adds Producer property, but that property plays no role in comparison, although it might be relevant.

First step towards polymorphic implementation of CompareTo method is to make it virtual. That would allow derived classes to add more conditions before deciding on comparison result. However, that is only half of the solution. The other problem occurs when instances of different classes are compared, like in this example:

Piano p = new Piano()
{
    Mark = 3.2F
};

GrandPiano gp = new GrandPiano()
{
    Mark = 3.2F,
    Producer = "Schimmel"
};

int res1 = gp.CompareTo(p);
int res2 = p.CompareTo(gp);

Knowing that total order is antisymmetric, we conclude that correct implementation of the CompareTo method in base and derived class should return opposite values in the last two lines of the example. But it is not quite obvious what values those should be. Is GrandPiano instance greater than the base class instance? Or is it the opposite? It should be obvious that these two instances are not equal, because GrandPiano instance introduces a value for the piano producer which clearly distinguishes it from plain piano.

To find out the solution to this issue, we will take a look at the memory layout of the two objects. First object is instance of the base class Piano, and it only contains the Mark property. Second instance is of derived class GrandPiano and it has two properties: Mark and Producer.

For more information about memory layout of derived objects, please refer to Lesson 2 - Class Inheritance .

From picture above it looks like base instance is supposed to be sorted before derived instance, simply because it is shorter and all common fields are equal. This situation carries a strong resemblance with dictionaries, in which lexicographic ordering is applied to words. When two words begin the same, but one is longer than the other, then shorter word comes first in the sort order. If we take a look at a common thesaurus, this is what we would discover under the letter A:

            
a
a bit
a bit much
a lot
a-bomb
a-bomb shelter
aardvark
abandon
abandoned
abandoned town
abandonment
...
                
    

The same logic could be applied to comparing derived classes with base classes. If base part of the two objects is the same, then "shorter" type is the smaller one. In other words, when base part is equal, then base instance is less than the derived instance. Even if derived type has not added any relevant fields that would affect the comparison, it would be very complicated for the base instance to pass control to the derived instance when its CompareTo method is called. It is rather safe to consistently declare all derived instances greater than base instances, provided that base parts of compared objects are equal.

The situation is complicated even further if another class is derived from the base class. In that situation there is no way to compare instances of two distinct derived classes, because each is free to add unrelated properties that affect comparison, but which cannot be compared against each other. To resolve the issue, we compare base parts of the two distinct derived instances. If base parts are equal then we simply need to devise a consistent comparison rule that will always return the same result. One simple solution is just to compare full names of the two derived types. With this solution, all instances of one derived class will be strictly less than all instances of another derived class whenever their base parts are equal.

IComparable<T> Implementation Pattern

In previous sections we have identified goals that should be achieved by a proper implementation of CompareTo method. Now we are ready to give guidelines to implementers. Most important guideline is that comparison of values and of types should be separated into two methods. CompareTo method then calls value comparison, while types comparison is used only if value comparison returns zero - type information is used only to break the tie between base and derived instances.

Here is the comprehensive list of elements to include in implementation of CompareTo method in the base and derived classes:

• Implement protected virtual method CompareToValues which only compares values that are in common to this instance and instance passed as an argument. Base implementation compares only the relevant base fields. Return value of this method has the same meaning as return value of CompareTo method.
• Override CompareToValues in derived class. Overridden method should call base implementation and only if it returns zero should it compare additional fields defined by the derived class. This means that derived implementation is used only to break the ties among derived instances that have equal base fields. Breaking this rule would hurt the antisymmetry and transitivity principles.
• Implement CompareTypes helper method in the base class to perform comparison among instance types. If two instances are equal by value, then their types are compared. Base type is always less than derived type. Two unrelated types (i.e. distinct derived types) are compared by their full name to ensure consistency. CompareTypes method returns Int32 result with same meaning as for CompareTo method. This rule is important for preserving the antisymmetry principle.
• Implement CompareTo method in the base class to call CompareToValues; on zero result, tie would be broken by calling the CompareTypes helper method.
• Never throw exceptions from CompareTo or CompareToValues methods. Inability to perform comparison means that order introduced by the CompareTo method is not total.
• Make sure that null argument is treated correctly. Ensure that CompareToValues(null) returns positive value, indicating that all objects are greater than null.

Demonstration

In this section we will demonstrate the IComparable<T> implementation pattern on the piano class hierarchy, which was previously introduced. Base class (Piano) compares instances by their marks, which are floating point values assigned by the specialist. Derived class GrandPiano adds one more property (Producer), which is used in comparison between grand pianos when they have the same mark. Finally, another derived class is added, called PrivatePiano, which tracks pianos in private property and only adds one property, Owner, which tracks name of the piano owner. Not much of the logic, but quite sufficient to make comparison difficult.

Table below shows how the rules listed in the previous section apply to this hierarchy of classes.

When rules are applied in this way, all three qualities of total order - transitivity, antisymmetry and totality - are preserved. Below is the source code which implements these rules.

public class Piano : IComparable<Piano>
{

    public float Mark { get; set; }

    public int CompareTo(Piano other)
    {

        int result = CompareToValues(other);

        // If comparison based solely on values
        // returns zero, indicating that two instances
        // are equal in those fields they have in common,
        // only then we break the tie by comparing
        // data types of the two instances.
        if (result == 0)
            result = CompareTypes(other);

        return result;

    }

    protected virtual int CompareToValues(Piano other)
    {

        if (object.ReferenceEquals(other, null))
            return 1;   // All instances are greater than null

        // Base class simply compares Mark properties
        return Mark.CompareTo(other.Mark);

    }

    protected int CompareTypes(Piano other)
    {

        // Base type is considered less than derived type
        // when two instances have the same values of
        // base fields.

        // Instances of two distinct derived types are
        // ordered by comparing full names of their
        // types when base fields are equal.
        // This is consistent comparison rule for all
        // instances of the two derived types.

        int result = 0;

        Type thisType = this.GetType();
        Type otherType = other.GetType();

        if (otherType.IsSubclassOf(thisType))
            result = -1;    // other is subclass of this class
        else if (thisType.IsSubclassOf(otherType))
            result = 1;     // this is subclass of other class
        else if (thisType != otherType)
            result = thisType.FullName.CompareTo(otherType.FullName);
                            // cut the tie with a test that returns
                            // the same value for all objects

        return result;

    }

    public override string ToString()
    {
        return string.Format("Mark={0:0.0}, Piano", Mark);
    }

}

public class GrandPiano: Piano
{

    public string Producer { get; set; }

    protected override int CompareToValues(Piano other)
    {
        // Derived class must override this method if it has
        // added fields that affect comparison result.
        // New fields are taken into account only if base class
        // finds that base fields are equal.

        int result = base.CompareToValues(other);

        if (result == 0 && other is GrandPiano)
        {

            GrandPiano gp = (GrandPiano)other;
            string thisProducer = Producer ?? string.Empty;
            string otherProducer = gp.Producer ?? string.Empty;

            result = thisProducer.CompareTo(otherProducer);

        }

        return result;

    }

    public override string ToString()
    {
        return string.Format("Mark={0:0.0}, Producer={1}, GrandPiano",
                                Mark, Producer);
    }

}

public class PrivatePiano : Piano
{

    public string Owner { get; set; }

    protected override int CompareToValues(Piano other)
    {
        // Derived class must override this method if it has
        // added fields that affect comparison result.
        // New fields are taken into account only if base class
        // finds that base fields are equal.

        int result = base.CompareToValues(other);

        if (result == 0 && other is PrivatePiano)
        {

            PrivatePiano pp = (PrivatePiano)other;
            string thisOwner = Owner ?? string.Empty;
            string otherOwner = pp.Owner ?? string.Empty;

            result = thisOwner.CompareTo(otherOwner);

        }

        return result;

    }

    public override string ToString()
    {
        return string.Format("Mark={0:0.0}, Owner={1}, PrivatePiano",
                                Mark, Owner);
    }

}

From this source code we can see that most of the work is done in the base class, which is always a positive fact. Derived classes are in charge of their own properties. Should a class add relevant properties to its definition, it should override the CompareToValues method and perform comparison of the newly added properties where applicable. The only thing derived classes should take care of is to test own properties only if base implementation has signaled that inherited properties are equal in this instance and instance passed as an argument.

We can use these classes to construct a small collection of pianos and then use generic Array.Sort<Piano> method to sort it. This method will detect that Piano implements generic IComparable<Piano> interface and then it will naturally rely on implementation of CompareTo(Piano) method to order items in the array. Here is the code:

Piano[] pianos = new Piano[]
{
    new Piano() { Mark = 3.2F },
    new GrandPiano() { Mark = 3.2F,
                        Producer = "Petzold" },
    new Piano() { Mark = 3.4F },
    new PrivatePiano() { Mark = 3.2F,
                            Owner = "Joe" },
    new GrandPiano() { Mark = 3.2F,
                        Producer = "Schimmel" },
    new PrivatePiano() { Mark = 3.4F,
                            Owner = "Henry" }
};

Array.Sort<Piano>(pianos);

for (int i = 0; i < pianos.Length; i++)
    Console.WriteLine(pianos[i]);

This code produces output:

            
Mark=3.2, Piano
Mark=3.2, Producer=Petzold, GrandPiano
Mark=3.2, Producer=Schimmel, GrandPiano
Mark=3.2, Owner=Joe, PrivatePiano
Mark=3.4, Piano
Mark=3.4, Owner=Henry, PrivatePiano
                
    

It is obvious that items have been sorted by value of the Mark property. When mark is equal on two items, then additional field is used when items are of the same type. Otherwise, type resolution scheme is applied, so that Piano is the smallest, GrandPiano follows and PrivatePiano type is considered the largest.

In the following sections we will briefly explain changes that must be made to other parts of the class implementing IComparable<T> to ensure that it behaves consistently.

Overriding Equals and GetHashCode in Classes that Implement IComparable<T>

When a class implements IComparable<T>, it should also override Equals method in order to be consistent. Default implementation of Equals method in reference types simply compares instances by reference, not by value. This would then be in contradiction with result returned by the CompareTo method - two instances that are different by reference (Equals returns false), might be equal by value (CompareTo returns zero). In order to avoid such awkward behavior, class should definitely override the Equals method so that it routes the call to the CompareTo method.

Off course, when Equals method is overridden, class would also have to override the GetHashCode method, so that it works consistently with Equals - two instances that are equal in terms that Equals method returns true, must return the same value from their GetHashCode methods.

For more information about overriding these methods, please refer to article How to Override Equals and GetHashCode Methods in Base and Derived Classes .

Here are our piano classes embellished with Equals and GetHashCode overrides:

public class Piano : IComparable<Piano>
{
    ...
    public override bool Equals(object obj)
    {
        return (CompareTo(obj as Piano) == 0);
    }

    public override int GetHashCode()
    {
        return Mark.GetHashCode();
    }

}

public class GrandPiano: Piano
{
    ...
    public override int GetHashCode()
    {
        string prod = Producer ?? string.Empty;
        return base.GetHashCode() ^ prod.GetHashCode();
    }

}

public class PrivatePiano : Piano
{
    ...
    public override int GetHashCode()
    {
        string owner = Owner ?? string.Empty;
        return base.GetHashCode() ^ owner.GetHashCode();
    }

}

Note that derived classes do not have to override Equals method - all the logic has already been provided by the base class. It is only important for them to keep the GetHashCode method consistent by adding the fingerprint of their own properties.

In the previous article ( How to Override Equals and GetHashCode Methods in Base and Derived Classes ) we have explained that Equals method should return false when two instances compared for equality are of different type. In this article we have reached the same conclusion the other way around. CompareTo method will never return zero for instances of distinct types, meaning that implementation of Equals override will work correctly even when delegated to the CompareTo method.

Implementing General IComparable Interface

Once that class has implemented generic IComparable<T> interface, it might be a good idea to support the general IComparable interface as well. It is in fact like implementing IComparable<Object>. There are several ups and downs of this practice, which we will briefly cover in this section.

First of all, the question why would we implement general IComparable interface when we have already implemented a strong typed one? The answer is simple - to widen the range of possible usages of the class. Comparison logic is already there, but there are situations in which underlying collection cannot find the route to the strongly typed CompareTo method.

Second important question is how to compare pianos with non-piano objects? The answer is - there is no way to accomplish such comparison. General IComparable interface does not implement total order relation, but only the partial order among those objects that are pianos in this case. Generic IComparable<T> interface implementation was not supposed to throw exceptions because all classes derived from Piano are still describing pianos, so why would we not compare them. Now that we are stepping out of the world of pianos, we cannot ensure that comparison will be possible and hence we forbid it by throwing an exception as soon as CompareTo(Object) method smells a non-piano object.

Here is the implementation of general IComparable interface on a class that already implements generic IComparable<T> interface:

public class Piano : IComparable<Piano>, IComparable
{
    ...
    public int CompareTo(object obj)
    {

        if (obj != null && !(obj is Piano))
            throw new ArgumentException("Object must be of type Piano.");

        return CompareTo(obj as Piano);

    }
}

This simple implementation is inherited by derived classes so they do not have to add anything to their implementation.

---