CODEWITHSUNDEEP
c++visitor-pattern
Arne Mertz
Arne Mertz

Reputation: 24626

Visitor pattern for const and nonconst versions of a tree

I am stuck with a code duplication issue, regarding the visitor pattern for a tree. The current situation is as follows: I have a tree, consisting of two different node classes, i.e. leafs and non-leafs. In addition I have two visitor base classes that look very alike except that one visits const trees and the other non-const trees. The actual actions the concrete visitors have to do are independent of the node's concrete types. I'll give a short example:

class Visitor;
class ConstVisitor;

class Node {
public:
  virtual void accept(Visitor&) = 0;
  virtual void accept(ConstVisitor&) const = 0;
};

class Leaf : public Node {
  virtual void accept(Visitor& v)        {v.visitLeaf(*this);}
  virtual void accept(ConstVisitor& cv)  {cv.visitLeaf(*this);}
};

class CompoundNode : public Node {
public:
  vector<Node*> getChildren() const;
  virtual void accept(Visitor& v)        {v.visitCompoundNode(*this);}
  virtual void accept(ConstVisitor& cv)  {cv.visitCompoundNode(*this);}
};

class Visitor {
protected:
  virtual void processNode(Node& node) = 0;
public:
  void visitLeaf(Leaf& leaf) {
    processNode(leaf);
  }
  void visitCompoundNode(CompoundNode& cNode) {
    processNode(cNode);
    auto children = cNode.getChildren();
    for (auto child : children)
      child->accept(this);
  }
};

class ConstVisitor {
protected:
  virtual void processNode(Node const& node) = 0;
public:
  void visitLeaf(Leaf const& leaf) {
    processNode(leaf);
  }
  void visitCompoundNode(CompoundNode const& cNode) {
    processNode(cNode);
    auto children = cNode.getChildren();
    for (auto child : children)
      child->accept(this);
  }
};

Concrete visitor classes inherit either from Visitor or from ConstVisitor, depending on whether their processNode method has to alter the nodes visited or not.

You see, there is lots of code duplication between the two visitors, and since I will have to implement another traversal strategy, also for both const and nonconst nodes, I want to avoid that duplication. Are there any possibilities to extract the duplicate code, preferably without using const_cast all over the place?

Upvotes: 11

Views: 2194

Answers (2)

Open AI - Opting Out
Open AI - Opting Out

Reputation: 24153

You could use templates:

template<typename NodeType,
         typename CompoundNodeType,
         typename LeafType>
class BaseVisitor {
protected:
    virtual void processNode(NodeType& node) = 0;
public:
    void visitLeaf(LeafType& leaf) {
        processNode(leaf);
    }
    void visitCompoundNode(CompoundNodeType& cNode) {
        processNode(cNode);
        auto children = cNode.getChildren();
        for (auto child : children)
        child->accept(this);
    }
};

class Visitor: public BaseVisitor<Node, CompoundNode, Leaf> {
};

class ConstVisitor: public BaseVisitor<const Node, const CompoundNode, const Leaf> {
};

Upvotes: 0

Andy Prowl
Andy Prowl

Reputation: 126502

You could define a TVisitor class template as done below:

#include <type_traits>

class Node;
class CompoundNode;
class Leaf;

template<bool isNonConstVisitor>
class TVisitor
{
    typedef typename std::conditional<isNonConstVisitor, 
        Node, Node const>::type node_type;

    typedef typename std::conditional<isNonConstVisitor, 
        CompoundNode, CompoundNode const>::type compound_node_type;

    typedef typename std::conditional<isNonConstVisitor, 
        Leaf, Leaf const>::type leaf_node_type;

protected:

    virtual void processNode(node_type& node) = 0;

public:

    void visitLeaf(leaf_node_type& leaf) { processNode(leaf); }

    void visitCompoundNode(compound_node_type& cNode) {
        processNode(cNode);
        auto children = cNode.getChildren();
        for (auto child : children) { child->accept(*this); }
    }
};

And then use Visitor and ConstVisitor as type aliases for corresponding instantiations of that class template:

typedef TVisitor<true> Visitor;
typedef TVisitor<false> ConstVisitor;

Upvotes: 12

Related Questions