| /*============================================================================= |
| 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) |