-
Notifications
You must be signed in to change notification settings - Fork 7
/
PostOrder.cs
119 lines (105 loc) · 4.47 KB
/
PostOrder.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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
namespace TreeLib.Depthfirst
{
using System;
using System.Collections.Generic;
using System.Linq;
/// <summary>
/// Implements a Generic class that can traverse a tree with tree nodes of type
/// <typeparamref name="T"/> and supports invoking calls on each node via
/// Generic method in the Traversal method.
/// </summary>
/// <typeparam name="TRESULT"></typeparam>
/// <typeparam name="T"></typeparam>
public class PostOrder<TRESULT, T>
{
/// <summary>
/// This code shows the first development version of the PostOrder
/// traversal algorithm as published by Dave Remy in his 2010 RemLog blog at:
/// https://blogs.msdn.microsoft.com/daveremy/2010/03/16/non-recursive-post-order-depth-first-traversal-in-c/
///
/// </summary>
/// <param name="root">This object points at the root of the tree structure.</param>
/// <param name="children">This Generic method implements a way of enumerating all
/// childrens for the root or current node in the traversal.</param>
/// <param name="ret">This object contains result data of the traversal and should
/// have been initialized by the caller.</param>
/// <param name="process">This method accepts the current node and the result object
/// <paramref name="ret"/> as aparameter to the required processing on each node.</param>
/// <param name="progress">Optional generic method accepts the cuurent node as parameter
/// and implements a progress indicator.</param>
/// <param name="exception">Optional generic method accepts the current node <typeparamref name="T"/>
/// and result object <paramref name="ret"/> as parameter to implement exception handling
/// for browsing of children.</param>
public TRESULT Traverse(T root
, Func<T, IEnumerable<T>> children
, TRESULT ret
, Func<TRESULT, T, TRESULT> process
, Action<T> progress = null
, Func<TRESULT, Exception, T, TRESULT> exception = null
)
{
var toVisit = new Stack<T>();
var visitedAncestors = new Stack<T>();
toVisit.Push(root);
while (toVisit.Count > 0)
{
var current = toVisit.Peek();
int iChildrenCount = 0;
try
{
iChildrenCount = children(current).Count();
}
catch (Exception e)
{
if (exception != null)
ret = exception(ret, e, current); // exception handling
}
if (iChildrenCount > 0)
{
if (current.Equals(PeekOrDefault(visitedAncestors)) == false)
{
visitedAncestors.Push(current);
try
{
PushReverse(toVisit, children(current).ToArray());
}
catch (Exception e)
{
if (exception != null)
ret = exception(ret, e, current); // exception handling
}
continue;
}
visitedAncestors.Pop();
}
if (progress != null)
progress(current);
ret = process(ret, current); // Process the node
toVisit.Pop();
}
return ret;
}
/// <summary>
/// Return the top element of stack or null if the Stack is empty.
/// </summary>
/// <param name="s"></param>
/// <returns></returns>
private T PeekOrDefault(Stack<T> s)
{
return s.Count == 0 ? default(T) : s.Peek();
}
/// <summary>
/// Push all children of a given node in reverse order into the
/// <seealso cref="Stack{T}"/> <paramref name="s"/>.
///
/// Use this to traverse the tree from left to right.
/// </summary>
/// <param name="s"></param>
/// <param name="list"></param>
private void PushReverse(Stack<T> s, T[] list)
{
foreach (var l in list.Reverse())
s.Push(l);
}
}
}