← Back to branch summary

~ubuntu-branches/ubuntu/trusty/monodevelop/trusty-proposed

« back to all changes in this revision

Viewing changes to external/nrefactory/ICSharpCode.NRefactory/Utils/TreeTraversal.cs

  • Committer: Package Import Robot
  • Author(s): Jo Shields
  • Date: 2013-05-12 09:46:03 UTC
  • mto: This revision was merged to the branch mainline in revision 29.
  • Revision ID: package-import@ubuntu.com-20130512094603-mad323bzcxvmcam0
Tags: upstream-4.0.5+dfsg
Import upstream version 4.0.5+dfsg

Show diffs side-by-side

added added

removed removed

Lines of Context:
external/nrefactory/ICSharpCode.NRefactory/Utils/TreeTraversal.cs
 
1
// Copyright (c) 2010-2013 AlphaSierraPapa for the SharpDevelop Team
 
2
// 
 
3
// Permission is hereby granted, free of charge, to any person obtaining a copy of this
 
4
// software and associated documentation files (the "Software"), to deal in the Software
 
5
// without restriction, including without limitation the rights to use, copy, modify, merge,
 
6
// publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons
 
7
// to whom the Software is furnished to do so, subject to the following conditions:
 
8
// 
 
9
// The above copyright notice and this permission notice shall be included in all copies or
 
10
// substantial portions of the Software.
 
11
// 
 
12
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED,
 
13
// INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR
 
14
// PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE
 
15
// FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR
 
16
// OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
 
17
// DEALINGS IN THE SOFTWARE.
 
18
 
 
19
using System;
 
20
using System.Collections.Generic;
 
21
 
 
22
namespace ICSharpCode.NRefactory.Utils
 
23
{
 
24
        /// <summary>
 
25
        /// Static helper methods for traversing trees.
 
26
        /// </summary>
 
27
        public static class TreeTraversal
 
28
        {
 
29
                /// <summary>
 
30
                /// Converts a tree data structure into a flat list by traversing it in pre-order.
 
31
                /// </summary>
 
32
                /// <param name="root">The root element of the tree.</param>
 
33
                /// <param name="recursion">The function that gets the children of an element.</param>
 
34
                /// <returns>Iterator that enumerates the tree structure in pre-order.</returns>
 
35
                public static IEnumerable<T> PreOrder<T>(T root, Func<T, IEnumerable<T>> recursion)
 
36
                {
 
37
                        return PreOrder(new T[] { root }, recursion);
 
38
                }
 
39
                
 
40
                /// <summary>
 
41
                /// Converts a tree data structure into a flat list by traversing it in pre-order.
 
42
                /// </summary>
 
43
                /// <param name="input">The root elements of the forest.</param>
 
44
                /// <param name="recursion">The function that gets the children of an element.</param>
 
45
                /// <returns>Iterator that enumerates the tree structure in pre-order.</returns>
 
46
                public static IEnumerable<T> PreOrder<T>(IEnumerable<T> input, Func<T, IEnumerable<T>> recursion)
 
47
                {
 
48
                        Stack<IEnumerator<T>> stack = new Stack<IEnumerator<T>>();
 
49
                        try {
 
50
                                stack.Push(input.GetEnumerator());
 
51
                                while (stack.Count > 0) {
 
52
                                        while (stack.Peek().MoveNext()) {
 
53
                                                T element = stack.Peek().Current;
 
54
                                                yield return element;
 
55
                                                IEnumerable<T> children = recursion(element);
 
56
                                                if (children != null) {
 
57
                                                        stack.Push(children.GetEnumerator());
 
58
                                                }
 
59
                                        }
 
60
                                        stack.Pop().Dispose();
 
61
                                }
 
62
                        } finally {
 
63
                                while (stack.Count > 0) {
 
64
                                        stack.Pop().Dispose();
 
65
                                }
 
66
                        }
 
67
                }
 
68
                
 
69
                /// <summary>
 
70
                /// Converts a tree data structure into a flat list by traversing it in post-order.
 
71
                /// </summary>
 
72
                /// <param name="root">The root element of the tree.</param>
 
73
                /// <param name="recursion">The function that gets the children of an element.</param>
 
74
                /// <returns>Iterator that enumerates the tree structure in post-order.</returns>
 
75
                public static IEnumerable<T> PostOrder<T>(T root, Func<T, IEnumerable<T>> recursion)
 
76
                {
 
77
                        return PostOrder(new T[] { root }, recursion);
 
78
                }
 
79
                
 
80
                /// <summary>
 
81
                /// Converts a tree data structure into a flat list by traversing it in post-order.
 
82
                /// </summary>
 
83
                /// <param name="input">The root elements of the forest.</param>
 
84
                /// <param name="recursion">The function that gets the children of an element.</param>
 
85
                /// <returns>Iterator that enumerates the tree structure in post-order.</returns>
 
86
                public static IEnumerable<T> PostOrder<T>(IEnumerable<T> input, Func<T, IEnumerable<T>> recursion)
 
87
                {
 
88
                        Stack<IEnumerator<T>> stack = new Stack<IEnumerator<T>>();
 
89
                        try {
 
90
                                stack.Push(input.GetEnumerator());
 
91
                                while (stack.Count > 0) {
 
92
                                        while (stack.Peek().MoveNext()) {
 
93
                                                T element = stack.Peek().Current;
 
94
                                                IEnumerable<T> children = recursion(element);
 
95
                                                if (children != null) {
 
96
                                                        stack.Push(children.GetEnumerator());
 
97
                                                } else {
 
98
                                                        yield return element;
 
99
                                                }
 
100
                                        }
 
101
                                        stack.Pop().Dispose();
 
102
                                        if (stack.Count > 0)
 
103
                                                yield return stack.Peek().Current;
 
104
                                }
 
105
                        } finally {
 
106
                                while (stack.Count > 0) {
 
107
                                        stack.Pop().Dispose();
 
108
                                }
 
109
                        }
 
110
                }
 
111
        }
 
112
}