リングバッファ

説明

循環バッファ、サイクリックバッファ、リングバッファは、単一の固定サイズのバッファを、端と端がつながっているかのように使うデータ構造です。

循環バッファは最初は空で、あらかじめ決められた長さを持ちます。 たとえば、これは7要素のバッファです：

[ ][ ][ ][ ][ ][ ][ ]

バッファの真ん中に1が書き込まれたとします（循環バッファでは、正確な開始位置は問題になりません）：

[ ][ ][ ][1][ ][ ][ ]

次に、さらに2つの要素、2と3が追加され、1の後に続けて入るとします：

[ ][ ][ ][1][2][3][ ]

そのあとでバッファから2つの要素を取り除くと、バッファの中で最も古い値が取り除かれます。 この場合に取り除かれる2つの要素は1と2で、バッファには3だけが残ります：

[ ][ ][ ][ ][ ][3][ ]

バッファに7つの要素が入ると、完全にいっぱいになります：

[5][6][7][8][9][3][4]

バッファがいっぱいになるとエラーが発生し、スロットが空くまでこれ以上書き込めないことをクライアントに知らせます。

バッファがいっぱいのとき、クライアントは強制書き込みで最も古いデータを上書きすることを選べます。 この場合、さらに2つの要素AとBが追加され、3と4を上書きします：

[5][6][7][8][9][A][B]

3と4はAとBに置き換えられ、バッファの中で最も古いデータは5になりました。 最後に、2つの要素を取り除くと、返されるのは5と6で、バッファはこうなります：

[ ][ ][7][8][9][A][B]

空きがあるので、ここでクライアントが再び上書きを使ってCとDを保存すると、使われるのは前に5と6が入っていた場所で、7と8の場所ではありません。 7は依然として最も古い要素で、バッファは再びいっぱいになります。

[C][D][7][8][9][A][B]

タスク

型Tの要素を保持するパラメトリックな複合型CircularBuffer{T}を定義し、最大capacity個の要素を保存できるインスタンスを作成する次のコンストラクターを書いてください。

CircularBuffer{T}(capacity::Integer) where {T} -> CircularBuffer{T}

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を拡張して、DataStructures.jlパッケージのCircularBufferのテストに合格するようにしてください。これらのテストは、このExercism演習で提供されるテストに含まれていますが、無効になっています。これらのテストを有効にするには、ファイルまたはノートブックのトップレベルにenable_bonus_tests = trueという行を追加してください。

これらのテストに合格するには、CircularBufferをAbstractVectorのサブタイプとして宣言し、次の2つの関数を定義する必要があります：

• 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の強力さと拡張性の多くは、非公式なインターフェースの集まりから生まれています。カスタム型で動作するようにいくつかの特定のメソッドを拡張するだけで、その型のオブジェクトはそれらの機能を受け取るだけでなく、それらの振る舞いを汎用的に組み合わせて作られた他のメソッドでも使えるようになります。

JuliaのBaseモジュールのソースコードを調べて、関数定義を確認し、どの関数を拡張すべきか判断する必要があります。関数呼び出しに関連するコードを見つけるには、@whichマクロを使って、関数呼び出しがディスパッチされる具体的なメソッドを特定できます。また、そのメソッドが定義されているファイルと行番号も表示します（Jupyter NotebookでIJuliaを使っている場合は、GitHub上の該当コードへのリンクまで表示されます）。

REPLで作業している場合は、@editマクロを使って、該当するファイルと行をデフォルトのテキストエディターで開くほうがよいかもしれません。

---

出典

Wikipedia