ExtensionMethodsSample

Extension Methods

For more details, refer to the source code.

Here are serveral methods that require further explanation.

ITreeNode

Traverse

/// <summary>
/// Expands and enumerates a tree structure starting from the current node, allowing custom logic for adding and updating nodes during the traversal.
/// </summary>
/// <typeparam name="T">The type of the node.</typeparam>
/// <param name="startNode">The starting node for the traversal.</param>
/// <param name="getNodes">
/// A function that determines additional nodes to add based on the specified node.  
/// Takes the current node as an argument and returns a collection of nodes related to it.
/// </param>
/// <param name="updatePendingNodes">
/// A function that updates the list of unenumerated nodes during traversal. This function takes the following arguments:
/// <list type="table">
/// <listheader><term>1st arg</term>
/// <description>The current node. The value passed as the first argument to the <paramref name="getNodes"/> function.<br/></description>
/// </listheader>
/// <listheader><term>2nd arg</term>
/// <description>The collection of new nodes added for the current node. The return value of the <paramref name="getNodes"/> function.<br/></description>
/// </listheader>
/// <listheader><term>3rd arg</term>
/// <description>The remaining unenumerated collection.  <br/></description>
/// </listheader>
/// <listheader><term>Return</term>
/// <description>If it has already been used as an argument to <paramref name="getNodes"/>, that element will be enumerated.
/// If the head element of this collection has not been used as an argument to <paramref name="getNodes"/>, it will be passed as the argument to <paramref name="getNodes"/>. <br/>
/// </description></listheader>
/// </list></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 method is a highly flexible utility that supports various enumeration patterns. It is widely used throughout the library, but due to its complex parameters and behavior, some aditional explanation is warranted.

For example, it can be used to implement a PreOrder traversal, as shown below.

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[...]
}

First, nodes to be added to the enumeration are retrieved using a => a.Children, specified as the getNodes function.
Next, the enumeration order is defined by the updatePendingNodes function: (a, b, c) => b.Prepend(a).Concat(c), where b is the collection returned from getNodes, and c is the remaining unenumerated collection.

The actual enumeration order will be: a, a.Children[0], a.Children[1], ..., C[0], C[1], ...
Here, the first element a has already been passed to getNodes, so it is enumerated immediately.
Next, getNodes is applied to the next element, a.Children[0], while the remaining elements, such as a.Children[1] and onward, are passed as the third argument c to updatePendingNodes.

Let's also follow how the traversal behaves in the case of 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[...]
}

The getNodes logic is the same as in PreOrder.
In updatePendingNodes, however, the order of a and b is reversed compared to PreOrder.
The resulting traversal oder is: a.Children[0], a.Children[1], ..., a, C[0], C[1], ...
Here, the first element a.Children[0] has not yet been passed to getNodes.
Therefore, a.Children[0] is not enumerated immediately; instead, it is passed to getNodes, and the remaining elements (a.Children[1], etc.) are passed as the third argument c to updatePendingNodes.

By leveraging this behavior, you can implement upward traversal as follows:

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));
}

Or enumerate only leaf nodes like this:

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));
}

DescendArrivals

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>;

example:

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,d

DescendTraces

public 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>;

example:

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