Sorting Arrays and Collections (Part 2)

Part 1 here

In the previous instalment we discussed how to use the IComparable interface to facilitate automatic sorting of arrays and collections. This time we will look at the IComparer interface and how it can be used to sort objects that may or may not be inherently comparable.

Like IComparable,the IComparer interface comes in both standard and generic flavours. Normally you would implement the generic version, although there may be instances where you need to implement the standard version. Sorting the items in a ListView is one such instance.

Again like IComparable, the IComparer interface declares only a single method. Where the IComparable.CompareTo method takes a single object and compares it to the current instance, the IComparer.Compare method takes two objects and compares them to each other. As an example, let's consider the case where you have a collection of strings that you want to sort by length instead of alphabetically. In this case we cannot rely on the IComparable implementation of the String class itself so we must define our own comparison, which we can do by implementing the IComparer interface:

C#

public class StringLengthComparer : IComparer<string>

{

    public int Compare(string x, string y)

     {

         return x.Length.CompareTo(y.Length);

     }

}

VB

Public Class StringLengthComparer

    Implements IComparer(Of String)

    Public Function Compare(ByVal x As String, _

                            ByVal y As String) As Integer _

    Implements IComparer(Of String).Compare

        Return x.Length.CompareTo(y.Length)

    End Function

End Class

Our StringLengthComparer.Compare method will take two Strings and return a result that indicates their relative order based on their Lengths. Notice that we are still making use of the IComparable.CompareTo method, which we know is a good convention to follow. In this case we are comparing the two Length properties, which are type Int32. The Int32 structure implements the IComparable interface so we should make use of it.

We can now perform a custom sort of a list of strings like so:

C#

List<string> strings = new List<string>();

strings.Add("The longest of all");

strings.Add("Short");

strings.Add("Even longer");

strings.Add("Longer");

Console.WriteLine("Before sorting:");

foreach (string str in strings)

{

     Console.WriteLine(str);

}

strings.Sort(new StringLengthComparer());

Console.WriteLine("After sorting:");

foreach (string str in strings)

{

     Console.WriteLine(str);

}

VB

Dim strings As New List(Of String)

strings.Add("The longest of all")

strings.Add("Short")

strings.Add("Even longer")

strings.Add("Longer")

Console.WriteLine("Before sorting:")

For Each str As String In strings

    Console.WriteLine(str)

Next

strings.Sort(New StringLengthComparer)

Console.WriteLine("After sorting:")

For Each str As String In strings

    Console.WriteLine(str)

Next

In this case we pass an instance of our StringLengthComparer class as an argument when we call Sort and all comparisons will be done using the Compare method of our class instead of the CompareTo methods of the objects in the list. Sorting arrays is much the same except, again, the Array.Sort method is static/Shared:

C#

string[] strings = {"The longest of all",

                    "Short",

                    "Even longer",

                    "Longer"};

Console.WriteLine("Before sorting:");

foreach (string str in strings)

{

    Console.WriteLine(str);

}

Array.Sort(strings, new StringLengthComparer());

Console.WriteLine("After sorting:");

foreach (string str in strings)

{

    Console.WriteLine(str);

}

VB

Dim strings As String() = {"The longest of all", _

                           "Short", _

                           "Even longer", _

                           "Longer"}

Console.WriteLine("Before sorting:")

For Each str As String In strings

    Console.WriteLine(str)

Next

Array.Sort(strings, New StringLengthComparer)

Console.WriteLine("After sorting:")

For Each str As String In strings

    Console.WriteLine(str)

Next

Now, our StringLengthComparer class is relatively simple. It only knows how to compare strings in one way. What if we want to be able compare objects in various ways depending on the circumstances? We can certainly do that with a class that implements IComparer. There’s no limit to the complexity of the class, as long as it provides the functionality defined by the interface. For example, let’s consider our Person class from the previous instalment:

C#

public class Person : IComparable, IComparable<Person>

{

     private string _lastName;

     private string _firstName;

     public string LastName

     {

        get { return this._lastName; }

         set { this._lastName = value; }

     }

     public string FirstName

     {

         get { return this._firstName; }

         set { this._firstName = value; }

     }

     public Person(string firstName, string lastName)

     {

         this._firstName = firstName;

         this._lastName = lastName;

     }

     public int CompareTo(object obj)

     {

         return this.CompareTo((Person) obj);

     }

     public int CompareTo(Person other)

     {

        // Compare by LastName by default.

        int result = this.LastName.CompareTo(other.LastName);

         // If LastNames are the same...

         if (result == 0)

        {

            // ...compare by FirstName.

            result = this.FirstName.CompareTo(this.FirstName);

        }

        return result;

     }

}

VB

Public Class Person

    Implements IComparable, IComparable(Of Person)

    Private _lastName As String

    Private _firstName As String

    Public Property FirstName() As String

        Get

            Return Me._firstName

        End Get

        Set(ByVal value As String)

            Me._firstName = value

        End Set

    End Property

    Public Property LastName() As String

        Get

            Return Me._lastName

        End Get

        Set(ByVal value As String)

            Me._lastName = value

        End Set

    End Property

    Public Sub New(ByVal firstName As String, _

                   ByVal lastName As String)

        Me._firstName = firstName

        Me._lastName = lastName

    End Sub

    Public Function CompareTo(ByVal obj As Object) As Integer _

    Implements System.IComparable.CompareTo

        Return Me.CompareTo(DirectCast(obj, Person))

    End Function

    Public Function CompareTo(ByVal other As Person) As Integer _

    Implements System.IComparable(Of Person).CompareTo

        'Compare by LastName by default.

        Dim result As Integer = Me.LastName.CompareTo(other.LastName)

        'If LastNames are the same...

        If result = 0 Then

            '...compare by FirstName.

            result = Me.FirstName.CompareTo(other.FirstName)

        End If

        Return result

    End Function

End Class

What if we want to be able to sort a list of Person objects by either FirstName or LastName? The Person class already implements the IComparable interface, which implementation compares by LastName then FirstName. As such, we could just provide an implementation of IComparer that compares by FirstName then LastName. That way we could either accept the default comparison or use our IComparer implementation, depending on the circumstances. For consistency though, a better idea might be to provide an IComparer implementation that can compare in either way and then use that all the time:

C#

public class PersonComparer : IComparer<Person>

{

    public enum ComparisonProperty

    {

        FirstName,

        LastName

    }

    private readonly ComparisonProperty _comparisonProperty;

    public PersonComparer(ComparisonProperty comparisonProperty)

    {

        this._comparisonProperty = comparisonProperty;

    }

    public int Compare(Person x, Person y)

    {

        int result = 0;

        switch (this._comparisonProperty)

        {

            case ComparisonProperty.FirstName:

                result = this.CompareByFirstName(x, y);

                break;

            case ComparisonProperty.LastName:

                result = this.CompareByLastName(x, y);

                break;

        }

        return result;

    }

    private int CompareByFirstName(Person x, Person y)

    {

        // Compare by FirstName by default.

        int result = x.FirstName.CompareTo(y.FirstName);

        // If FirstNames are the same...

        if (result == 0)

        {

            // ...compare by LastName.

            result = x.LastName.CompareTo(y.LastName);

        }

        return result;

    }

    private int CompareByLastName(Person x, Person y)

    {

        // Compare by LastName by default.

        int result = x.LastName.CompareTo(y.LastName);

        // If LastNames are the same...

        if (result == 0)

        {

            // ...compare by FirstName.

            result = x.FirstName.CompareTo(y.FirstName);

        }

        return result;

    }

}

VB

Public Class PersonComparer

    Implements IComparer(Of Person)

    Public Enum ComparisonProperty

        FirstName

        LastName

    End Enum

    Private ReadOnly _comparisonProperty As ComparisonProperty

    Public Sub New(ByVal comparisonProperty As ComparisonProperty)

        Me._comparisonProperty = comparisonProperty

    End Sub

    Public Function Compare(ByVal x As Person, _

                            ByVal y As Person) As Integer _

    Implements IComparer(Of Person).Compare

        Dim result As Integer

        Select Case Me._comparisonProperty

            Case ComparisonProperty.FirstName

                result = Me.CompareByFirstName(x, y)

            Case ComparisonProperty.LastName

                result = Me.CompareByLastName(x, y)

        End Select

        Return result

    End Function

    Private Function CompareByFirstName(ByVal x As Person, _

                                        ByVal y As Person) As Integer

        'Compare by FirstName by default.

        Dim result As Integer = x.FirstName.CompareTo(y.FirstName)

        'If FirstNames are the same...

        If result = 0 Then

            '...compare by LastName.

            result = x.LastName.CompareTo(y.LastName)

        End If

        Return result

    End Function

    Private Function CompareByLastName(ByVal x As Person, _

                                       ByVal y As Person) As Integer

        'Compare by LastName by default.

        Dim result As Integer = x.LastName.CompareTo(y.LastName)

        'If LastNames are the same...

        If result = 0 Then

            '...compare by FirstName.

            result = x.FirstName.CompareTo(y.FirstName)

        End If

        Return result

    End Function

End Class

Note that the CompareByLastName method compares in exactly the same way as the Person.CompareTo method. As such, we could have made use of that existing functionality in our PersonComparer class:

C#

private int CompareByLastName(Person x, Person y)

{

    return x.CompareTo(y);

}

VB

Private Function CompareByLastName(ByVal x As Person, _

                                   ByVal y As Person) As Integer

    Return x.CompareTo(y)

End Function

This does save us duplicating some code but it also makes the implementation of the PersonComparer class more reliant on the implementation of the Person class. By implementing our CompareByLastName method exactly as we want it, we allow the IComparable implementation of the Person class to change without changing the behaviour of our PersonComparer class.

We can now put our PersonComparer class to work in sorting a list of Person objects by either LastName or by FirstName:

C#

List<Person> people = new List<Person>();

people.Add(new Person("Mary", "Smith"));

people.Add(new Person("John", "Williams"));

people.Add(new Person("John", "Smith"));

people.Add(new Person("Andrew", "Baxter"));

Console.WriteLine("Before sorting:");

foreach (Person person in people)

{

    Console.WriteLine(string.Format("{0}, {1}",

                                    person.LastName,

                                    person.FirstName));

}

people.Sort(new PersonComparer(PersonComparer.ComparisonProperty.LastName));

Console.WriteLine("After sorting by LastName:");

foreach (Person person in people)

{

    Console.WriteLine(string.Format("{0}, {1}",

                                    person.LastName,

                                    person.FirstName));

}

people.Sort(new PersonComparer(PersonComparer.ComparisonProperty.FirstName));

Console.WriteLine("After sorting by FirstName:");

foreach (Person person in people)

{

    Console.WriteLine(string.Format("{0} {1}",

                                    person.FirstName,

                                    person.LastName));

}

VB

Dim people As New List(Of Person)

people.Add(New Person("Mary", "Smith"))

people.Add(New Person("John", "Williams"))

people.Add(New Person("John", "Smith"))

people.Add(New Person("Andrew", "Baxter"))

Console.WriteLine("Before sorting:")

For Each person As Person In people

    Console.WriteLine(String.Format("{0}, {1}", _

                                    person.LastName, _

                                    person.FirstName))

Next

people.Sort(New PersonComparer(PersonComparer.ComparisonProperty.LastName))

Console.WriteLine("After sorting by LastName:")

For Each person As Person In people

    Console.WriteLine(String.Format("{0}, {1}", _

                                    person.LastName, _

                                    person.FirstName))

Next

people.Sort(New PersonComparer(PersonComparer.ComparisonProperty.FirstName))

Console.WriteLine("After sorting by FirstName:")

For Each person As Person In people

    Console.WriteLine(String.Format("{0} {1}", _

                                    person.FirstName, _

                                    person.LastName))

Next

As I said earlier, you can make your class as complex as you like, comparing objects in numerous different ways involving as many properties as you want.

Now, implementing the IComparer interface in a new class is a good option if you want to be able to compare instances of a type in multiple different ways and/or in multiple different places. If you only need to sort in one place, or at least only in one code file, then there is a slightly easier way. We’ll look at that in the next instalment.

Part 3 here