ساختن Custom Collection در Swift

*این مطلب به همراهی مهدی حاجی محمدعلی و به عنوان تحقیق درس برنامه سازی موبایل، و از روی این منبع نوشته شده است.

معمولا آرایه‌ها، مجموعه‌ها و دیکشنری‌ها، کالکشن‌تایپ هایی هستند که در کتابخانه استاندارد سوییفت وجود دارند و از‌ آنها استفاده می‌شود، اما اگر این‌ها نیاز شما را برطرف نکنند چطور؟ می‌توانید کالکشن دلخواه خودتان را با پیاده سازی پروتکل‌هایی که در کتابخانه استاندارد سوییفت وجود دارند، بسازید.

در این آموزش ما میخواهیم یک (multiset(Bag بسازیم. از این بعد آنرا سبد صدا میزنیم.

مقدمات کار

با کد زیر شروع می‌کنیم

برای اینکه ورودی مجموعه را بتوانیم در (O(1 مقایسه کنیم و ذخیره کنیم نیاز داریم تا ورودی از جنس Hashable باشد.چون میخواهیم مانند مجموعه‌های استاندارد سوییفت valueType باشد از struct استفاده میکنیم.

یک سبد دقیقا مشابه set هست و اگر عنصر تکراری به آن اضافه شود آنرا جدا نگه نمیدارند اما تعداد تکرار یک عنصر را ذخیره میکند، برای مثال لیست خرید نمونه‌ای از یک سبد است که هر مورد در آن تعداد هم دارد.

برای پیاده‌سازی این ویژگی، کد زیر را اضافه میکنیم

برای ذخیره تعداد برای هر عنصر از دیکشنری (content) استفاده میکنیم.آنرا fileprivate قرار میدهیم تا خارج از کد ما دسترسی نداشته باشد.

تعداد عناصر یکتا یا همان سایز مجموعه را در uniqueCount نگه میداریم.

تعداد کل عناصر را - با احتساب تکراری ها - در totalCount نگه میداریم.

اضافه کردن تابع Add

۱.تابع (:add(_:occurrences : این تابع ورودی memeber که از تایپ جنریک Element است را به همراه ورودی آپشنال occurrences میگیرد و به تعداد occurences ، آنرا به سبد ما اضافه میکند.از کلیدواژه mutating هم استفاده میکنیم تا بتوانیم مقدار contents را داخل تابع تغییر دهیم.

۲.تابع precondition: در طول برنامه برای اطمینان از صحت عملکرد برنامه استفاده میشود. این تابع یک شرط و یک رشته به عنوان ورودی میگیرد. اگر شرط برقرار بود برنامه ادامه می‌یابد و اگر شرط برقرار نبود برنامه متوقف شده و رشته چاپ می‌شود.

۳. اگر آیتم وجود داشت تعداد آنرا به اندازه مقدار داده شده زیاد میکند و اگر وجود نداشت آنرا به دیکشنری contents اضافه می‌کند.

پیاده سازی تابع Remove

این تابع هم ۲ ورودی مانند تابع add میگیرد.در قسمت ۱ چک میکند که آیتم به مقدار حداقل به مقداری که قرار است کم بشود، وجود داشته باشد. اگر نبود از تابع خارج می‌شود.

۲.مطمئن می‌شود که مقدار حذفی حتما عددی مثبت باشد.

۳. اگر موجودی آیتم بیشتر از مقدار برای کم کردن بود آنرا کم میکند در غیر این‌ صورت آیتم را کلا حذف می‌کند.

حالا سبد ما صرفا قابلیت اضافه مردن و کم کردن دارد ولی ما میخواهیم امکان iterate,filter,map ,... هم داشته باشد. برای اضافه کردن این قابلیت ها باید تعدادی از پروتکل‌های سوییفت را پیاده‌سازی کنیم.

پیاده‌سازی پروتکل‌ها

پروتکل‌ها در سوییفت مجموعه‌ای از توابع و متغیر ها هستند که شی استفاده کننده از این پروتکل باید آنها را پیاده‌سازی کند.( مانند interface در جاوا). برای استفاده از پروتکل (adopt) بعد از نام کلاس در تعریف، دونقطه قرارداده و اسم پروتکل را جلوی آن مینویسیم.بعد از تعریف باید خصوصیات و توابع پروتکل را پیاده‌سازی کرد.

برای مثال، در حال حاضر صورت رشته‌ای سبد ما اطلاعات خاصی به ما نمیدهد. اگر قطعه کد زیر را اجرا کنید و نتیجه را در دیباگر مشاهده کنید میبینید که شی سبد صرفا به صورت <Bag<String نمایش داده می‌شود.

برای حل این مسئله، پروتکل CustomStringConvertible را به کلاسمان الحاق میکنیم.

این پروتکل متغیری به نام describtion دارد که مقدار آن را برابر صورت رشته‌ای دیکشنری content قرار میدهیم. کلاس دیکشنری، خودش این پروتکل را به صورتی پیاده سازی کرده که با تبدیل دیکشنری به رشته، محتوای داخل دیکشنری به صورت رشته دربیاید.

حالا اگر دوباره کد تستیمان را اجرا کنیم میبینم که در هر مرحله محتوای داخل سبد به صورت رشته نمایش داده می‌شود.

ساختن initializer

دونه دونه اضافه کردن اعضا به سبد سخته، پس می‌خواهیم قابلیتی فراهم کنیم که موقع ساختن سبد، یک کالکشن دریافت کنه و همه رو اضافه بکنه.

برای مثال ما انتظار داریم که کد زیر کار بکند.

برای اینکه کد بالا کار بکند باید برای سبد، initializer مناسب را تعریف کنیم.

پس کد زیر را اضافه میکنیم:

1. برای اینکه بتونیم initializer های مختلف با ورودی ها اضافه بسازیم اول باید یک تابع init خالی بگذاریم.
2. یک initializer تعریف میکنیم که به عنوان ورودی هر شئ‌ای که پروتکل Sequence را پیاده کرده باشد و اشیاء داخلش از جنس اشیاء داخل سبد ما باشد را به عنوان ورودی می‌گیرد و بعد آنرا پیمایش کرده و اشیاء آن را به سبد ما اضافه می‌کند.
3. یک initializer دیگر هم مانند قبلی اضافه می‌کنیم با این تفاوت که اینجا ورودی ما tuple از جنس (Element,Int) است و مثلا به عنوان ورودی می‌تواند یک دیکشنری از اشیاء را همراه با تکررشان به سبد اضافه کند.

حالا می توانید کدی که گذاشته بودیم را اجرا کنیم.

ساختن مستقیم با کالکشن

این initializer هایی که ساختیم به ما امکانات بیشتری برای ساخت سبد می‌دهد، اما همچنان نیاز داریم تا برای ساختن سبد یک کالکشن بسازیم و آنرا به تابع سازنده سبد بدهیم. اما اگر بخواهیم با شکل مستقیم آرایه یا دیکشنری، سبدمان را بسازیم چطور؟ مثلا کد زیر مثالی از ساختن سبد به همین شیوه است.

برای اینکه کد بالا اجرا شود باید پروتکل های ‌ExpressibleByArrayLiteral و ExpressibleByDictionaryLiteral را به شیوه زیر پیاده سازی کنیم.

این دو پروتکل از دو شکل مستقیم آرایه و دیکشنری استفاده می‌کنند و با تابع سازنده‌ای که قبلا نوشته بودیم سبد ما را می‌سازند.

اما Custom Collection واقعا چیست؟

حالا که جلو آمده‌ایم می‌توانیم بهتر بفهمیم که کاستوم کالکشن چیست.یک شئ مجموعه‌ای است که هر دو پروتکل Collection و Sequence را پیاده‌سازی می‌کند.

در قسمت قبل تابع initializer ای تعریف کردیم که به عنوان ورودی شیئی که Sequence را پیاده کرده باشد می‌گرفت. Sequence معرف داده‌ای است که قابلیت پیمایش روی داده‌هایش را به ما می‌دهد.

پیمایش مفهموم ساده‌ای است اما قابلیت‌های مهمی را به داده ما می‌دهد.مثلا عملیات های زیر با پیاده کردن Sequence فراهم می‌شود:

• تابع map(_:) بر روی هر کدام از داده‌های داخل مجموعه عملیاتی را انجام می‌دهد و نتیجه را برمی‌گرداند.
• تابع filter(_:) قسمتی از داده‌ها‌ را که با شرط داده شده مطابقت دارند را برمی‌گرداند.
• تابع (:‌sorted(by داده‌ها را بر اساس تابع داده‌شده مرتب می‌کند

برای دیدن بقیه توابعی که به وسیله Sequence فراهم می‌شوند داکیومنت آن را ببینید.

برای اینکه مطمئن بشویم پیمایش ما بر روی داده‌ها آن را خراب نمی‌کند.از آنجایی که Sequence این مسئله را تضمین نمی‌کند باید پروتکل Collection را هم حتما پیاده کنیم.Collecton از Indexable و Sequence ارث‌ میبرد.

پیاده کردن Collection تعدادی تابع و متغیر به دردبخور را مجانی در اختیار شما می‌گذارد:

• بولینی که نشان میدهد کالکشن خالی‌ است یا نه: isEmpty
• اولین عضو را برمیگرداند: first
• تعداد اعضای مجموعه را برمی‌گرداند: count

تعدادی دیگر هم هست که می‌توانید در داکیومنت آن ببینید.

حالا سبدتون رو بردارید تا این پروتکل هارو پیاده‌سازی کنیم :)

مطابقت دادن با sequence

تنها کد بالا برای مطابقت لازم است.

در کد بالا:

۱. یک typealias به نام iterator که از نوع DictionaryIterator میباشد ساخته‌ایم. Sequence برای دانستن نحوه iterate کردن ما به آن نیاز دارد. DictionaryIterator تایپی است که اشیا از جنس دیکشنری از آن برای iterate کردن استفاده می‌کند. ما از این تایپ استفاده می‌کنیم زیرا سبد داده‌های اصلی خود را در یک دیکشنری ذخیره می‌کند.

۲. یک makeIterator تعریف می‌کنیم که یک iterator را برای حرکت روی هر عنصر sequence خروجی می‌دهد.

۳. داخل تابع makeIterator یک iterator روی contents می‌گیریم. خود contents نیز با sequence مطابقت دارد.

این همه آن چیزی است که برای ساختن یک سبد مطابق با sequence نیاز داریم.

حال می‌توانیم روی هر یک از عناصر سبد حرکت کنیم و تعداد هر شی را به‌دست آوریم. کد زیر را به انتهای playground پس از for-in قبلی اضافه می‌کنیم:

حال با اجرای playground می‌توانید هر عنصر سبد و تعداد آن را ببینید.

مشاهده برخی مزایای sequence

حرکت روی عناصر سبد امکان پیاده‌سازی توابعی سودمند در sequence را به ما می‌دهد. کد زیر را در پایان playground اضافه کنید تا برخی از مزایای این اتفاق را مشاهده کنید:

برنامه را اجرا کنید.

می‌توانید چندی از این توابع را در بالا ببینید.

حال می‌توان امکانات بیشتری به sequence افزوده و پیاده‌سازی آن را بهتر کنید. در ادامه به پیاده‌سازی بهتر sequence می‌پردازیم:

بهینه‌سازی sequence

در حال حاضر ما تمام دیتاهای اساسی‌مان را روی یک دیکشنری نگه‌میداریم و آن را کنترل می‌کنیم. این ویژگی خوبی است زیرا می‌توانیم بوسیله آن کالکشن مورد نظرمان را به سادگی درست کنیم. ولی مشکل ما این است که این مساله کاربرانی که از سبد استفاده می‌کنند را گیج می‌کند. زیرا اینکه سبد به ما یک iterator از نوع dictionaryiterator می‌دهد چندان درست به‌نظر نمی‌رسد.

ولی سوییف این مشکل را به راحتی برای ما حل می‌کند. سوییف از تایپ AnyIterator نیز پشتیبانی می‌کند که به‌سیله آن می‌توانیم هویت iterator اصلی را از باقی کد پنهان نگه داریم.

پیاده‌سازی sequence extension را به‌صورت زیر تغییر دهید:

با این تغییرات روی Sequence extension:

۱. یک iterator از نوع any را به‌جای dictionary استفاده کردیم. سپس همانند قبل می‌توانیم تابع makeIterator را روی تعریف کنیم تا آن را به ما خروجی دهد.

۲. همانند قبل یک iterator را با فراخوانی تابع makeIterator روی content بدست می‌آوریم.

۳. حال iterator را بصورت یک شی AnyIterator خروجی می‌دهیم. این شی از طریق تابع next روی iterator قسمت قبل می‌تواند روی دیتای ما حرکت کند. حال این شی را خروجی می‌دهیم.

حال اگر کد را اجرا کنید با خطاهایی مواجه می‌شوید:

پیش از این ما از DictionaryIterator با دوتایی های key , value استفاده می‌کردیم. حال این شی را تغییر داده‌ایم و نام های دوتایی را به element : count تغییر داده‌ایم. در نتیجه برای حل این خطا key , value را با element, count جایگزین می‌کنیم. حال با اجرای برنامه precondition های شما pass می‌شود.

حال کسی متوجه استفاده ما از dictionary نمی‌شود. حال زمان پیاده‌سازی collection می‌باشد…

استفاده و پیاده‌سازی Collection protocl

برای پیاده‌سازی کالکشن باید Colection protocol را پیاده‌سازی کنیم. کالکشن یک sequence است که به عناصر آن بوسیله یک اندیس می‌توان دسترسی پیدا کرد و روی آن چندین بار حرکت کرد.

برای پیاده‌سازی کالکشن باید جزییات زیر را در نظر بگیریم:

۱. اندیس شروع و پایان: که کران‌های کالکشن را مشخص می‌کند و نقطه شروع عرض را مشخص می‌کند.

۲. Position: این امکان را به ما می‌دهد که به هر عنصر کالکشن با یک اندیس دسترسی پیدا کنیم. عملیات دسترسی نیز باید با در (1)O انجام شود.

۳. اندیس: اندیس را به محض اندیس پاس شده بازگرداند.

کد زیر را پایین sequence extension قرار دهید:

در این قسمت:

۱. نوع اندیس در کالکشن از نوع dictionaryindex تعریف می‌شود. ما این اندیس را از طریق content پاس می‌دهیم.

۲. اندیس شروع و پایان content را خروجی می‌دهیم.

۳. از یک precondition برای بدست آوردن اندیس های معتبر استفاده می‌کنیم. مقدار عنصر content متناسب با اندیس را به صورت یک تاپل باز می‌گردانیم.

۴. مقدار index(after) of content را باز می‌گردانیم.

با افزودن این توابع و مقادیر کالکشن به درستی ساخته می‌شود.

آزمایش کالکشن

کد زیر را به انتهای playground اضافه کنید تا عملکردهای جدید را آزمایش کنید:

حال دوباره playground را اجرا کنید.

حال نشانه هایی از dictionary در کد دیده می‌شود. پس به بهینه کردن کد می‌پردازیم:

بهینه‌سازی کالکشن

حال باید DictionaryIndex را از کد مان حذف کنیم. به صورت زیر می‌توان این مساله را حل کرد:

در تکه کد بالا:

۱. یک تایپ جدید به نام bagindex تعریف می‌کنیم. همانند سبد این تایپ نیز باید قابل hash شدن باشد تا در دیکشنری قابل استفاده باشد.

۲. داده داخلی برای این نوع اندیس را یک شی از نوع dictionaryIndex قرار می‌دهیم.

۳. یک initializer تعریف میکنیم که یک شی از DictionaryIndex را بگیرد و ذخیره کند.

حال باید توجه کنیم که کالکشن ایندکس قابل مقایسه نیاز دارد تا بتواند عملیات‌های مورد نیاز را با توجه به تفاوت اندیس‌ها انجام دهد. با توجه به این BagIndex باید comparable را پیاده‌سازی کند.

کد زیر را پس از bagIndex قرار دهید:

منطق این کد واضح است. از توابعی همانند dictionaryIndex استفاده می‌کنیم تا مقدار درست را خروجی دهیم.

به‌روز کردن BagIndex:

حال باید Bag را تغییر داده و از bagindex استفاده کنیم. حال تکه کد زیر را با collection extension جایگزین کنید:

هر یک از اعداد کامنت شده در کد بالا یک تغییر را نشان می‌دهد. به تفصیل این تغییرات می‌پردازیم:

۱. تایپ اندیس(index) از dictionaryindex به bagindex تغییر داده ایم.

۲. یک bagindex را در content برای startindex و endindex می‌سازیم.

۳. از متغیر index داخل bagindex استفاده می‌کنیم تا به هر عنصر از contentsدسترسی پیدا کرده و آن را بازگردانیم.

۴. مقدار Dictionaryindex را از contents بوسیله مقدار bagindex میگیریم و یک bagindex جدید با این مقدار ایجاد می‌کنیم.

حال توانستیم کاری کنیم که کاربران از استفاده ما از دیکشنری باخبر نشوند.

حال برای آنکه کار را به اتمام برسانیم بهتر است امکان انتخاب یک بازه را بوسیله slice به کاربر بدهیم.

استفاده از slice

قسمت یا slice یک زیرمجموعه‌ای از عناصر داخل کالکشن می‌باشد و این امکان را می‌دهد تا روی یک زیرمجموعه از کالکشن تغییراتی اعمال کنیم بدون آن که نیاز به کپی کردن از عناصر داشته باشیم.

هر slice یک رفرنس به کالکشن اصلی را نگه می‌دارد. Slice ها اندیس‌ها را با کالکشن ابتدایی خود به اشتراک گذاشته و یک رفرنس یا اشاره به اندیس شروع و پایان آن بازه خواهند داشت تا زیرمجموعه مورد نظر را تحت نظر داشته باشد. Slice ها پیچیدگی زمانی ثابت (۱)O دارند زیرا بصورت مستقیم به کالکشن اصلی خود اشاره می‌کنند.

برای متوجه شدن نحوه عملکرد آنها کد زیر را به انتهای playground اضافه کنید:

۱. یک سبد میوه از ۴ میوه مختلف ساختیم.

۲. اولین نوع از میوه را حذف می‌کنیم. این‌کار یک slice جدید بوجود می‌آورد که میوه نوع اول را جدا می‌کند به جای آنکه یک شی سبد جدید را ایجاد کنید.

۳. اندیس آخرین میوه باقی‌ماده را می‌یابد.

۴. نه تنها اندیس را از کالکشن اصلی می‌گیریم تا به یک عنصر آن دسترسی پیدا کنیم بلکه اندیس را از slice محاسبه می‌کنیم.

خب دیگه تموم شد. تونستیم یک کالکشن برای خودمون بسازیم:)