[Swift] Generics を使って RingBuffer を作る

Swift

Swift の Generics を使って、Ring Buffer を作ってみます。

環境&対象

以下の環境で動作確認を行なっています。

  • macOS Big Sur 11.3
  • Xcode 12.5
  • iOS 14.5

Ring Buffer

例えば、Array はバッファとして線形に確保され、一方の端から使われ始めます。確保されたバッファに収まらなくなった時には、バッファが自動的に拡張されます。

通常は、Array の持つこのような振る舞いが便利なのですが、特定数まで保持していれば、それ以上は不要というようなケースもあります。

例えば、待ち行列のような バッファの後ろには追加し、バッファの先頭からは削除するというような操作のみを行うケースでは、先頭部分の削除されたエリアを再利用したくなります。

このような時に、RingBuffer が使われます。

Wikipedia の説明は、こちら

TDD (Test Driven Development) で作ります。

いつもどおり、TDD で作っていきます。

最初から Generics で考えるとややこしいので、まずは Int を対象に Ring Buffer で管理するもの作成し、その後 Generics を導入します。

仕様 = Test Spec

以下のような使い方ができる仕様で作ります。

インスタンス作成

capacity: で容量を指定できるようにします。

この数字は、最大保持数を意味します。この例では、最大4つの要素を保持し、それ以上の要素は古いものから破棄していくことになります。

データ追加

write(_:) でデータを追加できるようにします。(最初は Int 限定ですが、Generics によって、タイプを拡張します)

保持データ数

count で、保持しているデータ数を取得できるようにします。(返却値は、最大で capacity です)

テストとして書くと以下のようになります。

データ参照

インデックス経由でデータを参照できるようにします。
最新のデータを latestIndex で参照でき、最古のデータは、oldestIndex で参照します。

テストとして書くと以下のようになります。

エラー処理

# Ring Buffer なので、書き込むことができなくなることはないです。

インデックスでデータを参照するので、インデックスが範囲外の時には、値として nil を返すものとします。

テストとして書くと以下のようになります。

テストコード

Capacity を超える数を write されるかどうかで2パターン作成しました。

実装 : RingBufferInt

いきなり Generics を入れるとわかり難いので、まずは Int で動くものを作成します。

上記のコードは、すでに先に記述したテストをパスします。

Ring Buffer の複数タイプ対応

上記の実装は、Int を保持する RingBuffer でした。実装コードを確認するとわかりますが、buffer で保持するデータとして Int を使用しているために、write や subscript の返り値に Int を使っていますが、その他の箇所では RingBuffer の保持する型が Int であることを必要としてはいません。

RingBuffer の仕組みとしては String でも Double でも同様に保持し処理することができます。

しかし、実際に String を保持しようとすると、様々な箇所の Int を String に置き換える必要があります。

対象とするタイプを変更するために、コードの大部分をコピーして、一部書き換えるという作業は、百害あって一利なし です。

そのようなケース向けに Swift が用意している機能が Generics です。

Generics

Buffer の保持するタイプを例に挙げていますが、もう少し簡単なケースから説明してみます。

Generics を使うと解決できる課題

以下のような、受け取った2つの Int を入れ替える関数を考えてみます。

使い方は以下のようになります。

RingBuffer の時と同様に 、変数の中身の交換という処理自体は 対象が Int であることを必要としていません。Double であっても、 String であっても同様の処理を実装することはできます。

ただし、引数が それぞれの型であることが必要であるため、Double を入れ替える関数や String を入れ替える関数は 上記コードをコピーしたものを書き換える必要が発生します。

# なお、valueA と valueB は同じ型であることが必要です。

Generics を使うと このような課題を解決することができます。

Generics を使った関数

先の swapTwoInt(_:,_:) を Generics を使うと以下のように書き換えることができます。

関数定義中の関数名の直後に<>で T を囲っています。この T は、<>で囲われることで placeholder として定義されています。(ここで定義された T がその後の引数定義に出てきています。必要であれば、関数内部でも使うことができるようになります)

MEMO
Placeholder で使われる名称は、関連性がわかるような名称をつけることが推奨されています。

このケースでは、置き換える値のタイプという以上の意味はないので、T を使っています。意味を特に持たせたくない時には、T や U,V などの英字1文字がよく使われるようです。

関連性がわかる名称の例としては、Swift Standard Library の Dictionary の定義を参照すると placeholder で Key, Value という意味のある名称が使われていることが確認できます。

なお、関数定義時には、T は定義されている必要はありません。

この関数が使用される時に、T は決定される必要があります。つまり以下のように使用される必要があります。

ですが、上記は “Cannot explicitly specialize a generic function” というコンパイルエラーとなります。
エラーの意味は、「generic function を具体的タイプを指定して使うことはできない」と言うものです。

Swift は、強力な型推論する機能をもっているため、型推論できる時には 以下のように省略して書くことが必要のようです。

例えば以下のように書くと、型推論されていることがわかるエラーが表示されます。

エラーの意味は、「(1つ目の引数が Int であるため、)2つ目の引数も Int に変換しようとしたが、Double は、Int に変換できない」と言うものです。
Swift が文脈から 引数の型情報を取得し適用していることがわかります。

Generics を使った struct

次に、struct に Generics を適用する方法を見てみます。

struct での placeholder 指定は、struct の名称直後に記述します。先の RingBuffer を Generics を使って記述すると以下のようになります。

Generics をつかった RingBuffer のテストコード

コード解説
  1. RingBuffer 初期化時には、capacity 指定だけで保持するタイプが推測できないため、明示的に Int を指定する必要があります。

RingBuffer 初期化部分以外は先のテストと同じです。

まとめ:Generic を使って、TDD で RingBuffer を作る

Generic を使って、RingBuffer を作る
  • placeholder 指定を使って、タイプを一般化できる
  • placeholder 指定されたタイプは、Swift によって推測される
  • よく使われる構造は、Generic を使って様々なタイプに対応させると、タイプごとにコードを書く必要がなくなる
MEMO
サンプルとして作成した swapValues は 同機能の swap という関数が Swift Standard Library から提供されていますので、上記実装を自分で作成する必要はありません。

説明は以上です。
不明な点やおかしな点ありましたら、こちらまで。

別記事で Generics の型に制限をつけて、機能追加する方法を説明しています。
Swift[Swift] Generics の型に制約をつけて拡張する

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です