search for maximum hierarchy

Discussion in 'XML' started by KemperR, Sep 9, 2004.

  1. KemperR

    KemperR Guest

    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>
     
    KemperR, Sep 9, 2004
    #1
    1. Advertising

  2. (KemperR) writes:
    > 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">
    <xsl:param name="data"/>
    <xsl:param 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>
    <xsl:eek:therwise>
    <xsl:value-of select="$max"/>
    </xsl:eek:therwise>
    </xsl:choose>
    </xsl:with-param>
    </xsl:call-template>
    </xsl:when>
    <xsl:eek:therwise>
    <xsl:value-of select="$max"/>
    </xsl:eek:therwise>
    </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
    Mail to the address above is discarded.
    Mail to ben at that address might be read.
    http://www.edginet.org/
     
    Ben Edgington, Sep 9, 2004
    #2
    1. Advertising

  3. Ben Edgington <> writes:

    > (KemperR) writes:
    > > 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.


    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">
    <xsl:param name="data"/>
    <xsl:param 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>
    <xsl:eek:therwise>
    <xsl:value-of select="$max"/>
    </xsl:eek:therwise>
    </xsl:choose>
    </xsl:with-param>
    </xsl:call-template>
    </xsl:when>
    <xsl:eek:therwise>
    <xsl:value-of select="$max+1"/>
    </xsl:eek:therwise>
    </xsl:choose>

    </xsl:template>

    </xsl:stylesheet>

    --
    Ben Edgington
    Mail to the address above is discarded.
    Mail to ben at that address might be read.
    http://www.edginet.org/
     
    Ben Edgington, Sep 9, 2004
    #3
  4. Ben Edgington wrote:

    > 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
     
    =?ISO-8859-1?Q?J=FCrgen_Kahrs?=, Sep 9, 2004
    #4
  5. KemperR

    Marrow Guest

    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">
    <xsl:eek:utput 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">
    <xsl:eek:utput 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">
    <xsl:param 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>
    <xsl:eek:therwise>
    <xsl:value-of select="$new-max"/>
    </xsl:eek:therwise>
    </xsl:choose>
    </xsl:template>
    </xsl:stylesheet>


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


    "KemperR" <> wrote in message
    news:...
    > 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>
     
    Marrow, Sep 9, 2004
    #5
  6. KemperR

    Rolf Kemper Guest

    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

    Ben Edgington <> wrote in message news:<>...
    > Ben Edgington <> writes:
    >
    > > (KemperR) writes:
    > > > 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.

    >
    > 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">
    > <xsl:param name="data"/>
    > <xsl:param 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>
    > <xsl:eek:therwise>
    > <xsl:value-of select="$max"/>
    > </xsl:eek:therwise>
    > </xsl:choose>
    > </xsl:with-param>
    > </xsl:call-template>
    > </xsl:when>
    > <xsl:eek:therwise>
    > <xsl:value-of select="$max+1"/>
    > </xsl:eek:therwise>
    > </xsl:choose>
    >
    > </xsl:template>
    >
    > </xsl:stylesheet>
     
    Rolf Kemper, Sep 9, 2004
    #6
  7. Rolf Kemper wrote:

    > 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.
     
    =?ISO-8859-1?Q?J=FCrgen_Kahrs?=, Sep 9, 2004
    #7
  8. KemperR

    William Park Guest

    KemperR <> wrote:
    > 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

    --
    William Park <>
    Open Geometry Consulting, Toronto, Canada
     
    William Park, Sep 9, 2004
    #8
  9. 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
     
    David Carlisle, Sep 9, 2004
    #9
  10. William Park wrote:

    > 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.
     
    =?ISO-8859-1?Q?J=FCrgen_Kahrs?=, Sep 9, 2004
    #10
  11. KemperR

    William Park Guest

    J?rgen Kahrs <> wrote:
    > William Park wrote:
    >
    > > 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 '|').

    >
    > > - `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.


    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.

    --
    William Park <>
    Open Geometry Consulting, Toronto, Canada
     
    William Park, Sep 9, 2004
    #11
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Alan Pretre

    Re: hierarchy chart

    Alan Pretre, Jul 25, 2003, in forum: ASP .Net
    Replies:
    0
    Views:
    1,293
    Alan Pretre
    Jul 25, 2003
  2. Alan
    Replies:
    0
    Views:
    536
  3. Karl Heinz Buchegger

    Re: How to search a hierarchy of objects?

    Karl Heinz Buchegger, Aug 6, 2003, in forum: C++
    Replies:
    7
    Views:
    351
    Karl Heinz Buchegger
    Aug 7, 2003
  4. Abby Lee
    Replies:
    5
    Views:
    475
    Abby Lee
    Aug 2, 2004
  5. phanhuyich
    Replies:
    4
    Views:
    330
Loading...

Share This Page