内部イテレータを外部イテレータに変形する(その2:2分木構造の場合)

つづき。ようやく当初の目的だった木構造
配列のときと同様、目標は、以下のような2分木クラスの内部イテレータTreeNode.ForEachを元にTreeNode.ForEachIterableを作成し、外部イテレータを返すTreeNode.GetEnumeratorからTreeNode.ForEachIterableを呼ぶこと。

class Tree<T>
{
  TreeNode<T> _root;

  // ... 中略 ...

  public void ForEach(Action<T> action)
  {
    if (_root != null) _root.ForEach(action);
  }
}

class TreeNode<T>
{
  // 格納する値
  T _value;
  // 左の子
  TreeNode<T> _left;
  // 右の子
  TreeNode<T> _right;
  // 親
  TreeNode<T> _parent;

  // ... 中略 ...

  public void ForEach(Action<T> action)
  {
    if (_left != null) _left.ForEach(action);
    action(_value);
    if (_right != null) _right.ForEach(action);
  }
}

んで、今はTreeNode.ForEachとTreeNode.GetEnumeratorで呼ぶことになるTreeNode.ForEachIterableの定義でつまづいているところ。前回の配列でわかった事は、

  • IProcedureWithMemory.Process
  • IProcedureWithMemory.LastProcessedValue

を交互に呼び出せさえすれば良いということ。しかし、それがどうすれば実現できるのかまだ分かっていない。配列の例に倣って

// 第2引数は終了条件(nullをINextJobSetter.SetNextする必要があるので)
static void ForEachIterable(TreeNode<T> node, Predicate<TreeNode<T>> checkTerm, IProcedure<T> proc, INextJobSetter nextJob)
{
  if (node._left != null)
    ForEachIterable(node._left, checkTerm, proc, nextJob);

  proc.Process(node._value);

  nextJob.SetNext(
    checkTerm(node) ?
    (Action)null :
      node._right == null ?
      (Action)(() => { }) :
      (Action)(() => ForEachIterable(node._right, checkTerm, proc, nextJob)));
}

ってやってみたけど、左の子を処理している部分の再帰は一気に進んでしまう。左の子の再帰部分でも、

  1. それより後の計算をthunkに閉じ込める
  2. INextJobSetter.SetNextする
  3. 再帰から抜ける

しないといけない。


これができない時の手段としては、

  1. IProcedureWithMemory.Processの実行をthunkにしてリストとかに溜めていく
  2. ForEachが終わってから溜めといたthunkを一つずつ処理してはLastProcessedValueで取り出す

みたいな感じでいけるような気がする。だけど負けな気もするなぁ。
call/ccとか...いや、何でもない。

追記

あらかじめリストに溜めていく方法だと、木構造のノードが多いときに、メモリもりもり食ってしまうなぁ。「ツリー構造用の外部/内部イテレータの実装 - terazzoの日記」の「外部イテレータを実装 その1. 最初に全要素をスキャンして配列を作成」と同じやり方だし、今うだうだ考えているのは、これを避けたかったからなので却下だな...。
...ってか、IProcedureWithMemory.Processの実行をthunkにしてリストに溜めていくくらいだったら、処理する値を直接溜めていけばいいやんけ...。