内部イテレータできた!
ForEachDetailLeftとForEachDetailRightを単純に組み合わせてできるわけじゃなかった。だけどヒントにはなった気がする。やり方は違うけど、結果的に 木構造の外部イテレータ - チキン煮込みチーズミックス4辛 となんか似てる。何がって言われてもよくわからんけど。
ちなみに、前回の状態からこれができるまで、約3時間も費やしております。すばやくなんてできないよ...。
ソースコードは以下。TreeNode
/// <summary>内部イテレータ</summary> public void ForEach(Action<T> action) { JobHolder holder = new JobHolder(); ForEachDetail(this, action, holder, null); while (null != holder.Job) { holder.Job(); } } /// <summary>委譲される手続きの入口</summary> static void ForEachDetail( TreeNode<T> root, Action<T> action, JobHolder holder, Action cont) { // rootを根とする部分木の、最小のノードを見つける TreeNode<T> leftmost = root; while (leftmost._left != null) leftmost = leftmost._left; // 見つけたノードから走査開始 // contは、この部分木の走査が終了したあとにすべきこと // 例)この部分木を包むひとつ上の部分木の走査を開始する AtLeftMost(leftmost, action, holder, cont); } static void AtLeftMost( TreeNode<T> leftmost, Action<T> action, JobHolder holder, Action cont) { action(leftmost._value); if (leftmost._parent != null) { if (leftmost == leftmost._parent._left) { holder.Job = () => OnTheWay(leftmost._parent, action, holder); } else { holder.Job = cont; } } else { holder.Job = null; } } static void OnTheWay(TreeNode<T> node, Action<T> action, JobHolder holder) { action(node._value); if (node._right != null) { TreeNode<T> nextRoot = GetNextRoot(node); if (nextRoot == null) { // 出口はここしかない? // ForEachでForEachDetailに渡したnullは使われないな... holder.Job = () => ForEachDetail(node._right, action, holder, null); } else { holder.Job = () => ForEachDetail( node._right, action, holder, () => OnTheWay(nextRoot, action, holder)); } } else { if (node._parent != null) { holder.Job = () => OnTheWay(node._parent, action, holder); } else { holder.Job = null; } } } static TreeNode<T> GetNextRoot(TreeNode<T> node) { while (node._parent != null) { if (node._parent._left == node) return node._parent; node = node._parent; } return null; }
実際に動かしてみた → http://ideone.com/zbXa5
あとはこれを外部イテレータにするだけ。