Geek Answers Handbook

XSLT 1.0 Greedy backpack grouping techniques?

I have an XML dataset (provided by SharePoint 2007 for DVWP), structured something like this:

<Rows>
  <Row ID="1" Spanoffset="0" Span="55" Spantail="55"/>
  <Row ID="2" Spanoffset="30" Span="31" Spantail="61"/>
  <Row ID="3" Spanoffset="61" Span="20" Spantail="81"/>
  <Row ID="4" Spanoffset="82" Span="30" Spantail="112"/>
</Rows>

Say what each line represents a line starting @Spanoffsetand width @Span, @Spantailso I do not need to calculate it if I need it. I am trying to put packages together efficiently so that lines that do not match are grouped together. The dataset is pre-sorted using @Spanoffset. This is essentially a backpack problem, as each line can be in several possible groups. What I want to do is a simple greedy decision, and I know how I could encode it, say, C # or java, but since I cannot mark the nodes as visited (I can, but I lose them when I return to the recursion tree) and I can’t delete the remote nodes while I visit them, I don’t understand how to do this.

For example, the above data looks something like this:

<div style="clear:both">
  <div style="width: 110px; margin-left: 0px; float:left;">1</div>
  <div style="width: 40px; margin-left: 12px; float:left;">3</div>
  <div style="width: 60px; margin-left: 2px; float:left;">4</div>
</div>
<div style="clear:both">
  <div style="width: 62px; margin-left: 60px; float:left;">2</div>
</div>

, , , Row , . , , .

XSLT, , :

<xsl:template match="row">
  <xsl:variable name="tail" select="@Spantail"/>
  <div style="width:{2*@Span}px;
    left:{2*(@Spanoffset)}px;">
    <xsl:value-of select="@ID"/>
  </div>                        
  <xsl:apply-templates select="(following-sibling::row)[@Spanoffset>=$tail][1]"/>
</xsl:template>


<div style="width: 110px;left: 0px">1</div>
<div style="width: 40px; left: 122px">3</div>
<div style="width: 60px; left: 164px">4</div>
<div style="width: 62px; left: 60px">2</div>
<div style="width: 40px; left: 122px">3</div>
<div style="width: 60px; left: 164px">4</div>
<div style="width: 40px; left: 122px">3</div>
<div style="width: 60px; left: 164px">4</div>
<div style="width: 60px; left: 164px">4</div>

, 2 ( ), , . 1) / (), . 2) <div>.

2 , ?

: , , CDATA, <div>, . - true, , false, , . <Row> , .

+4
1

, XSLT, node -set(), XSLT:

<xsl:template name="add-row">
    <xsl:param name="row"/>
    <xsl:param name="prev-group" />
    <xsl:if test="$row and not($row/@ID = $prev-group/Row/@ID)">
        <xsl:copy-of select="$row" />
        <xsl:call-template name="add-row">
            <xsl:with-param name="row" select="$row/following-sibling::Row[@Spanoffset &gt; $row/@Spantail][1]" />
            <xsl:with-param name="prev-group" select="$prev-group" />
        </xsl:call-template>
    </xsl:if>   
</xsl:template>

<xsl:template name="add-group">
    <xsl:param name="first-row" />
    <xsl:param name="prev-group" select="exsl:node-set(/)" />
    <xsl:if test="$first-row">
        <xsl:variable name="group">
            <xsl:call-template name="add-row">
                <xsl:with-param name="row" select="$first-row" />
                <xsl:with-param name="prev-group" select="$prev-group" />
            </xsl:call-template>
        </xsl:variable>
        <div clear="both">
            <xsl:for-each select="exsl:node-set($group)/Row">
                <div style="width: {2*@Span}px; left: {2*@Spanoffset}px"><xsl:value-of select="@ID"/></div>                             
            </xsl:for-each>
        </div>
        <xsl:call-template name="add-group">
            <xsl:with-param name="first-row" select="$first-row/following-sibling::Row[@Spanoffset &lt; preceding-sibling::Row/@Spantail][1]" />
            <xsl:with-param name="prev-group" select="exsl:node-set($group)" />
        </xsl:call-template>
    </xsl:if>
</xsl:template>

<xsl:template match="Rows">
    <xsl:call-template name="add-group">
        <xsl:with-param name="first-row" select="Row[1]" />
    </xsl:call-template>
</xsl:template>

:

<xsl:stylesheet
  version="1.0"
  xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
  extension-element-prefixes="exsl"
  xmlns:exsl="http://exslt.org/common">

http://exslt.org/common - Java XSLT, Xalan Saxon; MSXML, urn: schemas-microsoft-com: xslt .

+1

More articles:


All Articles