Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > testing parent-child relations using only id's

Reply
Thread Tools

testing parent-child relations using only id's

 
 
Suzanne Vogel
Guest
Posts: n/a
 
      12-28-2003
Hi,

I've been trying to write a function to test whether one class is
derived from another class. I am given only id's of the two classes.
Therefore, direct use of template methods is not an option.

Let's call the id of a class "cid" (for "class id").

The function signature should look like this:
******************************************
bool isDerivedFrom(cid child, cid parent);
******************************************

I see two basic options:
(1) Test whether we can typecast from an instance of the child class to
an instance of the parent class. If the typecast fails (by returning
NULL or throwing an exception), then we know that the child is *not*
derived from the parent. eg,
(a) Use dynamic_cast<> (somehow), since it throws an exception if
you try to cast to a non-parent class.
(2) Manually (as preprocessing) build a tree structure of id's that
parallels the actual class hierarchy, to examine later during runtime.

I would *much* prefer option#1, since it is more extensible. However, it
is difficult to figure out how, since it requires templates under the
hood, and these must be abstracted away to cid's in the final function
signature. That is why I am writing to this newsgroup.

Perhaps under the hood, we can use dynamic_cast<> in a helper function:

template<class TChild, class TParent>
bool isDerivedFrom()
{
TChild* child = new TChild();
try
{ dynamic_cast<TParent*>(child);
}
catch(exception&) { return false; }

return true;
}

************************************************** **********************************
How can I get the 'isDerivedFrom(cid child, cid parent)' function to
call this templated version appropriately?
************************************************** **********************************

Here are the utilities that I have to work with:
(1) A generic IObj superclass, as parent to all classes in the system.
Each subclass has an associated cid and implements a virtual getter
function for it:
const cid IObj::getCID(); //get the cid for this class
(2) A mapping from cid's to create functions which return an instance of
the specified class, as an IObj* pointer:
IObj* getNewObj(cid c);
(3) (probably not useful in this case) A mapping from cid's to strings
representing class names:
string& getClassName(cid c);

Here are some problems I discovered in my implementation attempts, which
we need to be aware of:
(1) Casting from IObj* always fails via dynamic_cast<> (since IObj is
parent to every class, and dynamic_cast<> can only cast from child classes).
(2) Casting from void* always succeeds via C-cast (since it is totally
non-typesafe) and cannot be done at all via dynamic_cast<>.

For instance, I tried this, but it always fails due to #1:

template<class TParent>
bool isDerivedFrom(cid child)
{
IObj* childObj = getNewObj(child);
try
{ dynamic_cast<TParent*>(childObj); //always fails, since childObj
is a ptr to IObj, *not* a ptr to whatever its ultimate derived type is
}
catch(exception&) { return false; }

return true;
}

The real magic would be to use ***MACROS***, to temporarily forgo uses
of IObj.

************************************************** **********************************
How can I implement the macro(s) "MACRO_GET_CLASS_NAME" and/or
"MACRO_GET_CHILD_OBJ" below?
************************************************** **********************************

MAGIC #1. (How can I implement the macros here?)

bool isDerivedFrom(cid child, cid parent)
{
try
{
dynamic_cast<MACRO_GET_CLASS_NAME(parent)>(MACRO_G ET_CHILD_OBJ(child));
}
catch(exception&) { return false; }

return true;
}

MAGIC #2. (How can I implement the macro here?)

template<class T>
class WrapperClass
{
static bool isDerivedFrom(cid child) // this func ptr can be stored
*non-templated* in a map of (cid, static funcs), so it's useful
{
try
{ dynamic_cast<T>(MACRO_GET_CHILD_OBJ(child));
}
catch(exception&) { return false; }

return true;
}
};

I tried the following, but attempting to use them in "MAGIC #1" and
"MAGIC#2" did not compile. I also *hate* them because they require
exhaustively listing class id's,

which is not very extensible (eg, if someone else wants to add classes
to my program).

#define MACRO_GET_CLASS_NAME(id) ( \
id == kCID_Foo ? Foo \
: id == kCID_Bar ? Bar \
: NILL )


#define MACRO_GET_CHILD_OBJ(id) ( \
( id == kCID_Foo ? new Foo() \
: id == kCID_Bar ? new Bar() \
: NULL ) )

(Please ignore the memory leaks resulting from using "new" without using
"delete" here. I had a solution to prevent that, but it's not worth
cluttering my questions here by presenting it. )

Aaargh! Where's a hack when you need one? I'm about to hack out my
brains.

Thanks for any suggestions.

Suzanne

 
Reply With Quote
 
 
 
 
Jeff Schwab
Guest
Posts: n/a
 
      12-28-2003
Suzanne Vogel wrote:
> Hi,
>
> I've been trying to write a function to test whether one class is
> derived from another class. I am given only id's of the two classes.


What do you mean by "id's?" At first I thought you meant the type_info
objects returned by the typeid operator, but after reading below, I
guess you mean integer constants.

> Therefore, direct use of template methods is not an option.
>
> Let's call the id of a class "cid" (for "class id").
>
> The function signature should look like this:
> ******************************************
> bool isDerivedFrom(cid child, cid parent);
> ******************************************
>
> I see two basic options:
> (1) Test whether we can typecast from an instance of the child class to
> an instance of the parent class. If the typecast fails (by returning
> NULL or throwing an exception), then we know that the child is *not*
> derived from the parent. eg,
> (a) Use dynamic_cast<> (somehow), since it throws an exception if
> you try to cast to a non-parent class.
> (2) Manually (as preprocessing) build a tree structure of id's that
> parallels the actual class hierarchy, to examine later during runtime.


Why does that need to be done as preprocessing? Anyway, I think such a
"tree structure" is what you need. TC++PL has a similar example (p.
416) using a std::map, with class names as the keys.

> I would *much* prefer option#1, since it is more extensible. However, it
> is difficult to figure out how, since it requires templates under the
> hood,


It does?

> and these must be abstracted away to cid's in the final function
> signature. That is why I am writing to this newsgroup.
>
> Perhaps under the hood, we can use dynamic_cast<> in a helper function:
>
> template<class TChild, class TParent>
> bool isDerivedFrom()
> {
> TChild* child = new TChild();
> try
> { dynamic_cast<TParent*>(child);


That cast will never throw. dynamic_cast only throws when you try to
cast to a reference; if a cast to a pointer type fails, dynamic_cast
just returns 0. Anyway, no cast is needed in this situation; a pointer
to a child class always can be assigned to a pointer to any of the
child's public base classes. In your example, if TChild does *not* have
TParent as a public base, you'll get a compile-time error.

> }
> catch(exception&) { return false; }


Why are you trying to catch a temporary by non-const reference?

>
> return true;
> }
>
> ************************************************** **********************************
>
> How can I get the 'isDerivedFrom(cid child, cid parent)' function to
> call this templated version appropriately?
> ************************************************** **********************************
>
>
> Here are the utilities that I have to work with:
> (1) A generic IObj superclass, as parent to all classes in the system.
> Each subclass has an associated cid and implements a virtual getter
> function for it:
> const cid IObj::getCID(); //get the cid for this class
> (2) A mapping from cid's to create functions which return an instance of
> the specified class, as an IObj* pointer:
> IObj* getNewObj(cid c);
> (3) (probably not useful in this case) A mapping from cid's to strings
> representing class names:
> string& getClassName(cid c);
> Here are some problems I discovered in my implementation attempts, which
> we need to be aware of:
> (1) Casting from IObj* always fails via dynamic_cast<> (since IObj is
> parent to every class, and dynamic_cast<> can only cast from child
> classes).


I think you've got it backwards: dynamic_cast is used to cast from
parent classes to their children.

> (2) Casting from void* always succeeds via C-cast (since it is totally
> non-typesafe) and cannot be done at all via dynamic_cast<>.
>
> For instance, I tried this, but it always fails due to #1:
>
> template<class TParent>
> bool isDerivedFrom(cid child)
> {
> IObj* childObj = getNewObj(child);
> try
> { dynamic_cast<TParent*>(childObj); //always fails, since childObj is
> a ptr to IObj, *not* a ptr to whatever its ultimate derived type is
> }
> catch(exception&) { return false; }
>
> return true;
> }
>
> The real magic would be to use ***MACROS***, to temporarily forgo uses
> of IObj.


If you can't write the code by hand, what makes you think the
preprocessor can? Repeat after me: screw macros... screw macros...

<snip> bunch of nonsense with macros </snip>

> Aaargh! Where's a hack when you need one? I'm about to hack out my
> brains.


I know how you feel. I'm not sure you need a "hack" just yet, though.

Try creating a bunch of class templates, one for CID, that defines the
exact type of the corresponding class. Then, use a dynamic_cast as a
"blood test" to figure out whether "parent" really is the daddy. In
fact, you can just return the result of the dynamic cast.

Good luck,
Jeff

Btw, if that all sounds like gibberish, say the word.

> Thanks for any suggestions.
>
> Suzanne
>


 
Reply With Quote
 
 
 
 
Jeff Schwab
Guest
Posts: n/a
 
      12-28-2003

> Try creating a bunch of class templates, one for each CID to define the
> exact type of the corresponding class. Then, use a dynamic_cast as a
> "blood test" to figure out whether "parent" really is the daddy. In
> fact, you can just return the result of the dynamic cast.


Just realized this will only work if the CID's with which your function
is called are known at compile time. Do you know whether this is the
case? Do you know exactly how the function will be called?

Thanks,
Jeff

 
Reply With Quote
 
Jeff Schwab
Guest
Posts: n/a
 
      12-28-2003
Jeff Schwab wrote:
>
>> Try creating a bunch of class templates, one for each CID to define
>> the exact type of the corresponding class. Then, use a dynamic_cast
>> as a "blood test" to figure out whether "parent" really is the daddy.
>> In fact, you can just return the result of the dynamic cast.

>
>
> Just realized this will only work if the CID's with which your function
> is called are known at compile time. Do you know whether this is the
> case? Do you know exactly how the function will be called?


Oh, and one more thing...

Are the CID's consecutive? If so, there's a straightforward, run-time
approach that will work in constant time and requires no templates.
Create an array of pointers to objects of abstract class "Comparator,"
or some such name. For each class with a CID, derive a class from both
Comparator and the class with the CID, and add it to the array at an
index corresponding to the CID. Your function can use the CID's as
indices into the array, and call methods of the Comparator-derived
objects. Inside those methods, the exact type of each object will be known.

Better yet, if you know the whole hierarchy ahead of time, you could
just build a big table of bool's. Even if the CID's aren't consecutive,
you could build a map with std:air< CID, CID > as keys and bool's as
values.

 
Reply With Quote
 
Martin Eisenberg
Guest
Posts: n/a
 
      12-28-2003
Hi,

Jeff Schwab wrote:

> Better yet, if you know the whole hierarchy ahead of time, you
> could just build a big table of bool's. Even if the CID's
> aren't consecutive, you could build a map with std:air< CID,
> CID > as keys and bool's as values.


How does that compare to a multimap<CID, CID> where the presence of a
particular ID pair would tell what your bool does?


Martin
 
Reply With Quote
 
Jeff Schwab
Guest
Posts: n/a
 
      12-28-2003
Martin Eisenberg wrote:
> Hi,
>
> Jeff Schwab wrote:
>
>
>>Better yet, if you know the whole hierarchy ahead of time, you
>>could just build a big table of bool's. Even if the CID's
>>aren't consecutive, you could build a map with std:air< CID,
>>CID > as keys and bool's as values.

>
>
> How does that compare to a multimap<CID, CID> where the presence of a
> particular ID pair would tell what your bool does?
>
>
> Martin


Since the keys are unique, I don't think a multimap makes sense here.
On the other hand, your idea of testing for the very presence of keys
(rather than mapping them to boolean values) is a good one, and will
have a smaller footprint in memory. Instead of a std::map, a std::set<
std:air< CID, CID > > probably makes the most sense.

-Jeff

 
Reply With Quote
 
Suzanne Vogel
Guest
Posts: n/a
 
      12-29-2003
Thanks for responding. I decided to ditch the dynamic_cast<> idea and
just go with a prebuilt-map of cid's.

>> I've been trying to write a function to test whether one class is
>> derived from another class. I am given only id's of the two classes.

>
> What do you mean by "id's?" At first I thought you meant the type_info
> objects returned by the typeid operator, but after reading below, I
> guess you mean integer constants.


Yes, integer constants.

>> Therefore, direct use of template methods is not an option.
>>
>> Let's call the id of a class "cid" (for "class id").
>>
>> The function signature should look like this:
>> ******************************************
>> bool isDerivedFrom(cid child, cid parent);
>> ******************************************
>>
>> I see two basic options:
>> (1) Test whether we can typecast from an instance of the child class
>> to an instance of the parent class. If the typecast fails (by
>> returning NULL or throwing an exception), then we know that the child
>> is *not* derived from the parent. eg,
>> (a) Use dynamic_cast<> (somehow), since it throws an exception if
>> you try to cast to a non-parent class.
>> (2) Manually (as preprocessing) build a tree structure of id's that
>> parallels the actual class hierarchy, to examine later during runtime.

>
> Why does that need to be done as preprocessing? Anyway, I think such a
> "tree structure" is what you need.


Yes, I decided on (2). Here's how:

Register classes as (cid, set<cid>) pairs at the beginning of the
program, where set<cid> represents all the direct parents of cid. After
registering all classes, "preprocess" (okay, sorry: misuse of
terminology) by transforming into (cid, set<cid>) pairs, where set<cid>
represents *all* predecessors (parents, grandparents, great-,...) of
cid. Then, start the main program loop which uses this inheritance
structure. If class A is derived from class B, then the cid of A has a
set<cid> which contains the cid of B.

It works. I could've done it before, but I so wanted to use
dynamic_cast<>! :-O

>> I would *much* prefer option#1, since it is more extensible. However,
>> it is difficult to figure out how, since it requires templates under
>> the hood,

>
> It does?


dynamic_cast<> is templated. That's all I meant.

>> and these must be abstracted away to cid's in the final function
>> signature. That is why I am writing to this newsgroup.
>>
>> Perhaps under the hood, we can use dynamic_cast<> in a helper function:
>>
>> template<class TChild, class TParent>
>> bool isDerivedFrom()
>> {
>> TChild* child = new TChild();
>> try
>> { dynamic_cast<TParent*>(child);

>
> That cast will never throw.


It does in my test program. It works.

> dynamic_cast only throws when you try to
> cast to a reference;


Or to a pointer.

> if a cast to a pointer type fails, dynamic_cast
> just returns 0.


No, it throws an exception.

> Anyway, no cast is needed in this situation; a pointer
> to a child class always can be assigned to a pointer to any of the
> child's public base classes.


I know, but I want to *test* whether TChild is *truely* a child of
TParent. I don't know that it is. I know that in some situations it
won't be, and the cast will fail. (And it does fail.)

> In your example, if TChild does *not* have
> TParent as a public base, you'll get a compile-time error.


No, that's static_cast<>, not dynamic_cast<>.

>> }
>> catch(exception&) { return false; }

>
> Why are you trying to catch a temporary by non-const reference?


I don't care about the exception itself. All I care is that one was raised.

>> return true;
>> }
>>
>> ************************************************** **********************************
>>
>> How can I get the 'isDerivedFrom(cid child, cid parent)' function to
>> call this templated version appropriately?
>> ************************************************** **********************************


>> (1) Casting from IObj* always fails via dynamic_cast<> (since IObj is
>> parent to every class, and dynamic_cast<> can only cast from child
>> classes).

>
> I think you've got it backwards: dynamic_cast is used to cast from
> parent classes to their children.


No, I tried it again: dynamic_cast<> casts child to parent. Which makes
sense, since parents are smaller than children, and you'd certainly want
to cast to something smaller than yourself so as not to exceed memory
allocation.

>> (2) Casting from void* always succeeds via C-cast (since it is totally
>> non-typesafe) and cannot be done at all via dynamic_cast<>.
>>
>> For instance, I tried this, but it always fails due to #1:
>>
>> template<class TParent>
>> bool isDerivedFrom(cid child)
>> {
>> IObj* childObj = getNewObj(child);
>> try
>> { dynamic_cast<TParent*>(childObj); //always fails, since childObj
>> is a ptr to IObj, *not* a ptr to whatever its ultimate derived type is
>> }
>> catch(exception&) { return false; }
>>
>> return true;
>> }
>>
>> The real magic would be to use ***MACROS***, to temporarily forgo uses
>> of IObj.

>
> If you can't write the code by hand, what makes you think the
> preprocessor can? Repeat after me: screw macros... screw macros...


Macros are beautiful. I like macros and cheese. Okay, macros don't
work here.

> <snip> bunch of nonsense with macros </snip>
>
>> Aaargh! Where's a hack when you need one? I'm about to hack out my
>> brains.

>
> I know how you feel. I'm not sure you need a "hack" just yet, though.


Thanks for your suggestions. I dehackified my solution. Boring old
cid's, no dynamic_cast<>. Poo.

> Try creating a bunch of class templates, one for CID, that defines the
> exact type of the corresponding class. Then, use a dynamic_cast as a
> "blood test" to figure out whether "parent" really is the daddy. In
> fact, you can just return the result of the dynamic cast.


I thought about that... Wasn't exactly sure what it meant, didn't want
to create one class corresponding to each class in my program...
Realized that it was just beating around the bush and not solving the
real problem: that dynamic_cast<> takes template params and not cid's
(argh!). But thanks for the suggestion.

> Good luck,


Thanks. At least I'm satisfied that dynamic_cast<> is probably *not* the
solution.

> Jeff
>
> Btw, if that all sounds like gibberish, say the word.


Nah. Thanks.

Suzanne

 
Reply With Quote
 
Suzanne Vogel
Guest
Posts: n/a
 
      12-29-2003
>>Better yet, if you know the whole hierarchy ahead of time, you
>>could just build a big table of bool's. Even if the CID's
>>aren't consecutive, you could build a map with std:air< CID,
>>CID > as keys and bool's as values.

>
>
> How does that compare to a multimap<CID, CID> where the presence of a
> particular ID pair would tell what your bool does?


That's kinda what I decided on. I'm using hashmap<cid, set<cid> >, where
cid represents the child and set<cid> represents all its descendents. I
figured it saves space over the map<pair<cid,cid>, bool> idea suggested
above.

(I've never used multimap before. Thanks for the tip.)

Suzanne

 
Reply With Quote
 
Martin Eisenberg
Guest
Posts: n/a
 
      12-29-2003
Jeff Schwab wrote:

> Martin Eisenberg wrote:
>> Hi,
>>
>> Jeff Schwab wrote:
>>
>>
>>>Better yet, if you know the whole hierarchy ahead of time, you
>>>could just build a big table of bool's. Even if the CID's
>>>aren't consecutive, you could build a map with std:air< CID,
>>>CID > as keys and bool's as values.

>>
>>
>> How does that compare to a multimap<CID, CID> where the
>> presence of a particular ID pair would tell what your bool
>> does?
>>
>>
>> Martin

>
> Since the keys are unique, I don't think a multimap makes sense


It turns out that my notion of retrieval from the multiset was wrong.
Suzanne's map<cid, set<cid> > idea is essentially what I had in mind.

> here. On the other hand, your idea of testing for the very
> presence of keys (rather than mapping them to boolean values) is
> a good one, and will have a smaller footprint in memory.
> Instead of a std::map, a std::set< std:air< CID, CID > >
> probably makes the most sense.


I like that the set of pairs is just the definition of a relation.
It needs only one lookup where Suzanne needs two, but in a larger
set. Would that noticeably affect speed? I also tried to figure out
which would be larger, but the results were nonsensical.


Martin
 
Reply With Quote
 
Jeff Schwab
Guest
Posts: n/a
 
      12-29-2003
Martin Eisenberg wrote:
> Jeff Schwab wrote:
>
>
>>Martin Eisenberg wrote:
>>
>>>Hi,
>>>
>>>Jeff Schwab wrote:
>>>
>>>
>>>
>>>>Better yet, if you know the whole hierarchy ahead of time, you
>>>>could just build a big table of bool's. Even if the CID's
>>>>aren't consecutive, you could build a map with std:air< CID,
>>>>CID > as keys and bool's as values.
>>>
>>>
>>>How does that compare to a multimap<CID, CID> where the
>>>presence of a particular ID pair would tell what your bool
>>>does?
>>>
>>>
>>>Martin

>>
>>Since the keys are unique, I don't think a multimap makes sense

>
>
> It turns out that my notion of retrieval from the multiset was wrong.
> Suzanne's map<cid, set<cid> > idea is essentially what I had in mind.
>
>
>>here. On the other hand, your idea of testing for the very
>>presence of keys (rather than mapping them to boolean values) is
>>a good one, and will have a smaller footprint in memory.
>>Instead of a std::map, a std::set< std:air< CID, CID > >
>>probably makes the most sense.

>
>
> I like that the set of pairs is just the definition of a relation.
> It needs only one lookup where Suzanne needs two, but in a larger
> set. Would that noticeably affect speed? I also tried to figure out
> which would be larger, but the results were nonsensical.
>
>
> Martin


Each set carries some overhead. But creating a separate set for each
CID, the overhead has been multiplied by the number of CID's. That's
one reason I prefer the single-set approach. I don't like the added
complication of having two separate containers, either. Both approaches
have logarithmic complexity; which is faster probably depends on the
number of CID's present. A straight table lookup would be faster and
more compact than either of these approaches, if the difference between
the highest and lowest CID's isn't too big.

-Jeff

 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Dropdownlist - relations-asp.net-how to? =?Utf-8?B?UmF2aQ==?= ASP .Net 1 05-17-2004 09:43 PM
Dropdownlist - relations - asp.net =?Utf-8?B?UmF2aQ==?= ASP .Net 1 05-17-2004 07:13 AM
data relations Joe Van Meer ASP .Net 4 05-05-2004 06:57 PM
data relations and datasets inquiry Joe Van Meer ASP .Net 0 05-05-2004 01:30 PM
Can't decide between Relations::Family and Class::DBI Nicolas STAMPF Perl 0 05-04-2004 12:16 PM



Advertisments