/*============================================================================= | |
Copyright (c) 2001-2007 Hartmut Kaiser | |
Copyright (c) 2001-2003 Daniel Nuffer | |
http://spirit.sourceforge.net/ | |
Use, modification and distribution is subject to the Boost Software | |
License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at | |
http://www.boost.org/LICENSE_1_0.txt) | |
=============================================================================*/ | |
#if !defined(PARSE_TREE_UTILS_IPP) | |
#define PARSE_TREE_UTILS_IPP | |
/////////////////////////////////////////////////////////////////////////////// | |
namespace boost { | |
namespace spirit { | |
BOOST_SPIRIT_CLASSIC_NAMESPACE_BEGIN | |
/////////////////////////////////////////////////////////////////////////////// | |
// | |
// Returnes the first leaf node of the given parsetree. | |
// | |
/////////////////////////////////////////////////////////////////////////////// | |
template <typename T> | |
inline tree_node<T> const & | |
get_first_leaf (tree_node<T> const &node) | |
{ | |
if (node.children.size() > 0) | |
return get_first_leaf(*node.children.begin()); | |
return node; | |
} | |
/////////////////////////////////////////////////////////////////////////////// | |
// | |
// Find a specified node through recursive search. | |
// | |
/////////////////////////////////////////////////////////////////////////////// | |
template <typename T> | |
inline bool | |
find_node (tree_node<T> const &node, parser_id node_to_search, | |
tree_node<T> const **found_node) | |
{ | |
if (node.value.id() == node_to_search) { | |
*found_node = &node; | |
return true; | |
} | |
if (node.children.size() > 0) { | |
typedef typename tree_node<T>::const_tree_iterator const_tree_iterator; | |
const_tree_iterator end = node.children.end(); | |
for (const_tree_iterator it = node.children.begin(); it != end; ++it) | |
{ | |
if (find_node (*it, node_to_search, found_node)) | |
return true; | |
} | |
} | |
return false; // not found here | |
} | |
/////////////////////////////////////////////////////////////////////////////// | |
// | |
// The functions 'get_node_range' return a pair of iterators pointing at the | |
// range, which containes the elements of a specified node. | |
// | |
/////////////////////////////////////////////////////////////////////////////// | |
namespace impl { | |
template <typename T> | |
inline bool | |
get_node_range (typename tree_node<T>::const_tree_iterator const &start, | |
parser_id node_to_search, | |
std::pair<typename tree_node<T>::const_tree_iterator, | |
typename tree_node<T>::const_tree_iterator> &nodes) | |
{ | |
// look at this node first | |
tree_node<T> const &node = *start; | |
if (node.value.id() == node_to_search) { | |
if (node.children.size() > 0) { | |
// full subrange | |
nodes.first = node.children.begin(); | |
nodes.second = node.children.end(); | |
} | |
else { | |
// only this node | |
nodes.first = start; | |
nodes.second = start; | |
std::advance(nodes.second, 1); | |
} | |
return true; | |
} | |
// look at subnodes now | |
if (node.children.size() > 0) { | |
typedef typename tree_node<T>::const_tree_iterator const_tree_iterator; | |
const_tree_iterator end = node.children.end(); | |
for (const_tree_iterator it = node.children.begin(); it != end; ++it) | |
{ | |
if (impl::get_node_range<T>(it, node_to_search, nodes)) | |
return true; | |
} | |
} | |
return false; | |
} | |
} // end of namespace impl | |
template <typename T> | |
inline bool | |
get_node_range (tree_node<T> const &node, parser_id node_to_search, | |
std::pair<typename tree_node<T>::const_tree_iterator, | |
typename tree_node<T>::const_tree_iterator> &nodes) | |
{ | |
if (node.children.size() > 0) { | |
typedef typename tree_node<T>::const_tree_iterator const_tree_iterator; | |
const_tree_iterator end = node.children.end(); | |
for (const_tree_iterator it = node.children.begin(); it != end; ++it) | |
{ | |
if (impl::get_node_range<T>(it, node_to_search, nodes)) | |
return true; | |
} | |
} | |
return false; | |
} | |
/////////////////////////////////////////////////////////////////////////////// | |
BOOST_SPIRIT_CLASSIC_NAMESPACE_END | |
} // namespace spirit | |
} // namespace boost | |
#endif // !defined(PARSE_TREE_UTILS_IPP) |