I am working in a tree like structure in which each parent node can contain several sons, and each son can have only one parent, much like a directory structure in a file system.
I have done many of these and have a number of different approach to solve the chicken-and-egg problem than I'm going to share with you now, but I wonder if there is a more of less optimal general design pattern that I've been ignoring so far to solve it.
Now, the issue is that when you set a parent into a son node, the parent must add this new node to its inner offspring list, and when you add a son to a parent, the son must update it's parent, all in order to maintain a coherent tree, otherwise you could end up with parents that have sons that don't recognize them as fathers, and vice versa...
Let's see it with an example (I'll use JAVA), for code problems are better shown in code than explained in paragraphs:
class Node {
private Node parent;
private ArrayList<Node> sons=new ArrayList<Node>();
public void setParent(Node parent) {
this.parent = parent;
parent.addSon(this);
}
public void addSon(Node son) {
this.sons.add(son);
son.setParent(this);
}
}
OK, this is the simplest form for the sake of simplicity, although there are other things to deal with (son removal from its previous parent, for example). I'm pretty sure you already see the recursive problem we have here.
An more or less obvious approach is to check at runtime whether the son has already assigned this as its parent, so I'd rewrite those methods as:
public void addSon(Node son) {
this.sons.add(son);
if (son.parent != this)
son.setParent(this);
}
But I wonder if there would be a better approach to solve this. For example, another approach that will save some redundant calls could be using an static method, something like:
class Node {
private Node parent;
private ArrayList<Node> sons=new ArrayList<Node>();
public static assignSon(Node parent, Node son) {
parent.sons.add(son);
son.parent = parent;
}
}
So, provided assignSon is the only method one can use to relate sons to their fathers, this solves the chicken-an-egg problem but it is also somehow less intuitive to use from outside, and you'll have to write more code, you know, where before you can do something like:
son.setParent(parent);
Or
parent.addSon(son);
You'll to write now:
Node.assignSon(parent, son);
It's not a big deal, but still... well, whatever. If you know an optimal approach for this problem and you want to share with this community, I for one will be very thankful!
TIA!
Aucun commentaire:
Enregistrer un commentaire