Wie viele Blätter hat der BaumHeute habe ich mich mal dem Dojo aus der aktuellen Dotnetpro gewidmet. Primär möchte ich damit üben hier im Blog zu dokumentieren und die Gedankengänge nieder zu schreiben. Bei dem Dojo selbst geht es um eine API die Bäume abbildet und deren Inhalt ausgeben kann. Es ist eines der einfacheren Dotnetpro Dojos. In der Aufgabenstellung sind zwei generische Interfaces vorgegeben die zu implementieren sind.
Bei der Implementierung soll besonderes Augenmerk auf die beiden Methoden
PreOrderValues() und
PostOrderValues() gelegt werden. Diese dienen dazu den Inhalt der Bäume zu durchlaufen. Genau hier liegt aber der Knackpunkt, denn welchen Weg nimmt man beim Durchlaufen eines Baums? Anders als bei gewöhnlichen Listen gibt es hier nicht nur einen Start und Endpunkt. Zu den beiden Methoden werden zwei Beispiele geliefert um die Wege zu demonstrieren so einen Baum zu durchlaufen.
- Wurzel als Startpunkt - Diese Variante gibt zunächst das Wurzelelement zurück. Dann die Kind-Elemente des Wurzelelements und wiederum deren Kind-Elemente usw.
- Blätter als Startpunkt - Diese Variante fungiert gerade umgekehrt. Sie beginnt bei den Blättern und gibt damit zunächst die äussersten Elemente zurück, um sich anschliessend immer weiter bis zur Wurzel voranzuarbeiten.
Unit-TestFür die Durchführung des Dojos werden automatisierte Unit-Tests gefordert. Deshalb beginne ich zunächst diese Tests einzurichten, damit ich meine spätere Arbeit direkt überprüfen kann. Ich nutze dazu das kostenlose Framework
NUnit.
Ich habe nun zwei Test-Methoden erstellt die jweils eine der beiden oben genannten Durchlauf-Varianten testen. Da die beiden Interfaces bereits vorhanden sind konnte ich fast den kompletten Testcode bereits im Voraus fertigstellen. Lediglich eine Instanz des Tree mit dem Root-Node fehlt noch.
Der erste Unit-Test schlägt in diesem Zustand natürlich auch prompt fehl, da es zu einer
NullReferenceException kommt. Nicht weiter verwunderlich.
Implementierung der InterfacesEs wird nun also Zeit die Klassen zu erstellen, welche die beiden Interfaces implementieren. Dazu lege ich die generischen Klassen
Tree und
Node an. Hierbei übernimmt zunächst Visual Studio die meiste Arbeit, indem es die Eigenschafts- und Methodenrümpfe erstellt, die von den Interfaces gefordert werden.
Bevor ich jedoch mit der Implementierung des Codes beginne, denke ich zunächst darüber nach wie die beiden Klassen instantiiert werden sollen. Gut zu erkennen ist ja bereits die durch das Interface
INode vorgegebene
Add-Methode. Sie nimmt einen Parameter vom Typ
T entgegen und gibt eine
INode(Of T) zurück. Somit muss innerhalb der Methode aus dem Parameter vom Typ
T eine
Node werden welche diesen kapselt. Da die
Value-Eigenschaft einer
INode nur les- und nicht schreibbar ist, muss der Wert über den Konstruktor der
Node -Klasse injiziert werden.
Wenn einer
Node eine Child-Node mit Hilfe der
Add-Methode hinzugefügt wird, dann muss diese neue Child-Node auch innerhalb der
Node gespeichert werden. Dazu benötige ich ein privates Feld.
Der Wert der für eine
Node im Konstruktor angegeben wird muss natürlich ebenso gespeichert werden. Dazu gibt es ebenfalls ein privates Feld in der Klasse
Node.
Die Eigenschaften
Value,
Children und
ChildValues sind leicht zu implementieren. Sie geben lediglich die Inhalte der beiden privaten Felder zurück.
Zuletzt noch die Klasse
Tree. Sie beinhaltet bisher eine Eigenschaft vom Typ
INode(Of T). Dabei handelt es sich um das Wurzelelement. Da ein Baum nicht existieren kann ohne eine Wurzel zu haben, soll der Wert für das Wurzelelement direkt im Konstruktor des Baums angegeben.
Todo-Liste:- Konstruktor für Node mit Wert von Typ T als Parameter
- Privates Feld um Child-Nodes zu speichern.
- Privates Feld um Inhalt/Wert der Node zu speichern
- Eigenschaften Value, Children und ChildValues an den Inhalt der privaten Felder anbinden
- Konstruktor für Tree mit der von Typ T als Parameter
Genug darüber nachgedacht. Diese Liste kann erstmal abgearbeitet werden bevor ich mir Gedanken über die beiden Methoden
PostOrderValues() und
PreOrderValues() mache.
Der Code ist nun bis auf die beiden Methoden implementiert. Erstmals können nun auch die beiden Methoden des Unit-Test komplettiert werden indem die beiden Tree-Felder mit Tree-Instanzen gefüllt werden.
tree = New Tree(Of Int32)(1)Führe ich den Unit-Test nun aus, wird er erneut fehlschlagen. Dieses Mal jedoch erst an späterer Stelle, nämlich nach dem Aufruf der Methoden
PostOrderValues() und
PreOrderValues(). Diese liefern noch eine Null-Referenz was in den Assertions für die entsprechenden Fehler sorgt.
Die Methode PreOrderValuesNun ist es soweit und die beiden Methoden kommen an die Reihe.
Nochmal das Ergebnis des Beispiels bzw. der Methode
PreOrderValues() anschauen:
{1, 2, 5, 6, 3, 7, 8, 4, 9, 10}
Zunächst wird der Inhalt der Root-Node (1) ausgegeben, dann der Inhalt der ersten Child-Node (2) und zuletzt der Inhalt der beiden Child-Nodes (5, 6) der Child-Node (2).
Was bedeutet das nun für die Methode
PreOrderValues? Auf Root-Ebene soll die Methode in dem Beispiel eine Liste mit den oben genannten 10 Werten zurückgeben. Auf zweiter Ebene eine Liste mit 3 Elementen und auf letzter Ebene eine Liste mit einem Element. Auf letzter Ebene kann die Methode nur den Inhalt der Node Instanz zurückgeben da keine Child-Nodes vorhanden sind. Es ergibt sich also die Bedingung: Wenn keine Child-Nodes vorhanden, dann besteht die Ergebnisliste nur aus mir selbst. Sind Child-Nodes vorhanden besteht die Ergebnisliste aus mir selbst + deren Ergebnislisten.
Die Methode PostOrderValuesDer Unterschied zur Methode
PreOrderValues liegt darin, dass diese zunächst den Wert der zugehörigen Node selbst ausgibt und anschliessend die Werte der Child-Nodes. Diese Methode soll es umgekehrt tun, zunächst die Werte der Child-Nodes und anschliessend den eigenen. Was liegt also näher als einfach die Reihenfolge des Codings zu verdrehen? Gesagt getan, und siehe da es funktioniert.
ZusammenfassungDas Dojo war bestens geeignet um einen Blog-Post zu verfassen. Es war simpel und schnell gemacht, so dass ich mich mehr um das aufschreiben kümmern konnte. Doch genau dies ist auch die Intention der Dotnetpro Dojos - es geht nicht um das Coding selbst, sondern um das drum herum.
 |
| Finally :-) |
