Baumkletterer

(Auszug aus "Perl & XML" von Erik T. Ray & Jason McIntosh)

Das erste dieser Werkzeuge ist der Baumkletterer. Wie der Name schon nahe legt, kann er einen Baum »ersteigen«, um Knoten in einer vorgegebenen Reihenfolge zu finden. Das vereinfacht den Quelltext und ermöglicht es, sich auf die Bearbeitung der Knoten zu konzentrieren. Den Baumkletterer zu benutzen ähnelt dem Einsatz eines trainierten Affen für das Pflücken von Kokosnüssen: Man muß nicht die eigene Haut riskieren und kann sich damit begnügen, ein Loch mit Meerwasser in den Strand zu graben, um die gepflückten Nüsse feucht zu halten.

Der einfachste Baumkletterer ist ein Iterator (manchmal auch Läufer genannt). Er kann sich im Baum vorwärts oder rückwärts bewegen, indem er sich in der gewünschten Weise entlang der Knotenreferenzen hangelt. Unter dem Begriff »vorwärts« verstehen wir dabei dieselbe Reihenfolge, die die Knoten auch im ursprünglichen Textdokument hatten oder im letztendlichen Dokument haben werden. Der genaue Algorithmus einer Vorwärtsbewegung sieht so aus:

  • Wenn es keinen aktuellen Knoten gibt, dann beginne beim Wurzelknoten.
  • Wenn der aktuelle Knoten Kinder hat, dann begib dich zum ersten Kindknoten.
  • Wenn das nicht der Fall ist und der akuelle Knoten nachfolgende Geschwister hat, dann begib dich zum ersten dieser Geschwister.
  • Wenn auch das nicht der Fall ist, dann begib dich solange zum jeweils nächsten Vaterknoten, bis einer mit nachfolgenden Geschwistern gefunden wird.

Der Algorithmus garantiert, daß jeder Knoten des Baums bzw. Teilbaums genau einmal als aktueller Knoten durchlaufen wird. Das funktioniert also wunderbar, wenn man alle Knoten eines Teildokuments bearbeiten will. Man kann den Algorithmus natürlich auch recht einfach mit Hilfe von Rekursion nachbilden. Der Vorteil einer iterativen Vorgehensweise besteht darin, daß man die Kontrolle recht einfach an Subroutinen übergeben kann, indem man ihnen den Iterator übergibt. Das Beispiel unten zeigt die Implementierung eines Iterators für DOM-Bäume. Wir haben Methoden für die Vorwärts- und Rückwärtsbewegung eingebaut.

Beispiel: Ein DOM-Iterator als Modul

package XML::DOMIterator;    

sub new {
    my $class = shift;
    my $self = {@_};
    $self->{ Node } = undef;
    return bless( $self, $class );
}

# Einen Knoten vorwärts bewegen
#
sub forward {
    my $self = shift;
  
    # Versuche zunächst, den Baum hinunter zu klettern
    if( $self->is_element and
    $self->{ Node }->getFirstChild ) {
    $self->{ Node } = $self->{ Node }->getFirstChild;
  
    # Keine Kindknoten, also begib dich zu den nachfolgenden Geschwistern,
    # eventuell zu denen eines Ahnen
    } else {
        while( $self->{ Node }) {
            if( $self->{ Node }->getNextSibling ) {
            $self->{ Node } = $self->{ Node }->getNextSibling;
            return $self->{ Node };
       }
      $self->{ Node } = $self->{ Node }->getParentNode;
    }
  }
}

# Rückwärtsbewegung um einen Knoten
#
sub backward {
    my $self = shift;
  
    # Begib dich zu den vorigen Geschwistern, sofern vorhanden,
    # ggf. auch zu deren Kindknoten.
    if( $self->{ Node }->getPreviousSibling ) {
        $self->{ Node } = $self->{ Node }->getPreviousSibling;
        while( $self->{ Node }->getLastChild ) {
            $self->{ Node } = $self->{ Node }->getLastChild;
    }
  
    # Aufwärts
    } else {
    $self->{ Node } = $self->{ Node }->getParentNode;
    }
    return $self->{ Node };
}

# Referenz auf den aktuellen Knoten liefern
#
sub node {
    my $self = shift;
    return $self->{ Node };
}

# Aktuellen Knoten setzen
#
sub reset {
    my( $self, $node ) = @_;
    $self->{ Node } = $node;
}

# Prüfung, ob der aktuelle Knoten ein Element ist
#
sub is_element {
    my $self = shift;
    return( $self->{ Node }->getNodeType == 1 );
}

Im nächsten Beispiel sehen wir ein Testprogramm für den Iterator. Er gibt für jeden Knoten des Baums eine kurze Beschreibung aus – erst vorwärts und dann rückwärts.

Beispiel: Ein Testprogramm für das Iteratormodul

use XML::DOM;   

# Initialisierung von Parser und Iterator
my $dom_parser = new XML::DOM::Parser;
my $doc = $dom_parser->parsefile( shift @ARGV );
my $iter = new XML::DOMIterator;
$iter->reset( $doc->getDocumentElement );

# Vorwärtsbewegung mit Ausgabe aller Knoten
print "\nVorwärts:\n";
my $node = $iter->node;
my $last;
while( $node ) {
   describe( $node );
   $last = $node;
   $node = $iter->forward;
}

# und jetzt dasselbe rückwärts
print "\nRückwärts:\n";
$iter->reset( $last );
describe( $iter->node );
while( $iter->backward ) {
   describe( $iter->node );
}

# Informationen über einen Knoten ausgeben
#
sub describe {
   my $node = shift;
   if( ref($node) =~ /Element/ ) {
      print 'element: ', $node->getNodeName, "\n";
      } elsif( ref($node) =~ /Text/ ) {
      print "other node: \"", $node->getNodeValue, "\"\n";
   }
}

Die meisten baumorientierten XML-Parser haben Baumkletterer eingebaut. Zum Beispiel kennt XML::LibXML::Node eine Methode iterator( ), die den Teilbaum des Baums durchläuft und alle gefundenen Knoten der Reihe nach an eine Subroutine übergibt. Das Modul Data::Grove::Visitor implementiert ebenfalls einen Iterator.

Das folgende Beispiel zeigt ein Programm, das einen Baumkletterer verwendet, um Verarbeitungsanweisungen (PIs) in einem Dokument zu suchen.

Beispiel: Ein Suchprogramm für Verarbeitungsanweisungen

use XML::LibXML;

my $dom = new XML::LibXML;
my $doc = $dom->parse_file( shift @ARGV );
my $docelem = $doc->getDocumentElement;
$docelem->iterator( \&find_PI );

sub find_PI {
   my $node = shift;
   return unless( $node->nodeType == &XML_PI_NODE );
   print "PI gefunden: ", $node->nodeName, "\n";
}

Baumkletterer sind hervorragend geeignet für die Bearbeitung kompletter Teilbäume, da sie in diesem Fall die Navigation vollständig übernehmen können. Es wird aber häufig vorkommen, daß Sie nicht an jedem einzelnen Knoten interessiert sind, sondern lieber gezielt den einen oder anderen herausgreifen wollen. Zum Beispiel suchen Sie vielleicht nach Elementen mit einem bestimmten Namen oder einem besonderen Attributwert. In diesem Fall könnte der selektivere Ansatz von XPath für Sie interessant sein, den wir in XPath einführen werden.

  

  

<< zurück vor >>

 

 

 

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

Copyright © 2003 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 "Perl & XML" 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