tree/impl/parse_tree_utils.ipp

0001 /*=============================================================================
0002     Copyright (c) 2001-2007 Hartmut Kaiser
0003     Copyright (c) 2001-2003 Daniel Nuffer
0004     http://spirit.sourceforge.net/
0005
0006     Use, modification and distribution is subject to the Boost Software
0007     License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0008     http://www.boost.org/LICENSE_1_0.txt)
0009 =============================================================================*/
0010
0011 #ifndef BOOST_SPIRIT_CLASSIC_TREE_IMPL_PARSE_TREE_UTILS_IPP
0012 #define BOOST_SPIRIT_CLASSIC_TREE_IMPL_PARSE_TREE_UTILS_IPP
0013
0014 ///////////////////////////////////////////////////////////////////////////////
0015 namespace boost {
0016 namespace spirit {
0017
0018 BOOST_SPIRIT_CLASSIC_NAMESPACE_BEGIN
0019
0020 ///////////////////////////////////////////////////////////////////////////////
0021 //
0022 //  Returnes the first leaf node of the given parsetree.
0023 //
0024 ///////////////////////////////////////////////////////////////////////////////
0025 template <typename T>
0026 inline tree_node<T> const &
0027 get_first_leaf (tree_node<T> const &node)
0028 {
0029     if (node.children.size() > 0)
0030         return get_first_leaf(*node.children.begin());
0031     return node;
0032 }
0033
0034 ///////////////////////////////////////////////////////////////////////////////
0035 //
0036 //  Find a specified node through recursive search.
0037 //
0038 ///////////////////////////////////////////////////////////////////////////////
0039 template <typename T>
0040 inline bool
0041 find_node (tree_node<T> const &node, parser_id node_to_search,
0042     tree_node<T> const **found_node)
0043 {
0044     if (node.value.id() == node_to_search) {
0045         *found_node = &node;
0046         return true;
0047     }
0048     if (node.children.size() > 0) {
0049         typedef typename tree_node<T>::const_tree_iterator const_tree_iterator;
0050
0051         const_tree_iterator end = node.children.end();
0052         for (const_tree_iterator it = node.children.begin(); it != end; ++it)
0053         {
0054             if (find_node (*it, node_to_search, found_node))
0055                 return true;
0056         }
0057     }
0058     return false;   // not found here
0059 }
0060
0061 ///////////////////////////////////////////////////////////////////////////////
0062 //
0063 //  The functions 'get_node_range' return a pair of iterators pointing at the
0064 //  range, which contains the elements of a specified node.
0065 //
0066 ///////////////////////////////////////////////////////////////////////////////
0067 namespace impl {
0068
0069 template <typename T>
0070 inline bool
0071 get_node_range (typename tree_node<T>::const_tree_iterator const &start,
0072     parser_id node_to_search,
0073     std::pair<typename tree_node<T>::const_tree_iterator,
0074         typename tree_node<T>::const_tree_iterator> &nodes)
0075 {
0076 // look at this node first
0077 tree_node<T> const &node = *start;
0078
0079     if (node.value.id() == node_to_search) {
0080         if (node.children.size() > 0) {
0081         // full subrange
0082             nodes.first = node.children.begin();
0083             nodes.second = node.children.end();
0084         }
0085         else {
0086         // only this node
0087             nodes.first = start;
0088             nodes.second = start;
0089             std::advance(nodes.second, 1);
0090         }
0091         return true;
0092     }
0093
0094 // look at subnodes now
0095     if (node.children.size() > 0) {
0096         typedef typename tree_node<T>::const_tree_iterator const_tree_iterator;
0097
0098         const_tree_iterator end = node.children.end();
0099         for (const_tree_iterator it = node.children.begin(); it != end; ++it)
0100         {
0101             if (impl::get_node_range<T>(it, node_to_search, nodes))
0102                 return true;
0103         }
0104     }
0105     return false;
0106 }
0107
0108 } // end of namespace impl
0109
0110 template <typename T>
0111 inline bool
0112 get_node_range (tree_node<T> const &node, parser_id node_to_search,
0113     std::pair<typename tree_node<T>::const_tree_iterator,
0114         typename tree_node<T>::const_tree_iterator> &nodes)
0115 {
0116     if (node.children.size() > 0) {
0117         typedef typename tree_node<T>::const_tree_iterator const_tree_iterator;
0118
0119         const_tree_iterator end = node.children.end();
0120         for (const_tree_iterator it = node.children.begin(); it != end; ++it)
0121         {
0122             if (impl::get_node_range<T>(it, node_to_search, nodes))
0123                 return true;
0124         }
0125     }
0126     return false;
0127 }
0128
0129 ///////////////////////////////////////////////////////////////////////////////
0130 BOOST_SPIRIT_CLASSIC_NAMESPACE_END
0131
0132 }   // namespace spirit
0133 }   // namespace boost
0134
0135 #endif