← Back to branch summary

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

« back to all changes in this revision

Viewing changes to contrib/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:
contrib/ICSharpCode.NRefactory/Utils/TreeTraversal.cs
1
 
// Copyright (c) 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
 
}