1

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?

Improve this question
2
  • An alternative would be to provide a Func<T, int> or IComparer<T>/IEqualityComparer<T> as an argument to the constructor, much like Dictionary does. Commented Apr 7, 2018 at 3:04
  • 1
    Note that there is no "nested" type in your scenario. A nested type is something like class C { class D {} } where C.D is now a class. Commented Apr 7, 2018 at 4:16

2 Answers 2

Reset to default
6

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/

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

Thanks for your answer! It seems that the problem in my code is the mixed usage of non-generic IComparable and generic IComparable<T>... Also thanks for your suggestion in the last paragraph! I really should learn this language more thoroughly...
0

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.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.