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

My solution looks like:

public class Tree<T> : ITree<T> where T : INode{
    public T RootNode { get; private set; }
    public Tree(T rootNode){
        RootNode = rootNode;
    }
}

public interface ITree<T> where T : INode{
    T RootNode { get; }
}

public interface INode{
    INode Parent { get; }
    List<INode> Children { get; }
}

internal class Node : INode{
    public INode Parent { get; private set; }
    public List<INode> Children { get; private set; }
    public Node( INode parent, List<INode> children = new List<INode>()){
        Parent = parent;
        Children = children;
    }
}

HTH.

NOTE: Additional validations like ParentNode != null for child nodes; node belongs to the same parent to which it is being added etc. not implemented in this sample.

Answer 2

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>
{
}

Answer 3

(Don't do this - leaving it in to help prevent anyone else from dropping the extension by accident too ;) )

Does this help?

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

    public abstract class GenericContainer<Branch> where Branch: GenericNode<Node, Container> 
    {
        private Leaf firstChild;
        private Leaf secondChild;
    }
}

Also compiles in 3.5. Branch is restricted to being a Node by the GenericNode declaration.

Answer 4

I thought I had a working solution, but it doesn't fully work:

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

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

    public static class ContainerHelpers
    {
        public static void AddChild(Container c, Node n)
        {
            c.firstChild = n; // not a real implementation ;)
            n.parent = c;
        }
    }
}

// EDIT: This does not work correctly! (see example below)
public static class GenericNodeExtensionMethods
{
    public static void AddChild<Node, Container>(this Container c, Node n)
        where Node : GenericNode<Node, Container>
        where Container : Node
    {
        GenericNode<Node, Container>.ContainerHelpers.AddChild(c, n);
    }
}

//
// Example Usage
//

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

public class MyContainer : MyNode
{
}

public class MySubNode : MyNode
{
}

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


class Program
{
    static void Main(string[] args)
    {
        MyNode n = new MyNode();
        MyContainer c = new MyContainer();
        c.AddChild(n);

        MySubNode s = new MySubNode();
        //
        // This does not work because it tries to fill the generic in the
        // extension method with <MySubNode, MyContainer>, which does not
        // fulfil the constraint "where Container : Node".
        //
        //c.AddChild(s);

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

While the extension method method of exposing methods only for Container does not work correctly, structuring the GenericNode class like this has the nice property that Container and Node can be the same class - giving the end-user the option of having a specific type in the tree that can have children, or allowing all types to have children.

(Also for some reason the extension method doesn't show up in IntelliSense in VC# 2008 SP1, although it does in 2010.)

Still looking for a better solution...

Answer 5

One option is to insulate the client from the actual structure of the tree entirely, by not exposing Node objects directly:

public interface ITagged<T>
{
    T Tag { get; set; }
}

public sealed class Tree<T>
{
    //All Tree operations are performed here (add nodes, remove nodes, possibly move nodes, etc.)
    //Nodes are only exposed as 'ITagged<T>', such as:
    public ITagged<T> Root { get; private set; }

    public IEnumerable<ITagged<T>> GetChildren(ITagged<T> item)
    {
        //Cast to Container and enumerate...
    }

    //Several other tree operations...

    private class Node : ITagged<T>
    {
        Container parent;
        Node nextNode;
        Node previousNode;

        public T Tag { get; set; }
    }

    private class Container : Node
    {
        Node firstChild;
        Node lastChild;
    }
}

The tree can now contain any type of data object, without having to descend from a special type or include any properties controlling tree structure. The tree structure is all handled internally by the Tree class and all Tree operations are provided by the Tree class. Now the client is completely insulated from implementation details. All the client ever sees are their data objects. If you still want to be able to still provide navigation from the nodes, you could provide a link back to the Tree in the node interface and then provide extension methods that use the Tree methods to implement the navigation.

Answer 6

Just fix your generic-type parameter names, and remember to add the generic-type parameter to the inherited GenericNode.

ie.

public abstract class GenericNode<TNode, TContainer>
    where TNode : GenericNode<TNode, TContainer>
    where TContainer : GenericNode<TNode, TContainer>.GenericContainer
{
    public TContainer Parent { get; set; }
    public TNode Next { get; set; }
    public TNode Previous { get; set; }

    public abstract class GenericContainer : GenericNode<TNode, TContainer>
    {
        public TNode FirstChild { get; set; }
        public TNode LastChild { get; set; }
    }
}

Compiles just fine.