xsl-list
[Top] [All Lists]

Re: Re: how to optimize recursive algorithm?

2003-11-28 15:16:31

Ok,
let's take a document like this (the real file is an XML schema file, I am
just simplifying a little bit the structure):

<element name='root'>
    <all>
        <element name='ab'/>
        <element name='longname'>
            <choice>
                <element name='xyz'/>
                <element name='tuop'/>
            </choice>
        </element>
        <element name='last'/>
    </all>
</element>

I want to represent this document graphically (in SVG) as a tree structure
like this:

root
 |-------------<------------------|
 |--- ab-------->-----------------|
 |--- longname -->----- xyz-->---|
 |                             |--- tuop-->--|
 |--- last -------->----------------|


The problem I submitted refers to the calculation of the width of the branch
on the right hand side of each element's name (plus the first branch
represented as a path going backwards) that should be aligned to the
rightmost position for all elements.
Its total length is the maximum of the sum of the length of all elements
residing on each "branch" plus a certain fixed amount to leave some room
between the elements.

In this case it would be the maximum between:
the length of "ab"
the length of "longname" plus "xyz"
the length of  "longname" plus "tuop".
the length of "last".

My current transformation is written using "push process" style.
Which means that when calculating the length of the right branch for a given
element, it will call a template calculating the maximum length of all
preceding siblings (plus their descendants) and all following siblings (and
their descendants). This results in calculating the value of "ab" n-1 times,
"longname" + "xyz" n-1 times, and so on.

My question is how to avoid the calculation of each element's length more
than once, possibly using pure XSLT 1.0.

At the time of writing an idea popped up in my mind, probably as a
consequence of what Micheal Kay suggested.
Perhaps I could add a template for the elements like <all> and <choice>,
that I am now using only within test clauses to recognize certain patterns,
where I can detect the need of such calculation at an early stage and carry
it out beforehand, passing the results as parameters to the other templates.

Any other ideas?

Thanks and bye,
Flavio


 XSL-List info and archive:  http://www.mulberrytech.com/xsl/xsl-list