mardi 30 décembre 2014

Transforming trees in C++

I have an heterogeneous n-ary tree made by different kind of nodes, for example:



class Node { }

class Subnode1 : public Node
{

}

class Subnode2 : public Node
{
private:
unique_ptr<Subnode1> child;

public:
Subnode1* getChild() { return child.get(); }
}

class Subnode4 : public Subnode2 { }

class Subnode3 : public Node
{
private:
list<unique_ptr<Subnode2>> children;
public:
// getter
}

// etc


The structure could contain any amount of types of nodes and it will be extended in the future.


I implemented a way to visit the tree which allows me to customize what to do when each node is visited which is basically implemented in this way:



void genericVisit(Node* node) {
if (dynamic_cast<Subnode2>(node))
visit(static_cast<Subnode2*>(node));
// etc
}

virtual void visit(Subnode2* node) {
if (node->getChild())
genericVisit(node->getChild());
}

// etc


It works nicely to traverse the tree but now I have the requirement to be able to replace subtrees with other subtrees so I'm thinking about the best approach to follow without altering the structure too much.


The best solution would have been to let getter return directly unique_ptr<Subnode2>& so that I do the visit on the unique pointers and I'm able to change the content of the smart pointer while visiting it. This would work but unique_ptr is not polymorphic, and there is no way to dispatch the call to the most specialized method, eg:



void genericVisit(unique_ptr<Node>& node) { // NON WORKING CODE
if (dynamic_cast<unique_ptr<Subnode2>&>(node))
visit(static_cast<unique_ptr<Subnode2>&>(node));
// etc
}


So I was wondering which could be the best solution to the problem, minding that while traversing the tree, as long as I change the content of the current subtree without changing the reference to that node in the parent, (which would be allowed by using an unique_ptr) I don't see any problem.


Aucun commentaire:

Enregistrer un commentaire