James Michael Hare

...hare-brained ideas from the realm of software development...
posts - 166 , comments - 1431 , trackbacks - 0

My Links

News

Welcome to my blog! I'm a Sr. Software Development Engineer in the Seattle area, who has been performing C++/C#/Java development for over 20 years, but have definitely learned that there is always more to learn!

All thoughts and opinions expressed in my blog and my comments are my own and do not represent the thoughts of my employer.

Blogs I Read

Follow BlkRabbitCoder on Twitter

Tag Cloud

Article Categories

Archives

Post Categories

.NET

CSharp

Little Wonders

Little Wonders

vNext

C#/.NET Toolbox: Generic Reversing Comparers

I’m going to start another series of posts that I’m calling C#/.NET Toolbox that will just contain little GUCs (Generic Utility Classes) I’ve developed along the way.  If these already exist as part of the framework and I’ve overlooked them, feel free to let me know!  And if you know of a better way to implement them, do the same!  I’m never too old to learn something new (I hope!).

Update: improved the ReverseComparer and added an extension method that will reverse any comparer instance.

The Problem: Reversing a Comparison

I was looking at some code the other day, and came across a instance where a developer was trying to handle a column click to sort or reverse sort the data.  So, they developed a Comparer which was pretty huge that could account for any column selected and then compare based on that column.  Now, while I get very nervous at the low cohesion in that sort of thing, that wasn’t the main thing that caught my eye, it was this (paraphrasing the code):

   1: // custom comparer for the rows based on selected column
   2: var columnComparer = new ColumnComparer(selectedColumn);
   3:  
   4: // use built-in Sort() method on List<T>
   5: rows.Sort(columnComparer);
   6:  
   7: if (sortDirection == SortDirection.Descending)
   8: {
   9:     // use built-in Reverse() method to reverse contents of List<T>
  10:     rows.Reverse();
  11: }

I looked at this, and while the Sort() is really the larger of the big-Os to worry about here, I still didn’t really like the fact we were sorting it one way just to reverse it, so my initial thought was to ask the developer to make a reverse comparer. 

True, they could just add another parameter to their ColumnComparer to make it ascending versus descending, but to me this is bad cohesion and would bloat the code even more.  There tends to be a natural order to the domain values in many types, and reversing that order should be a generic, and separate, operation.

So, combining all these thoughts together and stirring them in my brain, I thought, “why not make a GUC for reversing an IComparer<T> and for reverse comparing IComparable<T>.

First, I checked the .NET Framework to see if I was missing something that already did this, and I couldn’t find one offhand.  Next I searched and found a few responses but none I was completely happy with.  So I began to code these for myself.

IComparable<T> vs. IComparer<T>

Now, many of us know the difference between these two interfaces, but some may not, so a quick introduction to them.

IComparable<T> is an interface that a type with a natural order in its domain values can implement directly.  Things like int, double, char, string, DateTime all have an inherent sense of order and so these rightfully belong inside the type themselves.  Thus, all the Framework types with a natural order tend to implement IComparable<T> for completeness.

These types where they exist in the .NET Framework already implement IComparable<T>.  In fact, any types you develop with a true natural order (not implementation or user specific, but the objects they represent have an intuitive order) should strongly consider implementing IComparable<T> as well.

To Implement IComparable<T> in your type, you implement the interface where T is your type, and then provide a method CompareTo() which compares the current (this) instance of T to the argument passed in. 

CompareTo() should return:

Ordering Result
this < argument negative number (typically -1)
this == argument zero (0)
this > argument positive number (typically +1)

Now, IComparer<T> is different because it is an external comparison of two items.  The best reason to create an IComparer<T> implementation is if the type T you are comparing doesn’t have a natural order, or if you are seeking a comparison that differs from the natural order. 

For instance, if you have a row of data, what’s the natural order?  It really depends!  What does the user want to sort by?  What’s the meaning of the data?  In things such as this, it is better to create external comparers so that you can switch between many different comparers as the need dictates, and you don’t pollute the type itself with all the possible comparisons.

To implement IComparer<T>, you create a new class that implements the interface where T will be the type you are seeking to compare.  Then, you define a method Compare() that takes two instances of T, and returns:

Ordering Result
first < second argument negative number (typically -1)
first == second argument zero (0)
first > second argument positive number (typically +1)

 

The ComparerReverser<T>: Reversing an IComparer<T> instance

If you want to reverse an existing comparer, the process is trivial, all you need to do is negate the comparison so that if it returns a positive number instead of a negative number, and a negative number instead of a positive number.  This can easily be accomplished by negating the result (unary – operator), but even more efficient is to simply reverse the order of the arguments passed to the existing comparer. 

In other words, x > y is obviously the reverse of y > x, thus to reverse Compare(x,y) we just need to call Compare(y,x) instead.  This yields the ComparerReverser below.  I named it such because it’s whole job is to wrap a comparer (IComparer<T> and reverse it).

   1: // A generic comparer that reverses the action of a wrapped comparer.
   2: public sealed class ComparerReverser<T> : IComparer<T>
   3: {
   4:     private readonly IComparer<T> _wrappedComparer;
   5:  
   6:     // Initializes an instance of a ComparerReverser that takes a wrapped comparer
   7:     // and returns the inverse of the comparison.
   8:     public ComparerReverser(IComparer<T> wrappedComparer)
   9:     {
  10:         if (wrappedComparer == null)
  11:         {
  12:             throw new ArgumentNullException("wrappedComparer");
  13:         }
  14:         
  15:         _wrappedComparer = wrappedComparer;
  16:     }
  17:  
  18:     // Compares two objects and returns a value indicating whether 
  19:     // one is less than, equal to, or greater than the other.
  20:     public int Compare(T x, T y)
  21:     {
  22:         // to reverse compare, just invert the operands....
  23:         return _wrappedComparer.Compare(y, x);
  24:     }
  25: }

Update: We can also add a nice extension method that will take any IComparer<T> and wrap it for us.  This allows us to quickly make a reverser from any existing comparer instance.

   1: // Extension method that will take any comparer and reverse it.
   2: public static class ComparerExtensions
   3: {
   4:     // Reverses the comparer by wrapping it in a ComparerReverser instance.
   5:     public static IComparer<T> Reverse<T>(this IComparer<T> comparer)
   6:     {
   7:         if (comparer == null)
   8:         {
   9:             throw new ArgumentNullException("comparer");
  10:         }
  11:  
  12:         return new ComparerReverser<T>(comparer);
  13:     }
  14: }

Which would allow us to simplify constructing a reversing comparer by taking an existing comparer and adding .Reverse() to the end like this:

   1: var list = new List<string> { "A", "C", "B", "F", "D", "E" };
   2:  
   3: // sorts strings in reverse order to F, E, D, C, B, A
   4: list.Sort(Comparer<string>.Default.Reverse());

In fact, you can Reverse() a Reverse() and get back (logically) the same comparer.

The ReverseComparer<T>: Reversing IComparable<T> comparisons

Likewise, if you want to reverse the result of comparing two instances of IComparable<T>, we shouldn’t do this in the type itself, because it alters the natural ordering of the object.  So the best thing to do is create a new IComparer<T> class that compares two IComparable<T> instances in reverse order.  That is, Compare(x,y) should call y.CompareTo(x) to reverse the comparison result.

Update: According to the MSDN, null is less than any non-null instance.  As a result we should make sure that if both arguments are null, a zero is returned, and that a single null argument is less than the non-null argument.

This yields the code (could also make this a singleton since really doesn’t need to be multiply instantiated).

   1: // A generic comparer that reverses the comparisons of IComparable instances
   2: public sealed class ReverseComparer<T> : IComparer<T> where T : IComparable<T>
   3: {
   4:     public int Compare(T x, T y)
   5:     {
   6:         if (x == null)        // handle nulls according to MSDN
   7:         {
   8:             if (y == null)
   9:             {                
  10:                 return 0;     // if both null are equal
  11:             }
  12:     
  13:             return 1;        // x null but y not, so x < y, but reversing to 1!
  14:         }
  15:     
  16:         if (y == null)        // y null but x not, so x > y, but reversing to -1!
  17:         {
  18:             return -1;
  19:         }
  20:     
  21:         // if neither arg is null, pass on to CompareTo in reverse order.  
  22:         return y.CompareTo(x);
  23:     }
  24: }

Usage:

Now, having these two reversing comparers in our toolbox, we can easily use them to reverse comparisons of any IComparable<T> types:

   1: var list = new List<string> {"A", "B", "C", "D", "E", "F", "G"};
   2:  
   3: // yes, you can also use a Comparer<T> here, but for simple illustration...
   4: list.Sort(new ReverseComparer<string>());
   5:  
   6: // output is: G, F, E, D, C, B, A
   7: list.ForEach(Console.WriteLine);

Or you can reverse the result of any IComparer<T> instance, such as the ColumnComparer discussed in the first example:

   1: // custom comparer for the rows based on selected column
   2: var columnComparer = new ColumnComparer(selectedColumn);
   3:  
   4: // based on sort direction, either sort in order or reverse...
   5: rows.Sort(sortDirection == SortDirection.Descending
   6:     ? new ComparerReverser(columnComparer) : columnComparer);

Summary

Hopefully, you found some use out of these generic comparison reversers.  Feel free to comment, write, or tweet me with any thoughts or corrections you may have!

 

 Technorati Tags: ,,,,,

 

Print | posted on Thursday, December 2, 2010 7:37 PM | Filed Under [ My Blog C# Software .NET Toolbox ]

Powered by: