source: NonGTP/Boost/boost/spirit/tree/impl/parse_tree_utils.ipp @ 857

Revision 857, 4.3 KB checked in by igarcia, 19 years ago (diff)
RevLine 
[857]1/*=============================================================================
2    Copyright (c) 2001-2003 Daniel Nuffer
3    Copyright (c) 2001-2003 Hartmut Kaiser
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///////////////////////////////////////////////////////////////////////////////
15namespace boost {
16namespace spirit {
17
18///////////////////////////////////////////////////////////////////////////////
19//
20//  Returnes the first leaf node of the given parsetree.
21//
22///////////////////////////////////////////////////////////////////////////////
23template <typename T>
24inline tree_node<T> const &
25get_first_leaf (tree_node<T> const &node)
26{
27    if (node.children.size() > 0)
28        return get_first_leaf(*node.children.begin());
29    return node;
30}
31
32///////////////////////////////////////////////////////////////////////////////
33//
34//  Find a specified node through recursive search.
35//
36///////////////////////////////////////////////////////////////////////////////
37template <typename T>
38inline bool
39find_node (tree_node<T> const &node, parser_id node_to_search,
40    tree_node<T> const **found_node)
41{
42    if (node.value.id() == node_to_search) {
43        *found_node = &node;
44        return true;
45    }
46    if (node.children.size() > 0) {
47        typedef typename tree_node<T>::const_tree_iterator const_tree_iterator;
48
49        const_tree_iterator end = node.children.end();
50        for (const_tree_iterator it = node.children.begin(); it != end; ++it)
51        {
52            if (find_node (*it, node_to_search, found_node))
53                return true;
54        }
55    }
56    return false;   // not found here
57}
58
59///////////////////////////////////////////////////////////////////////////////
60//
61//  The functions 'get_node_range' return a pair of iterators pointing at the
62//  range, which containes the elements of a specified node.
63//
64///////////////////////////////////////////////////////////////////////////////
65namespace impl {
66
67template <typename T>
68inline bool
69get_node_range (typename tree_node<T>::const_tree_iterator const &start,
70    parser_id node_to_search,
71    std::pair<typename tree_node<T>::const_tree_iterator,
72        typename tree_node<T>::const_tree_iterator> &nodes)
73{
74// look at this node first
75tree_node<T> const &node = *start;
76
77    if (node.value.id() == node_to_search) {
78        if (node.children.size() > 0) {
79        // full subrange
80            nodes.first = node.children.begin();
81            nodes.second = node.children.end();
82        }
83        else {
84        // only this node
85            nodes.first = start;
86            nodes.second = start;
87            std::advance(nodes.second, 1);
88        }
89        return true;
90    }
91
92// look at subnodes now
93    if (node.children.size() > 0) {
94        typedef typename tree_node<T>::const_tree_iterator const_tree_iterator;
95
96        const_tree_iterator end = node.children.end();
97        for (const_tree_iterator it = node.children.begin(); it != end; ++it)
98        {
99            if (impl::get_node_range<T>(it, node_to_search, nodes))
100                return true;
101        }
102    }
103    return false;
104}
105
106} // end of namespace impl
107
108template <typename T>
109inline bool
110get_node_range (tree_node<T> const &node, parser_id node_to_search,
111    std::pair<typename tree_node<T>::const_tree_iterator,
112        typename tree_node<T>::const_tree_iterator> &nodes)
113{
114    if (node.children.size() > 0) {
115        typedef typename tree_node<T>::const_tree_iterator const_tree_iterator;
116
117        const_tree_iterator end = node.children.end();
118        for (const_tree_iterator it = node.children.begin(); it != end; ++it)
119        {
120            if (impl::get_node_range<T>(it, node_to_search, nodes))
121                return true;
122        }
123    }
124    return false;
125}
126
127///////////////////////////////////////////////////////////////////////////////
128}   // namespace spirit
129}   // namespace boost
130
131#endif // !defined(PARSE_TREE_UTILS_IPP)
Note: See TracBrowser for help on using the repository browser.