ExtensionMethodsSample_ja - Houzkin/TreeStructures GitHub Wiki
詳細はソースコードを参照
数が多いので、複雑なメソッドをピックアップします。
/// <summary>
/// 現在のノードを起点としてツリー構造を展開し列挙します。
/// 列挙の過程でノードを追加・更新するためのカスタムロジックを指定できます。
/// </summary>
/// <typeparam name="T">ノードの型。</typeparam>
/// <param name="startNode">列挙を開始する起点のノード。</param>
/// <param name="getNodes">
/// 指定したノードに基づいて追加すべきノードを決定する関数。
/// 現在のノードを引数に取り、それに関連するノードのコレクションを返します。
/// </param>
/// <param name="updatePendingNodes">
/// 列挙中にまだ列挙されていないノードのリストを更新するための関数。
/// この関数は以下の引数を取ります:
/// 第１引数：現在のノード。<paramref name="getNodes"/> に最初の引数として渡された値です。
/// 第２引数：現在のノードに対して追加された新しいノードのコレクション。<paramref name="getNodes"/> の戻り値です。
/// 第３引数：まだ列挙されていない残りのコレクション。
/// 戻り値：このコレクションの先頭要素がまだ <paramref name="getNodes"/> に渡されていない場合、その要素が次に渡されます。
/// すでに <paramref name="getNodes"/> に渡された要素であれば、その要素は列挙されます。
/// </param>
public static IEnumerable<T> Traverse<T>(this ITreeNode<T> startNode,
Func<T, IEnumerable<T?>> getNodes,
Func<T, IEnumerable<T?>,IEnumerable<T?>, IEnumerable<T?>> updatePendingNodes)
where T : ITreeNode<T> { }Traverseメソッドは様々な列挙方法を実現できる、汎用性に富んだメソッドです。
ライブラリ内においても頻繁に使用されていますが、引数と列挙の挙動が難解なため補足をしておきます。
PreOrderを実現するために以下のように記述しています。
public static IEnumerable<T> PreOrder<T>(this ITreeNode<T> self) where T : ITreeNode<T>{
return self.Traverse(
a => a.Children,
(a, b, c) => b.Prepende(a).Concat(c));// a, b[...], c[...]
}getNodesで指定するa => a.Childrenによって列挙に加えるノードを取得します。
次の引数updatePendingNodesでは、この戻り値が第2引数:bに割り当てられ、(a,b,c)=>b.Prepend(a).Concat(c)と、列挙の順序を指定しています。
実際の順序としては、a, a.Children[0], a.Children[1]..., C[0], C[1]... となります。
ここで先頭の要素aは既にgetNodesの引数として使用されているのでaが列挙されます。
そして、次の要素a.Children[0]に対してgetNodesの関数が適用され、a.Children[1]以降の要素がupdatePendingNodesの第3引数:cとして使用されます。
同様にPostOrderの挙動を追ってみます。
public static IEnumerable<T> PostOrder<T>(this ITreeNode<T> self) where T : ITreeNode<T>{
return self.Traverse(
a => a.Children,
(a, b, c) => b.Append(a).Concat(c));// b[...], a, c[...]
}getNodesに関してはPreOrderと同じです。
updatePendingNodesではaとbの順序がPreOrderと逆になります。
順序としては、a.Children[0], a.Children[1]..., a, C[0], C[1]... です。
ここで先頭のa.Children[0]はまだgetNodesの引数として使用されていません。
よって、a.Children[0]は列挙されないままgetNodesが適用され、a.Children[1]以降の要素がそのままupdatePendingNodesの第3引数:cとして使用されます。
このような振る舞いを応用して、祖先を遡る場合は
public static IEnumerable<T> Upstream<T>(this ITreeNode<T> self) where T : ITreeNode<T> {
return self.Traverse(
a => new T?[1] { a.Parent },
(a, b, c) => new T?[1] { a }.Concat(b).Concat(c));
}Leafのみを列挙する場合は
public static IEnumerable<T> Leafs<T>(this ITreeNode<T> self) where T : ITreeNode<T> {
return self.Traverse(
a => a.Children,
(a, b, c) => (b.Any() ? b : new T?[1] { a }).Concat(c));
}となります。
public static IEnumerable<T> DescendArrivals<T, Trc>(this ITreeNode<T> self, Func<T, Trc> selector, IEnumerable<Trc> trace, IEqualityComparer<Trc>? comparer = null)
where T : ITreeNode<T> ;
public static IEnumerable<T> DescendArrivals<T>(this ITreeNode<T> self,Func<T,bool> predicate)
where T:ITreeNode<T>;使用例：
A
├ B
│ ├ D
│ │ ├ H
│ │ └ I
│ └ E
│ ├ J
│ └ K
└ b
├ F
└ 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,dpublic static IReadOnlyList<IEnumerable<T>> DescendTraces<T,Trc>(this ITreeNode<T> self,Func<T,Trc> selector,IEnumerable<Trc> trace,IEqualityComparer<Trc>? comparer = null)
where T : ITreeNode<T> ;
public static IReadOnlyList<IEnumerable<T>> DescendTraces<T>(this ITreeNode<T> self, Func<T, bool> predicate)
where T:ITreeNode<T>;使用例：
var nodetraces = root.DescendTraces(
x => x.Name,
new string[] { "A", "B", "D" },
Equality<string>.ComparerBy(x => x.ToUpper()));
foreach(var trace in nodetraces)
Console.WriteLine(string.Join(",", trace.Select(x => x.Name)));
// A,B,D
// A,b,d