Re: Visitor, dynamic_cast or ...

From: H. S. Lahman (h.lahman_at_verizon.net)
Date: 10/25/03 

Date: Sat, 25 Oct 2003 20:58:55 GMT

Responding to Lagae...

> Each time i run into the same problem. I have a base class with sometimes as
> less as 2 derived classes. I put them in some datastructure (so i do need
> the base class (even with type safe containers like the ones in stl)). Then
> off course i loose type information. Sometimes this can be solved with
> virtual functions, sometimes not. In the cases where it cannot be solved
> with virtuals ,each time i find myselve considering these solutions:
>
> (1) use visitors
> (2) use dynamic_cast
> (3) group everything into a single class

As soon as dynamic_downcast becomes a viable alternative one should be
suspicious that there are missing relationships. (There are exceptions
but they involve external object streams where one cannot know the type
of a particular object and there are no other language facilities to
deal with determining the type.)

>
> (2) i dont like dynamic_cast, also because it incurs a performance penalty
> (1) is faster than (2) but can lead to very awkward implementations
> sometimes (see further)
> (3) dont like this one
>
> To illustrate my problem: suppose you are building a set of classes to work
> with octrees. For those of you that are not familiar with octrees: An octree
> is a datastructure similar to a binary search tree. Start with a cube.
> Divide the cube into 8 equal octants, recursively apply the subdivision to
> some cells. This way you end op with a tree with two kinds of nodes:
> internal nodes have (exactly) 8 children, the children can be leaf nodes or
> internal nodes, the 8 children are not necesarily of the same type. Leaf
> nodes contain some data. This data structure can be used for range queries
> (like a kd-tree, but splits up each of the 3 dimensions in each node), or to
> represent sparse 3d arrays of data (cells with equal data are grouped).
> Octrees are used to represent such sparse grids that would otherwise not fit
> in memory.

The basic octree seems very similar a basic Composite pattern:

          0..1 1 *
[Client] ----------- [Node] --------------+
                        A |
                        | |
                +-------+------+ |
                | | 1 |
             [Leaf] [Internal] ----+

The difference is that the [Internal] nodes do not share behaviors with
[Leaf] nodes (e.g., operation() in the GoF pattern). That is, the
[Internal] nodes are purely navigational while the [Leaf] nodes have the
properties a Client actually wants.

That suggests that there are two relationships between [Client] and the
octree. One relationship is used purely for navigation to get to a
particular Leaf. Once the Leaf is reached, the other relationship is
instantiated:

          1 navigates 1
[Client] --------------------- [OcTree]
    | 1 | 0..1
    | |
    | currently accesses | starts at
    | 1 | 1
[Leaf] [Internal] ----------+
    | | 1 |
    | | |
    +--------------+----------------+ |
                   | |
                   - |
                   V |
                [Node] ------------------------------+
                       * parent of

In this case the intelligence of navigating the Composite-like tree
lives in [OcTree]. For example, it might have a Find(key) method that
is accessed by [Client] that always returns a Leaf reference. Since the
distinction between [Leaf] and [Internal] is purely a matter of
navigating the tree (i.e., that a limb is terminated), [OcTree] does not
have to understand which subclass it has in hand in any behavioral
sense. So one can use a simple type attribute to distinguish [Leaf] vs.
[Internal] for navigation purposes. Or one can incorporate that into
the [Node] identity key (e.g., setting the MSB).

When OcTree.Find returns a Leaf, that effectively instantiates the
[Client]/[Leaf] relationship. So [Client] does not know that [Internal]
nodes even exist.

[Note that the 1:* relationship being fixed at 8 allows additional
optimization at the OOP level because it can be a fixed array of Node*
references.]

This yields a fairly simple and efficient view of the tree that doesn't
require complexities like Visitor, nastiness like dynamic_downcast, or
god classes. However, that is only accomplished by separating the
concerns of tree navigation from leaf processing (i.e., by implementing
and navigating a second relationship).

*************
There is nothing wrong with me that could
not be cured by a capful of Drano.

H. S. Lahman
hsl@pathfindermda.com
Pathfinder Solutions -- Put MDA to Work
http://www.pathfindersol.com
(888)-OOA-PATH

Relevant Pages

  • Re: Visitor, dynamic_cast or ...
    ... >> is a datastructure similar to a binary search tree. ... > The basic octree seems very similar a basic Composite pattern: ... Once the Leaf is reached, ... > concerns of tree navigation from leaf processing (i.e., ...
    (comp.object)
  • Re: Visitor, dynamic_cast or ...
    ... An OcTree can have 0..N Nodes. ... It is so only because its responsibility is to understand the ... >>necessary navigation be be done exactly the same way. ... the Leaf class becomes redundent. ...
    (comp.object)
  • Re: Visitor, dynamic_cast or ...
    ... which means that every navigation context must ... understand the rules for conditionality. ... In my version the only conditional association end was on the OcTree ... given internal Node can have a mix of internal and leaf children). ...
    (comp.object)
  • Re: Questions for the Next Manifestation
    ... of this earth, have failed, throughout the long period of their ... When a tree grows, every step of the way, that part ... of the tree was destined to be a leaf. ... being the preservation of our genetic code to the preservation of our ...
    (soc.religion.bahai)
  • Re: Cantor and the binary tree
    ... As far as the tree construction goes, you might notice that the binary ... one of each of those is a leaf and the other not. ... there are also some considerations of the continuity of the real number ... one that acknowledges the infinite. ...
    (sci.math)