Anleitung
Einen Zipper für einen Binärbaum erstellen.
Zipper sind eine rein funktionale Art, innerhalb einer Datenstruktur zu navigieren und sie zu verändern.
Sie bestehen im Wesentlichen aus einer Datenstruktur und einem Zeiger in diese Datenstruktur (der Fokus genannt wird).
Ein Zipper könnte zum Beispiel für einen Rose Tree (bei dem jeder Knoten einen Wert und eine Liste von Kindknoten enthält) die folgenden Operationen unterstützen:
-
from_tree (erzeugt einen Zipper aus einem Rose Tree, der Fokus liegt auf dem Wurzelknoten)
-
to_tree (erzeugt den Rose Tree aus dem Zipper)
-
value (gibt den Wert des Fokusknotens zurück)
-
prev (verschiebt den Fokus zum vorherigen Kindknoten desselben Elternknotens,
gibt einen neuen Zipper zurück)
-
next (verschiebt den Fokus zum nächsten Kindknoten desselben Elternknotens, gibt
einen neuen Zipper zurück)
-
up (verschiebt den Fokus zum Elternknoten, gibt einen neuen Zipper zurück)
-
set_value (setzt den Wert des Fokusknotens, gibt einen neuen Zipper zurück)
-
insert_before (fügt einen neuen Unterbaum vor dem Fokusknoten ein, er wird zum
prev des Fokusknotens, gibt einen neuen Zipper zurück)
-
insert_after (fügt einen neuen Unterbaum nach dem Fokusknoten ein, er wird zum
next des Fokusknotens, gibt einen neuen Zipper zurück)
-
delete (entfernt den Fokusknoten und alle Unterbäume, der Fokus wandert zum
next-Knoten, wenn möglich, ansonsten zum prev-Knoten, wenn möglich,
ansonsten zum Elternknoten, gibt einen neuen Zipper zurück)
Verhalten des Zippers
Der Zipper bietet eine funktionale Möglichkeit, in einem Node-Baum zu navigieren.
Alle Zipper-Aufrufe sollten ein neues Zipper-Objekt zurückgeben.
Wenn der Zipper keine Werte ändert (d. h. keine Set*-Methode wurde aufgerufen), sollte der Zipper denselben zugrunde liegenden Baum verwenden.
Wenn eine Set*-Methode aufgerufen wird, sollte der neue Zipper einen neuen Baum haben, während der ursprüngliche Baum unverändert bleibt.
Zipper-Aufrufe, die den Fokus auf einen ungültigen Node setzen, sollten einen Fehler zurückgeben.
