projects / ceph.git / blame
| Commit | Line | Data |
|---|---|---|
| 7c673cae FG |
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 | ||
| f67539c2 TL |
11 | #ifndef BOOST_SPIRIT_CLASSIC_TREE_IMPL_PARSE_TREE_UTILS_IPP |
| 12 | #define BOOST_SPIRIT_CLASSIC_TREE_IMPL_PARSE_TREE_UTILS_IPP | |
| 7c673cae FG |
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 | get_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 | /////////////////////////////////////////////////////////////////////////////// | |
| 39 | template <typename T> | |
| 40 | inline bool | |
| 41 | find_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 | |
| f67539c2 | 64 | // range, which contains the elements of a specified node. |
| 7c673cae FG |
65 | // |
| 66 | /////////////////////////////////////////////////////////////////////////////// | |
| 67 | namespace impl { | |
| 68 | ||
| 69 | template <typename T> | |
| 70 | inline bool | |
| 71 | 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 | tree_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 | ||
| 110 | template <typename T> | |
| 111 | inline bool | |
| 112 | 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 | 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 | /////////////////////////////////////////////////////////////////////////////// | |
| 130 | BOOST_SPIRIT_CLASSIC_NAMESPACE_END | |
| 131 | ||
| 132 | } // namespace spirit | |
| 133 | } // namespace boost | |
| 134 | ||
| f67539c2 | 135 | #endif |