מבוא לאוספים ב-Squeak: עץ הירושה, פרוטוקולי Collection ו-8 המאפיינים הפונקציונליים
איך מעל 90 מחלקות אוספים שונות בסמולטוק מתאחדות תחת מחלקת-העל המופשטת Collection, אילו פרוטוקולים משותפים מעניקים לנו שפה אחידה לכל אוסף, ואיך מסווגים אוספים לפי 8 תכונות התנהגותיות.
מודל מנטלי ועיקרון מנחה: שפה פולימורפית אחת מעל עשרות מבני נתונים שונים!
דמיין מערכת מכולות חכמה שבה ארגז ממוספר (Array), שק ללא סדר שמכיל כפילויות (Bag), כספת שמונעת כפילויות (Set) וארון עם תוויות שמות (Dictionary) — כולם מבינים בדיוק את אותן פקודות בסיסיות כמו size, includes:, add: ו-do:!
כל מחלקות האוספים יורשות ממחלקת-העל המופשטת Collection (שיורשת מ-Object). ההודעות המשותפות מוגדרות ב-Collection, והן משוכתבות, נדרסות ומותאמות בכל תת-מחלקה לפי אופי המימוש שלה.
בניגוד לשפות C ו-Java שבהן האינדקס מתחיל מ-0, בסמולטוק האינדקס הראשון באוספים אינדקסיאליים הוא תמיד 1! וכל אוסף ניתן להמרה קלה לאוסף אחר באמצעות פרוטוקול ההסבה (asSet, asArray, asOrderedCollection).
1. סעיף 12.1: מבוא ועץ היררכיית האוספים ב-Squeak
מעל 90 מחלקות אוספים המאורגנות תחת עץ ירושה אחיד ושלושה ענפים ראשיים
אנחנו צוללים עכשיו אל אחת מספריות התוכנה המרכזיות, החזקות והעשירות ביותר בשפת Smalltalk ובסביבת Squeak: ספריית האוספים (Collections). הספרייה הזו מונה מעל 90 מחלקות אוספים שונות, המספקות מענה שלם לניהול, אחסון ומניפולציה של קבוצות עצמים במבני נתונים מגוונים.
הקסם הארכיטקטוני של הספרייה הזו טמון בכך שכלל המחלקות בהיררכיה יורשות ממחלקת-העל המופשטת Collection (שיורשת בעצמה מ-Object). מתחת ל-Collection מתפצל העץ לשלושה ענפים מרכזיים שמגדירים את אופי הארגון של האיברים:
📏 1. ענף SequenceableCollection
מחלקה מופשטת המאגדת את כל האוספים שבהם לאיברים קיים סדר מוגדר היטב (מהאיבר הראשון ועד לאחרון). תחתיה נמצא את:
• LinkedList (רשימה מקושרת)
• Interval (סדרה חשבונית)
• OrderedCollection (אוסף דינמי סדור) ותת-מחלקתו SortedCollection (אוסף ממוין לפי תכונה)
• ArrayedCollection (מופשטת) שממנה יורשות Array (מערך בגודל קבוע), String (מופשטת, שממנה יורשות ByteString מחרוזת רגילה ו-Symbol סימבול ייחודי) ו-Text (מחרוזת מעוצבת).
🔑 2. ענף Set (קבוצה)
מאגד אוספים מבוססי טבלאות גיבוב שבהם אין חשיבות לסדר ההכנסה, והם מנפים כפילויות באופן אוטומטי. תחת Set נמצא את:
• Dictionary (מילון מפתח-ערך), וממנו יורשים IdentityDictionary (השוואת מפתחות לפי זהות ==) ו-PluggableDictionary.
• PluggableSet.
🛍️ 3. ענף Bag (שקיק)
מאגד אוספים בלתי סדורים (ללא סדר פנימי בין האיברים), אשר בניגוד ל-Set מאפשרים שמירה של איברים כפולים ומתמחים בספירת מספר המופעים של כל איבר באוסף.
מחלקות מופשטות (ממוסגרות בקו מרוסק) ומחלקות קונקרטיות תחת Object → Collection
2. סעיף 12.2 (חלק א'): הפרוטוקולים המשותפים של מחלקת-העל Collection
גישה, בדיקה, הוספה והסרה, הסבה, אנומרציה ויצירה (מתודות מחלקה)
רוב המחלקות בהיררכיה שלנו תומכות במגוון עשיר של הודעות משותפות המוגדרות כבר במחלקת-העל Collection. הודעות אלו משוכתבות, נדרסות ומותאמות בכל תת-מחלקה לפי אופי המימוש שלה, והן מחולקות לפרוטוקולים לוגיים ברורים:
📍 1. פרוטוקול גישה (Accessing)
- •
size: מחזירה את מספר האיברים המאוחסנים בפועל באוסף. - •
capacity: מחזירה את הקיבולת הפוטנציאלית המוקצית של האוסף (במרבית האוספים הדינמיים הקיבולת גדלה אוטומטית לפי הצורך). - •
at:: מקבלת אינדקס ומחזירה את האיבר הממוקם בו. - •
at:put:: מקבלת אינדקס ואיבר ומציבה את האיבר באינדקס המבוקש.
🔍 2. פרוטוקול בדיקה (Testing)
- •
isEmpty: מחזירהtrueאם האוסף ריק. - •
includes:: בודקת האם איבר מסוים קיים באוסף (לפי שוויון ערכי=). - •
contains:: מקבלת בלוק ומחזירהtrueאם קיים באוסף איבר שעבורו הבלוק מחזירtrue. - •
occurrencesOf:: מקבלת עצם ומחזירה את מספר המופעים שלו באוסף (האיברים השווים לו).
➕ 3. הוספה והסרה (Adding & Removing)
- •
add:/addAll:: הוספת איבר בודד או הוספת כל איבריו של אוסף אחר לאוסף הנוכחי. - •
remove:: הסרת איבר קיים מהאוסף (אם אינו קיים – מתעורר מצב חריג!). - •
remove:ifAbsent:: הסרת עצם, ואם אינו קיים מוערך בלוק הגיבוי וערכו מוחזר. - •
removeAll:: מקבלת אוסף ומסירה את איבריו (או ניקוי האוסף; חריג אם לא כל האיברים קיימים).
🔄 4. פרוטוקול הסבה (Converting)
- •
asArray: הסבת האוסף המקבל למערך חדש (Array). - •
asOrderedCollection: הסבה לאוסף דינמי סדור לפי סדר האיברים. - •
asSortedCollection: הסבה לאוסף ממוין לפי יחס הסדר הטבעי (<=). - •
asSortedCollection: aBlock: הסבה לאוסף ממוין לפי קריטריון מותאם בבלוק השוואה דו-פרמטרי. - •
asSet/asBag: הסבה לקבוצה (ללא חזרות) או לאוסף שקיק (Bag).
🏗️ 5. פרוטוקול יצירה – מתודות מחלקה
- •
new: יצירת אוסף ריק מסוג המקבל (למשלSet new). - •
new: anInteger: יצירת אוסף בגודל מבוקש שאיבריו מאותחלים ב-nil(למשלArray new: 10) או הקצאת קיבולת התחלתית. - •
with:/with:with:/with:with:with:/with:with:with:with:: יצירת אוסף חדש המכיל מראש 1 עד 4 איברים שהועברו כארגומנטים. - •
withAll: aCollection: יצירת אוסף חדש המאותחל עם כל איברי האוסף שהועבר כפרמטר.
🔁 6. פרוטוקול אנומרציה (Enumerating)
- •
do:: הערכת בלוק עבור כל איבר באוסף. - •
collect:: החזרת אוסף חדש מהערכים שחזרו מהערכת הבלוק. - •
select:/reject:: בחירת איברים שעבורם הבלוק החזירtrueאוfalse. - •
detect:/detect:ifNone:: איתור האיבר הראשון שמקיים תנאי. - •
inject:into:: צבירת ערך מצטבר על פני כל איברי האוסף (נחקור לעומק בלשונית 12.5!).
3. סעיף 12.2 (חלק ב'): סיווג האוספים לפי 8 מאפיינים פונקציונליים
איך לבחור את האוסף המדויק לכל משימה הנדסית על פי 8 צירים התנהגותיים?
למרות שרוב האוספים מבינים את הפרוטוקולים המשותפים של Collection, הם נבדלים זה מזה בשמונה מאפיינים פונקציונליים המגדירים את ההתנהגות והמבנה שלהם:
מופעים של תת-מחלקות SequenceableCollection מחזיקים איברים המסודרים בסדר רציף מוגדר (מהראשון לאחרון) ותומכים במתודות הגישה לקצוות first ו-last.
מופעים של SortedCollection שומרים את איבריהם ממוינים באופן רציף לפי תכונה מסוימת (כברירת מחדל לפי <=, או באמצעות בלוק השוואה ייעודי sortBlock).
מרבית האוספים הסדורים מאפשרים גישה ישירה לאיברים באמצעות אינדקס מספרי שלם דרך at: ו-at:put: (כמו Array, OrderedCollection, String). זכור: בסמולטוק האינדקס הראשון הוא תמיד 1!
מופעים של Dictionary ותת-מחלקותיו מאפשרים גישה לאיברים באמצעות מפתחות מותאמים (מכל טיפוס עצם) במקום אינדקסים מספריים.
מרבית האוספים ניתנים לשינוי ועריכה לאורך חייהם באמצעות at:put: (Mutable). לעומתם, Interval ו-Symbol הם בלתי ניתנים לשינוי (Immutable) מרגע יצירתם (למשל 10 to: 15 תומך ב-at: אך שליחת at:put: מעוררת שגיאה!).
מופעים של Array ו-Interval נוצרים בגודל קבוע ואינם יכולים להתרחב. לעומתם, OrderedCollection, Set ו-Bag גדלים דינמית לפי הצורך ותומכים ב-add:, addFirst:, addLast: ו-insert:before:.
אוספים מסוג Set ו-Dictionary מנפים כפילויות ואינם מאפשרים שמירת איברים או מפתחות זהים פעמיים. לעומתם, Array, OrderedCollection ו-Bag מקבלים ומאחסנים איברים כפולים.
הטרוגניים (Array, OrderedCollection, Set, Bag) מאחסנים עצמים מטיפוסים שונים יחד. הומוגניים מוגבלים לטיפוס יחיד: String ו-Symbol לתווים (Character), ByteArray לבתים שלמים (0–255), IntegerArray לשלמים ו-FloatArray לממשיים.
מיני-סימולציה 12.1: סייר הפרוטוקולים של מחלקת-העל Collection
מעבדת הסיווג הפונקציונלי: בחן כל מחלקת אוסף מול 8 המאפיינים!
בחר מחלקת אוסף מתוך ההיררכיה וראה מיד את תעודת הזהות המלאה שלה לאורך כל 8 המאפיינים הפונקציונליים, כולל אילו הודעות מותר או אסור לשלוח לה:
הגשר הנרטיבי: הבנו מה האוספים יודעים לעשות מבחוץ – אבל איך הם בנויים ומיוצגים פיזית בזיכרון?
ראינו ש-Array הוא בגודל קבוע ואילו OrderedCollection גדל דינמית, ש-Set מנפה כפילויות וש-Interval מייצג סדרה שלמה של מספרים בלי שאפשר לשנותו.
אבל איך הקסם הזה עובד מתחת למכסה המנוע בזיכרון של Squeak? איך Interval של מיליון מספרים תופס רק 3 מספרים שלמים בזיכרון? ואיך Bag בנוי בעצם מעל Dictionary? בוא נעבור ליחידה 12.3 ונגלה!
מימושים של אוספים: כיצד האוספים מיוצגים ופועלים בזיכרון?
חמש הטכניקות הפיזיות שבהן סמולטוק מממשת אוספים בזיכרון: מימושי מערך, מימושים סדורים דינמיים, מימושי גיבוב (Hash) כולל המימוש החכם של Bag מעל Dictionary, רשימות מקושרות וייצוג אינטרוולים בשלושה שלמים בלבד.
מודל מנטלי ועיקרון מנחה: המבנה הפיזי בזיכרון קובע את היכולות והמגבלות של האוסף!
Array הוא כמו תבנית ביצים קשיחה שגודלה נקבע במפעל. לעומתו, OrderedCollection הוא מנהל חכם שמחזיק תבנית ביצים פנימית — וברגע שהיא מתמלאת, הוא קונה בשקט תבנית גדולה יותר ומעביר אליה את הביצים בלי שתרגיש!
אוספים מבוססי גיבוב (Set ו-Dictionary) נשענים תמיד על המתודות = ו-hash לאיתור איברים ולמניעת כפילויות, ואילו Bag ממומש בפועל מעל Dictionary (איבר ← מונה מופעים).
המחלקה Interval אינה שומרת פיזית את כל איבריה בזיכרון! היא ממומשת באמצעות שלושה מספרים שלמים בלבד במשתני מופע: התחלה (start), סיום (stop) וגודל פסיעה (step).
1. חמשת סוגי המימושים של אוספים בזיכרון
מדוע חשוב להבין איך כל אוסף שומר את הנתונים שלו מאחורי הקלעים?
כשאנחנו שולחים הודעה כמו add: או includes: לאוסף, הקוד שלנו נהנה מהפשטה מלאה — אנחנו לא צריכים לדעת איך האוסף בנוי מבפנים כדי להשתמש בו. אבל כדי לבחור את האוסף הנכון ולהבין למה Array אינו יכול לגדול בעוד ש-OrderedCollection מתרחב בקלות, אנחנו חייבים להכיר את חמשת המימושים הפיזיים של האוספים בזיכרון של Smalltalk:
שמירה ישירה במשתני המופע של העצם
במחלקות כמו Array ו-ByteArray, הנתונים נשמרים ישירות במשתנה המופע האינדקסיאלי של עצם האוסף עצמו, והזיכרון מוקצה במלואו כבלוק רציף בעת היצירה. לכן גודל האוסף קבוע מרגע יצירתו ואינו ניתן לשינוי.
מערך פנימי מוחזק במשתנה מופע
מחלקות כמו OrderedCollection ו-SortedCollection אינן שומרות את האיברים ישירות בגוף העצם, אלא מאחסנות אותם בתוך מערך פנימי המוחזק באחד ממשתני המופע של האוסף. כאשר המערך הפנימי מתמלא, האוסף מקצה אוטומטית מערך חדש וגדול יותר, מעתיק אליו את הנתונים, ומעדכן את המצביע הפנימי באופן שקוף לחלוטין למשתמש!
טבלת גיבוב ב-Set וב-Dictionary, ומימוש Bag
אוספים מסוג Set ו-Dictionary משתמשים גם הם במערך פנימי מוצבע (בדומה למימושים הסדורים), אך מתפעלים אותו כטבלת גיבוב (Hash Table) ונשענים על המתודות = ו-hash לאיתור, הוספה ומניעת כפילויות.
ומה לגבי Bag? האוסף Bag ממומש באלגנטיות מעל Dictionary: האיברים עצמם משמשים כמפתחות (או אלמנטים מזוגות מפתח-ערך), והערכים הצמודים להם מייצגים את מונה מספר המופעים של כל איבר!
שרשרת חוליות המצביעות זו לזו
המחלקה LinkedList מיישמת רשימה מקושרת סטנדרטית קלאסית, שבה כל עצם חוליה ברשימה מחזיק מצביע לחוליה הבאה ברצף.
ייצוג סדרה חשבונית שלמה באמצעות 3 מספרים שלמים בלבד!
המחלקה Interval מייצגת סדרה חשבונית מבלי לשמור פיזית את כל איבריה בזיכרון! היא ממומשת באמצעות שלושה מספרים שלמים בלבד המאוחסנים במשתני מופע ומייצגים את קצות הערכים וההפרש ביניהם: נקודת ההתחלה (start), נקודת הסיום (stop), וגודל הפסיעה (step).
לדוגמה: האינטרוול 1 to: 10 by: 2 (המייצג לוגית את הסדרה 1, 3, 5, 7, 9) מיוצג במלואו בזיכרון על ידי שלושת המספרים: 1, 10 ו-2!
השוואה ויזואלית: איך נראים חמשת המימושים של אוספי Smalltalk בתוך הזיכרון?
מיני-סימולציה 12.2: מחשבון הזיכרון של Interval מול Array
מעבדת הזיכרון החיה: גדילת המערך הפנימי ב-OrderedCollection ומימוש Bag מעל Dictionary
📈 ניסוי א': המערך הפנימי של OrderedCollection
size: 2 | capacity: 4
הוסף איברים וצפה כיצד ברגע שהמערך הפנימי מתמלא, האוסף מקצה אוטומטית מערך פנימי חדש וגדול יותר ומעתיק אליו את הנתונים:
🛍️ ניסוי ב': איך Bag ממומש מעל Dictionary?
bag size: 0
הוסף איברים כפולים אל ה-Bag וראה איך במילון הפנימי שלו האיבר נשמר פעם אחת בלבד ומונה המופעים שלו גדל ב-1:
הגשר הנרטיבי: אחרי שהצצנו אל מאחורי הקלעים של הזיכרון – בוא נכיר לעומק את 7 מחלקות האוספים העיקריות!
עכשיו, כשברור לנו איך כל משפחת אוספים מיוצגת בזיכרון, אנחנו מוכנים לצלול אל הקוד המעשי של שבע המחלקות החשובות והנפוצות ביותר ב-Squeak (סעיף 12.4): Array (ומלכודת המערך הליטרלי #(1+2) מול הדינמי {1+2}!), OrderedCollection, Interval, Dictionary (וההבחנה המכרעת מול IdentityDictionary!), Set, SortedCollection (עם sortBlock:) ו-String!
מחלקות עיקריות: Array, OrderedCollection, Interval, Dictionary, Set, SortedCollection ו-String
פירוט מעמיק של כל מתודות היצירה, הגישה והמניפולציה בשבע המחלקות הנפוצות ביותר, כולל ההבדל בין #(1+2) ל-{1+2}, ההבחנה בין Dictionary ל-IdentityDictionary, ומיון מלבנים עם sortBlock:.
מודל מנטלי ועיקרון מנחה: הבחנות הזהב של מחלקות הליבה ב-Smalltalk
#(...) מול דינמי {...}
מערך ליטרלי #(...) נבנה בזמן הידור ואינו מעריך ביטויים: #(1+2) יוצר מערך בן 3 איברים #(1 #+ 2)! מערך דינמי {...} מוערך בזמן ריצה (איבריו מופרדים בנקודות): {1+2} מחשב ומחזיר איבר יחיד #(3)!
Dictionary מול IdentityDictionary
Dictionary משווה מפתחות לפי שוויון ערכי (=) ו-hash. לעומתו, IdentityDictionary משווה מפתחות לפי זהות פרימיטיבית (==) — ולכן הוא אידיאלי ומהיר למפתחות שהם סימבולים (#)!
Set אינו תומך ב-at:!
בקבוצה (Set) אין סדר פנימי ולכן לא ניתן לשלוף איברים באמצעות אינדקס (at:)! מנגד, ב-SortedCollection האיברים נשמרים ממוינים תמיד (לפי <= או לפי בלוק דו-פרמטרי sortBlock:).
1. Array (מערך)
סדור · גודל קבוע · אינדקס ראשון הוא 1! · הטרוגני
מערך הוא אוסף סדור של איברים בגודל קבוע מראש שניתן לגשת אליהם על פי אינדקס.
כלל קריטי: בניגוד לשפות כגון C או Java שבהן האינדקס מתחיל מ-0, בסמולטוק האינדקס הראשון של מערך הוא תמיד 1!
איברי המערך יכולים להיות עצמים מטיפוסים שונים ומגוונים (אוסף הטרוגני), וגישה ועדכון מתבצעים באמצעות at: ו-at:put:.
אנחנו יכולים ליצור מערך בשלוש דרכים שונות שחשוב מאוד להבחין ביניהן:
• Array new: 5 ← יוצר מערך בן 5 איברים המאותחלים ב-nil: #(nil nil nil nil nil).
• Array with: 1 with: 2 with: 3 ← יוצר מערך בגודל 3 עם הערכים הנתונים.
• Array with: 1 with: 2/3 with: 'xxx' ← מדגים מערך הטרוגני עם טיפוסים מעורבים.
#(...) (זמן הידור):
נוצר בזמן הידור מליטרלים קבועים שערכם ידוע מראש (מספרים, תווים, מחרוזות, בוליאנים וסימבולים) המופרדים ברווחים. אינו מעריך ביטויים! לכן הביטוי #(1+2) אינו מחשב חיבור, אלא יוצר מערך בן 3 איברים: המספר 1, הסימבול #+, והמספר 2!
{...} (זמן ריצה):
מוערך בזמן ריצה, ואיבריו מופרדים בנקודות (.). הביטוי {1+2} מעריך את החיבור ומחזיר מערך בן איבר יחיד: #(3)!
2. OrderedCollection (אוסף דינמי סדור)
סדור · גדל וקטן דינמית · שומר סדר הכנסה · מקבל כפילויות
OrderedCollection הוא אוסף כללי וגמיש הרבה יותר ממערך: הוא שומר על סדר הכנסת האיברים ומסוגל לגדול ולקטון דינמית לפי הצורך בזמן ריצה.
המתודות המרכזיות שלו:
add: (הוספת איבר בסוף האוסף), addFirst: (הוספת איבר בראש האוסף), addLast: (הוספת איבר בסוף האוסף), insert:before: (הוספת איבר לפני איבר נתון), at: ו-at:put: (שליפה והצבה לפי אינדקס מספרי), remove: (הסרת המופע הראשון של האיבר המבוקש; אם אינו נמצא באוסף – מתעורר מצב חריג!), remove:ifAbsent: (הסרת איבר בליווי בלוק חלופי שמופעל וערכו מוחזר אם האיבר אינו קיים), ו-asOrderedCollection (הסבת אוסף קיים ל-OrderedCollection).
3. Interval (תחום ערכים / סדרה חשבונית)
סדור · Immutable (בלתי ניתן לשינוי) · Fixed size · 3 משתנים בלבד
המחלקה Interval מייצגת סדרה חשבונית סדורה של מספרים. זהו אוסף בלתי ניתן לשינוי (Immutable) ובגודל קבוע (Fixed size), המיוצג בזיכרון באמצעות שלושה משתנים בלבד: התחלה (start), סיום (stop) וגודל פסיעה (step). ניתן ליצור אותו בשתי דרכים: באמצעות מתודות המחלקה from:to: ו-from:to:by:, או באמצעות שליחת ההודעות to: ו-to:by: ישירות לעצמים מסוג Number (כולל שברים!):
4. Dictionary (מילון) ו-IdentityDictionary
ממופה לפי מפתח (Keyed) · זוגות Association · מנפה מפתחות כפולים
מילון הוא אוסף של זוגות מפתח-ערך מסוג Association (הנכתבים כ-key->value). הגישה לערכים נעשית באמצעות מפתחות מותאמים ולא באמצעות אינדקסים מספריים.
מתודות הגישה והעדכון במילון:
at: aKey put: aValue (הוספת זוג מפתח-ערך; אם המפתח קיים – ערכו מתעדכן!), at: aKey (שליפת ערך לפי מפתח; אם חסר – מתעורר חריג!), at: aKey ifAbsent: aBlock (שליפת ערך עם בלוק ברירת מחדל אם המפתח חסר), removeKey: aKey (הסרת הזוג מפתח-וערך לפי המפתח), keys (מחזירה את אוסף כל המפתחות כקבוצה מסוג Set!), values (מחזירה מערך מסוג Array של כל הערכים ללא המפתחות), ו-associations (מחזירה מערך של כל זוגות האסוציאציה key->value).
Dictionary לעומת IdentityDictionary
• Dictionary משווה בין מפתחות באמצעות בדיקת שוויון ערכי (האופרטור =) ובאמצעות המתודה hash (שני מפתחות שווים אם = מחזיר true ו-hash מחזיר אותו ערך).
• IdentityDictionary משווה בין מפתחות אך ורק באמצעות בדיקת זהות פרימיטיבית (האופרטור == — האם הם בפועל אותו העצם בזיכרון).
• הכלל התכנותי: כאשר המפתחות הם סימבולים (#), מומלץ להשתמש ב-IdentityDictionary מפני שסימבולים הם ייחודיים במערכת ובדיקת == מהירה בהרבה; כאשר המפתחות הם עצמים אחרים (כגון מחרוזות רגילות String), חובה להשתמש ב-Dictionary רגיל!
5. Set (קבוצה)
ללא כפילויות · ללא סדר פנימי · אינו תומך ב-at:!
קבוצה היא אוסף איברים ללא כפילויות וללא סדר פנימי. מניעת הכפילויות נשענת על טבלת גיבוב ועל המתודות = ו-hash (לכן 3 ו-9/3 נחשבים לאותו איבר!).
הקבוצה תומכת בפעולות תורת הקבוצות: union: (איחוד שתי קבוצות – מחזיר קבוצה חדשה ואינו משנה את המקבל), intersection: (חיתוך בין שתי קבוצות), includes: (בדיקת שייכות), ומתודת ההסבה asSet המנפה אוטומטית כפילויות מכל אוסף.
מגבלה קריטית: לא ניתן לשלוף איברים מתוך Set באמצעות אינדקס (at:)!
6. SortedCollection (אוסף ממוין)
ממוין ברציפות · ברירת מחדל <= · מותאם אישית עם sortBlock:
SortedCollection הוא אוסף סדור השומר את איבריו ממוינים ברציפות בכל עת.
כברירת מחדל, המיון מתבצע באמצעות שליחת הודעת ההשוואה <= בין איברי האוסף (מתודה המוגדרת במחלקות כמו Magnitude, Number, String ו-Point).
כאשר אנחנו רוצים למיין עצמים שאינם תומכים ב-<= (כמו Rectangle) או למיין לפי קריטריון מותאם אישית (למשל לפי שטח המלבן או בסדר יורד), אנו מעבירים בלוק השוואה בעל שני פרמטרים באמצעות sortBlock: (או מסבים אוסף קיים עם asSortedCollection / asSortedCollection: aBlock):
7. String (מחרוזת)
אוסף סדור והומוגני של תווים (Character) · שרשור עם פסיק (,)
מחרוזת ב-Smalltalk היא אוסף סדור והומוגני של תווים (Character, המסומנים עם $ כמו $H).
ניתן ליצור מחרוזת כליטרל בין גרשיים בודדים 'Hello', או באמצעות מתודות מחלקה: String with: $H with: $i או String newFrom: #($w $o $r $l $d).
מתודות ייחודיות למחרוזות: אופרטור הפסיק (,) לשרשור מחרוזות, at: ו-at:put: לשליפה ועדכון תו באינדקס, replaceAll:with: (החלפת כל המופעים של תו בתו אחר במקום), replaceFrom:to:with: (החלפת טווח תווים), copyReplaceAll:with: (יצירת עותק חדש של המחרוזת והחלפת כל המופעים של תת-מחרוזת אחת באחרת), findString: (החזרת אינדקס הופעת תת-מחרוזת), asUppercase ו-asNumber:
מערך ליטרלי מול דינמי, מילון מול מילון-זהות, ומיון מלבנים ב-SortedCollection
מיני-סימולציה 12.3: מפענח מערכים ב-Smalltalk – ליטרלי #(...) מול דינמי {...}
מעבדת המחלקות העיקריות: הרץ והשווה פעולות על OrderedCollection, Set, Dictionary ו-SortedCollection
הגשר הנרטיבי: הכרנו את מחלקות האוספים – עכשיו איך אנחנו סורקים ומעבדים אותן בלי מילת מפתח של לולאת for?
בשפת Smalltalk אין תחביר מיוחד ללולאות כמו for או while על אוספים. במקום זאת, כל הסריקה, הסינון, הטרנספורמציה והצבירה מתבצעים על ידי שליחת הודעות איטרציה לאוסף עצמו שמקבלות בלוק כארגומנט!
ביחידה הבאה (12.5) נפתח יחד את המכסה של do:, collect: (ונכיר את הסוד של self species new!), select:, reject:, detect: ו-inject:into:!
איטרטורים ב-Smalltalk: do:, collect:, select:, reject:, detect: ו-inject:into:
איך כל הלולאות על אוספים בסמולטוק ממומשות כהודעות המקבלות בלוקים, קוד המימוש הפנימי המדויק של כל איטרטור ב-Collection (כולל self species new), ומימוש occurrencesOf: בעזרת inject:into:.
מודל מנטלי ועיקרון מנחה: אל תנהל את הלולאה מבחוץ — שלח לאוסף בלוק ותן לו לעבוד!
במקום שתעמוד בעצמך מול המדף ותעבור פריט-פריט עם אינדקס, ב-Smalltalk אתה מוסר למחסנאי (עצם האוסף) "פתק הוראות" (בלוק קוד), והאוסף עצמו עובר על איבריו ומבצע את הבלוק על כל איבר!
המתודה do: היא לב ליבה של האיטרציה, ועל גביה ממומשות במחלקה Collection כל שאר המתודות: collect:, select:, reject:, detect:ifNone: ו-inject:into:!
collect: ו-select: יוצרות את אוסף התוצאה החדש באמצעות self species new — ולכן אם תפעיל collect: על מחרוזת (String), הבלוק חייב להחזיר תווים (Character) בלבד!
כפי שלמדנו בתחילת הדרך, בשפת Smalltalk אין מילות מפתח תחביריות ללולאות כמו for או while. כל לולאות הסריקה והאיטרציה ממומשות באמצעות שליחת הודעות לעצמים (לשלמים, לבלוקים או לאוספים) המקבלות בלוק כארגומנט. בוא נחקור לעומק את ששת האיטרטורים המרכזיים של מחלקות האוספים, כולל קוד המימוש הפנימי המדויק שלהם!
1. איטרציית בסיס: do: וגרסאותיה המורחבות
סריקת כל איברי האוסף
המתודה do: מקבלת בלוק בעל פרמטר יחיד, ומעריכה אותו עבור כל איבר באוסף (פרמטר הבלוק מקבל בכל סיבוב את ערכו של האיבר התורן).
במחלקה SequenceableCollection היא ממומשת באמצעות שליחת ההודעה to:do: למספר 1 עד גודל האוסף (self size), ושליפת האיבר התורן עם self at: index:
do::
withIndexDo:: מעבירה לבלוק שני פרמטרים — את האיבר התורן ואת האינדקס שלו ([:each :index | ...]).reverseDo:: מעבר על איברי האוסף בסדר הפוך (מהסוף להתחלה).do:without:: ביצוע הבלוק על כל איברי האוסף למעט איבר בעל ערך נתון.- איטרטורים ייחודיים למילון (
Dictionary):keysDo:(איטרציה על המפתחות),valuesDo:(איטרציה על הערכים), ו-associationsDo:(איטרציה על צמדי האסוציאציהkey->value). זכור: ברירת המחדל שלDictionary>>do:מבצעת איטרציה על הערכים בלבד!
2. איסוף ומיפוי תוצאות: collect:
טרנספורמציה (בדומה ל-map) · self species new
המתודה collect: מקבלת בלוק עם פרמטר אחד, מעריכה אותו עבור כל איבר באוסף, ומחזירה אוסף חדש מאותו הטיפוס/המין (species) המורכב מהערכים שחזרו מהערכת הבלוק! תסתכל איך היא ממומשת במחלקה Collection על גבי do::
collect: יוצרת אוסף חדש מאותו הסוג של האוסף המקבל (self species new), אם מפעילים collect: על מחרוזת (String), הבלוק חייב להחזיר תווים (Character) בלבד! החזרת מספרים מתוך הבלוק תגרום לשגיאה/קריסה בזמן ריצה כי String היא אוסף הומוגני שיכול להכיל תווים בלבד!
3. בחירה וניפוי: select: ו-reject:
סינון איברים לפי תנאי בוליאני
• select: מעריכה בלוק בוליאני עבור כל איבר ומחזירה אוסף חדש (self species new) המכיל אך ורק את האיברים שעבורם הבלוק החזיר true.
• reject: מחזירה אוסף חדש המכיל רק את האיברים שעבורם הבלוק החזיר false. שים לב לאלגנטיות שבה reject: ממומשת ב-Collection על ידי קריאה פנימית ל-select:!
4. איתור איבר בודד: detect: ו-detect:ifNone:
החזרת האיבר הראשון שמקיים את התנאי
• detect: מחזירה את האיבר הראשון באוסף שעבורו הבלוק מחזיר true. אם לא נמצא אף איבר כזה – מתעורר מצב חריג (שגיאת NotFound / errorNotFound:).
• detect:ifNone: מקבלת שני בלוקים: בלוק תנאי aBlock (עם פרמטר) ובלוק חלופי exceptionBlock (ללא פרמטר). ברגע שנמצא איבר שעבורו aBlock מחזיר true, מבוצעת יציאה מוקדמת מהמתודה (^ each). אם הלולאה הסתיימה ללא התאמה, מוערך ומוחזר ערכו של exceptionBlock!
5. קיפול וצבירה (inject:into:) והודעות איטרציה נוספות
Left Fold · צבירה למצבר
המתודה inject:into: מבצעת קיפול מצטבר משמאל לימין (Left Fold): היא מקבלת ערך התחלתי (thisValue) ובלוק בינרי בעל שני פרמטרים (binaryBlock) — הפרמטר הראשון הוא המצבר (subTotal / acc / nextValue) והפרמטר השני הוא האיבר התורן (each / next).
בסיבוב הראשון מועברים לבלוק הערך ההתחלתי והאיבר הראשון, ובכל סיבוב הבא מועברים התוצאה שחזרה מהבלוק הקודם והאיבר הבא!
count:: מקבלת בלוק בוליאני ומחזירה מספר שלם — כמות האיברים באוסף שעבורם הבלוק החזירtrue.anySatisfy:: מחזירהtrueברגע שאיבר אחד לפחות באוסף מקיים את תנאי הבלוק.allSatisfy:: מחזירהtrueרק אם כל איברי האוסף מקיימים את תנאי הבלוק.
Collectionכיצד כל האיטרטורים נבנים על גבי מתודת הבסיס do:?
מיני-סימולציה 12.4: בוחן דקויות איטרציה – איטרטורים על Dictionary ובטיחות collect: על String
מעבדת האיטרטורים החיה: הרצה צעד-אחר-צעד של do:, collect:, select:, reject:, detect: ו-inject:into:
#(1 2 3 4 5) – אינדקס 1 עד 5):newCollection / מצבר):הגשר הנרטיבי: עכשיו כשאנחנו שולטים באוספים ובאיטרטורים – אילו מלכודות ריצה מחכות לנו במבחנים ואיך נמנעים מהן?
למה הביטוי התמים collection := OrderedCollection new add: 1; add: 2. מציב במשתנה collection את המספר 2 במקום את האוסף?
ולמה מחיקת מספרים לא-ראשוניים מתוך אוסף של 2 to: 20 תוך כדי ריצת לולאת do: משאירה באוסף בטעות את המספרים הלא-ראשוניים 9 ו-15?
בוא נעבור ליחידה 12.6 ונפצח את כל דגשי הבחינה הקריטיים!
הערות שימושיות ודגשי בחינה מרכזיים: מלכודת add: ו-yourself, מחיקה באיטרציה, = ו-hash ושוויון אוספים
שש סוגיות הליבה שחוזרות בתרגילים ובמבחנים: למה add: מחזירה את האיבר ולא את האוסף, למה אסור למחוק איברים תוך כדי do: (באג ה-9 וה-15!), החוזה הדו-כיווני בין = ל-hash, מפתחות Immutable, איברים הטרוגניים ב-SortedCollection ושוויון ב-SequenceableCollection>>=.
מודל מנטלי ועיקרון מנחה: הבנת המנגנון הפנימי מונעת את כל הבאגים הקלאסיים ב-Smalltalk!
add: ו-yourself
המתודה add: מחזירה תמיד את האיבר שנוסף ולא את האוסף! לכן בשרשור Cascade חובה לסיים ב-; yourself כדי להחזיר את האוסף עצמו (self).
מחיקת איבר בזמן ריצת do: מסיטה את האיברים הבאים שמאלה וגורמת לדילוג על האיבר הבא (כמו דילוג על 9 ו-15!). הפתרון: איטרציה על עותק range copy do: [...]!
=, hash ו-species
אם דורסים את = חובה לדרוס גם את hash, מפתחות במילון ובקבוצה צריכים להיות Immutable, ושני אוספים סדורים שווים רק אם הם מאותו species ואיבריהם שווים לפי הסדר!
1. מלכודת המתודה add: והשימוש ב-yourself ב-Cascade
דגש בחינה מרכזי #1
זוהי אחת הטעויות הנפוצות ביותר בכתיבת קוד ב-Smalltalk: המתודה add: מוגדרת להחזיר תמיד את האיבר שהתקבל להוספה, ולא את האוסף עצמו!
מה קורה אם אנחנו כותבים שרשור הודעות (Cascade עם ;) תמים ושומרים את תוצאתו במשתנה?
כיוון שהערך החוזר משרשור Cascade נקבע לפי ההודעה האחרונה בשרשרת (add: 2), המשתנה collection יכיל את המספר 2 במקום את האוסף!
הפתרון התקני: שליחת ההודעה yourself בסוף ה-Cascade (מתודה המוגדרת ב-Object שפשוט מחזירה את המקבל ^ self), או פיצול לפקודות נפרדות:
2. מלכודת מחיקת איברים מאוסף תוך כדי איטרציה (באג ה-9 וה-15!)
דגש בחינה מרכזי #2
חל איסור מוחלט להסיר איבר מאוסף בזמן שמבצעים עליו איטרציה!
בוא נראה את הדוגמה הקלאסית: נניח שיש לנו אוסף של המספרים מ-2 עד 20, ואנחנו מנסים למחוק ממנו את כל המספרים שאינם ראשוניים תוך כדי ריצה בלולאת do::
למה 9 ו-15 נשארו באוסף? (ההסבר המבני):
זכור ש-do: רצה עם אינדקס שעולה ב-1 בכל צעד (1 to: self size do: [:index | ...]).
כאשר האיטרציה מגיעה למספר הזוגי 8 (אינו ראשוני) ומוחקת אותו באמצעות remove: 8, כל האיברים שאחריו באוסף מוסטים שמאלה ותופסים אינדקס הקטן ב-1 — כך שהמספר 9 מחליק שמאלה לתוך המשבצת שבה ישב קודם 8!
אלא שמונה הלולאה index ממשיך הלאה למשבצת הבאה (שבה נמצא כעת 10), ולכן המספר 9 מדולג לחלוטין ומעולם אינו נבדק! אותו דבר בדיוק קורה כאשר המספר 14 נמחק והמספר 15 מוסט שמאלה ומדולג!
הפתרון התקני: ביצוע האיטרציה על גבי עותק משוכפל שאינו משתנה באמצעות שליחת ההודעה copy, בעוד המחיקה מתבצעת מהאוסף המקורי range:
3. החוזה המחייב בין אופרטור = למתודה hash
אוספים מבוססי גיבוב (כגון Set ו-Dictionary) משתמשים באופרטור השוויון = ובמתודה hash לבדיקת קיום איברים ומפתחות.
לכן, אם הגדרתם מחדש (דרסתם) את מתודת ה-= במחלקה שלכם, חובה להגדיר מחדש גם את המתודה hash, כך ששני עצמים שווים (a = b) יחזירו תמיד את אותו ערך hash!
4. שימוש בעצמים Immutable כמפתחות ואיברי קבוצה
מומלץ להשתמש בעצמים שאינם ניתנים לשינוי (Immutable) כמפתחות ב-Dictionary או כאיברים ב-Set.
אם נשתמש בעצם ניתן לשינוי (Mutable) ונשנה את מצבו הפנימי לאחר שכבר הוכנס למילון או לקבוצה, ערך ה-hash שלו עלול להשתנות, והמילון לא יצליח לאתר אותו שוב (או ששני עצמים שווים ייחשבו בטעות כשונים)!
5. איברים הטרוגניים בתוך SortedCollection
ניתן לאחסן ב-SortedCollection איברים מטיפוסים שונים, בתנאי שקיימת ביניהם פונקציית השוואה תקפה!
אם נכניס לאותו SortedCollection מספרים ומחרוזות מבלי להגדיר sortBlock מותאם שמטפל בהשוואה בין שני הטיפוסים, ניסיון ההשוואה של מספר מול מחרוזת באמצעות <= יוביל לשגיאת ריצה!
6. שוויון בין אוספים סדורים (SequenceableCollection>>=)
המחלקה SequenceableCollection דורסת את מתודת השוויון =. שני אוספים סדורים שווים אם ורק אם מתקיימים התנאים:
1. הם מצביעים לאותו עצם ממש (self == t1), או:
2. הם שייכים לאותו ה-species (self species == t1 species), וגם:
3. יש להם בדיוק את אותם האיברים ובאותו הסדר (hasEqualElements: t1 הנשענת על סריקת at:).
מדוע מחיקת האיבר 8 מסיטה את 9 שמאלה וגורמת ללולאה לדלג עליו?
מיני-סימולציה 12.5: בוחן yourself ב-Cascade ושוויון SequenceableCollection>>=
מעבדת באג המספרים הראשוניים (2 עד 20): הרץ ישירות (range do:) מול הרצה על עותק (range copy do:)
הגשר הנרטיבי: עברנו על כל פרק 12 מראשיתו ועד סופו – בוא נסכם את הכל במילון המושגים האינטראקטיבי!
כעת, אחרי שכיסינו את עץ הירושה של Collection, הפרוטוקולים המשותפים, 8 המאפיינים הפונקציונליים, 5 סוגי המימושים בזיכרון, 7 המחלקות העיקריות, פרוטוקול האיטרטורים המלא וכל מלכודות הבחינה, נעבור ליחידה המסכמת של הפרק (12.7) ונתרגל את כל המושגים בכרטיסיות הזיכרון התלת-ממדיות!
מילון מושגים אינטראקטיבי וסיכום אינטגרטיבי של פרק 12 (אוספים ב-Squeak)
חיבור כל חלקי הפאזל של פרק 12: עץ הירושה של Collection, הפרוטוקולים המשותפים, 8 המאפיינים הפונקציונליים, 5 המימושים בזיכרון, 7 המחלקות העיקריות, האיטרטורים ודגשי הבחינה — יחד עם 12 כרטיסיות זיכרון תלת-ממדיות.
מודל מנטלי ועיקרון מנחה: שליטה באוספים היא שליטה בלב הפועם של Smalltalk
מעל 90 מחלקות יורשות מ-Collection (בענפי SequenceableCollection, Set ו-Bag) וממומשות ב-5 טכניקות זיכרון (מערך קבוע, מערך פנימי מתרחב, טבלת גיבוב, רשימה מקושרת, ואינטרוול בן 3 שלמים).
שבע מחלקות הליבה (Array, OrderedCollection, Interval, Dictionary, Set, SortedCollection, String) נסרקות ומעובדות באמצעות בלוקים בהודעות do:, collect:, select:, reject:, detect: ו-inject:into:.
סיום Cascade של add: ב-yourself, שכפול אוסף עם copy לפני מחיקה בלולאה, דריסת hash יחד עם =, מפתחות Immutable, ובדיקת species בשוויון אוספים סדורים.
מבט-על על ספריית האוספים ב-Squeak: מעץ הירושה ועד לאיטרטורים ולכללי הזהב
מיני-סימולציה 12.6: יועץ בחירת האוספים – איזו מחלקת אוסף מתאימה לכל משימה?
כרטיסיות זיכרון תלת-ממדיות (3D Flashcards) לכל 12 מושגי הליבה של פרק 12
לחץ על כל כרטיסייה כדי להפוך אותה ולבחון את עצמך על כל אחד מ-12 מושגי המפתח של פרק 12:
נחשפו: 0 / 12השלמנו במלואו את פרק 12 (אוספים ב-Squeak) ואת כל חלק V (מחלקות)!
כעת יש בידיך שליטה מלאה בספריית האוספים של Smalltalk — מהיררכיית Collection, הפרוטוקולים והמימושים בזיכרון, דרך שבע מחלקות הליבה והאיטרטורים, ועד לכללי הזהב שמונעים שגיאות ריצה.