C++Talk.NET Forum Index C++Talk.NET
C++ language newsgroups
 
Archives   FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

A recurring problem with inheritance

 
Post new topic   Reply to topic    C++Talk.NET Forum Index -> C++ Language (Moderated)
View previous topic :: View next topic  
Author Message
Steven T. Hatton
Guest
PostPosted: Sun Aug 15, 2004 10:53 am    Post subject: A recurring problem with inheritance Reply with quote


I may once have found a solution to this problem, but I don't recall what it
was if I did find it. There are circumstances in which recursion provides
an elegant and natural means of building composite data structures. That
is, one node in a structure generates another instance of its object type
as a child(in a tree), or a sibling(in a list). I will call both trees and
lists, graphs herein.

The algorithm for creating the structure can be isolated from the other
aspects of the node. For example, suppose you are assembling nested
widgets in a GUI. The layout information, such as width, height, position,
etc. is not an essential part of the graph building algorithm. The
algorithm only cares about whether the current node needs to construct an
additional child or sibling node.

This means the members of the node class pointing to other nodes, and the
code for assembling the node can be placed in a base class that knows
nothing about layout. When we construct nodes we pass the necessary
information about what subsequent nodes may need to be constructed to the
sibling, or child nodes we are constructing. This is good OO design. We
abstract the essential from the incidental and make the essential part of a
base class.

So far, so good. But now we hit a snag. When the constructor of the base
class is called, it knows nothing about derived classes. It can be
expected to construct the appropriate base class nodes determined by the
information it receives from its predecessor. We can't, however expect it
to construct nodes of the derived type. The bit of useless code below
demonstrates the dilemma. The alternatives involve putting the construction
code for the graph outside the node class, or in a static "factory" member
function, or in the most derived class. Any other suggestions?

#include <iostream>
#include <vector>
#include <string>

using std::cout;
using std::ostream;
using std::string;

class BaseNode {
BaseNode * next;
int count;
public:
BaseNode(const int& more);
virtual ~BaseNode();
virtual ostream& print(ostream& out) const;
};

BaseNode::BaseNode(const int& more)
: next(0),
count(more)
{
if(more)
{
this->next = new BaseNode(more - 1);
}
}

BaseNode::~BaseNode()
{
delete next;
cout << "~BaseNode: #" << count << "n";
}

ostream& BaseNode::print(ostream& out) const
{
if(next)
{
next->print(out);
}
return out << "BaseNode: #" << count << "n";
}

ostream& operator<<(ostream& out, const BaseNode& bn)
{
return bn.print(out);
}

//----------------------------------------------------
class DerivedNode: public BaseNode{
string message;
public:
DerivedNode(const int more, const string& message_="I've got more data");

ostream& print(ostream& out) const;
};

DerivedNode::DerivedNode(const int more, const string& message_)
: BaseNode(more), //constructs list of BaseNode with DerivedNode as head.
message(message_)
{}

ostream& DerivedNode::print(ostream& out) const
{
out << "DerivedNode::BaseNode::print(out)n";
BaseNode::print(out);
return out << "DerivedNode message: " << this->message << "n";
}

ostream& operator<<(ostream& out, const DerivedNode& dn)
{
return dn.print(out);
}


int main(int argc, char* argv[]){
BaseNode bn(5);
cout << bn << "n";

cout << "------------n";

DerivedNode dn(5);

cout << dn << "n";
}

$ ./node
BaseNode: #0
BaseNode: #1
BaseNode: #2
BaseNode: #3
BaseNode: #4
BaseNode: #5

------------
DerivedNode::BaseNode::print(out)
BaseNode: #0
BaseNode: #1
BaseNode: #2
BaseNode: #3
BaseNode: #4
BaseNode: #5
DerivedNode message: I've got more data

~BaseNode: #0
~BaseNode: #1
~BaseNode: #2
~BaseNode: #3
~BaseNode: #4
~BaseNode: #5
~BaseNode: #0
~BaseNode: #1
~BaseNode: #2
~BaseNode: #3
~BaseNode: #4
~BaseNode: #5
--
Regards,
Steven

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
Back to top
Dag Viken
Guest
PostPosted: Tue Aug 17, 2004 8:00 pm    Post subject: Re: A recurring problem with inheritance Reply with quote


"Steven T. Hatton" <hattons (AT) globalsymmetry (DOT) com> wrote

Quote:
So far, so good. But now we hit a snag. When the constructor of the base
class is called, it knows nothing about derived classes. It can be
expected to construct the appropriate base class nodes determined by the
information it receives from its predecessor. We can't, however expect it
to construct nodes of the derived type. The bit of useless code below
demonstrates the dilemma. The alternatives involve putting the
construction
code for the graph outside the node class, or in a static "factory" member
function, or in the most derived class. Any other suggestions?

Try making your base class a template class with the derived class as a
parameter. That way you can easily create instances of the derived class in
the base class constructor. However, only constructor parameters for the
base class can be passed to the derived class constructor. One way to get
around this is to specify optional parameters to the class constructors.

#include <iostream>
#include <vector>
#include <string>

using std::cout;
using std::ostream;
using std::string;

template<class Derived>
class BaseNodeT {
protected:
BaseNodeT * next;
int count;
public:
BaseNodeT(int more, const string& optpar1 = "")
: next(0),
count(more)
{
if(more)
{
next = new Derived(more - 1, optpar1);
}
}
virtual ~BaseNodeT()
{
delete next;
cout << "~BaseNodeT: #" << count << "n";
}
virtual ostream& print(ostream& out) const
{
if(next)
{
next->print(out);
}
return out << "BaseNodeT: #" << count << "n";
}
};

template ostream& operator<<(ostream& out, const BaseNodeT {
return bn.print(out);
}

//----------------------------------------------------
class BaseNode: public BaseNodeT<BaseNode>{
typedef BaseNodeT<BaseNode> BaseT;
public:
BaseNode(int more, const string& optpar1=""): BaseT(more) {};
};

//----------------------------------------------------
class DerivedNode: public BaseNodeT<DerivedNode>{
typedef BaseNodeT<DerivedNode> BaseT;
string message;
public:
DerivedNode(int more, const string& message_="I've got more data");

ostream& print(ostream& out) const;
};

DerivedNode::DerivedNode(const int more, const string& message_)
: BaseT(more, message_), //constructs list of DerivedNode's
message(message_)
{
}

ostream& DerivedNode::print(ostream& out) const
{
out << "DerivedNode::BaseNodeT BaseT::print(out);
return out << "DerivedNode message: " << this->message << "n";
}

ostream& operator<<(ostream& out, const DerivedNode& dn)
{
return dn.print(out);
}


int main(int argc, char* argv[]){
BaseNode bn(5);
cout << bn << "n";

cout << "------------n";

DerivedNode dn(5, "This works");

cout << dn << "n";
}

Dag


[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

Back to top
Steven T. Hatton
Guest
PostPosted: Fri Aug 20, 2004 1:35 am    Post subject: Re: A recurring problem with inheritance Reply with quote


Dag Viken wrote:

Quote:
"Steven T. Hatton" <hattons (AT) globalsymmetry (DOT) com> wrote in message
news:gsmdnUxsrZOQ-oPcRVn-qw (AT) speakeasy (DOT) net...
So far, so good. But now we hit a snag. When the constructor of the
base
class is called, it knows nothing about derived classes. It can be
expected to construct the appropriate base class nodes determined by the
information it receives from its predecessor. We can't, however expect
it to construct nodes of the derived type. The bit of useless code below
demonstrates the dilemma. The alternatives involve putting the
construction
code for the graph outside the node class, or in a static "factory"
member
function, or in the most derived class. Any other suggestions?

Try making your base class a template class with the derived class as a
parameter. That way you can easily create instances of the derived class
in the base class constructor. However, only constructor parameters for
the base class can be passed to the derived class constructor. One way to
get around this is to specify optional parameters to the class
constructors.

In an effort to understand what is actually happening, I attempted to strip
your example of all but the bare essentials of the recursive mechanism. I
believe that is represented in the following. I have to confess, I do not
understand exactly what is going on. My questions are included as comments
in the code.

/* A template for classes of BaseNodeT<Derived_T> */

template<class Derived>
class BaseNodeT {
protected:
BaseNodeT * next;
int count;
public:
BaseNodeT(int more)
: next(0),
count(more)
{
if(more)
{
next = new Derived(more - 1); // clearly the essential operation.
}
}
//destructor omitted.
};


//----------------------------------------------------
class BaseNode: public BaseNodeT<BaseNode>{
typedef BaseNodeT<BaseNode> BaseT; // is this more than shorthand?
public:
BaseNode(int more): BaseT(more) {};
};

//----------------------------------------------------
class DerivedNode: public BaseNodeT<DerivedNode>{
typedef BaseNodeT<DerivedNode> BaseT; // is the use of the same
// name 'BaseT' significant?
public:
DerivedNode(int more);

};

DerivedNode::DerivedNode(const int more)
: BaseT(more) //constructs list of DerivedNode's
{}

I've been trying to figure out if I can get g++ to produce the instantiated
template in a form that is equivalent to the C++ code for the class being
produced. I don't know if such a tool is available, but it might prove to
be a valuable device for understanding what your template is actually
producing.

--
Regards,
Steven

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

Back to top
Dag Viken
Guest
PostPosted: Sun Aug 22, 2004 10:49 pm    Post subject: Re: A recurring problem with inheritance Reply with quote
"Steven T. Hatton" <hattons (AT) globalsymmetry (DOT) com> wrote

Quote:
Dag Viken wrote:

"Steven T. Hatton" <hattons (AT) globalsymmetry (DOT) com> wrote in message
news:gsmdnUxsrZOQ-oPcRVn-qw (AT) speakeasy (DOT) net...
So far, so good. But now we hit a snag. When the constructor of the
base
class is called, it knows nothing about derived classes. It can be
expected to construct the appropriate base class nodes determined by
the
information it receives from its predecessor. We can't, however expect
it to construct nodes of the derived type. The bit of useless code
below
demonstrates the dilemma. The alternatives involve putting the
construction
code for the graph outside the node class, or in a static "factory"
member
function, or in the most derived class. Any other suggestions?

Try making your base class a template class with the derived class as a
parameter. That way you can easily create instances of the derived class
in the base class constructor. However, only constructor parameters for
the base class can be passed to the derived class constructor. One way
to
get around this is to specify optional parameters to the class
constructors.

In an effort to understand what is actually happening, I attempted to
strip
your example of all but the bare essentials of the recursive mechanism. I
believe that is represented in the following. I have to confess, I do not
understand exactly what is going on. My questions are included as comments
in the code.

/* A template for classes of BaseNodeT<Derived_T> */

template<class Derived
class BaseNodeT {
protected:
BaseNodeT * next;
int count;
public:
BaseNodeT(int more)
: next(0),
count(more)
{
if(more)
{
next = new Derived(more - 1); // clearly the essential operation.
}
}
//destructor omitted.
};


//----------------------------------------------------
class BaseNode: public BaseNodeT typedef BaseNodeT<BaseNode> BaseT; // is this more than shorthand?

No, it is just so I can just type BaseT instead of BaseNodeT<BaseNode>.
You can get rid of it and write the constructor below as:
BaseNode(int more): BaseNodeT<BaseNode>(more) {};

Quote:
public:
BaseNode(int more): BaseT(more) {};
};

//----------------------------------------------------
class DerivedNode: public BaseNodeT<DerivedNode>{
typedef BaseNodeT<DerivedNode> BaseT; // is the use of the same
// name 'BaseT' significant?

No, it is just I name I picked for a template base class.

Quote:
public:
DerivedNode(int more);

};

DerivedNode::DerivedNode(const int more)
: BaseT(more) //constructs list of DerivedNode's
{}

I've been trying to figure out if I can get g++ to produce the
instantiated
template in a form that is equivalent to the C++ code for the class being
produced. I don't know if such a tool is available, but it might prove to
be a valuable device for understanding what your template is actually
producing.

--
Regards,
Steven

The DerivedNode class instantiates the following base class (just the
differences from the template definition shown):

template<>
class BaseNodeT<DerivedNode> {
:
next = new DerivedNode(more - 1);
:
};

The BaseNode class instantiates this baseclass:

template<>
class BaseNodeT<BaseNode> {
:
next = new BaseNode(more - 1);
:
};

Each derived class instantiates its own unique base class. In non-templated
C++ code you are not able to refer to a derived class in the base class
since the derived class has not been defined yet. With templates used as
shown, the base class is instantiated within the derived class declaration
so the base class has access to the derived class.

Dag


[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

Back to top
Glen Low
Guest
PostPosted: Mon Aug 23, 2004 10:30 am    Post subject: Re: A recurring problem with inheritance Reply with quote
Quote:
So far, so good. But now we hit a snag. When the constructor of the base
class is called, it knows nothing about derived classes. It can be
expected to construct the appropriate base class nodes determined by the
information it receives from its predecessor. We can't, however expect it
to construct nodes of the derived type. The bit of useless code below
demonstrates the dilemma. The alternatives involve putting the construction
code for the graph outside the node class, or in a static "factory" member
function, or in the most derived class. Any other suggestions?

BaseNode::BaseNode(const int& more)
: next(0),
count(more)
{
if(more)
{
this->next = new BaseNode(more - 1);
}
}

1. You could move this code to the (each) derived class constructor.
2. You could declare a templated constructor as follows:

class BaseNode
{
public:
template <typename T> BaseNode (const int& more, T* /* dummy */)
....
{
if (more)
this->next = new T(more - 1);
}
};

Note that this strange beast of a templated constructor is called
regularly like this:

BaseNode b (7, (DerivedNode*) NULL);

The second parameter is a dummy parameter that does nothing except
select the right template specialization (you can't specify it
directly with such a templated constructor).

Thus your derived class would look like:

class DerivedNode: public BaseNode
{
public:
DerivedNode (const int& more): BaseNode (more, (DerviedNode*)
NULL)
{
}
};

This is fairly clean from the client POV since all public classes are
non-templates and have a single root in BaseNode, and so probably live
quite well in GUI space. (Solutions where BaseNode is a template don't
have these properties.)

Cheers,
Glen Low, Pixelglow Software
www.pixelglow.com

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

Back to top
Display posts from previous:   
Post new topic   Reply to topic    C++Talk.NET Forum Index -> C++ Language (Moderated) All times are GMT
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum


Powered by phpBB © 2001, 2006 phpBB Group
SEO toolkit © 2004-2006 webmedic.