あなたの知らないCollectionの世界

[collection]: http://swiftdoc.org/v3.0/protocol/Collection/

この投稿は「Swift Advent Calendar 2016」 8日目のものです。

~~今日が火曜日だったら完璧だったのに...~~
今回は「あなたの知らない[`Collection`][collection]の世界」というテーマでお送りします。

##### 環境
- Xcode8.1
- Swift3.0.1

## そもそも[`Collection`][collection] (protocol) って
> (シーケンスの持つ)要素(element)が複数回、非破壊的に走査することができて、インデックスされた添字によってアクセスできるシーケンス

のことを指すようです。(ちょっと訳が怪しい... :pray: )
普段何気なく使っている`Array`もこの`Collection`（正確には MutableCollection protocolですが) に適合しています。`Dictionary`や`Set`なんかも。

## Collection protocolの継承図

<img width="239" alt="スクリーンショット 2016-12-03 11.13.08.png" src="https://qiita-image-store.s3.amazonaws.com/0/27802/ab2b1c47-b053-d218-7131-fa740a9d3e89.png">

`Collection` 自体は、 `Indexable` と `Sequence` を継承(に適合) しています。
それ以降はこの`Collection`をベースに多岐に渡って様々な*protocol*、*struct*に展開されていきます。  
最終的には`Array`や`Dictionary`、`Set`、`AnyCollection`、Stringの`CharacterView`などに辿り着きます。
横に長いので、見たい方は↓をご覧ください。

- [継承図](http://swiftdoc.org/v3.0/protocol/Collection/hierarchy/)

## Collectionに適合していると何ができるのが
Collectionに適合していると、以下のようなことができます

- 「for in」文で列挙ができる
- 定められた添字でアクセスができる (e.g. `array[0]`)
- 要素の数を調べることができる (*count*, *isEmpty*など)
- *filter*, *map*, *flatMap*, *reduce*, *sort*などの関数が使える

などなど。(※一部、`Sequence`のみでもできることがあります)
基本的には`Array`や`Dictionary`で普段使っていると思うので、馴染みがあるのではと思います。

## Collectionを自作の型で使ってみる
試しに`Collection`に適合させた自作の型を作ってみます

### FizzBuzzを`Collection`で

FizzBuzzをCollectionで作ってみます。  
`limit`を与えることで、1〜`limit`(limit含む)をFizz,Buzzを使って表せるCollectionとして定義してみます。

```swift
struct FizzBuzzCollection: Collection {

    typealias _Element = String
    typealias Index = Int
    
    var startIndex: Index { return 0 }
    var endIndex: Index { return limit }
    
    let limit: Int
    
    subscript (position: Index) -> _Element {
        precondition((startIndex..<endIndex) ~= position, "Index out of bounds.")
        let num = position + 1
        switch (num % 3, num % 5) {
        case (0, 0): return "Fizz Buzz"
        case (0, _): return "Fizz"
        case (_, 0): return "Buzz"
        default: return "\(num)"
        }
    }
    
   func index(after i: Index) -> Index {
        precondition(i < endIndex, "Can't advance beyond endIndex")
        return i + 1
    }
}
```

### 使ってみる

```swift
let fizzbuzzCollection = FizzBuzzCollection(limit: 100)
fizzbuzzCollection.forEach { print($0) }
//1
//2
//Fizz
//4
//Buzz
//Fizz
//...
//98
//Fizz
//Buzz

print(fizzbuzzCollection[4]) // -> "Buzz"
print(fizzbuzzCollection.first as Any) // -> Optional("1")
```

### `Collection`に適合するために必要な定義
`Collection` に適合するためには、少なくとも以下の定義が必要になってきます。

```swift
// 要素の始点(Index型)を返す
var startIndex: Self.Index { get }

// 要素の終点(Index型)を返す
var endIndex: Self.Index { get }

// あるindexの次のindex(Index型)を返す
func index(after i: Self.Index) -> Self.Index

// Index型の添字でアクセスを可能にするsubscript
subscript(position: Self.Index) -> Self.Iterator.Element { get }
```

実はこれらが決まることで、本来は定義が必須となっていますが、以下のものも定まるようになります。

```swift
var indices: Self.Indices { get }
subscript(bounds: Range<Self.Index>) -> Self.SubSequence { get }
func makeIterator() -> Self.Iterator
```

最初、必須だよと書かれてるものが多くて定義大変じゃね...って思っていたのですが、この3つはその上の４つが決まると良いようです :thinking: 

また、 `Index`及び`Element`の型が何であるかtypealiasで定義する必要があります

```swift
typealias Element = String
typealias Index = Int
```

ただ、こちらも以下のようにそれぞれの関数で型を正確に与えてあげることで`Index`及び`Element`の型が定まるので、`typealias`での定義は不要になります。

```swift
struct FizzBuzzCollection: Collection {
    
    var startIndex: Int { return 0 }
    var endIndex: Int { return limit }
    
    let limit: Int
    
    subscript (position: Int) -> String {
        precondition((startIndex..<endIndex) ~= position, "Index out of bounds.")
        let num = position + 1
        switch (num % 3, num % 5) {
        case (0, 0): return "Fizz Buzz"
        case (0, _): return "Fizz"
        case (_, 0): return "Buzz"
        default: return "\(num)"
        }
    }
    
   func index(after i: Int) -> Int {
        precondition((startIndex..<endIndex) ~= position, "Index out of bounds.")
        return i + 1
    }
}
```

個人的には、最初に`typealias`で型を書いて...としたほうが宣言時は分かりやすいのですが、使う時に`_Element`みたいに見えてしまうので、後者の書き方のほうが好きです :v_tone1:
<br />

また、注意点としては、`subscript`や`index(after:)`では範囲外になってしまうかどうかの判定をしてあげると良いでしょう。

```swift
subscript (position: Index) -> _Element {
    precondition((startIndex..<endIndex) ~= position, "Index out of bounds.")
    ...
}

func index(after i: Index) -> Index {
    precondition(i < endIndex, "Can't advance beyond endIndex")
    ...
}


let fizzbuzzCollection = FizzBuzzCollection(limit: 100)
fizzbuzzCollection[99] // -> "Buzz"
fizzbuzzCollection[100] // => Error! "Index out of bounds."
```

##### 余談
ちなみに、`(startIndex..<endIndex) ~= position`の部分を、`indices.contains(position)`なんてちょっと格好つけてしまうとここに計算コストがかかってしまって遅くなってしまうので注意です。(本人談)

### first, lastを取得する

FizzBuzzCollection は `Collection`に適合させているので、要素の最初、最後を取得するのは簡単...! :star2: 


```swift
let fizzbuzzCollection = FizzBuzzCollection(limit: 100)
print(fizzbuzzCollection.first as Any) // => "Optinal("1")"
print(fizzbuzzCollection.last as Any) // ... Error!
```

あれ、 **<font color="red">lastが取れない...だと。</font>**
[document][collection]を読んでみると、*first*はあるけど、*last*がない...

### *last*を使えるようにする
`last`を使えるようにするには、 `Collection`を`BidirectionalCollection`にしてあげる必要があります。

```swift
struct FizzBuzzCollection: BidirectionalCollection {
    // ...
}
```

そうすると、

```swift
// 指定したindex(i)の前のindexを取得する
func index(before i: Index) -> Self.Index
```

*index(before:)*を実装しろと言われるので実装します。

```swift
struct FizzBuzzCollection: BidirectionalCollection {
    func index(before i: Int) -> Int {
        precondition(startIndex <= i, "Can't back beyond startIndex")
        return i - 1
    }
}
```

これで、*last*が晴れて使えるようになります :clap_tone1: 

```swift
let fizzbuzzCollection = FizzBuzzCollection(limit: 100)
print(fizzbuzzCollection.first as Any) => "Optinal("1")"
print(fizzbuzzCollection.last as Any) ... Error!
```


継承図を見るとこんな感じ。`Collection`と`BiDirectionalIndexable`を継承しています。

<img width="322" alt="スクリーンショット 2016-12-03 18.07.20.png" src="https://qiita-image-store.s3.amazonaws.com/0/27802/6d48849a-7582-85c7-30f2-5993479e6ac2.png">

ここまで扱えるようになれば自作のCollectionとしては十分なものとなったと思います。
もし、要素へのランダムアクセスに関して適切な計算量で行える実装ができる場合には、 `RandomAccessCollection` として実装してみてもよいかもしれません。
`BidirectionalCollection` と比べて必須の実装は増えませんが、
*index(_:offsetBy:)*, *distance(from: to:)* といったメソッドを計算量 *O(1)* で実装できるのが望ましいようです。

## ちなみにArrayは...

今回は`BidirectionalCollection` まで話が進みましたが、更に進めていくとArrayにたどり着くことができます。

<img width="1478" alt="スクリーンショット 2016-12-03 18.19.31.png" src="https://qiita-image-store.s3.amazonaws.com/0/27802/2634b4a1-26a7-df10-a6a2-9cf945a9d76c.png">

普段何気なく使っているArrayも、このようにいくつものprotocolを経て成り立っているのがわかります。
そして、改めてprotocol指向なんだなと思い知らされます :laughing: 

## AnyCollectionとは... :thinking: 
`AnyCollectionは`、`Collection`を継承していて、`Collection`を型消去して扱うことができるようになる*struct*です。
おっと... **型消去** がでてきましたね。
型消去に関しては[平常心で型を消し去る](https://realm.io/jp/news/tryswift-gwendolyn-weston-type-erasure/)を見るのをおすすめします。(説明は割愛...)

何に使うのかというと、例えば外から`FizzBuzzCollection`という実装を隠したいが、外からはちゃんとこの`Collection`を使いたいという場合に、この `AnyCollection` を使ってあげます。

```swift
class MyCollections {
    lazy var fizzBuzzCollection: AnyCollection<String> = AnyCollection(FizzBuzzCollection(limit: 100))
    
    // これはNG。
    lazy var fizzBuzzCollection: Collection = FizzBuzzCollection(limit: 100)
}
```

こうすることで、`MyCollections`を外から生成して`fizzBuzzCollection`を見るときには、`FizzBuzzCollection`という型は見えず、`AnyCollection<String>`という型で見えるようになり、型を隠蔽することができます。

<img width="299" alt="スクリーンショット 2016-12-04 1.38.50.png" src="https://qiita-image-store.s3.amazonaws.com/0/27802/a4280a1b-94ff-5de8-2024-bc25fda5bf13.png">

もう一つの使い方としては、例えばFizzBuzzCollectionと同じく要素が`String`の`PPAPCollection`があったとしましょう。

```swift
struct PPAPCollection: Collection {
    
    // P-P-A-Pの順で要素をいれる
    let elements: (String, String, String, String)
    init(_ first: String, _ second: String, _ third: String, _ fourth: String) {
        self.elements = (first, second, third, fourth)
    }
    
    var startIndex: Int { return 0 }
    var endIndex: Int   { return 4 }
    
    subscript(index: Int) -> String {
        switch index {
        case 0: return elements.0
        case 1: return elements.1
        case 2: return elements.2
        case 3: return elements.3
        default: fatalError("Index out of bounds.")
        }
    }
    
    func index(after i: Int) -> Int {
        precondition(i < endIndex, "Can't advance beyond endIndex")
        return i + 1
    }
    
    var ppap: String {
        return [elements.0, elements.1, elements.2, elements.3].map {
            $0.capitalized
        }.joined(separator: "-")
    }
}

let ppapCollection = PPAPCollection("pen", "pineapple", "apple", "pen")
print(ppapCollection.ppap)
// => Pen-Pineapple-Apple-Pen!
```

どちらもfunnyなcollectionということで、これらをまとめる配列を作るとします。

このときに `[Collection]`としてまとめることができないので、 **`[AnyCollection<String>]`** としてAnyCollectionに包んであげることで型消去しつつまとめてあげることができます。

```swift
var NG_funnyCollections: [Collection] = [
    FizzBuzzCollection(limit: 100),
    PPAPCollection("pen", "pineapple", "apple", "pen")
]
// Protocol 'Collection' can only be used as a generic constraint because it has Self or associated type requirements と怒られる

var funnyCollections: [AnyCollection<String>] = [
    AnyCollection(FizzBuzzCollection(limit: 100)),
    AnyCollection(PPAPCollection("pen", "pineapple", "apple", "pen"))
]
// AnyCollectionとして包んであげることで、どちらも要素が`String`であるCollectionをまとめられた！
```

ちなみに、`AnyCollection<Any>` みたいにして何でも...というわけにはいかないので注意です :pray: 

## 

## 内部にlistを所有するようなCollectionを自作してみる
今度は内部にlist(Array)を持つ`Collection`を自作してみます。
本を表す型*Book*と、本棚を表す型*BookShelf*を用意し、*BookShelf*に`BidirectionalCollection`を適合してみます

```swift
struct Book {
    let title: String
    let content: String
}

struct BookShelf: BidirectionalCollection {
    
    private let list: [Book]
    
    let title: String
    
    
    init(title: String, list: [Book]) {
        self.title = title
        self.list = list
    }
    
    var startIndex: Int { return self.list.startIndex }
    var endIndex: Int { return self.list.endIndex }
    
    subscript (position: Int) -> Book {
        return list[position]
    }
    
    func index(after i: Int) -> Int {
        return self.list.index(after: i)
    }
    
    func index(before i: Int) -> Int {
        return self.list.index(before: i)
    }
}
```

### 使ってみる

### Collectionを使うメリット
この例だと、使うメリットはなんなのかと言われると、 Array **+ α**をもつ型として定義できるところかと思います。
Collectionを適合させた場合とそうでない場合を比較すると、

```swift
let shelf = BookShelf(title: "swiftの本棚", list: ["The Swift Programming Language"])
// 適合させていない場合
shelf.list.forEach { book in prnt(book.title) }
let firstBook: Book? = Shelf.list.first

// 適合させた場合
shelf.forEach  { book in prnt(book.title) }
let firstBook: Book? = shelf.first
```

`Shelf.list`でもいいじゃんという感じもしますが、その型自身を`Collection`と見立てて操作ができるので個人的には良いなと思います。

あとは、以下のような感じで何かしらのモデルをまとめつつ、他の **+α** をもつときに、`Collection`化してあげることで、
`models.list` みたいな冗長さを解消できると思います。

```swift
struct SomeViewModels {
    private let id: Int
    private let models: [SomeViewModel]
}

let models = SomeViewModels(id: 1, models: [SomeViewModel(),...])
models.id
models.list.forEach { model in ... } // models.listってちょっと冗長的
```

- Collection化すると...

```swift
struct SomeViewModels {
    private let id: Int
    private let models: [SomeViewModel]
}

let models = SomeViewModels(id: 1, models: [SomeViewModel(),...])
models.id
models.forEach { model in ... } // 冗長さを感じなくなった!
```

とはいいつつも、使い所が難しいかもしれないです。が、やはり内部に持つ`list`(配列)を外から見えなくしつつ、その型を`Collection`として扱えるのは良いのかもしれません。

## その他Documentを見て気になったもの

どうやら、Swift4で `IndexableBase, Indexable, BidirectionalIndexable, RandomAccessIndexable`などが削除されるようなので、もし使ってる場合は今のうちに代案がないか考えておきましょう...!

http://swiftdoc.org/v3.0/protocol/IndexableBase/

> Deprecated: it will be removed in Swift 4.0. Please use 'Collection' instead.

一応、 `InedexableBase, Indexable`の場合は`Collection`を使えと書いてあります :star2:

## まとめ
普段使っているArrayやDictionaryの先祖を辿ってみる、実際にprotocolを適合させた自作の型を使ってみると理解が深まりますね！
本当は`SubSequence`とか`Iterator`とかまで深掘りしたかったのですが、迷宮入りしそうだったので今回は諦めて、なるべくそれを今回は意識しなくて済むようにさせて頂きました :pray: 
今回自分でまとめるまで、`AnyCollection`ってなんぞや?って感じだったので、勉強にもなりました。
また、自作の型にCollectionを適合させる場合には、範囲外アクセスしてしまわぬよう気をつけましょう。 :dizzy_face:

何かあれば気軽に編集リクエストとかでもお投げください。

## 参考
- [swiftdoc](http://swiftdoc.org/v3.0/)
- [Collection][collection]

## おまけ
`Collection`とはちょっと離れますが、`Iterator`だけを使って`FizzBuzz`もできるよということで貼っておきます。

```swift
let makeFizzBuzzIterator: (Int) -> AnyIterator<String> = { limit in
    var index = 0
    return AnyIterator<String> {
        defer { index += 1 }
        if index < limit {
            let num = index + 1
            switch (num % 3, num % 5) {
            case (0, 0): return "Fizz Buzz"
            case (0, _): return "Fizz"
            case (_, 0): return "Buzz"
            default: return "\(num)"
            }
        } else {
            return nil
        }
    }
}

makeFizzBuzzIterator(100).forEach { print($0) }
```