Comparing and Sorting

Comparing and Sorting

The .NET Framework includes a standard set of interfaces that are used for comparing and sorting objects. Although implementing these interfaces is optional, any class that does implement them can interact with other .NET Framework classes to achieve greater functionality. In this section, you’ll see how these interfaces make it possible to compare and sort instances of your types, in the same way the built-in types are used.

Creating Comparable Types with the IComparable Interface

The IComparable interface can be implemented by types to provide a standard way of comparing multiple objects. By implementing IComparable, types can maintain reference equality semantics while providing a standard method for value comparison.

The IComparable interface is declared as follows:

interface IComparable
{
    int CompareTo(object obj);
}

The CompareTo method returns one of the following three possible values:

  • Less than 0 if the current object compares as less than obj

  • 0 if the current object compares as equal to obj

  • Greater than 0 if the current object compares as greater than obj

The following code shows an example of a simple value type that implements IComparable. The ZipCode structure models a U.S. postal ZIP Code, including the optional “plus 4” digits that help further define the destination. The IComparable.CompareTo method is used to enable comparison of multiple ZipCode objects.

public struct ZipCode: IComparable
{
    public ZipCode(string zip, string plusFour)
    {
        _zip = zip;
        _plusFour = plusFour;
    }

    public ZipCode(string zip)
    {
        _zip = zip;
        _plusFour = null;
    }

    public int CompareTo(object obj)
    {
        if(obj == null)
            return 1;

        if(obj.GetType() != this.GetType())
            throw new ArgumentException("Invalid comparison");

        ZipCode other = (ZipCode)obj;
        int result = _zip.CompareTo(other._zip);
        if(result == 0)
        {
            if(other._plusFour == null)
                result = _plusFour == null? 1: 0;
            else
                result = _plusFour.CompareTo(other._plusFour);
        }
        return result;
    }

    public override string ToString()
    {
        string result;
        if(_plusFour != null && _plusFour.Length != 0)
            result = string.Format("{0}-{1}", _zip, _plusFour);
        else
            result = _zip;
        return result;
    }

    string _zip;
    string _plusFour;
}

The ZipCode class has two fields that are used to store the components that make up a U.S. ZIP Code. The ZipCode.ToString method is overridden to provide string formatting in the customary format of, for example, 92653 or 92653-8204 if a “plus 4” code is present. The method of most interest in the ZipCode class is CompareTo. Although the details of how two objects are compared will differ, all implementations of CompareTo will follow this general pattern:

public int CompareTo(object obj)
{
    // If the other object is null, this object sorts as greater.
    if(obj == null)
        return 1;
    // If there's a type mismatch, throw an exception.
    if(obj.GetType() != this.GetType())
        throw new ArgumentException("Invalid comparison");
    // Return a result based on a comparison of the two objects.
    
    

}

An implementation of the CompareTo method should first test to see whether null was passed as a parameter. If so, the comparison should be short-circuited and a result greater than 0 should be returned to indicate that the current object compares as greater than null. It’s also important to test that the objects being compared have the same type or are of a comparable type. Other­wise, you can run into a scenario such as this one:

Orange anOrange;
Apple  anApple;
int result = anOrange.CompareTo(anApple);

After adding support for IComparable to a class or a structure, you can make use of the type’s support for comparison in two ways. The first way is to directly call the CompareTo method to determine the relative sort order for two objects, as shown here:

ZipCode lagunaHills = new ZipCode("92653", "8204");
ZipCode redmond = new ZipCode("98052");
ZipCode phoenix = new ZipCode("85044");

int comparison = lagunaHills.CompareTo(redmond);

The second way to take advantage of IComparable is to leverage other types and methods in the .NET Framework that are aware of the IComparable interface. These types offer increased functionality when they’re used with classes and structures that implement IComparable. For example, the Array.Sort static method can be used to sort an array of types that implement IComparable, as shown here:

ZipCode [] codes = { lagunaHills, redmond, phoenix };
Array.Sort(codes);
foreach(ZipCode code in codes)
{
    // Display sorted array of ZIP Codes.
    Console.WriteLine(code);
}

The version of the Array.Sort method used here detects and uses the IComparable interface to determine the relative sort order of objects in the array. If you attempt to use this version of Sort with an array of objects that don’t implement IComparable, an InvalidOperationException will be thrown.

Building Comparison Classes with the IComparer Interface

The IComparable interface is useful for those cases in which there’s a clear ordering method for class instances. However, there are times when a number of possible sort methods are available for a collection of objects. The IComparer interface enables you to build classes that are specialized to compare instances of other classes.

The IComparer interface is declared as follows:

interface IComparer
{
    int Compare(object x, object y);
}

The Compare method works much like the CompareTo method discussed in the previous section, returning one of the following values:

  • Less than 0 if the first object compares as less than the second object

  • 0 if the first object compares as equal to the second object

  • Greater than 0 if the first object compares as greater than the second object

As with the IComparable.CompareTo method, if an object reference is null, it compares as less than any object.

Implementing IComparer in Pluggable Classes

The IComparer interface makes it possible for you to create multiple comparison classes, each of which performs a different type of comparison. The following class implements the IComparer interface and sorts ZipCode objects in ascending order:

public class AscendingComparer: IComparer
{
    public int Compare(object x, object y)
    {
        int result = 0;
        if(x == null && y == null)
            result = 0;
        else if(x == null)
            result = -1;
        else if(y == null)
            result = 1;
        else
        {
            if(x.GetType() != y.GetType())
            throw new ArgumentException("Invalid comparison");
            IComparable comp = x as IComparable;
            if(comp == null) 
                throw new ArgumentException("Invalid comparison"); 
            result = comp.CompareTo(y); 
        }
        return result;
    }
}

This code shows a common pattern for implementing IComparer.Compare. In much the same way as in the earlier IComparable example, any reference to null is sorted as less than object references. If two valid object references are compared, the types of the objects are tested to ensure that they’re comparable. In this case, the AscendingComparer class tests to verify that both objects have the same type.

The following code implements the DescendingComparer class, which works exactly like AscendingComparer except that it sorts its objects in reverse order:

public class DescendingComparer: IComparer
{
    public int Compare(object x, object y)
    {
        int result = 0;
        if(x == null && y == null)
            result = 0;
        else if(y == null)
            result = -1;
        else if(x == null)
            result = 1;
        else
        {
            if(x.GetType() != y.GetType())
            throw new ArgumentException("Invalid comparison");
            IComparable comp = y as IComparable;
            if(comp == null) 
                throw new ArgumentException("Invalid comparison"); 
            result = comp.CompareTo(x);
        }
        return result;
    }
}

When sorting is required, you can simply plug in an instance of the preferred comparison class, allowing multiple sort options to be used for a single type. For example, the following code uses both of the previous comparison classes to sort ZipCode objects:

Array.Sort(codes, new AscendingComparer());
foreach(ZipCode code in codes)
{
    Console.WriteLine(code);
}
Array.Sort(codes, new DescendingComparer());
foreach(ZipCode code in codes)
{
    Console.WriteLine(code);
}

In the preceding examples, the AscendingComparer and DescendingComparer classes are exposed as public classes. Another alternative is to expose the classes that perform the comparison through properties, as shown here:

Array.Sort(codes, codes.AscendingComparer);

    

Array.Sort(codes, codes.DescendingComparer);

    
 

The advantage of this approach is that the comparison classes are more completely encapsulated, thus hiding more implementation details from the user.

Using the Built-In Comparison Classes

The .NET Framework includes two classes that implement the IComparer interface and can be leveraged in your own classes to simplify comparisons. The Comparer and CaseInsensitiveComparer classes provide basic implementations of IComparer that are suitable for many comparison classes. Both of these classes respect the culture preferences of the user, providing proper comparisons based on the locale and language settings associated with the current thread.

You never directly create an instance of the Comparer class using the new operator. Instead, you call the Default method, which returns a properly initialized Comparer object, as shown here:

Comparer theComparer = Comparer.Default;

After you have a Comparer object, you can delegate comparison calls to its Compare method. The following code illustrates a simplified version of AscendingComparer implemented using the Comparer class:

public int Compare(object x, object y)
{
    return Comparer.Default.Compare(x, y);
}

In this code, ZipCode objects are passed to the Comparer class, which is able to properly compare the objects through their IComparable interface. This is the only way that Comparer can perform comparisons on arbitrary objects. If your classes don’t implement IComparable, you can’t pass instances of the classes to Comparer.Compare.

The CaseInsensitiveComparer class works much like the Comparer class, comparing any two objects through the IComparable interface, except that it performs a case-insensitive comparison on strings that it encounters. Like the Comparer class, the static Default method is used to obtain a reference to a properly initialized CaseInsensitiveComparer object, as shown here:

CaseInsensitiveComparer aComparer = CaseInsensitiveComparer.Default;

Unlike the Comparer class, you can use the new operator to create CaseInsensitiveComparer objects. The default constructor has little advantage over the Default method, other than enabling you to cache a specific Case­InsensitiveComparer object. An overloaded version of the constructor allows you to specify the culture to be used for the comparison. (The culture of the current thread is used by default.) The following code performs a string comparison using the Swedish culture definition:

public class SwedishNameComparer: IComparer
{
    public int Compare(object x, object y)
    {
        CultureInfo ci = new CultureInfo("sv");
        CaseInsensitiveComparer aComparer = null;
        aComparer = new CaseInsensitiveComparer(ci);
        return aComparer.Compare(x, y);
    }
}


    


public Main()
{
    string [] places = { "Kista", "Alvsjo", "Stockholm" };
    Array.Sort(places, new SwedishNameComparer());
    foreach(string place in places)
    {
        Console.WriteLine(place);
    }
}

The preceding code sorts the strings according to the ordering used in Swedish, where A is placed after Z, as shown here:

Kista
Stockholm
Alvsjo

If the en-US (English as spoken in the United States) culture is used to sort the strings, the strings are sorted as follows:

Alvsjo
Kista
Stockholm

Which comparison is most appropriate? The answer depends on the expectations of the user, which are expressed in the culture settings associated with the current thread. Because the comparison classes included with the .NET Framework take the culture settings into account, they handle these sorting issues correctly.



Part III: Programming Windows Forms