catap's blog ~ записки ёmacs'ера

В процессе работы попалась интересная (сложная) задачка на xslt:

Есть xml:

<root>
  <values>
    <value g="a" title="t1" /> 
    <value g="b" title="t2" /> 
    <value g="b" title="t3" /> 
    <value g="a" title="t4" /> 
    <value title="t5" /> 
    <value title="t6" /> 
    <value g="b" title="t7" />
  </values>
</root>

Требуется из него получить:

<root>
  <items>
    <group name="a">
      <value>t1</value>
      <value>t4</value>
    </group>
    <group name="b">
      <value>t2</value>
      <value>t3</value>
      <value>t7</value>
    </group>
    <value>t5</value>
    <value>t6</value>
  </items>
</root>

Ниже решение, которое нашел я. Если хотите — смотрите сразу, но интереснее подумать. У меня это заняло около полу часа, а у вас?

<xsl:stylesheet version="1.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
  <xsl:key name="grp" match="value" use="concat(generate-id(parent::*), '-', @g)"/>
  <xsl:template match="values">
    <root>
      <items>
        <xsl:apply-templates select="value[generate-id(.)=generate-id(key('grp',concat(generate-id(parent::*), '-', @g))[1])]"/>
        <xsl:for-each select="value[not(@g)]">
          <xsl:apply-templates select="."/>
        </xsl:for-each>
      </items>
    </root>
  </xsl:template>

  <xsl:template match="value">
    <xsl:choose>
      <xsl:when test="@g != ''">
        <group name="{@g}">
          <xsl:for-each select="key('grp',concat(generate-id(parent::*), '-', @g))">
            <value>
              <xsl:value-of select="@title"/>
            </value>
          </xsl:for-each>
        </group>
      </xsl:when>
      <xsl:otherwise>
    <value>
      <xsl:value-of select="@title"/>
    </value>      
      </xsl:otherwise>
    </xsl:choose>
  </xsl:template>
</xsl:stylesheet>

сложность этого кода O(2*n), есть еще вариант (более очевидный) со сложностью O(n*n). Если кому-то известен метод быстрее чем O(2*n), то я буду признателен, если вы его сообщите мне ;)

p.s. — как выяснилось, я «заново открыл» группировку Мюнха ☹ В преть буду использовать гугл до головы… Ну или после, что бы знать что я хоть придумал ☺