বাতিঘরের লগবুক

হ্যাশ-সেটগুলি মিউটেবল, আনঅর্ডারড কালেকশন, যা প্রতিটি মান সর্বাধিক একবার সংরক্ষণ করে। লুকআপ, ইনসার্ট ও ডিলিট সবই গড়ে 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 থেকে) থেকে আলাদা, কারণ member? একটি সিকোয়েন্সের উপরে লিনিয়ার স্ক্যান করে। একটি হ্যাশ-সেটের জন্য 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 রিটার্ন করে, হ্যাশ-সেট নয়।

কেন এটি গুরুত্বপূর্ণ

হ্যাশ-সেটগুলি গ্রাফ ট্রাভার্সালের জন্য হ্যাশটেবলগুলির সাথে স্বাভাবিকভাবে জোড়া লাগে: একটি হ্যাশটেবল প্রতিটি নোডকে তার প্রতিবেশীদের সাথে ম্যাপ করে, আর একটি হ্যাশ-সেট রেকর্ড করে কোন নোডগুলি ইতিমধ্যে ভিজিট করা হয়েছে, যাতে সার্চটি লুপ না করে বা একই কাজ পুনরাবৃত্তি না করে। এরপর ট্রাভার্সালটি একটি কিউ এবং ওই দুটি স্ট্রাকচার নিয়ে গঠিত, যা আপনি বাইরের দিকে এগোতে এগোতে ইন-প্লেস মিউটেট করেন।