ツリー構造をなすクラスを作る

前書き

C#にはツリー構造を扱うクラスが用意されていないので5年くらい前に自作しました。nugetにアップロードして自分で使うオレオレらいぶらりー。
しばらくコードを書くこと自体がなかったけど最近また書き始めて、そのライブラリを久々に使ってみるとバグが見つかったり、使いにくかったり、分かりにくい表現だったり。
そんな、自分しか使っていないと思ったライブラリが何方か存じませんがダウンロードされているらしいんですよ。

これ、何かの間違いです？ホントにダウンロードされてる？
であれば雑な作りで申し訳ないというか...。

という前置きがありましてオレオレらいぶらりーを少しはまともなライブラリにしてみようと思い立ったのです。
何分一人であれこれ考えたり忘れたりまた同じこと考えたりしてるので、使用例、考えた過程と結果、考えきれてないことやらを記しておこうと思った次第。

今現在作りかけですが見切り発車です。

Nuget-TreeStructures

参考にしたページ

IT用語辞典：木構造 【tree structure】 ツリー構造
Wikipedia：Compositeパターン
Wikipedia：木構造
やってみる：C#ツリー構造のインタフェースを考える
雨の歌をいつか書く：ツリー構造クラスの自作
ドクロモエ：C# でツリー構造のデータを使う
Introduction to Tree – Data Structure and Algorithm Tutorials
とそのリンク先など

使用例

何はともあれ、まずは木を作って表示させてみます。

//ノードを定義
public class ExampleNode : TreeNode<ExampleNode> {
    public ExampleNode() { }
    public string Name { get; set; }
}

追加メソッドでちまちま追加する

public static partial class CreateTreeExample {
    public static void CreateSample() {
        var A = new ExampleNode { Name = "A" };
        var B = new ExampleNode { Name = "B"};
        var C = new ExampleNode { Name = "C"};
        var D = new ExampleNode { Name = "D"};
        var E = new ExampleNode { Name = "E"};
        var F = new ExampleNode { Name = "F"};
        var G = new ExampleNode { Name = "G" };
        var H = new ExampleNode { Name = "H"};
        var I = new ExampleNode { Name = "I"};
        var J = new ExampleNode { Name = "J" };
        var K = new ExampleNode { Name = "K" };
        var L = new ExampleNode { Name = "L"};
        var M = new ExampleNode { Name = "M"};
        var N = new ExampleNode { Name = "N"};
        var O = new ExampleNode { Name = "O"};
        var P = new ExampleNode { Name = "P"};

        Console.WriteLine("AddChildメソッドで組み立てる");
        A.AddChild(B).AddChild(C).AddChild(D);
        B.AddChild(E).AddChild(F);
        F.AddChild(G).AddChild(H);
        C.AddChild(I);
        I.AddChild(J).AddChild(K).AddChild(L);
        D.AddChild(M);
        M.AddChild(N);
        N.AddChild(O).AddChild(P);

        Console.WriteLine(A.ToTreeDiagram(x => x.Name));
        Console.WriteLine("高さ、レベル、ノードインデックスも追加で表示");
        Console.WriteLine(A.ToTreeDiagram(x => $"Name:{x.Name},Height:{x.Height()},Depth:{x.Depth()},NodeIndex:{x.NodeIndex()}"));
        A.Disassemble();//全て分解
        Console.ReadLine();

NodeIndexを指定したDictionaryから作成

        Console.WriteLine("インデックスを指定したDictionaryから組み立てる");
        var dic = new Dictionary<int[], ExampleNode>() {
            [new int[] { }] = A,
            [new int[] { 0 }] = I,
            [new int[] { 0, 0 }] = C,
            [new int[] { 0, 1 }] = L,
            [new int[] { 0, 0, 0, }] = D,
            [new int[] { 0, 0, 0, 0 }] = E,
            [new int[] { 0, 0, 0, 1 }]=J,
            [new int[] { 0, 0, 0, 0, 0 }]=F,
            [new int[] { 0, 0, 0, 0, 1 }]=K,
            [new int[] { 1 }]=G,
            [new int[] { 1, 0 }]=H,
            [new int[] { 1, 1 }]=B,
            [new int[] { 1, 2 }]=M,
            [new int[] { 1, 3 }]=N,
            [new int[] { 1, 0, 0 }]=O,
            [new int[] { 1, 3, 0 }]=P,
        };
        Console.WriteLine(dic.AssembleTree().ToTreeDiagram(x => x.Name));
        Console.WriteLine("親ノードから振り当てられているインデックスと、パスを追加で表示");
        Console.WriteLine(A.ToTreeDiagram(x => $"Name:{x.Name},BranchIndex:{x.BranchIndex()},NodePath:{x.NodePath(y=>y.Name)}"));

        A.Disassemble();//全て分解
        Console.ReadLine();

N分木を作る。レベルオーダーで追加されていきます。

小出しにはなりますが、拡張メソッドもたくさんあるので表示させてみる。

        Console.WriteLine("コレクションをN分木として組み立てる");
        var root = "ABCDEFGHIJKLMNOPQRSTUVWXYZ".ToCharArray().Select(x => x.ToString())
            .AssembleAsNAryTree(3, x => new ExampleNode() { Name = x });
        
        Console.WriteLine(root.ToTreeDiagram(x => x.Name));
        Console.WriteLine($"Levelorder:{string.Join(",", root.Levelorder().Select(x=>x.Name))}");
        Console.WriteLine($"Preorder:{string.Join(",", root.Preorder().Select(x => x.Name))}");
        Console.WriteLine($"Postorder:{string.Join(",", root.Postorder().Select(x => x.Name))}");
        Console.WriteLine($"Inorder:{string.Join(",", root.Inorder().Select(x => x.Name))}");

        Console.WriteLine("\n ----- Pickup C node -----");
        var C = root.Levelorder().First(x => x.Name == "C");
        Console.WriteLine($"Upstream:{string.Join(",", C.Upstream().Select(x=>x.Name))}");
        Console.WriteLine($"Ancestors:{string.Join(",", C.Ancestors().Select(x => x.Name))}");
        Console.WriteLine($"Leafs:{string.Join(", ", C.Leafs().Select(x=>x.Name))}");
        Console.WriteLine($"Genarations:{string.Join(",", C.Generations().Select(x => x.Name))}");
        Console.WriteLine($"Siblings:{string.Join(",",C.Siblings().Select(x=>x.Name))}");
        Console.WriteLine($"Width:{C.Width()}");

        Console.WriteLine("\n ----- Pickup R node -----");
        var R = root.Levelorder().First(x => x.Name == "R");
        Console.WriteLine($"Upstream:{string.Join(",", R.Upstream().Select(x => x.Name))}");
        Console.WriteLine($"Ancestors:{string.Join(",", R.Ancestors().Select(x => x.Name))}");
        Console.WriteLine($"Leafs:{string.Join(", ", R.Leafs().Select(x => x.Name))}");
        Console.WriteLine($"Genarations:{string.Join(",", R.Generations().Select(x => x.Name))}");
        Console.WriteLine($"Siblings:{string.Join(",", R.Siblings().Select(x => x.Name))}");
        Console.WriteLine($"Width:{R.Width()}");
        Console.WriteLine($"Root:{R.Root().Name}");

        Console.ReadLine();
    }

Xmlコメントの説明だけじゃ分かりにくいかなと思うメソッドは適宜補足する

継承関係

ツリー構造をなすInterfaceとして以下の３つを定義しています。

    /// <summary>ツリー構造を提供する。</summary>
    /// <typeparam name="TNode">各ノードの型</typeparam>
    public interface ITreeNode<TNode> where TNode : ITreeNode<TNode> {
    
        /// <summary>親ノードを取得する。</summary>
        TNode? Parent { get; }
        
        /// <summary>子ノードを取得する。</summary>
        IEnumerable<TNode> Children { get; }
    }
    /// <summary>子ノードを変更可能なツリー構造を定義する。</summary>
    /// <typeparam name="TNode">ノードの型</typeparam>
    public interface IMutableTreeNode<TNode> : ITreeNode<TNode> 
        where TNode : ITreeNodeCollection<TNode> {
        
        /// <summary>子ノードを追加する。</summary>
        /// <param name="child">子ノード</param>
        /// <returns>現在のノード</returns>
        TNode AddChild(TNode child);
        
        /// <summary>指定されたインデックスの位置に子ノードを追加する。</summary>
        /// <param name="index">インデックス</param>
        /// <param name="child">子ノード</param>
        /// <returns>現在のノード</returns>
        TNode InsertChild(int index, TNode child);
        
        /// <summary>子ノードを削除する。</summary>
        /// <param name="child">削除する子ノード</param>
        /// <returns>削除されたノード</returns>
        TNode RemoveChild(TNode child);
        
        /// <summary>子ノードを全て削除する。</summary>
        /// <returns>削除されたノード</returns>
        IReadOnlyList<TNode> ClearChildren();
    }
    /// <summary>観測可能なツリー構造を表す。</summary>
    /// <typeparam name="TNode">ノードの型</typeparam>
    public interface IObservableTreeNode<TNode>: ITreeNode<TNode> 
        where TNode : IObservableTreeNode<TNode>{
        
        /// <summary>ツリー構造変更時、<see cref="StructureChangedEventExecutor{TNode}"/>によって呼び出されます。</summary>
        /// <param name="e"></param>
        void OnStructureChanged(StructureChangedEventArgs<TNode> e);
        
        /// <summary>ツリー構造が変化したときの通知イベント</summary>
        event EventHandler<StructureChangedEventArgs<TNode>>? StructureChanged;
    }

上記interfaceとそれらを実装するクラスの継承図

使い分けですが、
細かくカスタマイズするならTreeNodeBase
データ構造として使用するならTreeNodeまたはObservableTreeNode
WPFのバインド用にラッパー兼ViewModelとして使用するならTreeNodeImitator
をそれぞれ継承します。
ラップするオブジェクトがITreeNodeを実装していないCompositeパターンであればCompositeImitatorでラップできます（何れにせよラップされる側の子ノードコレクションはINotifyCollectionChangedを実装していることが必須）。

データ構造をWPFのTreeViewなどに表示させるだけであれば、SetupメソッドをoverrideしてReadOnlyObservableCollectionを返せばTreeNodeBaseやTreeNodeCollectionでも可能です。
実際にObservableTreeNodeCollectionでは下のように記述しています。

public class ObservableTreeNodeCollection<TNode> 
    : TreeNodeCollection<TNode>, IObservableTreeNode<TNode>, INotifyPropertyChanged
    where TNode : ObservableTreeNodeCollection<TNode> {
    
    //内部処理用
    protected override IEnumerable<TNode> SetupInnerChildCollection() 
        => new ObservableCollection<TNode>();
        
    //外部公開用
    protected override IEnumerable<TNode> SetupPublicChildCollection(IEnumerable<TNode> innerCollection) 
        => new ReadOnlyObservableCollection<TNode>((innerCollection as ObservableCollection<TNode>)!);
    
    //略
}

NAryTreeNodeはBranchの数を指定でき、子ノードのコレクションにnullを含むノードとして定義しています。
TreeNodeWrapperは追加・削除可能なツリー構造を完全なReadOnlyな状態で公開したいときに使用します。

nullをどう扱うか

前身のオレオレライブラリーではChildrenにnullが入ることは拒否していたけど、どうもそれじゃ都合が悪いことがあります。
BinaryTreeのように、LeftとRightの2本の枝が常に伸びているとき、Inorderで正しく列挙できない。
空の場合はnullではなくEmptyNode<T>を定義するのは面倒くさい。派生先で定義して、nullの代わりにEmptyNodeの新規インスタンスを指定することになってしまうし、拡張メソッドのHeight()やLeafs()の戻り値がくるってしまう。そういう使い方をしてもらっても構わないが必須にはしたくない。
かといってnullを列挙されたところでメソッドは呼べないし何の利用価値もない。多分木であれば尚更。
NullReferenceExeptionの原因にもなる。

ということで、TreeNodeBaseでは子ノードにnullの追加を許可しますが、TreeNodeとその派生クラスでは拒否します。
列挙については、nullを許容はすれど列挙はしない。
その辺を良しなにやってくれるのが拡張メソッドのEvolveメソッドです。

/// <summary>現在のノードを起点として、ツリー構造を展開・列挙する</summary>
/// <typeparam name="T">ノードの型</typeparam>
/// <param name="self">現在のノード</param>
/// <param name="getnewseeds">要素から、追加するノードを指定する</param>
/// <param name="updateseeds">展開元の要素、追加された要素、未処理要素を引数にとり、未処理要素を更新する。<para>未処理要素は先頭から展開・列挙処理される。</para></param>
public static IEnumerable<T> Evolve<T>(this ITreeNode<T> self,
    Func<T, IEnumerable<T?>> getnewseeds, 
    Func<T, IEnumerable<T?>, IEnumerable<T?>, IEnumerable<T?>> updateseeds) 
    where T : ITreeNode<T> {
    //略
}

同時に、このメソッドでツリー構造が循環してしまってた場合の無限ループも回避します。

TreeNodeBaseでは循環もチェックするがCompositeImitatorはチェックしようがない（祖先方向に監視していない。子孫方向の参照を呼び出されたタイミングで初めて循環をチェックできるが、拒否ればラッパーとして機能してない）ので。

Evolveメソッドは他の多くの拡張メソッドから呼び出されてます。少し例を挙げると以下。

/// <summary>対象ノードを始点とし、先行順でシーケンスを生成する。</summary>
public static IEnumerable<T> Preorder<T>(this ITreeNode<T> self) where T : ITreeNode<T> {
    return self.Evolve(a => a.Children, (a, b, c) => b.Prepend(a).Concat(c));
}

/// <summary>対象ノードから祖先方向へシーケンスを生成する。最後尾がRootとなる。</summary>
public static IEnumerable<T> Upstream<T>(this ITreeNode<T> self) where T : ITreeNode<T> {
    return self.Evolve(a => new T?[1] { a.Parent }, 
        (a, b, c) => new T?[1] { a }.Concat(b).Concat(c));
}

/// <summary>対象ノードから子孫方向に、末端のノードを列挙する。</summary>
public static IEnumerable<T> Leafs<T>(this ITreeNode<T> self) where T : ITreeNode<T> {
    return self.Evolve(a => a.Children, 
        (a, b, c) => (b.OfType<T>().Any() ? b : new T?[1] { a }).Concat(c));
}

第２引数は同一のノードに対して１度しか適用されません。
適用されなかった場合第３引数も適用されません。
第３引数で順序を変更して、先頭の要素が変更前後で変わらなかったら列挙されます。

AddChild RemoveChild の戻り値

ツリー構造を保つ上で同一のノードは追加できない
　　↓
ISet<T>の機能が要求される

子ノードコレクションを編集することを考えるとIndexでアクセスできたほうが良い
派生先で子ノードコレクションをObservableCollectionで管理する
　　↓
IList<T>のinterfaceが要求される

よって、子ノードコレクションはISetとIListを掛け合わせた立ち位置になる。
ISet<T>.Addメソッドの戻り値はbool、IList<T>.Addメソッドの戻り値はvoid。
Removeメソッドは共にboolが返ってくる。

前身のライブラリではISet<T>,IList<T>に倣うより、利便性を優先してAdd,Remove共にSelfを返していました。
a.AddChild(b).Children.Count(); の様にメソッドチェーンを記述でき、変数aの子ノードコレクションのカウントが返ってきます。
boolより使いやすい。しかし、Removeの時に不満あり。
都合上、RemoveしたノードをDisposeしたいorキャッシュとしてリストに保持しときたい時に不便。何ならClearで全てのノードを返してほしい。
a.RemoveChild(b).Dispose();で変数bの削除と破棄を一行で書きたい。

一貫性をどう保つかですが、処理が正常に行われることを前提とし、常に追加または削除される子ノードにフォーカスを当てています。
Addされたなら追加された子ノードbは親ノードaからアクセス可能。
Removeされたなら親ノードを返されても削除された子ノードbにはアクセスできないから子ノードbが返ってくる。

この理屈を通すなら、拡張メソッドのTry( Add | Remove )Childも変わってくる。
正常に追加された→true,Self
既に追加済みor追加できなかった→false,child

正常に削除された→true,child
コレクションに存在しないor削除できなかった→false,Self

既に追加済みでもchildが返ってくるの？となりますが、処理が正常に実行できたかどうかのTryメソッドですし、falseなのに親か子かどちらのノードが返ってきたのかわからないのでは使いにくい。
既に追加済みでもtrueを返すことも検討しましたが、Tryメソッドの意義から離れてしまうのはいただけない。
この辺りが妥協点かなと。

付け加えると、TryRemoveOwnメソッドでは何れもSelfが返ってきます。
続く