Вказівки
Створення застібки для бінарного дерева.
Застібка - це чисто функціональний спосіб орієнтуватися в структурі даних і змінювати її.
По суті, вона містить структуру даних і вказівник у цю структуру (який називають фокусом).
Наприклад, для трояндового дерева (де кожен вузол містить значення та масив дочірніх вузлів) застібка може підтримувати такі операції:
-
from_tree (отримати застібку з трояндового дерева, фокус стоїть на кореневому вузлі)
-
to_tree (отримати трояндове дерево із застібки)
-
value (отримати значення вузла у фокусі)
-
prev (перемістити фокус на попередній дочірній вузол того самого батьківського вузла,
повертає нову застібку)
-
next (перемістити фокус на наступний дочірній вузол того самого батьківського вузла, повертає нову
застібку)
-
up (перемістити фокус на батьківський вузол, повертає нову застібку)
-
set_value (встановити значення вузла у фокусі, повертає нову застібку)
-
insert_before (вставити нове піддерево перед вузлом у фокусі; воно
стає prev вузла у фокусі, повертає нову застібку)
-
insert_after (вставити нове піддерево після вузла у фокусі; воно стає
next вузла у фокусі, повертає нову застібку)
-
delete (видаляє вузол у фокусі та всі піддерева; фокус переходить на
вузол next, якщо це можливо, інакше на вузол prev, якщо це можливо,
інакше на батьківський вузол, повертає нову застібку)
Поведінка Zipper
Zipper надає функціональний спосіб навігації деревом Node.
Усі виклики Zipper мають повертати новий обʼєкт Zipper.
Якщо Zipper не змінює значень (тобто жодного методу Set* не було викликано), він має використовувати те саме дерево, яке лежить в його основі.
Коли викликається метод Set*, новий Zipper має отримати нове дерево, а початкове дерево залишається незмінним.
Виклики Zipper, які змінюють фокус на недійсний Node, мають повертати помилку.
