Вказівки
Кільцевий буфер, циклічний буфер або ring buffer - це структура даних, яка використовує єдиний буфер фіксованого розміру так, ніби його зʼєднано кінець у кінець.
Спочатку кільцевий буфер порожній і має певну заздалегідь визначену довжину.
Наприклад, ось буфер на 7 елементів:
[ ][ ][ ][ ][ ][ ][ ]
Припустімо, що в середину буфера записують 1 (точне початкове розташування для кільцевого буфера не має значення):
[ ][ ][ ][1][ ][ ][ ]
Далі припустімо, що додають ще два елементи, 2 і 3, які дописуються після 1:
[ ][ ][ ][1][2][3][ ]
Якщо після цього з буфера вилучити два елементи, вилучаються найстаріші значення в буфері.
У цьому випадку вилучено 1 і 2, і в буфері залишається лише 3:
[ ][ ][ ][ ][ ][3][ ]
Коли в буфері 7 елементів, він заповнений повністю:
[5][6][7][8][9][3][4]
Коли буфер заповнений, виникає помилка, яка повідомляє клієнта, що подальші записи заблоковано, доки не звільниться місце.
Коли буфер заповнений, клієнт може на власний розсуд перезаписати найстаріші дані примусовим записом.
У цьому випадку додають ще два елементи, A і B, які перезаписують 3 і 4:
[5][6][7][8][9][A][B]
3 і 4 замінено на A і B, тож найстарішими даними в буфері тепер стає 5.
Нарешті, якщо вилучити два елементи, то повернуться 5 і 6, і в результаті буфер матиме такий вигляд:
[ ][ ][7][8][9][A][B]
Оскільки є вільне місце, якщо клієнт знову скористається перезаписом, щоб зберегти C і D, то використано буде місце, де раніше зберігалися 5 і 6, а не позицію 7 і 8.
7, як і раніше, найстаріший елемент, і буфер знову заповнений повністю.
[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 уже повний, то викиньте виняток BoundsError, якщо overwrite дорівнює false (типове значення); інакше, якщо 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): Поверніть true, якщо cb повний.
Далі потрібно переконатися, що наведені нижче функції з 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, щоб відкрити відповідний файл і рядок у типовому текстовому редакторі.
