This is the mail archive of the xsl-list@mulberrytech.com mailing list .


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: Re: The Solution -- Re: how to rearrange nodes based on a dependency graph?


As beautifully as this is designed, the only sad thing is that
it can't work without using some Microsoft (or other) extension.
Apparently the node-set function is available in many xslt
processors, but then why is it not part of the specification?

It is my reading, correctme if I'm wrong, that the only reason
why this node-set function needs to exist in the first place is
because the result tree fragment has some ugly restriction. The
XSLT spec mumbles about it being only accessible through string
functions etc. The node-set apparently turns that result tree
fragment into real XPath-inspectable trees.

Furthermore, the only place where this is really needed is for
the concatenation of the node sets from pSorted and vNextLevel.
That should have been easily possible in basic XPath. I tried
rewriting:

       <xsl:variable name="vrtfNewSorted">
         <xsl:copy-of select="$pSorted"/>
         <xsl:copy-of select="$vNextLevel"/>
       </xsl:variable>

to this:

       <xsl:variable name="XvrtfNewSorted"
                     select="$pSorted|$vNextLevel"/>

but apparently this orders things in the document order, not
in the order specified. It's weird that the XPath spec talks
about node sets when in reality they are ordered. And all of
this only to prevent the user from rearranging the ordering.

regards
-Gunther


Gunther Schadow wrote:

> Wow, thanks Dimitre, this looks exactly right! And so much more
> elegant than what I have been fiddling with! I had been close
> to banging my "nodes-seen" list into XSL but your solution is
> so much better!
> 
> Thanks,
> -Gunther
> 
> Dimitre Novatchev wrote:
> 
>> Hi Gunther,
>>
>> If I'm not wrong, this problem is a case of the "topological sort" 
>> problem.
>>
>> The solution bellow arranges the DAG into levels of hierarchy -- the 
>> nodes that do
>> not depend on other nodes are at the top, the nodes that depend 
>> ***only*** on the
>> nodes in the sorted hierarchy (up to this moment) form the next level 
>> of the
>> hierarchy.
>>
>> Suppose that we have the following source xml document:
>>
>> <document xml:space="preserve">
>>     <frag id='1'>
>>         <requires>2</requires>
>>         <requires>3</requires>
>>     </frag>
>>
>>     <frag id='2'>
>>         <requires>4</requires>
>>         <requires>5</requires>
>>     </frag>
>>
>>     <frag id='3'>
>>         <requires>5</requires>
>>     </frag>
>>
>>     <frag id='4' />
>>
>>     <frag id='5' />
>> </document>
>>
>> The hierarchical representation is:
>>
>>       1
>>      / \
>>     2   3
>>    / \ /
>>   4   5
>>
>>
>> And here's the stylesheet:
>>
>> <xsl:stylesheet version="1.0" 
>> xmlns:xsl="http://www.w3.org/1999/XSL/Transform";
>> xmlns:msxsl="urn:schemas-microsoft-com:xslt">
>>   <xsl:output indent="yes" omit-xml-declaration="yes"/>
>>   <xsl:template match="/">
>>     <xsl:call-template name="topSort">
>>       <xsl:with-param name="pSorted" select="/*/frag[not(requires)]"/>
>>       <xsl:with-param name="pUnsorted" select="/*/frag[requires]"/>
>>     </xsl:call-template>
>>   </xsl:template>
>>     <xsl:template name="topSort">
>>     <xsl:param name="pSorted" select="/.."/>
>>     <xsl:param name="pUnsorted" select="/.."/>
>>
>>     <xsl:variable name="vNextLevel"
>>                   select="$pUnsorted[not(requires[not(. = 
>> $pSorted/@id)])]"/>
>>     <xsl:choose>
>>       <xsl:when test="not($vNextLevel)">
>>         <xsl:copy-of select="$pSorted"/>
>>       </xsl:when>
>>       <xsl:otherwise>
>>         <xsl:variable name="vrtfNewSorted">
>>           <xsl:copy-of select="$pSorted"/>
>>           <xsl:copy-of select="$vNextLevel"/>
>>         </xsl:variable>
>>
>>         <xsl:variable name="vCntNextLevel" select="count($vNextLevel)"/>
>>         <xsl:variable name="vNewUnsorted"
>>                       select="$pUnsorted[not(@id = $vNextLevel/@id)] "/>
>>         <xsl:call-template name="topSort">
>>           <xsl:with-param name="pSorted" 
>> select="msxsl:node-set($vrtfNewSorted)/*"/>
>>           <xsl:with-param name="pUnsorted" select="$vNewUnsorted"/>
>>         </xsl:call-template>
>>
>>       </xsl:otherwise>
>>     </xsl:choose>
>>   </xsl:template>
>> </xsl:stylesheet>
>>
>> When applied on the above xml source document, the result of the 
>> transformation is:
>>
>> <frag id="4" />
>> <frag id="5" />
>> <frag id="2">
>>         <requires>4</requires>
>>         <requires>5</requires>
>> </frag>
>> <frag id="3">
>>         <requires>5</requires>
>> </frag>
>> <frag id="1">
>>         <requires>2</requires>
>>         <requires>3</requires>
>> </frag>
>>
>>
>> The tricky part is to express in a single XPath expression the nodes 
>> that will form
>> the next level:
>>
>> <xsl:variable name="vNextLevel"
>>               select="$pUnsorted[not(requires[not(. = $pSorted/@id)])]"/>
>>
>> This is: all elements from $pUnsorted, which do not have any 
>> "requires" child that
>> is not equal to the "id" of one of the elements in the sorted 
>> hierarchy $pSorted.
>>
>> Hope that this really helped.
>>
>> Cheers,
>> Dimitre Novatchev.
>>
>>
>>
>> Gunther Schadow <gunther at aurora dot regenstrief dot org> wrote:
>> -------------------------------------------------------------------------------- 
>>
>>
>> Hi XSL listers,
>>
>> I'm hung up on a puzzling problem and need your help. I am
>> relatively new to XSL but thanks to the pretty readable
>> specification and some example I was so far able to find
>> my way. Except when I wanted to be really clever, like here.
>>
>> The purpose of what I'm doing is kind of what you might
>> know as "literal programming." It's writing a document
>> that explains the detail of some formal language utterance,
>> such as a program, or an XML schema or an IDL specification
>> or whatever have you. The document is to be written for
>> readability and may well have a different flow than what's
>> required for the formal language (program or xsd or whatever.)
>> For example, in describing a Pascal program, I might want to
>> discuss an outline of the main program first before I go
>> into the detail of the procedures. Yet in the program text,
>> the procedures need to come before the main program. The
>> point of course is that the text document should be the main
>> focus of development and maintenance, and the program text
>> should be generated from there. That's where XSLT comes
>> in and falls short? (you tell me if it does of if I fall
>> short :-)
>>
>> Here is an example. This XML instance discusses a mocked up
>> up XML schema for defining some data.
>>
>>
>> <document>
>>
>> Blah bla
>>
>> <frag id='1' requires='2'>
>>     BEGIN
>>       DoSomethingUseful();
>>     END
>> </frag>
>>
>> Blah blah
>>
>> <frag id='2'>
>>    PROCEDURE DoSomethingUseful
>>    BEGIN
>>      ...
>>    END
>> </frag>
>>
>> </document>
>>
>>
>>
>>
>> The <frag> tag has an 'id' (ID) attribute with matching
>> 'requires' (IDREFS) attribute.
>>
>> The XSL templates will go through the document and discard
>> everything, except when encountering a fragment. It will
>> then will hunt down the requires idrefs to find other
>> fragments that should come first. Of course, if a fragment has
>> already been emitted, it shouldn't appear again. And that't
>> really my big problem.
>>
>> Here is my XSL so far:
>>
>> <xsl:key name='fragkey' match='frag' use='@id' />
>>
>> <xsl:template match='frag'>
>>    <xsl:for-each select='@requires'>
>>      <xsl:apply-templates select="key('fragkey',.)"/>
>>    </xsl:for-each>
>>
>>    <xsl:for-each select='*'>
>>      <xsl:call-template name='copy-stuff'/>
>>    </xsl:for-each>
>> </xsl:template>
>>
>> <xsl:template name='copy-stuff'>
>>    <xsl:copy>
>>      <xsl:for-each select='@*|*'>
>>        <xsl:call-template name='copy-stuff'/>
>>      </xsl:for-each>
>>    </xsl:copy>
>> </xsl:template>
>>
>>
>>
>> This works nicely, except for the fact that fragment number 2
>> is emitted twice, first as the dependency of fragment 1 and
>> then because it appears as the next fragment in the document.
>> (Similarly this runs amok if there's a circular dependency.)
>>
>> I tried to use a variable as a check-off list of fragments
>> already emitted, but that's not possible because XSL "variables"
>> are actually constants. When I try to write such a function
>> in LISP without using global variables and side effects, it
>> get's pretty difficult and the only way to survive here is
>> because I can examine return values. In XSL, I cannot examine
>> the output tree, or can I?
>>
>> Any suggestions are appreciated. Of course I can dumb down
>> this system and instead of requirement links I could use
>> some kind of sequence number or forward linking and sort by
>> that etc. But I feel that the dependency graph is the most
>> appropriate way to represent this and if XSL is a complete
>> functional language it should have some way to deal with that.
>>
>> regards,
>> -Gunther
>>
>>
>>
>>
>> __________________________________________________
>> Do You Yahoo!?
>> Check out Yahoo! Shopping and Yahoo! Auctions for all of
>> your unique holiday gifts! Buy at http://shopping.yahoo.com
>> or bid at http://auctions.yahoo.com
>>
> 
> 


-- 
Gunther Schadow, M.D., Ph.D.                    gschadow@regenstrief.org
Medical Information Scientist      Regenstrief Institute for Health Care
Adjunct Assistant Professor        Indiana University School of Medicine
tel:1(317)630-7960                         http://aurora.regenstrief.org



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


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]