How can I restrict the children of nodes in a tree structure.

Question

I'm creating a tree structure that is based on an AbstractNode class. The AbstractNode class has a generic collection property that contain its child nodes. See the code example below.

Is there some way, possibly using generics, that I can restrict a concrete version of AbstractNode to only allow one type of child node? See the code below for ConcreteNodeA, where its ChildNodes property is a collection of ConcreteNodeB rather then AbstractNode. This of course does not compile, but I'm wondering if there is some other method I could use to have the same effect.

Of course everything will work with the the ChildNodes collection property always being of type AbstractNode, but I'm trying to embed some logic into my classes in regards to what nodes should be the children of other nodes. Plus when referencing the ChildNodes property it would be nice if I didn't have to cast the collection into a collection of the type I know it should be.

public abstract class AbstractNode
{

    public abstract NodeCollection<AbstractNode> ChildNodes
    {
        get;
        set;
    }
}

public class ConcreteNodeA : AbstractNode
{
    //THIS DOES NOT COMPLILE
    //Error 1 'ConcreteNodeA.ChildNodes': type must be 'NodeCollection<AbstractNode>' 
    //to match overridden member 'AbstractNode.ChildNodes'  
    public override NodeCollection<ConcreteNodeB> ChildNodes
    {
        get;
        set;
    }
}

public class ConcreteNodeB : AbstractNode
{
    public override NodeCollection<AbstractNode> ChildNodes
    {
        get;
        set;
    }
}

public class NodeCollection<T> : BindingList<T>
{ 
    //add extra events here that notify what nodes were added, removed, or changed
}

---

Update

Alright I think I figured out what I want to do but I'd like to know if anyone thinks this "feels bad" or "smells funny" and why. Rather then my nodes having a ChildNodes collection property I'm thinking of making each Node the actual collection. So my tree structure is would really just be a series of collections of collections. My abstract Node classes will then use various constraints on the generic to control the kinds of sub nodes it can have.

Does this make sense? Is there a reason I wouldn't want to do this? I've never used generics in one of my own classes before so I'm not sure if I'm overlooking something.

public interface INode
{

}

public abstract class AbsNode<T> : BindingList<T>, INode where T : INode
{

}

public abstract class AbsNodeA<T> : AbsNode<T> where T : AbsSubNodeA
{

}

public abstract class ConcreteNodeA : AbsNodeA<AbsSubNodeA>
{

}

public abstract class AbsSubNodeA : INode
{

}

public class ConcreteSubNodeA :AbsSubNodeA
{

}

public class ConcreteSubNodeB :AbsSubNodeA
{

}

Answer 1

Could something like

public abstract class AbstractNode<T> //where T : AbstractNode
{

  public abstract NodeCollection<T> ChildNodes
  {
    get;
    set;
  }
}

possibly work? Just not sure on the commented out part

EDIT: This feels really bad inside but it compiles...

  public abstract class BaseNode
  {
  }

  public abstract class AbstractNode<T> : BaseNode where T : BaseNode
  {
    public abstract NodeCollection<T> ChildNodes
    {
      get;
      set;
    }
  }

  public class ConcreteNodeA : AbstractNode<ConcreteNodeA>
  {
    public void Special() { }

    public override NodeCollection<ConcreteNodeA> ChildNodes
    {
      get;
      set;
    }
  }

  public class ConcreteNodeB : AbstractNode<ConcreteNodeA>
  {
    public void DoSomething()
    {
      ChildNodes[0].ChildNodes[0].ChildNodes[0].Special();
    }

    public override NodeCollection<ConcreteNodeA> ChildNodes
    {
      get;
      set;
    }
  }

  public class NodeCollection<T> : BindingList<T>
  {
    //add extra events here that notify what nodes were added, removed, or changed
  }

Answer 2

Hi, This reminds me of something I have been playing with, and I'll throw in the code here suggesting you take it with a "grain of salt" : I have not fully tested it yet, and there are, to me, some very strange things about this code (look for "// weird :" comments). This was done in VS Studio 2010 beta 2, compiled against FrameWork 4.0.

using System;
using System.Collections.Generic;
using System.Linq;

// WARNING : EXPERIMENTAL CODE : DO NOT USE FOR ANYTHING BUT EDUCATIONAL PURPOSES

// comments about how crazy the code is : are welcome :)

namespace stronglyTypedTree
{
    // TreeNodes is a strongly typed List of strongly typed Nodes
    public class TreeNodes<T> : List<Node<T>>
    {
        // weird : sometimes the compiler informs me that new is
        // required, if i have not used new, and sometimes it informs
        // me, when I have added new, that new is not required
        public new void Add(Node<T> newNode)
        {
            Console.WriteLine("Add called in TreeNodes class : Type = " + typeof(T).ToString() + " : Node Key = " + newNode.Key.ToString());
            newNode.Parent = this;
            base.Add(newNode);
        }
    }

    // strongly typed Node
    public class Node<T>
    {
        // note : implement a key/value pair
        // instead of this ?
        internal T _key;

        // experimental : have not fully considered
        // the case of root nodes

        // better to make this a property ?
        public TreeNodes<T> Parent;

        // better to make this a property ?
        public TreeNodes<T> Nodes;

        public Node()
        {
            Nodes = new TreeNodes<T>();
        }

        // weird : calling base() here does NOT seem to call the
        // parameterless ctor above : the Nodes collection is, thus, 
        // not instantiated : will cause errors at run-time !
        public Node(T keyValue) : base()
        {
            _key = keyValue;
            // had to insert this : see note above
            Nodes = new TreeNodes<T>();
        }

        public T Key
        {
            get { return _key; }
            set { _key = value; }
        }
    }

    public class Tree<T>
    {
        public TreeNodes<T> Nodes;

        public string Name;

        public Tree()
        {
            Nodes = new TreeNodes<T>();
        }

        // weird : see note on ctor with one parameter
        // in the Node class above
        public Tree(string treeName) : base()
        {
            Name = treeName;
            // had to insert this : see note above
            Nodes = new TreeNodes<T>();
        }
    }

    // define some strongly typed Node classes

    // weird : i thought i could get away with not defining explicit ctors :
    // that ctor's of the Node class would be automatically invoked
    public class intNode : Node<int>
    {
        public intNode() : base() { }

        public intNode(int keyValue) : base(keyValue) { }
    }

    public class strNode : Node<string>
    {
        public strNode() : base() { }

        public strNode(string keyValue) : base(keyValue) { }
    }
}

Some sample test calls :

    intNode myIntNode1 = new intNode();
    myIntNode1.Key = 100;
    intNode myIntNode2 = new intNode(777);

    strNode myStrNode1 = new strNode();
    myStrNode1.Key = "hello";
    strNode myStrNode2 = new strNode("string node 2");

    Tree<int> intTree = new Tree<int>();
    intTree.Name = "Tree of Integer";

    Tree<string> strTree = new Tree<string>("Tree of String");

    intTree.Nodes.Add(myIntNode1);
    intTree.Nodes.Add(myIntNode2);

    strTree.Nodes.Add(myStrNode1);
    strTree.Nodes.Add(myStrNode2);

    myIntNode1.Nodes.Add(new intNode(999));
    myStrNode2.Nodes.Add(new strNode("subNode of strNode2"));

    Console.WriteLine(intTree.Nodes.Count);

    Console.WriteLine(intTree.Nodes[0]);

    Console.WriteLine(strTree.Nodes.Count);

    Console.WriteLine(strTree.Nodes[1]);

best, Bill

Answer 3

Unfortunately not. You have to choose; do you want the Children property of ConcreteNode to be NodeCollection<AbstractNode> or NodeCollection<ConcreteNode>?

The problem comes when you consider adding a node to your collection; what if you have a ConcreteNodeA, which you've cast as AbstractNode. Then, you try to call

concreteA_As_Abstract.Add(concreteB);

NodeCollection should allow the add; NodeCollection will not. So you have to make a choice.

The new C#4 covariance/contravariance features may help you (see Eric Lippert's blog for more) but they aren't around until VS2010.

Answer 4

Is this what you want:

namespace Foo 
{   
    public interface INode
    {
        string Speak();
    }

    public abstract class AbstractRoot<T> where T : INode
    {
        public abstract IList<T> Children { get; set; }
    }

    public class GammaChild : INode
    {
        public string Speak() { return "I am GammaNode."; }
    }

    public class BetaChild : AbstractRoot<BetaChild>, INode
    {
        public string Speak() { return "I am BetaNode."; }
        public string BetaSpeak() { return "I am talking Beta-specific things."; }

        private IList<BetaChild> children;
        public override IList<BetaChild> Children { get { return children; } set { children = value; } }
    }

    public class AlphaRoot<T> : AbstractRoot<T>, INode where T : BetaChild
    {
        public string Speak() { return "I am AlphaRoot."; }

        private IList<T> children;
        public override IList<T> Children { get { return children; } set { children = value; } }
    }

    public class Test
    {
        public void Run()
        {
            AlphaRoot<BetaChild> alphaBetaTree = new AlphaRoot<BetaChild>();
            alphaBetaTree.Children.Add(new BetaChild());

            alphaBetaTree.Children[0].BetaSpeak();

            AlphaRoot<GammaChild> alphaGammaTree = new AlphaRoot<GammaChild>();
            alphaGammaTree.Children.Add(new GammaChild());
        }
    }
}

And as expected, the compile error when trying to use the tree for GammaChild is:

The type 'Foo.GammaChild' must be convertible to 'Foo.BetaChild' in order to use it as parameter 'T' in the generic type or method 'Foo.AlphaRoot<T>'