配列との違いは何だろう

木構造の内部イテレータでつまづいている話の続き。木構造で考える前に、配列で考えていたので、それに戻ってみる。

配列をラップしたMyArrayクラスのソースコードは以下の通り。

class MyArray<T> : IIterableIn<T>
{
  T[] _ar;

  public MyArray(T[] ar)
  {
    _ar = ar;
  }

  public T this[int index]
  {
    get { return _ar[index]; }
    set { _ar[index] = value; }
  }

  public int Count
  {
    get { return _ar.Length; }
  }

  public void ForEach(Action<T> action)
  {
    JobHolder holder = new JobHolder();
    ForEachDetail(0, this, action, holder);
    while (null != holder.Job)
    {
      holder.Job();
    }
  }

  static void ForEachDetail(int i, MyArray<T> ar, Action<T> action, JobHolder holder)
  {
    if (i >= ar.Count)
    {
      holder.Job = null;
    }
    else
    {
      action(ar[i]);

      if (ar.Count <= i + 1)
      {
        holder.Job= null;
      }
      else
      {
         holder.Job =
           () => ForEachDetail(
           i + 1,
           ar,
           action,
           holder);
      }
    }
  }
}

IIterableIn、JobHolderは 前回のエントリ と同じ。

さて、配列の時と何が違うのか考えてみる。NextJobHolderを導入した動機は、再帰が一気に済んでしまわないように堰き止めることだった。配列の場合は、ForEachDetail内部でのForEachDetailの呼び出しが1回だけだったから、

  • 要素を処理する
  • 次の処理を登録する
  • ForEachDetailから抜ける

がとてもシンプルだった。
しかし、木構造はForEachDetailの呼び出しが2回あって、その間に要素を処理するところがある。なんじゃこりゃ。通りがけ順の走査だから面倒なのかな?いや、違うと思うなぁ...。

配列では再帰が一気に済まないようにForEachからForEachDetailを呼び出しているんだけど、木構造でもこれに倣って、ForEachDetail内部での左の子を処理する部分のForEachDetailを、再帰が一気に済まないように書き換えると良いのかな...。うーむ。
これでしばらく考えてみよう。