Wednesday, October 24, 2007

Schwartzian Transform in C# 2.0

In case someone was reading Joe Cheng's post about performing a Schwartzian Transform in C# 3.0 and was wondering what it would look like in 2.0 code, here it is:

private static void SchwartzSort<E, S>(List<E> list,
Converter<E, S> converter,
Comparison<S> comparison) {
    List<KeyValuePair<S, E>> pairs = list.ConvertAll<KeyValuePair<S, E>>(delegate(E x) {
        return new KeyValuePair<S, E>(converter(x), x);
    });
    pairs.Sort(delegate(KeyValuePair<S, E> x, KeyValuePair<S, E> y) {
        return comparison(x.Key, y.Key);
    });
    for (int i = 0; i < list.Count; i++) {
        list[i] = pairs[i].Value;
    }
}
 
/// <summary>
/// Sorts a list using a Schwartzian transform (applies a conversion
/// function to each element and sorts by the value of that function).
/// </summary>
/// <typeparam name="E">The type of element to be sorted</typeparam>
/// <typeparam name="S">The type of the element to sort by</typeparam>
/// <param name="list">The list to be sorted (sort occurs in place).</param>
/// <param name="converter">
/// The converter function (converts element of type <code>E</code> to type <code>S</code>).
/// </param>
/// <param name="comparison">
/// The comparison function, compares 2 values of type <code>S</code>.
/// </param>
/// <seealso cref="Sort{E,S}(List{E},Converter{E,S})"/>
public static void Sort<E, S>(List<E> list, Converter<E, S> converter, Comparison<S> comparison) {
    SchwartzSort(list, converter, comparison);
}
 
/// <summary>
/// Sorts a list using a Schwartzian transform using the default comparer
/// on type <code>S</code> (applies a conversion function to each element
/// and sorts by the value of that function).
/// </summary>
/// <typeparam name="E">The type of element to be sorted</typeparam>
/// <typeparam name="S">The type of the element to sort by</typeparam>
/// <param name="list">The list to be sorted (sort occurs in place).</param>
/// <param name="converter">
/// The converter function (converts element of type <code>E</code> to type <code>S</code>).
/// </param>
/// <seealso cref="Sort{E,S}(List{E},Converter{E,S},Comparison{S})"/>
public static void Sort<E, S>(List<E> list, Converter<E, S> converter) where S:IComparable {
    SchwartzSort(list, converter, delegate(S x, S y) { return x.CompareTo(y); });
}



Obviously this is not quite as aesthetically pleasing as the 3.0 version, but it is still useful for any developers doing 2.0 coding out there and need to sort a list by the results of a function. Here is an example of how it would be used:



public class foobar {
    private string _foo;
    private string _bar;
 
    public string Foo {
        get { return _foo; }
        set { _foo = value; }
    }
 
    public string Bar {
        get { return _bar; }
        set { _bar = value; }
    }
 
    public foobar(string foo, string bar) {
        _foo = foo;
        _bar = bar;
    }
}


Assuming class foobar:



List<foobar> items = new List<foobar>(4);
items.Add(new foobar("a","b"));
items.Add(new foobar("asdf","jkl"));
items.Add(new foobar("green","purple"));
items.Add(new foobar("c", "a"));
 
Sort<foobar,string>(items, delegate(foobar item) { return item.Foo; });

1 comment:

Jonathan Lim said...

Thank you for posting this code. I did a Google search for most of the words in the title of your post and your blog showed up first.