配列との違いは何だろう
木構造の内部イテレータでつまづいている話の続き。木構造で考える前に、配列で考えていたので、それに戻ってみる。
配列をラップした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を、再帰が一気に済まないように書き換えると良いのかな...。うーむ。
これでしばらく考えてみよう。