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#ifndef BOOST_SPIRIT_CLASSIC_TREE_IMPL_PARSE_TREE_UTILS_IPP 12#define BOOST_SPIRIT_CLASSIC_TREE_IMPL_PARSE_TREE_UTILS_IPP 13 14/////////////////////////////////////////////////////////////////////////////// 15namespace boost { 16namespace spirit { 17 18BOOST_SPIRIT_CLASSIC_NAMESPACE_BEGIN 19 20/////////////////////////////////////////////////////////////////////////////// 21// 22// Returnes the first leaf node of the given parsetree. 23// 24/////////////////////////////////////////////////////////////////////////////// 25template <typename T> 26inline tree_node<T> const & 27get_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/////////////////////////////////////////////////////////////////////////////// 39template <typename T> 40inline bool 41find_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 contains the elements of a specified node. 65// 66/////////////////////////////////////////////////////////////////////////////// 67namespace impl { 68 69template <typename T> 70inline bool 71get_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 77tree_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 110template <typename T> 111inline bool 112get_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/////////////////////////////////////////////////////////////////////////////// 130BOOST_SPIRIT_CLASSIC_NAMESPACE_END 131 132} // namespace spirit 133} // namespace boost 134 135#endif 136