How to make interchangeable the general type and type of concrete?

Question

I am writing an unshakable binary tree class in which all methods (Insert, Remove, RotateLeft, etc.) return a new instance of the tree instead of changing it.

I am going to create many different tree implementations: Avl tree, red-black tree, splay tree, etc. I have the following:

public class AbstractBinaryTree<TreeType, T> where TreeType : AbstractBinaryTree<TreeType, T> where T : IComparable<T> { protected abstract TreeType CreateNode(TreeType left, T value, TreeType right); protected abstract T Value { get; } protected abstract TreeType Left { get; } protected abstract TreeType Right { get; } protected abstract bool IsNil(); public TreeType Insert(T item) { if (this.IsNil()) { return CreateNode(this, item, this); // ^ doesn't compile, can't convert type // AbstractBinaryTree<TreeType, T> to type TreeType } else { int compare = item.CompareTo(this.Value); if (compare < 0) { return CreateNode(this.Left.Insert(item), this.Value, this.Right); } else if (compare > 0) { return CreateNode(this.Left, this.Value, this.Right.Insert(Value)); } else { return this; // ^ doesn't compile, can't converrt type // AbstractBinaryTree<TreeType, T> to type TreeType } } } } 

The idea here is that AbstractBinaryTree is a node tree - moreover, it is the same type as TreeType . If I can use the above base class correctly, I can write something like this:

 public class AvlTree<T> : AbstractBinaryTree<AvlTree<T>, T> { public override AvlTree<T> Insert(T item) { return Balance(base.Insert(item)); } } 

so that my Insert method returns AvlTree<T> instead of AbstractBinaryTree<AvlTree<T>, T> . However, I cannot even get this far, because the base class does not compile.

How to pass an instance of AbstractBinaryTree to a method that accepts a TreeType type?

Answer 1

I have no answer - just a few tips that might be helpful. I think this will work in a language that has a concept of type self (I cannot find a good site for the link either!). In any case, a type of self means that you can declare an abstract base class (say A ), and it can have a method that returns a type of self. When creating an inherited class (for example, B ), using the self type will refer to B (which is interesting because the base class did not know about this class). For C # 4 fans, the self type is covariant.

Anyway, you can try to find a way to emulate self types in C # using generics ...

Another pointer to an article I saw some time ago. As far as I remember, he used generics the same way you did, so maybe he can give you some idea of ​​how to solve the problem.

• Expression issue revised by Mads Torgersen (now on C # team!)

Answer 2

Use AbstractBinaryTree<TreeType, T>

  public abstract class AbstractBinaryTree<TreeType, T> where TreeType : AbstractBinaryTree<TreeType, T> where T : IComparable<T> { protected abstract TreeType CreateNode(AbstractBinaryTree<TreeType, T> left, T value, AbstractBinaryTree<TreeType, T> right); protected abstract T Value { get; } protected abstract TreeType Left { get; } protected abstract TreeType Right { get; } protected abstract bool IsNil(); public virtual AbstractBinaryTree<TreeType, T> Insert(T item) { if (this.IsNil()) { return CreateNode(this.Left, item, this.Right); // ^ doesn't compile, can't convert type // AbstractBinaryTree<TreeType, T> to type TreeType } else { int compare = item.CompareTo(this.Value); if (compare < 0) { return CreateNode(this.Left.Insert(item), this.Value, this.Right); } else if (compare > 0) { return CreateNode(this.Left, this.Value, this.Right.Insert(Value)); } else { return this; // ^ doesn't compile, can't converrt type // AbstractBinaryTree<TreeType, T> to type TreeType } } } } public class AvlTree<T> : AbstractBinaryTree<AvlTree<T>, T> where T : IComparable<T> { public override AbstractBinaryTree<AvlTree<T>, T> Insert(T item) { return base.Insert(item); } } 

---

Using the Balance () function to broadcast

 private AvlTree<T> Balance(AbstractBinaryTree<AvlTree<T>, T> item) { return (AvlTree<T>)item; } public override AbstractBinaryTree<AvlTree<T>, T> Insert(T item) { return Balance(Insert(item)); } 

Answer 3

Oh wow, I'm doing too much for myself, but in any case, the solution is really super simple:

AbstractBinaryTree already contains the Left, Value, and Right property, so I can just create a copy of the current node using CreateNode(this.Left, this.Value, this.Right) instead of returning this :

 public abstract class AbstractBinaryTree<TreeType, T> where TreeType : AbstractBinaryTree<TreeType, T> where T : IComparable<T> { protected abstract TreeType CreateNil(); protected abstract TreeType CreateNode(TreeType left, T value, TreeType right); protected abstract T Value { get; } protected abstract TreeType Left { get; } protected abstract TreeType Right { get; } protected abstract bool IsNil(); public virtual TreeType Insert(T item) { if (this.IsNil()) { // can't return 'this', so just creating a new nil node TreeType nil = CreateNil(); return CreateNode(nil, item, nil); } else { int compare = item.CompareTo(this.Value); if (compare < 0) { return CreateNode(this.Left.Insert(item), this.Value, this.Right); } else if (compare > 0) { return CreateNode(this.Left, this.Value, this.Right.Insert(Value)); } else { // can't return 'this', so just creating a new node with a // copy of the same values return CreateNode(this.Left, this.Value, this.Right); } } } } public class AvlTree<T> : AbstractBinaryTree<AvlTree<T>, T> { public override AvlTree<T> Insert(T value) { return Balance(base.Insert(value)); } } 

The AvlTree implementation works great because we recursively insert into the tree along the way down and balance the tree when the call breaks.

If anyone can suggest a way that allows me to reuse this instead of highlighting a new object with a copy of its values, I would like to hear it, but now it works.