Making a Type Sortable






Making a Type Sortable

Problem

You have a data type that will be stored as elements in an array or an ArrayList. You would like to use the Array.Sort and ArrayList.Sort methods to allow custom sorting of your data types in the array. In addition, you may need to use this type in a SortedList collection.

Solution

Implement the IComparable interface. The Square class shown in Figure implements this interface in such a way that the Array, ArrayList, and SortedList objects can sort and search an array or collection of these Square objects.

Making a type sortable by implementing IComparable

public class Square : IComparable
{
    public Square( ){} 
    public Square(int height, int width) 
    {
       this.height = height;
       this.width = width;
    }
    private int height;
    private int width;
    public int Height
    {
       get{ return (height); }
       set{ height = value; }
    }
    public int Width
    {
       get{ return (width); }
       set{ width = value; }
    }
    
    public int CompareTo(object obj)
    {
       if (this.GetType( ) != obj.GetType( ))
       {
          throw (new ArgumentException(
             "Both objects being compared must be of type Square.")); 
       }
       else
       {
          Square square2 = (Square)obj;
          long area1 = this.Height * this.Width; 
          long area2 = square2.Height * square2.Width;
          if (area1 == area2)
          {
             return (0);
          }
          else if (area1 > area2)
          {
             return (1);
          }
          else
          {
             return (-1);
          }
       }
    }
    public override string ToString( ) 
    {
       return ("Height:" + height + " Width:" + width); 
    } 
}

Discussion

By implementing the IComparable interface on your class (or structure), you can take advantage of the sorting routines of the Array, ArrayList, List<T>, and SortedList classes. The algorithms for sorting are built into these classes; all you have to do is tell them how to sort your classes via the code you implement in the IComparable.CompareTo method.

When an array of Square objects is passed to the Array.Sort static method, the array is sorted using the IComparable interface of the Square objects. The same goes for the ArrayList.Sort method. The Add method of the SortedList class uses this interface to sort the objects as they are being added to the SortedList.

The Array.Sort and ArrayList.Sort methods use the QuickSort algorithm to sort an array's elements.


IComparer is designed to solve the problem of allowing objects to be sorted based on different criteria in different contexts. This interface also allows you to sort types that you did not write. If you also wanted to sort the Square objects by height, you could create a new class called CompareHeight, shown in Figure, which would also implement the IComparer interface.

Making a type sortable by implementing IComparer

public class CompareHeight : IComparer
{

    public int Compare(object obj1, object obj2)
    {
       if (!(obj1 is Square) || !(obj2 is Square))
       {
          throw (new ArgumentException(
                "Both parameters must be of type Square."));
       }
       else
       {
          Square square1 = (Square)obj1;
          Square square2 = (Square)obj2;
          if (square1.Height == square2.Height)
          {
             return (0);
          }
          else if (square1.Height > square2.Height)
          {
             return (1);
          }
          else
          {
             return (-1); 
          } 
       } 
    }
}

This class is then passed in to the IComparer parameter of the Sort routine. Now you can specify different ways to sort your Square objects.

For best performance, keep the CompareTo method short and efficient, since it will be called multiple times by the Sort methods. For example, in sorting an array with four items, the Compare method is called 10 times.


The TestSort method shown in Figure demonstrates how to use the Square and CompareHeight classes with the Array, ArrayList, and SortedList classes.

TestSort method

public static void TestSort( ) 
{
    Square[] arrayOfSquares = new Square[4] {new Square(1,3),
                                   new Square(4,3),
                                   new Square(2,1),
                                   new Square(6,1)};
    ArrayList arrayListOfSquares = new ArrayList( );
    arrayListOfSquares.Add(new Square(1,3));
    arrayListOfSquares.Add(new Square(4,3));
    arrayListOfSquares.Add(new Square(2,1));
    arrayListOfSquares.Add(new Square(6,1));
    IComparer HeightCompare = new CompareHeight( );
    // Test an ARRAY.
    Console.WriteLine("ARRAY");
    Console.WriteLine("Original array");
    foreach (Square s in arrayOfSquares)
    {
       Console.WriteLine(s.ToString( ));
    }
    Console.WriteLine( );
    Console.WriteLine("Sorted array using IComparer=HeightCompare");
    Array.Sort(arrayOfSquares, HeightCompare);
    foreach (Square s in arrayOfSquares)
    {
       Console.WriteLine(s.ToString( ));
    }
    Console.WriteLine( );
    Console.WriteLine("Sorted array using IComparable");
    Array.Sort(arrayOfSquares);
    foreach (Square s in arrayOfSquares)
    {
       Console.WriteLine(s.ToString( ));
    }
    // Test an ARRAYLIST.
    Console.WriteLine( );
    Console.WriteLine( );
    Console.WriteLine("ARRAYLIST");
    foreach (Square s in arrayListOfSquares)
    {
       Console.WriteLine(s.ToString( ));
    }
    Console.WriteLine( );
    Console.WriteLine("Sorted ArrayList using IComparer=HeightCompare");
    arrayListOfSquares.Sort(HeightCompare);
    foreach (Square s in arrayListOfSquares)
    {
       Console.WriteLine(s.ToString( ));
    }
    Console.WriteLine( );
    Console.WriteLine("Sorted ArrayList using IComparable");
    arrayListOfSquares.Sort( );
    foreach (Square s in arrayListOfSquares)
    {
       Console.WriteLine(s.ToString( ));
    }
    // Test a SORTEDLIST.
    SortedList SortedListOfSquares = new SortedList( );
    SortedListOfSquares.Add(0, new Square(1,3));
    SortedListOfSquares.Add(2, new Square(4,3));
    SortedListOfSquares.Add(1, new Square(2,1));
    SortedListOfSquares.Add(3, new Square(6,1));
    Console.WriteLine( );
    Console.WriteLine( );
    Console.WriteLine("SORTEDLIST");
    foreach (DictionaryEntry s in SortedListOfSquares)
    {
       Console.WriteLine(s.Key + " : " + ((Square)s.Value).ToString( )); 
    } 
}

This code displays the following output:

	ARRAY
	Original array
	Height:1 Width:3
	Height:4 Width:3
	Height:2 Width:1
	Height:6 Width:1
	Sorted array using IComparer=HeightCompare
	Height:1 Width:3
	Height:2 Width:1
	Height:4 Width:3
	Height:6 Width:1
	Sorted array using IComparable
	Height:2 Width:1
	Height:1 Width:3
	Height:6 Width:1
	Height:4 Width:3
	ARRAYLIST
	Height:1 Width:3
	Height:4 Width:3
	Height:2 Width:1
	Height:6 Width:1
	Sorted ArrayList using IComparer=HeightCompare
	Height:1 Width:3
	Height:2 Width:1
	Height:4 Width:3
	Height:6 Width:1
	Sorted ArrayList using IComparable
	Height:2 Width:1
	Height:1 Width:3
	Height:6 Width:1
	Height:4 Width:3
	SORTEDLIST
	0 : Height:1 Width:3
	1 : Height:2 Width:1
	2 : Height:4 Width:3
	3 : Height:6 Width:1

See Also

See Recipe 3.6; see the "IComparable Interface" topic in the MSDN documentation.



 Python   SQL   Java   php   Perl 
 game development   web development   internet   *nix   graphics   hardware 
 telecommunications   C++ 
 Flash   Active Directory   Windows