دستورالعملها
«بافر حلقهای»، «بافر چرخهای» یا «بافر حلقوی» یک ساختار داده است که از یک بافر واحد با اندازهی ثابت استفاده میکند، طوریکه انگار دو سر آن به هم متصل شده است.
بافر حلقهای ابتدا خالی است و طولی از پیش تعیینشده دارد.
برای مثال، این یک بافر ۷ عنصری است:
[ ][ ][ ][ ][ ][ ][ ]
فرض کنید عدد ۱ در میانهی بافر نوشته میشود (مکان دقیق شروع در بافر حلقهای اهمیتی ندارد):
[ ][ ][ ][1][ ][ ][ ]
سپس فرض کنید دو عنصر دیگر، ۲ و ۳، اضافه میشوند که بعد از ۱ قرار میگیرند:
[ ][ ][ ][1][2][3][ ]
اگر سپس دو عنصر از بافر حذف شوند، قدیمیترین مقدارهای داخل بافر حذف میشوند.
دو عنصری که در این حالت حذف میشوند ۱ و ۲ هستند و بافر تنها با ۳ باقی میماند:
[ ][ ][ ][ ][ ][3][ ]
اگر بافر ۷ عنصر داشته باشد، کاملاً پر است:
[5][6][7][8][9][3][4]
وقتی بافر پر باشد، خطایی ایجاد میشود و به کاربر اطلاع میدهد که نوشتنهای بعدی تا آزاد شدن یک خانه مسدود است.
وقتی بافر پر است، کاربر میتواند با یک نوشتن اجباری، قدیمیترین داده را بازنویسی کند.
در این حالت، دو عنصر دیگر، A و B، اضافه میشوند و ۳ و ۴ را بازنویسی میکنند:
[5][6][7][8][9][A][B]
۳ و ۴ با A و B جایگزین شدهاند و اکنون ۵ قدیمیترین دادهی بافر است.
در پایان، اگر دو عنصر حذف شوند، آنچه برگردانده میشود ۵ و ۶ است و بافر زیر را به دست میدهد:
[ ][ ][7][8][9][A][B]
چون فضا موجود است، اگر کاربر دوباره از بازنویسی برای ذخیرهی C و D استفاده کند، فضایی که پیشتر ۵ و ۶ در آن ذخیره شده بودند استفاده میشود، نه محل ۷ و ۸.
۷ هنوز قدیمیترین عنصر است و بافر دوباره پر شده است.
[C][D][7][8][9][A][B]
وظایف
یک نوع ترکیبی پارامتری به اسم CircularBuffer{T} تعریف کنید که عناصری از نوع T را در خود نگه میدارد و سازندهای بنویسید
CircularBuffer{T}(capacity::Integer) where {T} -> CircularBuffer{T}
که نمونهای میسازد که میتواند تا capacity عنصر را ذخیره کند.
توابع زیر را از Base گسترش دهید تا روی CircularBufferها کار کنند:
-
Base.push!(cb::CircularBuffer, item; overwrite::Bool=false): عنصر item را به انتهای cb اضافه میکند و سپس cb را برمیگرداند. اگر cb از قبل پر باشد، در صورتی که overwrite برابر با false باشد (مقدار پیشفرض)، یک BoundsError پرتاب میکند؛ در غیر این صورت، اگر overwrite برابر با true باشد، اولین عنصر را حذف میکند تا برای item جا باز شود.
-
Base.popfirst!(cb::CircularBuffer): اولین عنصر cb را حذف میکند و برمیگرداند.
-
Base.empty!(cb::CircularBuffer): همهی عناصر را از cb حذف میکند و سپس cb خالی را برمیگرداند.
وظایف امتیاز
این تمرین نسبتاً بزرگ و بالقوه پیچیده است و همین منتور کردن آن را چالشیتر و وقتگیرتر میکند. برای کمک به منتور خود، لطفاً تا وقتی که منتورتان راهحل شما را برای بخش اول تمرین بررسی نکرده است، کدی برای تمرینهای امتیاز ارسال نکنید.
CircularBuffer خود را گسترش دهید تا تستهای CircularBuffer از بستهی DataStructures.jl را پاس کند. این تستها در تستهای ارائهشده برای این تمرین Exercism گنجانده شدهاند اما غیرفعال هستند؛ برای فعال کردن این تستها، خط سطح بالا enable_bonus_tests = true را به فایل یا نوتبوک خود اضافه کنید.
برای پاس کردن این تستها باید CircularBuffer را زیرنوعی از AbstractVector اعلام کنید و دو تابع تعریف کنید:
-
capacity(cb::CircularBuffer): ظرفیت cb را برمیگرداند.
-
isfull(cb::CircularBuffer): اگر cb پر باشد، true را برمیگرداند.
سپس باید مطمئن شوید که توابع زیر از Base بهدرستی با CircularBufferها کار میکنند: append!، empty!، pop!، pushfirst، setindex!، collect، eltype، first، getindex، isempty، iterate، last، length و size.
نکته: لازم نیست همهی این توابع را گسترش دهید و نباید هم این کار را بکنید! با تعریف CircularBuffer بهعنوان زیرنوعی از AbstractVector، توابع عمومی که برای AbstractVector تعریف شدهاند از این پس CircularBuffer را هم بهعنوان ورودی میپذیرند. بخش مربوط به رابطها را در راهنمای Julia ببینید:
بخش زیادی از توان و قابلیت گسترش Julia از مجموعهای از رابطهای غیررسمی میآید. با گسترش چند متد مشخص برای کار با یک نوع سفارشی، اشیای آن نوع نهتنها این قابلیتها را به دست میآورند، بلکه میتوان از آنها در متدهای دیگری هم استفاده کرد که بهصورت عمومی بر پایهی این رفتارها نوشته شدهاند.
باید کد منبع ماژول Base در Julia را بررسی کنید تا تعریف توابع را ببینید و بفهمید کدامیک را گسترش دهید. برای پیدا کردن کد مربوط به یک فراخوانی تابع، میتوانید از ماکروی @which استفاده کنید تا متد مشخصی را که فراخوانی تابع به آن فرستاده میشود شناسایی کنید. این ماکرو همچنین فایل و شمارهی خطی را نشان میدهد که آن متد در آنجا تعریف شده است (در Jupyter Notebook از طریق IJulia، حتی پیوندی به کد مربوطه در GitHub هم به شما میدهد).
اگر در REPL کار میکنید، ممکن است ترجیح دهید از ماکروی @edit استفاده کنید تا فایل و خط مربوطه را در ویرایشگر متن پیشفرض خود باز کنید.
