Go to Qiita Advent Calendar 2024 Top
LoginSignup
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@Houzkin(保月 千代麿)

ツリー構造をなすクラスを作る(その3)

Last updated at Posted at 2023-12-30

Nuget-TreeStructures

枝の数を固定するNAryTreeNode

NAryTreeはBranchの数を初期化時に指定した数に固定します。
空の枝にはnullが設定されています。
AddChildしてもコレクションのカウントは増えません。
nullの枝に設定されていくだけです。

使用例

ここではNAryTreeNodeを継承したBinaryTreeNodeを使ってみます。

//バイナリーツリーを定義
public class SampleBinary : BinaryTreeNode<SampleBinary> {
    public string Value { get; set; }
}

Console.WriteLine("バイナリーツリーを作成");
var A = new SampleBinary() { Value = "A" };
var B = new SampleBinary() { Value = "B" };
var C = new SampleBinary() { Value = "C" };
var D = new SampleBinary() { Value = "D" };
var E = new SampleBinary() { Value = "E" };
var F = new SampleBinary() { Value = "F" };
var G = new SampleBinary() { Value = "G" };

A.Left = B;
A.Right = C;
B.Right = D;
D.Left = E;
C.Right = F;
F.Left = G;

Console.WriteLine(A.ToTreeDiagram(x => x.Value));
Console.WriteLine($"Inorder:{string.Join(",", A.Inorder().Select(x => x.Value))}");

screenshot.11.jpg

NAryTreeNodeの注意点

NAryTreeNodeはTreeNodeと違い、既に用意された枝に要素を設定していくことになります。
拡張メソッドのConvert()、AssembleTree()でツリーを組み立てる場合はインデックスを指定する必要があるので、以下のように、要求されるインデックスを引数にとるオーバーロードを用意しています。

Console.WriteLine("\n各ノードを別のノードに変換して組み立てる");
var convertedRoot = A.Convert(
    x => new SampleBinary() { Value = x.Value },
    (i, p, c) => p.SetChild(i, c));//指定されたインデックスに子ノードを設定

Console.WriteLine(convertedRoot.ToTreeDiagram(x => $"({x.Value})"));
Console.WriteLine($"Inorder:{string.Join(",", convertedRoot.Inorder().Select(x => x.Value))}");


Console.WriteLine("\n各ノードの値をDictionaryで表すノードマップに変換して、組み立てる");
//キーにNodeIndexをとるDictionaryに変換
var dic = A.ToNodeMap(x => x.Value);
//NodeIndexを使って組み立てる
var assembledRoot = dic.AssembleTree(
    x => new SampleBinary() { Value = x },
    (i, p, c) => p.SetChild(i, c));//指定されたインデックスに子ノードを設定

Console.WriteLine(assembledRoot.ToTreeDiagram(x => $"[{x.Value}]"));
Console.WriteLine($"Inorder:{string.Join(",", assembledRoot.Inorder().Select(x => x.Value))}");

screenshot.12.jpg

これによってInorderで列挙した場合でも同様の順序になり、ツリー構造の変更を回避できます。
比較のため、先述のExampleNodeへ変換してみます。

Console.WriteLine("\n比較のため、Branchを固定しないノードに組み替える");
var exroot = A.Convert(x => new ExampleNode() { Name = x.Value });
Console.WriteLine(exroot.ToTreeDiagram(x => x.Name));

Console.WriteLine($"Inorder:{string.Join(",", exroot.Inorder().Select(x => x.Name))}");

screenshot.13.jpg
ツリーの表示は同じですがGeneral Treeの場合はLeftがnullの状態というのを再現できないのでInorderの順序も再現できません。

NAryTreeNodeの内部コレクション

子ノードのコレクションはdefaultでは配列を使っていますが、他のコレクションに置き換え可能です。
IList<T>を実装していることが望ましいですが、ICollection<T>を実装さえしていれば、要素の数が指定された数に到達するまでdefault値を追加します。
この話は後述。

ObservableなCollectionで管理したい場合は以下のようにoverrideして使用できます。

public class InheritNary : NAryTreeNode<InheritNary> {
    public InheritNary(int nary) : base(nary) { }

    protected override IEnumerable<InheritNary> SetupInnerChildCollection()
        => new ObservableCollection<InheritNary>();
        
    protected override IEnumerable<InheritNary> SetupPublicChildCollection(IEnumerable<InheritNary> innerCollection) {
        return new ReadOnlyObservableCollection<InheritNary>(innerCollection as ObservableCollection<InheritNary>);
    }
}

このライブラリのコンセプト

使用例を淡々と書くのにも飽きてきたので、TreeNodeWrapperとTreeNodeImitatorの使用例を書く前に、このライブラリーのコンセプトみたいなものを書いてみます。
長い時間を費やしたので思い入れもあります。

特徴は、

  1. ITreeNode<T> に対する豊富な拡張メソッド
  2. 親ノードと子ノードの相互参照を実現
  3. ツリー構造をなすクラス群とそれらの拡張性
  4. 他ライブラリとの親和性

の4つです。
このライブラリの名前空間TreeStructures; で定義されたツリーノードを継承して使用します。

ITreeNode<T> に対する豊富な拡張メソッド

ITreeNode<T>の拡張メソッドは現在オーバーロードも含め60以上を定義しています。
例を挙げると、
列挙はPreorder, Levelorderなど全ての走査法や、 Leafs, Ancestors, DiscendArrivals, DescendTraces, etc
移動は、Root, NextSibling, LastSibling, etc
編集はTryAddChildをはじめ、Try○○Child, Disassemble, RemoveAllDescendant, etc
パラメータの取得は、NodeIndex, NodePath, Height, Depth, etc
判定メソッドは、IsDescendantOf, IsAncestorOf, IsRoot, etc
変換は、ToNodeMap, ToSerializableNodeMap, ToTreeDiagram
組み立てメソッドは、Convert, AssembleTree, AssembleAsNAryTree
もう少し作りたいメソッドはありますがそれはまた追々。

親と子の相互参照を実現

親ノードと子ノードの相互参照は基底クラスで完結しています。
TreeNodeBaseの場合

protected virtual void RemoveChildProcess(
    TNode child,Action<IEnumerable<TNode>,TNode>? action = null) { /*略*/ }

protected virtual void InsertChildProcess(
    int index, TNode child, Action<IEnumerable<TNode>,int,TNode>? action = null){ /*略*/ }
    
protected virtual void SetChildProcess(
    int index, TNode child, Action<IEnumerable<TNode>, int, TNode>? action = null) { /*略*/ }

protected virtual void ClearChildProcess(Action<IEnumerable<TNode>>? action = null) { /*略*/ }

protected virtual void ShiftChildProcess(
    int oldIndex, int newIndex, Action<IEnumerable<TNode>,int,int>? action = null) { /*略*/ }

protected virtual void DisposeProcess() { /*略*/ }

のように○○ChildProcessで定義されたメソッドで行います。
RemoveChildProcessの内部処理は引数childの親ノードをnullに変更してactionのdelegateによって子ノードコレクションを操作。

InsertChildProcess場合は、引数childの、前の親ノードのRemoveChildProcess(child)を呼び出し、Parentを設定した後、actionのdelegateによって子ノードコレクションを操作。

引数actionは、null指定でデフォルトの処理が実行されるので、デフォルトの処理がIList<T>にキャストするのにSetupInnerChildCollectionで指定したコレクションがIList<T>を実装してない、といった場合はactionを記述する必要があります。
defaultの処理はXMLコメントに記載しています。
screenshot.10.jpg

子ノード追加時に、
protected virtual bool CanAddChildNode([AllowNull] TNode child) { }
を呼び出して、ツリーの循環と兄弟ノードとの重複をチェックしています。
うっかり祖先ノードを子ノードとしての追加、あるいは既に追加されているノードと同一ノードの追加を防ぎます。

( Composite | TreeNode )Wapprerとその派生型ではプライベートメソッドで相互参照を処理してます。

ツリー構造をなすクラス群とそれらの拡張性

Setup( Inner | Public ) ChildCollection メソッドで、内部で子ノードを管理するコレクションと外部公開用のコレクションをそれぞれ指定できます。これらはIEnumerable<T> を実装していればよいので、独自にカスタマイズしたコレクションや他のライブラリで定義されたコレクションを設定できます。
例えば、ObservableSortedCollectionやスレッドセーフなコレクションなど、状況によって要求される機能を持ったコレクションを使えます。
NAryTreeNodeを継承しておきながら外部にはnullを除外したコレクションとして公開する、といったことも可能です。
実用性は感じませんが、Stack<T>やQueue<T>などでも子ノードを管理できます。
(RemoveChildProcessの引数actionをどうするかは一考の余地がありますが)

( Composite | TreeNode )( Wapprer | Imitator ) では、内部子ノードコレクションは変更できませんが、外部公開用のコレクションは下記メソッドをオーバーライドしてカスタマイズ可。
ReactiveCollectionなどでフィルターをかけたりすることを想定しています。

public abstract class CompositeWrapper<TSrc,TWrpr> : ITreeNode<TWrpr> ,INotifyPropertyChanged, IDisposable
    where TSrc : class
    where TWrpr:CompositeWrapper<TSrc,TWrpr> {
    
    /// <summary>外部に公開するコレクションを設定する</summary>
    /// <remarks>基底クラスからは<see cref="SourceNodeChildren"/>をラップした<see cref="ImitableCollection{TSrc, TConv}"/>を返す。</remarks>
    protected virtual IEnumerable<TWrpr> SetupPublicChildCollection(ImitableCollection<TWrpr> children) 
        => children;

削除された子ノードに対する処理を記述する場合はManageRemovedChildをoverride。

 /// <summary>削除された子ノードに対する処理</summary>
 /// <remarks>基底クラスでは<see cref="Dispose"/>メソッドが呼び出される</remarks>
 /// <param name="removedNode">削除された子ノード</param>
 protected virtual void ManageRemovedChild(TWrpr removedNode) {
     (removedNode as IDisposable)?.Dispose();
 }

Wrapperは外部からの操作を受け付けない、完全なReadOnlyにすることも可能な作りとなっているのでDisposeメソッドは隠蔽しています。

CompositeImitator, TreeNodeImitatorはMVVMパターンにおけるViewModelとして使用することも想定しているので、削除された子ノードに対する処理の指定に加え、モデル側の子ノードコレクションとの連動の停止と再開の切り替えメソッドも公開しています。( PauseImitation / ImitateSourceSubTree )

以上のような機能を備えることで、TreeNodeを階層構造をなすコンテナーとして使えるだけでなく、データオブジェクトとしても使うことができます。

他ライブラリとの親和性

様々な便利なライブラリが公開されているので、このライブラリで完結することは目指していません。
Setup( Inner | Public )ChildCollectionメソッドはその典型です。
ITreeNode<T>を実装していないコンポジットパターンをなすオブジェクトに対しても、CompositeWrapperやCompositeImitatorでラップすることでITreeNodeの拡張メソッドを提供できます。
また、下に示した拡張メソッドのConvertとAssembleTreeのオーバーロードは戻り値をITreeNodeに限定しません。

Convert の オーバーロード
/// <summary>対象ノードを始点とするツリーと同じ構造で、各ノードの型を変換した構造を再構築する。</summary>
/// <typeparam name="T">変換前の型</typeparam>
/// <typeparam name="U">変換後の型</typeparam>
/// <param name="self">対象ノード</param>
/// <param name="generator">各ノードに適用されるノード変換関数</param>
/// <param name="addAction">第一引数に要求されるBranchIndex、第二引数に親となるオブジェクト、第三引数に子となるオブジェクトを取り、その関係を成り立たせる関数。</param>
public static U Convert<T, U>(this ITreeNode<T> self, Func<T, U> generator, Action<int, U, U> addAction)
    where T : ITreeNode<T> { /* */}

/// <summary>対象ノードを始点とするツリーと同じ構造で、各ノードの型を変換した構造を再構築する。</summary>
/// <typeparam name="T">変換前の型</typeparam>
/// <typeparam name="U">変換後の型</typeparam>
/// <param name="self">対象ノード</param>
/// <param name="generator">各ノードに適用されるノード変換関数</param>
/// <param name="addAction">第一引数に親となるオブジェクト、第二引数に子となるオブジェクトを取り、その関係を成り立たせる関数。</param>
public static U Convert<T, U>(this ITreeNode<T> self, Func<T, U> generator, Action<U, U> addAction)
    where T : ITreeNode<T> { /* */}
AssembleTree の オーバーロード
/// <summary>各データをキーが示すインデックスをもとに組み立てる。</summary>
/// <typeparam name="TKey">ノードインデックスを示す、<see cref="int"/>型の要素を持つ<see cref="IEnumerable"/></typeparam>
/// <typeparam name="T">データの型</typeparam>
/// <param name="self">現在のオブジェクト</param>
/// <param name="addAction">第一引数に要求されるBranchIndex、第二引数に親となるオブジェクト、第三引数に子となるオブジェクトを取り、その関係を成り立たせる関数。</param>
public static T AssembleTree<TKey,T>(this IDictionary<TKey, T> self, Action<int,T, T> addAction)
    where TKey : IEnumerable<int> { }

/// <summary>各データをキーが示すインデックスをもとに組み立てる。</summary>
 /// <typeparam name="TKey">ノードインデックスを示す、<see cref="int"/>型の要素を持つ<see cref="IEnumerable"/></typeparam>
 /// <typeparam name="T">データの型</typeparam>
 /// <param name="self">現在のオブジェクト</param>
 /// <param name="addAction">第一引数に親となるオブジェクト、第二引数に子となるオブジェクトを取り、その関係を成り立たせる関数。</param>
public static T AssembleTree<TKey, T>(this IDictionary<TKey, T> self, Action<T, T> addAction) 
    where TKey : IEnumerable<int> { }
    
/// <summary>階層を示すインデックスをもとに、各データの変換と組み立てを行う。</summary>
/// <typeparam name="TKey">ノードインデックスを示す、<see cref="int"/>型の要素を持つ<see cref="IEnumerable"/></typeparam>
/// <typeparam name="T">データ</typeparam>
/// <typeparam name="U">変換先の型</typeparam>
/// <param name="self">現在のオブジェクト</param>
/// <param name="conv">変換関数</param>
/// <param name="addAction">第一引数に要求されるBranchIndex、第二引数に親となるオブジェクト、第三引数に子となるオブジェクトを取り、その関係を成り立たせる関数。</param>
public static U AssembleTree<TKey,T, U>(this IDictionary<TKey, T> self, Func<T, U> conv, Action<int, U, U> addAction) 
    where TKey:IEnumerable<int> { }

/// <summary>階層を示すインデックスをもとに、各データの変換と組み立てを行う。</summary>
/// <typeparam name="TKey">ノードインデックスを示す、<see cref="int"/>型の要素を持つ<see cref="IEnumerable"/></typeparam>
/// <typeparam name="T">データ</typeparam>
/// <typeparam name="U">変換先の型</typeparam>
/// <param name="self">現在のオブジェクト</param>
/// <param name="conv">変換関数</param>
/// <param name="addAction">第一引数に親となるオブジェクト、第二引数に子となるオブジェクトを取り、その関係を成り立たせる関数。</param>
public static U AssembleTree<TKey, T, U>(this IDictionary<TKey, T> self, Func<T, U> conv, Action<U, U> addAction) 
    where TKey : IEnumerable<int> { }

namespace

名前空間についても少し触れておきます。

  • TreeStructures;
    　abstractで定義された汎用ツリーノードと周辺オブジェクト
    　
  • TreeStructures.Linq;
    　ITreeNode<T>, IMutableTreeNode<T>, IEnumerable<T>に対する拡張メソッド
    　
  • TreeStructures.Utility;
    　Try○○メソッドの戻り値として使用するResultWithValueの定義など
    　
  • TreeStructures.Collections;
    　内部実装や拡張メソッドの処理過程などで使用されるコレクション　
    　
  • TreeStructures.EventManagement;
    　Event関連、ObservableなTreeNodeを実装するときに使用するオブジェクトなど
    　
  • TreeStructures.Xml.Serialization;
    　シリアライズ・デシリアライズ時に使用するDictionaryなど
    　
  • TreeStrucutures.Tree;
    　特定の目的・用途を想定したツリー

説明を書けば書くほど、分かりやすいネーミングか心配になりますな。
続く

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?