How to make an intrusive tree class in C# use generics?

Question

In C# I have an intrusive tree structure that looks like this:

public abstract class Node
{
    Container parent;
    Node nextNode;
    Node previousNode;

    public abstract class Container : Node
    {
        Node firstChild;
        Node lastChild;
    }
}

The various objects that can be added to the tree inherit from either Node or Container depending on whether they can have children or not.

By making Container an inner class it means that it can access the private members in Node for managing the container's list of children.

This is all well and good. But now I wish to make it generic so that I can reuse it while maintaining type safety - basically moving all the tree functionality to a generic class above Node and another between Node and Container. Here's a rough design of what I'm trying to do:

public abstract class GenericNode<Node, Container>
    where Node : GenericNode<Node, Container>
    where Container : GenericNode<Node, Container>.GenericContainer
{
    Container parent;
    Node nextNode;
    Node previousNode;

    public abstract class GenericContainer : Node
    {
        Node firstChild;
        Node lastChild;
    }
}

Which, of course, doesn't work because you can't make GenericContainer inherit from Node (compiler error CS0689). Even if I drop the inner class requirement (say, by using internal and just being careful in my own library) I still can't figure out a design that doesn't run into the same problem (and error).

(I didn't think I would have to, but just to spell it out: I am not trying to "fix" the compile error, nor am I looking for a simple tree implementation. This is a container design question.)

And so now I'm a bit stumped. Does anyone have any better ideas about how to design this thing?

Edit: Be sure to take a look at this answer, which is another stab at the design, that attempts to use extension methods to avoid the problem of "injecting" a class into the inheritance hierarchy (but unfortunately doesn't fully work).

Answer 1

Following your extension method approach, what if you define the inheritance constraint (between Node and Container) on an interface instead, and decorate container classes with the interface.

{
    MyNode n = new MyNode();
    var c = new MyNode.MyContainer();
    c.AddChild(n);

    MySubNode s = new MySubNode();
    c.AddChild(s);

    OtherNode o = new OtherNode();
    o.AddChild(o);

    //compiler doesn't allow this, as you'd expect:
    //c.AddChild(o);
}        

public interface IContainer<TContainerType, TNodeType>
    where TNodeType : GenericNode<TContainerType, TNodeType>
    where TContainerType : TNodeType, IContainer<TContainerType, TNodeType>
{
}

public static class ContainerExtensions
{
    public static void AddChild<TContainerType, TNodeType>(this IContainer<TContainerType, TNodeType> self, TNodeType node)
        where TNodeType : GenericNode<TContainerType, TNodeType>
        where TContainerType : TNodeType, IContainer<TContainerType, TNodeType>
    {
        GenericNode<TContainerType, TNodeType>.AddChild(self as TContainerType, node);
    }
}

public class GenericNode<TContainerType, TNodeType>
    where TNodeType : GenericNode<TContainerType, TNodeType>
    where TContainerType : GenericNode<TContainerType, TNodeType>
{
    TContainerType parent;
    TNodeType nextNode;
    TNodeType previousNode;

    // Only used by Container
    TNodeType firstChild;
    TNodeType secondChild;

    internal static void AddChild(TContainerType container, TNodeType node)
    {
        container.firstChild = node;
        node.parent = container;
    }
}

public class MyNode : GenericNode<MyContainer, MyNode>
{        
}

public class MyContainer : MyNode, IContainer<MyContainer, MyNode>
{
}

public class MySubNode : MyNode
{
}

public class OtherNode : GenericNode<OtherNode, OtherNode>, IContainer<OtherNode, OtherNode>
{
}