Transforming trees in C++

Question

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.

Answer 1

One way to solve the problem on having to dispatch on unique_ptr<T> is to go back to passing around pointers the way you do in your visitor, but changing the return type to Node*, like this:

// Top-level function stays the same
Node* genericVisit(Node* node) {
    if (dynamic_cast<Subnode2>(node)) {
        return visit(static_cast<Subnode2*>(node));
    }
    // etc
}
// Specialized overloads can return replacements as they go
virtual Node* visit(Subnode2* node) {
    if (mustReplace()) {
        Subnode1 *myReplacement = ...
        return myReplacement;
    }
    if (node->getChild()) {
        Node *replacement = genericVisit(node->getChild());
        // nullptr means no replacement; non-null means we replace the child
        if (replacement) {
            node->setChild(replacement);
        }
    }
    return nullptr;
}

This approach requires implementer to pay attention to what's returned (i.e. nullptr or not) before performing the replacement. On the other hand, it keeps the final decision on performing the replacement in the hands of the function that makes the visitor call, which ultimately translates to more control over the internals, i.e. better encapsulation.