内部イテレータを外部イテレータに変形する(その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))); }
ってやってみたけど、左の子を処理している部分の再帰は一気に進んでしまう。左の子の再帰部分でも、
- それより後の計算をthunkに閉じ込める
- INextJobSetter.SetNextする
- 再帰から抜ける
しないといけない。
これができない時の手段としては、
- IProcedureWithMemory.Processの実行をthunkにしてリストとかに溜めていく
- ForEachが終わってから溜めといたthunkを一つずつ処理してはLastProcessedValueで取り出す
みたいな感じでいけるような気がする。だけど負けな気もするなぁ。
call/ccとか...いや、何でもない。
追記
あらかじめリストに溜めていく方法だと、木構造のノードが多いときに、メモリもりもり食ってしまうなぁ。「ツリー構造用の外部/内部イテレータの実装 - terazzoの日記」の「外部イテレータを実装 その1. 最初に全要素をスキャンして配列を作成」と同じやり方だし、今うだうだ考えているのは、これを避けたかったからなので却下だな...。
...ってか、IProcedureWithMemory.Processの実行をthunkにしてリストに溜めていくくらいだったら、処理する値を直接溜めていけばいいやんけ...。