Durchführen eines Level-Order Traversal

(Auszug aus "XSLT Kochbuch" von Sal Mangano)

Problem

Sie wollen Elemente nach zunehmender Ebene (Baumtiefe) gliedern. Mit anderen Worten wollen Sie die Baumbreite zuerst durchlaufen.

Lösung

Diese Form des Durchlaufens ist wie geschaffen für die Verwendung von xsl:for-each zusammen mit xsl:sort:

<xsl:for-each select="//*">
  <xsl:sort select="count(ancestor::*)" data-type="number"/>
  <!-- Verarbeiten des aktuellen Elements -->
</xsl:for-each>

Diese rekursive Lösung ist länger und weniger offensichtlich:

<xsl:template match="/*">
  <xsl:call-template name="level-order"/>
</xsl:template>
<xsl:template name="level-order">
  <xsl:param name="max-level" select="10"/>
  <xsl:param name="current-level" select="1"/>
  <xsl:choose>
    <xsl:when test="$current-depth &lt;= $max-level">
      <!-- Verarbeiten der aktuellen Ebene -->
      <xsl:call-template name="level-order-aux">
        <xsl:with-param name="level" select="$current-level"/>
        <xsl:with-param name="actual-level" select="$current-level"/>
      </xsl:call-template>
      <!-- Verarbeiten der nächsten Ebene -->
      <xsl:call-template name="level-order">
        <xsl:with-param name="current-level" select="$current-level + 1"/>
      </xsl:call-template>
    </xsl:when>
  </xsl:choose>
</xsl:template>
<xsl:template name="level-order-aux">
  <xsl:param name="level" select="1"/>
  <xsl:param name="actual-level" select="1"/>
  <xsl:choose>
    <xsl:when test="$level = 1">
      <!-- Hier Verarbeiten des aktuellen Elements -->
      <!-- $actual-level ist die Nummer der aktuellen Ebene -->
    </xsl:when>
    <xsl:otherwise>
      <!-- Bei allen Kindern rekursives Absteigen auf die nächste Ebene -->
      <xsl:for-each select="*">
        <xsl:call-template name="level-order-aux">
          <xsl:with-param name="level" select="$level - 1"/>
          <xsl:with-param name="actual-level" select="$actual-level"/>
        </xsl:call-template>
      </xsl:for-each>
    </xsl:otherwise>
  </xsl:choose>
</xsl:template>

Diese Lösung erfordert es, dass Sie entweder eine beliebige Grenze für die maximale Tiefe des Baums setzen oder die maximale Tiefe berechnen. Eine Möglichkeit hierzu besteht darin, den Knoten zu ermitteln, der keine Kinder und mehr Vorfahren hat als alle anderen Knoten ohne Kinder:

<xsl:param name="max-level">
  <xsl:for-each select="//*[not(*)]">
    <xsl:sort select="count(ancestor::*)" data-type="number" order="descending" />
    <xsl:if test="position( ) = 1">
      <xsl:value-of select="count(ancestor::*) + 1" />
    </xsl:if>
  </xsl:for-each>
</xsl:param>

Diskussion

Es besteht wohl nicht oft Bedarf am ebenenweisen Durchlaufen eines XML-Dokuments. Das Gruppieren von Knoten nach Tiefe oder Abstand von der Wurzel passt nicht in den natürlichen Kontrollfluss von XSLT, das bei einem Durchlaufen in den Dokumentenbaum absteigen soll. Dies wird durch die Tatsache offenbar, dass Sie xsl:sort benutzen mussten, um das Stylesheet dazu zu bringen, dass es die Knoten nach ihrer Tiefe oder äquivalent dazu nach der Anzahl der Vorfahren verarbeitet. Die Komplexität der rekursiven Lösung ist ein weiterer Beweis für diesen unnatürlichen Vorgang.

Dennoch ist diese Form des Durchlaufens manchmal ganz praktisch. Beispielsweise können Sie sie verwenden, um ein Organigramm (orgchart.xml) zu verarbeiten, das Angestellte anhand ihres Abstands von der Unternehmensspitze auflistet, wie im folgenden Beispiel dargestellt. Die Ausgabe wird im darauffolgenden Beispiel gezeigt.

Beispiel: Level-Order Traversal von orgrchart.xml mit Hilfe von sort.

<?xml version="1.0" encoding="UTF-8"?>
<xsl:stylesheet version="1.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
  <xsl:output method="text"/>
  <xsl:template match="/">
    <xsl:for-each select="//employee">
      <xsl:sort select="count(ancestor::*)" order="ascending"/>
      <xsl:variable name="level" select="count(ancestor::*)"/>
      <xsl:choose>
        <xsl:when test="$level = 0">
          <xsl:value-of select="@name"/>
          <xsl:text> ist der Boss.&#xA;</xsl:text>
        </xsl:when>
        <xsl:otherwise>
          <xsl:value-of select="@name"/>
          <xsl:text> hat </xsl:text>
          <xsl:value-of select="$level"/>
          <xsl:text> Chef(s) zu erledigen.&#xA;</xsl:text>
        </xsl:otherwise>
      </xsl:choose>
    </xsl:for-each>
  </xsl:template>
</xsl:stylesheet>

Beispiel: Ausgabe.

Jil Michel ist der Boss.
Nancy Pratt hat 1 Chef(s) zu erledigen.
Jane Doe hat 1 Chef(s) zu erledigen.
Mike Rosenbaum hat 1 Chef(s) zu erledigen.
Phill McKraken hat 2 Chef(s) zu erledigen.
Ima Little hat 2 Chef(s) zu erledigen.
Walter H. Potter hat 2 Chef(s) zu erledigen.
Wendy B.K. McDonald hat 2 Chef(s) zu erledigen
Cindy Post-Kellog hat 2 Chef(s) zu erledigen.
Oscar A. Winner hat 2 Chef(s) zu erledigen.
Betsy Ross hat 3 Chef(s) zu erledigen.
Craig F. Frye hat 3 Chef(s) zu erledigen.
Hardy Hamburg hat 3 Chef(s) zu erledigen.
Rich Shaker hat 3 Chef(s) zu erledigen.
Allen Bran hat 3 Chef(s) zu erledigen.
Frank N. Berry hat 3 Chef(s) zu erledigen.
Jack Apple hat 3 Chef(s) zu erledigen.
Jack Nicklaus hat 3 Chef(s) zu erledigen.
Tom Hanks hat 3 Chef(s) zu erledigen.
Susan Sarandon hat 3 Chef(s) zu erledigen.
R.P. McMurphy hat 4 Chef(s) zu erledigen.
Forrest Gump hat 4 Chef(s) zu erledigen.
Andrew Beckett hat 4 Chef(s) zu erledigen.
Helen Prejean hat 4 Chef(s) zu erledigen.

Ein Vorteil der rekursiven Variante besteht darin, dass es einfach ist festzustellen, wann Sie von einer Ebene auf die nächste wechseln. Sie könnten diese Information einsetzen, um Ihre Ausgabe besser zu formatieren, wie in den beiden folgenden Beispielen gezeigt wird.

Beispiel: Level-Order Traversal von orgrchart.xml mit Hilfe von Rekursion.

<?xml version="1.0" encoding="UTF-8"?>
<xsl:stylesheet version="1.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
  <xsl:output method="text" version="1.0" encoding="UTF-8"/>
  <xsl:strip-space elements="*"/>
  <xsl:template match="/employee">
    <xsl:call-template name="level-order"/>
  </xsl:template>
  <xsl:template name="level-order">
    <xsl:param name="max-depth" select="10"/>
    <xsl:param name="current-depth" select="0"/>
    <xsl:choose>
      <xsl:when test="$current-depth &lt;= $max-depth">
        <xsl:variable name="text">
          <xsl:call-template name="level-order-aux">
            <xsl:with-param name="level" select="$current-depth"/>
            <xsl:with-param name="actual-level" select="$current-depth"/>
          </xsl:call-template>
        </xsl:variable>
        <xsl:if test="normalize-space($text)">
          <xsl:value-of select="$text"/>
          <xsl:text>&#xa;</xsl:text>
          <xsl:call-template name="level-order">
            <xsl:with-param name="current-depth" select="$current-depth + 1"/>
          </xsl:call-template>
        </xsl:if>
      </xsl:when>
    </xsl:choose>
  </xsl:template>
  <xsl:template name="level-order-aux">
    <xsl:param name="level" select="0"/>
    <xsl:param name="actual-level" select="0"/>
    <xsl:choose>
      <xsl:when test="$level = 0">
        <xsl:choose>
          <xsl:when test="$actual-level = 0">
            <xsl:value-of select="@name"/>
            <xsl:text> ist der Boss.&#xA;</xsl:text>
          </xsl:when>
          <xsl:otherwise>
            <xsl:value-of select="@name"/>
            <xsl:text> hat </xsl:text>
            <xsl:value-of select="$actual-level"/>
            <xsl:text> Chef(s) zu erledigen.&#xA;</xsl:text>
          </xsl:otherwise>
        </xsl:choose>
      </xsl:when>
      <xsl:otherwise>
        <xsl:for-each select="employee">
          <xsl:call-template name="level-order-aux">
            <xsl:with-param name="level" select="$level - 1"/>
            <xsl:with-param name="actual-level" select="$actual-level"/>
          </xsl:call-template>
        </xsl:for-each>
      </xsl:otherwise>
    </xsl:choose>
  </xsl:template>
</xsl:stylesheet>

Ausgabe.

Jil Michel ist der Boss.

Nancy Pratt hat 1 Chef(s) zu erledigen.
Jane Doe hat 1 Chef(s) zu erledigen.
Mike Rosenbaum hat 1 Chef(s) zu erledigen.

Phill McKraken hat 2 Chef(s) zu erledigen.
Ima Little hat 2 Chef(s) zu erledigen.
Walter H. Potter hat 2 Chef(s) zu erledigen.
Wendy B.K. McDonald hat 2 Chef(s) zu erledigen.
Cindy Post-Kellog hat 2 Chef(s) zu erledigen.
Oscar A. Winner hat 2 Chef(s) zu erledigen.

Betsy Ross hat 3 Chef(s) zu erledigen.
Craig F. Frye hat 3 Chef(s) zu erledigen.
Hardy Hamburg hat 3 Chef(s) zu erledigen.
Rich Shaker hat 3 Chef(s) zu erledigen.
Allen Bran hat 3 Chef(s) zu erledigen.
Frank N. Berry hat 3 Chef(s) zu erledigen.
Jack Apple hat 3 Chef(s) zu erledigen.
Jack Nickolas hat 3 Chef(s) zu erledigen.
Tom Hanks hat 3 Chef(s) zu erledigen.
Susan Sarandon hat 3 Chef(s) zu erledigen.

R.P. McMurphy hat 4 Chef(s) zu erledigen.
Forrest Gump hat 4 Chef(s) zu erledigen.
Andrew Beckett hat 4 Chef(s) zu erledigen.
Helen Prejean hat 4 Chef(s) zu erledigen.

Falls Sie aus irgendeinem Grund wahlfreien Zugriff auf Knoten auf einer bestimmten Ebene haben wollten, könnten Sie folgendermaßen einen Schlüssel definieren:

<xsl:key name="level" match="employee" use="count(ancestor::*)"/>
<xsl:template match="/">
  <xsl:for-each select="key('level',3)">
    <!-- Irgendetwas mit den Knoten auf Ebene 3 tun -->
  </xsl:for-each>
</xsl:template>

Sie könnten die Auswahl auch noch genauer spezifizieren oder ein Prädikat mit der Funktion key verwenden:

<xsl:key name="level" match="//employee" use="count(ancestor::*)"/>
<xsl:template match="/">
  <xsl:for-each select="key('level',3)[@sex='female']">
    <!-- Irgendetwas mit den weiblichen Angestellten auf Ebene 3 tun -->
  </xsl:for-each>
</xsl:template>

Die Verwendung der key-Funktion von XSLT ist nicht zwingend vorgeschrieben, da Sie immer auch select="//*[count(ancestors::*)=3]" schreiben können, wenn Sie Zugriff auf Elemente der Ebene 3 benötigen; allerdings leidet die Leistung, wenn Ihr Stylesheet wiederholt einen solchen Ausdruck auswertet. Falls Ihr Stylesheet, um genau zu sein, eine wohldefinierte Struktur besitzt, sind Sie besser dran, wenn Sie ausdrücklich zur gewünschten Ebene navigieren, z. B. select="/employee/employee/employee", obwohl diese Art der Navigation ziemlich unhandlich werden kann.

  

<< zurück vor >>

 

 

 

Tipp der data2type-Redaktion:
Zum Thema XSLT bieten wir auch folgende Schulungen zur Vertiefung und professionellen Fortbildung an:

Copyright © 2006 O'Reilly Verlag GmbH & Co. KG
Für Ihren privaten Gebrauch dürfen Sie die Online-Version ausdrucken.
Ansonsten unterliegt dieses Kapitel aus dem Buch "XSLT Kochbuch" denselben Bestimmungen, wie die gebundene Ausgabe: Das Werk einschließlich aller seiner Teile ist urheberrechtlich geschützt. Alle Rechte vorbehalten einschließlich der Vervielfältigung, Übersetzung, Mikroverfilmung sowie Einspeicherung und Verarbeitung in elektronischen Systemen.

O'Reilly Verlag GmbH & Co. KG, Balthasarstraße 81, 50670 Köln, kommentar(at)oreilly.de