Repository navigation
Tutorial2.ja
ツリー構造を表すインターフェイスとして、ITreeNodeとIMutableTreeNodeを定義しています。
ITreeNode.cs
public interface ITreeNode<out TNode> where TNode : ITreeNode<TNode> {
TNode? Parent { get; }
IEnumerable<TNode> Children { get; }
}
public interface IMutableTreeNode<TNode> : ITreeNode<TNode>
where TNode : IMutableTreeNode<TNode> {
TNode AddChild(TNode child);
TNode InsertChild(int index, TNode child);
TNode RemoveChild(TNode child);
IReadOnlyList<TNode> ClearChildren();
}次のコードで、GeneralTreeNodeにて定義されている追加・削除メソッドを使用します。
既に親ノードが設定されているノードを子ノードとして追加する場合、親子関係も変更されます。
var nodes = "ABCDEF".ToDictionary(x => x.ToString(), x => new NamedNode() { Name = x.ToString() });
// Add,Insert
nodes["A"].AddChild(nodes["B"]).AddChild(nodes["C"]).InsertChild(0, nodes["D"]).InsertChild(3, nodes["E"]);
nodes["E"].AddChild(nodes["F"]);
foreach(var root in nodes.Values.Where(n => n.IsRoot()))
Console.WriteLine(root.ToTreeDiagram(x => x.Name));
/*
A
├ D
├ B
├ C
└ E
└ F
*/
// Move
nodes["B"].AddChild(nodes["C"]);
foreach(var root in nodes.Values.Where(n => n.IsRoot()))
Console.WriteLine(root.ToTreeDiagram(x => x.Name));
/*
A
├ D
├ B
│ └ C
└ E
└ F
*/
// Remove
nodes["A"].RemoveChild(nodes["E"]);
foreach(var root in nodes.Values.Where(n => n.IsRoot()))
Console.WriteLine(root.ToTreeDiagram(x => x.Name));
/*
A
├ D
└ B
└ C
E
└ F
*/
// Remove all child nodes.
nodes["A"].ClearChildren();
foreach(var root in nodes.Values.Where(n => n.IsRoot()))
Console.WriteLine(root.ToTreeDiagram(x => x.Name));
/*
A
B
└ C
D
E
└ F
*/追加によって兄弟ノードの重複あるいは循環が発生する場合は、追加処理は実行されません。
var nodes = "ABCDEF".ToDictionary(x => x.ToString(), x => new NamedNode() { Name = x.ToString() });
nodes.Values.AssembleAsNAryTree(2);
Console.WriteLine(nodes["A"].ToTreeDiagram(x => x.Name));
/*
A
├ B
│ ├ D
│ └ E
└ C
└ F
*/
nodes["A"].AddChild(nodes["B"]);
Console.WriteLine(nodes["A"].ToTreeDiagram(x => x.Name));
/* Node B cannot be added to Node A because it is a duplicate.
A
├ B
│ ├ D
│ └ E
└ C
└ F
*/
nodes["D"].AddChild(nodes["A"]);
Console.WriteLine(nodes["A"].ToTreeDiagram(x => x.Name));
/* Node A cannot be added to Node D because it would create a cycle.
A
├ B
│ ├ D
│ └ E
└ C
└ F
*/IMutableTreeNodeに対する拡張メソッドによって、ノードの分解や条件を満たすノードの削除、Tryメソッドなどを利用できます。
各編集メソッドの戻り値は、追加メソッドの場合は現在のノード(親となるノード)、削除メソッドの場合は削除されたノードとなります。
Tryメソッドで、正常に処理が実行された場合も同様の振る舞いです。
これにより、削除されたノードや追加に失敗したノードにアクセスしやすくなります。
次のコードで、ノードの分解と条件に一致した子孫の削除を行います。
var root1 = new List<NodePath<string>>() {
new("A","B","C","D"),
new("A","B","E"),
new("A","F"),
}.AssembleTreeByPath(x => new NamedNode() { Name = x.Last() });
var nodes = root1.LevelOrder().ToDictionary(x => x.Name, x => x);
foreach (var rt in nodes.Values.Where(x => x.IsRoot()))
Console.WriteLine(rt.ToTreeDiagram(x => x.Name));
/*
A
├ B
│ ├ C
│ │ └ D
│ └ E
└ F
*/
var disassembleNodes = nodes["B"].Disassemble();
Console.WriteLine("Disassemble nodes: "+ string.Join(",", disassembleNodes));
// Disassemble nodes: E,C,D,B
foreach (var rt in nodes.Values.Where(x => x.IsRoot()))
Console.WriteLine(rt.ToTreeDiagram(x => x.Name));
/*
A
└ F
B
C
E
D
*/
var root2 = "ABCDEFGHIJK".ToCharArray().AssembleAsNAryTree(3, x => new NamedNode() { Name = x.ToString() });
nodes = root2.LevelOrder().ToDictionary(x => x.Name, x => x);
foreach (var rt in nodes.Values.Where(x => x.IsRoot()))
Console.WriteLine(rt.ToTreeDiagram(x => x.Name));
/*
A
├ B
│ ├ E
│ ├ F
│ └ G
├ C
│ ├ H
│ ├ I
│ └ J
└ D
└ K
*/
var removedDescendants = root2.RemoveAllDescendant(x => x.BranchIndex() == 1);
Console.WriteLine("Removed Descendants: " + string.Join(",", removedDescendants));
//Disassemble nodes: C,F
foreach (var rt in nodes.Values.Where(x => x.IsRoot()))
Console.WriteLine(rt.ToTreeDiagram(x => x.Name));
/*
A
├ B
│ ├ E
│ └ G
└ D
└ K
C
├ H
├ I
└ J
F
*/対象ノードからの走査方法を提供しています。
var root = "ABCDEF".ToCharArray().AssembleAsNAryTree(2, x => new NamedNode() { Name = x.ToString() });
Console.WriteLine(root.ToTreeDiagram(x => x.Name));
/*
A
├ B
│ ├ D
│ └ E
└ C
└ F
*/
var lvseaq = string.Join(',', root.LevelOrder());
Console.WriteLine(lvseaq);
//A,B,C,D,E,F
var preseaq = string.Join(',', root.PreOrder());
Console.WriteLine(preseaq);
//A,B,D,E,C,F
var postseaq = string.Join(',', root.PostOrder());
Console.WriteLine(postseaq);
//D,E,B,F,C,A
var inseaq = string.Join(',', root.InOrder());
Console.WriteLine(inseaq);
//D,B,E,A,F,Cvar root = new List<NodePath<string>>() {
new ("A","B"),
new ("A","C","D","E"),
new ("A","C","D","F","G"),
new ("A","C","I"),
new ("A","H","J"),
}.AssembleTreeByPath(x => new NamedNode() { Name = x.Last() });
var nodes = root.PreOrder().ToDictionary(x => x.Name, x => x);
Console.WriteLine(nodes["A"].ToTreeDiagram(x=>x.Name));
/*
A
├ B
├ C
│ ├ D
│ │ ├ E
│ │ └ F
│ │ └ G
│ └ I
└ H
└ J
*/
var nodeD = nodes["D"];
Console.WriteLine($"Upstream:{string.Join(",",nodeD.Upstream())}");
Console.WriteLine($"Ancestors:{string.Join(",",nodeD.Ancestors())}");
Console.WriteLine($"Leafs:{string.Join(",",nodeD.Leafs())}");
Console.WriteLine($"Siblings:{string.Join(",",nodeD.Siblings())}");
Console.WriteLine($"Generations:{string.Join(",",nodeD.Generations())}");
/*
Upstream:D,C,A
Ancestors:C,A
Leafs:E,G
Siblings:D,I
Generations:D,I,J
*/上記ツリーを流用します。
GetNodeIndex、GetNodePathで、ツリー内の位置を示します。
Console.WriteLine(tree.ToTreeDiagram(x =>$"{x.Name},NodeIndex:{x.GetNodeIndex()}"));
/*
A,NodeIndex:[]
├ B,NodeIndex:[0]
├ C,NodeIndex:[1]
│ ├ D,NodeIndex:[1,0]
│ │ ├ E,NodeIndex:[1,0,0]
│ │ └ F,NodeIndex:[1,0,1]
│ │ └ G,NodeIndex:[1,0,1,0]
│ └ I,NodeIndex:[1,1]
└ H,NodeIndex:[2]
└ J,NodeIndex:[2,0]
*/
Console.WriteLine(tree.ToTreeDiagram(x =>$"{x.Name},NodePath:{x.GetNodePath(n=>n.Name)}"));
/*
A,NodePath:A
├ B,NodePath:A/B
├ C,NodePath:A/C
│ ├ D,NodePath:A/C/D
│ │ ├ E,NodePath:A/C/D/E
│ │ └ F,NodePath:A/C/D/F
│ │ └ G,NodePath:A/C/D/F/G
│ └ I,NodePath:A/C/I
└ H,NodePath:A/H
└ J,NodePath:A/H/J
*/各ノードの位置関係などを示すパラメータを示します。
Console.WriteLine(root.ToTreeDiagram(x => $"{x.Name}, Depth:{x.Depth()}, Height:{x.Height()}, Width:{x.Width()}, BranchIndex:{x.BranchIndex()}"));
/*
A, Depth:0, Height:4, Width:1, BranchIndex:-1
├ B, Depth:1, Height:0, Width:3, BranchIndex:0
├ C, Depth:1, Height:3, Width:3, BranchIndex:1
│ ├ D, Depth:2, Height:2, Width:3, BranchIndex:0
│ │ ├ E, Depth:3, Height:0, Width:2, BranchIndex:0
│ │ └ F, Depth:3, Height:1, Width:2, BranchIndex:1
│ │ └ G, Depth:4, Height:0, Width:1, BranchIndex:0
│ └ I, Depth:2, Height:0, Width:3, BranchIndex:1
└ H, Depth:1, Height:1, Width:3, BranchIndex:2
└ J, Depth:2, Height:0, Width:3, BranchIndex:0
*/Depth : ルートノードを0とした、ルートノードからの距離
Height : リーフノードを0とした、最深のリーフノードからの距離
Width : 同世代にあたるノードの数
BranchIndex : 親ノードから割り当てられているインデックス
再度、上記ツリーを流用します。 拡張メソッドによって、親ノード以外のノードも取得できます。
Console.WriteLine($"Root:{nodeD.Root()}");
//Root:A
Console.WriteLine($"NextSibling:{nodeD.NextSibling()}");
//NextSibling:I
nodeD.PreviousSiblingOrSelf().When(
o => Console.WriteLine($"PreviousSibling:{o.Name}"),
x => Console.WriteLine($"{x.Name} is first sibling."));
//D is first sibling.対象ノードから子孫方向に向けて、各ノード毎に、条件に一致するノードを探索します。
DescendArrivalsメソッドは、条件を満たした末端のノード、DescendTracesは対象ノードから条件を満たした末端までの経路となったノードも返します。
引数に配列を取る場合は、階層を降りる度に次の要素と一致するかどうかを条件とします。 各階層にて各対応要素と一致し続けた、最後の要素を全て列挙します。
var root = "ABbDEFdHIJKL".ToCharArray().AssembleAsNAryTree(2, x => new NamedNode() { Name = x.ToString() });
Console.WriteLine(root.ToTreeDiagram(x => x.Name));
/*
A
├ B
│ ├ D
│ │ ├ H
│ │ └ I
│ └ E
│ ├ J
│ └ K
└ b
├ F
│ └ L
└ d
*/
var nodes = root.DescendArrivals(x => x.Name, new string[] { "A", "B", "D" },Equality<string>.ComparerBy(x=>x.ToUpper()));
Console.WriteLine(string.Join(",", nodes.Select(x => x.Name)));
//D,d
var nodeRoute1 = root.DescendTraces(x => x.Name, new string[] { "A", "B", "D" }, Equality<string>.ComparerBy(x => x.ToUpper()));
foreach(var route in nodeRoute1){
Console.WriteLine(string.Join(",", route.Select(x => x.Name)));
}
//A,B,D
//A,B,d配列に条件式を取った場合は、対象ノードを含め、条件が一致した末端の要素を列挙します。
nodes.Last().Parent?.AddChild(nodes.First());
Console.WriteLine(root.ToTreeDiagram(x => x.Name));
/*
A
├ B
│ └ E
│ ├ J
│ └ K
└ b
├ F
│ └ L
├ d
└ D
├ H
└ I
*/
var nodes2 = root.DescendArrivals(x => x.BranchIndex() > 0 || x.IsRoot());
Console.WriteLine(string.Join(",", nodes2.Select(x => x.Name)));
//d,I
var nodeRoute2 = root.DescendTraces(x=>x.BranchIndex() > 0 || x.IsRoot());
foreach(var route in nodeRoute2){
Console.WriteLine(string.Join(",",route.Select(x => x.Name)));
}
//A,b,d
//A,b,D,I