نادي الشعر

المجموعة المنفصلة (بنية الاتحاد والبحث) تحفظ مجموعة من القيم مقسّمة إلى مجموعات غير متداخلة، وتجيب بسرعة عن سؤال واحد: هل هاتان القيمتان في المجموعة نفسها؟ وهي توجد في مفردات disjoint-sets.

بناء مجموعة منفصلة

<disjoint-set> يبني بنية فارغة. تُضاف القيم، وهي الذرات، بواسطة add-atom واحدة تلو الأخرى، أو بواسطة add-atoms من متتالية. وتبدأ كل ذرة في مجموعة خاصة بها.

<disjoint-set> ( -- disjoint-set )
add-atom       ( atom disjoint-set -- )
add-atoms      ( seq disjoint-set -- )

USING: disjoint-sets ;

<disjoint-set>
{ 1 2 3 } over add-atoms   ! 1, 2 and 3 each in their own group

المجموعة المنفصلة قابلة للتغيير: تُغيّرها add-atom وadd-atoms وequate في مكانها بدلًا من إرجاع مجموعة جديدة. وتكون keep مفيدة عندما تريد استعادة المجموعة المنفصلة إلى المكدس بعد أن تكون إحدى هذه الكلمات قد استهلكتها.

دمج المجموعات

equate يوحّد المجموعتين اللتين تحتويان على ذرّيها. والاتحاد عملية متعدية: اوحد ذرتين، ثم اوحد إحداهما مع ثالثة، فتنتقل الثلاث جميعًا إلى مجموعة واحدة.

equate ( atom1 atom2 disjoint-set -- )

الممثلون

لكل مجموعة عضو واحد معياري، هو ممثلها. تُرجع representative هذا الممثل، وتنتمي ذرتان إلى المجموعة نفسها إذا وفقط إذا تساوى ممثلاهما.

representative ( atom disjoint-set -- representative )

USING: disjoint-sets ;

<disjoint-set>
{ 1 2 3 } over add-atoms
1 2 pick equate
1 over representative .   ! => 1
2 over representative .   ! => 1   (same representative as 1)
3 over representative .   ! => 3   (still on its own)

اختيار المجموعة لذرة معينة كممثل لها تفصيل داخلي، فلا تعتمد أبدًا على اختيار ذرة بعينها، بل اعتمد فقط على اتفاق ذرتين في المجموعة نفسها.