Binary tree with different node types

Question

I'm working on a somewhat complex mathematical code, written in C++. I'm using (templated) tree structures for adaptive function representation. Due to some mathematical properties I end up in a situation where I need to change from one type of node to another. This needs to happen transparently and with minimal overhead, both in terms of storage and performance, since these structures are used in very heavy computations.

The detailed situation is as follows: I have a templated abstract base class defining general mathematical and structural properties of a general, doubly-linked node. Each node needs information both from it's parent and from a top-level Tree class, in addition to keeping track of it's children. Two classes inherit from this class, the FunctionNode and the GenNode. These classes are very different in terms of storage and functionality, and should not be (at least public) ancestors of each other. Thus, I would like to construct a tree like this:

     T
     N
    / \
   N    N
       / \
      G   N
     / \
    G   G

Where T is a Tree, N is a normal FunctionNode and G is a GenNode. The problem is the N - G transition: N needs to have children of type G, and G a parent of type N. Since N and G are only cousins and not siblings, I can't convert a N* to a G*. It's sufficient for G to know that N is a BaseNode, but N has to somehow store G polymorphically so that the correct virtuals get called automagically when the tree is traversed. Any ideas how to solve this problem elegantly and efficiently would be much appreciated! :) Of course one could just hack this, but since this is a very fundamental piece of code I would like to have a good solution for it. It's likely that there will be many derivations of this code in the future.

Best regards,

Jonas Juselius

Centre for Theoretical and Computational Chemistry, University of Tromsø

Answer 1

Don't use inheritance when delegation will do. Look at the Strategy design pattern for guidance on this.

The "N - G" transition may be better handled by having a subclass of N (N_g) which is a unary operator (where other N's are binary) and will delegate work to the associated G object. The G subtree is then -- actually -- a disjoint family of classes based on G's, not N's.

   T
   N
  / \
 N    N
     / \
    N_g N
    |
    G
   / \
  G   G

---

"One of the problems is that I do not know beforehand whether the next N will be N or N_g."

"beforehand?" Before what? If you are creating N's and then trying to decide if they should have been N_g's, you've omitted several things.

1. You've instantiated the N too early in the process.

2. You've forgotten to write an N_g constructor that works by copying an N.

3. You've forgotten to write a replace_N_with_Ng method that "clones" an N to create an N_g, and then replaces the original N in the tree with the N_g.

The point of polymorphism is that you don't need to know "beforehand" what anything is. You should wait as long as possible to create either an N or an N_g and bind the resulting N (or subclass of N) object into the tree.

"Furthermore, sometimes I need to prune all G:s, and generate more N:s, before perhaps generating some more G:s."

Fine. You walk the tree, replacing N_g instances with N instances to "prune". You walk the tree replacing N instances with N_g's to generate a new/different G subtree.

Answer 2

Look into using RTTI - Run-time Type Information.

Answer 3

Have you though of using Boost.Any ?

It seems like the textbook example in my opinion.

Answer 4

Having thought about the problem some more I came up with the following idea:

Logically, but not functionally, GenNode is a-kind-of FunctionNode. If one splits FunctionNode into two classes, one containing the common denominators, and one having the additional functionality only FunctionNode should have, FunctionNode can inherit from that class using private inheritance. Now GenNode can safely inherit from FunctionNode, and all problems can be solved like normal using virtuals. Any comments?