[xsl] Re: Re: Re: how to optimize recursive algorithm?

Subject: [xsl] Re: Re: Re: how to optimize recursive algorithm?
From: "Dimitre Novatchev" <dnovatchev@xxxxxxxxx>
Date: Sat, 29 Nov 2003 19:37:49 +0100
OK, I understand the problem. Here is how to calculate the maximum display
size.

The transformation below does this in steps:

 1. Build a table of all unique names (using the Muenchian method for
grouping) and their respective display size.

 2. Create a new document from the current document. The structure and names
are the same but a new attribute has been added to every element and the
value of this attribute is the display size of the element.

 3. The FXSL "maximum" template is called to return one of the nodes with
maximum display size.


Step 1. above also uses the FXSL template "transform-and-sum" to represent
each element in the sum with the display size of its name.


So this transformation:

<xsl:stylesheet version="1.0"
 xmlns:xsl="http://www.w3.org/1999/XSL/Transform";
 xmlns:ext="http://exslt.org/common";
 xmlns:myComp="my:comp"
 xmlns:myNamesize="my:NameSize"
 exclude-result-prefixes="ext myComp myNamesize"
 >
  <xsl:import href="maximum.xsl"/>
  <xsl:import href="transform-and-sum.xsl"/>

  <xsl:output omit-xml-declaration="yes"/>

  <xsl:param name="pFontSize" select="8"/>
  <xsl:param name="pDelta" select="5 * $pFontSize"/>

  <xsl:key name="kNames" match="*" use="name()"/>

  <xsl:variable name="vrtfNameTable">
    <xsl:for-each
     select="//*[generate-id() = generate-id(key('kNames', name())[1])]">

      <name><xsl:value-of select="name()"/></name>
      <size>
        <xsl:value-of select="string-length(name())*$pFontSize*1.33333
                            + $pDelta"/>
      </size>
    </xsl:for-each>
  </xsl:variable>

  <xsl:variable name="vNameTable" select="ext:node-set($vrtfNameTable)"/>

  <xsl:variable name="vrtfNewDoc">
    <xsl:apply-templates select="/*" mode="calcSize"/>
  </xsl:variable>

  <xsl:variable name="vNewDoc" select="ext:node-set($vrtfNewDoc)"/>


  <xsl:variable name="vMyCopmare" select="document('')/*/myComp:*[1]"/>
  <xsl:variable name="vNameSize" select="document('')/*/myNamesize:*[1]"/>

  <xsl:template match="/">
    <xsl:call-template name="maximum">
      <xsl:with-param name="pList" select="$vNewDoc//*[not(*)]"/>
      <xsl:with-param name="pCMPFun" select="$vMyCopmare"/>
    </xsl:call-template>
  </xsl:template>

  <xsl:template match="*" mode="calcSize">
    <xsl:param name="currSize" select="0"/>
    <xsl:copy>
      <xsl:copy-of select="@*"/>
      <xsl:attribute name="__dispSize">
        <xsl:call-template name="transform-and-sum">
          <xsl:with-param name="pFuncTransform" select="$vNameSize"/>
          <xsl:with-param name="pList" select="ancestor-or-self::*"/>
        </xsl:call-template>
      </xsl:attribute>
      <xsl:apply-templates mode="calcSize"/>
    </xsl:copy>
  </xsl:template>

  <myComp:myComp/>
  <xsl:template match="myComp:*">
    <xsl:param name="arg1" select="/.."/>
    <xsl:param name="arg2" select="/.."/>

    <xsl:value-of select="0 + ($arg1/@__dispSize > $arg2/@__dispSize)"/>
  </xsl:template>

  <myNamesize:myNamesize/>
  <xsl:template match="myNamesize:*">
    <xsl:param name="arg"/>

    <xsl:value-of select="$vNameTable/name[. =
name($arg)]/following-sibling::*[1]"/>

  </xsl:template>
</xsl:stylesheet>

when applied on your source.xml:

<t>
  <ab/>
  <longname>
    <xyz/>
    <tuop/>
  </longname>
  <last/>
</t>

produces the wanted result:

<tuop __dispSize="258.66632" />


=====
Cheers,

Dimitre Novatchev.
http://fxsl.sourceforge.net/ -- the home of FXSL



"FC" <flavio@xxxxxx> wrote in message
news:000701c3b681$c92271a0$6501a8c0@xxxxxxxxx
>
> Comments interspersed with text.
>
>
> ----- Original Message -----
> From: "Dimitre Novatchev" <dnovatchev@xxxxxxxxx>
> To: <xsl-list@xxxxxxxxxxxxxxxxxxxxxx>
> Sent: Saturday, November 29, 2003 09:24
> Subject: [xsl] Re: Re: how to optimize recursive algorithm?
>
>
> > > 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
> >
> > Here you are talking about "the maximum of the sum of the length of all
> > elements" ... ?
> >
> > What is a "length of an element" ?
> >
>
> Since I was describing a graphical output I overlooked the specification
of
> pixels as length unit. I am sorry for that.
> The length of an element is the element's name rendered in a certain font,
> which is corresponding to the width of the "bounding box" surrounding the
> text.
> I need to know in advance the horizontal dimension of this bounding box,
> because I want to add certain graphical elements basing on its width.
> The length, or the width if you prefer, of the text element therefore is
its
> length in pixels. To cut a long story short, say the length of an element
to
> be proportional to its character length, according roughly to a formula
like
> this:
>
> length(name) *  fontsize * 3 / 4
>
> In reality the formula is more complex because of kerning and spacing
> values, but let's ignore them in this exercise, because it is also
> reasonable to use fixed width fonts which avoid such annoying
complication.
>
>
> > "the maximum of the sum of the length of all elements" should be just
"the
> > sum of the length of all elements" -- a sum is just a single number, it
is
> > not meningful to try to find the maximum of a single number.
> >
>
> I must retrieve the maximum value because I need to align the vertical
lines
> to the rightmost position, as I tried to represent in the picture.
> The vertical pipes theoretically should be aligned with each other. Their
> position corresponds to the position of the widest branch plus a certain
> delta value.
> In order to retrieve this value, I need to know where is located the
element
> having the maximum x coordinate.
> The x coordinate depends not only on the length of the element itself, but
> also on the length of its ancestors, and this is why it is a sum (when
there
> are more elements sitting on a branch) and not a single number (unless
there
> is just one element).
> It is perfectly possible to have a situation where a single element with a
> very long name takes more space than two short elements, so I cannot make
> any assumption basing on the depth of an element to decide which one is
the
> most displaced to the right.
> The maximum value is the result of adding up the length of one or more
> elements belonging to the same axis (I called it branch), inside a certain
> boundary, in the example I gave, the boundary is represented by the node
> called <all>. The elements inside an <all> group must be drawn on top of
> each other and since they can be repeated, I want to draw a straight
> connector on the right hand side of the element joining a vertical line
that
> will convey the concept of repeatability of the elements (as in the poor
> picture I provided).
>
> The position of this vertical line, but also the rightmost x position of
the
> connector line drawn starting from the rightmost element sitting on a
> branch, depends on the maximum x value within the <all> group.
> So, unless I am able to calculate the value beforehand, it will be
> (re)calculated for each element(s) belonging to the <all> group, wasting a
> lot of time.
>
> So, describing the situation occurring in the given example, I must find
the
> largest value (the maximum) among:
>
> width-in-pixels("ab") + deltaX
> width-in-pixels("longname") + deltaX + width-in-pixels("xyz") + deltaX
> width-in-pixels("longname") + deltaX + width-in-pixels("tuop") + deltaX
> width-in-pixels("last") + deltaX
>
> where deltaX is a fixed value of padding space.
>
>
> > > 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:
> >
> > Now you are just looking for the maximum of several numbers, not the
> maximum
> > of their sum.
> >
> > > the length of "ab"
> > > the length of "longname" plus "xyz"
> > > the length of  "longname" plus "tuop".
> > > the length of "last".
> > >
> >
> > Summary:
> >    It is not clear what you want to achieve. However, I guess the
> following
> > link will be useful:
> >
> > http://skew.org/xml/stylesheets/treeview/ascii/
>
>
> What I want to achieve is similar, although in graphical format, using
SVG,
> and much more complex, the practical purpose is rather different also.
> You can see a sample of output of this transformation at the following
> address:
>
> http://www.yocoya.com/samples/embed_alter_database.html
>
> An SVG plugin is required to display the internal frame.
>
> This page gives you an idea of the graphical output obtained by applying
the
> transformation, although it doesn't constitute an example of the problem
> discussed here because there are no repeating groups of elements.
>
> >
> > Also, in case you need to find the element with the maximum depth, this
> > question has been asked before and has a nice and efficient solution
(e.g.
> > using FXSL) -- see
> > http://sources.redhat.com/ml/xsl-list/2002-05/msg00611.html
> >
>
> It looks similar to the the "function" I am already using, good!
>
>
> > Pardon me in case my guesses are wrong.
> >
> >
> >
> > =====
> > Cheers,
> >
> > Dimitre Novatchev.
> > http://fxsl.sourceforge.net/ -- the home of FXSL
> >
>
>
> Thanks for your help anyway,
>
> Flavio
>
>
>
>  XSL-List info and archive:  http://www.mulberrytech.com/xsl/xsl-list
>
>




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


Current Thread