Generic Constraints: T != V ??

[mskeel]

Let's say I've got a special collection where an item is both a key and a value such that two items are partnered in a unique 1:1 relationship. Say I want to make this collection generic.

 

Here's part of the interface I'd like to use to make this partnered relationship possible:

public interface IPartnerCollection<T, V>
{
  T this[V item] { get; set; }

  V this[T item] { get; set; }

  void Add(T, V);

  // ...

}

This works well and good so long as T and V do not have the same type. The default accessor works as planned. If, however T and V have the same type, an ambiguity is created as to which default property to use. The same would be the case for any overloaded methods one taking a parameter of type T, the other V. This would not be the case with other methods, such as Add in this case.

 

I do get a compile time warning, as expected, but only after I've made the declaration. For example, say I have a class that implements the above interface called PartnerCollection<T, V>.

//no compile errors
PartnerCollection<string, int> good = new PartnerCollection<string, int>();
good.Add("YO", 55);
Console.WriteLine("The partner of 55 is: " + good[55]);
Console.WriteLine("The partner of YO is: " + good["YO"].ToString());

//compile errors for ambiguous method call
PartnerCollection<string, string> bad = new PartnerCollection<string, string>();  //no error at declaration
bad.Add("YO", "55"); //no error when using an unambiguous method
Console.WriteLine("The partner of 55 is: " + bad["55"]); //error ONLY when you USE an ambiguous method
Console.WriteLine("The partner of YO is: " + bad["YO"]);

This makes sense...sort of. It's good to see that you can't create Generics remain mostly internally consistent, disallowing an ambiguous method. It's a little disturbing that the only way to know this is when you use the method. The only advantage I see here is that you still get a compile time error instead of a run time error.

 

My Question: Is there a way to know whether there will be an ambiguity at declaration instead of only when you use a potentially ambiguous method? In other words, is there a way I can put a constraint on a generic class such that T and V cannot have the same type?

Edited July 27, 2006 by mskeel

[Wile]

Havent tried this myself, but you can use the 'where' clause to contstraint a type. I think this would make the declaration something like:

[CS]

public interface IPartnerCollection<T, V>

where T : MyInterface1

where V : MyInterface2[/CS]

In this case whatever object is used as T, it must inherit MyInterface1, V must inherit MyInterface2.

 

see here for more information: http://msdn2.microsoft.com/en-us/library/6b0scde8.aspx

[snarfblam]

That is a great solution when the type parameters will be classes of your own creation: you can guaruntee that even if the two type parameters are the same, they will be able to exhibit two different behaviors as needed, but I would imagine that alot of explicit casting would be needed for the sake of overload resolution, and then there is the bigger issue of a possible need of pre-existing classes that can't comply with the constraints.

[mskeel]

...then there is the bigger issue of a possible need of pre-existing classes that can't comply with the constraints.

Bingo.

 

I need at least 10 characters to post. Becuase a quote doesn't count...?

[snarfblam]

Bingo. Because a quote doesn't count. I guess the logic is that a quote is something someone else said and doesn't count as your own input.

 

I think that you are stuck. Is the issue that you just want your code to be tidy and sound, or does the conflict actually pose a good probability of manifesting itself?

[MrPaul]

Stuck indeed!

 

I think that you are stuck.

 

I am inclined to agree. It's interesting that the following does not work:

 

    public interface IPartnerCollectionTypeCheck<T>
   {}

   public class PartnerCollection<T,V>
       : IPartnerCollectionTypeCheck<T>, IPartnerCollectionTypeCheck<V>                 
   {

       public void BadMethod(T t)
       {}
       public void BadMethod(V v)
       {}

   }

 

The compiler rightly moans that if T and V were the same type, PartnerCollection would be implementing the same interface twice. It is slightly odd then that it doesn't complain in a similar manner about possible duplicate methods.

 

The constraints offer no help either.

 

So you have a choice - either accept that in some situations there will be ambiguity and errors, or ensure that there are no such overloads, which would require you to make some distinction between which partner is which (as in a key/value relationship).

 

Good luck :cool:

[mskeel]

I figured as much.

 

That is an interesting find, MrPaul. Probably the best solution would be to add some kind of distinction between the two methods other than the types of the parameters they accept, as you have suggested. It won't be as tight of an interface, but it will ensure that you can use the class when you have a string to string partner lookup (for example). I'll play with it some more and see if I can come up with a better solution, but I think making the interface a little more robust will be better than disallowing items of the same type. Then again, I�m only using it for a string to int lookup, so maybe I won�t worry about it for now.

 

Generics are pretty cool, but there are a lot of subtle things to learn about them still. Thanks for the help, guys.

[Mike_R]

Ah, this is a really nice one, I love nonsense like this, LOL. I'm sorry I missed it. (I was away.)

 

I have nothing intelligent to add, however. You seem to want perfect symmetry here with the pairs, so the Overloads makes sense. However, if you were willing to bend your approach slightly, you could name the accessors 'GetKey' and 'GetValue' methods instead.

 

What's allowing you to do the reverse-lookup? Are you wrapping two Dictionaries internally within one collection?

[mskeel]

What's allowing you to do the reverse-lookup? Are you wrapping two Dictionaries internally within one collection?

Two Dictionary<Tkey, TVal>'s, yes. An item is a key in one Dictionary and a value in the other (where the value in the first Dictionary is now the key) allowing two items to be "partnered" such that, for example, when you ask for 5, you'll get "five" and when you ask for "five" you get 5.

 

Since the collection can only hold an item once (because it is both a key and a value) I could have the default property return an object, but I felt that kind of defeated the purpose of using a Generic in the first place.

 

The other option is to introduce something like the concept of a "right hand partner" and "left hand partner" but seeing as how it's completely arbitrary that might make things more confusing than it needs to be. I think I would still end up having to put extra cases in to mitigate the issue of same typed items in case the user asks for the "right hand partner" when the item is really on the "left" and vice versa.

 

Maybe generics just won't work in this case. Or maybe they'll work but it will just have to be with the caveat that the same types can't be used.

[MrPaul]

An ugly solution

 

This is fairly nasty but perhaps worth a look:

 

    public class PartnerCollection<T,V>           
   {
       //Fields
       private Dictionary<T,V>     m_tv;
       private Dictionary<V,T>     m_vt;

       //Constructors
       public PartnerCollection()
       {
           m_tv = new Dictionary<T,V>();
           m_vt = new Dictionary<V,T>();
       }

       public void GetPartner(T t, out V v)
       {
           if (typeof(T) == typeof(V)) {
               Console.WriteLine("Using t to find v, checking both dictionaries");
           } else {
               Console.WriteLine("Using t to find v, checking just <T,V> dictionary");
           }

           //Need an assignment
           m_tv.TryGetValue(t, out v);
       }

       public void GetPartner(out T t, V v)
       {
           if (typeof(T) == typeof(V)) {
               Console.WriteLine("Using v to find t, checking both dictionaries");
           } else {
               Console.WriteLine("Using v to find t, checking just <V,T> dictionary");
           }

           //Need an assignment
           m_vt.TryGetValue(v, out t);
       }
   }

 

I have tested this and it seems to work. However, it means that the partner retrieval must be its own method call, so cannot be used inline.

 

Best I could think of. :-\

Edited July 30, 2006 by MrPaul

[MrPaul]

A working version

 

        public void GetPartner(T t, out V v)
       {
           T   tempt;
           V   tempv;

           //Try <T,V> dictionary
           if (!m_tv.TryGetValue(t, out v) && (typeof(T) == typeof(V))) {
               //Try <V,T> dictionary
               tempv = (V) ((object) t);
               if (m_vt.TryGetValue(tempv, out tempt))
                   v = (V) ((object) tempt);
           }
       }
       public void GetPartner(out T t, V v)
       {
           T   tempt;
           V   tempv;

           //Try <V,T> dictionary
           if (!m_vt.TryGetValue(v, out t) && (typeof(T) == typeof(V))) {
               //Try <T,V> dictionary
               tempt = (T) ((object) v);
               if (m_tv.TryGetValue(tempt, out tempv))
                   t = (T) ((object) tempv);
           }
       }

 

Good luck :cool:

[mskeel]

That worked like a charm. Thanks, MrPaul. I did rearrange the methods so that they returned a bool to show success/failure, but everything worked right out of the box, thanks a lot.

 

I added these methods in with the previous overloads for a total package that will cover both situations. For the average case where both types will be different, the overloads are available, for the outliers, the slightly more cumbersome (in my opinion) GetPartner methods are available, though there is nothing preventing those from being used all the time. It seems like a nice solution and I feel pretty good about it.

 

It's kind of funny that you have to cast a variable of type T to an object before you can cast it to V even though you know that both T and V are the same type, but I guess that's the price you pay to get generic strong typing.

[snarfblam]

MrPaul, where do you keep getting these clever solutions from?

 

It's kind of funny that you have to cast a variable of type T to an object before you can cast it to V even though you know that both T and V are the same type, but I guess that's the price you pay to get generic strong typing.

Unfortunately, the compiler can't be that insightful. It's too bad that the compiler can't infer those logical details, but that would be asking for alot.

[MrPaul]

Wait, there's more!

 

Heh heh heh, I'm not done with this yet!

 

The GetPartner method is indeed cumbersome, due to the fact that it cannot be used inline. So, can we get around this? Yes we can. With the following approach, for cases where we want T and V to be the same type, there is a specialised derived PartnerCollection. For generic methods/classes which use T and V, the derived collection will still work, but where the code "knows" the collection is just one type (ie where it is defined), the derived collection prevents errors.

 

Phew, that doesn't look like it makes much sense on its own. Lets have a look. First up, the old PartnerCollection<T,V>:

 

    public class PartnerCollection<T,V>
   {
       //Fields
       protected Dictionary<T,V>     m_tv;
       protected Dictionary<V,T>     m_vt;

       //Properties
       public T this[V item]
       {
           get {return m_vt[item];}
           set {
               m_vt[item] = value;
               m_tv[value] = item;
           }
       }
       public V this[T item]
       {
           get {return m_tv[item];}
           set {
               m_tv[item] = value;
               m_vt[value] = item;
           }
       }

       //Constructors
       public PartnerCollection()
       {
           m_tv = new Dictionary<T,V>();
           m_vt = new Dictionary<V,T>();
       }
   }

 

Nothing new here. Now for the derived PartnerCollection<T>:

 

    public class PartnerCollection<T> : PartnerCollection<T,T>
   {
       //Properties
       public new T this[T item]
       {
           get {
               T ret;
               if (m_tv.TryGetValue(item, out ret))
                   return ret;
               else
                   return m_vt[item];
           }
           set {
               m_tv[item] = value;
               m_vt[value] = item;
           }
       }
   }

 

By overriding the indexer method, code which explicitly use this kind of collection will not have ambiguous methods. And now, the test code:

 

    public class TestMyPartners
   {
       public static void Main(string[] cmdline)
       {
           //This method knows that T and V are the same type, so uses
           //the derived PartnerCollection and all is well

           PartnerCollection<int> bad;
           bad = new PartnerCollection<int>();

           bad[10] = 20;
           Console.WriteLine(bad[20]); //Shows 10


           //1-type PartnerCollection gracefully morphs into 2-type
           CluelessMethod<int,int>(bad, 99, 101);

           //Look ma, it worked!
           Console.WriteLine(bad[99]); //Shows 101

           Console.ReadLine();
       }



       public static void CluelessMethod<T,V>(PartnerCollection<T,V> pc, T tval, V vval)
       {
           //This method doesnt know what T and V are, but this is ok, because
           //even if T == V, there will not be an error, since the method knows
           //which of the overloads to call.

           pc[vval] = tval;
       }

   }

 

Now this is some code we can be really proud of! :cool:

[PlausiblyDamp]

A bit late to the discussion but http://blogs.msdn.com/ericlippert/archive/2006/04/05/569085.aspx discusses a similar problem when only one of the 2 overloads is generic. The outcome is less than ideal...

[Mike_R]

That's a really interesting discussion, PD.

 

The followup, here, shows that they were basically forced to leave this conflict as is, or certainly for now.