tags:

views:

137

answers:

3

I'm writing a bijective dictionary class, but I want to ensure the two generic types are not the same type for two reasons.

Firstly, I would like it to implement the IDictionary interface in both directions, but

public class BijectiveDictionary<TKey, TValue>
    : IDictionary<TKey, TValue>, IDictionary<TValue, TKey>

gives me " 'BijectiveDictionary<TKey,TValue>' cannot implement both 'IDictionary<TKey,TValue>' and 'IDictionary<TValue,TKey>' because they may unify for some type parameter substitutions " (which is understandable, but undesirable.)

Secondly, I would like to write an optimized solution if both types are the same.

public class BijectiveDictionary<TKey, TValue>
    : IDictionary<TKey, TValue> where TValue : TKey
{
    // Optimized solution
}

public class BijectiveDictionary<TKey, TValue>
    : IDictionary<TKey, TValue>, IDictionary<TValue, TKey> where TValue : !TKey
{
    // Standard solution
}

Is this possible?

If not, I can consider not implementing IDictionary, but I couldn't guarantee TValue this[TKey key] and TKey this[TValue key] would be different, which would be unfortunate.


It looks like the problem here is that when the two types are the same, the special cases arise.

My original intent was to create a dictionary which maps exactly one key to exactly one value, and visa versa, such that for every KeyValuePair<TKey, TValue>(X, Y), a KeyValuePair<TValue, TKey>(Y, X) exists as well.

When TKey = TValue, then this can be simplified down to a single dictionary:

public T this[T key]
{
    get { return this[key]; }
    set
    {
        base.Add(key, value);
        base.Add(value, key);
    }
}

In this case, you cannot Add(2,3); Add(3,4) because Add(2,3) maps 3 to 2 as well, and [3] would return 2.

However, Jaroslav Jandek's solution proposed using a second dictionary to do this for cases when TKey != TValue. And although this works wonderfully for those cases, (and what I decided to implement, in the end) it doesn't quite follow my original intent when TKey = TValue, by allowing Add(2,3); Add(3,4) to map a single key 3 to two values (2 in one direction, and 4 in the other,) though I believe strictly speaking is still a valid bijective function.

+2  A: 

In short, no. Re optimising it, one option there might be a strategy based on a static initializer, that chooses an appropriate concrete implementation for the same-type case, but otherwise; i.e.

public class BijectiveDictionary<TKey, TValue>
    : IDictionary<TKey, TValue>
{
    static readonly ISomeStrategy strategy;
    static BijectiveDictionary() {
        if(typeof(TKey) == typeof(TValue)) {
            strategy = ...
        } else {
            strategy = ...
        }
    }
}

but you will almost certainly find yourself using MakeGenericType and reflection to create the instance (but once created it should be fine - and you only do that once).

Marc Gravell
+3  A: 

How about this (different approach):

public class BijectiveDictionary<TKey, TValue> : Dictionary<TKey, TValue>
{
    public BijectiveDictionary<TValue, TKey> Reversed { get; protected set; }

    public BijectiveDictionary()
    {
        this.Reversed = new BijectiveDictionary<TValue,TKey>(true);
        this.Reversed.Reversed = this;
    }

    protected BijectiveDictionary(bool reversedWillBeSetFromTheCallingBiji) { }

    protected void AddRaw(TKey key, TValue value)
    {
        base.Add(key, value);
    }

    // Just for demonstration - you should implement the IDictionary interface instead.
    public new void Add(TKey key, TValue value)
    {
        base.Add(key, value);
        this.Reversed.AddRaw(value, key);
    }

    public static explicit operator BijectiveDictionary<TValue, TKey>(BijectiveDictionary<TKey, TValue> biji)
    {
        return biji.Reversed;
    }
}

and in code:

BijectiveDictionary<int, bool> a = new BijectiveDictionary<int, bool>();

a.Add(5, true);
a.Add(6, false);

Console.WriteLine(a[5]);// => True
Console.WriteLine(((BijectiveDictionary < bool, int>)a)[true]);// => 5
//or
Console.WriteLine(a.Reversed[true]);// => 5
Jaroslav Jandek
Note: the explicit cast `Console.WriteLine(((BijectiveDictionary < int, int>)a)[true]);` **won't work** when the types of sets are the same. It is for obvious reasons - I wanted to point it out anyway.
Jaroslav Jandek
A: 

Even if you could, what would be the output of this code?

var dict = new BijectiveDictionary<int, int>();

dict.Add(2,3);
dict.Add(3,4);

Console.WriteLine(dict[3]); // Do I get 2 or 4?

Maybe you can restructure your code in another way which isn't ambiguous?

Vilx-
You couldn't do this, because this would break the bijective nature of the dictionary (unless I'm misunderstanding bijection, which is possible.) `dict.Add(3,4);` would err because 3 is already mapped to 2.
Daniel Rasmussen
@Vilx-: Exactly, that is why I used another approach. With my example, you would get implicitly 4 and explicitly 2.
Jaroslav Jandek
@Daniel Rasmussen: 3 is not mapped to 2. 3 is mapped to 4. You have to understand that `3 from set A` is different from `3 from set B`.My examply specifically differentiates between the 2 sets (detectable by a reference pointer).
Jaroslav Jandek
Again, perhaps I misunderstand bijection, but my belief is that for all values `f(X) = Y`, then `g(Y) = X`. Therefore, 3 *is* mapped to 4.
Daniel Rasmussen
@Daniel Rasmussen Yes, you are right. But consider this: In my example if f(2)=3, then g(3)=2. And, if f(3)=4, then g(4)=3. No conflict with your definition as you can see. But since `dict[3]` does not specify whether you want `g(x)` or `f(x)`, you can't really pick the right value. If the types were different you could infer from them which one you want, but in my example I deliberately made the types equal.
Vilx-
@Daniel Rasmussen: Again, you have to understand that it is an operation on sets => `f(3) = 4` and `f(3) = 2`. It looks like it is wrong, it is not. You should really see it as: `f(X3) = Y4` and `f(Y3) = X2`, therefore it is a valid bijection.For it to work you would **have to** specify the bijection mapping explicitly (which I do), because .NET does not "see" the difference between X3 and Y3 (3 from different sets). So **Vilx-'s** point is very much correct - it does not provide a solution, though.Btw. my code works for any scenario and IMHO it is much more intuitive than the other ways.
Jaroslav Jandek
Anyway, such code wouldn't even compile if both indexers were declared...
Jaroslav Jandek
See my comments, edited in above.
Daniel Rasmussen