Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!evax!utacfd!letni!texsun!newstop!exodus!rbbb.Eng.Sun.COM!chased
From: chased@rbbb.Eng.Sun.COM (David Chase)
Newsgroups: comp.lang.c++
Subject: Re: asking an object for its type
Message-ID: <8608@exodus.Eng.Sun.COM>
Date: 26 Feb 91 02:03:57 GMT
References: <23984@netcom.COM> <1190@sheol.UUCP> <1991Feb19.000449.22255@gpu.utcs.utoronto.ca> <607@taumet.com> <65451@brunix.UUCP> <11284@pasteur.Berkeley.EDU> <70870@microsoft.UUCP>
Sender: news@exodus.Eng.Sun.COM
Organization: Sun Microsystems, Mt. View, Ca.
Lines: 32

In article <70870@microsoft.UUCP> jimad@microsoft.UUCP (Jim ADCOCK) writes:
>A "trivial" solution to the run-time type problem ought to be closer
>to O(1) than O(N), where N is the number of classes that need to have
>some notion of run-time type.  ...

>I'd like to see consideration of some standard features in support of
>run-time type.

Do note that (using algorithms known to me) run-time type-checks and
subtype queries can be implemented much more efficiently in the
single-inheritance case.  This doesn't directly help C++, unless you
choose to limit the problem that you are trying to solve.

IF you use the single-inheritance model,

  "S subtype of T?"

can be answered in O(1) time, given O(N) off-line preprocessing which
yields an O(N) sized data structure.  Answering

  "nearest supertype of S in {T1,...,TM}?"

can be answered in O(logM) time, given (in addition to the above
preprocessing) O(MlogM) preprocessing which yields an O(M) sized data
structure.  The algorithms to do this can be extracted from a paper by
Dietz (I think), but I don't have the citation immediately available.

Compiler/linker/run-time support is useful in solving this problem, by
the way.

David Chase
Sun