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@cc.gatech.edu)