Utasítások
Zipper készítése bináris fához.
A zipperek tisztán funkcionális módját kínálják annak, hogy egy adatszerkezetben navigáljunk és azt módosítsuk.
Lényegében egy adatszerkezetet és egy arra mutató pointert tartalmaznak (ezt nevezzük fókusznak).
Például egy rózsafa esetén (amelynek minden csomópontja egy értéket és a gyermekcsomópontok listáját tartalmazza) egy zipper a következő műveleteket támogathatja:
-
from_tree (zippert készít egy rózsafából, a fókusz a gyökércsomóponton van)
-
to_tree (kiveszi a rózsafát a zipperből)
-
value (visszaadja a fókuszcsomópont értékét)
-
prev (a fókuszt az ugyanazon szülő előző gyermekére mozgatja,
új zippert ad vissza)
-
next (a fókuszt az ugyanazon szülő következő gyermekére mozgatja, új
zippert ad vissza)
-
up (a fókuszt a szülőre mozgatja, új zippert ad vissza)
-
set_value (beállítja a fókuszcsomópont értékét, új zippert ad vissza)
-
insert_before (új részfát szúr be a fókuszcsomópont elé, ez lesz a
fókuszcsomópont prev-je, és új zippert ad vissza)
-
insert_after (új részfát szúr be a fókuszcsomópont után, ez lesz a
fókuszcsomópont next-je, és új zippert ad vissza)
-
delete (eltávolítja a fókuszcsomópontot és az összes részfáját; a fókusz a
next csomópontra kerül, ha lehetséges, egyébként a prev csomópontra, ha
lehetséges, egyébként a szülőcsomópontra, és új zippert ad vissza)
Ezt a feladatot sokféleképpen meg lehet oldani, de mi azoknak szabtuk, akik szeretnének gyakorlatot szerezni saját [képességkezelők][ability-handler-docs] írásában.
Írj egy Zipper képességet, amellyel bejárhatsz egy binárisfa adatszerkezetet.
Magát a Zipper képességet készen megkapod, de neked kell implementálnod a kezelőt, amely lehetővé teszi a bejárást az általunk kijelölt binárisfa adatszerkezeten.
Adott a következő binárisfa. Ha meghívnánk a Zipper.right, Zipper.right, Zipper.up, majd a Zipper.left műveletet, akkor az 5 értékű csomópontnál kellene állnunk.
1
/ \
2 4
/ / \
3 5 7
A feladat szempontjából, ha olyan bináris fán hívod meg a left vagy right műveletet, amely nem tartalmaz bal vagy jobb ágat, akkor visszaadhatod az aktuális csomópont értékét.
Elgondolkodtató kérdések
Milyen szempontból hasonlít maga a képességkezelő egy zipperre? Tekintheted egy függvény continuation-jét a programod következő „csomópontjára” mutató pointerként? Eltárolhatod a kezelődben a continuation korábbi hívásait, hogy visszajuthass egy korábbi állapotba?
Milyen más adatszerkezeteken haladhatsz végig így? Írhatnál egy Zippert JSON fölé, vagy egyet a HTML DOM fa fölé?
