1 /*=============================================================================
2 Copyright (c) 2001-2007 Hartmut Kaiser
3 Copyright (c) 2001-2003 Daniel Nuffer
4 http://spirit.sourceforge.net/
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 =============================================================================*/
11 #if !defined(PARSE_TREE_UTILS_IPP)
12 #define PARSE_TREE_UTILS_IPP
14 ///////////////////////////////////////////////////////////////////////////////
18 BOOST_SPIRIT_CLASSIC_NAMESPACE_BEGIN
20 ///////////////////////////////////////////////////////////////////////////////
22 // Returnes the first leaf node of the given parsetree.
24 ///////////////////////////////////////////////////////////////////////////////
26 inline tree_node<T> const &
27 get_first_leaf (tree_node<T> const &node)
29 if (node.children.size() > 0)
30 return get_first_leaf(*node.children.begin());
34 ///////////////////////////////////////////////////////////////////////////////
36 // Find a specified node through recursive search.
38 ///////////////////////////////////////////////////////////////////////////////
41 find_node (tree_node<T> const &node, parser_id node_to_search,
42 tree_node<T> const **found_node)
44 if (node.value.id() == node_to_search) {
48 if (node.children.size() > 0) {
49 typedef typename tree_node<T>::const_tree_iterator const_tree_iterator;
51 const_tree_iterator end = node.children.end();
52 for (const_tree_iterator it = node.children.begin(); it != end; ++it)
54 if (find_node (*it, node_to_search, found_node))
58 return false; // not found here
61 ///////////////////////////////////////////////////////////////////////////////
63 // The functions 'get_node_range' return a pair of iterators pointing at the
64 // range, which containes the elements of a specified node.
66 ///////////////////////////////////////////////////////////////////////////////
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)
76 // look at this node first
77 tree_node<T> const &node = *start;
79 if (node.value.id() == node_to_search) {
80 if (node.children.size() > 0) {
82 nodes.first = node.children.begin();
83 nodes.second = node.children.end();
89 std::advance(nodes.second, 1);
94 // look at subnodes now
95 if (node.children.size() > 0) {
96 typedef typename tree_node<T>::const_tree_iterator const_tree_iterator;
98 const_tree_iterator end = node.children.end();
99 for (const_tree_iterator it = node.children.begin(); it != end; ++it)
101 if (impl::get_node_range<T>(it, node_to_search, nodes))
108 } // end of namespace impl
110 template <typename T>
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)
116 if (node.children.size() > 0) {
117 typedef typename tree_node<T>::const_tree_iterator const_tree_iterator;
119 const_tree_iterator end = node.children.end();
120 for (const_tree_iterator it = node.children.begin(); it != end; ++it)
122 if (impl::get_node_range<T>(it, node_to_search, nodes))
129 ///////////////////////////////////////////////////////////////////////////////
130 BOOST_SPIRIT_CLASSIC_NAMESPACE_END
132 } // namespace spirit
135 #endif // !defined(PARSE_TREE_UTILS_IPP)