]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | /*============================================================================= |
2 | Copyright (c) 2001-2007 Hartmut Kaiser | |
3 | Copyright (c) 2001-2003 Daniel Nuffer | |
4 | http://spirit.sourceforge.net/ | |
5 | ||
6 | Use, modification and distribution is subject to the Boost Software | |
7 | License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at | |
8 | http://www.boost.org/LICENSE_1_0.txt) | |
9 | =============================================================================*/ | |
10 | ||
11 | #if !defined(PARSE_TREE_UTILS_IPP) | |
12 | #define PARSE_TREE_UTILS_IPP | |
13 | ||
14 | /////////////////////////////////////////////////////////////////////////////// | |
15 | namespace boost { | |
16 | namespace spirit { | |
17 | ||
18 | BOOST_SPIRIT_CLASSIC_NAMESPACE_BEGIN | |
19 | ||
20 | /////////////////////////////////////////////////////////////////////////////// | |
21 | // | |
22 | // Returnes the first leaf node of the given parsetree. | |
23 | // | |
24 | /////////////////////////////////////////////////////////////////////////////// | |
25 | template <typename T> | |
26 | inline tree_node<T> const & | |
27 | get_first_leaf (tree_node<T> const &node) | |
28 | { | |
29 | if (node.children.size() > 0) | |
30 | return get_first_leaf(*node.children.begin()); | |
31 | return node; | |
32 | } | |
33 | ||
34 | /////////////////////////////////////////////////////////////////////////////// | |
35 | // | |
36 | // Find a specified node through recursive search. | |
37 | // | |
38 | /////////////////////////////////////////////////////////////////////////////// | |
39 | template <typename T> | |
40 | inline bool | |
41 | find_node (tree_node<T> const &node, parser_id node_to_search, | |
42 | tree_node<T> const **found_node) | |
43 | { | |
44 | if (node.value.id() == node_to_search) { | |
45 | *found_node = &node; | |
46 | return true; | |
47 | } | |
48 | if (node.children.size() > 0) { | |
49 | typedef typename tree_node<T>::const_tree_iterator const_tree_iterator; | |
50 | ||
51 | const_tree_iterator end = node.children.end(); | |
52 | for (const_tree_iterator it = node.children.begin(); it != end; ++it) | |
53 | { | |
54 | if (find_node (*it, node_to_search, found_node)) | |
55 | return true; | |
56 | } | |
57 | } | |
58 | return false; // not found here | |
59 | } | |
60 | ||
61 | /////////////////////////////////////////////////////////////////////////////// | |
62 | // | |
63 | // The functions 'get_node_range' return a pair of iterators pointing at the | |
64 | // range, which containes the elements of a specified node. | |
65 | // | |
66 | /////////////////////////////////////////////////////////////////////////////// | |
67 | namespace impl { | |
68 | ||
69 | template <typename T> | |
70 | inline bool | |
71 | get_node_range (typename tree_node<T>::const_tree_iterator const &start, | |
72 | parser_id node_to_search, | |
73 | std::pair<typename tree_node<T>::const_tree_iterator, | |
74 | typename tree_node<T>::const_tree_iterator> &nodes) | |
75 | { | |
76 | // look at this node first | |
77 | tree_node<T> const &node = *start; | |
78 | ||
79 | if (node.value.id() == node_to_search) { | |
80 | if (node.children.size() > 0) { | |
81 | // full subrange | |
82 | nodes.first = node.children.begin(); | |
83 | nodes.second = node.children.end(); | |
84 | } | |
85 | else { | |
86 | // only this node | |
87 | nodes.first = start; | |
88 | nodes.second = start; | |
89 | std::advance(nodes.second, 1); | |
90 | } | |
91 | return true; | |
92 | } | |
93 | ||
94 | // look at subnodes now | |
95 | if (node.children.size() > 0) { | |
96 | typedef typename tree_node<T>::const_tree_iterator const_tree_iterator; | |
97 | ||
98 | const_tree_iterator end = node.children.end(); | |
99 | for (const_tree_iterator it = node.children.begin(); it != end; ++it) | |
100 | { | |
101 | if (impl::get_node_range<T>(it, node_to_search, nodes)) | |
102 | return true; | |
103 | } | |
104 | } | |
105 | return false; | |
106 | } | |
107 | ||
108 | } // end of namespace impl | |
109 | ||
110 | template <typename T> | |
111 | inline bool | |
112 | get_node_range (tree_node<T> const &node, parser_id node_to_search, | |
113 | std::pair<typename tree_node<T>::const_tree_iterator, | |
114 | typename tree_node<T>::const_tree_iterator> &nodes) | |
115 | { | |
116 | if (node.children.size() > 0) { | |
117 | typedef typename tree_node<T>::const_tree_iterator const_tree_iterator; | |
118 | ||
119 | const_tree_iterator end = node.children.end(); | |
120 | for (const_tree_iterator it = node.children.begin(); it != end; ++it) | |
121 | { | |
122 | if (impl::get_node_range<T>(it, node_to_search, nodes)) | |
123 | return true; | |
124 | } | |
125 | } | |
126 | return false; | |
127 | } | |
128 | ||
129 | /////////////////////////////////////////////////////////////////////////////// | |
130 | BOOST_SPIRIT_CLASSIC_NAMESPACE_END | |
131 | ||
132 | } // namespace spirit | |
133 | } // namespace boost | |
134 | ||
135 | #endif // !defined(PARSE_TREE_UTILS_IPP) |