Zipper

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)