XSLT 1.0 Greedy knapsack grouping methods?

Question

I have an XML dataset (provided from SharePoint 2007 to a DVWP) structured something like:

<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 each row represents a bar that starts at @Spanoffset and is @Span wide, @Spantail is there so I don't have to calculate it if I need it. I am trying to pack the rows together efficently so that rows that wont overlap get grouped together. The dataset is pre-sorted by @Spanoffset. This is essentially a knapsack problem as each Row could fit in multiple possible groups. What I want to do is a simple greedy solution, and know how I could code it in say c# or java, but since I cannot mark nodes as visited (well I can, but I lose it when I come back up the recursion tree) and I cannot seem to remove nodes as I visit them, I am at a loss for how to approach this.

For example the above data would look 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>

I haven't been bothering trying to get the floats to work right as I have yet to be able to get the Row nodes to appear only one time each, in the right order. Once I get them there I am fairly certain I can get the formatting to work out.

The best XSLT I have come up with so far has been:

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

Which generates

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

So my problems are 2 (that I see) and I think they are intertwined. 1) How to fix/re-factor my template(s) to only emit each row once. and 2) How to wrap the groupings in container <div> elements.

Been banging my head against this for 2 days, any one able to help?

Edit: Well, after some sleep, I have the wrapping container by adding a boolean parameter to my template, and using some CDATA tags to emit <div> tags when its true. The boolean defaults to true, and when I call the nested apply-templates I set it to false, hence wrapping up the groups in containers. I still cant see a way of marking <Row>s as visited yet.

Answer 1

I think it's very tricky with just core XSLT, but it's easier with node-set(), a XSLT extension function:

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

Don't forget to declare extension prefix and namespace in your stylesheet tag:

<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 is a valid namespace for Java XSLT processors, such as Xalan or Saxon; if you're using MSXML, use urn:schemas-microsoft-com:xslt instead.