search for maximum hierarchy

[KemperR]

Dear All,

may be some of you can help me with an XSLT example how to solve the
following challange.
For the XML below I want to find out the maximum hierarchy level for a
specific element in my XSLT. The result for the example (searching for
<A/>) should be 4 as the element A is nested 4 times maximum.
I guess I have to use somehow the count function with 'following::A'
axes. But I could not get that to work yet.

Thanks a lot for your help
Rolf

<ROOT>
<A>
<A>
<B>
<C>
<A/> nested up to 3
</C>
</B>
</A>
<A>
<B>
<C>
<A>
<A/> nested up to 4
</A>
<C>
</B>
</A>
</A>
</ROOT>

 

[Ben Edgington]

may be some of you can help me with an XSLT example how to solve the
following challange.
For the XML below I want to find out the maximum hierarchy level for a
specific element in my XSLT. The result for the example (searching for
<A/>) should be 4 as the element A is nested 4 times maximum.
I guess I have to use somehow the count function with 'following::A'
axes. But I could not get that to work yet.

Hmmm. I found this surprisingly tricky to do. The solution looks
complex, but the bulk of it is just a recursive template for finding
the maximum of a list of numbers.

This does the job:

----XML---- (your xml corrected)
<ROOT>
<A>
<A>
<B>
<C>
<A/>
</C>
</B>
</A>
<A>
<B>
<C>
<A>
<A/>
</A>
</C>
</B>
</A>
</A>
</ROOT>

----XSL---
<xsl:stylesheet
version="1.0"
xmlns:xsl="http://www.w3.org/1999/XSL/Transform">

<xsl:template match="/">
<xsl:call-template name="max">
<xsl:with-param name="data">
<!-- We construct a list of local-maximum tree-depths -->
<xsl:for-each select="//*[not(child::*)]">
<xsl:value-of select="count(ancestor::*)"/>
<xsl:text>:</xsl:text>
</xsl:for-each>
</xsl:with-param>
<xsl:with-param name="max" select="0"/>
</xsl:call-template>
</xsl:template>

<xsl:template name="max">
<xslaram name="data"/>
<xslaram name="max"/>
<xsl:choose>
<xsl:when test="$data">
<xsl:variable name="current"
select="number(substring-before($data,':'))"/>
<xsl:call-template name="max">
<xsl:with-param name="data"
select="substring-after($data,':')"/>
<xsl:with-param name="max">
<xsl:choose>
<xsl:when test="$current>$max">
<xsl:value-of select="$current"/>
</xsl:when>
<xsltherwise>
<xsl:value-of select="$max"/>
</xsltherwise>
</xsl:choose>
</xsl:with-param>
</xsl:call-template>
</xsl:when>
<xsltherwise>
<xsl:value-of select="$max"/>
</xsltherwise>
</xsl:choose>

</xsl:template>

</xsl:stylesheet>

----Ouput----
<?xml version="1.0"?>
6


If you want to get "4" (for your definition of nesting) then change
the line
<xsl:value-of select="$max"/>
to
<xsl:value-of select="$max - 2"/>

Ben

 

[Ben Edgington]

Hmmm. I found this surprisingly tricky to do. The solution looks
complex, but the bulk of it is just a recursive template for finding
the maximum of a list of numbers.

Now I've actually read your question here's a slightly amended
stylesheet that does what you want 8^). I've only changed the two
XPath expressions near the top to use 'A' instead of '*', and added
one to the output of $max (so that the current 'A' element is included
in the count).

<xsl:stylesheet version="1.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform">

<xsl:template match="/">

<xsl:call-template name="max">
<xsl:with-param name="data">
<xsl:for-each select="//A[not(child::*)]">
<xsl:value-of select="count(ancestor::A)"/>
<xsl:text>:</xsl:text>
</xsl:for-each>
</xsl:with-param>
<xsl:with-param name="max" select="0"/>
</xsl:call-template>
</xsl:template>

<xsl:template name="max">
<xslaram name="data"/>
<xslaram name="max"/>
<xsl:choose>
<xsl:when test="$data">
<xsl:variable name="current"
select="number(substring-before($data,':'))"/>
<xsl:call-template name="max">
<xsl:with-param name="data"
select="substring-after($data,':')"/>
<xsl:with-param name="max">
<xsl:choose>
<xsl:when test="$current>$max">
<xsl:value-of select="$current"/>
</xsl:when>
<xsltherwise>
<xsl:value-of select="$max"/>
</xsltherwise>
</xsl:choose>
</xsl:with-param>
</xsl:call-template>
</xsl:when>
<xsltherwise>
<xsl:value-of select="$max+1"/>
</xsltherwise>
</xsl:choose>

</xsl:template>

</xsl:stylesheet>

 

[=?ISO-8859-1?Q?J=FCrgen_Kahrs?=]

Hmmm. I found this surprisingly tricky to do. The solution looks
complex, but the bulk of it is just a recursive template for finding
the maximum of a list of numbers.

Yes, this is not as easy as it looks at first sight.
An interesting example because it puts XSL's mechanisms
to the test. Here is a solution in xmlgawk which I
find much more readable than XSL.

# depth.awk
# Reads an XML document from standard input and
# prints a count value to standard output. The
# count value tells us how deep each kind of
# element is nested inside each other, neglecting
# nesting levels of other elements.
# comp.text.xml 2004-09-09
# JK 2004-09-09

BEGIN { XMLMODE=1 }

# For each element, increase the depth and find
# the maximum of the nesting depths for each element.
XMLSTARTELEM {
nest[XMLSTARTELEM] ++
if (nest[XMLSTARTELEM] > maxdepth[XMLSTARTELEM])
maxdepth[XMLSTARTELEM] = nest[XMLSTARTELEM]
}

# When leaving an element, decrease nesting depth.
XMLENDELEM {
nest[XMLENDELEM] --
}

# Print maximum depth for each kind of element.
END {
for (elem in maxdepth)
print elem, ":", maxdepth[elem]
}


This is the result for the XML data given in your
corrected version:

A : 4
B : 1
C : 1
ROOT : 1

 

[Marrow]

Hi,

Using <xsl:for-each> and sorting method of finding a max, something like...

<?xml version="1.0"?>
<xsl:stylesheet version="1.0"
xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
<xslutput method="text"/>
<xsl:template match="/">
<xsl:variable name="max-A">
<xsl:for-each select="//A">
<xsl:sort select="count(.| ancestor::A)" data-type="number"
order="descending"/>
<xsl:if test="position() = 1">
<xsl:value-of select="count(.| ancestor::A)"/>
</xsl:if>
</xsl:for-each>
</xsl:variable>
<xsl:text>Max nesting of &lt;A&gt; is: </xsl:text>
<xsl:value-of select="$max-A"/>
</xsl:template>
</xsl:stylesheet>

Using recursion, something like...

<?xml version="1.0"?>
<xsl:stylesheet version="1.0"
xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
<xslutput method="text"/>

<xsl:template match="/">
<xsl:variable name="max-A">
<xsl:apply-templates select="(//A)[1]"/>
</xsl:variable>
<xsl:text>Max nesting of &lt;A&gt; is: </xsl:text>
<xsl:value-of select="$max-A"/>
</xsl:template>

<xsl:template match="A">
<xslaram name="max" select="0"/>
<xsl:variable name="this-max" select="count(. | ancestor::A)"/>
<xsl:variable name="new-max" select="($max * number($this-max &lt;= $max))
+ ($this-max * number($this-max &gt; $max))"/>
<xsl:choose>
<xsl:when test="following::A | descendant::A">
<xsl:apply-templates select="(following::A | descendant::A)[1]">
<xsl:with-param name="max" select="$new-max"/>
</xsl:apply-templates>
</xsl:when>
<xsltherwise>
<xsl:value-of select="$new-max"/>
</xsltherwise>
</xsl:choose>
</xsl:template>
</xsl:stylesheet>


HTH
Marrow
http://www.marrowsoft.com - home of Xselerator (XSLT IDE and debugger)
http://www.topxml.com/Xselerator

 

[Rolf Kemper]

Dear Ben,

thanks for the code !!

It works fine, but I'm really surprised how complex it is to get this
actually easy information.

Rolf

Hmmm. I found this surprisingly tricky to do. The solution looks
complex, but the bulk of it is just a recursive template for finding
the maximum of a list of numbers.

Now I've actually read your question here's a slightly amended
stylesheet that does what you want 8^). I've only changed the two
XPath expressions near the top to use 'A' instead of '*', and added
one to the output of $max (so that the current 'A' element is included
in the count).

<xsl:stylesheet version="1.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform">

<xsl:template match="/">

<xsl:call-template name="max">
<xsl:with-param name="data">
<xsl:for-each select="//A[not(child::*)]">
<xsl:value-of select="count(ancestor::A)"/>
<xsl:text>:</xsl:text>
</xsl:for-each>
</xsl:with-param>
<xsl:with-param name="max" select="0"/>
</xsl:call-template>
</xsl:template>

<xsl:template name="max">
<xslaram name="data"/>
<xslaram name="max"/>
<xsl:choose>
<xsl:when test="$data">
<xsl:variable name="current"
select="number(substring-before($data,':'))"/>
<xsl:call-template name="max">
<xsl:with-param name="data"
select="substring-after($data,':')"/>
<xsl:with-param name="max">
<xsl:choose>
<xsl:when test="$current>$max">
<xsl:value-of select="$current"/>
</xsl:when>
<xsltherwise>
<xsl:value-of select="$max"/>
</xsltherwise>
</xsl:choose>
</xsl:with-param>
</xsl:call-template>
</xsl:when>
<xsltherwise>
<xsl:value-of select="$max+1"/>
</xsltherwise>
</xsl:choose>

</xsl:template>

</xsl:stylesheet>

 

[=?ISO-8859-1?Q?J=FCrgen_Kahrs?=]

It works fine, but I'm really surprised how complex it is to get this
actually easy information.

The complexity comes mostly from the kind of
tool you choose (XSL). There are tools capable
of solving the problem in a more evident way.
I have posted an easier and more general solution.

If the problem to solve was to open a can of
Coca Cola, and your only tool was a hammer,
you would certainly be prepared to face some mess.

 

[William Park]

Dear All,

may be some of you can help me with an XSLT example how to solve the
following challange.
For the XML below I want to find out the maximum hierarchy level for a
specific element in my XSLT. The result for the example (searching for
<A/>) should be 4 as the element A is nested 4 times maximum.
I guess I have to use somehow the count function with 'following::A'
axes. But I could not get that to work yet.

Thanks a lot for your help
Rolf

<ROOT>
<A>
<A>
<B>
<C>
<A/> nested up to 3
</C>
</B>
</A>
<A>
<B>
<C>
<A>
<A/> nested up to 4
</A>
<C>
</B>
</A>
</A>
</ROOT>

You had XSL and xmlgawk solution. Here is Bash shell solution:

start () { # Usage: start tag att=value ...
count=`echo ${XML_ELEMENT_STACK[*]|/$1} | wc -w`
[[ count -gt $1 ]] && eval $1=`echo $count`
}
xml -s start "<ROOT>...</ROOT>"
declare -p A B C

Explanation:
- ${...|/glob} returns all array element matching 'glob' pattern.
In this case, 'A', 'B', 'C'.
- if count is greater than previous value, set variable 'A', 'B', or
'C' to that value. This is similar to testing for "max".
- `echo $count` is needed to strip leading whitespaces put there by
'wc -w'.

Ref:
http://freshmeat.net/projects/bashdiff/
http://home.eol.ca/~parkw/index.html#xml
help xml

 

[David Carlisle]

A shorter, if not necessarily more efficient version os:


<xsl:stylesheet xmlns:xsl="http://www.w3.org/1999/XSL/Transform" version="1.0">
<xsl:template match="/">
<xsl:for-each select="//A">
<xsl:sort select="-count(ancestor::A)" data-type="number" />
<xsl:if test="position()=1">
<xsl:value-of select="count(ancestor-or-self::A)"/>
</xsl:if>
</xsl:for-each>
</xsl:template>
</xsl:stylesheet>

which gives 4 on the originally posted example.

David

 

[=?ISO-8859-1?Q?J=FCrgen_Kahrs?=]

You had XSL and xmlgawk solution. Here is Bash shell solution:

start () { # Usage: start tag att=value ...
count=`echo ${XML_ELEMENT_STACK[*]|/$1} | wc -w`
[[ count -gt $1 ]] && eval $1=`echo $count`
}
xml -s start "<ROOT>...</ROOT>"
declare -p A B C

Very short indeed. But a bit cryptic.

Explanation:
- ${...|/glob} returns all array element matching 'glob' pattern.
In this case, 'A', 'B', 'C'.

This is a very powerful feature that is missing in xmlgawk.
In xmlgawk an explicite loop is needed.

- `echo $count` is needed to strip leading whitespaces put there by
'wc -w'.

The descendents of the Bourne shell are not really first choice
for arithmetic applications.

 

[William Park]

You had XSL and xmlgawk solution. Here is Bash shell solution:

start () { # Usage: start tag att=value ...
count=`echo ${XML_ELEMENT_STACK[*]|/$1} | wc -w`
[[ count -gt $1 ]] && eval $1=`echo $count`
}
xml -s start "<ROOT>...</ROOT>"
declare -p A B C

Very short indeed. But a bit cryptic.

Explanation:
- ${...|/glob} returns all array element matching 'glob' pattern.
In this case, 'A', 'B', 'C'.

This is a very powerful feature that is missing in xmlgawk.
In xmlgawk an explicite loop is needed.

This is only available in my patch Bash shell. Standard Bash/Ksh/Zsh
doesn't have it. In Python, it's called list comprehension. But, in
shell-speak, it's nothing more than parameter expansion (around for 30
years) plus some content filtering (denoted by '|').

The descendents of the Bourne shell are not really first choice
for arithmetic applications.

Actually, integer expression is fairly complete. For example,
${var}
${var:i:j}
(( i ))
both 'i' and 'j' can be full arithmetic expression. It's the float
point which is the problem. Bash can't do floating point. Awk is much
better at that.