Creating ILookups

Question

I've got an ILookup generated by some complicated expression. Let's say it's a lookup of people by last name. (In our simplistic world model, last names are unique by family)

ILookup<string, Person> families;

Now I've got two queries I'm interested in how to build.

First, how would I filter by last name?

var germanFamilies = families.Where(family => IsNameGerman(family.Key));

But here, germanFamilies is an IEnumerable<IGrouping<string, Person>>; if I call ToLookup() on it, I'd best bet would get an IGrouping<string, IGrouping<string, Person>>. If I try to be smart and call SelectMany first I'd end up with the computer doing a lot of unnecessary work. How would you convert this enumeration into a lookup easily?

Second, I'd like to get a lookups of adults only.

var adults = families.Select(family =>
         new Grouping(family.Key, family.Select(person =>
               person.IsAdult())));

Here I'm faced with two problems: the Grouping type doesn't exist (except as an internal inner class of Lookup), and even if it did we'd have the problem discussed above.

So, apart from implementing the ILookup and IGrouping interfaces completely, or make the computer do silly amounts of work (regrouping what has already been grouped), is there a way to alter existing ILookups to generate new ones that I missed?

Answer 1

(I'm going to assume you actually wanted to filter by last name, given your query.)

You can't modify any implementation of ILookup<T> that I'm aware of. It's certainly possible to implement ToLookup with an immutable lookup, as you're clearly aware :)

What you could do, however, is to change to use a Dictionary<string, List<Person>>:

var germanFamilies = families.Where(family => IsNameGerman(family.Key))
                             .ToDictionary(family => family.Key,
                                           family.ToList());

That approach also works for your second query:

var adults = families.ToDictionary(family => family.Key,
                                   family.Where(person => persion.IsAdult)
                                         .ToList());

While that's still doing a bit more work than we might think necessary, it's not too bad.

EDIT: The discussion with Ani in the comments is worth reading. Basically, we're already going to be iterating over every person anyway - so if we assume O(1) dictionary lookup and insertion, we're actually no better in terms of time-complexity using the existing lookup than flattening:

var adults = families.SelectMany(x => x)
                     .Where(person => person.IsAdult)
                     .ToLookup(x => x.LastName);

In the first case, we could potentially use the existing grouping, like this:

// We'll have an IDictionary<string, IGrouping<string, Person>>
var germanFamilies = families.Where(family => IsNameGerman(family.Key))
                             .ToDictionary(family => family.Key);

That is then potentially much more efficient (if we have many people in each family) but means we're using groupings "out of context". I believe that's actually okay, but it leaves a slightly odd taste in my mouth, for some reason. As ToLookup materializes the query, it's hard to see how it could actually go wrong though...

Answer 2

For your first query, what about implementing your own FilteredLookup able to take advantage of coming from another ILookup ?
(thank to Jon Skeet for the hint)

public static ILookup<TKey, TElement> ToFilteredLookup<TKey, TElement>(this ILookup<TKey, TElement> lookup, Func<IGrouping<TKey, TElement>, bool> filter)
{
    return new FilteredLookup<TKey, TElement>(lookup, filter);
}

With FilteredLookup class being:

internal sealed class FilteredLookup<TKey, TElement> : ILookup<TKey, TElement>
{
    int count = -1;
    Func<IGrouping<TKey, TElement>, bool> filter;
    ILookup<TKey, TElement> lookup;

    public FilteredLookup(ILookup<TKey, TElement> lookup, Func<IGrouping<TKey, TElement>, bool> filter)
    {
        this.filter = filter;
        this.lookup = lookup;
    }

    public bool Contains(TKey key)
    {
        if (this.lookup.Contains(key))
            return this.filter(this.GetGrouping(key));
        return false;
    }

    public int Count
    {
        get
        {
            if (count >= 0)
                return count;
            count = this.lookup.Where(filter).Count();
            return count;
        }
    }

    public IEnumerable<TElement> this[TKey key]
    {
        get
        {
            var grp = this.GetGrouping(key);
            if (!filter(grp))
                throw new KeyNotFoundException();
            return grp;
        }
    }

    public IEnumerator<IGrouping<TKey, TElement>> GetEnumerator()
    {
        return this.lookup.Where(filter).GetEnumerator();
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }

    private IGrouping<TKey, TElement> GetGrouping(TKey key)
    {
        return new Grouping<TKey, TElement>(key, this.lookup[key]);
    }
}

and Grouping:

internal sealed class Grouping<TKey, TElement> : IGrouping<TKey, TElement>
{
    private readonly TKey key;
    private readonly IEnumerable<TElement> elements;

    internal Grouping(TKey key, IEnumerable<TElement> elements)
    {
        this.key = key;
        this.elements = elements;
    }

    public TKey Key { get { return key; } }

    public IEnumerator<TElement> GetEnumerator()
    {
        return elements.GetEnumerator();
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }
}

So basically your first query will be:

var germanFamilies = families.ToFilteredLookup(family => IsNameGerman(family.Key));

This allows you to avoid re-flattening-filtering-ToLookup, or creating a new dictionary (and so hashing keys again).

For the second query the idea will be similar, you should just create a similar class not filtering for the whole IGrouping but for the elements of the IGrouping.

Just an idea, maybe it could not be faster than other methods :)