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
{
#region BreadthFirst
/// <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);
}
return BreadthFirst(queue, getSubNodes);
}
private static IEnumerable<TNode> BreadthFirst<TNode>(Queue<TNode> queue,
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
#region BreadthFirst (repeat Nodes)
/// <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)
{
return nodes.BreadthFirst(getSubNodes);
}
foreach (TNode node in nodes)
{
if (passedNodes.Contains(node))
{
continue;
}
passedNodes.Add(node);
queue.Enqueue(node);
}
return BreadthFirst(queue, getSubNodes, passedNodes);
}
private static IEnumerable<TNode> BreadthFirst<TNode>(Queue<TNode> queue,
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;
}
passedNodes.Add(subNode);
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;
}
passedNodes.Add(node);
yield return node;
foreach (TNode subNode in getSubNodes(node).DepthFirst(getSubNodes, passedNodes))
{
yield return subNode;
}
}
}
#endregion
}