Istruzioni
Creare uno zipper per un albero binario.
Gli zipper sono un modo puramente funzionale di navigare all'interno di una struttura dati e di manipolarla.
In sostanza contengono una struttura dati e un puntatore all'interno di quella struttura dati (chiamato focus).
Per esempio, dato un rose tree (in cui ogni nodo contiene un valore e una lista di nodi figli), uno zipper potrebbe supportare queste operazioni:
-
from_tree (ottiene uno zipper da un rose tree, il focus è sul nodo radice)
-
to_tree (ottiene il rose tree dallo zipper)
-
value (ottiene il valore del nodo del focus)
-
prev (sposta il focus sul figlio precedente dello stesso genitore, restituisce un nuovo zipper)
-
next (sposta il focus sul figlio successivo dello stesso genitore, restituisce un nuovo zipper)
-
up (sposta il focus sul genitore, restituisce un nuovo zipper)
-
set_value (imposta il valore del nodo del focus, restituisce un nuovo zipper)
-
insert_before (inserisce un nuovo sottoalbero prima del nodo del focus, diventa il prev del nodo del focus, restituisce un nuovo zipper)
-
insert_after (inserisce un nuovo sottoalbero dopo il nodo del focus, diventa il next del nodo del focus, restituisce un nuovo zipper)
-
delete (rimuove il nodo del focus e tutti i sottoalberi, il focus si sposta sul nodo next se possibile, altrimenti sul nodo prev se possibile, altrimenti sul nodo genitore, restituisce un nuovo zipper)
Comportamento dello Zipper
Lo Zipper fornisce un modo funzionale per navigare un albero di Node.
Tutte le chiamate allo Zipper dovrebbero restituire un nuovo oggetto Zipper.
Se lo Zipper non cambia valori (cioè non è stato chiamato alcun metodo Set*), lo Zipper dovrebbe usare lo stesso albero sottostante.
Quando viene chiamato un metodo Set*, il nuovo Zipper dovrebbe avere un nuovo albero, lasciando invariato l'albero originale.
Le chiamate allo Zipper che spostano il focus su un Node non valido dovrebbero restituire un errore.
