Zipper

Οδηγίες

Δημιουργία ενός zipper για ένα δυαδικό δέντρο.

Τα Zippers είναι ένας καθαρά συναρτησιακός τρόπος να πλοηγείσαι μέσα σε μια δομή δεδομένων και να τη χειρίζεσαι. Περιέχουν ουσιαστικά μια δομή δεδομένων και έναν δείκτη μέσα σε αυτή τη δομή δεδομένων (που ονομάζεται εστίαση).

Για παράδειγμα, δεδομένου ενός rose tree (όπου κάθε κόμβος περιέχει μια τιμή και μια λίστα με παιδικούς κόμβους), ένα zipper μπορεί να υποστηρίζει τις εξής λειτουργίες:

• from_tree (παίρνει ένα zipper από ένα rose tree, η εστίαση είναι στον κόμβο ρίζας)
• to_tree (παίρνει το rose tree από το zipper)
• value (παίρνει την τιμή του κόμβου εστίασης)
• prev (μετακινεί την εστίαση στο προηγούμενο παιδί του ίδιου γονέα, επιστρέφει ένα νέο zipper)
• next (μετακινεί την εστίαση στο επόμενο παιδί του ίδιου γονέα, επιστρέφει ένα νέο zipper)
• up (μετακινεί την εστίαση στον γονέα, επιστρέφει ένα νέο zipper)
• set_value (ορίζει την τιμή του κόμβου εστίασης, επιστρέφει ένα νέο zipper)
• insert_before (εισάγει ένα νέο υποδέντρο πριν από τον κόμβο εστίασης, αυτό γίνεται το prev του κόμβου εστίασης, επιστρέφει ένα νέο zipper)
• insert_after (εισάγει ένα νέο υποδέντρο μετά από τον κόμβο εστίασης, αυτό γίνεται το next του κόμβου εστίασης, επιστρέφει ένα νέο zipper)
• delete (αφαιρεί τον κόμβο εστίασης και όλα τα υποδέντρα, η εστίαση μετακινείται στον κόμβο next αν είναι δυνατόν, αλλιώς στον κόμβο prev αν είναι δυνατόν, αλλιώς στον γονικό κόμβο, επιστρέφει ένα νέο zipper)

Υποδείξεις

Αυτή η άσκηση ασχολείται με την προσαρμοσμένη ισότητα. Για περισσότερες πληροφορίες, δες την υπερκάλυψη.