Object Sorting

• Download source files - 6.5 KB
• Download demo project - 22.37 KB

Introduction

Sorting is a relatively simple task, yet it seems to be redundant and time consuming to implement for objects using the .NET programming languages. This article will demonstrate a single approach that will allow any list of like objects to be sorted, regardless of the sort complexity.

Background

When .NET was first released, an old colleague of mine had challenged me to come up with a way to create an all encompassing sort routine. At the time I thought it was impossible, but as I learned more about Reflection, it became clear that it was indeed possible. I eventually came up with a solution that has served me well for several years.

Unfortunately, the solution was dependent upon the use of Reflection and late-binding techniques that were not nearly as performant as they could be. After reviewing the new features made available in the .NET Framework 2.0 and the future features set forth in the LINQ Project, I knew there must be a way to refactor the sorting technique I'd been using into a more efficient form.

How It Works

This sorting technique breaks down into two simple classes:

• ObjectComparer
• ComparerList

The first challenge was to come up with a way to automatically compare two objects. Unfortunately, for two objects to be able to compare themselves, they must implement the IComparable and/or IComparable<T> interfaces. Since a developer would have to repeatedly implement these interfaces, that approach will not do.

Realizing that an object must implement the appropriate interface to be comparable, it suddenly occurred to me that all of the intrinsic objects implement this interface. Further still, when comparing two objects, 99% of the time we are evaluating the value of an object member that is one of these types. In the remaining cases, the object to be compared must implement the appropriate interface to be comparable.

Since all comparisons must be able to be performed using the IComparable<T> interface, it was easy to create a generic class with a constraint specifying that the type supplied must support the required interface. The work of performing the comparison is then delegated to the interface implementation. However, there are two additional cases that I accounted for that a standard comparer does not. First, I made a special case for strings by allowing the comparer to specify whether it should ignore casing. This value is ignored if the values being compared are not strings. Second, I added a property that allows the comparer to negatively assert, or inverse, its evaluation. Sort algorithms are typically performed in ascending order, but by allowing the result of the comparison to be reversed, a sort can be performed in descending order.

The next challenge was to provide the comparer with the path to the member from the object whose value is to be compared. In my previous implementation this was performed by passing a string containing the binding path to the field or property to be sorted. Although that works, the approach has many shortcomings such as a lack of type safety, performance (because Reflection must be used), and developer error from typographical mistakes because features such as IntelliSense are not available.

To solve all of these problems, we are able to leverage the power of generics in conjunction with delegates. We start by defining the delegate U YieldMember<T,U>( T item ). The types for T and U are supplied by the implementation of the ObjectComparer class, where T is the type of object being compared and U is the type of value being compared. In addition, the introduction of anonymous methods provides the perfect solution to this situation and allows us to reduce the amount of code required to implement this technique in a clear and concise manner. In C# 3.0 and VB.NET 9.0, lambda expressions will make it possible to make this syntax even more concise.

The following is the ICompare<T> implementation for the ObjectComparer class:

public int Compare( T x, T y )
{
    bool reverse = InvertComparison;

    // check for null objects
    if ( IsNull( x ) && IsNull( y ) )
        return 0;
    else if ( IsNull( x ) )
        return ( reverse ? 1 : -1 );
    else if ( IsNull( y ) )
        return ( reverse ? -1 : 1 );

    // evaluate the value for x
    U value = _yield( x );
    int result = 0;

    if ( IsNull( value ) )
    {
        // check for null values
        result = ( IsNull( _yield( y ) ) ? 0 : -1 );
    }
    else if ( value is string )
    {
        // special handling for strings
        if ( IgnoreCase )
            result = StringComparer.OrdinalIgnoreCase.Compare( value, _yield( y ) );
        else
            result = StringComparer.Ordinal.Compare( value, _yield( y ) );
    }
    else
    {
        // let the IComparable<T> interface do all the work
        result = value.CompareTo( _yield( y ) );
    }

    // return result
    return ( reverse ? -result : result );
}

Performing a Simple Sort

To demonstrate how it all comes together, we'll start with a simple sorting example:

// get a list of processes
Process[] processes = Process.GetProcesses();

// sort the processes by the ProcessName property
Array.Sort<Process>(
    processes,
    new ObjectComparer<Process,string>(
        delegate( Process p )
        {
            return p.ProcessName;
        }
    ) );

foreach ( Process process in processes )
    Console.WriteLine( process.ProcessName );

Essentially what this shows is that an instance of the ObjectComparer class is created that will compare values of type string between Process objects using the anonymous method provided. The ObjectComparer doesn't care how the value is retrieved; it just has to return type string. This means that any number or combination of properties, fields, or even methods can be invoked. This provides a lot of flexibility in defining how two objects are compared. Best of all, all this comes with strong-typing and IntelliSense!

Complex Sorting

Now that you've seen a method in which you can sort any two objects on any member, you may be wondering how you could perform a more sophisticated sort. It is not uncommon to have a requirement to perform client-side sorting in the same manner a relational database would such as sort X ASC, Y DESC, and Z ASC.

When I first thought about trying to tackle this feat, it seemed as though it would be extremely difficult. To my surprise, this was the easiest part of the solution to implement. The ComparerList class provides the implementation of this functionality, which is simply a list of IComparer<T> and an implementation of IComparer<T> at the same time. In fact, this class doesn't really do much of anything other than allow you to chain several comparers together.

One of the most flexible parts about the ComparerList class is that it is not restricted to ObjectComparer implementations. Obviously, I designed the class to support the ObjectComparer class, but I also realized that there are definitely some scenarios the ObjectComparer cannot address and a different comparer implementation will be required. The ComparerList class allows you to mix and match any list of IComparer<T> implementations.

The following is the ICompare<T> interface implementation for the ComparerList class:

public int Compare( T x, T y )
{
    // exit if there is nothing to do
    if ( Count == 0 )
       return -1;

    // check for null values
    if ( IsNull( x ) && IsNull( y ) )
       return 0;
    else if ( IsNull( x ) )
       return -1;
    else if ( IsNull( y ) )
       return 1;

    int result = 0;

    // evaluate each comparer and continue while objects are equal 
    // or there are no more comparers
    foreach ( IComparer<T> comparer in this )
       if ( ( result = comparer.Compare( x, y ) ) != 0 )
          break;

    return result;
}

Performing a Complex Sort

To demonstrate the flexibility in performing a complex sort, we'll sort all processes by their handle count in descending order and their names in ascending order.

// get list of processes
Process[] processes = Process.GetProcesses();

// sort the processes by HandleCount descending, ProcessName ascending
Array.Sort<Process>(
    processes,
    new ComparerList(
        new ObjectComparer<Process,int>(
            delegate( Process p )
            {
                return p.HandleCount;
            }, true ),
        new ObjectComparer<Process,string>(
            delegate( Process p )
            {
                return p.ProcessName;
            }
        ) ) );

Console.WriteLine( "Handles Process" );
Console.WriteLine( "------- --------------------------" );

foreach ( Process process in processes )
    Console.WriteLine( "{0,-7:#,##0} {1}", process.HandleCount, process.ProcessName );

While the example shows the comparers being added in the constructor, this is really only useful for one-time sorts. The ComparerList inherits the List<T> class with all of its methods and properties accessible. This allows you to construct a list of sort methods dynamically at run-time by simply adding the appropriate comparer in the desired order.

Conclusion

While the expression syntax is a little verbose, it should be able to be refactored to an even more concise form after Orcas is released. Hopefully, I've accomplished my goal of illustrating a fresh approach to sorting objects in .NET with all of the benefits of strong-typing, IntelliSense, and compiler validation.

VB.NET Remarks

Sadly, VB.NET doesn't support anonymous methods (my VB is a little rusty, so correct me if I'm wrong). According to what I've read, the VB.NET team didn't feel it was important enough to include this feature amidst the other features they wanted to deliver.

Fear not VB.NET developers! You can still utilize this technique. Unfortunately, the syntax is slightly more verbose. I have provided the source for VB.NET and demonstrate how to utilize the sort classes accordingly.

History

• 9^th May, 2006: Initial post