2分木のイテレータに関して再開

数か月放置していたこのテーマ。またこの数日考え始めたけど、まだ解決してない。yield returnで2分木の外部イテレータ作れたから、考える意味なくなったけど。いや!意味がないはずはない。どこかで役に立つはず!

NextJobSetterやNextJobAccessorは、次に行うべき処理を

  • 取り出す(Accessor)
  • 登録する(Accessor、Setter)

ためのオブジェクトだった。でもいろいろ考えるうちに、IProcessが継続を意味するActionオブジェクトを受け取ったりし始めて、頭が混乱してきた。NextJobも「次の処理」すなわち継続を保持するためのものなのになんで型が違うの?どう使い分けるの?...とか。
ということで、継続渡しとか散々偉そうに書いてみたけど、全然理解できていないし、とりあえず継続云々みたいな難しいことは一旦忘れて、

  1. 次行う処理を保存
  2. そこから再開
  3. (゚д゚)ウマー

みたいな感じでいこうと思ってる。
イテレータとコルーチンが密接な関係であることが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を作らないといけないんだけど、それができてないのね...。