Re: [boost] Re: dynamic inheritance with FC++

From: Brian McNamara (lorgon_at_[hidden])
Date: 2004-02-29 19:29:01

On Sun, Feb 29, 2004 at 06:50:34AM -0600, Larry Evans wrote:
> On 02/28/2004 06:29 PM, Brian McNamara wrote:
> >        Expr tree           TExpr tree
> >           + <----------------- .
> >          / \                  / \
> >         /   \                /   \
> >        x_    y_            int   int
> >        |\    |\_____________/_____/
> >          \_________________/
> >
> > where the tree on the right contains only the "added data" as well as
> > pointers to the corresponding nodes of the original tree.
> 
> YES!  This is exactly what I want, expressed "most directly" AFAICT,
...
> However, this implementation has a disadvantage.  For example, The
> tree -> first isomorphism, implemented by the regexp_first_constructor
> :: new_from_nilable, would have to create, for the regexp_tree_alt ->
> regexp_first_alt mapping a list<regexp_first_top*> as superclass of
> regexp_first_alt corresponding to the list<regexp_tree_top*>
> superclass of regexp_tree_alt.  This duplicates the list
> overhead. OTOH, the way it's currently coded may be represented as:
> 
>          Expr tree           TExpr tree
>             + <----------------> .
>            / \
>           /   \
>          x_    y_             _int  _int
>          |\    |\             /|    /|
>            \     \___________/     /
>             \_____________________/
> 
> where <---> represents two pointers, one the inverse of the other.  At
> first, it looks like the number of pointers added by the isomorphism
> in the 2nd diagram exceeds that of the 1st (6 vs.5); however, the list
> overhead, I think, would tip the balance in the other direction at the
> cost, of course, of less speed for accessing the TExpr children.  It's
> a trade-off, which I'll have to think on some more.

I thought about that too.  Here's an idea to consider; encode it like
this:
          Expr tree           TExpr tree
           +,0,2                  .
             |                    | 
             |                    |  
          x  |  y             int | int
         /   |   \            /   |   \
         |   |   |            |   |   |
       --|---|---|--        --|---|---|--
       | ^ | ^ | ^ |        | ^ | ^ | ^ |
       -------------        -------------
       ExprTreeArray        TExprTreeArray

Ok, that representation isn't quite right, but hopefully you get the
idea.  Since the "structures" are the same, create arrays with pointers
to each of the nodes, so that eta[n] and teta[n] are the corresponding
nodes in the structure.  Then you only need to store the graph
structure in the original graph (using indices rather than pointers).
In order for the root of the TExpr tree to discover its children, it
just asks the root of the Expr tree for its child indices (0 and 2 in
the example), and then it grabs the corresponding nodes in the TExpr
array rather than the Expr array.

The representation I have above doesn't quite work (there's no easy way
to the TExpr root to "find" the Expr root), but I am pretty sure a
small variation of it will work.  By encoding the structure as array
indices instead of pointers, the structure for the various layers gets
stored implicitly, and so in the end I think this will be a win for a
size optimization.

-- 
-Brian McNamara (lorgon_at_[hidden])