I wasn't born in Yorkshire, but I spent most of my childhood growing up there. Yorkshire, a large county in the north east of England, has its own collection of slang, not least including the word "aye", which it appears is appropriate in response to pretty much any situation. Another slang phrase is "divvy up". Basically, this just means to divide a bunch of things up somehow.

These days, I spend a lot of my time writing C#. If I'm dealing with a bunch of things in C#, I'll usually store them in a generic List collection, or some other collection. This got me thinking: how can I divvy up a List in C# into multiple Lists? And that's when I decided to implement the Divvy extension method.

What we're aiming for

Suppose we have a list of scores:

var Scores = new List<int>()
    { 87, 32, 45, 60, 91, 10, 58, 77, 66, 71 };

We want to categorize them by grade. For example, anything over and including 85 is a grade A, anything from 70 to 84 is a grade B and so on. This is where our Divvy extension method is going to come in useful. We'll look at what the following code means and how to implement the Divvy method in a moment, but using it will look like this:

// Split them up by grade.
var GradeScores = Scores.Divvy(new Dictionary<string, Predicate<int>>()
{
    { "Grade A", x => x >= 85 },
    { "Grade B", x => x >= 70 && x < 85 },
    { "Grade C", x => x >= 50 && x < 70 },
    { "Fail",    x => x < 50 }
});

It will give us back a Dictionary where the keys are the names of the categories we supplied when calling Divvy and the values are lists of items in that category. Therefore, we can loop over like this:

// Display results.
foreach (var Grade in GradeScores.Keys)
{
    Console.Write(Grade + ": ");
    foreach (var Score in GradeScores[Grade])
        Console.Write(Score.ToString() + " ");
    Console.WriteLine();
}

Which will give us the following output:

Grade A: 87 91
Grade B: 77 71
Grade C: 60 58 66
Fail: 32 45 10

Neat, huh? Let's take a look at how on earth we make this work.

Extension Methods

The first problem is that we want to have a method on the List class. However, that class is in the .Net class library, so we can't go changing it. We also don't want to have to start using a subclass of List all over the place just to get the extra method.

C# 3.0 allows you to write extension methods (detailed tutorial here). These are static methods that can be called as if they were instance methods. This way, we can write a method that can be called on instances of the List class. So our starting point is:

namespace Jnthn.ListExtensions
{
    public static class DivvyUp
    {
        public static void Divvy<T>(this List<T> TheList)
        {
            
        }
    }
}

Note the use of the "this" keyword to mark this as an extension method. Also note that List is a generic type - it takes a type parameter T. However, we don't know what this type is, and we want to make Divvy generic too. Thus we declare it as Divvy<T>.

The Return Type

We are going to split the List into many other Lists, based upon the category the item gets placed into. The categories are named by strings, e.g. "Grade A" and "Grade B". Therefore, for our return type we can use:

Dictionary<string, List<T>>

That is, a Dictionary where the keys are strings and the values are List<T>s, where T is the type of the original List that we were called on. Therefore, our method is now:

public static Dictionary<string, List<T>> Divvy<T>(
    this List<T> TheList)
{
    // Implementation goes here.
}

The Categorizers Parameter

Now we need a way to specify how to divvy up the list into the different categories. This is a mapping (from category name to something that determines whether an item is in that category), so we can use a Dictionary. The keys will be category names, which are of type string:

Dictionary<string,?>

However, what should the type of the values be? Well, they will be functions that take an item of type T and return a bool (true or false) depending on whether the item is in that category or not. There is a delegate in the .Net class library named Predicate<T> that specifies this type of function. Therefore, our parameter's type will be:

Dictionary<string, Predicate<T>>

Meaning that our full method declaration is:

public static Dictionary<string, List<T>> Divvy<T>(
    this List<T> TheList,
    Dictionary<string, Predicate<T>> Categorizers)
{
    // Implementation goes here.
}

You'll be glad to know that the implementation is simpler than the signature.

Initializing The Result Dictionary

Before we start categorizing the items, we need to set up the result Dictionary. We'll instantiate a Dictionary with the same type as the return type we worked out earlier. Then we will loop over the keys of the Categorizers parameter, which are the names of the categories, and create mappings in the Result dictionary from the names to empty Lists.

var Result = new Dictionary<string, List<T>>();
foreach (var Category in Categorizers.Keys)
    Result.Add(Category, new List<T>());

Divvying Up

Finally, we get to the code that's going to do the real work, and it's actually really quite straightforward.

foreach (var Item in TheList)
    foreach (var Category in Categorizers.Keys)
        if (Categorizers[Category](Item))
        {
            Result[Category].Add(Item);
            break; // Since we've divvy'd it into a list.
        }

The outer loop iterates over each item in the List that we were invoked on. The inner loop iterates over the names of the categories. The only slightly tricky part is the condition. Remember that the keys of the Dictionary are actually Predicate<T>s - functions that will return a bool when passed a value of type T. So we just call that function, passing the current Item as a parameter. If it returns true, then we know the item is in the current category. We add it to the correct result list, and then break. This takes us out of the inner loop, and we continue onto the next item in the List.

Putting it all together

Here's the Divvy method as a whole.

public static Dictionary<string, List<T>> Divvy<T>(
    this List<T> TheList,
    Dictionary<string, Predicate<T>> Categorizers)
{
    // Initialize result dictionary of lists.
    var Result = new Dictionary<string, List<T>>();
    foreach (var Category in Categorizers.Keys)
        Result.Add(Category, new List<T>());
    // Go through list items and divvy 'em up.
    foreach (var Item in TheList)
        foreach (var Category in Categorizers.Keys)
            if (Categorizers[Category](Item))
            {
                Result[Category].Add(Item);
                break; // Since we've divvy'd it into a list.
            }
    // And that's it.
    return Result;
}

Looking Back At The Call To Divvy

Let's take another quick look at the call to Divvy to better understand what is going on.

var GradeScores = Scores.Divvy(new Dictionary<string, Predicate<int>>()
{
    { "Grade A", x => x >= 85 },
    { "Grade B", x => x >= 70 && x < 85 },
    { "Grade C", x => x >= 50 && x < 70 },
    { "Fail",    x => x < 50 }
});

Here we are using two features of C# 3.0: collection initializers (tutorial here) and lambda expressions (tutorial here). First we instantiate a new Dictionary, with keys of type string and parameters of type Predicate<T> - exactly what we declared the Categorizers parameter of Divvy to be. Then we use a collection initializers to specify a list of key/value pairs. Each goes in curly brackets, separating the key from the value by a comma. Therefore, "Grade A", "Grade B" and so on are keys.

The values are lambda expressions. If you read where "=>" as "where", you can read the first one as, "x where x is greater than or equal to 85". Note that we are declaring x here - it is just a parameter name. Remember that a lambda expression declares an anonymous method (or function), and what comes to the left of the => is a parameter list. "x =>" declares the x, and "x >= 85" uses it.

Aye!

And that's your lot. Enjoy divvying up your lists, and I'm off to tuck into a nice Yorkshire pudding.

Post Comment Return To Blog