Thursday, 20 January 2011

C# BiDirectional Lookup

This seems to happen regularly: I start using a Dictionary to group data, only to find that at some stage I need to lookup from value to key again. As .NET has no birectional map, dictionary or lookup, handling this is always cumbersome, like trying to find out which kitchen junk drawer contains the screwdriver you need.

In my case I was building groups of financial transactions by creating a map keyed on group name. I matched each new transaction to each existing transaction to work out which was the closest match, based on some criteria, then added the new transaction to the same group as the closest match.

The problem here is that I needed to do a reverse lookup – also traversing each element of the group map to work out which group the closest match was in. It works, but it feels wrong.

One solution is to maintain both forward and lookup structures – which informed the bidirectional lookup workout presented below. That felt a little better – at least I was no longer completely abusing the dictionary every time I wanted to add something.

A little thought, though, showed that if I want to work out which group a new transaction should be in, then I should compare each transaction to some group criteria (not trade criteria) and add it to the closest matching group. As there’ll be fewer groups than trades, this should be quicker – and no reverse lookup needed.

In any event: just because a bidirectional lookup might be wrong in this case, doesn’t mean it’s always so, and working a simple one up isn’t an enormous task. And it makes a nice workout for the list.

Also: this is certainly not the only way of doing a bidirectional lookup; it really does depend on what you need. For a set of {first, second} pairs, I wanted to allow a second to map to multiple firsts, and vice versa.

Bit of a mix of styles as it's the result of a workout.

public class BiDiLookup<TFirst, TSecond>
{
    private IDictionary<TFirst, List<TSecond>> Forward
    {
        get;
        set;
    }

    private IDictionary<TSecond, List<TFirst>> Backward
    {
        get;
        set;
    }

    private BiDiLookup()
    {
    }

    public BiDiLookup(
                IDictionary<TFirst, List<TSecond>> forward, 
                IDictionary<TSecond, List<TFirst>> backward)
    {
        Forward = forward;
        Backward = backward;
    }

    public void Add(TFirst first, TSecond second)
    {
        // Consider what to do when adding an already-existing pair ..
        // Nice trick here courtesy Jon Skeet to reduce the number 
        // of lookups -- see also GetByFirst etc for comparison
        List<TSecond> secondList;
	if (!Forward.TryGetValue(first, out secondList))
        {
            secondList = new List<TSecond>();
            Forward[first] = secondList;
        }
        List<TFirst> firstList;
        if (!Backward.TryGetValue(second, out firstList))
        {
            firstList = new List<TFirst>();
            Backward[second] = firstList;
        }
        secondList.Add(second);
        firstList.Add(first);
    }

    private static List<TFirst> EmptyFirstList = new List<TFirst>();
    private static List<TSecond> EmptySecondList = new List<TSecond>();

    public List<TSecond> GetByFirst(TFirst first)
    {
        // Consider what to do if first doesn't exist yet -- return an empty list? return null?
        if (Forward.ContainsKey(first))
        {
            return Forward[first];
        }
        return EmptySecondList;
    }

    public List<TFirst> GetBySecond(TSecond second)
    {
        if (Backward.ContainsKey(second))
        {
            return Backward[second];
        }
        return EmptyFirstList;
   }

   public void Remove(TFirst first, TSecond second)
    {
        // Consider -- what if we want to just remove all instances of first, or second?
        List<TSecond> seconds = Forward[first];
        List<TFirst> firsts = Backward[second];
        Forward.Remove(first);
        foreach (var s in seconds)
        {
            Backward[s].Remove(first);
            if (Backward[s].Count == 0)
            {
                Backward.Remove(s);
            }
        }
        Backward.Remove(second);
        foreach (var f in firsts)
        {
            Forward[f].Remove(second);
            if (Forward[f].Count == 0)
            {
                Forward.Remove(f);
            }
        }
    }
}

3 comments:

Don Andre said...

The implementation looks nice, but there is a problem in Remove, especially when custom equality comparers are used in the dictionaries.

The lists don't use equality comparers to check which item to remove and then will probably not be able to remove the items when not the exact same reference is used in removing them.

e.g.
var f = new Dictionary(new T1EqualityComparer());
var b = new Dictionary(new T2EqualityComparer());

var fb = new BiDirectionalLookup(f, b);
fb.Add(new T1(1), new T2(2));
fb.Add(new T1(1), new T2(3));
fb.Remove(new T1(1), new T2(2));

The code would compile, but a) it would throw an error in line 87 saying that Forward doesn't contain T1(1) (as it has already been removed) and b) it would leave T1(1) in the backwards dictionary's list for T2(3).

AmonGwareth said...

I put this into use today. First, I appreciate the effort you put into it but while writing unit tests to surround it I think I stumbled upon some bugs. So, I rewrote the Add and Remove methods like so:

public void Add(TFirst first, TSecond second)
{
IEnumerable secondList;
if (!Forward.TryGetValue(first, out secondList))
{
secondList = new List();
Forward[first] = secondList;
}

IEnumerable firstList;
if (!Backward.TryGetValue(second, out firstList))
{
firstList = new List();
Backward[second] = firstList;
}

Forward[first] = secondList.Append(second);
Backward[second] = firstList.Append(first);
}

and

public void Remove(TFirst first, TSecond second)
{
IEnumerable secondList;
if (Forward.TryGetValue(first, out secondList))
{
if (secondList.Contains(second))
{
secondList.ToList().Remove(second);
if (secondList.Any())
Forward[first] = secondList;
else
Forward.Remove(first);
}
else
Forward.Remove(first);
}

IEnumerable firstList;
if (Backward.TryGetValue(second, out firstList))
{
if (firstList.Contains(first))
{
firstList.ToList().Remove(first);
if (firstList.Any())
Backward[second] = firstList;
else
Backward.Remove(second);
}
else
Backward.Remove(second);
}
}

Think I'll continue to tinker with it. But I wanted to thank you for the initial solution.

Tim Barrass said...

This is great, thanks for the feedback both! And apologies for the lack of response -- it's much appreciated!