How can I restrict child nodes in a tree structure

Question

I am creating a tree structure based on the AbstractNode class. The AbstractNode class has a common collection property that contains its child nodes. See the sample code below.

Is there some way, perhaps using generics, I can restrict a specific version of AbstractNode to allow only one type of child node? See the code below for ConcreteNodeA , where its ChildNodes property is a ConcreteNodeB collection, not an AbstractNode . This, of course, does not compile, but I wonder if there is another method that I could use to have the same effect.

Of course, everything will work with the ChildNodes property, always of type AbstractNode , but I'm trying to inject some logic into my classes with respect to the fact that nodes must be children of other nodes. Plus, when referring to the ChildNodes property , it would be nice if I didn’t have to drop the collection into the collection of the type that I know 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

Ok, I think I understood what I want, but I would like to know if anyone thinks about it “badly” or “smells funny” and why. Instead of having my nodes have a ChildNodes collection property, I am thinking of making each Node an actual collection. So my tree structure will really be just a series of collections of collections. My abstract Node classes will then use various constraints for the generic type to control the types of nodes it can have.

It makes sense? Is there a reason why I do not want to do this? I have never used generics in one of my own classes, so I'm not sure if I'm missing 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; } } 

is it possible to work? Just not sure about the comments.

EDIT: This is very 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

Unfortunately not. You must choose; Do you want the ConcreteNode Kids property to be NodeCollection<AbstractNode> or NodeCollection<ConcreteNode> ?

The problem arises when you consider adding node to your collection; what if you have a ConcreteNodeA that you chose as AbstractNode . Then you try to call

 concreteA_As_Abstract.Add(concreteB); 

NodeCollection should allow the addition; NodeCollection will not be. Therefore, you must make a choice.

The new C # 4 covariance / contravariance features may help you (see Eric Lippert's blog for more), but they do not exist until VS2010.

Answer 3

It reminds me of what I played with, and I will write a code here, suggesting you take it with a “grain of salt”: I have not fully tested it yet, and there are, for me, some very strange things about this code (see comments " // weird: "). 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 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 examples of 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 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, a compilation error when trying to use the tree for GammaChild:

 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>'