জিপার

নির্দেশনা

বাইনারি ট্রির জন্য একটি জিপার তৈরি করা।

জিপার হলো কোনো ডেটা স্ট্রাকচারের ভেতরে ঘোরাঘুরি করা এবং সেটি পরিবর্তন করার একটি বিশুদ্ধ ফাংশনাল উপায়। এগুলো মূলত একটি ডেটা স্ট্রাকচার আর সেই ডেটা স্ট্রাকচারের ভেতরের একটি পয়েন্টার ধারণ করে (যাকে ফোকাস বলা হয়)।

উদাহরণস্বরূপ, একটি রোজ ট্রি দেওয়া হলে (যেখানে প্রতিটি নোডে একটি মান আর কিছু চাইল্ড নোডের অ্যারে থাকে) একটি জিপার এই অপারেশনগুলো সমর্থন করতে পারে:

• from_tree (একটি রোজ ট্রি থেকে একটি জিপার বের করে আনে, ফোকাস থাকে রুট নোডে)
• to_tree (জিপার থেকে রোজ ট্রিটি বের করে আনে)
• value (ফোকাস নোডের মান দেয়)
• prev (ফোকাসকে একই প্যারেন্টের আগের চাইল্ডে সরায়, নতুন একটি জিপার রিটার্ন করে)
• next (ফোকাসকে একই প্যারেন্টের পরের চাইল্ডে সরায়, নতুন একটি জিপার রিটার্ন করে)
• up (ফোকাসকে প্যারেন্টে সরায়, নতুন একটি জিপার রিটার্ন করে)
• set_value (ফোকাস নোডের মান সেট করে, নতুন একটি জিপার রিটার্ন করে)
• insert_before (ফোকাস নোডের আগে একটি নতুন সাবট্রি ঢোকায়, সেটি ফোকাস নোডের prev হয়ে যায়, নতুন একটি জিপার রিটার্ন করে)
• insert_after (ফোকাস নোডের পরে একটি নতুন সাবট্রি ঢোকায়, সেটি ফোকাস নোডের next হয়ে যায়, নতুন একটি জিপার রিটার্ন করে)
• delete (ফোকাস নোড ও তার সব সাবট্রি মুছে ফেলে, সম্ভব হলে ফোকাস চলে যায় next নোডে, নাহলে সম্ভব হলে prev নোডে, নাহলে প্যারেন্ট নোডে, এবং নতুন একটি জিপার রিটার্ন করে)