Structuring a tree

[Maurizio Tomasi]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

I am developing an application which needs to structure its data using a
tree. Each node in the tree is derived from an abstract base class
called Base. There are a number of derived classes, let's call them A,
B, C and so on. There are constraints on the children each of these
classes can have. Here are some examples:

1. Children of nodes of type A must be of type B;
2. Nodes of type C cannot have more than one child;
3. Nodes of type D must have exactly 3 child nodes of type A, B, C.
4. Nodes of type E cannot have children of type B.
5. Nodes of type F cannot have children at all.

My question is, what is the best approach to represent such complex
parent/child relationships? The "classic" way to implement trees in C++:

class Node {
std::list<Node *> child_list;

public:
Node ();
void add_child (Node * new_child);
std::list<Node *> get_children ();

// Virtual methods useful to my program would follow here
};

does not allow me to implement such constraints.

Cheers,
Maurizio Tomasi.
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.2 (GNU/Linux)
Comment: Using GnuPG with SUSE - http://enigmail.mozdev.org

iD8DBQFEjtwof5EaQtfBD9oRAmdUAJ0V2OVgyczfEsWeLKdXSSuGjtDF4QCfRHNH
Xz+6WPfqjUr2xQmy+ePlaIk=
=ajOr
-----END PGP SIGNATURE-----

 

[Dmytro]

What about:

class Node {
protected:
std::list<Node *> child_list;
Node* parent;
Node();
public:
virtual ~Node();
virtual bool is_valid() { return true; }
virtual bool can_add( Node * new_child ) { return true; }
virtual void add_child( Node * new_child )
{
if ( new_child->is_valid() && can_add( new_child ) )
{
child_list.push_back(new_child);
new_child->parent = this;
}
}
std::list<Node *> get_children ();
};

class A : public Node {
// ...
virtual bool can_add( Node * new_child )
{ return dynamic_cast<B*>( new_child ) != 0; }
};
class C : public Node {
// ...
virtual bool can_add( Node * new_child )
{ return child_list.empty(); }
};
class F : public Node {
// ...
virtual bool can_add( Node * new_child )
{ return false; }
};
// and so on...

-- Dmytro