Repository navigation
Tutorial3.ja
ツリー構造の挙動や公開するメンバーをカスタマイズできるように、抽象クラスとして提供しています。
ITreeNodeで定義されているプロパティのみが公開されており、ReadOnlyな状態のクラスです。
ノードの追加・削除による、親ノードとの相互参照の設定を担うため、protectedメンバーを定義しています。
派生先でこれらのメンバーをオーバーライドすることでカスタマイズできます。
また必要に応じて、操作するためのメソッドを公開できます。
ITreeNodeBase.cs
public abstract class TreeNodeBase<TNode> : ITreeNode<TNode>
where TNode:TreeNodeBase<TNode>,ITreeNode<TNode>{
protected TreeNodeBase() { }
#region ITreeNode interface
public TNode? Parent { get; }
public IEnumerable<TNode> Children { get; }
#endregion
protected IEnumerable<TNode> ChildNodes;
protected abstract IEnumerable<TNode> SetupInnerChildCollection();
protected virtual IEnumerable<TNode> SetupPublicChildCollection(IEnumerable<TNode> innerCollection)
=> innerCollection.AsReadOnly();
protected virtual bool CanAddChildNode(TNode child) { ...}
protected virtual void InsertChildCore(int index, TNode child,Action<IEnumerable<TNode>,int,TNode>? action = null) {...}
protected virtual void SetChildCore(int index, TNode child, Action<IEnumerable<TNode>, int, TNode>? action = null) {...}
protected virtual void RemoveChildCore(TNode child,Action<IEnumerable<TNode>,TNode>? action = null) {...}
protected virtual void ShiftChildCore(int oldIndex,int newIndex,Action<IEnumerable<TNode>,int,int>? action = null) {...}
protected virtual void ClearChildCore(Action<IEnumerable<TNode>>? action = null) {...}
protected virtual void Dispose(bool disposing) {...}
}-
SetupInnerChildCollectionメソッドで指定したコレクションがChildNodesプロパティとして設定されます。 -
ChildNodesプロパティが内部処理で直接操作されるコレクションです。 -
SetupPublicChildCollectionメソッドは引数にChildNodesをとり、戻り値がChildrenとして外部に公開されます。
内部コレクションと公開用コレクションを分けることで以下のメリットがあります。
- 内部コレクションに、
HashSet、LinkedList、ObservableCollectionなど最適なコレクションを指定できる - ダウンキャストによる、意図しない子ノードコレクションの変更を回避
カスタマイズ例を二つ示します。
public class Example1TreeNode : TreeNodeBase<Example1TreeNode> {
protected override IEnumerable<Example1TreeNode> SetupInnerChildCollection()
=> new ObservableCollection<Example1TreeNode>();
protected override IEnumerable<Example1TreeNode> SetupPublicChildCollection(IEnumerable<Example1TreeNode> innerCollection)
=> new ReadOnlyObservableCollection<Example1TreeNode>((innerCollection as ObservableCollection<Example1TreeNode>)!);
public new ReadOnlyObservableCollection<Example1TreeNode> Children
=> (base.Children as ReadOnlyObservableCollection<Example1TreeNode>)!;
}公開用コレクションはITreeNode.Childrenプロパティを通して公開されるのでIEnumerable型にアップキャストされます。
ReadOnlyObservableCollectionのまま公開するには、Childrenプロパティを隠蔽することで可能です。
public class Example2TreeNode : TreeNodeBase<Example2TreeNode> {
protected override IEnumerable<Example2TreeNode> SetupInnerChildCollection()
=> new HashSet<Example2TreeNode>();
}子ノードコレクションの追加・削除を行うにあたり、内部コレクションの型に合わせた操作方法を指定できます。
デフォルトの処理過程では、ChildNodesをICollection型やIList型にダウンキャストしています。
もしSetupInnerChildCollectionメソッドで指定したコレクションがこれらのインターフェイスを実装していない場合、変更が必要です。
引数actionによって変更可能で、null指定でデフォルトの操作が実行されます。(デフォルトの操作はXMLコメントに記載)

InsertChildCoreメソッドの引数actionは、デフォルトでは内部コレクションをIList型にダウンキャストします。
よって上記のように、内部コレクションにHashSet型を指定した場合は、以下のようにカスタマイズします。
public class Example2TreeNode : TreeNodeBase<Example2TreeNode> {
protected override IEnumerable<Example2TreeNode> SetupInnerChildCollection()
=> new HashSet<Example2TreeNode>();
protected override void InsertChildCore(int index, Example2TreeNode child, Action<IEnumerable<Example2TreeNode>, int, Example2TreeNode>? action = null) {
action ??= (collection, idx, node) => ((ICollection<Example2TreeNode>)collection).Add(node);
base.InsertChildCore(index, child, action);
}
public Example2TreeNode AddChild(Example2TreeNode child) {
this.InsertChildCore(0, child);
return this;
}
}HashSet型でも処理できるようにICollectionへダウンキャストして追加処理を行うよう、デフォルトの処理方法を変更しています。
action ??= (collection, idx, node) =>...としている理由は、他のメソッドや派生した先にて、個別に指定した操作方法を優先させるためです。
CanAddChildNodeメソッドは、追加することによって循環または兄弟ノードとの重複が発生するかどうかをチェックします。
InsertChildCore、SetChildCoreの処理過程で呼び出されます。
追加・削除メソッドを公開している多分木です。
以下のようにCanAddChildNodeメソッドをオーバーライドしており、子ノードコレクションにnullを追加できません。
protected override bool CanAddChildNode(TNode child) {
if (child == null) return false;
return base.CanAddChildNode(child);
}IMutableTreeNodeの実装によって、Tryメソッドなどの編集に関する拡張メソッドが利用可能です。
ツリー構造のデータを扱うとき、最も使いやすいクラスかと思います。
IObservableTreeNodeを実装した多分木です。
GeneralTreeNode同様、子ノードコレクションにnullの追加はできません。
ObservableGeneralTreeNode.ChildrenプロパティはIEnumerable型を返しますが、インスタンス自体はReadOnlyObservableCollection型です。
各ノードにてStructurechangedイベントを購読でき、ツリー内の、どのノードがどう変化したかを観測できます。
イベント引数は、全てのノード共通で受け取れる情報に加え、購読したノードから見て祖先ノードに変更があった場合はAncestorInfo、子孫ノードに変更があった場合はDescendantInfoを取得できます。
ITreeNode.cs
public interface IObservableTreeNode<TNode> : ITreeNode<TNode>
where TNode : IObservableTreeNode<TNode> {
/// <summary>Called by <see cref="StructureChangedEventExecutor{TNode}"/> when the tree structure changes.</summary>
void OnStructureChanged(StructureChangedEventArgs<TNode> e);
/// <summary>Notification event for when the tree structure changes.</summary>
event EventHandler<StructureChangedEventArgs<TNode>>? StructureChanged;
}簡易的なクラスを定義して、どういった通知が受け取れるのか示します。
public class ObservableNamedNode: ObservableGeneralTreeNode<ObservableNamedNode> {
public string Name { get; set; }
public override string ToString() => this.Name;
}サンプルとして使用するツリー構造を組立て、各ノードを購読します。
var nodesDic = "ABCDEFGHI".ToCharArray().Select(x => x.ToString()).ToDictionary(x => x, x => new ObservableNamedNode() { Name = x });
var root = nodesDic.Values.AssembleAsNAryTree(2);
Console.WriteLine(root.ToTreeDiagram(x => x.Name));
/*
A
├ B
│ ├ D
│ │ ├ H
│ │ └ I
│ └ E
└ C
├ F
└ G
*/
EventHandler<StructureChangedEventArgs<ObservableNamedNode>> structreChangedHdlr = (s, e) => {
Console.WriteLine($"sender:{s} \nTarget:{e.Target} TreeAction:{e.TreeAction} PreviousParentOfTarget:{e.PreviousParentOfTarget} OldIndex:{e.OldIndex} IsAncestorChanged:{e.IsAncestorChanged} IsDescendantChanged:{e.IsDescendantChanged}");
if (e.IsAncestorChanged) {
var info = e.AncestorInfo!;
Console.WriteLine($"MovedTarget:{info.MovedTarget} OldIndex:{info.OldIndex} PreviousParentOfTarget:{info.PreviousParentOfTarget} IsRootChanged:{info.IsRootChanged}");
}
if (e.IsDescendantChanged) {
var info = e.DescendantInfo!;
Console.WriteLine($"Target:{info.Target} SubtreeAction:{info.SubTreeAction} OldIndex:{info.OldIndex} PreviousParentOfTarget:{info.PreviousParentOfTarget}");
}
Console.Write("\n");
};
PropertyChangedEventHandler propertyChangedHdlr = (s, e) => {
if(e.PropertyName == "Parent")
Console.WriteLine($"sender:{s} Parent Changed.\n");
};
foreach (var node in root.PreOrder()) {
node.StructureChanged += structreChangedHdlr;
node.PropertyChanged += propertyChangedHdlr;
}Console.WriteLine("Remove node D");
nodesDic["B"].RemoveChild(nodesDic["D"]);
Console.WriteLine(root.ToTreeDiagram(x => x.Name));

node A,B、node C,E,F,G、node D,H,I はそれぞれ同じ通知内容になっています。
node A,B は IsDescendantChanged が true となって DescendantInfo を表示。
node C,E,F,G は、変更のあった node D の、祖先でも子孫でもないので IsAncestorChanged、IsDescendantChanged ともに False。
切り離された node D,H,I は IsAncestorChanged が true となり AncestorInfo を表示しています。
Console.WriteLine("Add node D as a child node to node E.");
nodesDic["E"].AddChild(nodesDic["D"]);
Console.WriteLine(root.ToTreeDiagram(x => x.Name));

node A,B,E は子孫に変更があったので IsDescendantChanged が true となり、
node C,F,G は共にfalse、
node D,H,I は祖先に変更があったので IsAncestorChanged が true です。
Console.WriteLine("Move node E to be a child node of node C.");
nodesDic["C"].AddChild(nodesDic["E"]);
Console.WriteLine(root.ToTreeDiagram(x => x.Name));

ツリー全体(node A)から見てnode E がツリー内を移動したので TreeAction は Move
node B から見てSubTreeから離れたので SubTreeAction は Leave
node C から見てSubTree外から加わったので SubTreeAction は Join
ツリー内の移動なのでnode E,D,H,Iから見て IsRootChanged は False となります。
子ノードコレクションの要素数を、初期化時またはコンストラクタで指定した数に固定します。
public class CustomNaryTreeNode : NAryTreeNode<CustomNaryTreeNode> {
public CustomNaryTreeNode(int nary) : base(nary) { }
public CustomNaryTreeNode() : base(2) { }
public string Name { get; set; }
}デフォルトでは内部コレクションに配列を使用していますが、
protected override IEnumerable<TNode> SetupChildCollection() => new List<TNode>();
とすることで子ノードコレクションをリスト型で初期化できます。
要素数を固定するにあたり、2つ注意点があります。
- 追加・削除によって子ノードコレクションの長さは変化しない
-
nullの要素は列挙されない
空の要素にはデフォルトでnullが設定されています。
要素を追加するとnullの位置に追加されていき、削除するとnullに置き換えられます。
nullの要素がない状態でAddChildメソッドで追加しようとしても追加できません。
追加できたかどうか、結果を取得したい場合はTryAddChildメソッドを使用してください。
要素数を2つに固定して、三分木の組立てを試みます。
var lst = "ABCDEFGH".ToCharArray().Select(x => new CustomNaryTreeNode(2) { Name = x.ToString()});
var root = lst.AssembleAsNAryTree(3);
Console.WriteLine(root.ToTreeDiagram(x => $"{x.Name}, BranchIndex: {x.BranchIndex()}"));
/*
A, BranchIndex: -1
├ B, BranchIndex: 0
│ ├ E, BranchIndex: 0
│ └ F, BranchIndex: 1
└ C, BranchIndex: 1
└ H, BranchIndex: 0
*/3つ目の要素は追加できないので、ノードD、G は追加されていません。
次のコードで、ノードBを削除します。
root.RemoveAllChild(x=>x.Name == "B");
Console.WriteLine(root.ToTreeDiagram(x => $"{x.Name}, BranchIndex: {x.BranchIndex()}"));
Console.WriteLine("In-Order:" + string.Join(",", root.InOrder().Select(x=>x.Name)));
/*
A, BranchIndex: -1
└ C, BranchIndex: 1
└ H, BranchIndex: 0
In-Order:A,H,C
*/ノードBが削除されても、ノードCのインデックスは1のままです。
ConvertメソッドでNAryTreeへ変換する、またはAssembleTreeメソッドでNaryTreeを組立てる時は、インデックスも指定する必要があります。
var dic = root.ToNodeMap(x=>x.Name);
foreach(var pair in dic)
Console.WriteLine($"key:{pair.Key}, value:{pair.Value}");
/*
key:[], value:A
key:[1], value:C
key:[1,0], value:H
*/
var root1 = dic.AssembleTree(
x => new CustomNaryTreeNode(2) { Name = x.ToString() },
(p, c, i) => p.SetChild(i, c));
Console.WriteLine(root1.ToTreeDiagram(x => $"{x.Name}, BranchIndex: {x.BranchIndex()}"));
Console.WriteLine("In-Order:" + string.Join(",", root1.InOrder().Select(x=>x.Name)));
/*
A, BranchIndex: -1
└ C, BranchIndex: 1
└ H, BranchIndex: 0
In-Order:A,H,C
*/比較として、インデックスを指定しなかった結果と、GeneralTreeに変換した結果も示します。
var root2 = dic.AssembleTree(x => new CustomNaryTreeNode(2) { Name = x});
Console.WriteLine(root2.ToTreeDiagram(x => $"{x.Name}, BranchIndex: {x.BranchIndex()}"));
Console.WriteLine("In-Order:" + string.Join(",", root2.InOrder().Select(x=>x.Name)));
/*
A, BranchIndex: -1
└ C, BranchIndex: 0
└ H, BranchIndex: 0
In-Order:H,C,A
*/
// NAry tree -> General tree
var root3 = root.Convert(x => new NamedNode() { Name = x.Name });
Console.WriteLine(root3.ToTreeDiagram(x => $"{x.Name}, BranchIndex: {x.BranchIndex()}"));
Console.WriteLine("In-Order:" + string.Join(",", root3.InOrder().Select(x=>x.Name)));
/*
A, BranchIndex: -1
└ C, BranchIndex: 0
└ H, BranchIndex: 0
In-Order:H,C,A
*/インデックスを指定しない場合、先頭から順に子ノードを追加していくためBranchIndexを再現できません。
GeneralTreeは、インデックス0の要素がnull、という状態を表現できません。
前述にて、nullは列挙しないとしましたが、表示または列挙する方法は用意しています。
以下のツリーを使って説明します。
var root = new Dictionary<NodeIndex, CustomNaryTreeNode>() {
[new NodeIndex()] = new CustomNaryTreeNode(3) { Name = "A" },
[new NodeIndex(0)] = new CustomNaryTreeNode(2) { Name = "B" },
[new NodeIndex(1)] = new CustomNaryTreeNode(2) { Name = "C" },
[new NodeIndex(0, 1)] = new CustomNaryTreeNode(0) { Name = "D" },
[new NodeIndex(1, 1)] = new CustomNaryTreeNode(2) { Name = "E" },
}.AssembleTree((p, c, i) => p.SetChild(i, c));
Console.WriteLine(root.ToTreeDiagram(x => $"{x.Name} branchIndex:{x.BranchIndex()}"));
/*
A branchIndex:-1
├ B branchIndex:0
│ └ D branchIndex:1
└ C branchIndex:1
└ E branchIndex:1
*/表示する方法としては、ToTreeDiagramメソッドの引数にて、nullだった時の表示を指定します。
Console.WriteLine(root.ToTreeDiagram(x => x.Name,"empty"));
/*
A
├ B
│ ├ empty
│ └ D
├ C
│ ├ empty
│ └ E
│ ├ empty
│ └ empty
└ empty
*/列挙する方法としては、ReadOnlyValuedTreeNodeを経由することで列挙できます。
Console.WriteLine(root.AsValuedTreeNode(x => x).ToTreeDiagram(x => x.Value?.Name ?? "null"));
/*
A
├ B
│ ├ null
│ └ D
├ C
│ ├ null
│ └ E
│ ├ null
│ └ null
└ null
*/
Console.WriteLine($"InOrder(do not ignore null): {string.Join(',', root.AsValuedTreeNode(x => x).InOrder().Select(x => x.Value?.Name ?? "null"))}");
Console.WriteLine($"InOrder(ignore null) : {string.Join(',', root.InOrder().Select(x => x.Name))}");
/*
InOrder(do not ignore null): null,B,D,A,null,C,null,E,null,null
InOrder(ignore null) : B,D,A,C,E
*/派生先にて破棄処理が必要になった場合は、
protected virtual void Dispose(bool disposing)を使用してください。
対象となったノードとその子孫ノードが破棄されます。
public class DisposableNode
: ObservableGeneralTreeNode<DisposableNode>, IDisposable {
public string Name { get; set; }
public override string ToString() => this.Name;
private bool disposedValue;
protected override void Dispose(bool disposing) {
if (disposedValue) return;
if (disposing) {
Console.WriteLine($"Start disposing {this.Name}.");
}
base.Dispose(disposing);
Console.WriteLine($"Finished disposing {this.Name}.");
disposedValue = true;
}
public void Dispose() {
Dispose(disposing: true);
GC.SuppressFinalize(this);
}
}次のコードで破棄処理の過程を示します。
var nodesDic = "ABCD".ToCharArray().Select(x => x.ToString()).ToDictionary(x => x, x => new DisposableNode() { Name = x });
var root = nodesDic.Values.AssembleAsNAryTree(1);
EventHandler<StructureChangedEventArgs<DisposableNode>> structreChangedHdlr = (s, e) => {
if (s == e.Target && e.IsAncestorChanged) {
Console.WriteLine($"sender:{e.Target} ,TreeAction:{e.TreeAction}");
}
};
foreach (var node in root.PreOrder()) {
node.StructureChanged += structreChangedHdlr;
}
Console.WriteLine(root.ToTreeDiagram(x => x.Name));
/*
A
└ B
└ C
└ D
*/
nodesDic["B"].Dispose();
/*
Start disposing B.
Start disposing D.
sender:D ,TreeAction:Leave
Finished disposing D.
Start disposing C.
sender:C ,TreeAction:Leave
Finished disposing C.
sender:B ,TreeAction:Leave
Finished disposing B.
*/
Console.WriteLine(root.ToTreeDiagram(x => x.Name));
/*
A
*/ノードBの破棄処理の過程で、子孫ノードを末端から順に破棄・切り離し処理が実行されました。
- ノードB:破棄開始
- ノードD:破棄開始
- ノードD:親ノードから離脱
- ノードD:破棄完了
- ノードC:破棄開始
- ノードC:親ノードから離脱
- ノードC:破棄完了
- ノードB:親ノードから離脱
- ノードB:破棄完了
| 処理過程 | 処理範囲 | 順序 |
|---|---|---|
| 破棄開始 | 対象と子孫(レベルオーダーの逆順) | B,D,C |
| 切り離し | 子孫(レベルオーダーの逆順)と対象 | D,C,B |
| 破棄完了 | 子孫(レベルオーダーの逆順)と対象 | D,C,B |
Disposeが呼ばれる順はB,D,C(Disposeを直接呼ばれたノード、レベルオーダーの逆順)、
切り離される順はD,C,B(レベルオーダーの逆順)、
Dispose処理が完了する順もD,C,Bとなります。
派生先にてIDisposableを実装している場合、子孫にIDisposableを実装していないノードが存在するツリー構造が組み上がることも考えられます。
その場合は祖先ノードが破棄されると、IDisposableを実装していないノードは切り離し処理のみ実行されます。
public class DspObsNamedNode : ObservableNamedNode, IDisposable {
private bool disposedValue;
protected override void Dispose(bool disposing) {
if (disposedValue) return;
if (disposing) {
Console.WriteLine($"Start disposing {this.Name}.");
}
base.Dispose(disposing);
Console.WriteLine($"Finished disposing {this.Name}.");
disposedValue = true;
}
public void Dispose() {
Dispose(disposing: true);
GC.SuppressFinalize(this);
}
}var dic = new List<ObservableNamedNode>() {
new DspObsNamedNode(){ Name = "A" },
new DspObsNamedNode(){ Name = "B" },
new ObservableNamedNode(){ Name = "C" },
new ObservableNamedNode(){ Name = "D" },
new DspObsNamedNode(){ Name = "E" },
}.ToDictionary(x => x.Name, x => x);
var root = dic.Values.AssembleAsNAryTree(1);
EventHandler<StructureChangedEventArgs<ObservableNamedNode>> structreChangedHdlr = (s, e) => {
if (s == e.Target && e.IsAncestorChanged) {
Console.WriteLine($"sender:{e.Target} ,TreeAction:{e.TreeAction}");
}
};
foreach (var node in root.PreOrder()) {
node.StructureChanged += structreChangedHdlr;
}
Console.WriteLine(root.ToTreeDiagram(x => x.Name));
/*
A
└ B
└ C
└ D
└ E
*/
(dic["B"] as DspObsNamedNode)?.Dispose();
/*
Start disposing B.
Start disposing E.
sender:E ,TreeAction:Leave
Finished disposing E.
sender:D ,TreeAction:Leave
sender:C ,TreeAction:Leave
sender:B ,TreeAction:Leave
Finished disposing B.
*/
Console.WriteLine(root.ToTreeDiagram(x => x.Name));
/*
A
*/