How do I make generic type and concrete type interchangeable?

Question

I'm writing an immutable binary tree class where all of the methods (Insert, Remove, RotateLeft, etc) return a new instance of a tree instead of modifying it in place.

I'm going to be creating lots of different implementations of tree: 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 tree node -- more than that, it is the same type as TreeType. If I can get the above base class working correctly, then 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 can't even get this far because the base class doesn't compile.

How do I pass an instance of AbstractBinaryTree into a method which takes a type TreeType?

Answer 1

I don't really have an answer - just a few hints that may be useful. I think this would work in a language that has a concept called self types (I can't find and good site to link!). Anyway, a self type means that you can declare an abstract base class (say A) and it can have a method that returns the self type. When creating an inherited class (say B) the uses of the self type will refer to B (which is interesting, because the base class didn't know about this class). For C# 4 fans, the self type is covariant.

Anyway, you could try searching for a way to emulate self types in C# using generics...

Another pointer is to an article that I've seen some time ago. As far as I remember, it used generics in a similar way as you do, so maybe it can give you some hint how to solve the problem.

• The Expression problem revisited by Mads Torgersen (now in the 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);
        }
}

---

With Balance() to cast

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 make things too hard for myself, but in any case the solution is really super simple:

AbstractBinaryTree already contains a 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 trying to return 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 implementation of AvlTree works out beautifully because we recursively insert into the tree on the way down, and balance the tree as the callstack unwinds.

If anyone can suggest a way that let's me reuse this instead of allocating a new object with a copy of its values, I'd like to hear it, but for right now this seems to work.