Tuesday, October 19, 2010

Creating a ToDictionaryList Extension

ToDictionary

.Net 3.5 introduced the Enumerable.ToDictionary Method. It allows you to take a list of items, and convert them into a dictionary based on some key given as a lambda expression. For example, this code snippet for Snippet Compiler will put a weeks worth of dates into a Dictionary<int,DateTime>, so you could do a dictionary lookup by day:

public static void RunSnippet()
{
DateTime time = new DateTime(2228, 3, 22);
List<DateTime> items = new List<DateTime>();
items.Add(time);
items.Add(time.AddDays(1));
items.Add(time.AddDays(2));
items.Add(time.AddDays(3));
items.Add(time.AddDays(4));
items.Add(time.AddDays(5));
items.Add(time.AddDays(6));

var dayByDay = items.ToDictionary(d => d.Day);
foreach (var dayKeyValue in dayByDay)
{
WL(dayKeyValue.Key + " " + dayKeyValue.Value);
}
}

Which results in this output:

22 3/22/2228 12:00:00 AM
23 3/23/2228 12:00:00 AM
24 3/24/2228 12:00:00 AM
25 3/25/2228 12:00:00 AM
26 3/26/2228 12:00:00 AM
27 3/27/2228 12:00:00 AM
28 3/28/2228 12:00:00 AM
Press any key to continue...



ToDictionaryList


But what if the key you want to use, is not unique? You’ll end up getting this warning:

System.ArgumentException: An item with the same key has already been added.
at System.Collections.Generic.Dictionary`2.Insert(TKey key, TValue value, Boolean add)
at System.Linq.Enumerable.ToDictionary[TSource,TKey,TElement](IEnumerable`1 source, Func`2 keySelector, Func`2 elementSelector, IEqualityComparer`1 comparer)

I had this same issue and decided to create a ToDictionaryList() extension method that would return a Dictionary<key,List<item>>. Here is an example using the ToDictionaryList() grouping the dateTimes by day:



public static void RunSnippet()
{
DateTime time = new DateTime(2228, 3, 22);
List<DateTime> items = new List<DateTime>();
items.Add(time);
items.Add(time.AddHours(1));
items.Add(time.AddMinutes(1));
items.Add(time.AddDays(1));
items.Add(time.AddHours(26));

var results = items.ToDictionaryList(d => d.Day);
foreach (var result in results)
{
foreach (var item in result.Value)
{
WL(result.Key + " " + item);
}
}
}


Which results in this output:

22 3/22/2228 12:00:00 AM
22 3/22/2228 1:00:00 AM
22 3/22/2228 12:01:00 AM
23 3/23/2228 12:00:00 AM
23 3/23/2228 2:00:00 AM
Press any key to continue...


Basically it is two dictionary entries, one for the 22nd which is a List<DateTime> of 3 DateTimes, and one for the 23, which contains two items. You can even write a lambda expression for the type of item to be in the list. So in the last example, if you changed "var results = items.ToDictionaryList(d => d.Day);" to "var results = items.ToDictionaryList(d => d.Day, d => d.Hour); " item would in int and which would result in this output:

22 0
22 1
22 0
23 0
23 2
Press any key to continue...


The Code


Here is the code required to make the ToDictionaryList Possible:


public static class Extensions
{
private static Func<TElement, TElement> Instance<TElement>()
{
return delegate(TElement x) { return x; };
}

public static Dictionary<TKey, List<TSource>> ToDictionaryList<TSource, TKey>(this IEnumerable<TSource> source, Func<TSource, TKey> keySelector)
{
return source.ToDictionaryList(keySelector, Instance<TSource>());
}

public static Dictionary<TKey, List<TElement>> ToDictionaryList<TSource, TKey, TElement>(this IEnumerable<TSource> source, Func<TSource, TKey> keySelector, Func<TSource, TElement> elementSelector)
{
Dictionary<TKey, List<TElement>> dictionary = new Dictionary<TKey, List<TElement>>();
List<TElement> elements;
foreach (TSource local in source)
{
if (!dictionary.TryGetValue(keySelector(local), out elements))
{
elements = new List<TElement>();
dictionary.Add(keySelector(local), elements);
}
elements.Add(elementSelector(local));
}

return dictionary;
}
}



The Instance Method is used to return a delegate function that returns a single item of the given type (Basically a (c => c)). The ToDictionaryList() will loop through all items in the list, adding them to a new list if the key doesn’t already exist in the dictionary, or add the item to the already existing list in the dictionary. Pretty simple really.

Smile

3 comments:

troll1184 said...

Why not just use ToLookup()

Daryl said...

Great question troll1184, at this point, because I didn't know that ToLookup() existed. I'll have to do some performance tests to see which is faster, but after looking at ToLookup() in reflector, it looks like they're storing the hash and some other things that I'm not, that I would imagine would make ToLookup faster than my ToDictionaryList(). This reminds me of the time I kept on using Where(c => SomeCondition(c)).Count > 0, instead of Any(c => SomeCondition). Thanks for the comment!

Daryl said...

After some testing, my ToDictionaryList() seems to be about 20-30% faster creating the collection, and about 10-15% faster retrieving the value.

After looking at where I was using ToDictionaryList(), I realized that there is one major drawback to the ILookup object. It returns an IEnumerable<>, which you can't update. I needed the ability to add and remove items from my list, so that is why I needed different version of ToLookup().