Durchführen eines Preorder Traversal

(Auszug aus "XSLT Kochbuch" von Sal Mangano)

Problem

Sie wollen rekursiv zuerst ein Element und dann dessen Kindelemente verarbeiten.

Lösung

Lösungen zu diesem Rezept weisen die folgende allgemeine Form auf:

<xsl:template match="node( )">
  <!-- Irgendetwas mit dem aktuellen Knoten tun -->
  <!--Kinder verarbeiten -->
  <xsl:apply-templates/>
</xsl:template>

Diskussion

Der Begriff Preorder (Präordnung oder Quasiordnung) ist ein Begriff aus der Informatik für das Durchlaufen eines Baumes derart, dass zuerst die Wurzel und rekursiv die Kinder der Wurzel in Präordnung besucht werden. Dieser Vorgang ist wohl die gebräuchlichste Methode für die Verarbeitung von XML. In diesem Kapitel werden zwei der vielen Anwendungen dieses Idioms betrachtet. Wenn Sie sich Rezepte in späteren Kapiteln anschauen, werden Sie diese Art des Durchlaufens häufig bemerken.

Stellen Sie sich ein Organigramm (orgchart.xml) vor, das in vereinfachter Weise kodiert, dass ein Angestelltenelement B das Kind eines anderen Angestelltenelements A ist, falls B bei A Bericht erstattet. Das folgende Beispiel setzt ein Preorder Traversal ein, um zu erklären, wer wen verwaltet. Das darauffolgende Beispiel zeigt die Ausgabe.

Beispiel: Stylesheet.

<?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:strip-space elements="*"/>
  <xsl:template match="/employee" priority="10">
    <xsl:value-of select="@name"/><xsl:text> ist Chef des Unternehmens. </xsl:text>
    <xsl:call-template name="HeShe"/><xsl:text> verwaltet </xsl:text>
    <xsl:call-template name="manages"/>
    <xsl:apply-templates/>
  </xsl:template>
  <xsl:template match="employee[employee]">
    <xsl:value-of select="@name"/> <xsl:text> ist ein Manager. </xsl:text>
    <xsl:call-template name="HeShe"/> <xsl:text> verwaltet </xsl:text>
    <xsl:call-template name="manages"/>
    <xsl:apply-templates/>
  </xsl:template>
  <xsl:template match="employee">
    <xsl:value-of select="@name"/><xsl:text> hat keine Sorgen. </xsl:text>
    <xsl:text>&#xa;&#xa;</xsl:text>
  </xsl:template>
  <xsl:template name="HeShe">
    <xsl:choose>
      <xsl:when test="@sex = 'male' ">
        <xsl:text>Er</xsl:text>
      </xsl:when>
      <xsl:otherwise>
        <xsl:text>Sie</xsl:text>
      </xsl:otherwise>
    </xsl:choose>
  </xsl:template>
  <xsl:template name="manages">
    <xsl:for-each select="*">
      <xsl:choose>
        <xsl:when test="position() != last() and last() &gt; 2">
          <xsl:value-of select="@name"/><xsl:text>, </xsl:text>
        </xsl:when>
        <xsl:when test="position() = last() and last() &gt; 1">
          <xsl:text> und </xsl:text><xsl:value-of select="@name"/><xsl:text>. </xsl:text>
        </xsl:when>
        <xsl:when test="last() = 1">
          <xsl:value-of select="@name"/><xsl:text>. </xsl:text>
        </xsl:when>
        <xsl:otherwise>
          <xsl:value-of select="@name"/>
        </xsl:otherwise>
      </xsl:choose>
    </xsl:for-each>
    <xsl:text>&#xa;&#xa;</xsl:text>
  </xsl:template>
</xsl:stylesheet>

Beispiel: Ausgabe.

Jil Michel ist Chef des Unternehmens. Sie verwaltet Nancy Pratt, Jane Doe und Mike Rosenbaum.

Nancy Pratt ist ein Manager. Sie verwaltet Phill McKraken und Ima Little.

Phill McKraken muss sich um nichts kümmern.

Ima Little ist ein Manager. Sie verwaltet Betsy Ross.

Betsy Ross muss sich um nichts kümmern.

Jane Doe ist ein Manager. Sie verwaltet Walter H. Potter und Wendy B.K. McDonald.

Walter H. Potter muss sich um nichts kümmern.

Wendy B.K. McDonald ist ein Manager. Sie verwaltet Craig F. Frye, Hardy Hamburg und Rich Shaker.

Craig F. Frye muss sich um nichts kümmern.

Hardy Hamburg muss sich um nichts kümmern.

Rich Shaker muss sich um nichts kümmern.

Mike Rosenbaum ist ein Manager. Er verwaltet Cindy Post-Kellog und Oscar A. Winner.

Cindy Post-Kellog ist ein Manager. Sie verwaltet Allen Bran, Frank N. Berry und Jack Apple.

Allen Bran muss sich um nichts kümmern.

Frank N. Berry muss sich um nichts kümmern.

Jack Apple muss sich um nichts kümmern.

Oscar A. Winner ist ein Manager. Er verwaltet Jack Nickolas, Tom Hanks und Susan Sarandon.

Jack Nicklaus ist ein Manager. Er verwaltet R.P. McMurphy.

R.P. McMurphy muss sich um nichts kümmern.

Tom Hanks ist ein Manager. Er verwaltet Forrest Gump und Andrew Beckett.

Forrest Gump muss sich um nichts kümmern.

Andrew Beckett muss sich um nichts kümmern.

Susan Sarandon ist ein Manager. Sie verwaltet Helen Prejean.

Helen Prejean muss sich um nichts kümmern.

Eine ernsthaftere Anwendung des Preorder Traversal ist die Konvertierung eines Ausdrucksbaums in die Präfixnotation. Auf der Grundlage des MathML-Fragments in den folgenden beiden Beispielen können Sie eine Transformation in eine Lisp-artige Syntax durchführen.

Beispiel: MathML-Fragment, das x2+4x+4 = 0 repräsentiert.

<apply>
  <eq/>
  <apply>
    <plus/>
    <apply>
      <power/>
      <ci>x</ci>
      <cn>2</cn>
    </apply>
    <apply>
      <times/>
      <cn>4</cn>
      <ci>x</ci>
    </apply>
    <cn>4</cn>
  </apply>
  <cn>0</cn>
</apply>

Beispiel: Stylesheet zum Konvertieren des MathML-Fragments in die Präfixnotation.

<?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:strip-space elements="*"/>
  <xsl:template match="apply">
    <xsl:value-of select="local-name(*[1])"/>
    <xsl:text>(</xsl:text>
    <xsl:apply-templates/>
    <xsl:text>)</xsl:text>
    <xsl:if test="following-sibling::*">,</xsl:if>
  </xsl:template>
  <xsl:template match="ci|cn">
    <xsl:value-of select="."/>
    <xsl:if test="following-sibling::*">,</xsl:if>
  </xsl:template>
</xsl:stylesheet>

Beispiel: Ausgabe.

eq(plus(power(x,2),times(4,x),4),0)

Der MathML-Konverter ist nicht das reinste Beispiel für Preorder Traversal, vor allem, weil MathML mathematische Ausdrücke auf unkonventionelle Weise kodiert. Er ist im Wesentlichen ein Ausdruck des Preorder-Idioms, weil der Code das apply-Element zuerst verarbeitet (und den Namen seines ersten Kindelements ausgibt) und dann dessen Kindelemente rekursiv verarbeitet (über <xsl:apply-templates/>). Der Code, der apply-templates folgt, setzt schließende Klammern und fügt Kommas ein, wo erforderlich, und hat kein weiteres Durchlaufen zur Folge.

  

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