templates of derived classes

[Zeppe]

Hi all!

my problem is this one, I think that it could be a common one, maybe a
pattern, so if you can help me somehow it would be great. Let's suppose
I have a class Base

class Base
{
// impl.
};

and a template class Foo

template <typename T>
class Foo
{
// impl.
private:
T obj_;
};

I use this class passing it as a pointer to various functions:

void bar(Foo<Base> * myFoo);

Now, I would like to derive a class

class Derived : public Base
{
// impl.
};

and pass among the functions a pointer to Foo<Derived>.

Well, how to do so? I would like to avoid the pointer in T, otherwise a
possible solution would be:

template <typename T>
class Foo
{
public:
template <typename IteratorT>
static Foo<T>* GenerateFrom(IteratorT begin, IteratorT end);
// impl.
protected:
T* obj_;
}

defining, instead of Foo<Derived>, a class

class FooDerived
: public Foo<Base>
{
public:
FooDerived()
: obj_(new Derived)
{
}

}


Ok, maybe a little bit well written to avoid the protected nude pointer.
Then none of my functions would change, being possible to pass a pointer
to FooDerived. Unfortunately, there is another issue that prevents me
from using this solution. I cannot build my FooDerived objects directly,
because I need to build them via the Foo static function GenerateFrom,
that calls the constructor of the element inside Foo objects.

I think I can delegate the construction of Foo to a factory, and pass it
as a template member of the GenerateFrom static function... but it seems
a little bit dirty solution to me.

Anyone of you has got some suggestion about a cleaner design for this
problem?

Cheers,

Zeppe

 

[Alf P. Steinbach]

* Zeppe:

Hi all!

my problem is this one, I think that it could be a common one, maybe a
pattern, so if you can help me somehow it would be great. Let's suppose
I have a class Base

class Base
{
// impl.
};

and a template class Foo

template <typename T>
class Foo
{
// impl.
private:
T obj_;
};

I use this class passing it as a pointer to various functions:

void bar(Foo<Base> * myFoo);

Now, I would like to derive a class

class Derived : public Base
{
// impl.
};

and pass among the functions a pointer to Foo<Derived>.

Well, how to do so?

You can templatize the functions, or make the arguments polymorphic, or
duplicate the functions.

I would like to avoid the pointer in T

You have not shown a "pointer in T".

, otherwise a possible solution would be:

template <typename T>
class Foo
{
public:
template <typename IteratorT>
static Foo<T>* GenerateFrom(IteratorT begin, IteratorT end);
// impl.
protected:
T* obj_;
}

Missing semicolon: copy and paste code, please.

defining, instead of Foo<Derived>, a class

class FooDerived
: public Foo<Base>
{
public:
FooDerived()
: obj_(new Derived)

Invalid: copy and paste code, please.

{
}

}

Missing semicolon: copy and paste code, please.

Ok, maybe a little bit well written to avoid the protected nude pointer.
Then none of my functions would change, being possible to pass a pointer
to FooDerived. Unfortunately, there is another issue that prevents me
from using this solution. I cannot build my FooDerived objects directly,
because I need to build them via the Foo static function GenerateFrom,
that calls the constructor of the element inside Foo objects.

This particular problem seems to be: you want a factory in a class C to
produce a pointer to an object of class derived from C.

Try out this problem without templates first.

Decide on how the factory should know which type of object to produce.

I think I can delegate the construction of Foo to a factory, and pass it
as a template member of the GenerateFrom static function... but it seems
a little bit dirty solution to me.

Anyone of you has got some suggestion about a cleaner design for this
problem?

It's unclear what the problems are. Possibly some will post a technical
solution to something that might be one of the problems. You have mixed
(1) templates, (2) factories and (3) polymorphism to achieve
/something/, but you have neglected to tell those who might help what
that something is, which is what you should do: explain what you're
trying to achieve, not what you think might be relevant to achieving it.

 

[Zeppe]

to FooDerived. Unfortunately, there is another issue that prevents me
from using this solution. I cannot build my FooDerived objects directly,
because I need to build them via the Foo static function GenerateFrom,
that calls the constructor of the element inside Foo objects.

Ok, I reply to myself to explain better this point. Of course,
GenerateFrmo would generate correctly my classes if I'd use Foo<Derived>
instead of DerivedFoo: public Foo<Base>.

Thank you,

Giuseppe

 

[Zeppe]

You can templatize the functions, or make the arguments polymorphic, or
duplicate the functions.

I don't want to templatize them, nor to duplicate them, because the
behaviour don't change with the different classes. Make the argument
polimorphic: yes, but how?

You have not shown a "pointer in T".

I've shown it just after that sentence...

Missing semicolon: copy and paste code, please.

Well, the real code is quite more complex and structured than this one.
I can't post the real code, but let me try something that should be
similar with a little bit of context, in the following: maybe it's a
little bit clearer.

This particular problem seems to be: you want a factory in a class C to
produce a pointer to an object of class derived from C.

Try out this problem without templates first.

The templates are the problem, if I remove them, I can't have the same
structure.

It's unclear what the problems are. Possibly some will post a technical
solution to something that might be one of the problems. You have mixed
(1) templates, (2) factories and (3) polymorphism to achieve
/something/, but you have neglected to tell those who might help what
that something is, which is what you should do: explain what you're
trying to achieve, not what you think might be relevant to achieving it.

Ok, let's try that way, I'll explain directly my problem in the context.
I have a tree. This tree is not a class, it's just a collection of tree
nodes. The tree nodes are templatized. So, basically:


class TreeNodeBase;
typedef boost::shared_ptr<TreeNodeBase> TreeNodePtr;

class TreeNodeBase
{
// impl.
};

template <class Item>
class TreeNode
: public TreeNodeBase
{
public:
TreeNode(const Item& item)
: TreeNodeBase()
, item_(item)
{
}

const Item& GetItem() const { return item_; }
Item& GetItemRef() { return item_; } // safer - explicit call
TreeNode<Item>* FindNode(const Item& item);
const TreeNode<Item>* FindNode(const Item& item) const;

template <class ItemIt, class ItemDistance>
static TreeNodePtr GenerateMinimumSpanningTree(ItemIt begin, ItemIt end);
private:
Item item_;
};

Ok? I can generate a minimum spanning tree from a set of elements by
GenerateMinimumSpanningTree, giving some forward iterators, and
specifying the distance class that i want to use to perform the weight
calculation.

In order to generate the MinimumSanningTree, the
GenerateMinimumSpanningTree function will use the Tree constructor, in a
piece of code like:
std::vector<std:air<TreeNodePtr, ItemIt> > trees;
for(ItemIt item = begin; item != end; ++item)
trees.push_back(std::make_pair(TreeNodePtr(new TreeNode<Item>(*item)),
item));

(the vector is used in the algorithm for the minimum spanning tree).

Then, after I generate like this a tree, in a particular problem I need
a tree of Descriptors.

Once I generate this tree of descriptors passing the appropriate forward
iterators to the GenerateMinimumSpannigTree algorithm, I can give it to
a class that will perform some classification of this tree. Ok? This
class will pass the tree to other members that have to perform some
calculation to perform the classification, that is, the tree will be
read by some functions, for example:

class FactorGraphSolver
{
public:
void SolveFor(QMUL::TreeNode<Descriptor>* node, unsigned categoryID,
unsigned partsLabelNumber);
// other things...
};

And I'm really fine with that function signature, because actually the
FactorGraphSolver needs just a Tree of Descriptors, nothing more,
nothing less.

Ok? Let's say that now I want to add a particular additional information
to that tree node, for example a reference to the real descriptor that
generated it, and a label. Then I'll pass to the classification class,
and this class will call the same usual subclasses to perform the
calculations and, once done, will label every node properly. At the end
of the function, I could explore the tree and, being composed of
descriptor that have a reference of the elements that have generated
them, I can label the original elements.

Ok, the problem is this one. It seems to me that I've said enough to
understand it. I won't post the real code because it's long and mostly
unrelated to the problem.

Thank you!

Zeppe

 

[Alf P. Steinbach]

* Zeppe:

I have a tree. This tree is not a class, it's just a collection of tree
nodes. The tree nodes are templatized. So, basically:


class TreeNodeBase;
typedef boost::shared_ptr<TreeNodeBase> TreeNodePtr;

class TreeNodeBase
{
// impl.
};

template <class Item>
class TreeNode
: public TreeNodeBase
{
public:
TreeNode(const Item& item)
: TreeNodeBase()
, item_(item)
{
}

const Item& GetItem() const { return item_; }
Item& GetItemRef() { return item_; } // safer - explicit call
TreeNode<Item>* FindNode(const Item& item);
const TreeNode<Item>* FindNode(const Item& item) const;

template <class ItemIt, class ItemDistance>
static TreeNodePtr GenerateMinimumSpanningTree(ItemIt begin, ItemIt end);
private:
Item item_;
};

Ok?

Not quite. With the above structure you'd have to tentatively downcast
(via Boost's dynamic cast) each TreeNode-pointer to see what actual type
it is, i.e. to determine the type T in TreeNode<T>. Unless all nodes in
a tree have the same T, in which case TreeNodeBase doesn't make sense.

The question for a proper design is essentially: can a tree have nodes
with different item types?

If the nodes in a given tree can have different item types, I'd suggest
as best solution to require them to be derived from some common abstract
class (an interface class would be best), and otherwise, completely
unrelated types, using boost::any (if I recall the name correctly).

I can generate a minimum spanning tree from a set of elements by
GenerateMinimumSpanningTree, giving some forward iterators, and
specifying the distance class that i want to use to perform the weight
calculation.

Presumably this means that your Items are really graph nodes.

If so, then I suggest moving that factory function out of TreeNode.

It doesn't generate a TreeNode, it generates a Tree.

In order to generate the MinimumSanningTree, the
GenerateMinimumSpanningTree function will use the Tree constructor, in a
piece of code like:
std::vector<std:air<TreeNodePtr, ItemIt> > trees;
for(ItemIt item = begin; item != end; ++item)
trees.push_back(std::make_pair(TreeNodePtr(new TreeNode<Item>(*item)),
item));

(the vector is used in the algorithm for the minimum spanning tree).

Presumably you mean "the TreeNode constructor".

Then, after I generate like this a tree, in a particular problem I need
a tree of Descriptors.

Once I generate this tree of descriptors passing the appropriate forward
iterators to the GenerateMinimumSpannigTree algorithm, I can give it to
a class that will perform some classification of this tree. Ok?

Not sure exactly what you mean.

Is it correct that you mean to generate a /corresponding/ tree of
descriptors?

Why not just put the descriptors in the TreeNodes, or if that is frozen
code, use a std::map to associate a descriptor with each TreeNode?

This
class will pass the tree to other members that have to perform some
calculation to perform the classification, that is, the tree will be
read by some functions, for example:

class FactorGraphSolver
{
public:
void SolveFor(QMUL::TreeNode<Descriptor>* node, unsigned categoryID,
unsigned partsLabelNumber);
// other things...
};

And I'm really fine with that function signature, because actually the
FactorGraphSolver needs just a Tree of Descriptors, nothing more,
nothing less.

Ok?

Seems OK. A separate tree of descriptors, describing the nodes of a
TreeNode tree, which itself is a minimum spanning tree for the Item
nodes in some graph.

Let's say that now I want to add a particular additional information
to that tree node, for example a reference to the real descriptor that
generated it, and a label. Then I'll pass to the classification class,
and this class will call the same usual subclasses to perform the
calculations and, once done, will label every node properly. At the end
of the function, I could explore the tree and, being composed of
descriptor that have a reference of the elements that have generated
them, I can label the original elements.

Huh? "real descriptor that generated it", what's that? You lost me.

Ok, the problem is this one. It seems to me that I've said enough to
understand it. I won't post the real code because it's long and mostly
unrelated to the problem.

As I understand it, just generate a parallel tree of descriptors.

I don't see how this ties in to having the factory function generate
nodes of some derived class.

 

[Zeppe]

Not quite. With the above structure you'd have to tentatively downcast
(via Boost's dynamic cast) each TreeNode-pointer to see what actual type
it is, i.e. to determine the type T in TreeNode<T>. Unless all nodes in
a tree have the same T, in which case TreeNodeBase doesn't make sense.

The question for a proper design is essentially: can a tree have nodes
with different item types?

I see. Actually, there is no general way to find out the type T from a
node pointer: it has to be implemented in some way for some particular
types T. And I suppose I can also drop the possibility to have different
types T as now... I just split the methods related to the tree
operations from the methods related to the items. But you're right, at
the moment I don't need the base class.

If the nodes in a given tree can have different item types, I'd suggest
as best solution to require them to be derived from some common abstract
class (an interface class would be best)

that would be NodeBase. It's abstract (of course you couldn't know, I'm
sorry I forgot to say it), having defined:
virtual ~TreeNodeBase() = 0;
(the destructor is implemented as well, it's that funny trick...)
The virtual member allows me to use the dynamic cast functions on the
TreeNode.

, and otherwise, completely
unrelated types, using boost::any (if I recall the name correctly).

I can't understand you. If the nodes are all the same, I would just have
the template class TreeNode. Why boost::any?

Presumably this means that your Items are really graph nodes.

well, they are all the information the node contain, so, mathematically
speaking, they are the graph nodes. In this code, Item is just the
container of the information that I want to associate to a node.

If so, then I suggest moving that factory function out of TreeNode.

It doesn't generate a TreeNode, it generates a Tree.

Good advice. Conceptually much better. Unfortunately I've written this
code for research purposes and I haven't still had the time to make some
slight improvement in the consistency of every concept.

Presumably you mean "the TreeNode constructor".

Sorry, of course I did.

Not sure exactly what you mean.

Is it correct that you mean to generate a /corresponding/ tree of
descriptors?

Why not just put the descriptors in the TreeNodes, or if that is frozen
code, use a std::map to associate a descriptor with each TreeNode?

That is, more or less. Actually, I have different possible types of
descriptors, and all of them, for the sake of the graph, resolve to a
simple vector of doubles (with an additional ID that I need for an
algorithm). In order to generate the tree, however, I need more
information, related to the particular kind of descriptor that I'm
using. That's why in the definition of the GenerateMinimuSpanningTree
there is also the template DistanceMeasure function... this will depend
on the type pointed by the iterators given as argument to that function,
and calculate the appropriate distance.

Seems OK. A separate tree of descriptors, describing the nodes of a
TreeNode tree, which itself is a minimum spanning tree for the Item
nodes in some graph.

Well, it seems mostly ok. In the following I'll explain you with more
detail.

Huh? "real descriptor that generated it", what's that? You lost me.

The initial iterators.. let me show you a more concrete example.
I have an Image (I'm starting from quite far, to let you understand
eveything). From the image I can extract some set of descriptors, that
can be of different types. For example, let's say, ColourDescriptor and
EdgeDescriptor, ok? I want to obtain a tree in which the nodes are
generic Descriptors, made by an ID and a vector of doubles generated by
each different descriptor type (i.e., ColourDescriptor and EdgeDescriptor).

So, each Descriptor implements a method to generate this vector of
double. Now, the tree I want has to connect all the Descriptors.
Considering the set of all the particular type descriptor (for example,
the set of ColourDescriptor) as a fully connected graph, I want the
minimum spanning tree of this graph, in which every node doesn't need to
contain the specific type of descriptor, but just the vector of doubles
and the ID (so, each node it's the associated generic Descriptor).

Here we come: the iterators that are input for the
GenerateMinimumSpanningTree function are iterators to a set of, for
example, ColourDescriptor. The DistanceMeasure function takes two
ColourDescriptor. The generated tree contain general Descriptor
generated by the ColourDescriptor.

Everything now works well. But let's say that at a certain point I my
want to come back from a general Descriptor to the particular
ColourDescriptor that has generated it. It would be good to derive a
DescriptorWithReference, that behaves exaclty as a normal descriptor,
but has got a refernece to the originator, as well. I'd like to apply
all the code I've written without any major change, because it's good
like this.

As I understand it, just generate a parallel tree of descriptors.

So, you are suggesting me to generate a tree of the original particular
descriptors (let's say, ColourDescriptor). Then, generate a tree with
the same structure but of general Descriptor. While generating the
second tree, I build a map to memorize all the correspondences. Then I
use the original tree (that fortunately won't be modified in the
structure). And, at the end, I recover the information from the map and
the two tree combined?

Do you know what? probably it's not the cleanest solution ever, but
considering that the memory for the duplication of the tree and the map
shouldn't be a problem, it can be the clearest way to proceed, also
because the code structure stays quite plain and the old code will keep
working.

I don't see how this ties in to having the factory function generate
nodes of some derived class.

I hope it's clear now that I given you more details!

Thank you!

Zeppe