CODEWITHSUNDEEP
c#genericsinheritancenested-generics
Chlorie
Chlorie

Reputation: 839

How to inherit a generic class from a nested generic class in C#

I was doing my homework and got stuck in some problems with generics and inheritance.

I have a generic red-black tree class, since it's red-black tree its keys should be comparable, so 

public class RedBlackTree<T> where T : IComparable<T>

And then I want another class, let's say, an interval tree, which is an augmented version of red-black tree. So I defined the interval like this:

public class Interval<T> : IComparable where T : IComparable<T>

and since interval tree is indeed a red-black tree with intervals as its keys but just with more specific methods, I defined the class like this:

public class IntervalTree<T> : RedBlackTree<Interval<T>> where T : IComparable<T>

But it won't let me do this, it says something like "cannot implicitly convert Interval<T> to System.IComparable<Interval<T>>", but I also can't write something like where Interval<T> : IComparable<Interval<T>>.

How would I do things like this in C#, or if there's no way to do this inheritance in C# what other templates should I use?

Upvotes: 1

Views: 2216

Answers (2)

Eric Lippert
Eric Lippert

Reputation: 659964

Let's take it apart. We'll stop using T for everything, because that gets confusing.

class RedBlackTree<RBTValue> where RBTValue : IComparable<RBTValue>

OK, so every RBTValue that is used to construct RedBlackTree<> must be an IComparable<RBTValue>.

You wish to say

 RedBlackTree<Interval<T>>

for some T at some point. What do we then know? Interval<T> is being used for RBTValue, and therefore Interval<T> must be known to be IComparable<Interval<T>>.

Therefore the definition of Interval<> needs to be:

class Interval<IValue> : IComparable<Interval<IValue>>

Now, is it also the case that any IValue needs to be IComparable<IValue>? If yes, then we need a constraint:

class Interval<IValue> : IComparable<Interval<IValue>> 
where IValue : IComparable<IValue>

Make sure this is clear. This is saying two things, (1) that an interval is comparable to another interval, and (2) that the values in an interval are comparable to other values.

Now we wish to define an interval tree.

class IntervalTree<ITValue> : RedBlackTree<Interval<ITValue>>
where ITValue : IComparable<ITValue>

Does this satisfy our needs? Interval<IValue> requires that IValue implement IComparable<IValue>. ITValue implements IComparable<ITValue> via the constraint, so the requirement is satisfied.

RedBlackTree<RBTValue> requires that RBTValue be IComparable<RBTValue>. Interval<ITValue> implements IComparable<Interval<ITValue>>, so that's also good, and we're all set.

That all said: you might consider instead implementing IntervalTree<> with an RBT as a member rather than as a base class. Is there ever a case where you are going to be treating interval trees polymorphically with red black trees? If not, there's no need to expose the implementation detail in the public surface.

Finally, these sorts of types can get very confusing. For some more thoughts on ways in which this pattern can be abused far more horribly, see

https://blogs.msdn.microsoft.com/ericlippert/2011/02/03/curiouser-and-curiouser/

Upvotes: 6

Dweeberly
Dweeberly

Reputation: 4777

The error you are getting is the following:

Compilation error (line xx, col yy): The type 'Program.Interval<T>' cannot be used as type parameter 'T' in the generic type or method 'Program.RedBlackTree<T>'. There is no implicit reference conversion from 'Program.Interval<T>' to 'System.IComparable<Program.Interval<T>>'.

You need to take the error apart and think about what it is telling you. In this case you are declaring that IntervalTree inherits from RedBlackTree<Interval<T>>. However, you have specified that the generic T type for RedBlackTree must implement IComparable<T>. If you implement IComparable for Interval the error will go away. Interval must implement the interface used to constrict RedBlackTree.

Upvotes: 0

Related Questions