Есть исходный плоский список:

<list>
  <c>
    <n>c1</n>
    <id>1</id>
  </c>
  <c>
    <n>c2</n>
    <id>1/0/0</id>
  </c>
  <c>
    <n>c3</n>
    <id>1/0</id>
  </c>
  <c>
    <n>c4</n>
    <id>1.2.3.4</id>
  </c>
  <c>
    <n>c5</n>
    <id>1.2.3.4.5.6.8.9</id>
  </c>
  <c>
    <n>c5</n>
    <id>1.2.3.4.5.6.8</id>
  </c>
  <c>
    <n>c6</n>
    <id></id>
  </c>
  <c>
    <n>c7</n>
    <id></id>
  </c>
</list>

Хочется превратить его при помощи xslt в иерархию:

<list>
  <c>
    <n>c6</n>
    <id></id>
  </c>
  <c>
    <n>c7</n>
    <id></id>
  </c>
  <c>
    <n>c1</n>
    <id>1</id>
    <c>
      <n>c3</n>
      <id>1/0</id>
      <c>
        <n>c2</n>
        <id>1/0/0</id>
      </c>
    </c>
  </c>
  <c>
    <n>c4</n>
    <id>1.2.3.4</id>
    <c>
      <n>c5</n>
      <id>1.2.3.4.5.6.8</id>
      <c>
        <n>c5</n>
        <id>1.2.3.4.5.6.8.9</id>
      </c>
    </c>
  </c>
</list>

Нужно найти все цепочки вхождений различных строк друг в друга, чтобы выстроить иерархию.
Ломаю голову уже несколько дней...

Доктор ТуамОсес: "Хорошая у Вас задача.

Я вот тоже давно думаю как из плоской базы данных заметок, где у каждой заметки есть несколько тэгов, выстраивать иерархию.

Задача усложняется тем, что нет однозначного решения: можно выстроить несколько разных деревьев.

Но хотелось бы что бы дерево строилось по принципу "от общего к частному".

Т.е. теги, выражающие общие понятия, оказались ближе к корню дерева"

<xsl:template match="/list">
<xsl:copy> <!-- = <list> -->
<xsl:for-each select="c">
<xsl:if test="not(../c[starts-with(id, current()/id)])">
<xsl:apply-templates select="."/>
</xsl:for-each>
</xsl:copy>
</xsl:template>

<xsl:template match="c">
<xsl:copy>
<xsl:copy-of select="*"/>
<xsl:apply-templates select="../c[starts-with(id, current()/id)]"/>
</xsl:copy>
</xsl:template>

Здравствуйте, _ustas_, Вы писали:

__>Нужно найти все цепочки вхождений различных строк друг в друга, чтобы выстроить иерархию.
__>Ломаю голову уже несколько дней...

У вас данные противоречать вашей формулировке, т.к. по формулировке узел с id="1.2.3.4" должен быть ребенком узла с id="1", а он в свою очередь должен иметь рождителя с id="".
Вот что у меня получилось:

<xsl:stylesheet version="1.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
    <xsl:output indent="yes"/>
    <xsl:template match="/">
        <result>
            <xsl:call-template name="out-c">
                <xsl:with-param name="nodes" select="/list/c[string-length(id) = 0]" />
            </xsl:call-template>
            <xsl:call-template name="out-c">
                <xsl:with-param name="nodes" select="/list/c[string-length(id) != 0]" />
            </xsl:call-template>
        </result>
    </xsl:template>

    <xsl:template name="out-c">
        <xsl:param name="nodes" />

        <xsl:for-each select="$nodes">
            <xsl:variable name="others" select="$nodes[generate-id() != generate-id(current())]"/>
            <xsl:if test="not($others[starts-with(current()/id, id) and current()/id != id])">
                <c>
                    <xsl:copy-of select="n | id"/>
                    <xsl:call-template name="out-c">
                        <xsl:with-param name="nodes" select="$others[starts-with(id, current()/id) and current()/id != id]" />
                    </xsl:call-template>
                </c>
            </xsl:if>
        </xsl:for-each>
    </xsl:template>
</xsl:stylesheet>

Здравствуйте, Lloyd, Вы писали:

L>Здравствуйте, _ustas_, Вы писали:

__>>Нужно найти все цепочки вхождений различных строк друг в друга, чтобы выстроить иерархию.
__>>Ломаю голову уже несколько дней...

L>У вас данные противоречать вашей формулировке, т.к. по формулировке узел с id="1.2.3.4" должен быть ребенком узла с id="1", а он в свою очередь должен иметь рождителя с id="".

Спасибо огромное за помощь!

На самом деле все верно, просто тут две независимые иерархии, если делиметер ".", то нужно искать только родителей с "." — они не могут быть "1", а только "1.1" или "1.1.1".
Если же делиметер "/", то родители могут быть и просто "1"...
Пустые узлы они не родители, это "ошибочные" как бы несконфигурированные. Их нужно просто в корень класть...
Так выгружает свои данные NMS система, это у CISCO два способа указания слотов устройств — с разделителями "." и "/".

пуристский подход с ключами, шаблонами и xslt 2.0

<?xml version="1.0"?>
<xsl:stylesheet version="2.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform" 
    xmlns:fn="http://www.w3.org/2004/07/xpath-functions"
    xmlns:tt="texunatech" extension-element-prefixes="tt fn">

<xsl:output method="xml" omit-xml-declaration="yes" indent="yes"/>

<xsl:key name="c-by-id-substrings" match="c" use="tt:generate-substrings(id/text(), 1)"/>
<xsl:key name="c-by-id" match="c" use="id"/>

<xsl:template match="/*">
    <xsl:copy>
        <xsl:apply-templates select="c[count(fn:distinct-values(key('c-by-id', tt:generate-substrings(id, 1))/id)) = 1]"/>
    </xsl:copy>
</xsl:template>

<xsl:template match="c">
    <xsl:copy>
        <xsl:copy-of select="*"/>
        <xsl:apply-templates select="key('c-by-id', fn:min(for $c in key('c-by-id-substrings', current()/id)[id != current()/id]/id return string($c)))"/>
    </xsl:copy>
</xsl:template>

<xsl:function name="tt:generate-substrings">
    <xsl:param name="str"/>
    <xsl:param name="pos"/>

    <xsl:sequence select="(substring($str, 1, $pos), if ($pos &lt; string-length($str)) then tt:generate-substrings($str, $pos + 1) else ())"/>
</xsl:function>
                   
</xsl:stylesheet>

Только тут не проверяется щекотливая ситуация, противоречащая начальному условию — элемент с id=1 может быть парентом элемента с id=1.2.3.4, а этого автор не хочет.



__>На самом деле все верно, просто тут две независимые иерархии, если делиметер ".", то нужно искать только родителей с "." — они не могут быть "1", а только "1.1" или "1.1.1".
__>Если же делиметер "/", то родители могут быть и просто "1"...
__>Пустые узлы они не родители, это "ошибочные" как бы несконфигурированные. Их нужно просто в корень класть...
__>Так выгружает свои данные NMS система, это у CISCO два способа указания слотов устройств — с разделителями "." и "/".

Немного накосячил.

<?xml version="1.0"?>
<xsl:stylesheet version="2.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform" 
    xmlns:fn="http://www.w3.org/2004/07/xpath-functions"
    xmlns:tt="texunatech" extension-element-prefixes="tt fn">

<xsl:output method="xml" omit-xml-declaration="yes" indent="yes"/>

<xsl:key name="c-by-id-substrings" match="c" use="tt:generate-substrings(id/text(), 1)"/>
<xsl:key name="c-by-id" match="c" use="id"/>

<xsl:template match="/*">
    <xsl:copy>
        <xsl:apply-templates select="c[count(fn:distinct-values(key('c-by-id', tt:generate-substrings(id, 1))/id)) = 1]"/>
    </xsl:copy>
</xsl:template>

<xsl:template match="c">
    <xsl:copy>
        <xsl:copy-of select="*"/>
            <xsl:apply-templates select="key('c-by-id-substrings', current()/id)[id != current()/id and 
            current()/id = fn:max(for $c in key('c-by-id', tt:generate-substrings(id, 1))/id return if ($c != id) then string($c) else ())]"/>
    </xsl:copy>
</xsl:template>

<xsl:function name="tt:generate-substrings">
    <xsl:param name="str"/>
    <xsl:param name="pos"/>

    <xsl:sequence select="(substring($str, 1, $pos), if ($pos &lt; string-length($str)) then tt:generate-substrings($str, $pos + 1) else ())"/>
</xsl:function>
                   
</xsl:stylesheet>