IBiLookup and Bilookup: key and value "dictionary" lookup

Question

I needed a more robust dictionary-like structure to obtain:

values by providing a key (default dictionary behavior);
keys by providing a value (not so much trivial).

Also, I wanted to expand this dictionary-like structure's functionality so that a key could be associated with multiple values.

Through this discussion, this answer and this other one provided the tools to implement that. I decided to remove the "access by index" from the BiDictionary (Jon Skeet's answer) since the ambiguity would happen more often than I would like (for example, when mapping strings into strings). The dictionary-like "structure" that I came up with is:

using System.Collections.Generic;

public interface IBiLookup<TLeft, TRight>
{
    IDictionary<TLeft, ICollection<TRight>> LeftToRight { get; }
    IDictionary<TRight, ICollection<TLeft>> RightToLeft { get; }

    bool TryGetByLeft(TLeft left, out ICollection<TRight> rights);
    bool TryGetByRight(TRight right, out ICollection<TLeft> lefts);

    void Add(TLeft left, TRight right);
}

public class BiLookup<TLeft, TRight> : IBiLookup<TLeft, TRight>
{
    public IDictionary<TLeft, ICollection<TRight>> LeftToRight
    {
        get { return this.leftToRight; }
    }
    public IDictionary<TRight, ICollection<TLeft>> RightToLeft
    {
        get { return this.rightToLeft; }
    }

    public bool TryGetByLeft(TLeft left, out ICollection<TRight> rights)
    {
        return LeftToRight.TryGetValue(left, out rights);
    }
    public bool TryGetByRight(TRight right, out ICollection<TLeft> lefts)
    {
        return RightToLeft.TryGetValue(right, out lefts);
    }

    public void Add(TLeft left, TRight right)
    {
        AddLeftToRight(left, right);
        AddRightToLeft(right, left);
    }

    private void AddLeftToRight(TLeft left, TRight right)
    {
        ICollection<TRight> rights;

        // 1) Is there an entry associated with the "left" value?
        // 2) If so, is the "right" value already associated?
        if (!TryGetByLeft(left, out rights))
        {
            // Then we have to add an entry in the leftToRight dictionary.
            rights = new List<TRight> { right };                
        }
        else
        {
            // So there are entries associated with the "left" value.
            // We must verify if the "right" value itself is not there.
            if (((List<TRight>)rights).FindIndex(element => element.Equals(right)) < 0)
            {
                // We don't have that association yet.
                rights.Add(right);
            }
            else
            {
                // The value is already in the list: do nothing.
                return;
            }
        }

        LeftToRight[left] = rights;
    }
    private void AddRightToLeft(TRight right, TLeft left)
    {
        ICollection<TLeft> lefts;

        // 1) Is there an entry associated with the "right" value?
        // 2) If so, is the "left" value already associated?
        if (!TryGetByRight(right, out lefts))
        {
            // Then we have to add an entry in the leftToRight dictionary.
            lefts = new List<TLeft> { left };
        }
        else
        {
            // So there are entries associated with the "right" value.
            // We must verify if the "right" value itself is not there.
            if (((List<TLeft>)lefts).FindIndex(element => element.Equals(left)) < 0)
            {
                // We don't have that association yet.
                lefts.Add(left);
            }
            else
            {
                // The value is already in the list: do nothing.
                return;
            }
        }

        RightToLeft[right] = lefts;
    }

    #region Fields

    private IDictionary<TLeft, ICollection<TRight>> leftToRight = new Dictionary<TLeft, ICollection<TRight>>();
    private IDictionary<TRight, ICollection<TLeft>> rightToLeft = new Dictionary<TRight, ICollection<TLeft>>();

    #endregion
}

I'm worried if splitting the Add(...) method into two, more specific methods, is a good implementation, since the BiLookup class would be extensively used and performance is something to keep in mind. Also, the purpose of this thread is to discuss if the interface and class implementations are as good as they could be, or what could be improved on them.

If I save both the Interface and the "deafult" implementation to a Class Library project, is the design good enough to be reused?

If you want to discuss performance it is a good idea to specify requirements. It looks like you don't care about Add performance, but want O(1) for both lookups. — Alexei Levenkov, Mar 05 '13 at 17:20
You are right, but since the requirements are somewhat "loose", I only wanted to make sure not to add unnecessary overhead to a simple (and overly used) Add(...) operation. — Victor Lacorte, Mar 05 '13 at 17:23

score 0 · Accepted Answer · answered Mar 05 '13 at 17:29

0

There is no way to see if "design good enough to be reused" without actually using it. You need to try to use your code in several different ways (all unit tests count as one) to see if it makes sense and encourages writing readable code.

If you don't have any particular requirements (performance or otherwise) than just make sure your unit test coverage for the code is good, all test passed and your expected usage scenario is covered by tests.

Notes on code: casts (i.e. ((List<TLeft>)lefts)) look unnecessary. FindIndex calls (linear search with O(number_of_items)) does not look at home in performance sensitive code.

answered Mar 05 '13 at 17:29

Alexei Levenkov

98,904
14
127
179

I don't have any experience with automated test (Unit Test, maybe?) but as far as my needs are the issue then yes, the way the code looks right now already suffices. Maybe what I'm asking here is too much since, as you have already stated, only through usage one can qualify a code as being good or not. I only wanted to make sure that the overall design is not too much flawed, and also discuss it since every now and then someone asks for this kind of solution. About the unnecessary cast, what would you suggest as another approach to iterate the list? – Victor Lacorte Mar 05 '13 at 17:59
On cast: [Any](http://msdn.microsoft.com/en-us/library/bb534972.aspx) will have the same performance. Also when you tried to use your code see if you really need `ICollection` - there is a good chance `IEnumerable` will be enough (may simplify implementation by allowing to use `Dictionary` for both indexes). – Alexei Levenkov Mar 05 '13 at 18:18
Thank you, IEnumerable makes more sense here. Using extension method Any (System.Linq) partially solves the issue since a cast would still be required before adding an element to an IEnumerable. – Victor Lacorte Mar 05 '13 at 19:38
Well, just figured that a cast to `ICollection` before performing an Add is much better than limiting the amount of objects that may use both classes (when debating `IEnumerable` vs `ICollection`). Thanks for the help Alexei, I'll accept your answer for now :) – Victor Lacorte Mar 05 '13 at 21:42

IBiLookup and Bilookup: key and value "dictionary" lookup

1 Answers1