CODEWITHSUNDEEP
c++templatesrecursion
Gasim
Gasim

Reputation: 7961

recursion through a function of derived classes of a template class

I am trying to traverse through a tree using recursion but I am encountering a problem because the base class is a template class. Here is the code below:

The problem arises because when RootNode traverse function is called it still uses the EmptyVisitor class for all the child classes of the node. But I do not know if its even possible to overcome this issue. I need TransformNode to "know" that its using the TransformVisitor not EmptyVisitor. I hope I could explain what I mean.

class BaseNode {
public:
    typedef std::set<BaseNode *> ChildSet;

protected:
    ChildSet mChildren;
    BaseNode * mParent;

public:
    BaseNode(BaseNode * parent=0) : mParent(parent) {}
    ~BaseNode() {}

    BaseNode * addChild(BaseNode * node); //adds `node` to `mChildren`
    inline BaseNode * getParent() { return mParent; }

    inline const ChildSet &getChildren() const { return mChildren; }
    inline ChildSet &getChildren() { return mChildren; }
};

class EmptyVisitor {
public:
    static void visit(BaseNode * node) {std::cout << "Empty Visitor\n";}
};

class TransformVisitor {
    static void visit(BaseNode * node) {
       std::cout << "Transform Visitor\n";
    }
};

template<class Visitor>
class Node : public BaseNode {
public:

    void traverse() {
        traverse(this);
    }

    void traverse(Node * node) {
        Visitor::visit(this);

        for(ChildSet::iterator i = node->getChildren().begin(); i != node->getChildren().end(); ++i) {
            traverse(static_cast<Node*>((*i)));
        }
    }

};

class RootNode : public Node<EmptyVisitor> {
};

class TransformNode : public Node<TransformVisitor> {
};

main.cpp

int main() {
    RootNode * root = new RootNode;
    root->addChild(new TransformNode);
    root->traverse();

   return 0;
}

Output:

Empty Visitor
Empty Visitor

Expected Output:

Empty Visitor
Transform Visitor

Upvotes: 0

Views: 251

Answers (1)

BartoszKP
BartoszKP

Reputation: 35891

There is no way for RootNode class to know what other classes derive from the same base class. Your design seems a bit too obfuscated, and has really nothing to do with the Visitor pattern. Why not just use an ordinary polymorphism?

This is just a sketch, as using polymorphism makes most of your template work obsolete, so it should be further refactored. However this simple fix, will lead you to the desired result:

template<class Visitor>
class Node : public BaseNode {
public:

    void traverse() {
        traverse(this);
    }

    void traverse(Node * node) {
        visit();

        for(ChildSet::iterator i = node->getChildren().begin();
            i != node->getChildren().end();
            ++i) {
            traverse(static_cast<Node*>((*i)));
        }
    }

    virtual void visit()
    {
        Visitor::visit(this);
    }
};

class TransformNode : public Node<TransformVisitor> {
    void visit()
    {
        TransformVisitor::visit(this);
    }
};

Perhaps you were interested in something like this or this?

Upvotes: 1

Related Questions