I have a graph library where I am trying to decompose things as much as possible, and the cleanest way to describe it that I found is the following: there is a vanilla type node implementing only a list of edges:
class node
{
public:
int* edges;
int edge_count;
};
Then, I would like to be able to add interfaces to this whole mix, like so:
template <class T>
class node_weight
{
public:
T weight;
};
template <class T>
class node_position
{
public:
T x;
T y;
};
and so on. Then, the actual graph class comes in, which is templated on the actual type of node:
template <class node_T>
class graph
{
protected:
node_T* nodes;
public:
static graph cartesian(int n, int m)
{
graph r;
r.nodes = new node_T[n * m];
return r;
}
};
The twist is that it has named constructors which construct some special graphs, like a Cartesian lattice. In this case, I would like to be able to add some extra information into the graph, depending on what interfaces are implemented by node_T.
What would be the best way to accomplish this?
I thought of the following humble solution, through dynamic_cast<>:
template <class node_T, class weight_T, class position_T>
class graph
{
protected:
node_T* nodes;
public:
static graph cartesian(int n, int m)
{
graph r;
r.nodes = new node_T[n * m];
if (dynamic_cast<node_weight<weight_T>>(r.nodes[0]) != nullptr)
{
// do stuff knowing you can add weights
}
if (dynamic_cast<node_position<positionT>>(r.nodes[0]) != nullptr)
{
// do stuff knowing you can set position
}
return r;
}
};
which would operate on node_T being the following:
template <class weight_T, class position_T>
class node_weight_position :
public node, public node_weight<weight_T>, public node_position<position_T>
{
// ...
};
Is this -- philosophically -- the right way to go? I know people don't look nicely at multiple inheritance, though with "interfaces" like these it should all be fine.
There are unfortunately problems with this. From what I know at least, dynamic_cast<> involves quite a bit of run-time overhead. Hence, I run into a problem with what I had solved earlier: writing graph algorithms that require weights independently of whether the actual node_T class has weights or not. The solution with this 'interface' approach would be to write a function:
template <class node_T, class weight_T>
inline weight_T get_weight(node_T const & n)
{
if (dynamic_cast<node_weight<weight_T>>(n) != nullptr)
{
return dynamic_cast<node_weight<weight_T>>(n).weight;
}
return T(1);
}
but the issue with it is that it works using run-time information (dynamic_cast), yet in principle I would like to decide it at compile-time and thus make the code more efficient.
If there is a different solution that would solve both problems, especially a cleaner and better one than what I have, I would love to hear about it!
What about type traits? If you have a compiler handy that supports parts of C++11 already, there is std::is_base_of in the <type_traits> header.
If you do not, there is boost with the same type trait.
Now, to really be able to use it, you need some meta programming:
// in the class...
// branch on whether the node type has weights
static void set_weights(node_T* nodes, std::true_type){
// has weights, set them
// ...
}
static void set_weight(node_T* nodes, std::false_type){
// doesn't have weights, do nothing
}
// in the function...
typedef std::is_base_of<node_weight<weight_T>, node_T>::type has_weights;
set_weight(nodes, has_weights());
This works thanks to some magic that lets the nested typedef type be either true_type or false_type based on whether the type trait is true or false. We need the meta programming (branching through overloads), because accessing members that aren't there will result in a compiler error, even if the access was in a branch that would never be executed.
I hope that makes any sense at all, it's quite difficult to type an answer to this topic on an iPod Touch...