Zipper

Вказівки

Створення застібки для бінарного дерева.

Застібка - це чисто функціональний спосіб орієнтуватися в структурі даних і змінювати її. По суті, вона містить структуру даних і вказівник у цю структуру (який називають фокусом).

Наприклад, для трояндового дерева (де кожен вузол містить значення та масив дочірніх вузлів) застібка може підтримувати такі операції:

• from_tree (отримати застібку з трояндового дерева, фокус стоїть на кореневому вузлі)
• to_tree (отримати трояндове дерево із застібки)
• value (отримати значення вузла у фокусі)
• prev (перемістити фокус на попередній дочірній вузол того самого батьківського вузла, повертає нову застібку)
• next (перемістити фокус на наступний дочірній вузол того самого батьківського вузла, повертає нову застібку)
• up (перемістити фокус на батьківський вузол, повертає нову застібку)
• set_value (встановити значення вузла у фокусі, повертає нову застібку)
• insert_before (вставити нове піддерево перед вузлом у фокусі; воно стає prev вузла у фокусі, повертає нову застібку)
• insert_after (вставити нове піддерево після вузла у фокусі; воно стає next вузла у фокусі, повертає нову застібку)
• delete (видаляє вузол у фокусі та всі піддерева; фокус переходить на вузол next, якщо це можливо, інакше на вузол prev, якщо це можливо, інакше на батьківський вузол, повертає нову застібку)

Підказки

У цій вправі йдеться про власну рівність. Докладніше див. перевизначення.