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

## 前書き
C#にはツリー構造を扱うクラスが用意されていないので5年くらい前に自作しました。nugetにアップロードして自分で使うオレオレらいぶらりー。
しばらくコードを書くこと自体がなかったけど最近また書き始めて、そのライブラリを久々に使ってみるとバグが見つかったり、使いにくかったり、分かりにくい表現だったり。
そんな、自分しか使っていないと思ったライブラリが何方か存じませんがダウンロードされているらしいんですよ。
![screenshot.14.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/70164/f7e54740-2be4-f8d7-758c-786a1855c0ba.jpeg)
これ、何かの間違いです？ホントにダウンロードされてる？
であれば雑な作りで申し訳ないというか...。

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

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

[Nuget-TreeStructures](https://www.nuget.org/packages/TreeStructures/)

https://github.com/Houzkin/TreeStructure

# 参考にしたページ
[IT用語辞典：木構造 【tree structure】 ツリー構造](https://e-words.jp/w/%E6%9C%A8%E6%A7%8B%E9%80%A0.html)
[Wikipedia：Compositeパターン](https://ja.wikipedia.org/wiki/Composite_%E3%83%91%E3%82%BF%E3%83%BC%E3%83%B3)
[Wikipedia：木構造](https://ja.wikipedia.org/wiki/%E6%9C%A8%E6%A7%8B%E9%80%A0)
[やってみる：C#ツリー構造のインタフェースを考える](https://ytyaru.hatenablog.com/entry/2022/01/27/000000)
[雨の歌をいつか書く：ツリー構造クラスの自作](https://leetmikeal.hatenablog.com/entry/20141129/1417253143)
[ドクロモエ：C# でツリー構造のデータを使う](https://dokuro.moe/use-tree-with-c-sharp/)
[Introduction to Tree – Data Structure and Algorithm Tutorials](https://www.geeksforgeeks.org/introduction-to-tree-data-structure-and-algorithm-tutorials/?ref=shm)
とそのリンク先など

# 使用例
何はともあれ、まずは木を作って表示させてみます。
```csharp
//ノードを定義
public class ExampleNode : TreeNode<ExampleNode> {
    public ExampleNode() { }
    public string Name { get; set; }
}
```
追加メソッドでちまちま追加する
```csharp
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();
```
![screenshot.14.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/70164/e7d73666-c05e-cf92-e739-09e6ee9e5ece.jpeg)

NodeIndexを指定したDictionaryから作成
```csharp
        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();
```
![screenshot.15.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/70164/a6b3a4fd-6dd8-6bc8-7af2-6f117fea4dfd.jpeg)


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

小出しにはなりますが、拡張メソッドもたくさんあるので表示させてみる。
```csharp
        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();
    }
```
![screenshot.6.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/70164/e0c88d52-5d42-2c3a-5c6b-e78b4f1bcbd1.jpeg)

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

# 継承関係
ツリー構造をなすInterfaceとして以下の３つを定義しています。
```csharp
    /// <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とそれらを実装するクラスの継承図


![TreeNode継承図1-1-2.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/70164/fd1d01b4-5537-7c4e-ce3d-6ff3f5e711b0.png)

:::note warn
継承図とクラス名に変更があります
<img src="https://raw.githubusercontent.com/Houzkin/TreeStructures/master/images/InheritanceGenericTreeNode.png" width=100%>
TreeNode -> GeneralTreeNode
ObservableTreeNode -> ObservableGeneralTreeNode
CompositeWrapper -> HierarchyWrapper
CompositeImitator -> BindableHierarchyWrapper
TreeNodeImitator -> BindableTreeNodeWrapper
:::


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

データ構造をWPFのTreeViewなどに表示させるだけであれば、SetupメソッドをoverrideしてReadOnlyObservableCollectionを返せばTreeNodeBaseやTreeNodeCollectionでも可能です。
実際にObservableTreeNodeCollectionでは下のように記述しています。
```csharp
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メソッドです。
```csharp
/// <summary>
/// 現在のノードを起点にツリー構造を展開し、トラバーサル中にノードの追加や更新をカスタムロジックで行いながら列挙します。
/// </summary>
/// <typeparam name="T">ノードの型。</typeparam>
/// <param name="startNode">トラバーサルを開始する起点のノード。</param>
/// <param name="getNodes">
/// 指定されたノードに基づいて追加されるノードを決定する関数。  
/// 現在のノードを引数として受け取り、そのノードに関連するノードのコレクションを返します。
/// </param>
/// <param name="updatePendingNodes">
/// トラバーサル中に未列挙のノードリストを更新する関数。この関数は以下の引数を取ります:
/// <list type="bullet">
/// <item><description>現在のノード。<paramref name="getNodes"/> 関数の第一引数として渡された値。</description></item>
/// <item><description>現在のノードに対して新しく追加されたノードのコレクション。
/// <paramref name="getNodes"/> 関数の戻り値。
/// </description></item>
/// <item><description>未列挙の残りのコレクション。  
/// <para>このコレクションの先頭要素がまだ <paramref name="getNodes"/> の引数として使用されていない場合、
/// その要素が <paramref name="getNodes"/> の引数として渡されます。</para>
/// <para>既に <paramref name="getNodes"/> の引数として使用されていた場合、その要素が列挙されます。</para>
/// </description></item>
/// </list>
/// </param>
public static IEnumerable<T> Evolve<T>(this ITreeNode<T> self,
    Func<T, IEnumerable<T?>> getNodes, 
    Func<T, IEnumerable<T?>, IEnumerable<T?>, IEnumerable<T?>> updatePendingNodes) 
    where T : ITreeNode<T> {
    //略
}
```
第２引数 `getNodes`は同一のノードに対して１度しか適用されません。
第３引数`updatePendingNodes`で順序を変更して、先頭の要素が既に`getNodes`を通過していたら列挙されます。

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

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

Evolveメソッドは他の多くの拡張メソッドから呼び出されてます。少し例を挙げると以下。
```csharp
/// <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));
}
```
現状、Evolveメソッドは`ITreeNode<T>`の制約を設けていますが、この制約なしでも機能します。
制約を設けなければ`ITreeNode<T>`を実装していないツリー構造にも適用できるのですが、Evolveメソッドが直感的でなく難しい、そのEvelveメソッドを使った実用的なメソッドには制約があり、これだけをインテリセンスに表示させてもメリットが感じられない。

回避策として拡張メソッドの`AsValuedTreeNode`を使うなど、ラップすればよいわけですし。
というのが現在の帰結です。
# 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が返ってきます。
[続く](https://qiita.com/Houzkin/items/0a8175dd51ef3bf7bc28)