Combining templates and inheritance in tree conversion

Question

I have data stored in a C++ tree structure which I read in from a file. The tree looks like that:

class BaseNode {
  std::vector<BaseNode*> children_;
  ...
};
class WhiteNode : public BaseNode { ... };
class BlackNode : public BaseNode { ... };

After the tree is built, I would like to convert it, e.g. to a string.

In order to keep the tree code separate from the conversion code, I would like to use templates, i.e. implementing something like that:

template <class T>
T WhiteNode::Convert() { ... };

However, since the tree nodes are stored as BaseNode*, I don't know how to access such a template member function. And since template member functions cannot be inherited, I don't think this will work.

I did come up with a working solution, though:

class BaseConversion {
public:
  virtual ~BaseConversion() {}
  virtual void * FromBlack() = 0;
  virtual void * FromWhite() = 0;
};

template <class T>
class Conversion : public BaseConversion {
public:
  void * FromBlack();
  void * FromWhite();
};

class BaseNode {
  std::vector<BaseNode*> children_;
  virtual void * Convert(BaseConversion * conversion) = 0;
public:
  virtual ~BaseNode() {}
  template <class T>
  T Convert() {
    return *static_cast<T*>(Convert(new Conversion<T>));
  }
};

class WhiteNode : public BaseNode {
  void * Convert(BaseConversion * conversion) {
    return conversion->FromWhite();
  }
};

class BlackNode : public BaseNode {
  void * Convert(BaseConversion * conversion) {
    return conversion->FromBlack();
  }
};

And the transformation logic can be entirely separate:

template <>
void * Conversion<std::string>::FromWhite() {
  return new std::string("converting WHITE node to std::string ...");
}

template <>
void * Conversion<std::string>::FromBlack() {
  return new std::string("converting BLACK node to std::string ...");
}

Testing the code:

BaseNode * node = new BlackNode;
std::cout << node->Convert<std::string>() << std::endl;
node = new WhiteNode;
std::cout << node->Convert<std::string>() << std::endl;

returns the expected result:

converting BLACK node to std::string ...
converting WHITE node to std::string ...

Although this solution works, I am sure it can be done much easier. Any other, simpler solution I came up with failed, e.g. due to type erasure.

I would appreciate any help on that. Thanks!

Answer 1

Something similar to your solution but without void*.

class NodeVisitor
{
   virtual void VisitBlack(BlackNode* node);
   virtual void VisitWhite(BlackNode* node);
};

class BaseNode {
  std::vector<BaseNode*> children_;
  ...
  virtual void visit(NodeVisitor* visitor) = 0;
};

class WhiteNode : public BaseNode {
  virtual void visit(NodeVisitor* visitor) { visitor->visitWhite(this); }
};

class BlackNode : public BaseNode {
  virtual void visit(NodeVisitor* visitor) { visitor->visitBlack(this); }
};

Then

std::string convert(BaseNode* node)
{
    class ConvertVisitor
         : public NodeVisitor
    {
        ConvertVisitor(std::string* res)
            : m_res(res)
        { }

        virtual void VisitBlack(BlackNode* node)
        {
            *m_res = // convert black node to string;
        }

        virtual void VisitWhite(BlackNode* node)
        {
            *m_res = // convert white node to string;
        }

        std::string* m_res;
    };

    std::string res;
    ConvertVisitor visitor(&res);
    node->visit(&visitor);
    return res;
}