1

I have a tree data structure where each node has a name, an id, a type and a number of children. Additionally each node has properties based on its type. Thereby each node with type A should only have children of Type B, C, D... and each node of type C should only have children with type D, E, F, etc.

Therefore I have implemented an abstract class containing all the common fields and subclasses for each type with an additional object for the uncommon properties.
The different types as well as the respective values are stored in an enum.
So I can check if a child can be added to a node using the values of the types defined in the enum.

Do you think it is fine to enforce the structure this way, or is there a better way to accomplsh that?

New contributor
Florian Winter is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
  • We cannot tell from the information in the question. You are favoring dynamic checking over static checking, but we don't know why. How are the child relationships captured? Can they change over time? During development? At runtime? – Erik Eidt Nov 7 at 20:14
  • Currently there are 5 different node types with their respective order defined but during development possibly more are added. The order of the existing node types will not change and the new types might be added at any position of the order. At runtime the number of node types is fixed and does not change. – Florian Winter Nov 7 at 20:36
  • Do I understand correctly that with each level the set of allowed children is exactly reduced by this children? Or are arbitrary connections like X.child=A allowed? What are theses node types representing? The concept of cascading subsets feels a bit fishy for me, there might be a better solution overall – Manziel Nov 7 at 21:36
  • No an example would be a project structure where you have a project with an id, name and some additional properties. Then as possible children the project could have modules, packages or classes. The module again could have packages or classes but not a project. A package can have classes but neither projects or packages as children and finally the class could have in this example no children at all. – Florian Winter Nov 7 at 22:16
1

An abstract class shall not depend on its concrete specialization. This is against the idea of abstraction and totally against the Open/Closed principle.

There are two main approaches for solving your design issue:

  • Abstract the rules, for example into an abstract NodeValidator class. In the tree-building process you could then rely on your abstract nodes and the abstract validator. You would inject the validator that is based on the concrete node types in the tree construction.
  • Avoid the deep class hierarchy, and opt for an Entity/Component system (a very special case of composition over inheritance). The type verification would the become a component validation. Since ECS allows for runtime composition, you could even imagine to load the component definitions with their properties and the rules from a configuration file, allowing for maximal flexibility.
0

I have a tree data structure where each node has a name, an id, a type and a number of children. Additionally each node has properties based on its type. Thereby each node with type A should only have children of Type B, C, D... and each node of type C should only have children with type D, E, F, etc.

Implementing this at the data layer is relatively straightforward.

select * 
from permitted_links ; 

+-------------+------------+
| parent_type | child_type | 
+-------------+------------+
| A           | B          |
| A           | C          |
| A           | D          |
| C           | D          |
| C           | E          |
| C           | F          |
+-------------+------------+

select * 
from nodes ; 

+----+--------+------+
| id | name   | type |
+----+--------+------+
|  1 | Node 1 | A    |
|  2 | Node 2 | D    |
+----+--------+------+

select * 
from links ; 

+-----------+-------------+----------+------------+
| parent_id | parent_type | child_id | child_type | 
+-----------+-------------+----------+------------+
|         1 | A           |        2 | D          |
+-----------+-------------+----------+------------+

(OK, I'll admit to a smidgen of denormalisation to get the node Types into the links table but, from the structure as presented, I'm guessing that Types don't change very often, if at all).

The "trick" is that the links table has a foreign key to the permitted_links table, which enforces the parent/child type restriction:

create table links 
( parent_id 
, parent_type 
, child_id 
, child_type 
  foreign key ( parent_type, child_type ) 
  references permitted_types ( parent_type, child_type )
); 

Your Answer

Florian Winter is a new contributor. Be nice, and check out our Code of Conduct.

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.