Wednesday, July 1, 2009

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

1 comment:

Chris128 said...

Useful stuff! Wish I had found this yesterday when I was learning how to use the IComparer interface