2分木のイテレータに関して再開
数か月放置していたこのテーマ。またこの数日考え始めたけど、まだ解決してない。yield returnで2分木の外部イテレータ作れたから、考える意味なくなったけど。いや!意味がないはずはない。どこかで役に立つはず!
NextJobSetterやNextJobAccessorは、次に行うべき処理を
- 取り出す(Accessor)
- 登録する(Accessor、Setter)
ためのオブジェクトだった。でもいろいろ考えるうちに、IProcessが継続を意味するActionオブジェクトを受け取ったりし始めて、頭が混乱してきた。NextJobも「次の処理」すなわち継続を保持するためのものなのになんで型が違うの?どう使い分けるの?...とか。
ということで、継続渡しとか散々偉そうに書いてみたけど、全然理解できていないし、とりあえず継続云々みたいな難しいことは一旦忘れて、
- 次行う処理を保存
- そこから再開
- (゚д゚)ウマー
みたいな感じでいこうと思ってる。
イテレータとコルーチンが密接な関係であることがyield return抜きでようやく実感できてきた今日この頃。
さて、繰り返しになるが、ソースコードを以下に。また若干修正している。内部イテレータと外部イテレータを一気にやるとまた混乱しそうなので、内部イテレータがちゃんと動くようになってから、それを外部イテレータでも使えるようにしていこうと思う。
まずは、内部イテレータを持っていることを示すインターフェース
interface IIterableIn<T> { void ForEach(Action<T> proc); }
次の仕事を保持しておくJobHolderクラス。以前はSetterとAccessorに分けてたけど、面倒だったので統合した。
/// <summary>次の仕事を保持する</summary> class JobHolder { /// <summary>次の仕事の正体</summary> Action _job; public Action Job { get { return _job; } set { _job = value; } } }
以上の脇役を踏まえて、本題である2分木のノード。このクラスのメソッドForEachDetailがうまく作れない。
class TreeNode<T> : IIterableIn<T> { /// <summary>格納する値</summary> T _value; /// <summary>親</summary> TreeNode<T> _parent; /// <summary>左の子</summary> TreeNode<T> _left; /// <summary>右の子</summary> TreeNode<T> _right; /// <summary>コンストラクタ</summary> /// <param name="value"></param> public TreeNode(T value) { _value = value; _parent = null; _left = null; _right = null; } /// <summary>格納する値</summary> public T Value { get { return _value; } set { _value = value; } } /// <summary>親</summary> public TreeNode<T> Parent { get { return _parent; } set { _parent = value; } } /// <summary>左の子</summary> public TreeNode<T> Left { get { return _left; } set { _left = value; } } /// <summary>右の子</summary> public TreeNode<T> Right { get { return _right; } set { _right = value; } } /// <summary>内部イテレータ</summary> public void ForEach(Action<T> action) { JobHolder holder = new JobHolder(); Predicate<TreeNode<T>> checkTerm = node => node.Parent == null; ForEachDetail(this, checkTerm, action, holder); while (null != holder.Job) { holder.Job(); } } /// <summary>内部イテレータおよび外部イテレータから呼び出されるメソッド</summary> static void ForEachDetail(TreeNode<T> node, Predicate<TreeNode<T>> checkTerm, Action<T> action, JobHolder holder) { if (node._left != null) { ForEachDetail(node._left, checkTerm, action, holder); } action(node._value); if (node._right != null) { holder.Job = () => { ForEachDetail(node._right, checkTerm, action, holder); if (checkTerm(node)) holder.Job = null; }; } } }
上のコードでは、左の子を処理する再帰呼び出しの中で、右の子を処理するためにJobを登録しているけど、再帰が止まらないからJobを取り出して実行する前にまた登録して、Jobを上書きしてしまっている。その結果、再帰の内部で走査されるべき右の子が走査されない。
再帰が一気に済んでしまわないようにForEachDetailを作らないといけないんだけど、それができてないのね...。