Zipper

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)

Indices

Cet exercice traite de l'égalité personnalisée. Pour plus d'informations, consulte la redéfinition.