دفتر سجل الفنار

مجموعات التجزئة مجموعات قابلة للتغيير وغير مرتبة، تخزّن كل قيمة مرة واحدة على الأكثر. عمليات البحث والإدراج والحذف كلها O(1) في المتوسط. وهي تسكن في hash-sets وتُطبّق بروتوكول sets.

القيم الحرفية لمجموعة التجزئة

HS{ "NS-1024" "WB-203" } .
! => HS{ "NS-1024" "WB-203" }

HS{ } هي القيمة الحرفية الفارغة. ومثل بقية القيم الحرفية في Factor، فهي كائن مشترك، فكل إشارة إلى HS{ } في الكود المصدري تشير إلى المجموعة نفسها. أما HS{ } clone فتمنحك نسخة جديدة مستقلة عند كل استدعاء.

من متتالية

>hash-set ( seq -- set )    ! build a fresh set from a sequence

عندما تكون القيم لديك في متتالية بالفعل، فإن >hash-set تحوّلها في خطوة واحدة، مع تجاهل أي قيم مكررة.

USING: hash-sets prettyprint ;

{ "NS-1024" "WB-203" "NS-1024" } >hash-set .
! => HS{ "NS-1024" "WB-203" }

الإضافة والحذف

adjoin     ( elt set -- )    ! insert in place; no-op if already present
adjoin-all ( seq set -- )    ! insert every element of seq in place
delete     ( elt set -- )    ! remove in place; no-op if absent

العمليات الثلاث كلها تُعدّل المجموعة في مكانها؛ ولا واحدة منها تُرجع أي شيء على المكدّس.

USING: hash-sets kernel sets ;

HS{ } clone
"NS-1024" over adjoin
"WB-203"  over adjoin
"NS-1024" over adjoin    ! duplicate — no effect
.                        ! => HS{ "NS-1024" "WB-203" }

adjoin-all هي الصيغة الجماعية: فهي تضيف كل عنصر من عناصر المتتالية، متجاهلةً القيم المكررة تمامًا كما يفعل adjoin مع عنصر واحد في كل مرة.

USING: hash-sets kernel sets ;

HS{ "NS-1024" } clone
{ "WB-203" "NS-1024" "QR-7" } over adjoin-all
.                        ! => HS{ "QR-7" "NS-1024" "WB-203" }  (order not guaranteed)

السؤال عن المجموعة

in?         ( elt set -- ? )   ! is elt in the set?
null?       ( set -- ? )       ! is the set empty?
cardinality ( set -- n )       ! number of elements
members     ( set -- seq )     ! enumerate as a sequence

in? اختبار العضوية في بروتوكول المجموعات. وهي تختلف عن member? (من sequences)، التي تُجري مسحًا خطيًا على متتالية. أما في مجموعة التجزئة، فإن in? بحث في جدول التجزئة، أي O(1) في المتوسط، وهو الغرض كله من استخدام مجموعة تجزئة.

null? تُبلّغك ما إذا كانت المجموعة بلا عناصر، وهي الطريقة المباشرة للسؤال «هل هذه فارغة؟» بدل مقارنة cardinality بالصفر.

: my-log ( -- set ) HS{ "NS-1024" "WB-203" } ;

"NS-1024" my-log in? .   ! => t
"X-99"    my-log in? .   ! => f
my-log null? .           ! => f
HS{ } clone null? .      ! => t
my-log cardinality .     ! => 2

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

union     ( set1 set2 -- set )
intersect ( set1 set2 -- set )
diff      ( set1 set2 -- set )
set-like  ( set exemplar -- set' )

union تعني «كل العناصر من أيٍّ من المجموعتين»؛ وintersect تعني «العناصر الموجودة في كلتيهما»؛ وdiff تعني «العناصر الموجودة في set1 وليس في set2». وكل واحدة منها تُرجع مجموعة جديدة دون تعديل مدخلاتها.

set-like تحوّل set إلى نوع exemplar. والتطبيقات الافتراضية لـ union/intersect/diff تستخدمها لجعل النتيجة تطابق نوع المستقبِل، إذ تُرجع <my-set> <hash-set> union قيمة my-set وليس مجموعة تجزئة.

لماذا يهمّ هذا

تتناغم مجموعات التجزئة طبيعيًا مع جداول التجزئة في اجتياز الرسوم البيانية: فجدول التجزئة يربط كل عقدة بالعقد المجاورة لها، وتسجّل مجموعة التجزئة العقد التي سبق زيارتها حتى لا يكرّر البحث العمل ولا يدور في حلقة. ويصبح الاجتياز بعد ذلك طابورًا مع البنيتين، تُعدَّلان في مكانهما بينما تكتسح نحو الخارج.