Line data    Source code

       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             : #if !defined(PARSE_TREE_UTILS_IPP)
      12             : #define PARSE_TREE_UTILS_IPP
      13             : 
      14             : ///////////////////////////////////////////////////////////////////////////////
      15             : namespace boost {
      16             : namespace spirit {
      17             : 
      18             : BOOST_SPIRIT_CLASSIC_NAMESPACE_BEGIN
      19             : 
      20             : ///////////////////////////////////////////////////////////////////////////////
      21             : //
      22             : //  Returnes the first leaf node of the given parsetree.
      23             : //
      24             : ///////////////////////////////////////////////////////////////////////////////
      25             : template <typename T>
      26             : inline tree_node<T> const &
      27           0 : get_first_leaf (tree_node<T> const &node)
      28             : {
      29           0 :     if (node.children.size() > 0)
      30           0 :         return get_first_leaf(*node.children.begin());
      31             :     return node;
      32             : }
      33             : 
      34             : ///////////////////////////////////////////////////////////////////////////////
      35             : //
      36             : //  Find a specified node through recursive search.
      37             : //
      38             : ///////////////////////////////////////////////////////////////////////////////
      39             : template <typename T>
      40             : inline bool
      41           0 : find_node (tree_node<T> const &node, parser_id node_to_search,
      42             :     tree_node<T> const **found_node)
      43             : {
      44           0 :     if (node.value.id() == node_to_search) {
      45           0 :         *found_node = &node;
      46           0 :         return true;
      47             :     }
      48           0 :     if (node.children.size() > 0) {
      49             :         typedef typename tree_node<T>::const_tree_iterator const_tree_iterator;
      50             : 
      51           0 :         const_tree_iterator end = node.children.end();
      52           0 :         for (const_tree_iterator it = node.children.begin(); it != end; ++it)
      53             :         {
      54           0 :             if (find_node (*it, node_to_search, found_node))
      55           0 :                 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 containes the elements of a specified node.
      65             : //
      66             : ///////////////////////////////////////////////////////////////////////////////
      67             : namespace impl {
      68             : 
      69             : template <typename T>
      70             : inline bool
      71           0 : 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)
      75             : {
      76             : // look at this node first
      77           0 : tree_node<T> const &node = *start;
      78             : 
      79           0 :     if (node.value.id() == node_to_search) {
      80           0 :         if (node.children.size() > 0) {
      81             :         // full subrange
      82           0 :             nodes.first = node.children.begin();
      83           0 :             nodes.second = node.children.end();
      84             :         }
      85             :         else {
      86             :         // only this node
      87           0 :             nodes.first = start;
      88           0 :             nodes.second = start;
      89           0 :             std::advance(nodes.second, 1);
      90             :         }
      91           0 :         return true;
      92             :     }
      93             : 
      94             : // look at subnodes now
      95           0 :     if (node.children.size() > 0) {
      96             :         typedef typename tree_node<T>::const_tree_iterator const_tree_iterator;
      97             : 
      98           0 :         const_tree_iterator end = node.children.end();
      99           0 :         for (const_tree_iterator it = node.children.begin(); it != end; ++it)
     100             :         {
     101           0 :             if (impl::get_node_range<T>(it, node_to_search, nodes))
     102           0 :                 return true;
     103             :         }
     104             :     }
     105             :     return false;
     106             : }
     107             : 
     108             : } // end of namespace impl
     109             : 
     110             : template <typename T>
     111             : inline bool
     112           0 : 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)
     115             : {
     116           0 :     if (node.children.size() > 0) {
     117             :         typedef typename tree_node<T>::const_tree_iterator const_tree_iterator;
     118             : 
     119           0 :         const_tree_iterator end = node.children.end();
     120           0 :         for (const_tree_iterator it = node.children.begin(); it != end; ++it)
     121             :         {
     122           0 :             if (impl::get_node_range<T>(it, node_to_search, nodes))
     123           0 :                 return true;
     124             :         }
     125             :     }
     126             :     return false;
     127             : }
     128             : 
     129             : ///////////////////////////////////////////////////////////////////////////////
     130             : BOOST_SPIRIT_CLASSIC_NAMESPACE_END
     131             : 
     132             : }   // namespace spirit
     133             : }   // namespace boost
     134             : 
     135             : #endif // !defined(PARSE_TREE_UTILS_IPP)