Instructions
Créer un zipper pour un arbre binaire.
Les zippers offrent une façon purement fonctionnelle de naviguer à l'intérieur d'une structure de données et de la manipuler.
Ils contiennent essentiellement une structure de données et un pointeur dans cette structure de données (appelé le focus).
Par exemple, avec un rose tree (où chaque nœud contient une valeur et une liste de nœuds enfants), un zipper peut prendre en charge les opérations suivantes :
-
from_tree (obtenir un zipper à partir d'un rose tree, le focus étant sur le nœud racine)
-
to_tree (extraire le rose tree du zipper)
-
value (obtenir la valeur du nœud focus)
-
prev (déplacer le focus vers l'enfant précédent du même parent,
renvoie un nouveau zipper)
-
next (déplacer le focus vers l'enfant suivant du même parent, renvoie un
nouveau zipper)
-
up (déplacer le focus vers le parent, renvoie un nouveau zipper)
-
set_value (définir la valeur du nœud focus, renvoie un nouveau zipper)
-
insert_before (insérer un nouveau sous-arbre avant le nœud focus, il
devient le prev du nœud focus, renvoie un nouveau zipper)
-
insert_after (insérer un nouveau sous-arbre après le nœud focus, il devient
le next du nœud focus, renvoie un nouveau zipper)
-
delete (supprime le nœud focus et tous ses sous-arbres, le focus passe au
nœud next si possible, sinon au nœud prev si possible,
sinon au nœud parent, renvoie un nouveau zipper)
Comportement du Zipper
Le Zipper offre une façon fonctionnelle de naviguer dans un arbre de Node.
Tous les appels au Zipper doivent renvoyer un nouvel objet Zipper.
Si le Zipper ne change pas les valeurs (c'est-à-dire si aucune méthode Set* n'a été appelée), il doit réutiliser le même arbre sous-jacent.
Quand une méthode Set* est appelée, le nouveau Zipper doit utiliser un nouvel arbre, sans modifier l'arbre d'origine.
Les appels au Zipper qui déplacent le focus vers un Node invalide doivent renvoyer une erreur.
