[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 の RingBuffer
    var sut = RingBufferInt(capacity: 4)

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

データ追加

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


    var sut = RingBufferInt(capacity: 4)
    // RingBuffer に 0 追加
    sut.write(0)
    // RingBuffer に 1 追加
    sut.write(1)

保持データ数

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

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


    var sut = RingBufferInt(capacity: 4)
    sut.write(0)
    sut.write(1)
    // count で 保持しているデータ数を返却
    XCTAssertEqual(sut.count, 2)

データ参照

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

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


    var sut = RingBufferInt(capacity: 4)
    sut.write(0)
    sut.write(1)
    sut.write(2)
    XCTAssertEqual(sut.count, 3)

    // 最も古いデータを参照 (i.e. 0)
    XCTAssertEqual(sut[sut.oldestIndex], 0)
    // 最も新しいデータを参照 (i.e. 2)
    XCTAssertEqual(sut[sut.latestIndex], 2)

エラー処理

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

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

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


    var sut = RingBufferInt(capacity: 4)
    sut.write(0)
    sut.write(1)
    sut.write(2)

    // [5] は存在しないので、nil が返される
    XCTAssertNil(sut[5])

テストコード

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


    func test_write_writeWithinCapacity_shouldKeepAsIs() throws {
        var sut = RingBufferInt(capacity: 4)
        sut.write(0)
        sut.write(1)
        sut.write(2)

        XCTAssertEqual(sut.count, 3)
        XCTAssertEqual(sut[sut.oldestIndex], 0)
        XCTAssertEqual(sut[sut.oldestIndex+1], 1)
        XCTAssertEqual(sut[sut.oldestIndex+2], 2)

        XCTAssertEqual(sut[sut.latestIndex], 2)
        XCTAssertEqual(sut[sut.latestIndex-1], 1)
        XCTAssertEqual(sut[sut.latestIndex-2], 0)

        XCTAssertNil(sut[5])
    }

    func test_write_writeMoreThanCapacity_shouldKeepOnlyCapacity() throws {
        var sut = RingBufferInt(capacity: 4)
        sut.write(0)
        sut.write(1)
        sut.write(2)
        sut.write(3)
        sut.write(4)

        XCTAssertEqual(sut.count, 4)

        XCTAssertEqual(sut[sut.oldestIndex  ], 1)
        XCTAssertEqual(sut[sut.oldestIndex+1], 2)
        XCTAssertEqual(sut[sut.oldestIndex+2], 3)
        XCTAssertEqual(sut[sut.oldestIndex+3], 4)

        XCTAssertEqual(sut[sut.latestIndex  ], 4)
        XCTAssertEqual(sut[sut.latestIndex-1], 3)
        XCTAssertEqual(sut[sut.latestIndex-2], 2)
        XCTAssertEqual(sut[sut.latestIndex-3], 1)
    }

実装 : RingBufferInt

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


public struct RingBufferInt {
    let capacity: Int
    private var buffer:[Int?]
    private(set) public var latestIndex: Int = -1
    private(set) public var oldestIndex: Int = 0
    
    public var count: Int {
        return (latestIndex - oldestIndex + 1)
    }
    
    public init(capacity: Int) {
        self.capacity = capacity
        self.buffer = Array(repeating: nil, count: capacity)
    }
    
    public mutating func write(_ value: Int) {
        latestIndex += 1
        buffer[latestIndex % capacity] = value
        
        if capacity < count {
            oldestIndex += 1
        }
    }
    
    subscript(index: Int) -> Int? {
        get {
            guard (oldestIndex <= index && index <= latestIndex) else { return nil }
            guard let value = buffer[index % capacity] else { return nil }
            return value
        }
    }
}

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

Ring Buffer の複数タイプ対応

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

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

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

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

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

Generics

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

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

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


func swapTwoInt(_ valueA: inout Int,_ valueB: intout Int) {
    let tempA = valueA
    valueA = valueB
    valueB = tempA
    return
}

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


var intA = 3
var intB = 5
swapTwoInt(&intA, &intB)

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

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

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

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

Generics を使った関数

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


func swapTwoValues(_ valueA: inout T, _ valueB: inout T) {
    let tempA = valueA
    valueA = valueB
    valueB = tempA
}

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

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

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

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

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

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


var intA = 3
var intB = 5
swapTwoValues(&intA, &intB)

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

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


var intA = 3
var intB = 5
swapTwoValues(&intA, &intB) //  は、Swift が推測してくれる

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


var intA = 3
var intB = 5
var intC = 4.0
swapTwoValues(&intA, &intC)
// Error: Cannot convert value of type 'Double' to expected argument type 'Int'

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

Generics を使った struct

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

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


public struct RingBuffer {
    let capacity: Int
    private var buffer:[T?]
    private(set) public var latestIndex: Int = -1
    private(set) public var oldestIndex: Int = 0
    
    public var count: Int {
        return (latestIndex - oldestIndex + 1)
    }
    
    public init(capacity: Int) {
        self.capacity = capacity
        self.buffer = Array(repeating: nil, count: capacity)
    }
    
    public mutating func write(_ value: T) {
        latestIndex += 1
        buffer[latestIndex % capacity] = value
        
        if capacity < count {
            oldestIndex += 1
        }
    }
    
    subscript(index: Int) -> T? {
        get {
            guard (oldestIndex <= index && index <= latestIndex) else { return nil }
            guard let value = buffer[index % capacity] else { return nil }
            return value
        }
    }
}

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


    func test_write_writeWithinCapacity_shouldKeepAsIs() throws {
        // (1)
        var sut = RingBuffer(capacity: 4)
        sut.write(0)
        sut.write(1)
        sut.write(2)

        XCTAssertEqual(sut.count, 3)
        XCTAssertEqual(sut[sut.oldestIndex], 0)
        XCTAssertEqual(sut[sut.oldestIndex+1], 1)
        XCTAssertEqual(sut[sut.oldestIndex+2], 2)

        XCTAssertEqual(sut[sut.latestIndex], 2)
        XCTAssertEqual(sut[sut.latestIndex-1], 1)
        XCTAssertEqual(sut[sut.latestIndex-2], 0)

        XCTAssertNil(sut[5])
    }

    func test_write_writeMoreThanCapacity_shouldKeepOnlyCapacity() throws {
        // (1)
        var sut = RingBufferInt(capacity: 4)
        sut.write(0)
        sut.write(1)
        sut.write(2)
        sut.write(3)
        sut.write(4)

        XCTAssertEqual(sut.count, 4)

        XCTAssertEqual(sut[sut.oldestIndex  ], 1)
        XCTAssertEqual(sut[sut.oldestIndex+1], 2)
        XCTAssertEqual(sut[sut.oldestIndex+2], 3)
        XCTAssertEqual(sut[sut.oldestIndex+3], 4)

        XCTAssertEqual(sut[sut.latestIndex  ], 4)
        XCTAssertEqual(sut[sut.latestIndex-1], 3)
        XCTAssertEqual(sut[sut.latestIndex-2], 2)
        XCTAssertEqual(sut[sut.latestIndex-3], 1)
    }
コード解説
  1. RingBuffer 初期化時には、capacity 指定だけで保持するタイプが推測できないため、明示的に Int を指定する必要があります。

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

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

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

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

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

コメントを残す

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