زیپ

دستورالعمل‌ها

ساختن یک zipper برای یک درخت دودویی.

Zippers روشی کاملاً تابعی برای پیمایش درون یک ساختار داده و دست‌کاری آن هستند. آن‌ها در اصل یک ساختار داده و یک اشاره‌گر به درون آن ساختار داده را در خود دارند (که به آن «کانون» می‌گویند).

برای نمونه، اگر یک درخت رز داشته باشیم (درختی که هر گره آن یک مقدار و فهرستی از گره‌های فرزند دارد)، یک zipper ممکن است از این عملیات پشتیبانی کند:

• from_tree (یک zipper از درخت رز بیرون می‌کشد، کانون روی گره‌ی ریشه است)
• to_tree (درخت رز را از zipper بیرون می‌کشد)
• value (مقدار گره‌ی کانون را می‌گیرد)
• prev (کانون را به فرزند قبلی همان والد منتقل می‌کند و یک zipper تازه برمی‌گرداند)
• next (کانون را به فرزند بعدی همان والد منتقل می‌کند و یک zipper تازه برمی‌گرداند)
• up (کانون را به والد منتقل می‌کند و یک zipper تازه برمی‌گرداند)
• set_value (مقدار گره‌ی کانون را تنظیم می‌کند و یک zipper تازه برمی‌گرداند)
• insert_before (یک زیردرخت تازه پیش از گره‌ی کانون درج می‌کند، این زیردرخت prev گره‌ی کانون می‌شود و یک zipper تازه برمی‌گرداند)
• insert_after (یک زیردرخت تازه پس از گره‌ی کانون درج می‌کند، این زیردرخت next گره‌ی کانون می‌شود و یک zipper تازه برمی‌گرداند)
• delete (گره‌ی کانون و همه‌ی زیردرخت‌ها را حذف می‌کند؛ کانون در صورت امکان به گره‌ی next، در غیر این صورت در صورت امکان به گره‌ی prev و در غیر این صورت به گره‌ی والد منتقل می‌شود و یک zipper تازه برمی‌گرداند)

رفتار Zipper

Zipper راهی تابعی برای پیمایش یک درخت Node فراهم می‌کند.

همه‌ی فراخوانی‌های Zipper باید یک شیء Zipper جدید برگردانند. اگر Zipper مقادیر را تغییر ندهد (یعنی هیچ متد Set* فراخوانی نشده باشد)، باید از همان درخت زیرین استفاده کند. وقتی یک متد Set* فراخوانی می‌شود، Zipper جدید باید درخت جدیدی داشته باشد، و درخت اصلی بدون تغییر بماند.

فراخوانی‌های Zipper که تمرکز را به یک Node نامعتبر تغییر می‌دهند باید یک خطا برگردانند.