باشگاه شعر

«مجموعه‌ی ناهم‌پوشان» (ساختار یکی‌کردن و یافتن) مجموعه‌ای از مقدارها را نگه می‌دارد که به گروه‌های بدون هم‌پوشانی تقسیم شده‌اند و به‌سرعت به یک پرسش پاسخ می‌دهد: آیا این دو مقدار در یک گروه قرار دارند؟ این ساختار در واژگان 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 یکی کنید، سپس یکی از آن دو را با اتم سومی، و هر سه در یک گروه قرار می‌گیرند.

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)

اینکه یک گروه کدام اتم را به‌عنوان نماینده‌اش برمی‌گزیند، یک جزئیات درونی است؛ هرگز به برگزیده شدن اتمی خاص تکیه نکنید، و تنها به این تکیه کنید که نماینده‌ی دو اتم در یک گروه یکسان باشد.