-
-
Notifications
You must be signed in to change notification settings - Fork 9
/
Traverse.cs
104 lines (96 loc) · 3.33 KB
/
Traverse.cs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
namespace SuperLinq;
public partial class SuperEnumerable
{
/// <summary>
/// Traverses a tree in a breadth-first fashion, starting at a root node and using a user-defined function to
/// get the children at each node of the tree.
/// </summary>
/// <typeparam name="T">
/// The tree node type
/// </typeparam>
/// <param name="root">
/// The root of the tree to traverse.
/// </param>
/// <param name="childrenSelector">
/// The function that produces the children of each element.
/// </param>
/// <returns>
/// A sequence containing the traversed values.
/// </returns>
/// <exception cref="ArgumentNullException">
/// <paramref name="childrenSelector"/> is <see langword="null"/>.
/// </exception>
/// <remarks>
/// <para>
/// The tree is not checked for loops. If the resulting sequence needs to be finite then it is the
/// responsibility of <paramref name="childrenSelector"/> to ensure that loops are not produced.
/// </para>
/// <para>
/// This function defers traversal until needed and streams the results.
/// </para>
/// </remarks>
public static IEnumerable<T> TraverseBreadthFirst<T>(T root, Func<T, IEnumerable<T>> childrenSelector)
{
ArgumentNullException.ThrowIfNull(childrenSelector);
return Core(root, childrenSelector);
static IEnumerable<T> Core(T root, Func<T, IEnumerable<T>> childrenSelector)
{
var queue = new Queue<T>();
queue.Enqueue(root);
while (queue.Count != 0)
{
var current = queue.Dequeue();
yield return current;
foreach (var child in childrenSelector(current))
queue.Enqueue(child);
}
}
}
/// <summary>
/// Traverses a tree in a depth-first fashion, starting at a root node and using a user-defined function to get
/// the children at each node of the tree.
/// </summary>
/// <typeparam name="T">
/// The tree node type.
/// </typeparam>
/// <param name="root">
/// The root of the tree to traverse.
/// </param>
/// <param name="childrenSelector">
/// The function that produces the children of each element.
/// </param>
/// <returns>
/// A sequence containing the traversed values.
/// </returns>
/// <exception cref="ArgumentNullException">
/// <paramref name="childrenSelector"/> is <see langword="null"/>.
/// </exception>
/// <remarks>
/// <para>
/// The tree is not checked for loops. If the resulting sequence needs to be finite then it is the
/// responsibility of <paramref name="childrenSelector"/> to ensure that loops are not produced.
/// </para>
/// <para>
/// This function defers traversal until needed and streams the results.
/// </para>
/// </remarks>
public static IEnumerable<T> TraverseDepthFirst<T>(T root, Func<T, IEnumerable<T>> childrenSelector)
{
ArgumentNullException.ThrowIfNull(childrenSelector);
return Core(root, childrenSelector);
static IEnumerable<T> Core(T root, Func<T, IEnumerable<T>> childrenSelector)
{
var stack = new Stack<T>();
stack.Push(root);
while (stack.Count != 0)
{
var current = stack.Pop();
yield return current;
// because a stack pops the elements out in LIFO order, we need to push them in reverse
// if we want to traverse the returned list in the same order as was returned to us
foreach (var child in childrenSelector(current).Reverse())
stack.Push(child);
}
}
}
}