C#でIEnumerableインターフェースを実装してみる

※この記事は、AmusementCreators Advent Calendar 2017 の13日目の記事です。

C#でIEnumerableインターフェースの実装に関していろいろ考えてやってみました。そのメモ書きとして残しておこうかと。
※検証した環境はWindows8.1 64bit .netframework4.7 開発ツールはVS2017です(C#のバージョンはおそらく7.1)。

本記事ではインターフェースや`foreach`文についていちいち説明はしませんので、それらについてよくわからないという人は、次のサイトを見ておくことをお勧めします。
http://ufcpp.net/study/csharp/oo_interface.html
http://ufcpp.net/study/csharp/sp_foreach.html
#`Ienumerable`インターフェースとは#
Ienumerableインターフェースとは、「**コレクションに対する単純な反復処理をサポートする反復子を公開する**」インターフェースのことです。
要は「**繰り返して連続して値を読み込むことができる機能を提供する**」インターフェースのことです。
#`IEnumerable`インターフェースの構造#
IEnumerableインターフェースをコンパイルするのに必要なコードを下に示します。なお、以下`System`名前空間、`System.Collections`名前空間、`System.Collections.Generic`名前空間は`using`ディレクティブによって省略されているものとします。

```C#:IEnumerableインターフェース実装に必要な最小構造
class Array : IEnumerable
    {
        public IEnumerator GetEnumerator() { return new ArrayEnumerator(); }

        class ArrayEnumerator : IEnumerator
        {
            public Object Current { get; }
            public bool MoveNext() { return true; }
            public void Reset() { }
        }

    }

```
もちろんこのままでは使い物になりませんが、コンパイルは通ります。筆者も、はじめ見たときはあまりにシンプルで拍子抜けしてしまいました。しかしこのシンプルさこそが応用を可能にしているのではないかと思います。
`IEnumerable`インターフェースは、`IEnumerator`インターフェースを返す引数なしの関数を持ちます。また、`IEnumerator`インターフェースは上記三つのメソッドおよびプロパティを持ちます。
基本的に、コレクションに対する操作はこの`IEnumerator`インターフェース(**反復子**と呼ばれる)を介することによって行われます。筆者は、この反復子の動作がなかなか理解出来なかったのですが、反復子を「**コレクションのどのセルを指し示すかを表す矢印**」と考えたことですんなりと理解できました。
(「セル」とは、ここでは要素を格納する箱を表します。コレクションでは要素だけでなく別の値も同時に保存する必要があるので、それらが入るような箱を用意しなければいけません。詳しくは後程話します)
![IEnumerator.png](https://qiita-image-store.s3.amazonaws.com/0/214300/8b273498-fd28-ce77-ec2a-94da736ad01a.png)
この図を用いて、`IEnumerator`インターフェースの各プロパティ、メソッドの動作を説明すると、
(1)`Current`プロパティ：現在矢印の指し示す要素を保管しておくプロパティ
(2)`MoveNext`メソッド：矢印の指し示す要素を次へ移すメソッド。移動できれば`true`、できなければ`false`を返す。
(3)`Reset`プロパティ：矢印の指し示す要素を一番初めへ戻すメソッド。

となります。筆者はこのイメージで動作を理解しています。
これを見れば、`foreach`文の動作も容易に理解することができると思います。

```C#:foreach文の展開
//`foreach(型名 変数 in コレクション){文}は、次のように展開されます。
try
{
    IEnumerator e = コレクション.GetEnumerator();//(1)
    while(e.MoveNext())//(2)
    {
        型名 変数 = (型名)e.Current;//(3)
        文
    }
} 
finally
{
    //Dispose処理(4)
}
```
(1)あるコレクションに対し、矢印を作成する。
(2)矢印が次の要素へ移動できる間(最後尾の要素に達するまで)、矢印を移動し
(3)変数に、現在矢印が指し示す要素を与えられた型でキャストして代入する
(4)矢印が移動できなくなったら、必要であればリソースの破棄を行う
![IEnumerator2.png](https://qiita-image-store.s3.amazonaws.com/0/214300/da051e18-3060-38f4-e7dd-1167c034ed58.png)
図で説明すると、上のような感じになります。
`foreach`文は、`IEnumerable`インターフェースを実装した要素に対して有効であり、かつ反復子をふんだんに使っているので上で書いた各プロパティ・メソッドの動作を理解するのには有効かと思います。実際に筆者も`foreach`文を見て、なるほどと納得することができました。

#IEnumerableインターフェースを用いたコレクションクラスの作成#
上の`IEnumerator`の動作が分かったらもう簡単にコレクションクラスを自作できる、ということはないと思います。少なくとも筆者は、この記事を書いている今現在しっかり理解できていない部分も多くあります。筆者は、「理解するには実際に書いてみるべし！」という考えを持っているので、
ここでは、`IEnumerable`インターフェースを用いた片方向連結リストを作成して、理解を深めていきたいと思います。
なお、筆者はC#に精通している人ではないので、ここで書いたコードは実行速度や可読性を重視しているわけではないですがあしからず。
##(1)作成するコレクションクラスの機能##
片方向連結リストについては次のサイトを参照してください。
http://ufcpp.net/study/algorithm/col_flist.html#implどのような
アルゴリズムを学んでいる方にとってはお馴染みかもしれません。
##(2)コンパイルするための最小限のコード##
クラス名は'Array'とし、`GetEnumerator`メソッドは`IEnumerator`インターフェースを実装した`ArrayEnumerator`クラスを返します。
(`IEnumerator`インターフェースと`IEnumerator`インターフェースはジェネリックバージョンもあり、それを使用するほうが好ましいとされているようですが、めんどくさいのでここでは非ジェネリックバージョンのクラスを用いています。)

```C#:Arrayクラス
/// <summary>
/// 片方向連結リスト
/// </summary>
class Array : IEnumerable
{
    public IEnumerator GetEnumerator() { return new ArrayEnumerator(); }

    class ArrayEnumerator : IEnumerator
    {
        public Object Current { get; }
        public bool MoveNext()
        {
            return true;
        }
        public void Reset() {  }
    }
}
```
先にも書いたように、`IEnumerable`インターフェースを実装するにはこのコードは必須です。
##(3)要素を格納するクラスを実装する##
コレクションクラスは複数の要素を一つにまとめるためのクラスなので、もちろんコレクションクラスには要素を格納するためのデータ型が必要です(前に書いた要素を格納するための箱)。今回作成するコレクションクラスは、このデータ型を`Cell`クラスとして実装します。つまり、連結リストにおけるノードを`Cell`クラスに実装します。なお、`Cell`クラスは`Array`クラスの内部に記述します。

```C#:Arrayクラス(Cellクラスの追加)
class Array : IEnumerable
{
    //先頭のセルを格納するフィールド。
    private Cell Head;
    //まず、コレクションのインスタンスを生成したと同時に
    //空のセル(フィールドがnullなセル。要素の格納はできない)を作成する
    public Array() { Head = new Cell(null); }

    public IEnumerator GetEnumerator() { return new ArrayEnumerator(); }

    //ここはあくまで現在のセルの場所を示すためのものなので、
    //例えば、新たにセルを加えたりなどセルの場所を扱う必要のない操作に関しては
    //一切不要（セルを加える操作では、このコレクションの場合常に先頭に追加されるため不要）
    class ArrayEnumerator : IEnumerator
    {
        public Object Current { get; }
        public bool MoveNext()
        {
            return true;
        }
          
        public void Reset() {  }
    }

    //セル。要素と次のセルを格納するフィールドを持つ。
    public class Cell
    {
        public Object Item { set; get; }
        public Cell Next { set; get; }
        //新たにセルが作られたとき、各フィールドに値を代入する。
        //コンストラクタの引数は、セルの要素。
        public Cell(Object item)
        {
            Item = item;
        }
    }
}
```
`Cell`クラス(以下セル)は、セルの持つ要素を格納する`Item`と、次に参照するセルを格納する`Next`というプロパティを持ちます。
また、`Array`クラスは先頭のセルを格納する`Head`フィールドを持ちます。さらに、`Array`クラスのコンストラクタでは、空のセル(要素がnullなセル)を作成しています。これは矢印(反復子)次に指すセルが存在するかどうかを判断するためのものです。具体的な動作は以降の項で説明します。
##(4)セルを追加する関数を追加する##
作成するコレクションクラスによって必要な機能や仕様は変わりますが、連結リストの場合は要素の追加する機能が必要です。ここでは、要素を追加する機能を`Add`メソッドとして実装します。加えて要素を追加する際の動作も説明します。

```C#:Addメソッド
/// <summary>
/// セルを新規に追加するメソッド。
/// </summary>
//これがなくては何もできない。
public void Add(Object item)
{        
    //現在の先頭のセル(ヘッド)を一時的に保存
    Cell temphead = Head;
    //ヘッドに、新たに作成したセルを格納。
    Head = new Cell(item);
    //ヘッドのもつ、次のセルを格納するフィールドに追加するセルを代入。
    Head.Next = temphead;
}
```
Addメソッド内の動作は下の図のようになっています。
![Add.png](https://qiita-image-store.s3.amazonaws.com/0/214300/f875b485-0d92-6b69-dcbd-8522d87ac7b7.png)
図では、`Add`メソッド実行時の動作を表しています。ただし、図の上半分は新規にコレクションを作成した際の動作(空のセルの作成)を示しています。
図の`Head`は、新たに`Add`で作成したセルを格納しています。`Add`メソッドで新たなセルを追加する前に、`temphead`(図の`PreHead`)に`Head`に格納されていたセルを格納します。新たに作成されたセルは`Head`に格納され、前の先頭のセルは`Head`の`Next`プロパティに格納されています。
片方向連結リストはこのような構造になっているため、要素を先頭から順に呼び出していくことが非常に容易です。なぜなら、`Head`の中身さえわかれば、あとは`Next`の中身を順々に見ていくことで、追加したすべての要素を引き出すことができるからです。
##(5)反復子を追加する##
`Add`メソッドを導入したことで、要素の追加を可能にしました。しかしこのままでは、それらの要素を**読み取る**ことはできません。そこで、要素の読み取りをするために新たに反復子を作成します。
先に書いたように、要素へのアクセスは全て反復子を用いて行うので、読み取り機能を実装する際は必然的に反復子を使うことになります。
ここでは、反復子のクラス名を`ArrayEnumerator`とし、`Array`クラス内に記述します。
なお、`Cell`クラスも`Array`クラス内に記述していましたが、`Array`クラス外部に記述しても内部に記述した際の動作と変わりませんが、これらのクラスがそれぞれ独立していると、「`Array`クラスが使うセル、`Array`クラスが持つ反復子」というのがわかりにくくなってしまうのでそのように記述をしています。

```C#:ArrayEnumeratorクラス
class ArrayEnumerator : IEnumerator
{
    Cell CurrentCell;
    Array Array;
            
    public ArrayEnumerator(Array array)
    {        
        this.Array = array;
        CurrentCell = null;
    }

    //矢印が指し示すセルの要素を返す
    public Object Current { get { return CurrentCell.Item; } }

    //返り値は、ちゃんと動かせたかどうか。
    //true(矢印を動かせた)、false(もうこれ以上矢印を動かせない)
    public bool MoveNext()
    {
        //現在指し示しているセルの次のセル(Next)があるかどうかを調べる。、
        if (CurrentCell == null)
            //矢印の位置を初期位置(Head)に戻す。
            CurrentCell = Array.Head;
        else
            //矢印を動かす。
            CurrentCell = CurrentCell.Next;
                  
        //条件文が同じなので統合したくなるが、それはできない。
        if (CurrentCell == null)
            return false;
        return true;
    }

    //先頭位置を元に戻す
    public void Reset() { CurrentCell = null; }
}
```

この記事の「`IEnumerable`インターフェースとは」の項に載せてある画像を見ながらの方が、`ArrayEnumerator`クラスの内容を理解しやすいと思います。
まずフィールドとして、現在指し示しているセルを格納する`CurrentCell`と対象となるコレクションクラスのインスタンスを格納する`Array`を作成しました。
コンストラクタでは、引数として矢印の作成の対象となるコレクションのインスタンスを取り、矢印の先頭位置を決めます。ここで先頭位置に`Head`を指定しないのは、この後出てくる`MoveNext`メソッドで先頭のセルが読み込まれないの防ぐためです。
さて、その`MoveNext`メソッドですが、機能としては**今示されているセルが空ならば矢印を先頭に持っていき、あれば次のセルに矢印を移し**、**もしその矢印が何のセルも示していなければfalse、何らかのセルを指していればtrueを返す**というものです。なぜ`bool`値を返すのかは、`foreach`文の内部構造を見るとはっきりすると思います。この機能からもわかるように`MoveNext`メソッドが、読み取り機能の中核をなしているといっても過言ではありません。
`Current`メソッドと、`Reset`メソッドについてはそこまで難しいことはしていないので特に説明はしません。

最後にこれまでのコードをまとめておきます。このクラスの変更に伴って`Array`クラス自身の内容も少し変更したので確認してみてください。

```C#:Arrayクラス(完成形)
/// <summary>
/// 片方向連結リスト
/// </summary>
class Array : IEnumerable
{
    //先頭のセルを格納するフィールド。
    private Cell Head;

    //空のセル(フィールドがnullなセル。要素の格納はできない)を作成する
    public Array() { Head = new Cell(null); }

    public IEnumerator GetEnumerator() { return new ArrayEnumerator(this); }//

    //反復子のクラス
    class ArrayEnumerator : IEnumerator
    {
        Cell CurrentCell;
        Array Array;
            
        public ArrayEnumerator(Array array)
        {
            this.Array = array;
            //初めにどのセルを指し示すのかを決める。          
            CurrentCell = null;
        }
        //現在指し示されているセルの要素を返す
        public Object Current { get { return CurrentCell.Item; } }

        //返り値のbool値は、ちゃんと動かせたかどうかという情報。
        //true(矢印を動かせた)、false(もうこれ以上矢印を動かせない)
        public bool MoveNext()
        {
            //現在指し示しているセルの次のセル(Next)があるかどうかを調べる。、
            if (CurrentCell == null)
                //矢印の位置を初期位置(Head)に戻す。
                CurrentCell = Array.Head;
            else
                //矢印を動かす。
            CurrentCell = CurrentCell.Next;
                   
            //条件文が同じなので統合したくなるが、それはできない。
            if (CurrentCell == null)
                return false;
            return true;

        }
        //先頭位置を元に戻す
        public void Reset() { CurrentCell = null; }
    }

    //セル。要素と次のセルを格納するフィールドを持つ。
    public class Cell
    {
        public Object Item { set; get; }
        public Cell Next { set; get; }

        //新たにセルが作られたとき、各フィールドに値を代入する。
        public Cell(Object item)
        {
            Item = item;
        }
    }

    /// <summary>
    /// セルを新規に追加するメソッド。
    /// </summary>
    public void Add(Object item)
    {
        //現在のヘッドを一時的に保存
        var temphead = Head;
        //先頭のセルを、追加したセルに切り替える。
        Head = new Cell(item);
        //先頭のセルのもつ、次のセルを格納するフィールドに追加するセルを代入。
        Head.Next = temphead;
    }
}
```

`Array`クラスが完成しましたが、このままでは機能としては貧弱すぎてほとんど使い物になりません(これと完全上位互換なコレクションクラスに`List<T>`クラスが存在します)。
実際に`IEnumerable`インターフェースを実装する際には、例えばコレクションを任意の順にソーティングする機能をつけるなどの機能追加や、各セルに対しインデックスを関連付けるなどして独自の機能や仕様を追加すると思います。
#まとめ#
ここまで説明してきましたが、実際筆者はこの記事を書く直前まで`IEnumerable`インターフェースの仕組みや実装方法についてほとんどわかっていませんでした。そのため、この記事を書きながらこのインターフェースについて勉強し、自分なりにこういうことではないかというのを考えながら書いていました。「ちゃんと理解してから書けよ！」と言われそうですが、自分では書いているうちにだんだんと理解できたのでまあいいか、と思っています。
#追記#
ある方がコメントで教えてくださったのですが、現在ではこれまで筆者が書いてきたような実装の仕方はほとんどされておらず、通常反復子を`yield return`を用いて書き、かつ`IEnumerable`インターフェースではなく、そのジェネリックバージョンの`IEnumerable<T>`インターフェースを実装するそうです。
実際にコレクションクラスを自作する際はこれらのことに注意したほうがいいと思います。