Feedback

# C# - TreeEnumerator

Veröffentlicht von am 11/2/2015
(0 Bewertungen)
Die Klasse TreeEnumerable enthält Erweiterungsmethoden welche es erlauben die Elemente von hierarchischen Objektstrukturen linear (als IEnumerable<T>) zu durchlaufen.

Die Elemente können dabei entweder "depth first" oder "breadth first" durchlaufen werden.
```using System;
using System.Collections.Generic;
/// <summary>
///   Provides a set of static extension methods, which supports simple iteration
///   over a graph stuctures.
/// </summary>
public static class TreeEnumerable
{

/// <summary>
///   Linearizes the specified graph, traversing it breadth-first.
/// </summary>
/// <typeparam name="TNode">
///   The type of the nodes.
/// </typeparam>
/// <param name="nodes">
///   A collection of nodes which are representing the root elements of the graph.
/// </param>
/// <param name="getSubNodes">
///   A function that defines how to get the sub notes for each node.
/// </param>
/// <returns>
///   An IEnumerable(Of TNode) that contains elements from the graph in a breadth-first linearized sequence.
/// </returns>
public static IEnumerable<TNode> BreadthFirst<TNode>(this IEnumerable<TNode> nodes,
Func<TNode, IEnumerable<TNode>> getSubNodes)
{
Queue<TNode> queue = new Queue<TNode>(256);

foreach (TNode node in nodes)
{
queue.Enqueue(node);
}

}

Func<TNode, IEnumerable<TNode>> getSubNodes)
{
TNode node;

while (queue.Count > 0)
{
node = queue.Dequeue();

if (node == null)
{
yield break;
}

foreach (TNode subNode in getSubNodes(node))
{
queue.Enqueue(subNode);
}

yield return node;
}
}

#endregion

/// <summary>
///   Linearizes the specified graph, traversing it breadth-first.
/// </summary>
/// <typeparam name="TNode">
///   The type of the nodes.
/// </typeparam>
/// <param name="nodes">
///   A collection of nodes which are representing the root elements of the graph.
/// </param>
/// <param name="getSubNodes">
///   A function that defines how to get the sub notes for each node.
/// </param>
/// <param name="repeatNodes">
///   A value that determines if nodes are being traversed repeated.
/// </param>
/// <returns>
///   An IEnumerable(Of TNode) that contains elements from the graph in a breadth-first linearized sequence.
/// </returns>
public static IEnumerable<TNode> BreadthFirst<TNode>(this IEnumerable<TNode> nodes,
Func<TNode, IEnumerable<TNode>> getSubNodes,
Boolean repeatNodes)
{
HashSet<TNode> passedNodes = new HashSet<TNode>();
Queue<TNode> queue = new Queue<TNode>(256);

if (repeatNodes)
{
}

foreach (TNode node in nodes)
{
if (passedNodes.Contains(node))
{
continue;
}

queue.Enqueue(node);
}

}

Func<TNode, IEnumerable<TNode>> getSubNodes,
HashSet<TNode> passedNodes)
{
TNode node;

while (queue.Count > 0)
{
node = queue.Dequeue();

if (node == null)
{
yield break;
}

foreach (TNode subNode in getSubNodes(node))
{
if (passedNodes.Contains(subNode))
{
continue;
}

queue.Enqueue(subNode);
}

yield return node;
}
}

#endregion

#region DepthFirst

/// <summary>
///   Linearizes the specified graph, traversing it depth-first.
/// </summary>
/// <typeparam name="TNode">
///   The type of the nodes.
/// </typeparam>
/// <param name="node">
///   A node that represents the root element of the graph.
/// </param>
/// <param name="getSubNodes">
///   A function that defines how to get the sub notes for each node.
/// </param>
/// <returns>
///   An IEnumerable(Of TNode) that contains elements from the graph in a depth-first linearized sequence.
/// </returns>
public static IEnumerable<TNode> DepthFirst<TNode>(TNode node, Func<TNode, IEnumerable<TNode>> getSubNodes)
{
return new[] { node }.DepthFirst(getSubNodes);
}

/// <summary>
///   Linearizes the specified graph, traversing it depth-first.
/// </summary>
/// <typeparam name="TNode">
///   The type of the nodes.
/// </typeparam>
/// <param name="nodes">
///   A collection of nodes which are representing the root elements of the graph.
/// </param>
/// <param name="getSubNodes">
///   A function that defines how to get the sub notes for each node.
/// </param>
/// <returns>
///   An IEnumerable(Of TNode) that contains elements from the graph in a depth-first linearized sequence.
/// </returns>
public static IEnumerable<TNode> DepthFirst<TNode>(this IEnumerable<TNode> nodes,
Func<TNode, IEnumerable<TNode>> getSubNodes)
{
foreach (TNode node in nodes)
{
yield return node;

foreach (TNode subNode in getSubNodes(node).DepthFirst(getSubNodes))
{
yield return subNode;
}
}
}

#endregion

#region DepthFirst (repeat Nodes)

/// <summary>
///   Linearizes the specified graph, traversing it depth-first.
/// </summary>
/// <typeparam name="TNode">
///   The type of the nodes.
/// </typeparam>
/// <param name="nodes">
///   A collection of nodes which are representing the root elements of the graph.
/// </param>
/// <param name="getSubNodes">
///   A function that defines how to get the sub notes for each node.
/// </param>
/// <param name="repeatNodes">
///   A value that determines if nodes are being traversed repeated.
/// </param>
/// <returns>
///   An IEnumerable(Of TNode) that contains elements from the graph in a depth-first linearized sequence.
/// </returns>
public static IEnumerable<TNode> DepthFirst<TNode>(this IEnumerable<TNode> nodes,
Func<TNode, IEnumerable<TNode>> getSubNodes,
Boolean repeatNodes)
{
if (repeatNodes)
{
return nodes.DepthFirst(getSubNodes);
}

return nodes.DepthFirst(getSubNodes, new HashSet<TNode>());
}

private static IEnumerable<TNode> DepthFirst<TNode>(this IEnumerable<TNode> nodes,
Func<TNode, IEnumerable<TNode>> getSubNodes,
HashSet<TNode> passedNodes)
{
foreach (TNode node in nodes)
{
if (passedNodes.Contains(node))
{
continue;
}

yield return node;

foreach (TNode subNode in getSubNodes(node).DepthFirst(getSubNodes, passedNodes))
{
yield return subNode;
}
}
}

#endregion
}
```
Abgelegt unter LINQ, Baumstruktur.

## 1 Kommentare zum Snippet

Tachyon schrieb am 11/2/2015:
Usage:
`// class Item {  public Item[] Items { get; set; } }var allItemsDepthFirst = items.DepthFirst(i => i.Items);var allItemsBreadthFirst = items.BreadthFirst(i => i.Items);`

Logge dich ein, um hier zu kommentieren!